Разработка численного метода решения систем нелинейных обыкновенных дифференциальных уравнений, описывающих временное поведение цифровых УБИС с учетом латентности тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Макаров, Сергей Викторович

• Макаров, Сергей Викторович
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Макаров, Сергей Викторович

ВВЕДЕНИЕ.

1. МЕТОДЫ СХЕМОТЕХНИЧЕСКОГО МОДЕЛИРОВАНИЯ УБИС.

1.1. Введение.

1.2. Основные этапы схемотехнического моделирования

1.2.1. Составление математической модели.

1.2.2.Численные методы решения математической модели.

1.3. Современные методы сокращения временных затрат при схемотехническом моделировании УБИС.

1. 3 .1. Метод временного анализа ADAPTS.

1.3.2.Учет латентности при моделировании цифровых УБИС

1.4. Использование декомпозиции при схемотехническом моделировании.

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

2 . РАЗРАБОТКА СПЕЦИАЛИЗИРОВАННОГО ЧИСЛЕННОГО МЕТОДА РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ.

2.1. Формирование независимых подсистем ЛАУ при моделировании цифровых УБИС.

2.1.1. Терминология.

2 .1. 2 . Эффективность разбиения СЛАУ.

2.1.3.Формирование независимых подсистем ЛАУ.

2.2. Особенности формирования независимых подсистем ЛАУ в реальных электрических схемах.

2.3. Критерии применимости разрабатываемого метода

2.4. Решение независимых подсистем ЛАУ.

2.4.1. Методы решения независимых подсистем ЛАУ.

2.4.2. Методы решения плохо обусловленных систем ЛАУ.

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

2.5.1.Обобщенный подход к представлению структурного описания электрической схемы.

2.5.2.Трансляция входных языков на этапе схемотехнического проектирования.

2.6. Выводы.

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

ПОДХОДОВ.

3.1. Алгоритмы формирования независимых подсистем ЛАУ при моделировании цифровых УБИС.

3.1.1.Модификация алгоритмов учета латентности для реализации разбиения на независимые подсистемы ЛАУ. 106 3 .1. 2 . Алгоритмы формирования независимых подсистем ЛАУ109 3.1.3.Алгоритмы динамического формирования независимых подсистем ЛАУ.

3.2. Результаты моделирования электрических схем с применением разбиения на независимые подсистемы ЛАУ

3.3. Алгоритмы для работы с обобщенным структурным описанием электрической схемы.

3.4. Выводы.

4. РАЗРАБОТКА ПРОГРАММНЫХ МОДУЛЕЙ.

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

4.2. Программные модули, реализующие метод разбиения на независимые подсистемы ЛАУ.

4.3. Реализация обобщенного структурного описания входных проектов в САПР КИПАРИС.

4.4. Тестирование разработанных программных модулей

4.5. Выводы.

Введение диссертации (часть автореферата) на тему «Разработка численного метода решения систем нелинейных обыкновенных дифференциальных уравнений, описывающих временное поведение цифровых УБИС с учетом латентности»

Диссертационная работа посвящена разработке математического, алгоритмического и программного обеспечения, предназначенного для решения систем нелинейных обыкновенных дифференциальных уравнений (ОДУ), описывающих поведение цифровых интегральных схем ультра большой степени интеграции (УБИС) с учетом временной разреженности. Предлагаемый в данной работе маршрут решения ОДУ предполагает многократное решение систем линейных алгебраических уравнений (СЛАУ). Разработанный метод позволяет учесть распадающуюся структуру сформированной СЛАУ и тем самым значительно понизить размерность задачи.

Актуальность проблемы

Широкое применение изделий микроэлектроники явилось причиной активного развития научно-технической базы в микроэлектронной промышленности. Уже почти на протяжении трех десятилетий степень интеграции интегральных схем (ИС) ежегодно удваивается. Если в начале 7 0- годов ставилась задача автоматизации проектирования и производства схем, содержащих десятки элементов, то сегодня необходимо создавать цифровые схемы, содержащие десятки миллионов элементов (УБИС). Такое бурное развитие микроэлектроники стало возможным благодаря технологическому прогрессу, который требует соответствующего уровня развития систем автоматизированного проектирования (САПР).

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

