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

Введение

Глава I. Анализ задач размещения стационарных тепловыделяющих источников

1.1. Общая постановка оптимизационной задачи размещения источников тепла, анализ ее особенностей

1.2. Обзор алгоритмов решения задачи размещения источников тепла II

1.3. Особенности размещения источников тепла многокристальной микросборки

1.4.'' Анализ методов проектирования проводящих покрытий 22 Выводы

Глава 2. Расчет температурного поля в многокристальной микросборке

2.1. Тепловая модель полупроводниковой микросхемы

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

2.3. Численная реализация метода расчета температурного поля твердой интегральной микросхемы

2.4. Тепловой расчет гибридных интегральных схем

2.5." Метод расчета температурного поля Ж МСБ

2.6.' Экспериментальное сравнение методов расчета температурного поля

Выводы

Глава 3. Размещение тепловыделяющих источников многокристальной микросборки 62 3.1v Постановка задачи размещения источников тепла

3.2. Построение матрицы температурных коэффициентов 63 « *

3.3. Алгоритм размещения тепловыделяющих источников 3;4. Расчет электрических параметров МК МСБ

Выводы

Глава 4, Трассировка межфрагментных соединений в многокристальной микросборке

4.1• Постановка задачи трассировки

4.2. Алгоритм построения минимальных деревьев электрических цепей

4.3.' Алгоритм определения внутренне устойчивого множества графа пересечений

4 •4» Минимизация числа слоев МК МСБ 113 4» 5. Экспериментальное сравнение эффективности алгоритмов раскраски 123 4.6v Общая характеристика комплекса программ сквозного проектирования микроэлектронной аппаратуры

Выводы

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

Основными направлениями экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года, принятые на

ХХУ1 съезде КПСС, предусмотрено "расширять автоматизацию проект-•« но-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники.,", а также ".«.;развитие математической теории, повышение эффективности ее использования в прикладных целях v."

Создание больших комплексов микроэлектронной аппаратуры (МЭА), а также использование многокристальных микросборок (МК МСБ) сделало малоэффективными традиционные принципы и методы проектирования радиоэлектронных устройств. В связи с широким использованием МЭА в различных областях науки, техники и производства, а также постоянным ее усложнением и обновлением, стремительно стали развиваться теория и практика применения машинного проектирования микроэлектронных устройств и систем.

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

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

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

Особое значение при создании МЭА имеет нагрев элементов. Новая элементная база," появившаяся в результате освоения производства интегральных схем, не устранила проблему теплового режи~ ма. Наоборот, повышение на несколько порядков плотности монтажа и непригодности большинства существующих систем охлаждения для

МЭА (из-за больших габаритов и веса) делают проблему теплового % режима еще актуальнее.

Предлагаемые в работе методы и алгоритмы оптимизации температурных полей МК МСБ позволяют обеспечить надежность МЭА по тепловому фактору еще на стадии разработки.

Размещение источников тепла можно представить как систему со следующими свойствами /26 /:

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

2) на область допустимых решений наложены ограничения, обусловленные геометрической формой области и размещаемых в ней источников;

3) температурное поле должно иметь заданные количественные либо качественные характеристики;

4) решение задачи состоит в переводе системы в оптимальное состояние, т.е. в определении такого размещения источников тепла, которое удовлетворяет всем ограничениям и является наилучшим в смысле заданных критериев.

В общем случае, как видно из приведенных свойств, данная задача может быть отнесена к классу задач оптимального управления системами с распределенными параметрами, исследованию которых посвящен-: ряд работ Н6-20,36,75,74,<35,9в/.

С другой стороны, рассматриваемые в диссертации задачи можно отнести к задачам оптимизации систем многосвязного управления I551,52 поскольку поиск наилучшего значения функции цели можно осуществить только при одновременном учете всей системы источников тепла в их взаимной связи. Исследованию и оптимизации многосвязных систем определенного вида посвящена работа М.В. Мирова и Б.Д.Литвака / 43 /.

