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

• Булах, Дмитрий Александрович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Булах, Дмитрий Александрович

ВВЕДЕНИЕ.

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

МОДЕЛИРОВАНИЯ ИС.

1.1. Постановка задачи моделирования ИС.

1.2. Анализ принципов работы программ моделирования.

1.3. Алгоритмы сокращения вычислительных затрат при формировании и решении математических моделей ИС.

1.4. Анализ недостатков алгоритмов сокращения вычислительных затрат.

1.5. Выводы.

1.6. Цели и задачи работы.

ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА КОМПИЛЯЦИОННОГО ФОРМИРОВАНИЯ

МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ИС.

2.1. Обоснование необходимости разработки нового алгоритма формирования математических моделей ИС.

2.2. Предлагаемый алгоритм компиляционного формирования математических моделей ИС.

2.3. Предлагаемый алгоритм работы программы моделирования ИС.

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

2.5. Области применения предлагаемого алгоритма.

2.6. Выводы.

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМА ПОЛУЧЕНИЯ ВЫРАЖЕНИЙ ДЛЯ ЗАПИСИ КОРНЯ СЛАУ В АНАЛИТИЧЕСКОМ ВИДЕ.

3.1. Выбор метода решения математической модели.

3.2. Структура предлагаемого алгоритма.

3.3. Предлагаемая модификация программ моделирования.

3.4. Теоретическая оценка эффективности применения алгоритма.

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

3.6. Выводы.

ГЛАВА 4 . ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ И РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ.

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

4.2. Функциональные блоки разработанного симулятора.

4.3. Программная реализация алгоритма компиляционного формирования математической модели ИС и его тестирование

4.4. Программная реализация алгоритма получения аналитических выражений для вычисления корня СЛАУ и его тестирование.

4.5. Сравнение времён расчётов схем в двух режимах работы программы моделирования.

4.6. Перспективы применения алгоритма компиляционного формирования математических моделей.

4.7. Выводы.

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

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

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

Актуальность.

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

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

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

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

Цель работы.

Целью данной диссертационной работы является разработка алгоритмического и программного обеспечения для ускорения процесса моделирования ИС во временной области на этапе схемотехнического проектирования.

Для достижения поставленной цели необходимо решить следующие научно-технические задачи:

1. провести исследование существующих методов и алгоритмов формирования и решения математических моделей ИС;

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

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

4. предложить алгоритм реализации задачи получения аналитических выражений в явном виде для вычисления корня СЛАУ;

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

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

7. реализовать разработанные алгоритмы в виде комплекса программ, выполняющего моделирование схем во временной области;

8 . провести практическую апробацию результатов работы.

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

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

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

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

4.Разработанный алгоритм позволяет получить выражения для вычисления корней СЛАУ в таком виде, который делает возможным распараллеливание процесса решения математической модели, что позволяет значительно повысить скорость вычислений.

5.Разработан алгоритм работы программ моделирования, реализующих предложенные алгоритмы формирования математической модели ИС и её решения.

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

На основе разработанных алгоритмов был создан комплекс программ, позволяющий выполнять моделирование ИС во временной области на этапе схемотехнического проектирования. Использование разработанных методов и алгоритмов позволяет сократить общее время моделирования ИС по сравнению с широко применяемыми системами моделирования фирм «Cadence», «Synopsys» и другими, а также значительно уменьшить размер требуемой оперативной памяти, что приводит к возможности моделировать схемы, содержащие большее число схемотехнических элементов.

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

Диссертационная работа являлась составной частью мероприятий проектно-конструкторской деятельности ОАО «Ангстрем» по созданию библиотеки промышленно выпускаемых базовых матричных кристаллов.

Положения, выносимые на защиту.

1. Алгоритм компиляционного формирования математических моделей ИС на этапе схемотехнического проектирования, основанный на процедуре генерации исходного программного кода на языке программирования высокого уровня С++, описывающего процесс формирования математических моделей схем в виде аналитических выражений.

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

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

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Булах, Дмитрий Александрович

4.7. Выводы.

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

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

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

3. Приведены результаты тестирования разработанных в диссертации методов компиляционного формирования математической модели и получения аналитических выражений для вычисления корня СЛАУ.

