informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2020-17-3-54-63inform-1073Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNАлгоритмы разбиения логических схем на подсхемыAlgorithms for partitioning logical circuits into subcircuitsКириенкоН. А.KirienkoN. A.

Natalia A. Kirienko, Cand. Sci. (Eng.), Associate Professor, Senior Researcher

Minsk

natalia.kirienko@tut.byОбъединенный институт проблем информатики НАН БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus2020150920201735463Copyright © Кириенко Н.А., 20202020Кириенко Н.А.Kirienko N.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1073

Рассматривается задача разбиения логической схемы на подсхемы, имеющая большое значение при выполнении оптимизационных преобразований в процессе синтеза схемы. Приводится краткий обзор методов и алгоритмов разбиения, выделяются две группы алгоритмов: конструктивные и итеративные. Представляется интерпретация логической схемы в виде графа, формулируется задача разбиения в теоретико-графовой модели и предлагается набор алгоритмов для ее решения. Функционирование логической схемы задается системой логических уравнений. Алгоритмы осуществляют разбиение системы логических уравнений на подсистемы с выполнением ограничений по числу входных и выходных переменных. Рассматриваются структуры данных, необходимых для выполнения алгоритмов. Описываются различные виды взаимосвязей уравнений, определяющих получение оптимальных решений. Исследуются вопросы применения алгоритмов разбиения для улучшения качества схемы на этапе технологически независимой оптимизации. Результаты экспериментального исследования, выполненного с помощью процедуры BDD-оптимизации функционального описания схемы и промышленного синтезатора LeonardoSpectrum  подтверждают  эффективность  разработанных  алгоритмов.  Алгоритмы  реализуются в виде набора процедур разбиения схемы в рамках экспериментальной системы логического проектирования FLC.

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.

автоматизация проектированияразбиение логической схемысистемы булевых функцийконструктивные алгоритмытехнологически-независимая оптимизациясинтез логических схемlogical circuitlogical circuit partitioningsystems of Boolean functionsconstructive algorithmstechnology-independent optimizationsynthesis of logical circuitsReferencesРабаи, Ж. М. Цифровые интегральные схемы. Методология проектирования / Ж. М. Рабаи, А. Чандракасан, Б. Николич. – М. : Вильямс, 2007. – 912 с.Rabaey Jan M. Digital Integrated Circuits: A Design Perspective. Prentice Hall, 1995, 702 p.Partitioning-based methods / ed.: C. J. Alpert, D. P. Mehta, S. S. Sapatnekar // Handbook of Algorithms for Physical design Automation. – CRC Press, 2009. – P. 290–308.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.Global and detailed placement / A. B. Kahng [et al.] // VLSI physical design: Graph Partitioning to Timing Closure. – Springer, 2011. – P. 95–122.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.Bibilo, P. Block synthesis of combinational circuits / P. Bibilo, N. Kirienko // Design of Embedded Control Systems. – Springer, 2004 – P. 189–196.Bibilo P., Kirienko N. Block synthesis of combinational circuits. Design of Embedded Control Systems. Springer, 2004, pp. 189–196.Базилевич, Р. П. Алгоритмические и программные средства для размещения разногабаритных элементов на конструктиве / Р. П. Базилевич, И. Ф. Щербюк // Автоматизация проектирования дискретных систем : материалы Шестой Междунар. конф. – Минск : ОИПИ НАН Беларуси, 2007. – С. 157–164.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).Breuer, M. A. Fundamental CAD algorithms / M. A. Breuer, M. Sarrafzadeh, F. Somenzi // IEEE Trans. Computer-Aided Design. – 2000. – Vol. 19, nо. 12. – P. 1449–1475.Breuer M. A., Sarrafzadeh M., Somenzi F. Fundamental CAD algorithms. IEEE Transactions ComputerAided Design, 2000, vol. 19, nо. 12, pp. 1449–1475.Kernighan, B. W. An efficient heuristic procedure for partitioning graphs / B. W. Kernighan, S. Lin. // Bell Labs Technical J. – 1970. – Vol. 49. – P. 291–307.Kernighan B. W., Lin S. An efficient heuristic procedure for partitioning graphs. Bell Labs Technical Journal, 1970, vol. 49, pp. 291–307.Fiduccia, C. M. A linear time heuristic for improving network partitions / C. M. Fiduccia, R. M. Mattheyes // Proc. IEEE-ACM Design Automation Conf., Las Vegas, Nevada, USA, 14–16 June 1982. – Las Vegas, 1982. – P. 175–181.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.Karypis, G. Multilevel k-way hypergraph partitioning / G. Karypis, V. Kumar // Proc. IEEE-ACM Design Automation Conf., New Orleans, USA, 21–25 June 1999. – New Orleans, 1999. – P. 343–348.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.Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning / D. S. Johnson [et al.] // Operations Research. – 1989. – Vol. 37. – P. 865–892.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.Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик ; под ред. В. М. Курейчика. – М. : Физматлит, 2006. – 320 с.Gladkov L. A., Kurejchik V. V., Kurejchik V. M. (ed.) Geneticheskie algoritmy. Genetic Algorithms. Moscow, Fizmatlit, 2006, 320 p. (in Russian).Бибило, П. Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов. – Минск : Беларус. навука, 2011. – 279 с.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).Автоматизация логического синтеза КМОП-схем с пониженным энергопотреблением / П. Н. Бибило [и др.] // Программная инженерия. – 2013. – № 8. – С. 35–41.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).A system for logical design of custom CMOS VLSI functional blocks with reduced power consumption /P. N. Bibilo [et al.] // Russian Microelectronics. – 2018. – Vol. 47, no. 1. – P. 65–81.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.Бибило, П. Н. Логическая оптимизация многоуровневых представлений систем булевых функций на основе блочного разбиения и разложения Шеннона / П. Н. Бибило, Н. А. Кириенко, Ю. Ю. Ланкевич // Информатика. – 2018. – Т. 15, № 3. – С. 56–70.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).Бибило, П. Н. Системы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П. Н. Бибило. – М. : Солон-Пресс, 2005. – 384 с.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).

The authors declare that there are no conflicts of interest present.