Использование перечисленных выше методов при размещении источников тепла затруднено, так как рассматриваемые в диссертации задачи оптимизации температурных полей имеют существенные особенности, а именно:

- функция действия источников тепла разрывна;

- сложный характер геометрических и теплофизических ограничений.

В ряде работ /74; 15,25-27,30,51,33, SO, 107,109/ рассмотрены вопросы оптимального проектирования МЭА, анализа и расчета температурных режимов приборов и устройств с помощью ЭВМ,

Настоящая работа выполнена в период с 1980 по 1984 г.г. на кафедре технической электроники Харьковского института радиоэлектроники в соответствии с госбюджетной и хоздоговорной тематикой^

Работа состоит из введения, четырех глав и приложений.4

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

Во второй главе разработана тепловая модель МК МСБ и метод ее расчета.

В третьей главе осуществлена математическая постановка оптимизационной задачи размещения тепловыделяющих источников МК МСБ с учетом условий трассировки электрических соединений. Значительное внимание уделено вопросам формализации теплофизических ограничений,

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

Основные положения диссертации и результаты исследований докладывались и обсуждались на:

1, Восьмой научно-технической конференции "Автоматизация конструкторского проектирования РЭА и ЭВА", Пенза, 1981 rv

2, Республиканском семинаре АН УССР по проблеме "Теоретическая электротехника, электроника и моделирование", Харьков, I98I-I984 г.г.

3, X Всесоюзном совещании-семинаре "Автоматизация проектирования структурных элементов, математического обеспечения ЭВМ и вычислительных систем", Москва, 1982 tf,

4, Городском семинаре "Математические методы геометрического проектирования", Харьков, 1982-1984 г,г.

5, Всесоюзной научно-технической конференции "Автоматизация проектирования ЭВМ и систем" Ереван, 1983 г,

6, На семинаре "Автоматизация проектирования электронной аппаратуры" Северо-Кавказского научного центра высшей школы, Таганрог, 1984 г.

43-й научной конференции Латвийского государственного университета им. П.' Стучки "Математическое и программное обеспечение автоматизации проектирования в радиоэлектронике", Рига, 1984 rv

8.' Всесоюзном совещании - семинаре "Теоретические и прикладные вопросы разработки, внедрения и проектирования радиоэлектронной аппаратуры", Москва, 1984 г. Основные результаты диссертационной работы опубликованы в работах / 5*3, 75", 7в, 77,78, 97 h

Основные положения, выносящиеся на защиту:

Iv Математическая постановка оптимизационной задачи размещения элементов МК МСБ с учетом условий трассировки электрических соединений.

2. Методы и алгоритмы решения поставленной задачи.

3. Тепловая модель МК МСБ и метод ее расчета.

4!.г Алгоритм построения минимальных деревьев электрических цепей.

5. Алгоритм распределения соединений по слоям, основанный на оптимизации непрерывной функции многих переменных.

6v Апробация методов и алгоритмов в реальных условиях внедрения.*

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

I* Сформулирована математическая постановка оптимизационной задачи размещения тепловыделяющих источников МК МСБ (дискретных стационарных источников тепла) с учетом условий трассировки электрических соединений, исследованы особенности реализации геометрических и теплофизических ограничений.

2. Разработана тепловая модель и метод расчета температурного поля. Проведено экспериментальное сравнение точности расчета температурного поля о результатами эксперимента.

3; Разработан и исследован алгоритм размещения источников тепла.

4v Исследован метод расчета электрических параметров МК МСБ, теоретически показано, что при определенных сочетаниях параметров нелинейных уравнений скорость сходимости данного метода выше, чем у метода Ньютона.

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

6у На основании доказанных утверждений разработан алгоритм минимизации количества слоев МК МСБ. Проведено экспериментальное сравнение эффективности предложенного алгоритма с рядом известных алгоритмов^

