Спектральные алгоритмы редукции линейных систем управления для задач микроэлектроники тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Карасева, Ирина Андреевна

• Карасева, Ирина Андреевна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Карасева, Ирина Андреевна

Оглавление

Введение

Глава 1. Алгоритм спектральной редукции

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

1.2 Предварительные преобразования

1.3 Блочная диагонализация

1.4 Сбалансированная дихотомия

1.5 Редукция

1.6 Численные эксперименты

1.7 Анализ результатов

1.8 Выводы

Глава 2. Метод быстрого вычисления задержки сигнала

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

2.2 Приближение выходного сигнала функциями Лагерра

2.3 Спектральная коррекция решения

2.4 Быстрое вычисление задержки сигнала

2.5 Численные эксперименты

2.6 Выводы

Заключение

Литература

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

Введение

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

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

Электромагнитный анализ, включенный, как этап проектирования, во все современные САПР микроэлектроники, сводит анализ эффектов, вызванных неидеальностью межсоединений, к анализу различных электрических схем.

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

Среди этих методов можно выделить несколько групп. Методы основанные на приближениях Паде, к таким методом относятся алгоритмы AWE /41, 42/, PVL /9, 10/ и его многопортовая версия MPVL /11/, а также SyPVL /12/ и его многопортовая версия SyMPVL /13, 14, 15/. Методы последовательного исключения узлов, самый известный метод TICER /8/. Проекционные методы с использованием подпространств Крылова /19, 20, 21/, среди которых наиболее известным является алгоритм PRIMA /16, 17, 18/. Спектральные методы, наиболее известный PACT /22, 23/. Методы сбалансированного усечения и другие /48, 49, 50/.

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

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

Цель диссертационной работы. Работа посвящена разработке и исследованию спектрального алгоритма редукции для RCLM-схем и метода быстрого вычисления задержки сигнала для RC-схем.

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

пассивности. Для RC-схем этот метод подобен хорошо известному методу PACT /22/, основанному на преобразованиях конгруэнтности, и может трактоваться как его обобщение. До настоящего времени не существовало спектральных алгоритмов для RLCM-схем, позволяющих сохранять пассивность. Для редукции RCL и RCLM схем применялись другие методы(/48, 49, 50/), главным образом технология PRIMA, основанная на аппроксимации в подпространствах Крылова.

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

Методы исследования. Для разработки и обоснования алгоритмов в диссертации используются методы матричного анализа.

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

Апробация результатов. Основные положения, сформулирован-

ные в диссертационной работе, обсуждались на семинарах в ФГБУ науки Институте вычислительной математики РАН, московском отделении Cadence Design Systems, ФГБУ науки Институте проблем проектирования в микроэлектронике, ФГБУ науки Вычислительный центр им. A.A. Дородницына РАН, НИЦ "Курчатовский институт", международной конференции " Matrix Methods and Operator Equations" (г. Москва, 2008 год), школе-конференции молодых ученых конференции "Математические идеи П. Л. Чебышева и их приложения к современным проблемам естествознания" (г. Обнинск, 2011 год).

Публикации. Основные результаты диссертации изложены в четырех печатных работах, две из которых опубликованы в журналах, рекомен-дованых ВАК.

Личный вклад автора. В работах [1,3], написанных в соавторстве, личный вклад автора в равных долях с соавторами.

Структура и объём диссертации. Диссертация состоит из введения, двух глав, заключения и списка литературы, состоящего из 51 наименований. Общий объем составляет 107 страниц, в том числе 23 таблицы и 10 рисунков.

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

На первом этапе используя преобразования конгруэнтности, исход-

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

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

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

Были проведены численные эксперименты на ИСЬ и ЖХМ-схемах из промышленного дизайна. Численные эксперименты показали высокую

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

Во второй главе рассматривается метод быстрого вычисления задержки сигнала для ЫС-схем. Моделирование ИС-схем на основе законов Ома и Кирхгофа приводит к линейной системе обыкновенных дифференциальных и алгебраических уравнений. Задержка определяется как разность времени, за которое напряжение, поданное на вход, достигает определенного значения, и времени, за которое напряжение на выходе достигает того же значения. Таким образом для приближенного вычисления задержки сигнала для заданного входного сигнала, необходимо найти приближенное значение выходного. Рассматривалась задача с одним выходом.

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

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