Численные методы решения систем ОДУ относительно невысокого порядка к настоящему времени уже достаточно хорошо изучены. Наиболее перспективным направлением дальнейшего снижения вычислительных затрат и увеличения размерности решаемой системы ОДУ является учет специфических особенностей прикладных задач. Таким образом, разработка нового метода решения систем нелинейных обыкновенных дифференциальных уравнений, учитывающего временную разреженность УБИС и позволяющего существенно снизить время моделирования цифровых УБИС, является актуальной задачей.

Цель работы

Целью диссертационной работы является разработка методов решения систем нелинейных ОДУ, уменьшающих время моделирования цифровых УБИС на этапе СхТ проектирования (СхТП) и позволяющих эффективно решать жесткие системы

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

Разрабатываемый метод, при использовании его в программах СхТП, должен:

• получать решение системы нелинейных ОДУ, описывающей временное поведение УБИС, с заданной точностью;

• обеспечивать значительное снижение временных затрат при моделировании цифровых УБИС, характеризующихся временной разреженностью;

• рассчитывать схемы общего вида за время, необходимое при использовании традиционных методов интегрирования;

• не требовать чрезмерных дополнительных затрат оперативной памяти при программной реализации.

Научная новизна работы

1. Разработан численный метод решения систем нелинейных ОДУ, учитывающий декомпозицию СЛАУ на распадающиеся подсистемы при возникновении латентных процессов в цифровых ИС на этапе схемотехнического моделирования.

2. Поставлена и решена задача разбиения множества активных уравнений на несвязные между собой подмножества.

3. Разработан обобщенный способ представления структурного описания ИС на этапе СхТ проектирования. Предложен унифицированный подход к созданию программ трансляции структурного описания входных проектов.

Практическая значимость работы

Разработано алгоритмическое и программное обеспечение для использования в программах СхТ проектирования, реализующее предложенные методы и подходы. Разработанное программное обеспечение состоит из следующих основных частей:

1. библиотека функций для учета распадающейся структуры СЛАУ, позволяющая использовать как точные методы решения независимых подсистем ЛАУ (с учетом или без учета разреженности), так и итерационные методы;

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

Внедрение результатов работы

Разработанное программное обеспечение, является составной частью подсистемы СхТ проектирования в КИПАРИС (комплекс инженерных программ для автоматизированного расчета интегральных схем). Зарегистрированная версия указанной подсистемы - Analog Simulator 50000. В настоящее время САПР КИПАРИС внедрена в Государственном НИИ Физических Проблем (Гос. НИИФП), Государственном центре компьютерных технологий «Силикон-Телеком Софт», а также используется в учебном процессе в Московском государственном институте электронной техники (МИЭТ).

Положения, выносимые на защиту 1. Численный метод решения систем нелинейных ОДУ, описывающих поведение ИС во времени, основанный на формировании независимых подсистем ЛАУ, который позволяет существенно снизить временные затраты при моделировании цифровых УБИС, характеризующихся временной разреженностью.

2. Критерии подбора методов решения СЛАУ для расчета независимых подсистем ЛАУ.

3. Обобщенное представление структуры ИС, позволяющее унифицировать хранение и управление проектами в программах схемотехнического моделирования и снижающее временные затраты при работе с ним.

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

Апробация работы

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

• Межвузовская научно-техническая конференция. "Микроэлектроника и информатика - 96", МИЭТ, 1996г.

• Межвузовская научно-техническая конференция, "Микроэлектроника и информатика - 97", МИЭТ, 1997г.

• Третья международная научно-техническая конференция "Микроэлектроника и информатика", Москва, Зеленоград, 1997г.

• Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. "Микроэлектроника и информатика - 98", МИЭТ, 1998г.

• Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. "Микроэлектроника и информатика - 99", МИЭТ, 1999г.

Публикации

По вопросам САПР БИС автором опубликовано 14 работ в том числе 9 по теме диссертационной работы, список которых приведен в конце автореферата. Результаты исследований также отражены в отчете о законченной НИР.

