Algorithms for partitioning logical circuits into subcircuits
https://doi.org/10.37661/1816-0301-2020-17-3-54-63
Abstract
The problem of partitioning a logical circuit into subcircuits is considered. It is of great importance when performing optimization transformations in the process of circuit synthesis. The brief review of partitioning methods and algorithms is given, and two groups of algorithms are identified: constructive and iterative one. The interpretation of a logical circuit in the form of a graph is presented. The problem of partitioning in terms of a graph-theoretic model is defined and some algorithms for solving the partitioning problem are proposed. Logic circuit functions are defined by a system of logical equations. Algorithms perform the partitioning the system of logical equations into subsystems with the restrictions of the number of input and output variables. The data structures to execute the algorithms are defined. Various types of equations connections, obtaining better solutions for partitioning are described. The problems of the use of partitioning algorithms to improve the quality of the circuit at the stage of technology-independent optimization are investigated. The results of an experimental study carried out by the BDD optimization procedure for the functional description of the circuit and LeonardoSpectrum synthesis confirm the effectiveness of the developed algorithms. The algorithms are implemented as partitioning circuit procedures in the experimental FLC system for logical design.
About the Author
N. A. Kirienko
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
Natalia A. Kirienko, Cand. Sci. (Eng.), Associate Professor, Senior Researcher
Minsk
References
1. Rabaey Jan M. Digital Integrated Circuits: A Design Perspective. Prentice Hall, 1995, 702 p.
2. Alpert C. J., Mehta D. P., Sapatnekar S. S. (eds.). Partitioning-based methods. Handbook of Algorithms for Physical design Automation. CRC Press, 2009, pp. 290–308.
3. Kahng A. B., Liening J., Markov I. L., Hu J. Global and detailed placement. VLSI physical design: Graph Partitioning to Timing Closure. Springer, 2011, pp. 95–122.
4. Bibilo P., Kirienko N. Block synthesis of combinational circuits. Design of Embedded Control Systems. Springer, 2004, pp. 189–196.
5. Bazilevich R. P., Shcherbyuk I. F. Algoritmicheskie i programmnye sredstva dlya razmeshcheniya raznogabaritnyh elementov na konstruktive [Algorithmic and software tools for placing oversized elements on a construct]. Avtomatizaciya proektirovaniya diskretnyh sistem: materialy Shestoy Mezhdunarodnoj konferencii [Computer-Aided Design of Discrete Devices: Proceedings of the Sixth International Conference]. Minsk, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, 2007, pp. 157–164 (in Russian).
6. Breuer M. A., Sarrafzadeh M., Somenzi F. Fundamental CAD algorithms. IEEE Transactions ComputerAided Design, 2000, vol. 19, nо. 12, pp. 1449–1475.
7. Kernighan B. W., Lin S. An efficient heuristic procedure for partitioning graphs. Bell Labs Technical Journal, 1970, vol. 49, pp. 291–307.
8. Fiduccia C. M., Mattheyes R. M. A linear time heuristic for improving network partitions. Proceedings IEEE-ACM Design Automation Conference, Las Vegas, Nevada, USA, 14–16 June 1982. Las Vegas, 1982, pp. 175–181.
9. Karypis G., Kumar V. Multilevel k-way hypergraph partitioning, Proceedings IEEE-ACM Design Automation Conference, New Orleans, USA, 21–25 June 1999. New Orleans, 1999, pp. 343–348.
10. Johnson D. S., Aragon C. R., Mcgeoch L. A., Schevon C. Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning. Operations Research, 1989, vol. 37, pp. 865–892.
11. Gladkov L. A., Kurejchik V. V., Kurejchik V. M. (ed.) Geneticheskie algoritmy. Genetic Algorithms. Moscow, Fizmatlit, 2006, 320 p. (in Russian).
12. Bibilo P. N., Romanov V. I. Logicheskoe proektirovanie diskretnyh ustrojstv s ispol'zovaniem produkcionno-frejmovoj modeli predstavlenija znanij. Logical Design of Discrete Devices with Use of Productional and Frame Model of Representation of Knowledge. Minsk, Belaruskaja navuka, 2011, 279 p. (in Russian).
13. Bibilo P. N., Cheremisinova L. D., Kardash S. N., Kirienko N. A., Romanov V. I., Cheremisinov D. I. Avtomatizaciya logicheskogo sinteza KMOP-skhem s ponizhennym energopotrebleniem [Low-power logical synthesis of cmos circuits automation]. Programmnaya inzheneriya [Software Engineering], 2013, no. 8, pp. 35–41 (in Russian).
14. Bibilo P. N., Avdeev N. A., Kardash S. N., Kirienko N. A., Lankevich Yu. Yu., …, Cheremisinova L. D. A system for logical design of custom CMOS VLSI functional blocks with reduced power consumption. Russian Microelectronics, 2018, vol. 47, no. 1, pp. 65–81.
15. Bibilo P. N., Kirienko N. A., Lankevich Yu. Yu. Logicheskaya optimizaciya mnogourovnevyh predstavlenij sistem bulevyh funkcij na osnove blochnogo razbieniya i razlozheniya Shennona [Logical optimization the multilevel representations of systems of Boolean functions based on partitioning into blocks and Shannon decomposition]. Informatika [Informatics], 2018, vol. 15, no. 3, pp. 56–70 (in Russian).
16. Bibilo P. N. Sistemy proektirovaniya integral'nyh skhem na osnove yazyka VHDL. StateCAD, ModelSim, LeonardoSpectrum. Integrated Circuit Design Systems Based on VHDL. StateCAD, ModelSim, LeonardoSpectrum. Moscow, Solon-Press, 2005, 384 p. (in Russian).
Review
For citations:
Kirienko N.A. Algorithms for partitioning logical circuits into subcircuits. Informatics. 2020;17(3):54-63. (In Russ.) https://doi.org/10.37661/1816-0301-2020-17-3-54-63
Views: 710
Email this article 