Разработка и исследование алгоритмов компоновки конструктивных узлов цифровой вычислительной аппаратуры. тема диссертации и автореферата по ВАК РФ 00.00.00, Егоров, А. Г.

• Егоров, А. Г.
• 1975

Оглавление диссертации Егоров, А. Г.

Введение

1. Модели и критерии, используемые при решении задач компоновки конструктивных узлов

1.1. Влияние интегральных схем на компоновку конструктивных узлов

1.2. О критериях компоновки конструктивных узлов.

1.3. Обзор методов решения задачи компоновки

1.4. Выбор моделей и критериев оптимизации

Выводы.

2. Покрытие функционально-логических схем несвязными модулями из заданного набора.

2.1. Постановка задачи.

2.2. Точный метод решения задачи покрытия

2.3. Определение минимального числа интегральных модулей

2.4. Приближенные способы покрытия

Выводы.

3. Методы формирования набора типовых элементов замены для нерегулярных схем

3.1. 0 .двух подходах к задаче формирования типовых элементов замены

3.2. Приближенные алгоритмы компоновки

3.3. Разбиение схемы на типовые элементы замены с введением избыточных элементов

3.4. Алгоритм разбиения схем из однофункциональных элементов с введением избыточности

Выводы.

4. Методы компоновки регулярных схем

4.1. Выбор оптимальной совокупности функциональных узлов.

4.2. Компоновка схем по обобщенному критерию. . , .125 Выводы.

5. Программная реализация алгоритмов компоновки и результаты их исследования.

5.1. Способ представления информации о схеме.

5.2. Основные положения программы покрытия.

5.3. Программа компоновки нерегулярных схем

5.4. Программная реализация метода динамического программирования

5.5. Программа выбора оптимальной совокупности функциональных узлов.

Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование алгоритмов компоновки конструктивных узлов цифровой вычислительной аппаратуры.»

Одной из особенностей современного этапа научно-технической революции является повсеместное внедрение средств вычислительной техники и , особенно, цифровых электронно-вычислительных машин (ЦВМ). Наряду с постоянным расширением круга задач, решаемых с помощью ЦВМ, непрерывно возрастает и их сложность, что приводит к необходимости создания все более мощных и надежных вычислительных комплексов в.кратчайшие сроки. Последние достижения микроэлектроники, позволяющие осуществить целый ряд сложных технических проектов, вместе с тем ставят достаточно много проблем, решение которых весьма затруднительно без широкого использования автоматизированных систем проектирования (АСП), охватывающих различные этапы разработки и изготовления ЦВМ и , в частности, наиболее трудоемкий этап технического проектирования. Применение АСП позволяет сократить сроки и стоимость проектирования, увеличить производительность труда, уменьшить затраты, связанные с исправлением неизбежно возникающих в процессе проектирования ошибок,и в некоторых случаях улучшить качество создаваемой аппаратуры.

До настоящего времени наибольшее внимание в рамках АСП уделялось двум задачам технического проектирования - размещению элементов, относящихся к младшим уровням конструктивной иерархии в I элементах старших уровней, и трассировке соединений между конструктивными элементами [32, 42, 64] . Однако , с переходом к интегральным схемам (ИС) на одно из первых мест по важности решения выдвинулась задача компоновки, под которой понимается определение компонентов конструктивных узлов каждого уровня иерархии. Особенно остро эта задача стоит при проектировании таких конструктив, как типовые элементы замены (ТЭЗ) и большие интегральные схемы (БИС), машин третьего и четвертого поколений.

В машинах первых поколений задача компоновки не вызывала существенных трудностей по целому ряду причин. В первую очередь это объяснялось достаточной мощностью дискретных элементов [85], что позволяло относительно просто решать проблему внешних соединений из-за отсутствия существенных ограничений на их длину. Кроме того, значительные габариты дискретных элементов, условия механической прочности печатных плат, ограничения теплового характера не давали возможность формировать блоки большего объема. Это, в свою очередь, способствовало упрощению задачи компоновки блоков, вследствие довольно большого числа их внешних выводов, приходящихся на каждый логический вентиль.

