Проектування топології багатошарових цифрових систем на кристалах з урахуванням завадостійкості

Размещено на http://www.allbest.ru/

Харківський національний університет радіоелектроніки

УДК 004.382-027.252

05.13.12 - системи автоматизації проектувальних робіт

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

ПРОЕКТУВАННЯ ТОПОЛОГІЇ БАГАТОШАРОВИХ ЦИФРОВИХ СИСТЕМ НА КРИСТАЛАХ З УРАХУВАННЯМ ЗАВАДОСТІЙКОСТІ

Іванов Віталій Геннадійович

Харків - 2011



Дисертацією є рукопис

Робота виконана в Харківському національному університеті радіоелектроніки Міністерства освіти і науки, молоді та спорту України.

Науковий керівник - доктор технічних наук, професор, лауреат Державної премії України в галузі науки і техніки Семенець Валерій Васильович, Харківський національний університет радіоелектроніки, перший проректор.

Офіційні опоненти: доктор технічних наук, професор Лобур Михайло Васильович, національний університет «Львівська політехніка», завідувач кафедри систем автоматизації проектування;

доктор технічних наук, доцент Литвинова Євгенія Іванівна, Харківський національний університет радіоелектроніки, професор кафедри автоматизації проектування обчислювальної техніки.

Захист відбудеться «10» червня 2011 р. о 13-00 годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий «6» травня 2011 р.

Вчений секретар спеціалізованої вченої ради Підпис Безкоровайний В.В.



ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. На сьогодні ідеї автоматизації проектування різних об'єктів завоювали широке визнання. Системи автоматизації стають незамінним інструментом проектувальника, особливо при створенні технічних систем, що характеризуються великою функціональною складністю і високим ступенем надійності. Однією з головних задач загальної проблеми автоматизації проектування і конструювання мікроелектронних пристроїв (МЕП) є автоматизація їх топологічного синтезу. Значне зростання розмірності задач топологічного проектування призводить до необхідності вдосконалення старих і розробки нових методів машинного проектування. Розробці математичних моделей, методів і алгоритмів автоматизації конструкторського проектування присвячені роботи А.Е. Абрайтіса, Р.П. Базилевіча, А.М. Бершадського, Б.М. Деньдобренко, В.М. Курейчика, К.К. Морозова, А.І. Петренка, Г.Г. Рябова, О.Я. Тетельбаума, І.П. Норенкова, М.В. Лобура, М.Гері, М.Ватенабе, До. Асада, Є. Ку, Х. Брейді, Д. Ульмана, До. Нісена, Р. Ейріса.

Не дивлячись на численні публікації, присвячені розв'язання задачі канального трасування МЕП, актуальною залишається задача підвищення ефективності систем автоматизації проектування топології цифрових систем на кристалах.

Зокрема, потрібна узагальнена постановка задачі багатошарового канального трасування, що враховує вплив «паразитних» ємностей на роботу цифрових систем, розробка математичних методів розв'язання задачі проектування топології з урахуванням вимог точності, обчислювальних і часових обмежень.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до плану Міністерства освіти і науки, молоді та спорту України в Харківському національному університеті радіоелектроніки (ХНУРЕ) в період з 2004 по 2010 роки в рамках науково-дослідних робіт: держбюджетна тема №238 «Розробка засобів для дослідження мікропроцесорних систем управління» (№ДР 0109U000664); госпдоговірної теми №08-38 «Дослідження й розробка методів контролю властивостей матеріалів, що утворюють монтажні з'єднання електронної апаратури» розділ 3 «Ітераційний метод канального трасування, адаптивний до конструкторських і технологічних обмежень» (№ДР0108U010273); дослідницько-конструкторської роботи «Точність» розділ 2 «Метод проектування багатошарових цифрових систем на кристалах» (№ДР01080005914).

Здобувач брав участь у виконанні робіт за вказаними темами як виконавець. В рамках виконаних робіт ним розроблені математичні методи, алгоритми і програмне забезпечення для розв'язання задач канального трасування.

Мета і завдання дослідження. Метою дисертаційної роботи є розробка математичних методів, алгоритмів і інструментальних засобів для проектування топології багатошарових цифрових систем на кристалах з урахуванням завадостійкості і вирішення на цій основі важливого науково-практичного завдання підвищення ефективності систем автоматизації проектування топології МЕП з урахуванням вимог точності, обчислювальних і часових обмежень. багатошаровий цифровий топологія автоматизація

Для досягнення поставленої мети потрібне розв'язання таких задач:

- провести огляд і аналіз сучасного стану проблеми автоматизованого проектування топології МЕП задля виявлення шляхів підвищення ефективності систем їх автоматизованого проектування;

- сформулювати постановку загальної задачі проектування топології багатошарових цифрових систем на кристалах з урахуванням завадостійкості;

- провести дослідження системи обмежень для задачі канального трасування для зменшення області допустимих рішень;

- розробити ітераційні методи для задачі канального трасування (КТ), орієнтовані на загальну постановку задачі проектування топології;

- розробити методи і програмне забезпечення для розв'язання задачі канального трасування МЕП;

- провести експериментальне дослідження ефективності і практичну апробацію отриманих теоретичних результатів.

Об'єктом дослідження є процеси синтезу фізичних структур багатошарових цифрових систем на кристалах.

