基于单元分类的CMOL常开缺陷单元容错映射

顾贤贵, 夏银水

基于单元分类的CMOL常开缺陷单元容错映射

顾贤贵, 夏银水*

（宁波大学 信息科学与工程学院, 浙江 宁波 315211）

CMOS纳米分子混合电路(CMOS/nanowire/MOLeclular hybrid circuits, CMOL)在制造过程中会引入较高缺陷率, 从而导致可用映射资源的减少. 针对由此产生的映射困难问题, 本文采用单元分类思想, 对部分缺陷单元加以利用, 以增加可映射单元数, 进而提高映射成功率. 首先根据单元缺陷类型的差异, 将缺陷单元分为可用和不可用两类进行标记, 然后对可用缺陷单元加以利用, 并采用改进的进化算法完成单元容错映射. 实验结果表明, 与已有方法相比, 新方法在运行效率和成功率上分别得到了19.17%和30.14%的提升.

CMOL; 进化算法; 单元容错映射

随着CMOS器件特征尺寸的不断缩小, 量子效应加剧, 制造成本飞涨等问题日益凸显, 使CMOS工艺的发展面临着前所未有的挑战[1]. CMOL电路因兼具CMOS电路丰富的逻辑功能和纳米器件的高集成度, 受到了国内外专家学者的广泛关注. 研究表明, 在功耗可控情况下, CMOL电路每秒每平方厘米的运算次数可达1020次, 被认为是后摩尔时代最具前景的CMOS替代工艺之一[2]. 然而, 自底向上自组装而成的CMOL电路在制造过程中因界面引脚与纳米线难以精确校准, 及纳米器件尺寸极度缩小等原因, 常会引入10-3~10-1大小的缺陷率, 这远高于传统CMOS电路10-9~10-7大小的缺陷率, 因此, CMOL单元容错映射方法研究是CMOL工艺迈向实用化进程的必要条件之一[3].

CMOL电路的单元容错映射通常分为两步进行. 首先考虑连通域约束, 完成无缺陷单元映射, 然后再考虑缺陷情况以及连通域约束, 完成单元容错映射. 其中, CMOL电路缺陷类型通常可分为两类: 常开缺陷(stuck-at-open defects)和常连缺陷(stuck-at-close defects). 迄今为止, 针对常开缺陷的单元容错映射工作已取得较大进展[4-7], 但针对常连缺陷的单元容错映射研究则相对较少[8-9]. Hung等[8]将单元容错映射问题转变可满足性问题, 并将提出的容错策略转化为布尔约束, 采用一种称为MINISAT的CHAFF型SAT求解器进行CMOL单元容错映射的求解工作, 但该方法存在求解效率低, 电路求解规模小等问题. 后续研究表明, 常连缺陷存在缺陷传播现象, 对此, Chen等[9]提出一种有效的常连缺陷传播阻断方法, 利用反相器对的互补信号阻断常连缺陷传播路径, 但引入的反相器对易造成电路时延退化.

上述工作共同之处在于均采用舍弃策略处理缺陷单元, 但随缺陷率的提高, 可映射资源减少造成电路映射成功率急剧降低. 针对此问题, 本文提出单元分类思想, 根据单元缺陷类型的差异, 将缺陷单元分为可用和不可用两类, 并进行标记. 对不可用缺陷单元进行舍弃, 而对可用缺陷单元加以利用, 同时采用改进的进化算法完成CMOL常开缺陷的单元容错映射. 结果表明, 新方法能够快速有效的完成CMOL电路的单元容错映射.

1 CMOL结构与单元容错映射

1.1 CMOL结构

图1 CMOL结构[1]

1.2 CMOL单元容错映射

其中,表示电路节点(逻辑门)集合;表示电路节点连接边集合;(g)表示电路节点g所映射的CMOL单元;dist表示2个CMOL单元之间的曼哈顿距离;表示连通域半径. 式(1)说明每个CMOL单元能且只能被1个电路节点所映射; 式(2)表示有连接关系的2个电路节点所映射单元之间的距离必须满足连通域约束.