Внедрение ИС заставило по-новому подойти к проблеме компоновки конструктивных узлов. Стремление к высокой надежности ЦВМ при незначительном объеме интегральных компонентов способствовало резкому увеличению функциональной сложности блоков. Шалые мощности интегральных схем,а также повышенные тактовые частоты привели к жестким ограничениям длины межсоединений, что поставило в прямую зависимость качество компоновки и работоспособность создаваемой аппаратуры. В этих условиях важность и трудоемкость задачи . компоновки наряду с ограниченным временем, обычно представляемым конструктору для её решения, сделали актуальной автоматизацию данного этапа технического проектирования.

Включение задачи компоновки в широкий круг вопросов, решаемых существующими АСП, требует рассмотрения следующих проблем:

1) выбор или построение математических моделей, адекватных объектам исследования;

2) обоснование используемых критериев оптимизации;

3) разработка математических методов и создание эффективных алгоритмов решения задач, возникающих при компоновке элементов различных уровней конструктивной иерархии.

В настоящее время известен ряд работ, посвященных решению перечисленных вопросов. Среди них следует презде всего отметить работы Крапчина А.И., Покровского А.Н., Мальгинова E.H. [53 ] , Мелихова А.Н., Берштейна Л. С., Курейчика В.Н. [бб] , Ноткина Р. Г.

73] , Хаспела [Юб] , рассмотревших задачу покрытия схем несвязными наборами интегральных модулей; Гайфуллина Э.Ш. [26] , исследовавшего более сложный случай связных модулей; Погребного В.К. [?8] , Шора Н.З., Мараховского Л.Ф. [юо] , работы Браччи [ЮЗ] , Цдигова A.A. [39] , Крыжановского Ю.М. [54] , Матюхина Н.Я., Олейника Р.И. [бЗ], Руссо, Вольфа [83], в которых разработаны алгоритмы компоновки конструктивных узлов; Абрайтиса Л.Б.[l] , Горин-штейна Л.Л.[3l], Штейна М.Е., Штейна Б.Е. [102] , где сформулированы алгоритмы точного решения задачи разбиения схем, а также работы других авторов. И тем не менее методы решения задачи компоновки требуют своего дальнейшего развития. Так, в алгоритмах компоновки необходимо использовать более точные модели схемы, позволяющие учесть ряд практических ограничений, в частности, ограничение на число внешних выводов блока. На базе таких моделей должны быть разработаны как точные, так и эффективные приближенные алгоритмы решения задачи компоновки. Поэтому в настоящей работе рассматриваются вопросы, связанные с формализацией и решением некоторых задач компоновки, применительно к цифровым вычислительным машинам, проектируемым на интегральных схемах.

Целью диссертации является разработка и исследование новых (точных и приближенных) алгоритмов решения задачи компоновки,позволяющих с учетом ограничений на модульную и контактную емкости конструктивных блоков осуществлять минимизацию числа блоков, требуемых для реализации заданной схемы, числа типов блоков, числа межблочных соединений, и практическая реализация этих алгоритмов в виде программ для ЦВМ, ориентированных на исследование в автоматизированной системе; проектирования печатных плат [18]» В соответствии с этим в работе осуществляется выбор математических моделей схем ЦВМ, с помощью которых строго формулируются задачи покрытия схем интегральными модулями, компоновки типовых элементов замены для регулярных и нерегулярных устройств, разбиения схем с введением избыточных элементов, разрабатываются и иссле,дуются точные и приближенные алгоритмы решения данных задач, обсуждаются програмлы, реализующие разработанные алгоритмы, проводятся их исследования.

В первой главе диссертации исследуются основные особенности технического проектирования ЦВМ на ИС. Анализируются основные критерии и методы решения задачи компоновки, а также известные математические модели функционально-логических схем (ФЛС). На основании проведенного анализа формулируются основные требования, используемые при дальнейшем рассмотрении, а также предлагаются две точные графовые модели схем, с помощью которых выводятся строгие математические выражения для определения числа внешних выводов отдельных блоков и суммарного числа межблочных соединений.

Во второй главе рассматривается задача покрытия <МС набором несвязных модулей. Дается строгая математическая: постановка этой задачи. Предлагается точный алгоритм ее решения, основанный на идеях метода динамического программирования. Для схем большой размерности обсуждается приближенный подход к их покрытию и рассматриваются алгоритма решения возникающих при этом задач.