Предметом дослідження є методи канального трасування багатошарових цифрових систем на кристалах на етапі їх проектування.

Методи досліджень. Дослідження базуються на комплексному використанні методів системного аналізу, теорії графів, математичного програмування. При розв'язанні задачі КТ використана теорія графів і метод системного аналізу; для розв'язання задач оптимізації проектування топології були використані методи направленого перебору варіантів.

Наукова новизна отриманих результатів. Результатом дослідження є розробка комплексу математичних методів та інструментального засобу для розв'язання задач оптимізації канального трасування і вирішення на цій основі важливої науково-технічної задачі підвищення ефективності систем автоматизації проектування топології цифрових систем на кристалах з урахуванням завадостійкості, вимог точності, обчислювальних і часових обмежень.

В насідок дослідження отримані такі нові результати:

- запропонована загальна комбінаторна постановка задачі канального трасування, як для двошарових, так і для багатошарових структур, що враховує впливи «паразитних» ємностей на роботу цифрових систем;

- розроблена система вирішальних правил, яка, на відміну від існуючих методів канального трасування, дозволяє зменшити зону пошуку допустимих рішень при проектуванні мікроелектронних пристроїв;

- розроблені ітераційні методи канального трасування багатошарових структур, що мають істотно меншу часову складність, чим відомі методи перебору;

- знайдені умови трасування планарної схеми в чотирьохсторонньому одношаровому каналі, які надають можливість отримувати більш ефективні проектні рішення.

Практичне значення отриманих результатів. Розроблені методи проектування топології цифрових систем на кристалах з урахуванням завадостійкості розвивають методологічну основу створення ефективних інструментальних засобів систем підтримки прийняття рішень для технологій автоматизованого трасування мікроелектронних пристроїв.

Усі запропоновані методи розв'язання задачі реалізовані програмно. Вони апробовані, показали свою працездатність і ефективність на прикладах розв'язання задач канального трасування.

Практичне значення результатів підтверджується їх впровадженням. Результати дисертаційної роботи впроваджені: у держбюджетну науково-дослідну роботу, виконану згідно з тематичним планом науково-дослідних робіт ХНУРЕ, що фінансуються за рахунок Міністерства освіти і науки, молоді та спорту України; у навчальному процесі на кафедрі проектування і експлуатації електронних апаратів ХНУРЕ (акт від 15.12.2010 р.); у ЦККБ «Протон» (акт від 10.02.2011 р.); у ГНПП «Об'єднання Комунар» (акт від 1.02.2011 р.).

Особистий внесок здобувача. Усі основні результати дисертаційної роботи отримані здобувачем особисто і опубліковані в роботах [1-10]. У роботах, опублікованих із співавторами здобувачеві належать такі результати: у [1] - способи зменшення області оптимізації задачі канального трасування; у [2] - схема розв'язання задачі розміщення; у [3] - цільова функція для задачі розміщення елементів на друкованій платі; у [4] - доведені твердження для зменшення зони пошуку задачі канального трасування; у [5] - дослідження ефективності вирішальних правил в задачі канального трасування; у [7] - програмне забезпечення для САПР; у [8] - розв'язання задачі установки компонентів при поверхневому монтажі; у [9] - критерій ранжирування при розв'язанні топологічних задач; у [10] - розрахунок об'єму припою при поверхневому монтажі.

Апробація результатів дисертації. Основні положення дисертаційної роботи і результати досліджень опубліковані в 6 статтях, докладалися і обговорювалися на: Третій науково - практичній Інтернет - конференції «Україна наукова», м. Київ, 20-22 грудня 2007 р.; Четвертій міжнародній науково-практичній конференції «Розвиток наукових досліджень 2008», м. Полтава 24-26 грудня 2008р.; Третій міжнародній науково-практичній конференції «Розвиток наукових досліджень 2007», м. Полтава, 26-28 грудня 2007 р.; Третій міжнародній науково-практичній Інтернет - конференції «Соціум. Наука. Культура», м. Київ 29-31 січня 2008 р.

Публікації. Основні результати дисертаційної роботи опубліковані в 10 роботах, з них: 6 статей в журналах і збірниках наукових праць, що входять до переліків, затверджених ВАК України, 4 тез доповідей, опублікованих в матеріалах наукових конференцій.

Структура та обсяг роботи. Робота складається із вступу, 4 розділів, висновків, списку використаних джерел із 130 найменувань на 14 сторінках, 1 додатку на 5 сторінках. Її повний обсяг становить 163 сторінки, у тому числі 26 рисунків (21 сторінка), 7 таблиць (7 сторінок).

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтована актуальність теми досліджень та необхідність розробки математичних методів синтезу топології цифрових систем на кристалах; сформульовані мета, завдання, об'єкт, предмет дослідження, наукова новизна та практична цінність роботи; названі методи дослідження; наведено декларацію особистого внеску здобувача у публікаціях зі співавторами, відомості про апробацію результатів і публікації за темою дисертації.

Перший розділ роботи присвячено огляду й аналізу сучасного стану проблеми автоматизованого проектування топології мікроелектронних пристроїв. У ньому виділені особливості МЕП як об'єктів автоматизованого проектування. МЕП, які проектуються, істотно розрізняються за кількістю шарів топології, розташуванням вертикальних та горизонтальних фрагментів схеми, кроком координатної сітки. Це потребує використання у системах автоматизації множин методів синтезу топології, що розрізняються за точністю, часовою та ємнісною складністю.

