автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Оптимизация фрагментов цифровых БИС на комплементарных МДП структурах

Основше сокращения и условные обозначения .б

Введение.в

ГЛАВА I. Свойства задач оптимизации фрагментов КЩЩ БИС, построенных на базе алгебраической модели

1.1. Задачи оптимизации КЩЩ БИС

1.2. Анализ функций, описывающих площадь схемы на кристалле .1о

1.3. Анализ функций, описывающих время задержи схемы

1.3.1. Формы функций времени задержки схемы.

1.3.2. Анализ формул времен задержек сложных

КЩЩ схем.2.

1.4. Учет параллельных проводящих путей МДС1 транзисторов .Зи

1.4.1. Выявление и отбрасывание некритических вариантов переключения.Зи

1.4.2. Учет разновременности прихода сигналов на . вход каскада.

1.4.3. Введение упрощающих связей.

1.4.4. Переформулировка задачи оптимизации.

1.5. Замена функции максимума на функцию среднего.

1.6. Преобразование задачи оптимизации площади схемы на кристалле

1.7. Формы задач геометрического программирования для оптимизации КЩЩ БИС

1.8. Исследование линий уровня функций времени задержки ЩЩ1 схемы.

Выводы по главе I .$

ГЛАВА 2. Разработка метода решения задачи геометрического программирования для оптимизации КЩЩ БИС.

2.1. Прямая и двойственная задачи ГП для оптими- . зации фрагментов КЩЩ БИС

2.1.1. Построение двойственной задачи ГП на основе . теории неравенств.о

2.1.2. Построение двойственной задачи Ш на основе теоремы Куна-Таккера . оУ

2.1.3. Построение двойственной задачи ГП путем вы деления из стандартной формы.

2.2. Свойства двойственной задачи ГП

2.2.1. Недифференцируемость двойственной целевой функции.

2.2.2. Блочное свойство оптимального решения

2.3. Методы Ньютона для двойственной задачи ГП.

2.3.1. Метод I (определения направления поиска).8б

2.3.2. Метод 2 (определения направления поиска).

2.3.3. Важность двойственных множителей

2.3.4. Сравнение 2-х методов 2-ого порядка для двойственной задачи ГП . 8У

2.4. Модификация метода Ньютона.

2.4.1. Использование структуры двойственных ограничений.

2.4.2. Использование блочной структуры двойственного оптимального решения

2.4.3. Учет простых граничных ограничений

2.4.4. Устранение недифференцируемости двойственной целевой функции.

Выводы по главе

ГЛАВА 3. Особенности реализации метода оптимизации фрагментов КЩП ШС; результаты вычислительных экспериментов

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

3.2. Особенности практической реализации метода.

3.3. Эффективная стартовая процедура.

3.4. Оценка временных затрат метода./

Выводы по главе 3.

Совершенствование элементной базы в значительной степени определяет развитие современных ЭВМ. Одним из возможных путей повышения качества цифровых БИС является использование в процессе проектирования методов математической теории оптимизации. Это позволяет в частности улучшать такие важнейшие показатели как быстродействие и площадь кристалла.

Традиционный подход к оптимизации фрагментов БИС заключается в использовании сложных моделей переключения схем и известных методов анализа на основе систем дифференциальных уравнений [ 1-4, 7, II] . Это приводит к значительным трудностям большого объема вычислений, который уже для схем средней степени интеграции становится практически неприемлемым при существующей на современном этапе производительности ЭВМ. С другой стороны, практика проектирования настоятельно требует оптимизации крупных фрагментов БИС, а в идеале - всей БИС в целом.

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

Эффективность разработки и использования в задачах оптимизации простых алгебраических моделей показана еще в [ 9] .

Этот методологический подход исследован в диссертационной работе И.С.Зуева [10] для случая комплементарных ЩЩ (ЩЦП) схем с диэлектрической изоляцией транзисторов с самосовмещенными затворами, где рассматривается минимизация времени переключения фрагмента с учетом его площади на кристалле. Достигнутые в этой работе скорости и объемы оптимизации, хотя ж превышают характеристики традиционного подхода, не являются достаточными для ШС современного уровня интеграции. Настоящая диссертационная работа представляет собой логическое продолжение работы [ю], причем упор делается на совершенствование методов оптимизации. В качестве основного направления исследований выбраны методы геометрического программирования (ГП).