Третья глава содержит исследование задачи компоновки блоков, реализующих нерегулярные структуры ЦВМ, которая представляется в виде разбиения графов, интерпретирующих исходную схему, на подграфы, соответствующие частям схемы, реализуемым в виде отдельных блоков с заданной модульной и контактной емкостями. Обсуждаются два возможных подхода к решению данной задачи и соответствующие этим подходам алгоритмы. Рассматривается возможность более качественного, по сравнению с обычным разбиением, решения за счет введения избыточных элементов. С этой целью задача компоновки блоков формулируется как задача нелинейного математического программирования с бивалентными переменными, для решения которой предлагается несложный эвристический алгоритм.

Четвертая глаза посвящена задаче формирования блоков, реализующих регулярные структуры ЦВМ. Рассматривается два случая соответствия между функциональными и конструктивными узлами. В первом - когда каждый конструктивный узел реализует один функциональный, задача построения набора блоков совпадает с задачей выбора оптимальной совокупности функциональных узлов, для решения которой предлагается эффективный точный алгоритм, представляющий собой одну из реализаций метода "ветвей и границ". Во-втором случае, когда в конструктивном узле реализуется произвольное число функциональных узлов, решение задачи формирования набора блоков осуществляется с помощью алгоритма, основанного на идеях метода динамического программирования.

В пятой главе диссертации проведено исследование программ, реализующих разработанные алгоритмы. Рассмотрены структуры и особенности этих программ, а также вопросы, связанные с организацией и способом представления входной информации при практическом применении программ в автоматизированной системе проектирования.

I. МОДЕЛИ И КРИТЕРИИ, ИСПОЛЬЗУЕШЕ ПРИ РЕШЕНИИ ЗАДАЧ ЮМЮНОВКИ КОНСТРУКТИВНЫХ УЗЛОВ

Заключение диссертации по теме «Другие cпециальности», Егоров, А. Г.

Основные результаты диссертационной работы были доложены на П Всесоюзной конференции "Алгоритмические методы проектирования цифровых систем" (Ленинград, 1972); на семинаре "Теоретические и прикладные вопросы технической кибернетики" (Таганрог, 1973); на третьем совещании "Логический сиситез в дискретных однородных средах11 (Рязань, 1974); на Всесоюзных школах-семинарах "Применение ЭЗД при разработке радиоэлектронных устройств с использованием средств микроэлектроники" (Кострома, 1974) и "Экспериментальные задачи при проектировании современных ЭШ" (Гурзуф, 1975); на семинаре "Автоматизированное техническое проектирование цифровых устройств" (Каунас, 1975), на конференции "Автоматизация проч . . ектирования средств автоматики и вычислительной техники" (Пенза,

