автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Исследование и разработка алгоритмов размещения компонентов ГБИС с помощью ЭВМ

ВВЕДЕНИЕ.

1. СОВРЕМЕННОЕ СОСТОЯНИЕ ПРОБЛЕМЫ АЛГОРИМЧЕСКОГО РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ.

1.1. Анализ критериев размещения.

1.2. Классификация алгоритмов размещения.

1.2.1. Класс точных алгоритмов.

1.2.2. Класс приближенных алгоритмов.

1.2.3а Интерактивные алгоритмы.

1.3. Анализ алгоритмов размещения разногабаритных элементов.

1.4. Анализ методов оценки эффективности алгоритмов размещения.

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

Выводы.

2. МАКРОЭЛЕМЕНТНЫЙ ПРИНЦИП РАЗМЕЩЕНИЯ РАЗНОГАБАРИТНЫХ ЭЛЕМЕНТОВ.

2.1. Макроэлементный метод и его этапы.

2.2. Методика выбора габаритных размеров макроэлементов

2.3. Последовательное распределение посадочных мест и назначение в них компонентов в макроэлементах

2.4. Размещение макроэлементов в регулярном монтажном поле.

2.5. Алгоритм размещения компонентов, основанный на макроэлементном принципе размещения.

Выводы.

3. ПОСЛЕДОВАТЕЛЬНОЕ РАЗМЕЩЕНИЕ РАЗНОГАБАРИТНЫХ КОМПОНЕНТОВ МЕТОДОМ СКАНИРОВАНИЯ В ДИСКРЕТНОМ ПРОСТРАНСТВЕ.

3.1. Унифицированное посадочное место и способ его представления в дискретном поле.

3.2. Выбор и обоснование применяемого критерия качества размещения.

3.3. Стратегия выбора компонентов для размещения

3.4. Методика поиска посадочных мест в дискретном пространстве.

3.5. Алгоритм размещения разногабаритных компонентов

Выводы.

4. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ РАЗМЕЩЕНИЯ РАЗНОГАБАРИТНЫХ КОМПОНЕНТОВ.

4.1. Организация программных комплексов для размещения разногабаритных компонентов

4.2. Экспериментальная оценка эффективности алгоритмов размещения.

4.3. Рекомендации по применению алгоритмов размещения

Выводы.

