Оптимизационный подход к канальной трассировке с учетом помехоустойчивости

Оптимизационный подход к канальной трассировке с учетом помехоустойчивости

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

Full description

Saved in:
Bibliographic Details
Date:2014
Main Author: Иванов, В.Г.
Format: Article
Language:Russian
Published: Інститут технічних проблем магнетизму НАН України 2014
Series:Електротехніка і електромеханіка
Subjects:
Силова електроніка
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/148722
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Оптимизационный подход к канальной трассировке с учетом помехоустойчивости / В.Г. Иванов // Електротехніка і електромеханіка. — 2014. — № 3. — С. 42–44. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-148722
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-1487222025-02-09T17:44:19Z Оптимизационный подход к канальной трассировке с учетом помехоустойчивости Optimization noise stability based approach to channel routing Иванов, В.Г. Силова електроніка Получено решение научно-технической задачи повышения эффективности систем автоматизации проектирования топологии микроэлектронных устройств с учетом помехоустойчивости. Предложены алгоритмы проектирования с учетом помехоустойчивости топологии в канале. Отримано рішення науково-технічної задачі підвищення ефективності систем автоматизації проектування топології мікроелектронних пристроїв з урахуванням завадостійкості. Запропоновано алгоритми проектування з урахуванням завадостійкості топології в каналі. Optimization noise stability based approach to channel routing 2014 Article Оптимизационный подход к канальной трассировке с учетом помехоустойчивости / В.Г. Иванов // Електротехніка і електромеханіка. — 2014. — № 3. — С. 42–44. — Бібліогр.: 5 назв. — рос. 2074-272X DOI: https://doi.org/10.20998/2074-272X.2014.3.08 https://nasplib.isofts.kiev.ua/handle/123456789/148722 658.5 ru Електротехніка і електромеханіка application/pdf Інститут технічних проблем магнетизму НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Силова електроніка
Силова електроніка
spellingShingle Силова електроніка
Силова електроніка
Иванов, В.Г.
Оптимизационный подход к канальной трассировке с учетом помехоустойчивости
Електротехніка і електромеханіка
description Получено решение научно-технической задачи повышения эффективности систем автоматизации проектирования топологии микроэлектронных устройств с учетом помехоустойчивости. Предложены алгоритмы проектирования с учетом помехоустойчивости топологии в канале.
format Article
author Иванов, В.Г.
author_facet Иванов, В.Г.
author_sort Иванов, В.Г.
title Оптимизационный подход к канальной трассировке с учетом помехоустойчивости
title_short Оптимизационный подход к канальной трассировке с учетом помехоустойчивости
title_full Оптимизационный подход к канальной трассировке с учетом помехоустойчивости
title_fullStr Оптимизационный подход к канальной трассировке с учетом помехоустойчивости
title_full_unstemmed Оптимизационный подход к канальной трассировке с учетом помехоустойчивости
title_sort оптимизационный подход к канальной трассировке с учетом помехоустойчивости
publisher Інститут технічних проблем магнетизму НАН України
publishDate 2014
topic_facet Силова електроніка
url https://nasplib.isofts.kiev.ua/handle/123456789/148722
citation_txt Оптимизационный подход к канальной трассировке с учетом помехоустойчивости / В.Г. Иванов // Електротехніка і електромеханіка. — 2014. — № 3. — С. 42–44. — Бібліогр.: 5 назв. — рос.
series Електротехніка і електромеханіка
work_keys_str_mv AT ivanovvg optimizacionnyjpodhodkkanalʹnojtrassirovkesučetompomehoustojčivosti
AT ivanovvg optimizationnoisestabilitybasedapproachtochannelrouting
first_indexed 2025-11-28T22:08:08Z
last_indexed 2025-11-28T22:08:08Z
_version_ 1850073628377350144
fulltext Силова електроніка 42 ISSN 2074-272X. Електротехніка і Електромеханіка. 2014. №3 © В.Г. Иванов УДК 658.5 В.Г. Иванов ОПТИМИЗАЦИОННЫЙ ПОДХОД К КАНАЛЬНОЙ ТРАССИРОВКЕ С УЧЕТОМ ПОМЕХОУСТОЙЧИВОСТИ Отримано рішення науково-технічної задачі підвищення ефективності систем автоматизації проектування тополо- гії мікроелектронних пристроїв з урахуванням завадостійкості. Запропоновано алгоритми проектування з урахуван- ням завадостійкості топології в каналі. Получено решение научно-технической задачи повышения эффективности систем автоматизации проектирования топологии микроэлектронных устройств с учетом помехоустойчивости. Предложены алгоритмы проектирования с учетом помехоустойчивости топологии в канале. В настоящее время идеи автоматизации проекти- рования топологии цифровых систем на кристаллах завоевали широкое признание. Под проектированием топологии понимают определение точного располо- жения электронных элементов на кристалле или под- ложке и реализацию всех соединений (трассировка цепей) в соответствии с электрической схемой так, чтобы удовлетворялись технологические требования к электрическим связям. Разработка новых эффективных по времени и качеству эвристических алгоритмов трассировки яв- ляется актуальной задачей. Большое распространение получили канальные алгоритмы трассировки, которые требуют меньших машинных ресурсов и в большинстве случаев обеспе- чивают полное разведение цепей. Изменяющаяся тех- нология изготовления БИС и СБИС ведет к усложне- нию эвристик трассировки и постоянно требует но- вых, нетрадиционных подходов к решению данной проблемы. Так же нужно отметить о существующих ограничениях, усложняющих эту задачу. Может по- требоваться, чтобы трассировка была проведена в областях фиксированных размеров или чтобы была минимизирована область трассировки. А возникаю- щие паразитные емкости и индуктивности в соседних соединительных проводниках приводит к искажению формы соответствующих сигналов. Существуют раз- личные подходы к решению задачи канальной трас- сировки с различными условиями, технологическими ограничениями и правилами [1-3]. Большинство алгоритмов ориентировано на од- нократную оценку емкостей после завершения про- цесса проектирования. Размерность реальных схем не позволяет даже проводить полный расчет емкостей для всей системы проводников. Большая размерность задачи и необходимость многократных оценок требуют применения быстро- действующих приближенных методов (например, оп- ределения емкостей по геометрическим параметрам проводников), однако сложность структуры микро- электронных устройств (МЭУ) не позволяет полно- стью исключить расчет электростатического поля. В практических расчетах печатный монтаж рассматри- вается обычно как плоскопараллельная система про- водников, собственные и взаимные емкости которых рассчитываются через соответствующие погонные параметры. Исследования физических полей в реаль- ных конструкциях МЭУ показывают, что качествен- ный и количественный характер распределения поля практически не зависит от конкретного положения источника поля на конструктиве. Это позволяет про- водить однократный расчет погонных емкостей для каждого слоя многослойной структуры. Большинство задач конструкторского проекти- рования имеют дискретный (комбинаторный) харак- тер и могут рассматриваться как задачи комбинатор- ной оптимизации [4]. Рассмотрим модель канала. На множествах Аi (множествах разрешенных ва- риантов трасс i-ой цепи) введем метрику Хаусдорфа, доопределенную для элементов, соответствующих отсутствию выбора;              ,0 ~~ ,0 ,0 ~~ ,0 ~~ , , ~ , ~ ),,( ),( 21 2121 21 21 21 ii iiii Nii ii ii i T ii ii Iaadist aa (1) где NT – число цепей канала. Подсчет метрики Хаусдорфа можно значительно упростить, если использовать при этом взвешенную ортогональную метрику исходного евклидова про- странства: , )1(2 0 ,)( 212121 yN x yyxxMM m     (2) где ∆х – минимально допустимое расстояние между центрами контактов по оси абсцисс, ∆у – расстояние между соседними магистралями канала, Nm – число магистралей. В этом случае расстояние между трассами цепи можно оценивать расстоянием между соответствую- щими магистралями:                ,0 ~~ ,0 ,0 ~~ ,0 ~ , ~ , 2 1 , ~ , ~ , ),( 21 2121 21 ~~ 21 21 ii iiii Nii ii ii i T ii ii Iaa aa (3) При таком способе подсчета метрики полагается, что трассы не имеют физической ширины. ISSN 2074-272X. Електротехніка і Електромеханіка. 2014. №3 43 Построим следующие оптимизационные алго- ритмы канальной трассировки на основе общей схемы итерационно-последовательного алгоритма [5]: Алгоритм 1 (алгоритм одиночных переназначе- ний трассировки). Осуществляется циклический последовательный выбор цепей в порядке их нумерации. Из множества Ai выбирается элемент (трасса) ai j которого значение критерия минимально, т.е. элемент с минимальным значением оценки )( jij i F  . (4) Критерий трассировки представляется в виде ,) ~ 1( ))()(( ~~ )( ~ )( 1 1 1 21 1 1             T T T T N k k N k N kt ktktktkttk N k k sign Ccgsign lsignF (5) где lk() – длина трассы k-ой цепи, gkt() – суммарная оценка нарушения ограничений непересечения между трассами k-ой и t-ой цепей, Сkt – оценка взаимной ем- кости трасс k-ой и t-ой цепей, подсчитывается по формуле (1), C – максимально допустимая взаимная емкость двух трасс, λk – штраф за отсутствие выбора трассы для k-ой цепи, 21 , ktkt  – штрафные коэффици- енты соответствующих геометрических и емкостных ограничений. Оценки ij в приращениях относительно вариан- та 0 ~ i могут быть записаны:         0 ~ ,0 0 ~ ,)( )()( 0 ~ 0 j jF FF ii ij ii , (6) где     TN jk k ikikikikkii CCgsignlF 1 21 ))()(( ~ )()( .(7) При этом оцениваются та элементы ai j, для кото- рых raa ii jii i   ),( . Если для всех назначений при- ращения окажутся положительными, то трасса для i- ой цепи не будет выбрана, будет выбран элемент ai 0 (если он попал в соответствующую окрестность). В случае выбора в качестве начального решения )0,...,0,0( ~0  первые NT шагов алгоритма одиночных переназначений можно рассматривать как последова- тельный алгоритм получения начального решения трассировки. Алгоритм 2 (алгоритм парных переназначений трассировки). Осуществляется циклический последовательный выбор пар цепей в порядке нумерации. Соответствую- щая подзадача решается алгоритмом минимального риска. Оценки эффективности выбора трасс строятся по формуле (6). В случае задания в качестве начально- го решения )0,...,0,0( ~0  алгоритм совмещает этапы построения начального варианта трассировки и опти- мизации построенного варианта трассировки. Алгоритм 3 (алгоритм групповых переназначе- ний трассировки). Для выбора подмножеств номеров цепей исполь- зуется алгоритм, аналогичный алгоритму размытой следящей области в задаче размещения. Точки систе- мы Z располагаются на горизонтальной прямой, про- ходящей через центр канала. Расстояние от точки Zn до трасс оценивается в метрике Хаусдорфа, в качестве метрики исходного пространства используется взве- шенная ортогональная метрика (2). Расстояние от точки Zn до трассы равно, таким образом, расстоянию в метрике (2) до наиболее удаленного от точки Zn контакта данной цепи; ) 2 1 1 max ,(     i jn i i n xx mj az i , (8) где ∆ – ширина канала. Задание радиуса окрестности точки выделяет со- ответствующий вертикальный участок канала. Выде- ление для переназначения подмножества цепей, полно- стью принадлежащих заданному вертикальному участ- ку, позволяет существенно упростить решаемую под- задачу. Рассматриваются взаимовлияния только тех цепей, трассы которых пересекают заданный участок. Исследование эффективности алгоритмов 1 и 2 было проведено на ряде тестовых задач, результаты решения двух из которых приведены в табл. 1. Таблица 1 Сравнение эффективности оптимизационных алгоритмов трассировки Задача 1 3адача 2 Вариант начального решения F(ξ0) алго- ритм 2 алго- ритм 3 F(ξ0) алго- ритм 2 алго- ритм 3 1 185 83 55 604 372 300 2 101 79 55 776 456 304 3 187 95 55 604 354 302 4 181 83 55 806 316 282 5 79 79 55 400 400 304 6 79 79 55 320 320 300 7 900 57 55 2500 362 302 1, 2, 3, 4 – интервальные алгоритмы; 5 - макси- мальный алгоритм; 6 – алгоритм минимального риска; 7 – без начального решения. В задаче 1 канал содержит 9 цепей, которые не- обходимо развести на 8 магистралях. В задаче 2 25 цепей канала необходимо развести на 15 магистралях. Координаты контактов цепей: (1; 7), (2; 5), (1; 3); (4; 17); (2; 6), (7; 22), (8; 16), (9; 13), (10; 13), (12; 24), (14; 17), (15; 18), (16; 22), (9; 19), (14; 20), (12; 21), (11; 23), (18; 25), (4; 6), (8; 24), (20; 25),(3; 10), (5; 21), (19; 23), (11; 15). В качестве начального решения использовались результаты ра- боты различных последовательных алгоритмов трас- сировки. Исследовался также вариант, в котором на- чальное решение отсутствовало. Для всех вариантов начальных решений (ни одно из них не было допус- тимым) алгоритм 3 находил допустимый с точки зре- ния ограничений вариант трассировки. Алгоритм 1, 44 ISSN 2074-272X. Електротехніка і Електромеханіка. 2014. №3 как правило, не находил допустимого решения, одна- ко позволял существенно приблизить его к допусти- мой области. Можно сделать вывод, что в задаче трассировки, обладающей жесткими ограничениями, алгоритм 1, обладающий сильными локальными свойствами, недостаточно эффективен. Эффективно применение алгоритма 2, являющегося более мощным средством оптимизации. Применение к решению данных задач алгоритма 3 с объемом решаемых подзадач, равным 5, также позво- лило найти во всех случаях допустимое решение. Вве- дение ограничений на межпроводниковые емкости ограничивает, в конечном счете, длину параллельного горизонтального участка двух трасс. В варианте реше- ния задачи 1, соответствующему минимальному значе- нию суммарной длины трасс, равной 55, длина парал- лельных участков трасс цепей 1 и 8, а также цепей 6 и 9, находящихся на соседних магистралях, равна 5. Ре- шение задачи 1 с учетом ограничений на длину сосед- них параллельных участков трасс позволило подучить алгоритмом 4-.3 вариант трассировки (4, 5, 7, 8, 2, 3, 1, 6, 8), для которого суммарная длина трасс равна 61, однако длина параллельных участков трасс на сосед- них магистралях не превышает 4. ВЫВОДЫ 1. Построены алгоритмы проектирования поме- хоустойчивой топологии в канале на основе общей схемы итерационно-последовательного алгоритма. Проведено сравнение предложенных алгоритмов с известными на тестовых и практических задачах. 2. Проведены исследования влияния решающих правил на результат решения задачи КТ. СПИСОК ЛИТЕРАТУРЫ 1. Shervani N. Algorithms for VLSI physical design automa- tion. Kluwer Academic Publishers, USA, 1995. – 538 p. 2. Yoshimura T., Kuh E.S. Efficient algorithms for channel routing. IEEE Trans. Comput.-Aided Des. Integrated Circuits & Syst., 1982, vol.1, no.1, pp. 25-35. 3. Burstein M. Channel routing. Layout Design and Verifica- tion, Elsevier Science, 1986, pp. 133-167. 4. Семенец В.В., Иванов В.Г. Анализ структуры задачи про- ектирования топологии микроэлектронных устройств // Ра- диоэлектроника и информатика. – 2007. – №3. – С. 113-118. 5. Иванов В.Г. Разработка итерационных алгоритмов ка- нальной трассировки // Автоматизированные системы управ- ления и приборы автоматики. – 2008. – №3/3(33) – С. 29-39. REFERENCES: 1. Shervani N. Algorithms for VLSI physical design automation. Kluwer Academic Publishers, USA, 1995. 538 p. 2. Yoshi- mura T., Kuh E.S. Efficient algorithms for channel routing. IEEE Trans. Comput.-Aided Des. Integrated Circuits & Syst., 1982, vol.1, no.1, pp. 25-35. 3. Burstein M. Channel routing. Layout Design and Verification, Elsevier Science, 1986, pp. 133-167. 4. Semenec V.V., Ivanov V.G. Analiz struktury zadachi proektirovanija topologii mikroelektronnyh ustrojstv. Radioelektronika i informatika, 2007, no.3, pp. 113-118. 5. Ivanov V.G. Razrabotka iteracionnyh algoritmov kanal'noj trassirovki. Avtomatizirovannye sistemy upravlenija i pribory avtomatiki, 2008, no.3/3(33), pp. 29-39. Поступила (received) 19.11.2013 Иванов Виталий Геннадьевич, к.т.н., Институт химических технологий Восточноукраинского национального университета им. Владимира Даля, 93009, Луганская обл., Рубежное, ул. Ленина, 31, тел/phone +38 06453 50156, e-mail: vetgen@e-mail.ua V.G. Ivanov Chemical Technology Institute of Volodymyr Dahl East Ukrainian National University 31, Lenin Str., Rubizhne, Lugansk region, 93009, Ukraine Optimization noise stability based approach to channel routing. A solution to an efficiency improvement problem for microelec- tronic device topology design automation systems is obtained with allowance for noise stability. Noise-stable channel topology de- signing algorithms are introduced. Key words – multi-layered digital system, crystal, design automation, topology, channel routing, optimization.

Similar Items