1975), а также на научно-технических конференциях РРТИ (Рязань,

- ■ <*

1973-1975 г.г,) и опубликованы в работах [13 * 17 , 25 , 36 , 37 ', 40 , 82],

ЗАКЛЮЧЕНИЕ В соответствии с поставленной целью в диссертации получены следующие основные результаты*

1, Проведен анализ особенностей технического проектирования цифровой аппаратуры на интегральных схемах и определены критерии решения задач компоновки конструктивных узлов» Показано, что целесообразно разделять схемы на нерегулярные и регулярные с тем» чтобы для первого класса схем принять в качестве основного требования минимизацию числа компонуемых блоков и числа внешних соединений, а для второго, дополнительно к перечисленным, учитывать и требование минимизации числа типов блоков,

2, На основании предложенных в работе моделей получены точные количественные оценки числа межблочных соединений и внешних выводов блоков* Дана формализация основных задач, возникающих при покрытии ФЛС набором интегральных модулей и компоновке блоков ЦВМ, и являющихся задачами нелинейного математического программирования,

3, Разработан точный метод решения задач покрытия ФЛС интегральными модулями и компоновки конструктивных узлов, основанный на идеях динамического программирования, который может быть использован для построения и оценки качества эвристических процедур, а также для компоновки схем, содержащих до нескольких десятков логических элементов,

4* Сформулирована задача определения наименьшего числа интегральных модулей, необходимых для покрытия функционально-логической схемы. Разработан алгоритм, обеспечивающий точное решение данной задачи для комплексов элементов типа "Логика - 2",

5, Рассмотрены два возможных подхода к задаче компоновки блоков, реализующих нерегулярные схемы. При первом - осуществляется покрытие ФЛС набором интегральных модулей, а затем схема разрезается на части, соответствующие блокам. При втором - блоки формируются в процессе разрезания ФЛС, построенной из ЛЭ, а задача покрытия решается отдельно для каждого блока* Проведенное исследование показало, что первый подход требует в среднем в 1,5 раза меньше времени чем второй,при практически одинаковых результатах.

6. Дана строгая математическая постановка задачи формирования блоков с учетом введения избыточных элементов. Для компоновки схем из однойункциопальных элементов предложен приближенный алгоритм решения данной задачи,

7. Исследован подход к проблеме стандартизации блоков, основанный на функционально-узловом методе проектирования. Разработан точный алгоритм выбора оптимальной совокупности функциональных узлов, обеспечивающий решение задач практической размерности.

8. Сформулирована задача компоновки регулярных схем по обобщенному критерию, для решения которой разработан точный алгоритм. Приведены оценки объема памяти и числа операций, требуемых для его реализации.

9. Рассмотрена проблема автоматического составления схемы ЦШ из отдельных её фрагментов. Разработан экономичный способ представления информации и программы, позволяющие сократить временные затраты на её подготовку и контроль.

10. Проведено экспериментальное исследование, позволяющее оценить возможности предлагаемых алгоритмов компоновки и определить области их применения.

II» Разработан комплекс программ, обеспечивающий автоматическое решение основных задач компоновки схем, содержащих 2000 логических элементов, и являющийся составной частью действующей в ОКБ ВТ РРТИ системы автоматизированного проектирования печатных плат.

Список литературы диссертационного исследования Егоров, А. Г., 1975 год

1. Абраитис Л.Б. Алгоритм для определения максимально связанных наборов элементов. "Автоматики и вычислительная техника",1970,Ж>

2. Абрайтис Л.Б.»Шимайтис А.П. Алгоритмы компоновки узлов и исследование их эффективности. В кн.: Вычислительная техника. Материалы научно-технической конференции Лит.ССР, Каунас,1971.

3. Агибалов Г.П. и др. Некоторые алгоритмы разбиения,покрытия иразмещения логических схем. "Управляющие системы и машины", 1974, А». 5.

4. Александров В.А., Бабаян Б.А. Разбиение регулярных схем на типовые блоки. В кн.: Алгоритмические методы проектирования цифровых систем. Л., ЖТМ0Д972.

5. Александров В.П.,Петухов В.В.,Потураев О.С. Выбор, числа разрядов БИС для реализации регулярных структур."Известия ВУЗов. Приборостроение",1971, 14, № 5.

6. Александров В.П., Петухов В.В., Потураев О.С. Вопросы определения состава комплексов на интегральных логических схемах . "Известия ВУЗов.Приборостроение", 1969, 14, Л 12.

7. Ананьевский С.А., Вузовский О.В., Кобылинский A.B. О задаче выбора оптимального модуля функционального ряда больших (многокристальных) интегральных схем." Управляющие системы и машины", 1973, № 2.

8. Бабаян Б.А., Семенихин С.В. Алгоритм компоновки интегральных схем. М.,ИТМиВТ АН СССР,1970.

9. Базилевич Р.П., Ткаченко С.П. Решение задачи разбиения методом параллельного свертывания. В кн.: Вычислительная техника. Каунас ,КПИ,1975.

10. Ю.Беденко B.B., Вузовский O.B.»Каневский Ю.С. О возможных способах функционального разбиения традиционных структур ЦВУ. В кн: Алгоритмические методы проектирования цифровых систем.!., ЛЮТО, 1972.

11. Н.Беллман Р.,Калаба Р. Динамическое программирование и современная теория управления.!.,Наука,1969.

12. Беркович М.М. Задачи стандартизации и некоторые методы их решения. "Экономика и математические методы",1969, V) ,№ 2.

13. Блинушов В.П.,Егоров А.Г.,Толоконников В.К. Алгоритм покрытия логической схемы заданным набором микросхем. В кн.:Алгоритмические методы проектирования цифровых систем.Л.,ЛИТМО,1972.