4. Показано преимущество по скорости моделирования от использования разработанных методов в составе программ-симуляторов в задаче моделирования ИС на этапе схемотехнического проектирования по используемым аппаратным ресурсам.

ЗАКЛЮЧЕНИЕ

В заключении следует выделить основные результаты диссертации.

1. В работе произведён обзор методов формирования и решения математической модели ИС на этапе схемотехнического проектирования. Выявлены их основные преимущества и недостатки.

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

3. Предложен алгоритм быстрого получения решения математической модели, основанный на записи выражений для вычисления значения корня СЛАУ в явном виде.

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

5. Предложен алгоритм функционирования программ-симуляторов, который позволяет использовать разработанные алгоритмы в процессе моделирования ИС.

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

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

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

Список литературы диссертационного исследования кандидат технических наук Булах, Дмитрий Александрович, 2010 год

1. Казённов Г.Г. Основы проектирования интегральных схем и систем. М.: Бином. Лаборатория знаний. 2 005.

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

3. Норенков И.П., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М.: "Высшая школа", 1983.

4. Корячко В.П., Курейчик В.М., Норенков И. П. Теоретические основы САПР. М.: "Знергоатомиздат", 1987 .

5. Ильин В.Н., Коган В.Л. Разработка и применение программ автоматизации схемотехнического проектирования. М.: Радио и связь, 1984.

6. Булах Д.А. Использование языка Verilog-A в современных схемотехнических САПР.// Известия высших учебных заведений. Электроника., №1. 2007.

7. Булах Д.А. Язык Verilog-A как средство описания моделей полупроводниковых элементов. // Микроэлектроника и информатика-2006, тезисы доклада. Москва. 2006.

8. Alali О. VHDL-AMS Analog Modelling and SPICE Simulation. // PhD dissertation, ENST, Paris, France, 1998 .

9. Chariot J.-F., Milet-Lewis N., Levi H. A VHDL-AMS approach for analyzing electro-thermal effects ina Flash memory.// MIXDES, Poland, 2000.

10. Andrei Vladimirescu. The SPICE Book. John Wiley & Sons, INC. 1994.

11. Kundert K. The Designers guide to SPICE and spectre. Springer, 1995.

12. Davis A.T. Implicit mixed-mode simulation of VLSI circuits. // PhD dissertation, Univercity of Rochester, NewYork, 1991.

13. Inside SPICE. McGraw Hill, 1994.

14. Косарев В.И. 12 лекций по вычислительной математике. М. : Издательство МФТИ, 2000.

15. Вержбицкий В.М. Основы численных методов. М. : Высшая школа, 2002.

16. Лобанов А.И., Петров И.Б. Лекции по вычислительной математике. М.: Бином. Лаборатория знаний. 2006.

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

18. Liniger W. A stopping criterion for the Newton-Raphson method in implicit multistep integration algorithms for nonlinear systems of ordinary differential equations. // Communications of the ACM, vol. 14, issue 9. 1971.

19. Moursund D.G. Optimal staring values of Newton-Raphson calculation. // Communications of the ACM, vol. 10, issue 7, 1967.

20. Beyer W.A. A note on starting the Newton-Raphson method. // Communications of the ACM, vol. 7, issue 7, 1964 .

21. Кузовкин В. А. Теоретическая электротехника: учебник для ВУЗов. М.: Логос. 2006.

22. Беллерт С., Возняцки Г. Анализ и синтез электрических цепей методом структурных чисел. М.: Мир, 1972.

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

24. УБИС с учётом латентности. // Диссертационная работа. Москва, МИЭТ. 2000.

25. Deng Z. , Schutt-Aine J.E. Turbo-SPICE with latency insertion method (LIM). // IEEE Electrical Perfomance of Electronic Packaging, 2005.

26. Erwe R., Tanabe N. Efficent simulation of MOS circuits. // Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions, 1991.

27. H. Shichman, D. A. Hodges. Modeling and simulation of insulated-gate field-effect transistor switching circuits // IEEE Journal of Solid-State Circuits. 1968. Sept. SC-3. 285.

28. T. Ytterdal, Y. Cheng and T. A. Fjeldly. Device Modeling for Analog and RF CMOS Circuit Design. John Wiley & Sons, Inc. 2003.

29. Валях E. Последовательно-параллельные вычисления. M.: Мир, 1985.

