Алгоритмы разбиения логических схем на подсхемы

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

1. Рабаи, Ж. М. Цифровые интегральные схемы. Методология проектирования / Ж. М. Рабаи, А. Чандракасан, Б. Николич. - М. : Вильямс, 2007. - 912 с.

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

3. Global and detailed placement / A. B. Kahng [et al.] // VLSI physical design: Graph Partitioning to Timing Closure. - Springer, 2011. - P. 95-122.

4. Bibilo, P. Block synthesis of combinational circuits / P. Bibilo, N. Kirienko // Design of Embedded Control Systems. - Springer, 2004 - P. 189-196.

5. Базилевич, Р. П. Алгоритмические и программные средства для размещения разногабаритных элементов на конструктиве / Р. П. Базилевич, И. Ф. Щербюк // Автоматизация проектирования дискретных систем : материалы Шестой Междунар. конф. - Минск : ОИПИ НАН Беларуси, 2007. - С. 157-164.

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

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

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

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

10. Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning / D. S. Johnson [et al.] // Operations Research. - 1989. - Vol. 37. - P. 865-892.

11. Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик ; под ред. В. М. Курейчика. - М. : Физматлит, 2006. - 320 с.

12. Бибило, П. Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов. - Минск : Беларус. навука, 2011. - 279 с.

13. Автоматизация логического синтеза КМОП-схем с пониженным энергопотреблением / П. Н. Бибило [и др.] // Программная инженерия. - 2013. - № 8. - С. 35-41.

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

15. Бибило, П. Н. Логическая оптимизация многоуровневых представлений систем булевых функций на основе блочного разбиения и разложения Шеннона / П. Н. Бибило, Н. А. Кириенко, Ю. Ю. Ланкевич // Информатика. - 2018. - Т. 15, № 3. - С. 56-70.

16. Бибило, П. Н. Системы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П. Н. Бибило. - М. : Солон-Пресс, 2005. - 384 с.