14. Влинушов В.П.,Егоров А.Г. Алгоритм компоновки микросхем.

15. В кн.:Вычислителъная техника. Межвузовский сборник»Рязань, 1974, вып.X.

16. Блинушов В.П. ,Егоров А.Г.,Толоконников В.К. О длине соединений в однородных средах. В кн.: Логический синтез в дискретных однородных средах. Материалы третьего совещания,Рязань, 1974.

17. Блинушов В.П., Егоров А.Г., Некрасов A.B. К оценке суммарной длины соединений печатной платы. "Известия АН СССР, Техническая кибернетика", 1973, $ 6.

18. Блинушов В.П., Егоров А.Г., Некрасов A.B. О распределении длиш ребер графа с регулярной структурой. В кн.: Применение средств вычислительной техники. Труды РРТИ, Рязань, 1974, вып.58.

19. Блинушов В.П. и др. Автоматизированная система проектирования плат с печатным монтажом. В кн.: Применение вычислительных машин в проектировании и производстве печатного монтажа.1. Л., ЛДНТП,1975.

20. Блонскис И.С., Лапене П.П. К вопросу выбора объема ТЭЗа, в кн.: Вычислительная техника.Каунас,ЕПИ,1975.

21. Болтянский В.Г. Оптимальное управление дискретными системами. М.»Наука,1973.

22. Брэуэр А. Последние достижения в области автоматизации проектирования и анализа цифровых систем. В кн.: Автоматизация в проектировании . М Мир , I 972 .

23. Бурков В.Н., Гроппен В.А. Разрезы в сильносвязанных графах и потенциалы перестановок. "Автоматика и телемеханика",1972,16.

24. Бурцев В.М. и др. Алгоритм компоновки принципиальных схем по микромодулям."Вопросы радиоэлектроники",сер.Электронная вычислительная техника, 1972, вып.З.

25. Веригин В.Н. Возможности и перспективы автоматизации проектирования ЦВМ с учетом особенностей интегральной техники.В кн.: Интегральная электроника и вычислительная техника. М.,Изд.1. ИТМ ВТ АН СССР, 1968.

26. Гайфуллин Э.Ш., Егоров А.Г., 10сим Г.В. Оптимальное разбиение функционально-алогических схем с учетом контактных ограничений. "Электронная техника", Серия 3, Микроэлектроника",I975, вып.2.

27. Гайфуллин Э.Ш. Задачи компоновки при проектировании ЦВМ. Канд.дис. М.,МЭИ,1970.

28. Гайфуллин Э.Ш. Компоновка частей схемы цифрового устройства в платы из заданного набора. "Труды МЭИ", 1972, вып.121.

29. Гайфуллин Э.Ш. и др. Компоновка элементов с учетом требования функциональной законченности плат."Труды ШИ", 1972, вып. 121.

30. Глухов Ю.Н., Шатохин О.Н. К вопросу проектирования серии логических ИС с повышенным уровнем интеграции. В кн.: Вопросы проектирования ЦВМ. М., Изд.ИЭУМ, вып.20.

31. Глушков В.М., Капитонова Ю.В., Летичевский A.A. Автоматизация проектирования вычислительных машин. Киев, Наукова думка,1975.

32. Горинштеин Л.Л. О разрезании графов. "Известия АН СССР. Техническая кибернетика", 1969, $ I.

33. Гурвич Е.И., Матюхин Н.Я. Автоматизированная система проектирования цифровых устройств на элементах третьего поколения, "Вопросы радиоэлектроники", сер. Общетехническая, 1968,вып.14.

34. Гуревич Д.З. »Елизаров В.Н., Рувинский Б.И. Большие интегральные схемы и вычислительные машины четвертого поколения,М., "Электроника",1970.

35. Дуроенев В.В., Плинер Л.А., Сургучева М.В. Размещение функциональной схемы на наборе ячеек с помощью ЭВМ,"Автоматика и вычислительная техника", Рига,1970, $ 2.

36. Евреинов Э.В,.Прангишвили И.В. Цифровые автоматы с настраиваемой структурой. М. »"Энергия", 1974.