Предложенный метод был использован для быстрого вычисления за-

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

Для сигналов которые достигают 1 вольта за время Т — 100, 200 и 400 пикосекунд были проведены численные эксперименты при помощи набора, состоящего из 35000 схем из промышленных дизайнов. Из этого набора выбирались схемы для дальнейшего исследования при помощи одного из критериев. Если схема удовлетворяла выбранному критерию, то для него вычислялось выходной сигнал, приближенное и точное время задержки и погрешность. В противном случае схема отбрасывался. Численные эксперименты показали эффективность представленного метода. Алгоритм позволяет быстро обработать примерно 59% схем из представленного набора.

Основные результаты и выводы.

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

2. Обоснованы преобразования, используемые в этом алгоритме. Доказано сохранение пассивности.

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

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Карасева, Ирина Андреевна

2.6. Выводы

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

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

Подводя итоги можно сделать следующие выводы:

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

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

Заключение

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

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

Алгоритмы представленные в данной работе были протестированы с использованием схем взятых из промышленных дизайнов. Спектральный алгоритм редукции был протестирован на ЯЬС и ЯСЬМ схемах. Для метода быстрого вычисления задержки сигнала также были проведены численные эксперименты с использованием набора состоящего из 35000 схем.

Численные эксперименты показали высокую эффективность обоих алгоритмов.

Список литературы диссертационного исследования кандидат физико-математических наук Карасева, Ирина Андреевна, 2012 год

Литература

1. I. A. Karaseva, Yu.M. Nechepurenko, A.S. Potyagalova. Spectral reduction for control systems modeling passive integrated circuits // Сотр. Maths. Math. Phys.. 2008. V.48, N.5. P.746-762.

2. Yu.M. Nechepurenko, A.S. Potyagalova, I.A. Karaseva Spectral model order reduction preserving passivity for large multiport RCLM networks //in Matrix methods: theory, algorithms, applications / Ed by Vadim Olshevsky and Eugene Tyrtyshnikov. New Jersey London: World Scientific Publishing. 2010. P.533-538.

3. I.A. Karaseva. Fast calculation of signal delay in RC-circuits based on Laguerre functions // Russ. J. Numer. Anal. Mach. Modeling. 2011. V.26, N3. C.295-301.

4. И.А. Карасева. Быстрое вычисление задержки сигнала в RC-схемах на основе функций JIareppa // V Международная конференция " Математические идеи П.Л.Чебышева и их приложение к современным проблемам естествознания". Научная школа-конференция молодых исследо-вателей:Тез. докладов / Под общей ред. В.А. Галкина. Обнинск: ИАТЭ НИЯУ МИФИ. 2011. С.21-22.

5. К. Nabors, J. White. FastCap: A multipole accelerated 3-D capacitance extraction program // IEEE Trans. Computer-Aided Design. 1991. V.10, N.ll. P. 1447-1459.

6. J. P. Hwang. REX-a VLSI parasitic extraction tool for electromigration and signal analysis // Proceedings of the 28th conference on ACM/IEEE design automation. 1991. P.717-722.

7. Kuang-Wei Chiang, Kuang-Wei Chiang, Chi-Yuan Lo. Time efficient VLSI artwork analysis algorithms in GOALIE2 // Proceedings of the 25th ACM/IEEE conference on Design automation. 1988. P.471-475.

8. B.N. Sheehan. Realizable Reduction of RC Networks // IEEE Trans. CAD. 2007. P. 1393—1407.

9. P. Feldmann, R. W.Freund. Efficient linear circuit analysis by Pade approximation via theLanczos process // In: Proceedings of EURO-DAC '94 with EURO-VHDL '94, IEEE Computer Society Press. 1994. P. 170-175.

10. P. Feldmann , R.W. Freund. Efficient linear circuit analysis by Pade approximation via the Lanczos process // IEEE Trans. Comput. Aided Des.. 1995. V.14. P.639-649.

11. P. Feldmann, R.W. Freund. Reduced-order modeling of large linear subcircuits via a block Lanczos algorithm // In: Proceedings 32nd ACM/IEEE Design Automation Conference. 1995. P.474-479.