Причина указанного выбора заключается в следующих уникальных свойствах этих методов. Методы ГП позволяют существенно увеличивать степень сложности (размерность, количество ограничений) решаемых с их помощью задач. Это объясняется тем, что, в отличие от других методов, вычислительные затраты большинства методов ГП (или степень трудности решаемой ими задачи) пропорциональны разности между числом одночленных позиномов и числом переменных в задаче [21, 24, 29-31] . Более того, двойственная задача ГП может быть выражена как сепарабельная выпуклая задача с целевой функцией, градиенты и гессианы которой легки для вычисления. С учетом этих и других свойств ГП, изложенных в настоящей диссертации, оказалось возможным разработать алгоритм второго порядка, не требующий от пользователя предоставления специальной информации о производных и вычислительные затраты которого пропорциональны числу переменных решаемой задачи. Затраты же времени ЭВМ в методе оптимизации [10] были пропорциональны квадрату числа переменных в оптимизационной задаче.

Методы ПЗ являются новыми и сравнительно мало изученными разделами теории математического программирования. Поэтому их практическое использование предполагает предварительное решение ряда теоретических и практических задач.

Цель работы

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

Цель достигается решением следующих задач:

- сведением задачи оптимизации фрагментов КЩЩ БИС к задаче

ГП;

- разработкой метода оптимизации фрагментов КЩЩ ШС;

- разработкой алгоритмов и программ оптимизации фрагментов КЩЩ ШС.

В шботе предлагаются:

1. Формулировка выражений алгебраической макромодели КЩЩ ШС - времен задержек и площади схемы на кристалле - в виде позиномиальных функций ширин каналов транзисторов.

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

3. Метод второго порядка для решения задач И1 специального вида, не требующий от пользователя предоставления специальной информации о производных и ориентированный на оптимизацию фрагментов КЩЩ ШС с использованием алгебраической модели.

Пшктическая ценность работы

1. Разработанный на основе постановки задачи в форме геометрического программирования метод позволяет на порядок по сравнению с результатами [10] сократить время оптимизации схемы на ЭВМ. Скорость же счета в сочетании с простотой модели обеспечивают пользователя удобным средством оптимизации выбранных фрагментов ШС с помощью ЭВМ.

2. Разработанные алгоритмы и программы оптимизации представляют пользователю возможность решения широкого класса задач ГП. Разработанная модификация метода Ньютона позволяет решать задачи оптимизации большой размерности до 300-400 переменных, причем существует принципиальная возможность увеличения максимальной размерности решаемой задачи до 1000-1500 переменных, и обеспечивает принципиальную возможность оптимизации крупных фрагментов ЩЦП ШС до 800-1000 транзисторов, существенно расширяя предельную сложность фрагмента, который может быть оптимизирован в целом.

3. Эффективность разработанного метода оптимизации продемонстрирована вычислительным экспериментом большого объема; среди оптимизируемых схем, в частности, имеется схема одноразрядного двоичного сумматора, для которого в процессе оптимизации получено увеличение быстродействия на 2С$.

Автор выражает благодарность научному руководителю диссертационной работы к.т.н., доценту Л.А.Шумилову, а также к.т.н. И.С. Зуеву за постоянное внимание и практическую помощь, оказанную в ходе исследований, проводимых по теме диссертации.

Основные результаты диссертации изложены в четырех печатных работах.

Работа в целом и отдельные ее результаты докладывались на

- Всесоюзном семинаре "Автоматизация проектирования в радиоэлектронике и вычислительной технике". Москва, 1984, апрель;

- Всесоюзной конференции "Микропроцессорные системы". Челябинск, 1984, май.

ЗАКЛЮЧЕНИЕ

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

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

2. Сформулированы задачи оптимизации фрагментов ЩЦП ШС в форме задач геометрического программирования специального вида. Основной задачей является задача минимизации площади схемы на кристалле при ограничении времени задержки.

3. Разработан метод второго порядка для оптимизации фрагментов ЩЦП ШС, не требующий от пользователя предоставления дополнительной информации о производных. Метод позволяет решать задачи оптимизации большой размерности до 300-400 переменных, причем существует принципиальная возможность увеличения максимальной размерности решаемой задачи до 1000-1500 переменных, и предоставляет принципиальную возможность оптимизации крупных фрагментов ЩЦП ШС до 800-1000 транзисторов, существенно расширяя предельную сложность фрагмента, который может быть оптимизирован в целом.

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

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

1. Анисимов Б.В., Белов Б.И., Норенков ИЛ. Машинный расчет элементов ЭВМ, Уч.пособие для вузов. М., "Высшая школа", 1976, 336 с.

2. Ильин В.Н. Основы автоматизации схемотехнического проектирования, 2-е изд., перераб. и доп. М., "Энергия",. 1979.