На основі огляду публікацій за темою дослідження виділено постановки і математичні описи типових задач при канальному підході проектування топології багатошарових систем на кристалах.

Встановлена необхідність постановки узагальненої задачі синтезу топології цифрових систем на кристалах, яка б об'єднувала відомі часткові задачі та враховувала б різнорідні критерії оптимізації. Для такої задачі необхідною є розробка математичних методів її розв'язання для кристалів з різною кількістю шарів топології та із врахуванням вимог точності, обчислювальних і часових обмежень.

У другому розділі досліджується структура обмежень задачі трасування у каналі. Показано, що розмірність не є вичерпною характеристикою складності задачі трасування. Важливим є врахування структури задачі трасування, що дає можливість спрощення, зведення до менш складних завдань. Показано, що залежно від виду обмежень є можливість значно зменшити область оптимізації цільової функції за рахунок відсікання неприпустимих варіантів трасування. На підставі доведених тверджень розроблені вирішальні правила для зменшення області пошуку. Визначені умови трасування одношарового МЕП, запропоновано метод трасування планарної схеми в одношаровому каналі. Регулярність структури вузлів мікроелектронної апаратури дозволяє застосувати канальний підхід при розробці їх топології. У таких конструкціях виділяється мережа горизонтальних і вертикальних каналів. Система обмежень трасування описується за допомогою графу вертикальних обмежень, графу горизонтальних обмежень і узагальненого графу вертикальних і горизонтальних обмежень (УГВГО). Розв'язання задачі трасування визначається так: для m вивідного ланцюга конфігурація містить один горизонтальний і m вертикальних відрізків. Горизонтальний відрізок розташовується в одному комутаційному шарі, вертикальні - в іншому. Групою називається множина ланцюгів, для яких існує шлях у графі вертикальних обмежень. Таким чином, задача трасування із застосуванням горизонтальних обмежень зводиться до пошуку розфарбовування вершин графа горизонтальних обмежень (графу інтервалів) GH(V, W) у найменшу кількість кольорів так, щоб суміжні вершини були позначені різними кольорами. Тут V - множина ланцюгів, W - множина ребер (обмежень). Вертикальні обмеження враховуються за допомогою графу GV (V, U), в якому дуга направлена від вершини i до вершини j, якщо хi < хj, де xi , хj - номери магістралей i-го і j-го ланцюгів. Задача трасування постає у вигляді:

(1)

, (2)

де ; ; n - кількість магістралей каналу; N - кількість ланцюгів у каналі.

(3)

(4)

(5)

де - множина кінцевих вершин всіх ребер, вихідною вершиною якої служить vi; - множина, зворотна множині .

Розглянуті двоконтактні ланцюги з одним горизонтальним фрагментом, координати контактних майданчиків яких пов'язані співвідношенням (i - номер ланцюга). Множина ланцюгів, для яких виконується ця умова, називається правою групою ланцюгів. Для будь-яких двох груп правих ланцюгів визначаються:

, i=1, 2, …, ; ; (6)

, (7)

де l1, l2 - довжина шляху у графі вертикальних обмежень першої і другої групи, відповідно; - локальний степінь вершини з номером aj.

Розглянемо УГВГО, для всіх вершин якого справедливе співвідношення рi> 0, .

Розглянемо t груп правих ланцюгів. Припустимо, що в УГВГО локальний степінь усіх вершин відмінний від нуля. Для кожної пари груп по аналогії із (6) - (7) обчислимо

,

де dб - кількість вершин групи з номером б, локальний степінь яких більше за одиницю; lб - довжина дуги в графі вертикальних обмежень з номером б .

Твердження 2.1. Якщо , то для трасування груп ланцюгів необхідні і достатні l треків, де .

У випадку, якщо знайдеться таке k, для якого gк <0, вводяться фіктивні вершини, що збільшують довжину шляху у графі вертикальних обмежень. Їх кількість вибирається так, щоб gj >0, .

Припустимо, що G - це граф, вершини якого відповідають групам ланцюгів, а ребра мають вагу, рівну кількості магістралей, на яких можуть бути реалізовані відповідні групи ланцюгів.

Твердження 2.2. Якщо виконується умова трикутника, то трасування t груп можливе на l - магістралях, де l - довжина мінімального орієнтованого шляху, що проходить через всі вершини графа G.

Наслідок. Якщо умова трикутника не виконується (lij>lik+lkj), то замінимо кожен елемент lij, для якого не виконується умова трикутника, на елемент

min[lik + lki] і продовжимо цю заміну доти, доки для всякого k не буде справедлива нерівність lij ? lik + lkj. Тоді довжина мінімального орієнтованого шляху, що проходить через усі вершини графа, буде нижньою межею для задачі трасування груп ланцюгів.

Якщо в групах існують вершини з локальним степенем, рівним нулю, то для двох груп ланцюгів справедливі твердження:

Твердження 2.3. Якщо gi ? 0, i = 1, 2,..., d, то для трасування двох груп ланцюгів необхідні і достатні l треків, де l = max{l1, l2}.