在无缺陷映射阶段, 得到满足式(1)、(2)的初始映射解, 然后在该解中加入缺陷信息, 通过单元重构完成CMOL单元容错映射[4,9].

本文涉及的缺陷类型表述如下:

(1)纳米二极管常开. 纳米二极管无法正常开启, 致使其连接的2条纳米线所处单元之间的信号通路被阻断.

(2)纳米线非周期性断裂. 纳米线发生不规则断裂, 致使其所处单元的可连接单元数减少.

(3)CMOS反相器常开. 连接CMOS反相器的界面引脚未与纳米线精确对准, 致使其所在单元无法实现逻辑非功能.

在CMOL电路中正是由于上述常开缺陷的存在, 使得原本可连接的2个CMOL单元之间的信号通路被阻断, 或无法完成相应的逻辑运算. CMOL单元容错映射就是一个在连通域约束下, 通过一定方法消除缺陷影响, 从而保证映射电路逻辑功能正确的过程.

2 基于单元分类的CMOL单元容错映射

2.1 CMOL单元分类与标记

在CMOL电路中, 每个CMOL单元可看作由CMOS反相器、输入/输出纳米线以及纳米二极管三部分组成, 如果其中任一部分发生缺陷, 那么该CMOL单元则被视为一个缺陷单元. 但不同的常开缺陷所产生的影响也有所不同, 其中, CMOS反相器常开意味着该反相器所组成的CMOL单元无法实现逻辑非功能, 所以此类缺陷单元无法被利用. 结合CMOL电路结构, 每个纳米二极管唯一确定2条正交纳米线, 每条纳米线唯一确定1个CMOL单元, 纳米二极管常开造成其所连接的2条纳米线所确定的2个CMOL单元之间的信号通路被阻断, 但这2个单元仍可与其他单元进行连接, 并构成信号通路, 因此此类缺陷单元可被利用. 同时, 纳米线非周期性断裂表示纳米线在非周期性断点处发生不规则断裂, 此类缺陷仅造成纳米线唯一确定CMOL单元的可连接单元数减少, 所以此类缺陷单元也可被利用. 综上所述, 根据CMOL单元是否发生缺陷以及发生缺陷时的影响差异, 可将单元分为以下三类: 无缺陷单元、可用缺陷单元和不可用缺陷单元. 其中,

(1)无缺陷单元: 表示该CMOL单元未发生任意一种常开缺陷;

(2)不可用缺陷单元: 表示该CMOL单元发生CMOS反相器常开缺陷;

(3)可用缺陷单元: 表示该CMOL单元的纳米二极管常开, 或纳米线非周期性断裂, 但不存在CMOS反相器常开缺陷.

算法1(CMOL单元分类与标记)

2.2 可用缺陷单元的映射约束与重构

针对不可用缺陷单元, 因其无法进行逻辑运算, 所以在单元容错映射阶段需要将其舍弃, 即不可被任何电路节点所映射. 针对可用缺陷单元, 由于其CMOS反相器功能是正常的, 仍可完成相应的逻辑运算, 所以其依然可被电路节点所映射. 但任意2个可用缺陷单元和, 如果在彼此的输入/输出连通域内, 那么在单元映射过程中将可能出现以下4种情况:

(1)、均未被电路节点所映射;

(2)、其中一个被电路节点映射, 而另一个未被映射;

(3)、两者都被电路节点映射, 但映射的电路节点不存在连接关系;

(4)、两者都被电路节点映射, 但映射的电路节点存在连接关系.

由于可用缺陷单元和之间无法构成信号通路, 这就要求两者不能被具有连接关系的电路节点和同时映射. 因此, 上述第4种情况会因信号通路阻断而出现逻辑错误, 其他3种情况因单元和之间不存在信号传输, 故不会导致逻辑错误. 因此, 在单元映射过程中, 为防止第4种情况出现, 需要对在彼此输入/输出连通域内的2个可用缺陷单元的映射进行约束施加, 表述如下:

算法2(可用缺陷单元的重构判定)

图2 单元重构