7. На основе исследований разработан и внедрен ряд программ расчета температурного поля, размещения тепловыделяющих источниковтрассировки межфрагментных соединений. Экономический эффект от их использования составил 48,43 тыс. рублей t

В ГОД .1

1. A.M. Бершадский, В.Б. Лебедев, Л.Р. Фионова, А.А. Шаврол.-Вопросы радиоэлектроники, сер. ЗВТ, 1978, вып. 13, с; 116121.•» , *

2. Алексеенко А.Г. и др; Алгоритм трассировки для машинного проектирования межсоединений микроэлектронной аппаратуры.-В кн.1: Микроэлектроника. М.: Сов. радио, 1971, вып; 4;су 282-293.

3. Базилевич Р.П. Обобщенный подход к формализации задачи машинной трассировки межсоединений на плоскости.- Изв. вузрв СССР. Радиоэлектроника, 1974, т. 17, №6, cv 98-103.

4. Ю.1 Баталов Б.В.у Егоров Ю.Б., Русаков С.Г.1 Основы математического моделирования больших интегральных схем на ЭШ.-М. : Радио и связь,' 1982168с.

5. Батщев Д.И., Морозов В.Ф., Асланов А.А. Метод автоматизированного синтеза топологии ГИС.- Вопросы радиоэлектроники, сер. ЭВТ, 1981, № 6, с. 9-19.i

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

7. Бершадский A.M.', Лебедев В .Б., Фионова Л. Р.- Построение функ11 •ции качества в задаче размещения тепловыделяющих источников.-Алгоритмические методы и программирование в радиоэлектронике, 1979, вып. 2, с. 102-104.

8. Бутковский А.Г.у Даринский Ю.В., Пустыльников Л.М; Подвижное управление системами с распределенными параметрами.-Автоматика и телемеханика, 1976, № 2, с. I5-25.1

9. Гинзбург Б.Д. 0 числе внутренней устойчивости графа,-Сообщ; АН Гр. ССР. 1977, 85, » 2, с; 289-291.*

10. Гладких Б.А., Ивашинцов И.А., Матушевский В.В. Приближенный алгоритм раскраски графов большой размерности.- Тр.! Сибирского физико-техн.' ин-та, 1971, вып. 62, с. 65-74.

11. Гурвич Е.И., Крапчин А,И, Быстродействующий алгоритм трассировки двуслойных печатных плат,- В кн.: Вычислительная техника.1 Т.4. Каунас, Каунасский политехи, ин-т, 1973,с. 132-136;

12. Дульнев Г.Н., Полыциков Б.В. Проблемы теплообмена в радиоэлектронных устройствах.- Радиотехника, 1977, 32, № II,о J 86-96.

13. Дульнев Г.Н., Потягайло А.Ю, Классификация тепловых моделей систем многих тел с источниками энергии,- Тр.Ленингр. ин-та точной механики и оптики, 1976, вып. 86, о.' 4-13.

14. Закревокий А.Д. Алгоритм синтеза дискретных автоматов1.1- М.1: Наука, 1971, 512 с.'

15. Закс Д.И.; Мадера А.Г. Метод расчета нестационарных температурных полей полупроводниковых микросхем.- Изв.- вузов СССР. Радиотехника, 1979, т.; 22, /в 6, с. 77-81.^1.• <

16. Закс Д.И;1, Наумов Н.М.! Анализ температурного поля полупроводниковой микросхемы.- Изв.' вузов СССР.1 Радиоэлектроника, 1975, т. 18, £ I, с. 60-63.1. Л " . ' >

17. Лазарева Т.О. Алгоритм трассировки печатных соединений нагоснове представления о каналах,- Автоматика и вычислительная техника, 1969, № 5, cv I2-I5.1

18. Лошаков В.Н. Алгоритм размещения линеек контактных площадок;*.