37. Егоров А.Г., Чикин В.А., Юсим Г.В. Об оптимальном разбиении функционально-логических схем. В кн.: Логический синтез в дискретных однородных средах. Материалы третьего совещания. Рязань,1974,

38. Егоров А.Г., Юсим Г.В. О покрытии функционально-логических схем набором несвязных модулей. В кн.:"Автоматизация проектирования средств автоматики и вычислительной техники". Материалы научно-технической конференции, Пенза,1975.

39. Жуков В.В., Кривошей A.B., Хорин В.В. Сравнительная оценка контактных соединений типа провод-провод при различных способах монтажа."Электронная техника", сер.Ш, Микроэлектроника, 1972, вып.1.

40. Идигов A.A. Задачи компоновки и функционального разбиения в системе машинного проектирования. Канд. дис.М.,МЭИ,1973.

41. Исследование возможности автоматизации разбиения функционально-логических схем. Отчет по НИР. Регистрационный ü 74008924, Рязань,1975.

42. Кацдарицкий C.B., Розанов В.А., Стихов А.Н. Алгоритм компоновки элементов ВМ."Труды МИЭМ",1971, вып.16.

43. Карапетян А.Н. Автоматизация оптимального конструирования элект ронных вычислительных машин. М.,"Сов.радио",1973.

44. Карасик В.М. Некоторые задачи проектирования ЦВМ на БИС. "Вопросы радиоэлектроники", сер.Электронная вычислительная техника,1971, вып.1.

45. Карасик В.М., Иорданская H.A. Метод построения нерегулярных схем управления на БИС. В кн.: Алгоритмические методы проектирования цифровых систем. Л.,Изд.ЛИТШ, 1972.

46. Карасик В.М., Кретов B.C. Методика автоматического разбиения нерегулярных схем ЦВМ на блоки БИС."Вопросы радиоэлектроники", сер.Электронная вычислительная техника,1973, вып.5.

47. Каррен. На пути к стандартизации БИС. "Электроника", рус.пер. 1970, Я 22.

48. Кейс и др. Автоматизация проектирования вычислительных системс использованием логических схем на твердом теле. В кн.: Кибернетический сборник.Новая серия.М., "Мир",1967, вып.1.

49. Кныш A.A., Тютин A.A. О задачах покрытия в техническом проектировании цифровых устройств. В кн.: Автоматизация проектирования в электронике. Киев."Техника", 1974,вып.10.

50. Кодачигов В.И. и др. О разрезании произвольного конечного графа на подграфы. В кн.:Цифровые модели и интегрирующие структупм Тяраиппп TQ7H.

51. Копыленко В. М., Куротченко В.И. К вопросу построения субблоков, оптимально реализующих заданное устройство. В кн.: Разработка информационно-логических устройств с учетом некоторых критериев оптимальности. Фрунзе, ЖИМ, 1971.

52. Корбут A.A.,Финкелыптейн Ю.Ю. Дискретное программирование. М., Наука, 1969.

53. Корниенко A.B. Разработка и исследование алгоритмов автоматизации разбиения цифровых вычислительных устройств на функциональные блоки. Автореферат канд. дис. Томск, Т1Ш, 1975.

54. Крапчин А.И.,Покровский А.Н.,Мальгинов E.H. Компоновка и размещение модулей. "Автоматика и вычислительная техника", Рига, 1969, 15.

55. Крыжановский Ю.М. Компоновка конструкторских элементов цифровых устройств. В кн.: Применение вычислительных машин для проектирования цифровых устройств. Под ред. Н.Я.Матюхина. М., Сов. радио, 1968.

56. Кхамбата А. Большие интегральные схемы. М., Мир, 197I.

57. Лавров С.С.Гончарова Л.И. Автоматическая обработка данных. М., Наука, 1971.

58. Ландау И.Я. Применение ЦВМ для проектирования ЦВМ. М., Энергия, 1974.

59. Линский B.C. Алгоритмическое проектирование вычислительных цифровых устройств. М., Изд. ВЦ АН СССР, 1963.

60. Лопато В.Н. Об автоматизации проектирования типовых блоков и узлов дискретных устройств. В кн.: Вопросы проектирования и использования электронных управляющих машин. Киев,"Наукова думка", 1968.