Твердження 2.4. Якщо в УГВГО, який описує обмеження на розташування правої групи і лівої групи ланцюгів, не існує вершин із локальним степенем рівним нулю, то трасування двох груп ланцюгів можливе на на l+1 треках, де l=max{l1, l2}.

Припустима множина розв'язків задачі не зміниться при заміні графа GV будь-якою його ступеню. Разом з тим, у графі вертикальних обмежень з'являться додаткові ребра. Протяжність e(vi,vj) визначається як шлях найбільшої довжини від вершини vi до vj. Числа протяжності для вершини vi визначаються як e- (vi) - максимальний простий шлях з кінцевою вершиною vi і e+ (vj) - максимальний простий шлях із початковою вершиною vi у графі GV. Отже, задача трасування приводиться до вигляду:

; (8)

; (9)

; (10)

; (11)

; (12)

. (13)

Твердження 2.5. Якщо для деякої підмножини вершин однієї вертикалі потужність множини припустимих значень змінних дорівнює потужності даної підмножини вершин і при вилученні з неї деякої вершини потужність множини припустимих значень зменшується на одиницю, то для будь-якого допустимого розв'язання початкової задачі значення змінної, відповідної вершині, має дорівнювати такому значенню, що вилучається.

Наслідок 1. Якщо для якоїсь вертикалі потужність підмножини вершин дорівнює М і існує єдина вершина з нульовим додатним або від'ємним числом протяжності, то значення відповідної змінної в будь-якому припустимому розв'язанні задачі дорівнює 1 у випадку нульового негативного числа протяжності і М у випадку нульового додатнього числа протяжності.

Наслідок 2. Для будь-якої вертикалі потужність підмножини вершин не може перевищувати М.

Твердження 2.6. Якщо потужність підмножин вершин для двох сусідніх вертикалей дорівнює М і підмножини відрізняються одна від одної однією вершиною, то в будь-якому припустимому розв'язанні задачі значення змінних, відповідні цим різним для підмножин вершинам, мають бути рівні.

Твердження 2.7. Якщо потужність підмножин вершин для двох сусідніх вертикалей дорівнює М і підмножини відрізняються одна від одної двома вершинами, то в будь-якому припустимому розв'язанні задачі значення змінних, відповідні цим різним для підмножин вершинам, мають бути попарно рівні, причому склад пар однозначно визначається напрямом ребер у графі вертикальних обмежень.

Твердження 2.8. Якщо для двох вершин УГВГО виконується умова і вони зв'язані неорієнтованим ребром, то або , або .

Твердження 2.9. Якщо для двох вершин vi і vj УГВГО, не зв'язаних ребром, виконуються умови: , то .

Отримані також умови трасування одношарового каналу з можливістю приведення трас під кутом 45є до лінії ортогональної сітки. Розглядається канал, на горизонтальних сторонах, якого розміщені контактні майданчики ланцюгів.

Твердження 2.10. 3адача трасування планерної схеми в каналі має розв'язання, якщо кількість магістралей не менша за щільність каналу.

У тому випадку, коли контактні майданчики схеми розташовані на чотирьох сторонах каналу, умови трасування формулюються таким чином.

Твердження 2.11. Задача трасування планарної схеми в каналі має розв'язання, якщо кількість горизонтальних магістралей не менша за вертикальну щільністі, а кількість вертикальних магістралей не менша за горизонтальну щільність каналу.

Виходячи із сформульованих тверджень 2.10 і 2.11 розроблений метод трасування одношарового каналу.

У третьому розділі розглянутий оптимізаційний підхід до вирішення задачі КТ.

Зафіксуємо прямокутну декартову систему координат . Розглянемо паралелепіпед, обмежений площинами , , , , , , де , , - фіксовані числа. Визначимо граф, який називатимемо каналом завдовжки , шириною і висотою .За вертикаль цього графу вважатимемо всі точки із цілочисельними координатами, що задовольняють умовам: , , . Ребрами графа є всі лінії системи координат, що сполучають вершини графа. Площину , називатимемо шаром. Множини виводів електричної схеми відображаються у множини вершин , , . Відповідно до цієї множини виводи схеми можуть лежати в будь-якому шарі. Виводи електричної схеми, що належать областям і позначатимемо, відповідно, додатними і від'ємними числами. Міжшарові переходи можуть сполучати будь-яку задану кількість шарів каналу. Прямі, паралельні осі називатимемо магістралями каналу і позначимо , (, ). Прямі, паралельні осі , називатимемо вертикалями каналу. Прямі, паралельні осі , називаються стовпцями каналу.

Множини координат виводів -го ланцюга позначаються

де - кількість виводів -го ланцюга.

Множини всіх ланцюгів називатимемо схемою , .

Ланцюг являє собою один горизонтальний відрізок - інтервал. Багатоконтактні ланцюги розділяються на двохконтактні сегменти. Надалі будь-яке електричне з'єднання називатимемо ланцюгом. Траси ланцюгів можуть проходити тільки по ребрах графа. Шар, в якому розташовуються переважно вертикальні (горизонтальні) провідники, називатимемо вертикальним (горизонтальним) V-шаром (H-шаром). Горизонтальні і вертикальні шари строго чергуються HVHV. Вибір такої моделі трасування дозволяє отримувати розв'язок із мінімальним ємнісним зв'язком між ланцюгами.