19. Электронная техника. Сер. 11;! Комплексная микроминиатюризация радиоэлектронных уотройств и систем, 1975, вып; 4, с.' 67-74.

20. Морозовокий В.Т.1 Многосвязные системы автоматического регулирования.- М.: Энергия, 1970.- 288 с.

21. Морозовский В.Т. О полных и частично автономных многомерных линейных САР.- Автоматика и телемеханика, 1962, № 9,с. II87-I20I.;

22. Огороднейчук И.Ф., Чурилов А.И.', Кладов Г.К. Модифицированный метод хорд и его применение при анализе нелинейных электронных схем.- Электроника и моделирование, 1974, вып. 2, с. 10-15.

23. Огороднейчук И.Ф.1, Чурилов А.И., Пономарева Л.А.1 Решение уравнений метода узловых потенциалов при анализе электронных схем.- АСУ и приборы автоматики, 1976, вып.! 40, с1;1 103-107.

24. Панасенко А.А.1, Максименко И.А.' Способ построения годографа функции плотного размещения выпуклых взаимно неориентированных многоугольных объектов.- В кн.1: Автоматизация раскроя тканей и обувных материалов.1 Киев, 1975, с. 45-46.'

25. Петренко АУИУ, Тетельбаум А.Я., Забалуев Н.Н. Основные процедуры топологической трассировки с оптимизацией.- В кн.1: Анализ и машинное проектирование электронных цепей.1 Киев: Наукова думка, 1980, с. 12-30.'

26. Петренко А.И., Тетельбаум A.Hv Формальное конструирование электронно-вычислительной аппаратуры,*- М,: Сов,радио, 1979,256 с.

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

28. Помазанов B.Mv К задаче о размещении ячеек в панели,- В кн.;: Применение вычислительных машин для проектирования цифровых устройств/ Под ред. Н.Н, Матюхина,- М.: Сов.! радио, 1968,200 с.

29. Проектирование монтажных плат на ЭВМ/ К,К, Морозов, А,И,! Мелихов,, В.Г. Одиноков и др.- М,: Сов. радио, 1979,- 224 cv

30. Семенец В.В. Алгоритм размещения и трассировки.- В кн.: Автоматизация проектирования ЭВМ и систем. Материалы Всесоюзнойконференции. Ереван, 1983, c!v 160-161.'' ,« .■* ,, ,»

31. Семенец В.В., Борзенков Б.И. Алгоритм трассировки печатных соединений.- В кн.: Автоматизация проектирования в электронике, Таганрог, 1984, су 65-70.''

32. Семенец В.В.!, Куник Е.Г., Довнарь А.И. Об одном способе определения максимального внутренне устойчивого множества.-1983,- 10 с.1- Рукопись деп. в УкрНИИНТИ, £ 460 Ук- Д83.■ * .1 * ,, ■ ** г

33. Смирнов В.И; Курс высшей математики, т. 2. М.': Наука, 1965.656 с.

34. Стоян Ю.Г., Хажмурадов М.А. Алгоритмы последовательно-одиночного размещения тепловых источников с учетом заданных расстояний между ними и границей области J2 . ИК АН УССР, Киев, 1976, 19 с.

35. Стоян Ю.Г;, Хажмурадов М.А.1, Коновко А.В. О рациональном размещении тепловых источников произвольной геометрической формы в случае задачи Дирихле.1- Харьков, 1976.^-57 с.

36. В надзагл.: АН УССР. Ин-т пробл. машиностроения.1

37. Стоян Ю.Г;, Хажмурадов M.A'J Об одном методе рационального размещения однотипных тепловых объектов, имеющих форму квадрата, в прямоугольной области.- В кн.1: Методы поисковой оптимизации и размещения геометрических объектов. Киев,

38. ИК АН УССР, 1976, с. 15-24.

39. Чубаров Е.П. Контроль и управление с подвижным воздействием.-M.s Энергия, 1976.- 170 с.

