基于可满足性模理论的CMOL电路单元映射
PDF下载 (831)金俊杰,储著飞*,王伦耀,夏银水.基于可满足性模理论的CMOL电路单元映射[J].宁波大学学报(理工版),2018,31(6):7-11.DOI:
JIN Jun-jie,CHU Zhu-fei*,WANG Lun-yao,XIA Yin-shui.CMOL cell mapping based on satisfiability modulo theory[J].Journal of Ningbo University(Natural Science & Engineering Edition),2018,31(6):7-11.DOI:
| Title: | CMOL cell mapping based on satisfiability modulo theory |
| 作者: | 金俊杰, 储著飞*, 王伦耀, 夏银水 |
| Author(s): | JIN Jun-jie, CHU Zhu-fei*, WANG Lun-yao, XIA Yin-shui |
| 关键词: | CMOL电路; 单元映射; 精确算法 |
| Keywords: | CMOL circuit; cell mapping; exact algorithm |
| 分类号: | TP391 |
| 文献标识码: | A |
| 摘要: | 针对纳米CMOS混合电路(CMOL)单元映射时, 传统的精确算法存在编码变量多、文件存储大导致的求解规模受限问题, 提出了一种基于可满足性模理论(SMT)的CMOL电路单元映射方法, 该方法通过整型编码减小文件存储大小, 通过渐进式求解算法兼顾求解规模和速度. 实验结果表明, 与传统的精确算法相比, 本文提出的方法可大幅减少中间处理文件的大小, 并以较小的求解速度为代价提高了处理大规模电路的能力. |
| Abstract: | Traditional exact algorithm methods require a vast number of variables and files of large size during CMOL cell mapping, which severely limits the algorithm scalability. To address this problem, a CMOL cell mapping method is proposed based on Satisfiability Modulo Theory (SMT). Instead of using binary variables, the proposed method makes use of integer variables to reduce the number of required variables and simplify the expression of constraints, which in turn significantly cuts the file size. Moreover, we adopt incremental solving strategy to seek both solution scale and CPU time by reducing the number of constraints and narrowing the range of variables. Experimental results show that the proposed method possesses better scalability with more affordable CPU time cost than traditional precision methods. |
| 参考文献 /References: | [1] Likharev K K, Strukov D B. CMOL: devices, circuits, and architectures[J]. Lecture Notes in Physics, 2006, 680:447-477. [2] Strukov D B, Likharev K K. A reconfigurable architecture for hybrid CMOS/Nanodevice circuits[C]//International Symposium on Field Programmable Gate Arrays, 2006: 131-140. [3] Xia Y, Chu Z, Hung N N, et al. An integrated optimization approach for nanohybrid circuit cell mapping[J]. IEEE Transactions on Nanotechnology, 2011, 10(6):1275-1284. [4] Sait S M, Arafeh A M. Efficient CMOL nanoscale hybrid circuit cell assignment using simulated evolution heuristic[C]//Proceedings of the Great Lakes Symposium on VLSI, 2012:21-26. [5] Arafeh A M, Sait S M. Cells reconfiguration around defects in CMOS/nanofabric circuits using simulated evolution heuristic[C]//International Symposium on Quality Electronic Design, 2015:581-588. [6] Sait S M, Oughali F C, Arafeh A M. Engineering a memetic algorithm from discrete cuckoo search and tabu search for cell assignment of hybrid nanoscale CMOL circuits[EB/OL]. [2018-01-08]. https://www.researchgate. net/publication/283903226. [7] 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. [8] 王先建, 王伦耀, 储著飞, 等. 基于伪布尔可满足性的纳米CMOS电路单元配置[J]. 电子与信息学报, 2012, 34(10):2508-2513. [9] Kumar V. Algorithms for constraint-satisfaction problems: A survey[J]. Menlo Park, 1992, 13(1):32-44. [10] Moura L D, Bjørner N. Satisfiability modulo theories: An appetizer[J]. Lecture Notes in Computer Science, 2009, 5902:23-36. [11] Tille D, Eggersgluss S, Drechsler R. Incremental solving techniques for SAT-based ATPG[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(7):1125-1130. [12] Liu D, Yu C, Zhang X, et al. Oracle-guided incremental SAT solving to reverse engineer camouflaged logic circuits[C]//Design, Automation & Test in Europe Conference & Exhibition, 2016:433-438. [13] Yamada A, Kitamura T, Artho C, et al. Optimization of combinatorial testing by incremental SAT solving[C]// International Conference on Software Testing, Verification and Validation, 2015:1-10. [14] Berre D L, Parrain A. The SAT4J library, release 2.2 system description[J]. Journal on Satisfiability, Boolean Modeling and Computation, 2010, 7:59-64. |
| 备注/Memo: | 收稿日期: 2018?04?12. 宁波大学学报（理工版）网址: http://journallg.nbu.edu.cn/ 基金项目: 国家自然科学基金（61501268, 61471211, 61571248）. 第一作者: 金俊杰（1991－）, 男, 安徽安庆人, 在读硕士研究生, 主要研究方向: 集成电路设计自动化. E-mail: 983879593@qq.com *通信作者: 储著飞（1986－）, 男, 安徽潜山人, 副教授, 主要研究方向: 集成电路设计自动化. E-mail: chuzhufei@nbu.edu.cn 宁波大学学报（理工版）网址：http://journallg.nbu.edu.cn/ |