Структура и объем диссертации

Диссертационная работа состоит из введения, четырех глав, заключения, списка используемых сокращений, списка литературы и приложений. Работа изложена на 162 листах машинописного текста, включает 42 рисунка и 5 таблиц. Список используемой литературы содержит 57 наименований.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Макаров, Сергей Викторович

-1474.5. Выводы

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

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

2.в качестве языка программирования выбран язык С++, поддерживающий объектно-ориентированный подход;

3. разработана библиотека функций, реализующая разработанный метод решения систем нелинейных ОДУ;

4. разработана иерархия классов, реализующая хранение и работу с обобщенным структурным описанием схемы;

5. проведено тестирование разработанного программного обеспечения.

ЗАКЛЮЧЕНИЕ

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

1. разработан численный метод решения систем нелинейных обыкновенных дифференциальных уравнений, описывающих временное поведение цифровых УБИС с учетом латентности;

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

3. сформулированы критерии эффективного выбора метода расчета независимых подсистем ЛАУ;

4. сформулированы причины возникновения ошибок, при решении независимых подсистем ЛАУ и способы их оценки;

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

6. разработаны алгоритмы формирования кластерной структуры;

7. предложено обобщенное описание структуры электрической схемы в программах СхТ проектирования;

8. предложен унифицированный подход к проектированию трансляторов входных языков описания СхТ проектов, использующий в качестве внутренних структур данных обобщенное описание структуры;

-1499. проведено сравнение разработанных алгоритмов с алгоритмами, реализующими традиционные методы моделирования; 10. разработаны программные модули, реализующие следующие методы и подходы: формирование независимых подсистем ЛАУ и их решение, создание и управление обобщенным описанием структуры, унифицированный подход к проектированию трансляторов.

Список литературы диссертационного исследования кандидат технических наук Макаров, Сергей Викторович, 2000 год

1. Казеннов Г.Г.,Соколов А.Г. Принципы и методология построения САПР БИС. Москва: Высшая школа, 1990.

2. Казеннов Г.Г., Соколов А.Г. Основы построения САПР и АСТПП. Москва: Высшая школа, 1989.

3. Ермак В.В., Перминов В.Н., Соколов А.Г. Рабочие станции в проектировании БИС. Москва: Высшая школа, 1990.

4. Петренко А.И., Власов А.И., Тимченко А.П. Табличные методы моделирования электронных схем на ЭЦВМ. Киев: Вища школа, 1977.

5. Чуа Л.О., Лин П.М. Машинный анализ электронных схем (алгоритмы и вычислительные методы). Москва: Энергия, 1980.

6. Chua L.O., Lin P.M. Computer-aided analysis of electronic circuits; algorithms and computational techniques. Prentice Hall, 1975.

7. Влах И., Сингхал К. Машинные методы анализа и проектирования электронных схем. Москва: Радио и связь, 1988.

8. Глориозов Е.Л., Ссорин В.Г., Сыпчук П.П. Введение в автоматизацию схемотехнического проектирования. Москва: Наука, 1976.

9. Писсанецки С. Технология разреженных матриц. Москва: Мир, 1988.

10. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. Москва: Мир, 1980.

11. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. Москва: Мир, 1998.

12. Голуб Дж., Ван Лоун Ч. Матричные вычисления. Москва: Мир, 1999.

13. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. Москва: Наука, 1984г.

14. Мудров А.Е. Численные методы для ПЭВМ. Томск: МП Раско, 1992.

15. Stein A.D., Nguyen T.V., George B.J., Rohrer R.A. ADAPTS: A Digital Transient Simulation Strategy for Integrated Circuits// 28th ACM/IEEE Design Automation Conference, Paper 2.2, 1991. pages 26-31.

16. Chawla B.R., Gummel H.K., Kozak P. MOTIS An MOS timing simulator// IEEE Trans, on Circuits and Systems. CAS-22(12):901-910, December 1975.

17. Kim Y.H., Kleckner J.E., Saleh R.A., Newton A.R. Electrical-logic simulation// IEEE Int. Conf. on CAD, 1984. pages 7-10.

