基于遗传算法的可逆逻辑综合方法及其CUDA并行化实现

摘要

随着集成电路的规模和集成度的不断增加，集成电路的功耗问题日益突出，现已成为制约集成电路进一步发展的瓶颈。集成电路的功耗主要来自于计算过程中的不可逆操作，可逆逻辑电路是仅包含可逆操作的新型电路，可以根除源于信息损失的能耗和发热，是研究和实现超低功耗集成电路、量子计算机等的基础和关键，业已成为国际性的研究热点。
　　可逆逻辑综合就是利用给定的可逆逻辑门，按照可逆网络无扇入扇出、无反馈等约束条件和限制，实现具备预期逻辑功能且尽可能优化的可逆逻辑电路。一类常见的可逆逻辑综合方法，其先设法生成具备预期逻辑功能的可逆逻辑电路，再在不改变其函数功能的前提下，通过重组、变换等技术，对其进行门数、量子代价等方面的优化。另一类常见方法则将电路生成与电路优化结合在一起，并且已经成为综合方法的主流。本文所研究的基于遗传算法的可逆逻辑综合方法，就是一种将生成与优化同时进行的可逆逻辑综合方法，其基本思路是将可逆逻辑电路编码为染色体，根据预期的逻辑功能和优化目标等评估适应度，利用遗传算法的全局寻优能力来找出功能正确、代价最小的可逆逻辑电路。
　　为了实现较大规模、较复杂可逆逻辑电路的综合、优化，本文还研究和采用了GPU通用计算技术——CUDA并行计算架构。GPU的并行计算架构是为计算密集型、高强度并行计算而设计的，特别适合处理那些具有较高算法强度且可以表达为并行计算的问题。CUDA是NVIDIA公司基于其推出的先进GPU系列，经过对C语言做相应扩展后推出的GPU通用计算开发套件，可大大减小并行化程序的开发难度，为GPU通用计算提供了一种高效、便捷的开发平台。
　　本文首先研究和编程实现了基本遗传算法，并通过函数优化实验对其进行了初步验证。其次，本文研究和编程实现了基于遗传算法的可逆逻辑综合方法，其特点是预先将多位可逆逻辑门（Toffoli门）的不同组态分别编码并存储，以“定轨级联”作为基本电路结构，相应地表达可逆逻辑电路的染色体便由等于其中所含各可逆逻辑门的编码串拼接而成，按照预期的逻辑功能和优化目标等评估适应度，再利用选择、交叉、变异等遗传算子和迭代过程，逐步找到功能正确、性能最优的可逆逻辑电路。最后，利用CUDA技术，对上述综合算法进行并行化改造和编程实现，获得了基于遗传算法和CUDA技术的可逆逻辑并行综合算法和程序。文中给出实验结果证明了该算法的可行性和有效性。从原理上讲，该算法同样适用于其他的可逆逻辑门库及其构成的电路，因而具有一定的参考和推广价值。

目录

声明

摘要

第1章 绪论

1．1 课题研究背景及意义

1．2 国内外研究现状

1．3 本文主要内容及论文结构

第2章 可逆逻辑电路基础

2．1 可逆逻辑电路概述

2．1．1 可逆逻辑与可逆计算

2．1．2 可逆逻辑电路的主要指标

2．2 常用可逆逻辑门

2．2．1 一位可逆逻辑门

2．2．2 多位可逆逻辑门

2．3 可逆逻辑电路综合方法

2．3．1 主要可逆逻辑电路综合方法

2．3．2 优缺点对比

第3章 CUDA开发基础

3．1 GPU发展简介

3．2 CUDA编程模型

3．2．1 主机端和设备端

3．2．2 线程层次

3．3 CUDA存储模型

3．4 CUDA软件体系结构

3．5 CUDA软件开发方法及流程

第4章 遗传算法的实现及验证

4．1 遗传算法

4．1．1 遗传算法简介

4．1．2 遗传算法操作流程

4．2 遗传算法的实现

4．2．1 适应度函数确定

4．2．2 编码方案确定

4．2．3 解码方案确定

4．2．4 选择算子

4．2．5 交叉算子

4．2．6 变异算子

4．2．7 遗传算法运行参数设定

4．2．8 实验结果分析

4．3 遗传算法的验证

第5章 可逆逻辑进化设计方法及其CUDA并行化实现

5．1 可逆逻辑电路遗传算法模型建立

5．1．1 概念与术语

5．1．2 Toffoli门的编码

5．1．3 Toffoli门真值表生成

5．1．4 适应度评估

5．2 遗传算法的并行化模型

5．3 遗传算子的并行化实现

5．3．1 并行选择算子

5．3．2 并行交叉算子

5．3．3 并行变异算子

5．3．4 最优保存策略

第6章 可逆逻辑并行进化设计实验的结果与分析

6．1 开发与实验平台介绍

6．2 CUDA开发环境的搭建

6．2．1 准备工作

6．2．2 环境变量设置

6．2．3 建立CUDA项目

6．3 四输入可逆逻辑电路实验示例

6．4 六输入可逆逻辑电路实验示例

6．5 七输入可逆逻辑电路实验示例

6．6 CUDA并行化效率分析

第7章 总结与展望

7．1 工作总结

7．2 展望

参考文献

攻读学位期间的研究成果

致谢