61. Лопато В.Н. Размещение функциональных схем в заданной системе модулей. В кн.: Вопросы проектирования и использования электронных управляющих машин. Киев,"Наукова думка", 1968.

62. Малиновский Б.П. и др. О задаче разбиения схемы малой ЦВМна БИС."Управляющие системы и машины", 1974, № 3.

63. Марцинкевичус А.Й., Анушонис С.С. Влияние межсхемных соединений на быстродействие логических цепей ЦВМ."Электронная техника", сер.У1.Микроэлектроника,1971, вып.8.

64. Матюхин H.H., Олейник Р.И. Алгоритмическое проектирование цифро вых устройств. "Вопросы радиоэлектроники", сер.УЛ.»Электронная вычислительная техника, 1965, вып.8.

65. Матюхин Н.Я. Автоматизация проектирования цифровых устройств

66. В кн.: Применение вычислительных машин для проектирования вычислительных устройств. М.,"Сов.радио",1968.

67. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств.М.,"Наука",1974.

68. Мелихов А.Н. и др. О компоновке конструктивных элементов схем ЦВМ. В кн.: Вычислительные системы, Новосибирск, 1973, № 54.

69. Мелихов А.Н. и др. Применение гиперграфов для компоновки схем в ячейки. Изв.Ш СССР, Техническая кибернетика, 1974, I 3.

70. Мелихов А.Н., Карелин В.П., Курейчик В.М. О разрезании графов на подграфы. В кн.:Математическое моделирование и теория электрических цепей. Киев, "Наукова думка",1973, № 10.

71. Мелихов А.Н. и др. Компоновка модульных схем. В кн.¡Вычислительная техника, том Ш, Каунас, КПИ, 1972.

72. Миницкий Е.А., Смирнов В.И. Некоторые вопросы конструирования микроэлектронной бортовой аппаратуры."Известия ЛЭТИ", Л.,1972, вып.113.

73. Мишин Ю.С.»Толоконников В.К. Алгоритм минимизации числа пересечений при автоматической трассировке печатных плат. В кн.: Вычислительная техника. Межвузовский сборник,Рязань, 1974,вып.

74. Морозов К.К., Одиноков В.Г. Использование ЭЦВМ при конструировании некоторых узлов радиоэлектронной аппаратурыГМ,, "Сов.радио", 1972.

75. Ноткин Р.Г. Об одной задаче покрытия."Кибернетика", 1971,$5.

76. Нотц, П1иша,Смит Дж.,Смит М.Технико -экономические вопросы построения больших интегральных систем обработки данных . "Электроника", (рус.пер.),1967, № 4.

77. Орлова Г.И., Доран Я.Г. Оптимальное деление графа на несколько подграфов. "Известия Ж СССР. Техническая кибернетика", 1972, № I.

78. Переворот в технике компоновки электронной аппаратуры.

79. Обзор "Электроника", (рус. пер.),1965, № 21,22,24 и 1966,$ 3.

80. Петрил. Современное состояние технологии больших интегральных систем."Зарубежная радиоэлектроника",1969, № 6.

81. Погребной В.К. Разработка и исследование алгоритмов автоматизации технического этапа проектирования вычислительных устройств. Канд.дис.Томск,ТПИ,1970.

82. Пресман Л.С. Минимальная реализация заданного графа. "Кибернетика", 1971, №2.

83. Проектирование цифровых вычислительных машин. Под ред.

84. С.А.Майорова,"Высшая школа", 1972.

85. Проектирование сверхбыстродействующей системы. Комплекс "Стретч".Под ред. В.Бухгольца. М.,"Мир",1965.

86. Разработка машинных методов проектирования печатных соединений. Отчет по НИР, регистрационный $ 73065183,Рязань, 1974.

87. Руссо Р.,Вольф П. Распределение и преобразование логических элементов с помощью цифровых вычислительных машин. В кн.: Автоматизация в проектировании",М.,"Мир", 1972.

88. Рылеева С.С. Полупроводниковые интегральные схемы в США. Обзор научно-технической литературы по электронной технике.1. М., ЦНИИТЭИМ, 1967, № II.

89. Самофалов К.Г., Кухарчук А.Г., Луцкий Г.М. Структуры ЭЦВМ четвертого поколения,Киев,"Техника",1972.