40. Чубаров Е.П. Параметрические поля и особенности их регулирования.- В кн.: Современные проблемы кибернетики, Наука, 1970, с.' 418-426.

41. Чубаров Е.П. Регулирование параметрических полей с помощью подвижного локального воздействия.- В кн.: Развертывающие системы. М.: Энергия, 1976, с. 57-77.

42. Чурилов А.И., Семенец В,В; К оценке скорости сходимости модифицированного метода сечений.- АСУ и приборы автоматики, 1982, вып;< 63, с. 10-15.

43. Широ Г.Э. Метод проектирования печатного монтажа, основан, „ ****ный на эвристических принципах.- В кн.: Методы разработки схем и конструкций цифровых систем. 4.2, Л., ЛФНТП, 1967, с. 74-82.

44. Широ Г.Э. Параллельная трассировка двуслойных печатных плат1.* • 'Iметодом сечения каналов.- В кн.: Вычислительная техника. Т.9. Каунас, Каунасский политехи, ин-т, 1977, cv I07-II0.

45. Широ Г.Э. Применение метода топологической трассировки для проектирования соединений в микросхемах,- Электронная промышленность, 1979, Н, с.' 69-77.• I * • 1

46. Широ Г.Э;, Ревишвили В.Г. Трассировка соединений с использованием стандартных топологических моделей.- Электронная техника. Сер. II.1 Комплексная микроминиатюризация радиоэлектронных устройств и систем, 1976, вып.1! 3(7), с".1 84-93.'I

47. Шнейдер А. А. Классификация и экспериментальное сравнение1 4 I •приближенных алгоритмов раскраски вершин графа.- В кн.: Вычислительная техника в машиностроении.1 Минск: Ин-т техн. кибернетики АН БССР, 1982, Л 3, с'.1 94-107.!* , • » .Л,

48. Шнейдер А.А.Экспериментальное исследование алгоритмов раскраски вершин графа.- В кн.: Автоматизация логического проектирования дискретных устройств. Минск: Ин-т техн. кибернетики АН БССР, 1980, вып. 2, с. 86-94.1

49. Элькин М.И. Расчет температурного поля интегральной микросхемы. Вестник Харьковского университета, 1975, J& 15,с. 41-46.

50. CLchitfes 6. Hoik си Ctna^H c>fми gape ФбкиНиы. - IEEE Змтмх&когиоп dzchoh dbwicib, 4974, no //, р- S20. >

51. Bte&zz. Л. Пекг mMwod* ~t<? ttcticcej pjf-cl qtapJi. Co?7if)iu n i cfdcwi <?f т^гс А СИ, J979,гroE.&t по. 4, p. -2S6, 106. Ba^Ld R, Compute^Ued Et/?c/Eysts of

52. Г16. Laighton E.T. CL g±aph coEo&'/rg с/ЕдоёМгп fog

53. Ой& Л с//JЛ7 /7О £/?/у /VS2.0. - £/ t^/afi Са£/£с?£л/о, Se&h^ey, /э.

54. Ra£ston (2. £2 c&uzse г!л ллл7<?£/<?а/ana £ys/'s, Jleitf

55. Ridc/e^s C,££t 0 f?£/?Л7 со/77/эл £/ha S/h^e cz. сол£/'лгусэ/7 si//7c£/'or?, IEEE a J?с/ос/ Systems, С/IS -26, л о //, /о, ш, RMetis С. Убёгг

56. De2Jl2J£^l faom /£хр£лал£/'л£ С/~/£ 2Ж — IEEE $£c?/7sc/c t/'ons ал £h.'±c/sZ£ с/лс/ Sys/r^^ CJS-26, по S, /э, 6бд-б*?а, 122, RlLfines- R-ete&sen ~Г. л/А Р <9. nor?ar?c/£ys/s p^o^kc/rn g ajzeu/tzechn/cо £ £Ул/'гге£з/£у D -елл7с/£А/1. Cop ел ел, .