Для кожного ланцюга множини трас визначаються набором магістралей. Призначення інтервалів ланцюгів схеми , (де - кількість ланцюгів) на магістралі каналу однозначно визначає трасування заданої схеми. Під розв'язанням задачі канального трасування розумітимемо таке призначення інтервалів ланцюгів на магістралі каналу, при якому задовольняються всі технологічні обмеження. Розв'язком є вектор

, , ; , .

Елемент визначає номер магістралі в шарі , на яку призначений ланцюг. Множина - кінцева числова множина, елементи якої визначають номери магістралей, на які може бути призначено ланцюг . Для кожного ланцюга множини індивідуально визначаються зовнішніми і внутрішніми обмеженнями. Зовнішніми обмеженнями можуть виступати перешкоди у каналі, раніше прокладені ланцюги, нерівномірна ширина каналу. Внутрішніми обмеженнями є геометричні обмеження, направлені на неперетинання трас.

Формальний запис задачі КТ, як задачі комбінаторної оптимізації на прямому добутку числових множин, може бути представлена в такому вигляді:



де

, , ; , .

Відповідно до даної постановки серед усіх векторів , що належать області припустимих розв'язків , необхідно вибрати такий вектор , який мінімізує функціонал . Функціонал відображає якість призначення ланцюгів схеми на магістралі каналу. Область складається з векторів , для яких виконується система з обмежень. Система обмежень дозволяє врахувати не тільки геометричні обмеження (умови неперетинання трас, але і функціональні (впливи міжпровідникових ємностей і ін.).

До загальної постановки задачі КТ зведені особливі задачі канального трасування. Розглянемо задачі HV- і HVH-трасування.

Вважатимемо, що якщо ланцюг призначений на перший шар, то номер магістралі буде додатним: , а якщо на третій шар - то від'ємним: . За цільову функцію виберемо суму інтегральної оцінки відхилення поточних положень ланцюгів від їх цільових магістралей і загальної довжини міжз'єднань. Оскільки довжина горизонтальних провідників фіксована, то й у функції мети слід враховувати лише довжину вертикальних провідників.

(14)

де - номер цільової магістралі для ланцюга ;

константи.

Область визначається системою геометричних (горизонтальних і вертикальних) обмежень:

(15)

де

Оскільки для задачі VHV-трасування вертикальні обмеження відсутні, єдиними обмеженнями є горизонтальні.

Для задачі трасування багатошарового каналу за цільову функцію розглядатимемо сумарну довжину вертикальних з'єднань:

Постановка задачі канального трасування дозволяє вирішувати задачу трасування багатошарового каналу навіть тоді, коли в одному стовпці каналу розташований більш ніж один вивід. Для задачі багатошарової КТ область визначається системою геометричних обмежень, що складається з трьох типів обмежень: горизонтальних, вертикальних і глибинних.

Горизонтальні обмеження:

де - номер шару, на який призначений інтервал - го ланцюга.

де - номер шару, на який призначений -й вертикальний сегмент -го ланцюга.

Глибинні обмеження:

де ; ;

, - номер шару на якому розміщений -й вертикальний сегмент-го ланцюга у каналі (у каналі суміжному з ).

Глибинні обмеження виникають між ланцюгами, виводи яких розташовані в одному стовпці.

Представлена в роботі схема побудови ітераційних методів КТ використовує ідеї методів локальної оптимізації. Процес оптимізації починається з отримання початкового наближення. Складність вибору такого розв'язання визначається наявністю жорсткої системи обмежень задачі КТ. Внесення множини обмежень задачі КТ до функції мети як штрафних функцій дозволяє вибирати початковий розв'язок за межами області припустимих значень. Після перетворення критерію:

(16)

де >>1 - штрафні коефіцієнти, кінцевою метою оптимізації стає отримання оптимального розв'язку, що належить області припустимих .

Оптимізаційна задача з урахуванням перетворення функції мети (16) запишеться у вигляді:

(17)

. (18)

У кожну з множин вводиться по одному елементу, що відповідає непризначенню ланцюга в магістралі каналу. Внаслідок цього вводиться додаткове обмеження, що відповідає неповному розв'язку :

, (19)

а також довизначається критерій відповідної функції штрафів:



(20)

Після цих перетворень за початковий розв'язок може бути обрано вектор, , який відповідає непризначенню всіх ланцюгів схеми.

Раціональний розв'язок задачі (17) - (18) з урахуванням доповнень (19) - (20) виходить внаслідок розв'язання послідовності під задач

(21)

(22)

де - деякий окіл комбінаторного об'єкта.

Процес отримання раціонального розв'язку поділяється на фіксовану r кількість етапів, кожному з яких відповідає певний спосіб формування околу, такий що

. (23)

Оскільки основною метою оптимізації є отримання розв'язку, що знаходиться в області G, то підлягали перетрасовуванню лише ті ланцюги, для яких якість є незадовільною з М обмежень, і ланцюги, що конфліктують з першими. Це дозволило запропонувати спосіб формування околів, що значно зменшує кількість розрахунків. Оскільки на початку оптимізації не задоволені обмеження для всіх ланцюгів, для першого етапу оптимізації вибраний мінімально можливий окіл. Для кожного подальшого етапу кількість ланцюгів з порушеннями обмежень зменшується і, отже, для кожного наступного етапу більшою мірою скорочується кількість розв'язків, які необхідно досліджувати. У роботі запропоновані такі варіанти околів:

