一种组合逻辑环转化方法

doi:10.3969/j.issn.1001-2400.2014.01.014

J4 ›› 2014, Vol. 41 ›› Issue (1): 75-80.doi: 10.3969/j.issn.1001-2400.2014.01.014

一种组合逻辑环转化方法

邸志雄;史江义;马佩军;张译;袁莉;郝跃;许钊

(西安电子科技大学宽带隙半导体国家重点实验室，陕西西安 710071)

收稿日期:2013-04-23 出版日期:2014-02-20 发布日期:2014-04-02
通讯作者: 邸志雄
作者简介:邸志雄(1984-)，男，西安电子科技大学博士研究生，E-mail：dizhixiong2@126.com．
基金资助:
中央高校基本科研业务费专项资金资助项目(K5051325010)

Method for transforming cyclic circuits into acyclic equivalents

DI Zhixiong;SHI Jiangyi;MA Peijun;ZHANG Yi;YUAN Li;HAO Yue;XU Zhao

(State Key Lab. of Wide Bandgap Semiconductor Technology Disciplines, Xidian Univ., Xi'an 710071， China)

Received:2013-04-23 Online:2014-02-20 Published:2014-04-02
Contact: DI Zhixiong

摘要/Abstract

摘要：

组合逻辑环能够减少电路逻辑资源，降低电路功耗,但是其难以被静态时序分析工具分析和计算，且难以生成功能验证向量和自动测试图形向量．针对此问题，提出一种组合逻辑环转化方法，以解决硬件描述语言以及高级语言逻辑综合阶段所面临的组合逻辑环拆分问题．不同于采用三值仿真策略的现有文献，引入了布尔可满足引擎对组合逻辑环电路进行了表征，使用静态逻辑蕴涵完成了环形电路的拆分．同时，根据环形电路的形成机理，提出了拆分组合逻辑环结构的规则，用于冗余向量优化以及非环电路的逻辑推理．实验结果表明，这种算法能够正确地拆分组合逻辑环结构，且转化时间短，转化后的电路规模小．

关键词: 组合逻辑环, 逻辑综合, SAT引擎, 静态逻辑蕴涵

Abstract:

The cyclic circuit is capable of reducing the area and power consumption, but it is difficult for tools such as static timing analyzers to analyze and compute. Furthermore, the simulation and DFT for the cyclic circuit are more expensive and complicated. Thus, a method for transforming cyclic circuits into acyclic equivalents based on the SAT(Boolean Satisfiability) is presented in this paper in order to remove the unwanted cycles in the high-level synthesis process. Different from the available researches, the SAT and static logic implication are introduced in this paper. Meanwhile, by analyzing the structure and mechanism of the cyclic circuits, some novel rules are presented to obtain the acyclic equivalents more precisely and effectively. Experiments are performed in our scientific research projects and the IPs which come from Opencore. And the transforming time and the area are decreased by 28％ and 16％.

Key words: cyclic circuit, synthesis, Boolean Satisfiability(SAT), static logic implication

中图分类号:

TP391.72

邸志雄;史江义;马佩军;张译;袁莉;郝跃;许钊. 一种组合逻辑环转化方法[J]. J4, 2014, 41(1): 75-80.

DI Zhixiong;SHI Jiangyi;MA Peijun;ZHANG Yi;YUAN Li;HAO Yue;XU Zhao. Method for transforming cyclic circuits into acyclic equivalents[J]. J4, 2014, 41(1): 75-80.

参考文献

［1］Mukherjee B, Dandapat A K. Design of Combinational Circuits by Cyclic Combinational Method for Low Power VLSI ［C］//2010 International Symposium on Electronic System Design. Piscataway: IEEE Computer Society, 2010: 107-112.
［2］ Chan T. A Robust Multithreaded HDL/ESL Simulator for Deep Submicron Integrated Circuit Designs ［C］//IEEE Asia Pacific Conference on Circuits and Systems. Piscataway: IEEE, 2012: 416-419.
［3］ Huang H Y, Huang C Y, Chen C H. Tile-based GPU Optimizations through ESL Full System Simulation［C］//IEEE International Symposium on Circuits and Systems. Washington: IEEE Computer Society, 2012: 1327-1330.
［4］ Chen Weiwei, Dmer R. An Optimizing Compiler for Out-of-order Parallel ESL Simulation Exploiting Instance Isolation ［C］//17th Asia and South Pacific Design Automation Conference. Piscataway: IEEE, 2012: 461-466.
［5］ Yoshikawa Y. A Binding Algorithm in High-level Synthesis for Path Delay Testability ［C］//18th Asia and South Pacific Design Automation Conference. Piscataway: IEEE, 2013: 546-551.
［6］ Neiroukh O, Edwards S A, Song Xiaoyu. An Efficient Algorithm for the Analysis of Cyclic Circuits ［C］//Proceedings of IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures. Piscataway: IEEE, 2006: 303-308.
［7］ Shiple T R, Berry G, Touati H. Constructive Analysis of Cyclic Circuits ［C］//Proceedings of European Design and Test Conference. Los Alamitos: IEEE,1996: 328-333.
［8］ Riedel M D, Bruck J. The Synthesis of Cyclic Combinational Circuits ［C］//Proceedings of IEEE Design Automation Conference. Piscataway: IEEE, 2003: 163-168.
［9］ Agarwal V, Kankani N, Rao R, et al. An Efficient Combinationality Check Technique for the Synthesis of Cyclic Combinational Circuit ［C］//Proceedings of the Asia and South Pacific Design Automation Conference. Piscataway: IEEE, 2005: 212-215.
［10］ Raghunathan A, Ashar P, Malik S. Test Generation for Cyclic Combinational Circuits ［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995, 14(11): 1408-1414.
［11］ Larouche M, Massé A B, Goboury S, et al. Solving Equations on Words through Boolean Satisfiability ［C］//28th Annual ACM Symposium on Applied Computing. New York: Association for Computing Machinery, 2013:104-106.
［12］ Wang J, Chen J L, Yu C F, et al. A Quantum Method to Test the Satisfiability of Boolean Functions ［C］//Proceedings-2012 IEEE 11th International Conference on Solid-State and Integrated Circuit Technology. Piscataway: IEEE, 2012: 1-5.
［13］ Neiroukh O, Edwards S A, Song Xiaoyu. Transforming Cyclic Circuits Into Acyclic Equivalents［J］. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2008, 27(10): 1775-1787.
［14］ Stok L. False Loops through Resource Sharing ［C］//IEEE/ACM International Conference on Computer-Aided Design. Los Alamito: IEEE, 1992: 345-348.
［15］ Gupta A, Selvidge C. Acyclic Modeling of Combinational Loops ［C］//Proceedings of the ICCAD-2005: International Conference on Computer-Aided Design. Piscataway: IEEE, 2005: 343-347.
［16］ Riedel M D, Bruck J. Cyclic Boolean Circuits［J］. Discrete Applied Mathematics, 2012, 160(13-14): 1877-1900.
［17］ Backes J D, Riedel M D. The Synthesis of Cyclic Dependencies with Boolean Satisfiability［J］. ACM Transactions on Design Automation of Electronic Systems, 2012, 17(4): 1-24.
［18］ Rivest R L. The necessity of feedback in Minimal Monotone Combinational Circuits［J］. IEEE Transactions on Computers, 1977, 26(6): 606-607.
［19］ Mohanty S P. Shortest String Containing All Permutations［J］. Discrete Mathematics, 1980, 31(1): 91-95.
［20］ Bouroncle F. Efficient Chaotic Iteration Strategies with Widenings［C］//International Conference on Formal Methods in Programming and Their Applications. Berlin: Springer, 1993: 128-141.
［21］潘伟涛, 谢元斌, 郝跃, 等. 二同构扩展数字集成电路规律性提取算法［J］. 西安电子科技大学学报, 2009, 36(3): 452-462.
Pan Weitao, Xie Yuanbin, Hao Yue, et al. Two-isomorphic Extending Algorithm for Regularity Extraction in Digital Integrated Circuits［J］. Journal of Xidian University, 2009, 36(3): 452-462.
［22］ Edwards S A. Making Cyclic Circuits Acyclic ［C］//Proceedings of the 40th Design Automation Conference. Piscataway: IEEE, 2003: 159-162.

一种组合逻辑环转化方法

Method for transforming cyclic circuits into acyclic equivalents

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

Metrics

本文评价

推荐阅读 10