В настоящее время системы автоматизированного проектирования (САПР) нашли применение во многих отраслях промышленности, но особенно прочное место они заняли в области создания устройств электронно-вычислительной техники, чему во многом способствовало то, что современные электронно-вычислительные МЭБШНЫ (ЭВМ) и устройства электронно-вычислительной аппаратуры (ЭВА) строятся по модульному многбуровнему иерархическому принципу [74], что во многом облегчает автоматизацию процесса проектирования.Преимущества САПР хорошо известны [72J , поэтому в решениях ХХУ1 съезда ЕПСС было указано о необходимости дальнейшего расширения автоматизации проектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники.В последние годы большие работы ведутся по созданию ЭВМ четвертого поколения, элементную базу которых составляют боль шие интегральные схемы (БЙСы) и гибридные большие интегральные схемы (ГБИСы). Ш С ы и ГЕЙСы характеризуются разнообразием размеров и форм составляющих их компонентов. Алгоритмическая база большинства действующих САПР ЭВМ и ЭВА рассчитана на проектирование модулей с регулярной топологией. Разногабаритность компонентов Ш С и ГЕЙС не позволяет использовать эти методы проектирования и, презкде всего, методы решения задачи размещения компонентов схем.Следовательно, актуальной является проблема создания новых эффективных методов и алгоритмов, способных обеспечить размещение разногабаритных компонентов.В ходе решения поставленной проблемы предстоит выбрать математическую модель, описывающую топологию ГБЙС и БИС, разрабо- 5 тать эффективную алгоритмическую базу для решения задачи размещения разногабаритных компонентов, включить разработанную подсистему размещения разногабаритных компонентов в состав действущей системы автоматизированного проектирования топологии констрзгктивно-функциональных узлов (САПР КФУ) ЭВА. Целью работы являются анализ существукщих методов и алгоритмов размещения компонентов, разработка новых алгоритмов для подсистемы размещения разногабаритных компонентов с использованием ЭВМ третьего поколения.Предмет и методы исследования. Предметом исследования являются алгоритмические методы решения задачи размещения разногабаритных компонентов ГБИС, БИС и многослойных печатных плат (МПП) и созданные на их основе машинные алгоритмы.Методы исследования базируются на анализе содержательных аспектов проблемы, использовании методов теории множеств,теории графов, прикладного программирования и на экспериментах с программной реализацией предложенных алгоритмов.Научная новизна работы заключается в получении следующих результатов: - разработан макроэлементный метод размещения разногабаритных компонентов и на его основе алгоритм размещения компонентов ГБИС и БИС; - исследована матричная модель монтажного поля, введено понятие унифицированного посадочного места и разработан способ его представления в матричной модели; - разработан алгоритм размещения разногабаритных компонентов, использзгщий в качестве критерия оптимизации функцию, обеспечиваицую равномерное распределение соединений по всей площади коммутационного поля и сокращащую число слоев коммутации на этапе трассировки; > 6 - разработан единый методологический подход, объединящий ряд частных методик,предназначенных для оценки эффективности алгоритмов размещения в зависимости от класса проектируемых схем.Практическая ценность. Применение алгоритмов,разработанных в работе, позволяет включить их в качестве подсистемы в систему автоматизированного проектирования КФУ ЭВА. Практическая эксплуатация разработанной подсистемы показала,что использование предложенных алгоритмов позволяет повысить плотность упаковки размещенных компонентов, повысить процент автоматически разведенных соединений, уменьшить число слоев коммзгтации и улучшить технологичность изделия.На основании данных экспериментальных исследований вырабо таны рекомендации по применению алгоритмов размещения и исполь зованию режимов их работы.Реализация работы. Результаты диссертационной работы использовались для создания подсистемы размещения разногабаритных компонентов, входящей в состав системы автоматизированного проектирования топологии ШУ ЭВА в рамках операционной системы ЭВМ третьего поколения (ОС ЕС). Разработанная система внедрена на ряде предприятий. Суммарный экономический эффект от внедрения составил 25,8 тыс.рублей.Апробация работы. Основные научные положения диссертации опубликованы в 6 печатных работах и докладывались автором на: - семинаре "Автоматизация проектирования электронно-вычислительной аппаратуры" ДЩПП, Ленинград, май 1980; - ли ЕХ5илейной научно-технической конференции профессорско-преподавательского состава Ленинградского института точной механики и оптики, Ленинград, октябрь 1980; - семинаре "Машинные методы проектирования электронно-внчисли тельной аппаратуры" ДЩИП, Ленинград, июнь I98I. - 7 Работа состоит из введения, четырех глав, заключения и списка литератзгрн.В первой главе рассмотрены целевые функции, с помощью которых осуществляется один из этапов проектирования - этап размещения элементов, приведена классификация применяемых критериев.Анализируются методы, используемые для решения задач размещения.Особое место уделено алгоритмам размещения разногабаритных элементов, дана их классификация. Рассмотрены способы, оценивающие эффективность алгоритмов размещения, проведен их анализ. Приведена постановка задачи диссертационной работы.Вторая глава посвящена разработке метода размещения разногабаритных компонентов в непрерывном монтажном поле. Сформули рован макро элементный принцип размещения компонентов. Предложен способ для определения площади посадочных мест для разногабаритных компонентов. Разработан алгоритм, использующий идею макроэлементного метода, позволяиций успешно размещать разногабаритные компоненты.В третьей главе рассматривается матричная модель монтажного поля, вводится понятие унифицированного посадочного места.Обосновывается критерий, применяемый для выбора посадочных мест размещаемых компонентов ГБИС и МПП. Формулируются правила последовательного выбора компонентов для размещения. Описан метод сканирования, осуществляюощй поиск посадочных мест в модифицированной матричной модели поля. Приведено описание разработанного алгоритма размещения разногабаритных компонентов.Четвертая глава отведена вопросам организации разработан ных программ в виде функциональных программных модулей,включен-. ных в действущую систему автоматизированного проектирования топологии конструктивно-функциональных узлов, и проведению экс- 8 периментальннх исследований разработанных алгоритмов. Приводятся данные сравнения разработанннх алгоритмов с известными алгоритмами согласно предложенной методике оценки эффективности.Даются рекомендации по использованию предложенных алгоритмов. - 9

ВЫВОДЫ

1. Разработаны функциональные программные модули по разме -щению разногабаритных компонентов для их включения в состав САПР КФУ.

2. Предложен единый методологический подход для оценки эффективности алгоритмов размещения, основанный на использовании ряда частных методик.

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

4. На основании экспериментальных данных выработаны рекомендации по применению разработанных алгоритмов.

ЗАКЛЮЧЕНИЕ

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

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

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

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

5. Разработан алгоритм размещения разногабаритных компонентов с использованием метода сканирования для поиска местоположения посадочных мест.

6. Приведена организация разработанных программ в виде функциональных программных модулей САПР КФУ.

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

1. Абрайтис Л.Б., Жилевичюс В.А. Исследование эффективности алгоритмов размещения. - В кн.: Вычислительная техника. Т.2, Каунас, 1971, с.86-93.

2. Абрайтис Л.Б., Жилевичюс В.А. Дополнительные экспериментальные исследования алгоритмов размещения элементов. В кн.: Вычислительная техника. Т.З, Каунас, 1972, с.354-359.

3. Абрайтис Л.Б., Лазаускас Д.А. Простой алгоритм размещения. В кн.: Вычислительная техника. Т.6, Каунас, 1974, с.83-86.

4. Абрайтис Л.Б., Рубляускас Д.А., Штуйкис В.А., Матицка.с И.-К.Л. Подсистема автоматизации проектирования топологии БИС ячеечного типа. Управляющие системы и машины, 1974, $ 5,с.79-81.

5. Абрайтис Л.Б., Шейнаускас Р.И., Жилевичюс В.А. Автоматизация проектирования ЭВМ. М.: Сов.радио, 1978.- 272 е., ил.

6. Абрайтис Л.Б., Шейнаускас Р.И., Жилевичюс В.А. Алгоритм для совместного решения задач компоновки и размещения. В кн.: Вычислительная техника. Т.2, Каунас, 1971, с.57-60.

7. Артемов В.Б., Рябов Л.П. Целевая функция и алгоритм расстановки для максимизации числа прямоугольных проводников.- Обмен опытом в радиопромышленности, 1975, вып.6, с.105-107.

8. Артемов В.Б., Рябов Л.П. Алгоритм размещения модулей различных габаритов на печатной плате. Обмен опытом в радиопромышленности, 1977, вып.2, с.29-31.

9. Арустамов С.А. Процедура параллельного размещения компонент и трассировки микросборок ГБИС. В кн.: Вычислительная техника. Т.8, Каунас, 1976, с.95-97.

10. Арутюнян К.Р. Об одном подходе к решению задач оптимизации монтажных соединений ЦУ. В кн.: Вычислительная техника.Т.З, Каунас, 1972, с.360-363.

11. Батшцев Д.Н., Морозов В.Ф., Полозов B.C. Алгоритмическое размещение геометрических объектов в задаче конструирования интегральных схем. В кн.: Вычислительная техника в машиностроении. Минск, ИТК АН БССР, декабрь, 1973, с.81-89.

12. Бахтин Б.И. Метод вычислений и характеристики оценочной функции размещения в АСП "Автограф". В кн.: Автоматизированные системы проектирования. М., МДНТП, 1975, с.95-100.

13. Бахтин Б.И. Характеристики алгоритма парных перестановок.- В кн.: Вычислительная техника. Т.7, Каунас, 1975, с.322-325.

14. Бахтин Б.И. Алгоритм перестановок конструктивных единиц для проектирования цифровых устройств. В кн.: Вычислительная техника. Т.2, Каунас, 1971, с.99-105.

15. Бахтин Б.И. Построение электрических цепей алгоритмами размещения. В кн.: Вычислительная техника. Т.6, Каунас, 1974, с.354-359.

16. Бахтин Б.И. Статистический метод оценки эффективности алгоритмов размещения компонентов электронной аппаратуры.- В кн.: Вычислительная техника. T.I, Каунас, 1970, с.282-287.

17. Бахтин Б.И., Костюк В.И. Анализ характеристик решения задачи размещения методом случайного назначения. В кн.: Вычислительная техника. Т.4, Каунас, 1973, с.94-99.

18. Бахтин Б.И., Костюк В.И. Структурное размещение радиоэлементов при машинном проектировании печатных узлов. В кн.: Микроэлектроника в вычислительной технике, 'Материалы к краткосрочному семинару. 1., ЛДНТП, 1975, с.89-90.

19. Бахтин Б.И., Скорубский В.И. Оценка парных перестановок.- В кн.: Автоматизация и алгоритмизация проектирования цифровых устройств и систем. Материалы к краткосрочному семинару. 4.1. Л., ЛДНТП, 1971, с.55-60.

20. Белов А.Ф., Горячев A.A., Курков Е.В. Обзор алгоритмов размещения компонентов на печатных платах. Ядерное приборостроение, 1972, вып.18, с.22-31.

21. Белов А.Ф., Курков Е.В., Горячев A.A., Зайцева Н.П. Решение задачи размещения модулей на плате по минимуму суммарной длины связей на ЭВМ "Минск-32". Ядерное приборостроение, 1972, вып.13, с.40-47.

22. Бершадский А.М., Былкин В.Д., Игошина Л.В. Об одном из подходов к решению задачи размещения элементов в монтажном пространстве. В кн.: Вычислительная техника. Т.II, Каунас, 1978, с.80-83.

23. Бершадский A.M., Лебедев В.Б., Фионова Л.Р. Построение функции качества в задачах размещения разногабаритных элементов. В кн.: Вычислительная техника. Т.12, Вильнюс, 1979, с.78-81.

24. Бершадский A.M., Соловьев В.В., Щербань А.Б. Связь задачи размещения элементов в монтажном пространстве с проблемой изоморфного вхождения. В кн.: Вычислительная техника. Т.8, Каунас, 1976, с.58-60.

25. Берштейн Л. С., Селянкин В.В. Об одном методе размещения элементов схем. В кн.: Однородные цифровые вычислительные и интегрирующие структуры. Таганрог, 1975, вып.З, с.188-194.

26. Берштейн Л.С., Селянкин В.В. Применение гиперграфов для точного решения задачи линейного размещения элементов. В кн.: Вычислительная техника. Т.6, Каунас, 1974, с.54-56.

27. Бойко В.Н., Герасименко Е.П., Кот В.И. Размещение модулей волновым алгоритмом с учетом метрикотопологических требова -ний. В кн.: Вычислительная техника. Т.8, Каунас, 1976, с.80-82.

28. Бойко В.Н., Дгомина С.Г. и др. Методы размещения модулей произвольной формы и трассировки печатных проводников различной ширины. Приборы и системы управления, 1975, № 7, с.13-16.

29. Боли Л.А. Особенности поэтапного проектирования топологии БИС по единой функции цели. В кн.: Автоматизация проекти -рования и производства электронно-вычислительной аппаратуры. Материалы краткосрочного семинара. - Л., ЛДНТП, 1973, с.36-38.

30. Бугаев Е.С., Юрин О.И. Общий алгоритм размещения элементов с нефиксированными связями. В кн.: Автоматизированные системы проектирования. М., МЛНТП, 1975, с.90-94.

31. Гайфуллин Э.Ш., Брежнев В.И., Кунин В.А. Алгоритмы размещения разногабаритных связных объектов в двухмерном пространстве. -В кн.: Труды МЭИ. М., 1975, вып.216, с.80-83.

32. Гейко Г.Д. Анализ методов размещения разногабаритных элементов. Ленинград, 1980.- 19 с. - Рукопись представлена Ленинград, ин-том точной механики и оптики. Деп. в ЦНЙИТЭИприборо-строения 3 июля 1980, № 1346.

33. Гейко Г.Д. Анализ формы монтажного поля и влияние ее на качество размещения.- В кн.: Автоматизация проектирования электронно-вычислительной аппаратуры. Материалы краткосрочного семинара. Л.,ЛДНТП,1980,с.20-25.

34. Гейко Г.Д. Алгоритм широкого применения по размещению разногабаритных элементов. Ленинград, 1981. - 8 с. - Тукопись представлена Ленинград.ин-том точной механики и оптики. Деп. в ЦНИИТЭИприборостроения 15 июня 1981, В 1582.

35. Гейко Г.Д. Макроэлементный принцип размещения разногабаритных элементов. Ленинград, 1981. - 9 с. - Рукопись представлена Ленинград.ин-том точной механики и оптики. Деп. в ЦНИИТЭИ-приборостроения 15 июня 1981, $ 1581.

36. Герасименко Е.П., Зозулевич Д.М. Минимизация вычислительного процесса при решении геометрических задач с помощью рецеп-торных матриц. В кн.: Вычислительная техника в машиностроении. Минск, НТК АН БССР,июнь, 1970, с.26-40.

37. Герасименко Е.П., Кот В.И. Размещение модулей произвольной геометрической формы на платах с печатным монтажом. В кн.: Труды научно-исследовательского института управляющих и вычислительных машин. Северодонецк, 1970, вып.2, с.72-76.

38. Гиль И.И., Хаммурадов М.А., Коновко A.B., Путяхин В.П. Оптимизация тепловых режимов элементов РЭА посредством их рационального размещения. В кн.: Вычислительная техника. Т.8, Каунас, 1976, с.69-72.

39. Гинзбург Б.Д. Алгоритм размещений модулей на плате. -Обмен опытом в радиопромышленности, 1972, вып.4, с.31-33.

40. Гинзбург Б.Д., Никитина Р.К. Новый подход к задачам размещения микросхем на плате и закрепления внешних контактов. -Вопросы радиоэлектроники. Сер.ЭВТ, 1972, вып.З, с.85-92.

41. Глориозов Е.А., Сыпчук П.П., Трубочкина Н.К. Об одном алгоритме проектирования топологии интегральных схем. В кн.: Автоматизация технического и схемотехнического проектирования. Труды МИЭМ. T.I. М., 1975, с.150-156.

42. Головачев Л.Б., Безруков В.И., Колесников Н.П., Малеева М.А. Размещение разноразмерных элементов на печатной плате.-Обмен опытом в радиопромышленности, 1977, вып.2, с.32-33.

43. Горанский Г.К., Зозулевич Д.М., Шерлинг Д.Р. Алгебро-логический метод решения геометрических задач при автоматизации проектирования с помощью ЭВМ. В кн.: Вычислительная техника в машиностроении. Шнек ИТК АН БССР, апрель, 1967, с.121-127.

44. Гуревич Д.З., Селготин В.А. Алгоритмические методы проектирования топологии БИС ячеечного типа. В кн.: Методы расчета и автоматизации проектирования устройств микроэлектронных ЦВМ. Киев, АН УССР, 1973, с.83-92.

45. Гурьянова Ф.А., Никитин С.А., Пкро Г.Э. Автоматизиро -ванная система изготовления конструкторской документации.- Электронная техника. Сер.З. Микроэлектроника, 1975, вып.2(56),с.103-107.

46. Деньдобренко Б.Н., Асланянц В.Р. Алгоритм размещения разногабаритных элементов на укладках гильотинного типа. В кн.: Микроэлектроника в вычислительной технике. Материалы семинара молодых ученых и специалистов. Л., ДДЕПП, 1974, с.84-89.

47. Забара С.С. О выборе структуры интерактивной графической системы проектирования. Управляющие системы и машины. 1978, № 6, с.100-105.

48. Иванников А.Д., Чистякова В.И. Определение внешних электрических характеристик цифровых МДП ИС по известной топологии. Электронная техника, Сер.З. Микроэлектроника, 1975, вып. 2(56), с.86-91.

49. Карапетян A.M. Автоматизация оптимального конструирования электронных вычислительных машин. М.: Сов.радио, 1973. -152 с., ил.

50. Карапетян A.M., Барсегян П.Л. О размещении типовых элементов конструкции с учетом критериев надежности. Вопросы радиоэлектроники. Сер.ЭВТ, 1971, Вып.8, с.131-135.

51. Кикутс Я.А. О проблеме размещения радиоэлектронных элементов на плате печатного монтажа. В кн.: Вычислительная техника. T.I, Каунас, 1970, с.280-281.

52. Кожухарь А.Ф., Оранов A.M. Алгоритм размещения множества вершин взвешенного графа в произвольном связном графе.-Управляющие системы и машины, 1975, I, с.122-125.

53. Комяк В.М., Гиль Н.И., Гернет В.Д. К вопросу о размещении радиоэлементов на плате.- В кн.: Вычислительная техника.Т.7, Каунас, 1975, с.329-332.

54. Конструирование и расчет БГИС, микросборок и аппаратуры на их основе./ Под ред.Б.Ф.Высоцкого М.: Радио и связь, 1981, - 216 с., ил.

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

56. Кудрявцев В.А. Способы организации автоматического конструирования плат минимальной площади. В кн.: Применение вычислительных машин в проектировании и производстве печатного монтажа. Материалы к краткосрочному семинару. Л., ЛДНТП, 1975,с.10-13.

57. Курейчик В.М., Калашников В.А. Об одном методе технического проектирования устройств на БИС. В кн.: Методы расчета и автоматизация проектирования устройств микроэлектронных ЦВМ. Киев, 1973, с.12-24.

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

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

60. Линский B.C. Об оптимальном размещении ячеек на стойке ЦВМ. Вопросы радиоэлектроники. Сер.ЭВТ, 1961, вып.З, с.17-26.

61. Майоров С.А., Петухов Г.А., Демьяхин В.А. Об одном подходе к монтажно-коммутационному проектированию печатных структур цифровых устройств. Управляющие системы и машины, 1975, № I, с.122-125.

62. Майоров С.А., Петухов Г.А., Скорубский В.И., Соколова Н.С., Чесноков М.И. О задаче размещения конструктивных единиц при проектировании цифровых устройств. В кн.: Вычислительная техника, T.I, Каунас, 1970, с.275-279.

63. Матицкас И.-К.Л. Размещение разногабаритных элементов с учетом коммутаций. В кн.: Вычислительная техника. Т.8, Каунас, 1976, с.73-76.

64. Матицкас И.-К.Л. Алгоритм размещения разногабаритных элементов в кратные позиции. Управляющие системы и машины.1979, JS 4, с. 120-123.

65. Матицкас И.-К.Л., Рубляускас Д.А. Итерационный алгоритм размещения разногабаритных элементов. В кн.: Вычислительная техника. Т.6, Каунас, 1974, с.57-59.

66. Матицкас И.-К.Л., Рубляускас Д.А. Алгоритм совместного размещения ячеек и трассировки соединений БИС. В кн.: Вычислительная техника. Т.4, Каунас, 1973, с.78-81.

67. Матюхин Н.Я. Автоматизация проектирования цифровых устройств. В кн.: Применение вычислительных машин при проектировании цифровых устройств./ Под ред.Н.Я.Матюхина. - М.: Сов.радио, 1968, с.5-43.

68. Медведев A.C., Ревенко В.Н., Штейн М.Е. О решении задач оптимизации, предшествующих трассировке печатных соединений.

69. В кн.: Вычислительная техника. Т.8, Каунас, 1976, с.91-94.

70. Медведев A.C., Штейн М.Е. О задачах компоновки и размещения компонентов цифровых узлов. Управляющие системы и машины, 1979, № I, с.70-73.

71. Микстуров В.М., Евтеев В.Г. Исследование работы программ комбинированного размещения кристаллов в МИС. В кн.: Вычислительная техника. Т.6, Каунас, 1974, с.61-65.

72. Морозов К.К., Одиноков В.Г. Использование ЭЦВМ при конструировании некоторых узлов РЭА. М.: Сов.радио, 1972.- 104 е., ил.

73. Одиноков В.Г. О двух методах случайного размещения элементов РЭА. В кн.: Вычислительная техника. Т.З, Каунас, 1972, с.337-340.

74. Петренко А.И., Добронравов O.E., Цурин О.Ф. и др. Диалоговая система проектирования топологии гибридных интегральных схем. Управляющие системы и машины, 1977, № 3, с.114-118.

75. Петренко А.И., Тетельбаум А.Я. Метод размещения компонентов при их точечной аппроксимации. В кн.: Вычислительная техника. Т.7, Каунас, 1975, с.307-310.

76. Петренко А.И., Тетельбаум А.Я., Щрамченко Б.Л. Автоматизация конструирования электронной аппаратуры. Киев.: Вшца школа, 1980. - 176 е., ил.

77. Петросян A.B., Анастасян Ю.Г. Об одной задаче оптимального размещения. Вопросы радиоэлектроники. Сер.ЭВТ, 1971, вып. 8, с.80-87.

78. Петросян A.B., Маркосян С.Е., Мелик-Адамян Ж.Э., Геоле-цян Г.Г. Этап размещения при МИ АППП. В кн.: Вычислительная техника. Т.6, Каунас, 1974, с.66-69.

79. Покровский А.Н. Обзор алгоритмов компоновки, размещения модулей и трассировки печатного монтажа при конструировании радиоэлектронной аппаратуры. Вопросы радиоэлектроники. Сер. ОТ, 1967, вып.14, с.106-128.

80. Помазанов В.М. К задаче размещения ячеек в панели.

81. В кн.: Применение вычислительных машин для проектирования цифровых устройств./ Под ред.Н.Я.Матюхина.- М.: Сов.радио, 1968, с.165-182.

82. Поцене Б.А., Рубляускас Д.А. Результаты экспериментального исследования алгоритма размещения разногабаритных элемен -тов.- В кн.: Вычислительная техника. Т.8, Каунас, 1976,с.77-79.

83. Розанов В.А., Сыпчук П.П., Юрин О.Н. Анализ методов решения задачи размещения. В кн.: Проблемы автоматизации проектирования и производства ЭВМ. Труды МИЭМ. 4.1, М., 1971, вып.16, с.84-113.

84. Розанов В.А., Юрин О.Н. Расположение модулей и трассировка соединений в многослойных печатных платах. Вопросы радиоэлектроники. Сер.ОТ, 1967, вып.14, с.129-136.

85. Рустамов И.А., Тготин A.A. О решении задачи размещения конструктивных компонентов с учетом требований трассировки. -Управляющие системы и машины, 1975, № 6, с.107-115.

86. Рустамов И.А., Тютин A.A. Об одной реализации алгоритма размещения графа на плоскости. В кн.: Вычислительная техника. Т.8, Каунас, 1976, с.83-85.

87. Рычков Л.А., Кузьмин Б.А., Эйдес A.A. Алгоритм размещения радиоэлементов разной формы. Приборы и системы управления, 1979, В 2, с.1-3.

88. Селютин В.А. Машинное конструирование электронных устройств. М.: Сов.радио, 1977. - 384 е., ил.

89. Селютин В.А., Гуревич Д.З., Кукланс А.И. Разработка топологии БИС с помощью ЦВМ. В кн.: Автоматизация и алгоритмизация проектирования цифровых устройств и систем. Материалы к краткосрочному семинару. 4.1, Л., ДЦНТП, 1971, с.42-45.

90. Селютин В.А., Улыбин Б.Н. О приближенных методах решения задачи размещения. В кн.: Вычислительная техника. T.I, Каунас, 1970, с.269-274.

91. Скорубский В.И. 0 расширении класса исследуемых перестановок модулей при оптимизации размещения. В кн.: Вычисли -тельная техника. Т.2, Каунас, 1971, с.94-98.

92. Стоян Ю.Г., Соколовский В.З. 0 решении одной задачи размещения методом сужающихся окрестностей. Управляющие системы и машины, 1978, Jä 5, с.114-116.

93. Теория и методы автоматизации проектирования вычислительных систем./ Под ред.М.Брейера.- М.: Мир, 1977.- 284 е.,ил.

94. Тетельбаум А.Я. Алгоритм перехода от идеальных координат размещения компонентов к системе фиксированных позиции.

95. В кн.: Вычислительная техника. Т.7, Каунас, 1975, с.311-314.

96. Тетельбаум А.Я. Последовательно-параллельный алгоритм размещения электронных компонентов. Управляющие системы и машины, 1977, В 5, с.II8-I22.

97. Федулов А.А. Размещение элементов и распределение внешних контактов на печатной плате в системе автоматизированного проектирования. Обмен опытом в радиопромышленности, 1975, вып. 6, с.105-107.

98. Шендерович Ю.И. Комплексная автоматизация разработки больших интегральных схем. Управляющие системы и машины, 1974, В 5, с.30-35.

99. Широ Г.Э., Осипов Л.Б. Размещение компонентов интегральных схем. В кн.: Применение вычислительных машин для проектирования цифровых устройств./ Под ред.Н.Я.Матюхина. - М.: Сов.радио, 1968, с.183-198.

100. Штейн М.Е., Медведев А.С. К задаче размещения компонент. Управляющие системы и машины, 1974, В 2, с.77-80.

101. Штейн М.Е., Штейн Б.Е. Методы машинного проектирования цифровой аппаратуры. М.: Сов.радио, 1973. - 296 е., ил.

102. Duggal R., Holland Т., Messinger Н.Р. A comparison of new and existing placement algorithms for auto-print circuit board layout. Proc. Hat. Electr. Conf.f 1968, v.29, p.694-700.

103. Gilmore P.O. Optimal and suboptimal algorithms for the guadratic assignment problem. J. SIAM, 1962, June, N 2, v.10, p.305-313.

104. Rosental G.W. Computing machine aids to a development project. IRE Trasaction an Electronic Computers, 1961, v.EC-10, N 3, p.400-406.