基于Hyper-heuristic的纳米芯片设计关键算法研究

当电子器件缩小到纳米尺度时，CMOS技术将达到其物理极限，纳电子器件的出现使得摩尔定律有可能继续有效。基于纳米技术的纳米芯片设计是IC设计的一个新的发展方向，其中许多新的设计问题都属于复杂的、大规模组合优化问题，传统的基于CMOS的设计工具不再适用。Hyper-heuristic是一类新的启发式算法框架，其特点是对不同问题具有很好的自适应性，同时具有较高的求解效率和求解质量。本课题基于hyper-heuristic算法框架，研究纳米芯片设计中的关键问题及其算法，重点研究基于可重构纳米crossbar结构的容缺陷逻辑映射问题及其算法，基于QCA多数门的逻辑综合问题及其算法，以及针对错误率动态变化的容错设计问题及其算法等。本课题的研究将为纳米芯片设计提供必要的算法支持，具有重要的学术意义和应用前景。

当电子器件缩小到纳米尺度时，CMOS 技术将达到其物理极限，基于纳米技术的纳米芯片设计是IC 设计的一个新的发展方向。新的自下而上的制造工艺和极小的器件尺寸，决定了未来纳米芯片不可避免地会存在高缺陷率和高错误率。针对纳米芯片的新特点，研究容缺陷和容错设计方法具有重要的意义。本项目针对纳米芯片的高缺陷率和高错误率问题，基于Hyper-heuristic算法框架，研究相关的容缺陷和容错设计方法，主要工作和成果包括：（1）系统深入地研究了基于可重构纳米Crossbar 结构的容缺陷逻辑设计方法。(a) 通过引入最大二分匹配（MBM），首次把容缺陷逻辑映射问题建模为组合优化问题；提出一种新颖的基于适应度近似的Memetic算法（MA/FA），在获得好的优化质量的同时，有效降低了算法的计算代价。相关论文发表在本领域顶级期刊IEEE TEVC上。(b) 为解决此前算法映射成功率低的问题，提出多样性映射的概念以及三种多样性容缺陷逻辑映射算法。与此前发表的最好算法的对比实验表明，映射成功率得到大幅度提高，尤其是在大规模问题方面上改进尤为明显。相关工作得到国际同行的关注。(c) 首次给出了容缺陷逻辑映射问题数学形式的公式化定义，定义了一个新的加权覆盖率作为算法的评估标准，并验证了其合理性。基于此，提出一种基于遗传算法（GA）的有效的覆盖率优化算法。(d)提出了新的无缺陷子结构提取算法，与此前最好算法比较，在求解质量相当的情况下，显著降低了算法的时间复杂度。（2）对基于冗余分配机制的容错设计算法进行了研究，针对多层多模块串并联复杂结构系统，提出了基于广度memetic算法的冗余资源分配算法，取得了较好的实验结果。（3）基于Hyper-heuristic算法框架，系统深入地研究了面向大规模优化问题的演化算法，提出了两阶段集成演化算法和两阶段集成Memetic算法，并将其很好地用于数值优化和工程应用问题的求解。（4）对基于QCA 多数门的逻辑综合问题及其算法进行了研究。