12. R.W. Freund, P. Feldmann. Reduced-order modeling of large passive linear circuits by means of the SyPVL algorithm // In: Technical Digest 1996 IEEE/ACM International Conference on Computer-Aided Design.IEEE Computer Society Press. 1996. P.280-287.

13. P.Feldmann, R.W. Freund. Interconnect-delay computation and signal-integrity verification using the SyMPVL algorithm // In: Proceedings of 1997 European Conference on Circuit Theory and Design. IEEE Computer Society Press. 1997. P. 132-138.

14. R.W. Freund, P.Feldmann. The SyMPVL algorithm and its applications to interconnect simulation // In: Proceedings of 1997 International Conference on Simulation of Semiconductor Processes and Devices. IEEE. 1997. P.113-116.

15. R. W. Freund, P.Feldmann. Reduced-order modeling of large linear passive multi-terminal circuits using matrix-Pade approximation // In: Proceedings of Design, Automation and Test in Europe Conference. IEEE Computer Society Press. 1998. P.530-537.

16. A. Odabasioglu, M. Celik, L.T. Pileggi. PRIMA: passive reduced-order interconnect macromodeling algorithm // IEEE/ACM International Conference on Computer-Aided Design, IEEE Computer Society Press. 1997. P.58-65.

17. A. Odabasioglu, M. Celik, L. T. Pileggi. PRIMA: passive reduced-order interconnect macromodeling algorithm //In: Technical Digest 1997 IEEE/ACM International Conference on Computer-Aided Design, IEEE Computer Society Press. 1998. V.17(8). P.645-654.

18. M. Celik, L. Pileggi, A. Odabasioglu. IC Interconnect analysis. Kluwer Academic Publishers. 2002.

19. R. W. Freund. On Padii-type model order reduction of J-Herimitian linear dynamical systems // Linear Algebra Appl. 2008. V.429. P.2451-2464.

20. R. W. Freund. Krylov-subspace methods for reduced-order modeling in circuit simulation // J. Comput. Appl. Math. 2000. V.123(l-2). P.395-421.

21. L.M. Silveira, M. Kamon, I. Elfadel, J. White. A coordinate-transformed Arnoldi algorithm for generating guaranteed stable reduced-order models of RLC circuits // In: Technical Digest 1996 IEEE/ACM International

Conference on Computer-Aided Design,IEEE Computer Society Press. 1996. P.288-294.

22. K.J. Kerns, A.T. Yang. Stable and efficient reduction of large multiport RC networks by pole analysis via congruence transforms//IEEE Trans. Computer-Aided Desing, 1997. V.17, N7. P.734-744.

23. K.J. Kerns, A.T. Yang. Preservation of passivity during RLC network reduction via congruence transforms // IEEE Trans. Computer-Aided Desing. 1998. V.16, N7. P.582-590.

24. G.H. Golub, C.F. Van Loan. Matrix computations, London: The John Hopkins University Press. 1991.

25. Ф.Р. Гантмахер. Теория матриц, Москва: Наука. 1966.

26. S.K. Godunov. Modern aspects of linear algebra. Transl. Math. Monographs. Providence. RI: Am. Math. Soc. V.175. 1998.

27. Ж.М. Рабаи, А. Чандракасан, Б. Николич. Цифровые интегральные схемы. Методология проектирования, Москва: Вильяме. 2007.

28. K.J. Kerns, A.T. Yang. Stable and efficient reduction of large, multiport RC networks by pole analysis via congruence transformations // IEEE Trans. CAD. 1997. V.16, N7. P.734-744.

29. E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra ,J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov and D. Sorensen. LAPACK Users Guide. Philadelphia: SIAM. 1992.

30. G. Stewart, J. Sun. Matrix perturbation theory, San Diego, California: Academic Press. 1990.

31. В. D. 0. Anderson, S. Vongpanitlerd. Network Analysis and Synthesis. N J.: Englewood Cliffs. Prentice-Hall. 1973.

32. M.R. Wohlers. Lumped and Distributed Passive Networks: A generalized and advanced viewpoint. NY: Academic. 1969.

