关键词:
可逆计算
可逆化模拟
动态集合
数据结构
节能计算
摘要:
随着信息产业的飞速发展和其在世界经济结构中地位的不断上升,计算与通信所带来的能源消耗也受到了更广泛的关注。早期人们主要通过优化电路结构或硬件架构来降低计算机的能耗,然而由于半导体技术本身有着各种潜在障碍,其发展也很快将到达拐点。而且从长远来看能耗的增长终将到达极限,到那时,人们需要使用新的技术来代替半导体。因此,本文将从计算能耗的产生根源进行考虑,以寻找能效更优的计算方法。Landauer极限定义了计算机“擦除”一个比特的信息至少需要消耗的能量。同半导体技术的发展一样,若不从根本上解决问题,Landauer极限总有一天会被触及,而可逆计算便是使Landauer极限失效的唯一方式。可逆计算指计算过程中的操作能够根据其输出状态推断出输入状态,从而避免“擦除”操作以降低能耗。然而现在通用计算机上很多操作是不可逆的,因此Bennett提出记录“历史操作”的方法来使不可逆操作转换为可逆操作,但需要消耗额外的空间,我们称为冗余(garbage)空间。传统的不可逆算法中通常都存在不可逆的操作,因此在对传统算法进行可逆化时,需要消耗冗余空间来保证算法的可逆性。为了降低冗余空间,本文设计可逆化方法,在保证时间复杂度不变的前提下,使可逆算法的冗余空间复杂度最优。另一方面,动态集合作为计算机程序的基础数据结构,有着广泛且非常关键的应用。动态集合在算法操作的过程中常常伴随着缩小、增大或发生其它的变化,非常灵活,很难进行可逆化。不同的算法需要对动态集合执行各种不同的操作,因此本文针对动态集合进行可逆化,这将为算法可逆化奠定基础。本文通过Janus语言及其模拟平台,对存储动态集合的数据结构进行了可逆化设计和模拟实现,不仅包含基本数据结构栈、队列和链表,还包括高级数据结构van Emde Boas树及与其设计相关的直接寻址、叠加的二叉树结构、叠加的一棵高度恒定的树及原型van Emde Boas结构,在保证时间复杂度不变的前提下,使这八种数据结构的可逆化达到了最优的冗余空间复杂度。本文还在可逆化过程中实现了对这些数据结构的数组表示。