3. Сигорский В.П., Петренко А.И. Алгоритмы анализа электронных схем. Изд. 2-е, перераб. и доп. М., "Сов.радио", 1976, 608 с.

4. Угрюмов Е.П. Элементы и узлы ЭЦВМ. Уч.пособие для втузов, М., "Высшая школа", 1976, 232 с.

5. Ильюшенко Ю.М. Микромощные цифровые интегральные схемы на основе дополняющих МОП транзисторных структур. Обзоры по электронной технике. Серия "Микроэлектроника". Вып.5 (202). М., 1970, 55 с.

6. Интегральные схемы на МИД-приборах. Пер. с англ. под ред. Кармазинского А.Н. М., "Мир", 1975, 528 с.

7. Иванников А.Д. Расчет размеров транзисторов при проектировании топологии МДП интегральных схем. "Электронная техника". Серия 10. "Микроэлектронные устройства". Вып.2, 1977, с.92-98.

8. Носов 10.Р., Петросянц К.О., Шилин В.А. Математические модели элементов интегральной электроники. М., "Сов.радио", 1976, 304 с.

9. Шумилов Л.А. Анализ и оптимизация полноточных запоминающих устройств. Диссертация на соискание ученой степени к.т.н. ЛЭТИ им.В.И.Ульянова (Ленина), Л., 1972.

10. Зуев И.С. Анализ и оптимизация фрагментов цифровых ШС на комплементарных ЭДЩ1 структурах. Диссертация на соискание ученой степени к.т.н. ЛЭТИ им.В.И.Ульянова (Ленина), Л., 1981.

11. Преснухин Л.Н., Воробьев Н.В. Шишкевич А.А. Расчет элементов цифровых устройств. М., "Высшая школа", 1982, 384 с.

12. Папков B.C., Цыбульников М.Б. Эпитаксиальные кремниевые слои на диэлектрических подложках и приборы на их основе. Под ред. Малинина А.Ю. М., "Энергия", 1979, 89 с.

13. Велик В.М., Гордеев Б.К. Метод расчета БИС на ВДП-тран-зисторах с дополняющими типами проводимости. "Микроэлектроника". Сб.статей под ред.Лукина Ф.В., вып.5, М., "Сов.радио", 1972, с.79-97.

14. Деревянкин В.М., Шумилов JI.A., Зуев И.С.Алгебраическая модель комплементарных МДП схем с диэлектрической изоляцией транзисторов с самосовмещенными затворами. "Электронное моделирование", 1982, & 5, с.39-45.5. &аЛ С. Т. CAan^te^bb-vb of MOS fowbsbte^.

15. EE /W ЪтШ>1 S964, W7 £2) //, >