33. Yu.M. Nechepurenko. A new spectral analysis technology based on the Schur decomposition // Russ. J. Numer. Anal. Math. Modelling. 1999. V.14, N3, P.265-274.

34. Ю.М. Нечепуренко, А. С. Потягалова. Общие свойства и модификации алгоритмов редукции // сб. Проблемы разработки перспективных микро- и наноэлектронных систем,- М.: ИППМ РАН. 2008. С.102-106.

35. А. С. Потягалова. Общие свойства и модификации алгоритмов редукции // Нано- и микросистемная техника. 2008. N7, С.15-19.

36. Z. Zhuquan, С. Antonio, L. Т. Kok. Continuous-time envelope-constrained filter design via Laguerre filters and H^ optimization methods // IEEE Trans. Signal Processing, 1998. V.46, N10, P.2601-2610.

37. C.K. Годунов. Обыкновенные дифференциальные уравнения с постоянными коэффициентами. Т.1: Краевые задачи. Новосибирск: Изд-во Новосиб. ун-та. 1994.

38. Дж. Ортега A new spectral analysis technology based on the Schur decomposition // Russ. J. Numer. Anal. Math. Modelling. 1999. V.14, N3. P.265-274.

39. A.C. Потягалова, И.Е. Солтан, Д.Ф. Ткачев, М. М. Хапаев. Опыт применения редукции паразитных элементов с использованием методов подпространств Крылова. // Нано- и микросистемная техника. 2006. N6. С.43-47.

40. D.P. Anderson, S. Vongpanitlerd. Network analysis and synthesis. A modern systems theory approach, New Jersey: Prentice-Hall, Inc.. 1973.

41. L.T. Pillage, R.A. Rohrer. Asymptotic waveform evaluation for timing analysis // IEEE Trans. Comput. Aided Des. 1990. V.9, P.352-366.

42. P. Feldmann, R. W. Freund. Efficient linear circuit analysis by Pade approximation via the Lanczos process // IEEE Trans. Comput. Aided Des, IEEE Computer Society Press. 1995. V.14. P.639-649.

43. W.HA. Schilders. Solution of indefinite linear systems using an LQ decomposition for the linear constraints Lin. Alg. Appl.. 2009. V.431. P.381-395.

44. W.H.J1. Schilders. The Need for Novel Model Order Reduction Techniques in the Electronics Industry // Model Reduction for Circuit Simultation. V.74. P.3-23.

45. A. Charest, R. Achar, M. Nakhla, I. Erdin. Delay extraction-based passive macromodeling techniques for transmission line type interconnects characterized by tabulated multiport data // Analog Int. Circ. Sign. Proc.. 2009. V.60. P. 13-25.

46. P. Feldmann, R. W. Freund. Interconnect-delay computation and signal-integrity verification using the SyMPVL algorithm // In: Proceedings of 1997 European Conference on Circuit Theory and Design. IEEE Computer Society Press. 1999. P. 132-138.

47. P. Liu, S.X.D. Tan, H. Li, Z. Qi, J. Kong, B. McGaughy, L. He. An efficient method for terminal reduction of interconnect circuits considering delay variations // In: ICCAD '05: Proceedings of the 2005 IEEE/ACM

International Conference on Computer-Aided Design. IEEE Computer Society. 2005. P.821-826.

48. P.J. Heres. Robust and efficient Krylov subspace methods for model order reduction // PhD Thesis. TU Eindhoven. The Netherlands. 2005.

49. R. Ionutiu, S. Lefteriu, A.C. Antonias. Comparison of model reduction methods with applications to circuit simulation // In: Proceedings SCEE-2006 Conference. Ciuprina, G., loan, D. (eds.) Springer Verlag. 2008. P. 3-24.

50. D. Saraswat, R. Achar, M.S. Nakhla. Global passivity enforcement algorithm for macromodels of interconnect subnetworks characterized by tabulated data // IEEE Trans. VLSI Syst.. 2005. V.13. P.819-832.

51. S. Grivet-Talocia, A. Ubolli. A comparative study of passivity enforcement schemes for linear lumped macromodels // IEEE Trans. Adv. Pack.. 2008. V.31. P.673-683.