18. Ruan G., Vlach J. Current limited switch-level timing simulator for MOS logic networks// Proc. IEEE International Conference on Computer Design, 1985. pages 597-601.

19. Vidigal L.M., Nassif S.R., Director S.W. CINNAMON: coupled integration and nodal analysis of MOS networks// Proc. 1986 Design Automation Conference, June 1986. pages 179-185.

20. Visweswariah C., Rohrer R.A. SPECS2: An integrated circuit timing simulator// In IEEE Int. Conf. on CAD, November 1987. pages 94-97.

21. Nagel L.W. SPICE2: A Computer Program to Simulate Semiconductor Circuits// Electronics Research Laboratory Rep. No ERLM520, University of California, Berkley, May 1975.

22. Vladimirescu A., Liu S. The simulation of MOS integrated circuits using SPICE2 // Berkeley Research Laboratory University California, 1980, Memo M80/7.

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

24. Кокин С.А., Макаров C.B., Перминов В.Н. Использование табличных представлений моделей активных элементов при схемотехническом моделировании БИС// Известия ВУЗов, Электроника, №5. Москва: МИЭТ, 1997. стр. 71-78.

25. Ильин В.Н., Фролкин В.Т., Будко А.И., Камнева Н.Ю., Тихомирова Е.М. Автоматизация схемотехнического проектирования. Учеб. Пособие для вузов. Под ред. В.Н. Ильина. Москва: Радио и связь, 1987.

26. Перминов В.Н. Особенности схемотехнического моделирования цифровых СБИС// Известия высших учебных заведений, Электроника, № 1-2. Москва, 1996г.

27. Перминов B.H., Соколов А.Г., Казеннов Г.Г., Кокин С.А. Моделирование ультра больших интегральных схем// Труды Всероссийской научно-технической конференции "Электроника и информатика-95", Тезисы докладов. Москва, 1995. с.79-81.

28. Казеннов Г.Г., Перминов В.Н., Соколов А.Г. Численные методы моделирования ультра больших интегральных схем//

29. Электронная промышленность, № 4-5. Москва, 1995. с.121-125.

30. Макаров C.B., Куликов O.A., Гаврилов М.С., Кокин С.А., Перминов В.Н. Моделирование динамических систем большой размерности// Межвузовская научно-техническая конференция. "Микроэлектроника и информатика 96", Тезисы докладов. Москва: МИЭТ, 1996. стр.40.

31. Dorr F.W. An example of ill-conditioning in the numerical solution of singular perturbation problems// Math. Сотр., 25 (1971), pp. 271-283.

32. Бахвалов H.С., Жидков H.П., Кобельков Г.M. Численные методы. Москва: Наука, 1987.

33. Казеннов Г.Г., Ермак В.В., Кремлев В.Я., Макаров C.B. и др. Разработка основ теории и функциональных подсистем САПР УЛЬТРА БИС// Отчет о НИР шифр "610-ГБ-53-Б-ПКИМС", Г.Р. №01970000156, инв. №02990000739. Москва: МИЭТ, 1998. 96стр.

34. Марчук Г.И., Шайдуров В.В. Повышение точности решений разностных схем. Москва: Наука, 197 9. с.320.

35. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Москва: Мир, 1985. с.509.

36. Комлев Н.Г. Словарь новых иностранных слов. Москва: МГУ, 1995г.

37. Куликов O.A., Макаров C.B., Перминов В.Н. Процедура сингулярного разложения матриц специального вида в системах схемотехнического моделирования СБИС// Известия ВУЗов, Электроника, №4. Москва: МИЭТ, 1999. стр. 45-51.

38. Валях Е. Последовательно-параллельные вычисления. Москва: Мир, 1985г.

39. Стемпковский A.J1., Шепелев В.А., Власов A.B. Системная среда САПР СБИС. Москва: Наука, 19 94г.

40. Макаров C.B., Кокин С.А., Перминов В.Н., Соколов А.Г., Внутреннее представление развернутого описания схемы в САПР КИПАРИС// Труды Межвузовской научно-технической конференции "Микроэлектроника и информатика". Москва, 1995. с.44-46.

41. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. Москва: Мир, 1975г.

42. Хантер Р. Проектирование и конструирование компиляторов. Москва: Финансы и статистика, 1984г.

43. Вирт Н. Алгоритмы и структуры данных. Москва: Мир, 1989г.

44. Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы. Том 1. Москва: Мир, 197 6г.

45. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. Том 3. Москва: Мир, 197 8г.

46. Страуструп Б. Язык программирования С++. СПб: Невский диалект. Москва: Издательство БИНОМ, 1999г.

47. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. Москва: Мир, 1980г.

48. Макаров C.B., Куликов O.A., Гаврилов М.С., Кокин С.А., Перминов В.Н. Агрегативный подход к проектированию постпроцессоров// Межвузовская научно-техническая конференция "Микроэлектроника и информатика 96", Тезисы докладов. Москва: МИЭТ, 1996г. стр. 41.

49. Кокин С.А., Макаров C.B., Перминов В.Н. Комплект программ схемотехнического моделирования КИПАРИС// Третья международная научно-техническая конференция "Микроэлектроника и информатика", Тезисы докладов. Москва, Зеленоград: МФИ-97. стр. 33.

50. Проректор по учебной работеI1,-М.Н., проф. /Поспелов А.С./ 1999г.

51. АКТ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ В УЧЕБНЫЙ ПРОЦЕСС

52. Зав. кафедрой ПКИМС, д.т.н.1. УТВЕРЖДАЮ»1. Гос.НИИФП,1. УТВЕРЖДАЮ»

53. Проректор пп няумнпй работе1. Бархоткин В.А./ 1999г.1. АКТ О ВНЕДРЕНИИ

54. Комплекс инженерных программ анализа электронных схем используется в составе САПР предприятия для проектирования интегральных схем.

55. От Гос.НИИФП: Гл. инжене£Ло£1-НИИФП,1. Зент /Тишин Ю.И./наялаб.^!-^, к.ф.-м.н.1. Кокин СЛ./

56. От МГИЭТ: Зав. кафедрой ПКИМС, д.т.н., проф.1. Казенное'Г. Г./доц. кафедры ПКИМС /Перминов В.Н./т кафедры ПКИМС /Макаров C.B. /1. УТВЕРЖДАЮ»эственного яерных он -Телеком проф.1. УТВЕРЖДАЮ»

57. Про^§1сюр-пи><ь1учней работе-—--- /Kanvi1. Бархоткин В.А./1999г.feôifL/ОКОЛОв А. Г./ 1999г.1. J ^7/ '1. АКТ О ВНЕДРЕНИИ

58. Комплекс инженерных программ анализа электронных схем используется в составе САПР предприятия для проектирования интегральных схем.

59. От Государственного От МГИЭТ: центра компьютерных " ' ~ ~.технологий «Силикон -, Телеком Софт»: Зам. директора, к.т.н., Л/У/ .-^^/АрхипкинВ.Я./— ■■. у11"" •1. РОССИЙСКАЯ ФЕДЕРАЦИЯ

60. РОССИЙСКОЕ АГЕНТСТВО ПО ПАТЕНТАМ И ТОВАРНЫМ ЗНАКАМ (РОСПАТЕНТ)

61. Об официальной регистрации программы для ЭВМ990247

62. Analog Simulator 50000 ("AnSim 50000")1. Правообладатель(ли):

63. Государственное ylpeojcdenue Государственник уентр компьютерных технологий "(ЖМКОН ЯЩИКОМ СОФЯТГ (RU)1. Автор(ы):

64. Соколов с Александр ГеоргиеШ, ЯТермннов Владимир Николаева, Кокни Серий с/1лександрови1, Макаров Сергей Зднкморовн1, Горюнов 90pud сДлекоандровн1, ЩуЗш c/bekced Шжровп1, ^Терминов Юенис Владимиром (RU)

65. Страна: Российская Федерация ;по заявке № 990107, дата поступления: 02 марта 1999 г.

66. Зарегистрировано в Реестре программ для ЭВМг. Москва, 30 апреля 1999 г.