一种组合逻辑环转化方法

doi:10.3969/j.issn.1001-2400.2014.01.014

Abstract

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

CLC Number:

TP391.72

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.

References

［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.

[1]	GUO Qiang,LI Jiaying,WANG Yani. Synthesis of linear arrays with sidelobe suppression and null steering using the improved coyeto optimization algorithm [J]. Journal of Xidian University, 2021, 48(6): 172-178.
[2]	CHANG Wensheng,TAO Haihong,DAI Baoquan,LIU Yanbin,SUN Guangcai. Frequency band synthesis STAP-GMTI system architecture with the reciprocal transceiver [J]. Journal of Xidian University, 2021, 48(2): 156-164.
[3]	ZHANG Lu,MU Dejun,HU Wei,TAI Yu. High-level synthesis design flow for power side-channel security [J]. Journal of Xidian University, 2020, 47(4): 64-69.
[4]	SUN Cuizhen,DING Jun,GUO Chenjiang. Improved gravitational search algorithm for shaped beam forming [J]. Journal of Xidian University, 2020, 47(2): 83-90.
[5]	ZHANG Jintao,LEI Jie,WU Lingyun,HUANG Biying,LI Yunsong. Improved algorithm for hyperspectral endmember extraction and its FPGA implementation [J]. Journal of Xidian University, 2019, 46(4): 22-27.
[6]	QU Bayi;MI Jie;CHEN Ruijie;DONG Shaofeng;CHEN Xiaolong;ZHOU Wei. Technology of the improvement on the output accuracy of DDS [J]. Journal of Xidian University, 2018, 45(3): 58-62.
[7]	JING Guobin;SUN Guangcai;XING Mengdao;GUO Rui;BAO Zheng. Novel two-step method of bandwidth synthesis for SF-MIMO-SAR [J]. Journal of Xidian University, 2018, 45(2): 148-153+159.
[8]	ZHANG Jiajia;ZHOU Fang;SUN Guangcai;XING Mengdao;BAO Zheng. High signal-noise-ratio high-resolution wide-swath imaging using two-dimensional intrapulse beam steering [J]. J4, 2014, 41(4): 6-12+150.
[9]	LIU Yan;JIAO Yongchang;ZHANG Yaming;WANG Xinkuan. Application of the invasive weed optimization algorithm to the pattern synthesis of array antennas [J]. J4, 2014, 41(1): 29-33+86.
[10]	LI Dong;LIAO Guisheng;YANG Zhiwei;XU Qing. Frequency scaling algorithm for high squint FMCW-SAR imaging [J]. J4, 2013, 40(4): 21-28.
[11]	WANG Xinkuan;JIAO Yongchang;TAN Yanyan. Adaptive iteration Fourier technique applied for antenna arrays pattern synthesis [J]. J4, 2013, 40(4): 85-89+187.
[12]	YANG Tao;SU Tao;ZHANG Wang. Transmit beampattern synthesis and waveform design for 2-D wideband MIMO radar [J]. J4, 2013, 40(3): 180-187.
[13]	WANG Pengjun;WANG Zhenhai. Delay and area optimization for FPRM circuits by FDDs [J]. J4, 2013, 40(1): 135-140.
[14]	LI Rui;SHI Xiaowei;XU Le;GU Xintao;LI Ping. Synthesis of a conformal antenna array using the competition differential evolution strategy [J]. J4, 2012, 39(3): 114-119.
[15]	ZHANG Shuai;GONG Shuxi;GUAN Ying;GONG Qi;LU Bao. Calculation and application of the mutual impedance and the scattering matrices of large finite arrays [J]. J4, 2012, 39(3): 106-113.

Method for transforming cyclic circuits into acyclic equivalents

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10