90. Сапожков К.А., Бершадский A.M., Соловьев В.В. Разрезание графа схемы волновым алгоритмом. В кн.: Вычислительная техника .Каунас,КПИ,I975.

91. Сафонов И.В. Об одном алгоритме унификации операционных блоков цифровых машин. "Автоматика и вычислительная техника", Рига, 1972, № 4.

92. Селютин В.А. Минимизация числа выводов при компоновке электронных узлов. В кн.: Вычислительная техника, том Ш, Каунас, КПИ, 1972.

93. Скарлетт Дж. ТТЛ интегральные схемы и их применение. М.,"Мир",1974.

94. Соколов В.Г. Об одном методе увеличения регулярности.

95. В кн.: Интегральная электроника и вычислительная техника. М.,Изд.ИТМ ВТ АН СССР, 1968, вып.1.

96. Сомкин В.М. и др. К вопросу об унификации блоков элементов вычислительных машин третьего поколения."Труды НИИ УВМ", 1971, вып.З.

97. Тафинцев В.А., Штейнберг В.И. О формировании библиотеки модулей для покрытия заданной логической схемы. "Вопросырадиоэлектроники",сер.УП,Электронная вычислительная техника,лгч Л «•}

98. Тенденции компоновки элементов электронных схем, применяемых в авиакосмической и военной технике. "Зарубежная электронная техника", 1973, 18.

99. Тимофеев Б.Б., Куликов М.Я. О разбиении логических сетейна типовые структуры. "Управляющие системы и машины",1973,5.

100. Титков В.И. Компоновка функциональных схем по типовым элементам замены (ТЭЗ). В кн.: Алгоритмические методы проектирования цифровых систем. Ленинград, ЛИТМ0Д972.

101. Турчина Е.Д. Исследование методов построения ЦВМ на основе унифицированных функциональных узлов. "Труды ЛШ",Ленинград, 1969, № 72.

102. Файзулаев Б.Н., Никитин В.М. Выбор оптимальной геометрии и компоновки функциональных узлов процессора быстродействующих ЭВМ."Вопросы радиоэлектроники", сер.УП, Электронная вычислительная техника, 1970, вып.З.

103. Цой С., Цхай С.Н. Прикладная теория графов, Алма-Ата,"Наука", 1971.

104. Чуев Ю.В., Спехова Г.П. Технические задачи исследования операций.!., "Сов.радио",1971.

105. Шор Н.З. ,Мараховский Л.Ф. Выбор оптимальной совокупности типовых элементов, "Труды семинара Теория автоматов и методы формализованного синтеза вычислительных машин и систем",Киев, 1968, вып.5.

106. Шрамченко Б.Л. О некоторых ограничениях задачи компоновки модульных схем. В кн.: Вычислительная техника, Каунас,ЕЛИ,1975.

107. Штейн М.Е., Штейн Б.Е. Методы машинного проектирования цифровой аппаратуры.М.,"Сов.радио", 1973.103104105106107108109110111112113114115116

108. Bracchi G. On the generation of system partitions for large-scale integration. IEEE Trans.Syst.Man and Cybern. 1971,1,N4.

109. Eireuer M.A. Recent developments in design automation. Computer (USA).1972,5,H3.

110. Ferrari D.,Sami M. An algorithm for partitioning networks into limited sets of different subnetwork. In Dig.1969. IEEE Int.Symp.Circuit Theory.

111. Haspel C.H. Automatic paeaging of computer circuit. IEEE Int. Convention Record .1965,pt.3.

112. Habayeb A.R. System decompozition, partitioping and integration for microelectronics. IEEE Trans.Syst.Sci.Cybera .1968, vol. SSC-4,N7.

113. Kernighan B. W. ,Lin S. An efficient heuristic procedure for partitioning graphs. Bell Syst.Tech.Journal .1970,vol.49«

114. Russo R.L. On the tradeoff between logic performance and circuit-to-pin ratio for LSI. IEEE Trans.Comput. 1972,H2.

115. Russo R.L.,0den P.H.,Wolff P.K. A heuristic procedure for the partitioning and mapping of computer logic graphs. IEEE Trans. Comput. 1971,vol.C-20,December.блок-схема алгоритма /Ч