; (24)

; (25)

, (26)

де - номери магістралей.

Формальна схема перебору елементів у визначених таким чином підмножинах початкової множини ? призводить до методів перепризначень, що полягають у циклічному вилученні та перепризначенні обраних груп ланцюгів на обрані групи магістралей. Кожна із задач перепризначень розв'язувалася методом мінімального ризику, порівняльна ефективність якого перевірена експериментально для задач різних етапів конструкторського проектування.

Для розв'язання задачі багатошарової КТ (БКТ), на відміну від HV(VHV) - трасування, вертикальні провідники можуть розташовуватися в різних шарах. Через це немає можливості визначити припустимий діапазон магістралей і цільові магістралі для ланцюгів. Запропонований підхід дозволяє ефективно розв'язувати задачу БКТ навіть тоді, коли контактні майданчики розташовані усередині багатошарової структури. У цьому випадку долучаються додаткові "глибинні" обмеження на розташування ланцюгів.

Четвертий розділ присвячений розробці засобів оцінки міжпровідникових ємностей при трасуванні електричних з'єднань, який орієнтований на багатошарову канальну модель МЕП. Ємність між ділянками трас у каналі вважається пропорційною довжині паралельної ділянки для провідників одного шару і площі перекриття проекцій провідників для трас різних шарів. Матрицю погонних ємностей у каналі отримують оберненням матриці потенційних коефіцієнтів. Розрахунок потенційних коефіцієнтів проводиться розв'язанням задачі тривимірного розподілу потенціалу в багатошаровому середовищі методом розділення змінних. У процесі роботи канального методу трасування враховуються обмеження на величину міжпровідникових ємностей.

Розроблені в дисертаційній роботі методи і алгоритми лягли в основу підсистеми канального трасування. Особливістю вказаної підсистеми є адаптованість до різних конструкторсько-технологічних обмежень і, внаслідок цього, можливість застосування в інтегрованих адаптивних САПР МЕП.

Підсистема КТ дозволяє виконувати трасування з'єднань у прямокутних каналах і каналах нерівномірної ширини. Зв'язок підсистеми з іншими програмами комплексу здійснюється на рівні зовнішніх файлів, через які передається інформація про конструкторсько-технологічні вимоги у вигляді послідовності встановлених директив та інформація про конфігурацію комутаційного поля, що відображає розташування каналів.

Підсистема складається з наступних основних програм: ідентифікації директив; перетворення даних у внутрішній формат математичної моделі; обчислення нижніх оцінок ширини каналу; зменшення зони пошуку допустимого розв'язку; ітераційного трасування в каналі; розрахунку взаємних ємностей. В основі програмної реалізації підсистеми лежать принципи структурного програмування - модульність, розділення модулів на ієрархічні рівні, а також метод реалізації програм зверху вниз.

На першому етапі на основі аналізу послідовності директив визначається маршрут проектування. Інформація про кожен канал перетворюється у внутрішній формат даних.

На другому етапі проектування проводяться попередні перетворення: формується модель каналу і система обмежень, обчислюються нижні оцінки ширини каналу.

Наступний етап полягає в застосуванні послідовності вирішальних правил, направлених на обмеження зони пошуку допустимого розв'язку.

На останньому етапі виконується трасування в автоматичному режимі. Перед трасуванням ланцюги ранжируються відповідно до обчислених параметрів на другому етапі. Потім підсистема в автоматичному режимі послідовно підключає для розв'язання поточного завдання методи одиночних, парних і групових перепризначень до тих пір, поки не буде отримано допустимий розв'язок. Якщо допустимий розв'язок не отриманий, то результатом роботи цього етапу може виступати або розв'язок із порушеннями ряду обмежень (для подальшого завершення трасування інтерактивним способом), або неповний розв'язок (для перерозподілу нереалізованих з'єднань в інші області глобальним трасувальником).

Наведені дані про скорочення зони пошуку допустимих розв'язків після застосування правил, описаних у розділі 2. Зменшити зону пошуку допустимого розв'язку вдалося в середньому на 20-25% для задачі HV-трасування і на 30-35% для задачі HVH-трасування.



ВИСНОВКИ

У дисертаційній роботі отримано розв'язок науково-технічної задачі підвищення ефективності систем автоматизації проектування топології мікроелектронних пристроїв шляхом створення ефективних математичних методів, алгоритмів і програмного забезпечення для процедур трасування багатошарових цифрових систем на кристалах з урахуванням завадостійкості, вимог точності, обчислювальних і часових обмежень.

1. У роботі проведений системологічний аналіз проблеми проектування топології мікроелектронних пристроїв, виконана її декомпозиція, встановлено, що більшість задач трасування МЕП мають комбінаторний характер і високу розмірність; складність їх сумісного розв'язку обумовлює ітераційний характер процедур проектування.