2.3 算法实现

进化算法具体实现以适值函数、选择策略和遗传算子三部分做详细说明.

2.3.1 适值函数

适值是度量个体性能状态优良情况的重要参数. 在CMOL单元容错映射中, 每一个电路映射结果可视为一个体, 使用本课题组的LRMA算法[10]生成个体构成初始种群. 个体违反约束(3)(4)的个数越少, 性状越优; 否则, 性状越差. 适值函数定义如下:

其中,表示逻辑电路的节点总数;表示电路节点所映射单元连通域内的单元总数;penalty(c,c)表示电路节点所映射单元与其连通域内单元之间违反约束(3)(4)的惩罚因子, 其中,

2.3.2 选择策略

选择策略决定着种群演化方向. 为确保性能状态优的个体有较大概率, 同时性能状态差的个体也有不为零的概率被选择进行遗传操作, 需采用线性排名结合轮盘赌策略进行个体选择. 首先计算种群所有个体适值, 并进行升序排列. 记种群规模为, 则性状最优个体编号为, 且设定计算值为max, 性状最差个体编号为1, 且设定计算值为min(minp:

随后对所有个体的计算值p进行归一化处理, 得到个体选择概率q,

根据q进行轮盘选择, 令

2.3.3 遗传算子

图3 二维染色体交叉

在进化算法中, 变异算子的主要功能是拓宽算法的选择空间, 以防止陷入局部最优, 因此变异阶段的单元互换不存在连通域约束检查机制. 此外, 单元变异率过高则可能导致算法无法收敛, 过低则可能限制了算法的求解能力, 所以本文设定变异算子仅在种群中性状最优个体的适值未得到改进的情况下被激活实施. 在CMOL单元容错映射过程中, 变异只会造成映射电路结构微小的变化, 即在染色体中随机选取2个基因进行位置互换. 图4所示为二维染色体变异示意图, 其中存在2种变异类型: (1)若2个单元都已被电路节点所映射, 则互换位置, 如图4(a)所示, 将电路节点4和8位置互换; (2)若2个单元其中一个为空白单元, 则将电路节点重新映射于空白单元上即可, 如图4(b)所示, 将电路节点7重新映射于箭头所指单元上.

图4 二维染色体变异

综上所述, 给出基于单元分类的CMOL单元容错映射伪代码的算法3.

算法3(基于单元分类的CMOL单元容错映射)

3 实验结果

实验结果见表1. 其中,“单元”表示标准测试电路节点总数; “时间”表示得到可行解时程序的运行时间; “线长”表示映射电路互连线长度总和; “成功率”表示100次试验中成功得到映射解的概率;“平均值”表示不同参数的平均值;“提高量”表示提出方法与比较文献的改进百分比. 同时选取了2篇在CMOL常开缺陷单元容错映射领域具有代表性的文献(SimE[4]和DUM[7])进行实验对比. 由表中数据可见, 与SimE相比, 本文方法得到了26.42%的时间和2.77%的线长优化. 但线长优化效果不明显, 主要原因是新方法在进化算法变异阶段不存在连通域约束检查机制, 导致映射解中存在部分违反连通域约束情况, 对此需要引入反相器对进行路由拓展而产生额外的线长消耗[12]. 与DUM相比, 得到了19.17%的时间和30.14%的成功率提升, 线长却存在27.31%的退化. 这主要是因为DUM采用缺陷无意识的映射方法, 即在×大小的缺陷CMOL阵列中提取出一块×(<)大小的无缺陷子阵列, 然后在该无缺陷子阵列中进行单元映射, 与此不同的是, 新方法在整个×大小的缺陷阵列中寻找映射解. 因此得到最终映射解的紧凑程度要低于DUM, 而线长是反应电路映射紧凑程度的重要指标, 映射结果越紧凑, 线长越小, 反之, 线长越大. 本文将缺陷单元细分为可用和不可用两类, 对可用缺陷单元加以利用, 映射资源的增加使算法更易找到有效解, 这是求解效率得到提升的主要原因.

表1 不同方法实验结果比较

4 结语

针对CMOL常开缺陷的单元容错映射问题, 本文采用缺陷单元分类处理思想, 提高了单元利用率从而提高了映射效率和求解成功率. 但提出方法仅限于常开缺陷的容错映射, 因此涵盖常开与常连缺陷的方法研究是未来的主要研究方向.

[1] Likharev K K, Strukov D B. CMOL: Devices, Circuits and Architectures[M]. Lecture Notes in Physics. Heidelberg: Springer, 2005.

[2] Lu W, Lieber C M. Nanoelectronics from the bottom up[J]. Nature Materials, 2007, 6(11):841-850

[3] Yan H, Choe H S, Nam S W, et al. Programmable nanowire circuits for nanoprocessors[J]. Nature, 2011, 470(7333):240-244.

[4] Sait S M, Arafeh A M. Reconfiguration-based defect- tolerant design automation for hybrid CMOS/nanofabrics circuits using evolutionary and non-deterministic heuris- tics[J]. Arabian Journal for Science and Engineering, 2015, 40(9):1-15.

[5] Zha X, Xia Y. Genetic algorithm based on divide-and- conquer strategy for defect-tolerant CMOL mapping[C]. Proceedings of the 12th IEEE International Conference on ASIC. Los Alamitos: IEEE Computer Society Press, 2017:863-866.

[6] 汪纪波, 夏银水, 储著飞, 等. 基于门节点分级选择的CMOL电路单元快速容错映射[J]. 计算机辅助设计与图形学学报, 2017, 29(1):172-179.

[7] 陈定亨, 夏银水, 储著飞. 缺陷无意识的CMOL单元容错映射[J]. 计算机辅助设计与图形学学报, 2017, 29 (11):2133-2139.

[8] Hung W N N, Gao C, Song X, et al. Defect-tolerant CMOL cell assignment via satisfiability[J]. IEEE Sensors Journal, 2008, 8(6):823-830.

[9] Chen D, Xia Y, Wang Z. Stuck-at-close defect propagation and its blocking technique in CMOL cell mapping[J]. Microelectronics Journal, 2018, 72(2):100- 108.

[10] Xia Y, Chu Z, Hung W N N, et al. An integrated optimization approach for nanohybrid circuit cell mapping[J]. IEEE Transactions on Nanotechnology, 2011, 10(6):1275-1284.

[11] Brglez F, Bryan D, Koźmiński K. Combinational profiles of sequential benchmark circuits[C]. Proceedings of IEEE International Symposium on Circuits and Systems. Los Alamitos: IEEE Computer Society Press, 1989:1929- 1934.

[12] Chu Z, Xia Y, Hung W N N, et al. Timing-driven logic restructuring for nano-hybrid circuits[J]. International Journal of Electronics, 2013, 100(5):669-685.

Cell classification based CMOL stuck-at-open defect-tolerant cell mapping

GU Xiangui, XIA Yinshui*

( Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China )

To tackle the problem of high defect rate in CMOS/nanowire/MOLeclular hybrid circuits (CMOL), a cell classification based defect-tolerant cell mapping method is proposed. First, recoverable and unrecoverable defective cells are marked, and the recoverable defective ones are put to use again. Then, a modified evolutionary algorithm is used to complete the defect-tolerant cell mapping. Compared with the existing approaches, the CPU time and success rate using the proposed method are optimized to 19.17% and 30.14%, respectively.

CMOL; evolutionary algorithm; defect-tolerant cell mapping

TP391.41

A

1001-5132（2020）01-0051-07

2019−07−22.

宁波大学学报（理工版）网址: http://journallg.nbu.edu.cn/

国家自然科学基金（61571248）.

顾贤贵（1995－）, 男, 浙江宁波人, 在读硕士研究生, 主要研究方向: 逻辑电路综合与优化. E-mail: 1014406105@qq.com

夏银水（1963－）, 男, 浙江余姚人, 研究员, 主要研究方向: 集成电路综合与优化. E-mail: xiayinshui@nbu.edu.cn

（责任编辑 章践立）