30. Плохотников К.Э. Математическое моделирование и вычислительный эксперимент. Методология и практика. Едиториал УРСС, 2003.

31. Устинов С.М., Замницкий В.А. Вычислительная математика. БХВ-Петербург, 2009.

32. Рыжиков Ю.И. Вычислительные методы. БХВ-Петербург. 2007 .

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

34. Тьюарсон Р. Разреженные матрицы. М.: Мир. 1977.

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

36. Saad Y. Iterative methods of sparse linear systems. PWS Publishing company, 1996.

37. Koester D.P., Ranka S., Fox G.C. A parallel Gauss-Seidel algorithm for sparse power system matries. // Conference on High Performance Networking and Computing. Washington DC, 1994.

38. S. C. Eisenstat and H. C. Elman and M. H. Schultz and A. H. Sherman, The (new) Yale sparse matrix package, in Elliptic Problem Solvers II, Academic Press, New York, 1984.

39. Джордж А., Лю Д. Численные методы решения больших разреженных систем уравнений. М.: Мир, 1984.

40. Эстербю О., Златев 3. Прямые методы для разреженных матриц. М.: Мир. 1987.

41. Перминов В.Н., Соколов А.Г., Казённов Г.Г., Кокин С.А. Моделирование ультра больших интегральных схем. // Труды Всероссийской научно-технической конференции «Электроника и информатика-95», тезисы докладов. Москва, 1995.

42. Кокин С.А., Перминов В.Н., Макаров С. В. Система AVOSpice компании UniqueICs. // Электроника:НТВ, №5. 2004 .

43. Головашкин Д.Л. Методы параллельных вычислений. Учебное пособие. Самара: СГАУ. 2002.

44. Корнеев В. Д. Параллельное программирование в MPI. Новосибирск: изд-во СО РАН. 2000.

45. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.: Мир, 1991 г.

46. Courtecuisse Н., Allard J. Parallel Dense Gauss-Seidel Algorithm on Many-Core Processors. // High Performance Computation Conference (HPCC), IEEE CS Press, 2009.

47. Лазарева Д.В., Говорова А.А. Использование преимуществ компиляционного формирования математической модели для ускорения моделирования. // Микроэлектроника и информатика-2010,тезисы доклада. М.: МИЭТ, 2010.

48. Motivations and methology for nanometer library characterization. // Cadence Technical Paper. 2005.

49. Dhaou I.B. Efficient library characterization for high-level power estimation. // IEEE Transactions on VLSI Systems, 2004.

50. Sheehan B.N. Realizable Reduction of RC Networks. // IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 2007.

51. Постельняк A.A. • Разработка компактного формата хранения результатов моделирования на этапе схемотехнического проектирования. // Микроэлектроника и информатика-2010, тезисы доклада. М.: МИЭТ, 2010.

52. Головашкин Д.Л., Горбунов О.Е. Параллельное решение СЛАУ методом Зейделя. Вестник Самарского Государственного университета. Серия физико-математические науки. Самара. СГАУ. 2004.

53. Gulati К., Croix J.F., Khatri S.P., Shastry, R. Fast circuit simulation on graphies processor units. ASP-DAC, Yokohama, 2009.

54. Белугин С.С. Разработка и исследование физико-табличных математических моделей компонентов ИС. // Диссертационная работа. Москва, МИЭТ. 2006.

55. Страуструп Б. Язык программирования С++, М. : Бином, 2004.

56. Страуструп Б. Дизайн и эволюция С++, Питер-пресс, 2006.

57. Александреску А. Современное проектирование на С++. Изд-во: СПб: Вильяме, 2008.

58. Мейерс С. Эффективное использование С++. ДМК-Пресс, 2000.

59. Фаулер М. Архитектура корпоративных программных приложений. Изд-во: СПб: Вильяме, 2004 г.

60. Саттер Г. Решение сложных задач на С++. Изд-во: СПб: Вильяме, 2002 г.

61. Kevin F. Вгеппап, April S. Brown. Theory of modern electronic semiconductor devices. John Wiley & 'Sons, INC. 2002.

62. Gulati K., Criox F.J., Khatri S.P., Shastry R. Fast Circuit Simulation on Graphics Processing Units. // Design Automation Conference, 2009. ASP-DAC 2009. Asia and South Pacific.

63. Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. ДМК-Пресс, 2010.