2. Як базова для вирішення складних декомпозиційних задач в САПР конструкцій МЕП запропонована і розширена загальна комбінаторна постановка для різних задач конструкторського синтезу МЕП. Такий підхід дає можливість розробляти формальні оптимізаційні процедури, орієнтовані на таку постановку, а потім на їх основі будувати методи розв'язання конкретних задач. Він застосовний для широкого кола задач автоматизованого синтезу проектних і конструкторських рішень і забезпечує вищу, в порівнянні з іншими наближеними методами, точність, має нові функціональні можливості: можливість синтезу множини варіантів декомпозиції, підвищену керованість при синтезі бажаних характеристик із заданими обмеженнями.

3. Модифікована схема ітераційно-послідовного методу комбінаторної оптимізації, орієнтована на запропоновану загальну постановку задачі. Підхід дозволяє об'єднати послідовні та ітераційні методи проектування топології МЕП, методи отримання початкового розв'язку і методи оптимізації початкового розв'язку. Запропонований підхід має істотно меншу часову складність, чим відомі методи, засновані на парних перестановках. Це дозволяє розв'язувати в умовах обмежених обчислювальних і часових ресурсів задачі більшої розмірності.

4. Розроблена система вирішальних правил звуження зони пошуку допустимого розв'язку. Застосування вказаних правил дає можливість не тільки зменшити час розв'язання задачі КТ, але і значно підвищити ефективність використовуваних для розв'язання оптимізаційних процедур.

5. Проведений аналіз задачі багатошарового канального трасування, запропоновані можливі шляхи її розв'язання. На базі ітераційного методу розроблений метод трасування багатошарового каналу, що дозволяє отримувати більш ефективні проектні рішення, з урахуванням завадостійкості.

6. Знайдені умови трасування пленарної схеми в одношаровому каналі і запропонований метод проектування топології одношарового каналу як окремого випадку задачі багатошарового канального трасування.

7. Практичне значення результатів підтверджується їх впровадженням. Результати дисертаційної роботи впроваджені у держбюджетні науково-дослідні роботи, що виконуються згідно з тематичним планом науково-дослідних робіт ХНУРЕ, що фінансуються за рахунок Міністерства освіти і науки, молоді та спорту України; у навчальному процесі на кафедрі проектування і експлуатації електронних апаратів ХНУРЕ; у ГНПП «Об'єднання Комунар» (м. Харків); у ЦККБ «Протон» (м. Харків).

8. Розроблені математичні методи, алгоритми і програмне забезпечення можуть бути використані при розв'язанні практичних задач проектування топології МЕП. Практична значущість отриманих результатів виявляється в скороченні часу проектування, підвищенні якості проектних рішень за рахунок обліку множини різнорідних показників, можливості розв'язку практичних задач більшої розмірності.



СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Семенец, В.В. Анализ структуры задачи проектирования топологии микроэлектронных устройств / В.В. Семенец, В.Г. Иванов // Радиоелектроніка і інформатіка. - 2007. - №3. - С. 113 -118.

2. Семенец, В.В. Алгоритм размещения компонентов печатных плат: зб. наук. праць / В.В. Семенец, С.Н. Ганжа, М.И. Хиль, В.Г. Иванов // Збірник наукових праць Харківського університету Повітряних Сил. - Х.: Харківській університет Повітряних Сил ім. І. Кожедуба, - 2007. - Вип. 3(15). - С. 46 - 48.

3. Семенец, В.В. Об одном подходе к размещению элементов на печатных платах, основанном на понятии «плотности» цепи / В.В. Семенец, С.Н. Ганжа, М.И. Хиль, В.Г. Иванов // Восточно-Европейский журнал передовых технологий. - 2007.- №6/4(30). - С. 40 - 42.

4. Семенец, В.В. К вопросу об анализе структуры задачи проектирования топологии микроэлектронных устройств / В.В. Семенец, В.Г. Иванов // Автоматизированные системы управления и приборы автоматики. - 2007. - Вып. 140 - С. 57-65.

5. Семенец, В.В. Принципы создания методологических основ проектирования САПР / В.В. Семенец, В.Г. Иванов // Прикладная радиоэлектроника. - 2008. - Т. 7, № 2. - C. 139 - 144.

6. Иванов, В.Г. Разработка итерационных алгоритмов канальной трассировки / В.Г. Иванов // Автоматизированные системы управления и приборы автоматики. - 2008. - № 3/3 (33) - С. 29 - 39.

7. Ганжа, С.Н. Учебная САПР технологических процессов поверхностного монтажа РЭА: Матеріали третьої міжнар. наук.- практ. конф. “Розвиток наукових досліджень 2007” / С.Н. Ганжа, А.П. Арушанов, М.И Хиль, С.А. Ганжа, В.Г. Иванов, 26 - 28 листопада 2007 р., м. Полтава. - Полтава: ІнтерГрафіка, 2007. - Т. 6. - С. 25 - 27.

8. Арушанов, А.П. Обеспечение точности установки электронных компонентов на печатные платы в САПР технологических процессов поверхностного монтажа РЭА: Матеріали третьої всеукр. наук.-практ. інтернет-конф. “Україна наукова” / А.П. Арушанов, С.Н. Ганжа, В.Г. Иванов, С.А. Ганжа, 20 - 22 грудня 2007 р., м. Київ.-Київ: ТК Меганом, 2007. - Ч.2. - С. 51 - 52.