16. S&a^zort. Эе-г/Г. ^72., л/*-5} op. 8&1- 690.

17. Тоигпа£ of J WVj, л/*5, ff. 435

18. Зангвилл У.И. Нелинейное программирование. Пер. с англ. Бабаева Д.А. Под ред. Голыдтейна Е.Г. М., "Сов.радио", 1973, 312 с,

19. Бекишев Г.А., Кратко М.И. Элементарное введение в геометрическое программирование. М., "Наука", 1980, 144 с.

20. Зенер К. Геометрическое программирование и техническое проектирование. Пер. с англ. М., "Мир", 1973.

21. Даффин Р., Питерсон Э., Зенер К. Геометрическое программирование. Пер. с англ. М., "Мир", 1972, 312 с.

22. De/пД? /?. S. Т£е о/ ал/ а^оc-o/yxtl&L scrfif-uraAe. J^t. ръг^юытлмл. " J&urt+ueJ? cj" Op^ejnis&d&ru ям/ Д^р&саЗ-сопъ^26(2), 1978, pp. m /S3.26. freck R/lScUz. 1G-. a,e&Ztt&f'Ue. pt^tiZ^yuc^^ " Joubtuzf cyf

23. Dp£fbii>a£oh- /^ J'97Sj pp. 2.0Z.27.

24. Ъет£о R. S. Dtui^ fa ся/Пгелъсоп агastd Дрр&слг&оъь", pp>. 24 Ъ-252.28. йг.} /Киччсу V/. MttLJs fitрь^члш/нО^", 7} j pp. 5H-35D.

25. J.C. 2)ec^/np^ ^ sep«.ba&£сии/ s/. 9f лА 5; Y&72; ff- /36.30. frl^ 6L.C. ofeOtnd-Uc p^^bctfiihujuj cyp&'cet&onz L*epfyfUza&on. "JbuA*tA£ dUgineeblsu? /Щ&Ф&пя&ая" 5, Ju^, </97/, pp. 187-494. 3/. Ъем&о Я. S. оъс&ъ af^futfCnsS fit.t&e. gefri^'bcc jo

26. CUiiJxsis. *Р-глоъюч^ъа", 77(/979) f л/* 2, pp. /56 /75.32. ^trW /П., СЪ. pwufiZ a<nd constIn ^wndfuZ рге^гамти^,

27. Jou,twt£ of TUia^is tfpp&afcons",1970, W 32, лА z>, pp.33. Хоккей JX,ъсс ''/ШТ/г&та^еса^ ъаупмсж*^ 7(/974),л/* 2., рр 18/-190.

28. J. G.j Qoc/id Sheets. JZ /п^аТ^ег/.тлаТсссвс/ ^геы^ез^ /и^ЙгЯй^ decaf рх&риемса^of ty&/rU2a£&tt cmcl.97&, pp. 265-2.77.

29. ПЫч-и^к 5. 6L., Sounder /П.Л. /лл^г-S&lAf^JLuy (/978), pp.72.36. 7/.RC.,1. Me of a. по/гД^а^.с^ифеёЕ & н^пТслеа/г. ся/р*.ъ^ггг^н^. * 77ге -/3; 19/О, pp. 178-184. Ъ7. &ох /УХ ^ /игТ&сн/ f77иг Y97S, Sj y/s. Y,

30. Химмельблау Д. Прикладное нелинейное программирование. М., "Мир", 1975, 534 с.

31. Исследование и разработка семейства одноплатных умножителей для мини; ЭВМ с использованием ШС КМОП КНС (отчет) ВТ-74, номер гос.регистрации 78038755, инв.№ Б 762870. ЛЭТИ им.В.И.Ульянова (Ленина), рук.Смолов В.Б., Л., 1978, 210 с.

32. Зуев И.С., Толкодубова Е.И., Шумилов Л.А. Оптимизация комплементарных МДП ШС на изолирующей подложке. В кн.: Микропроцессорные системы. Материалы Всесоюзной конференции. Челябинск, 1984, с.87-88.

33. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М., "Наука", 1975.

34. Численные методы условной оптимизации под ред. Гюш Ф., Мюррей У. Пер. с англ. М., "Мир", 1977.

35. Зуховшцшй С.И., Авдеева Л.И. Линейное и выпуклое программирование. М., "Наука", 1967.

36. Касьянков П.П. Математические методы оптимизации. Уч. пособие. Л., ЛЭТИ, 1978 (Ленинградский ордена Ленина электротехнический институт им.В.И.Ульянова (Ленина).

37. Толкодубова Е.И. Метод второго порядка для оптимизации комплементарных МДП ШС. Ленинград. Электротехн.ин-т им.В.И.Ульянова (Ленина), Л., 1984, 28 с, библ. 7 назв. (Рукопись деп. в ВИНИТИ 24.07.84, № 5344-84 Деп.).

38. Хедли Дж. Нелинейное и динамическое программирование. Пер. с англ. М., "Мир", 1967, 506 с.

39. Грунд Ф. Программирование на языке ФОРТРАН 1У. Пер. с немецкого под ред.Соболева В.Н. М., "Мир", 1976, 184 с.

40. Катцан Г. Язык ФОРТРАН 77. Пер. с англ. М., "Мир", 1982, 208 с.

41. Таненбаум Э. Многоуровневая организация ЭВМ. Пер. с англ. М., "Мир", 1979, 547 с.

42. Соучек Б. Мини-ЭВМ в системах обработки информации. Пер. с англ. М., "Мир", 1976, 520 с.

43. Операционная система ОС-РВ 2.0. Основные сведения о системе. Общее описание. 4.072.209-31.

44. Операционная система ОС-РВ 2.0. Подпрограммы системной библиотеки. Справочные материалы. 4.072.209-92-02.

45. Операционная система ОС-РВ 2.0. Языки программирования. Система программирования на языке Ф0РТРАН-1У. Описание языка. 4.072.209-35-01.

46. Операционная система ОС-РВ 2.0. Система программирования на языке Ф0РТРАН-1У. Транслятор с языка Ф0РТРАН-1У. Руководство программиста. 4.072.209-33-15.

47. Тамм Б.Г., Тыугу Э.Х. Пакеты прикладных программ. Изв. АН СССР. Техническая кибернетика, 1977, № 5, c.III-124.

48. Фатеев А.Е., Ройтман А.И., Фатеева Т.П. Прикладные программы в системах математического обеспечения ЕС ЭВМ. М., "Статистика", 1976, 184 с.59» Кнут Д. Искусство программирования для ЭВМ. Том П. М., "Мир", 1977, 728 с.-/5Y