9. Ганжа, С.Н. Ранжирование элементов при решении топологических задач размещения на печатных платах: Матеріали четвертої міжнар. наук.-практ. конф. “Розвиток наукових досліджень 2008” / С.Н. Ганжа, О.Д Охрименко, С.А. Ганжа, В.Г. Иванов, 24-26 листопада 2008 р. Полтава. - Полтава: ІнтерГрафіка, 2008. - Т. 6. - С. 19 - 20.

10. Арушанов, А.П. САПР технологических процессов поверхностного монтажа. Расчет объема припоя для микросхем в исполнении BGA: Матеріали третьої всеукраїнської науково-практичної інтернет-конференції “Соціум. Наука. Культура.” / А.П. Арушанов, С.Н. Ганжа, В.Г. Иванов, С.А. Ганжа, 29-31 січня 2008 р., Київ.-Київ: ТК Меганом, 2008. - Ч.2. - С. 63 - 64.



АНОТАЦІЯ

Іванов В.Г. Проектування топології багатошарових цифрових систем на кристалах з урахуванням завадостійкості. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.12 - системи автоматизації проектувальних робіт. - Харківський національний університет радіоелектроніки, Харків, 2011.

У дисертаційній роботі отримано розв'язання важливої науково-технічної задачі підвищення ефективності систем автоматизації проектування топології мікроелектронних пристроїв (МЕП) шляхом створення ефективних математичних методів, алгоритмів і програмного забезпечення для процедур синтезу багатошарових цифрових систем на кристалах з урахуванням вимог завадостійкості, точності, обчислювальних і часових обмежень. Сформульована постановка загальної задачі синтезу топології МЕП, яка об'єднує відомі часткові задачі та враховує різнорідні критерії оптимізації.

Розроблені система правил для задачі проектування топології двошарових та багатошарових каналів, яка дозволяє зменшити область пошуку допустимих розв'язків. Розроблені та вдосконалені методи усіченого перебору варіантів на основі методу переназначень для розв'язання задач синтезу топології багатошарових МЕП, що мають меншу часову складність ніж відомі методи. Визначені умови проектування топології планарної схеми в одношаровому каналі, які дозволяють одержувати більш ефективні розв'язки ніж відомі методи.

Ключові слова: багатошарова цифрова система, кристал, автоматизація проектування, топологія, канальне трасування, оптимізація.



АННОТАЦИЯ

Иванов В.Г. Проектирование топологии многослойных цифровых систем на кристаллах с учетом помехоустойчивости. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 - системы автоматизации проектных работ. - Харьковский национальный университет радиоэлектроники, Харьков, 2011.

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

Проведен системологический анализ проблемы проектирования топологии микроэлектронных устройств, выполнена, ее декомпозиция, установлено, что: большинство задач трассировки микроэлектронных устройств (МЭУ) имеют комбинаторный характер и высокую размерность; сложность их совместного решения обуславливает итерационный характер процедур проектирования.

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

Модифицирована схема итерационно-последовательного метода комбинаторной оптимизации, ориентированная на предложенную общую постановку задачи. Подход позволяет объединить последовательные и итерационные методы проектирования топологии МЭУ, методы получения начального решения и методы оптимизации начального решения. Предложенный подход имеет существенно меньшую временную сложность, чем известные методы, основанные на парных перестановках. Это позволяет решать в условиях ограниченных вычислительных и временных ресурсов задачи большей размерности.

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

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

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

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

Результаты диссертационной работы внедрены: в госбюджетные научно-исследовательские работы, выполняемые согласно тематическому плану научно-исследовательских работ ХНУРЭ, финансируемых за счет Министерства образования и науки, молодежи и спорта Украины; в учебном процессе на кафедре проектирования и эксплуатации электронных аппаратов ХНУРЭ; в ГНПП «Объединение Коммунар» (г. Харьков); в ЦККБ «Протон» (г. Харьков).

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

Ключевые слова: многослойная цифровая система, кристалл, автоматизация проектирования, топология, канальная трассировка, оптимизация.



SUMMARY

Ivanov V.G. Designing of multilayer digital crystal topology with regard to noise immunity. - Manuscript.

The thesis for the degree of Candidate of Engineering Sciences, specialty 05.13.12 - Design Work Automation Systems, Kharkiv National University of Radio Electronics, Kharkiv, 2011.

The important scientific and engineering problem of increasing efficiency of the automation systems for designing microelectronic devices (MED) topology by way of creating the effective mathematical methods, algorithms and software for the procedures of the multilayer digital crystals systems synthesis with regard to noise immunity, precision computational and temporal limitations is solved in the thesis. The general problem of the MED topology synthesis is formulated, it unites the known partial problems and takes into account heterogeneous optimization criteria.

The system of rules for the problem of double-layer and multilayer channels topology designing, which makes it possible to reduce the permissible decisions scope of search, is developed. The methods of truncated versions sorting based on the reassignment method for solving the problems of synthesis of the multilayer topology MED, having less temporal complexity than the available methods, are developed and improved. The conditions for designing the topology of a planar circuit in a single-channel layer, which make it possible to obtain more efficient solutions than the known methods, are developed.

Key words: multilayer digital system, crystal, automation of design, topology, channel tracing, optimization.

Размещено на Allbest.ru

...