Моделі та алгоритми ієрархічного трасування НВІС з декомпозицією дво- і тривимірного конструктивного простору

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

Національний університет “Львівська політехніка”

УДК 621.3.049.77+004.415+004.896

Моделі та алгоритми ієрархічного трасування НВІС

з декомпозицією дво- і тривимірного конструктивного простору

Спеціальність 05.13.12 - системи автоматизації

проектувальних робіт

Автореферат

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

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

КОРОТЄЄВА ТЕТЯНА ОЛЕКСАНДРІВНА

Львів-2002

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

Робота виконана на кафедрі програмного забезпечення Національного університету “Львівська політехніка”

Науковий керівник: доктор технічних наук, доцент Мельник Роман Андрійович, професор кафедри програмного забезпечення Національного університету “Львівська політехніка”, м.Львів.

Офіційні опоненти: доктор технічних наук, професор Овсяк Володимир Казимирович професор кафедри автоматизації та комп'ютерних технологій Української академії друкарства, м.Львів;

доктор технічних наук, професор Воробель Роман Антонович завідувач відділом „Обчислювальні методи і системи перетворення інформації” фізико-механічного інституту ім. Г.В.Карпенка НАН України, м.Львів

Провідна установа: Харківський національний університет радіоелектроніки, м.Харків.

Захист відбудеться „7” лютого 2003р. о 14.00 годині на засіданні спеціалізованої вченої ради Д35.052.05 в Національному університеті “Львівська політехніка” за адресою 79013, м.Львів, вул.Ст.Бандери, 12.

З дисертацією можна ознайомитись у бібліотеці Національного університету “Львівська політехніка” за адресою 79013, м.Львів, вул.Професорська, 1.

Автореферат розісланий „3” січня 2003 р.

Вчений секретар

спеціалізованої вченої ради

доктор технічних наук Федасюк Д.В.



АНОТАЦІЯ

Коротєєва Т.О. Моделі та алгоритми ієрархічного трасування НВІС з декомпозицією дво- і тривимірного конструктивного простору. - Рукопис.

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

Дисертація присвячена побудові моделей, алгоритмів та стратегій керування ними, що направлені на оптимізацію ієрархічного трасування, як складової задачі проектування топології інтегральних схем надвеликої розмірності з декомпозицією дво- та тривимірного конструктивного простору. Досягнуто підвищення ефективності етапу макротрасування НВІС з дво- та тривимірною топологією за рахунок використання стратегій керування алгоритмами визначення джерела хвилі, декомпозиції простору пошуку рішення, стратегій побудови фрагментів мінімальних зв'язувальних дерев. Це зменшило сумарну довжину ланцюгів схеми на 5-9%, а ширину каналу - на 13-15% в порівнянні з відомими результатами. Вперше введене формальне визначення суміжності ребер в графовій моделі монтажно-комутаційного простору. Розроблена підсистема “ROUTE” трасування ПЛІС в дво- та тривимірному просторі на основі вдосконалених та розроблених моделей, алгоритмів та стратегій керування ними. Інформаційне забезпечення підсистеми включає INTERNET-режим наповнення БД. В підсистемі реалізоване розпаралелене обчислення з використанням глобальної комп'ютерної мережі.

Ключові слова: САПР, топологія НВІС, макротрасування, мікротрасування, декомпозиція, комбінаторні задачі, обчислювальна складність, дискретна оптимізація, розпаралелення обчислень, програмовані логічні інтегральні схеми.



АННОТАЦИЯ

Коротеева Т.А. Модели и алгоритмы иерархической трассировки СБИС с декомпозицией двух- и трехмерного конструктивного пространства. - Рукопись. тривимірний трасування інтегральний топологія

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 - системы автоматизации проектных работ. - Национальный университет “Львовская политехника”, Львов, 2002.

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

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

Исследование результатов применения разработанных моделей, алгоритмов, стратегий оптимизации этапа макротрассировки проведено на примере программируемых логических интегральных схем. Полученные результаты показали уменьшение ширины канала на 13-15%, суммарной длины соединений на 5-9%, времени построения соединений на 33% в сравнении с известными результатами.

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

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

Разработана подсистема “ROUTE” иерархической трассировки ПЛИС в двух- и трёхмерном конструктивном пространстве на основе предложенных моделей, алгоритмов и стратегий усовершенствования методов макротрассировки и назначения. Используются Web-технологии для формирования баз данных.

Ключевые слова: САПР, топология СБИС, макротрассировка, микротрассировка, декомпозиция, комбинаторные задачи, вычислительная сложность, дискретная оптимизация, распараллеливание, программируемые логические интегральные схемы.



SUMMARY

Koroteyeva T.A. Models and algorithms of VLSI hierarchic routing with decomposition two and three-dimensional space. -Manuscript.

Thesis on searching for a candidate`s degree of technical sciences by specialty 05.13.12 - automation design systems. - Lviv Polytechnic National University, Lviv, 2002.

The thesis is dedicated to strategies, models and algorithms to solve a routing problem, as complex designing topology one when integrated circuits in two and three-dimensional space. The methods to increase an efficiency of VLSI macrorouting procedures are investigated and improved. The strategies to define a wave source, decomposition of search space for common results, forming of the chain fragments are realized. The listed strategies had allowed to reduce summary chain length by 5-9 per cent, channel width by 13-15 per cent for some FPGA. By the first time formulas to determinate the edge characteristics needed to form a front wave were used. The system for FPGA routing in two and three-dimensional space is developed. The input information could be supplied from an INTERNET and from the databases. Computer networks could be used do parallel calculations.

Keywords: CAD, topology of VLSI, macrorouting, microrouting, decomposition, combinatorial problems, algorithm complexity, discrete optimization, parallel calculations, FPGA.



Загальна характеристика роботи

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

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

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

Зв'язок з науковими програмами, планами, темами. Дисертаційна робота виконана у руслі наукових досліджень кафедри програмного забезпечення Національного університету “Львівська політехніка”, які проводилися дисертантом в якості виконавця на посаді інженера за період 1989-1994 рр.. В рамках державної цільової програми “Створення і розвиток навчально-дослідницьких САПР та їх підсистем у ВНЗ” виконувались договірні теми: “Декомпозиційне проектування ВІС”(1989р., ДР № 01890062609); “Розробка математичного забезпечення для ієрархічного проектування НВІС”(1990р., ДР № 01880079668). Бюджетні теми виконувались в рамках пріоритетних наукових напрямків Міністерства освіти і науки України: “Теоретичне обгрунтування і розроблення систем автоматизованого проектування ВІС, НВІС та ДП” та “Методи проектування комп'ютерних систем і технологій”, а саме: “Математичне та програмне забезпечення інтелектуальних систем автоматизованого проектування топології великих інтегральних схем”, (1993р., ДР № 01910044924); “Математичне та програмне забезпечення інтелектуальних систем синтезу топології великих інтегральних схем”, (1994р., ДР № 0194U029614).

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

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

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

1. Провести аналіз відомих конструктивно-технологічних проектних рішень сучасних НВІС та методів трасування топології, здійснити аналіз часової складності та розмірності задачі.

2. Синтезувати математичні моделі схем в дво- та тривимірному конструктивному просторі, розробити методику їх кодування.

3. Розробити стратегії підвищення ефективності методів ієрархічного макротрасування з декомпозицією конструктивного простору.

4. Обґрунтувати ефективність розроблених моделей, алгоритмів та стратегій керування ними, реалізувати їх в підсистемі трасування ПЛІС в дво- та тривимірному просторі.

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

Об'єктом дослідження є НВІС, ПЛІС в дво- та тривимірному конструктивному просторі.

Предмет дослідження. Моделі, алгоритми та стратегії проведення з'єднань для НВІС з декомпозицією дво- та тривимірного конструктивного простору.

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

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

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

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

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

4. Досягнуто підвищення ефективності алгоритму ієрархічного макротрасування НВІС дво- та тривимірної топології на основі використання сортування ланцюгів за критерієм насиченості та удосконаленої паралельно-послідовної стратегії побудови ланцюга через декомпозицію області мінімального прямокутника за критерієм насиченості контактами, що зменшило сумарну довжину ланцюгів схеми на 5-9%.

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

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

Практичне значення отриманих результатів. Автором розроблена підсистема “ROUTE” ієрархічного трасування ПЛІС в дво- та тривимірному конструктивному просторі на основі вдосконалених методів, моделей та алгоритмів. Її тестування підтвердило перспективність розроблених підходів трасування та оптимізації. Результати трасування ПЛІС, отримані в роботі, перевищують відомі на 13-15% за показником ширини каналу та на 5-9% за показником сумарної довжини ланцюгів схеми, що в подальшому дозволить зменшити затримку розповсюдження сигналу і геометричні розміри схем.

Підсистема складається з ряду програм та модулів загальним обсягом понад 10000 операторів, написаних на мові програмування Object Paskal для середовища Delphi. Інформаційне забезпечення підсистеми включає INTERNET-режим наповнення баз даних. В підсистемі реалізоване розпаралелене обчислення з використанням глобальної комп'ютерної мережі.

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

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

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались та обговорювались на: Міжнародній науково-практичній конференції “Укрсофт - 94”, м.Львів, 1994; Міжнародній науково-практичній конференції “Укрсофт - 95”, м.Львів, 1995; Міжнародній науково-практичній конференції CAD-SM (Досвід розробки та застосування приладо-технічних САПР в мікроелектроніці). - Львів, 2001; Міжнародній конференції TCSET'2002 (Сучасні проблеми радіоелектроніки, телекомунікації, комп'ютерної інженерії)- Львів, 2002.

Публікації. За темою дисертації опубліковано 13 наукових праць (6 статей у фахових виданнях, 4 депоновані статті, в тезах 3 доповідей ) загальним обсягом 66 сторінок.

Особистий внесок здобувача. Усі результати дисертаційної роботи отримані автором самостійно. У працях, опублікованих у співавторстві, дисертанту належать такі результати: [1] - удосконалення графової моделі ПЛІС з відображенням контактів ланцюгів на ребра графа. [2] - стратегія декомпозиції простору пошуку рішення шляхом введення проміжних точок. [3] - сортування ланцюгів в послідовності на реалізацію за критерієм насиченості; паралельно-послідовна стратегія побудови ланцюга. [4]- стратегії макротрасування ПЛІС в тривимірному просторі. [5] - формальне визначення суміжності ребер в графі; стратегії визначення джерела хвилі з допомогою методу оптимального згортання схеми. [6, 11] - класифікація складових ланцюга, дослідження впливу вагових функцій на призначення фрагментів трас. [7] - порівняльний аналіз результатів макротрасування ПЛІС за алгоритмом „Траса” з результатами зарубіжних дослідників. [8] - дослідження результатів застосування методу оптимального згортання схем при побудові мінімальних зв'язувальних дерев. [9] - розробка програмного, інформаційного та лінгвістичного забезпечення підсистеми макротрасування НВІС. [10] - аналіз моделей ДТРП та стратегій поширення хвилі. [12, 13] - дослідження стратегій визначення координат закріплення вертикальних складових в каналах.

Структура дисертації. Дисертація складається із вступу, п'яти розділів, висновків, списку використаних джерел, додатків. Повний обсяг дисертації становить 174 сторінки, серед них 153 сторінки основного тексту, 72 рисунка, 22 таблиці та 112 найменувань використаних літературних джерел (на 11 сторінках).

ОСНОВНИЙ Зміст роботи

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

Перший розділ присвячено огляду літературних джерел з області наукових досліджень методів трасування інтегральних схем та особливостям побудови САПР топології НВІС.

В другому розділі розглядається задача макротрасування схем в двовимірному просторі. Досліджені і розвинуті алгоритми та стратегії керування ними для її розв'язування. Моделлю монтажно-комутаційного простору (МКП) вибирається дискретне топологічне робоче поле (ДТРП) (рис.1а). Множини ребер дискретів, які розміщені в горизонтальному напрямку відповідають горизонтальним каналам МКП, а множини вертикальних ребер дискретів - вертикальним каналам МКП. Місця перетину вертикальних і горизонтальних каналів МКП схеми відображаються на точки перетину вертикальних і горизонтальних ребер, назвемо їх вузлами ДТРП і позначимо WU. На рис.1.а прикладами вузлів є точки з номерами 5, 6 і 7. Границя МКП відображається на границю ДТРП. Точки перетину ребер дискретів з границею ДТРП назвемо граничними точками і позначимо GT. На рис. 1.а прикладами граничних точок є точки з номерами 1,2,3,4 і 8.

Графо-топологічною моделлю ДТРП визначимо зважений за ребрами граф G(V, R), вершини V якого відображають множину WU вузлів ДТРП та множину GT граничних точок: V=WU GT. Якщо два вузла ДТРП або вузол і гранична точка є суміжні, то в графі існує ребро r_ij є R, яке з'єднує відповідні вершини v_i та v_j. Вага ребра l (r_ij) графа відповідає пропускній здатності ребра дискрета. З'єднання E={e₁, e₂, .., e_s}, які потрібно побудувати на МКП, задаються сімейством множин контактів елементів схеми X={ X(e₁), X(e₂), .., X(e_s)}, де s-кількість ланцюгів в схемі.

Традиційно при переході до графової моделі ДТРП з'єднання E представляються сімейством множин вершин графа V*={V*(e₁),V*(e₂),..,V*(e_s)}, які необхідно з'єднати. Пропонуємо інший підхід. Будемо представляти з'єднання Е сімейством множин ребер R*={R*(e₁), R*(e₂),…,R*(e_s)}. Попередньо встановлюємо відповідність: контакт x(e_і) елемента схеми - фрагмент каналу МКП, на який цей контакт має направлений вивід - відповідне ребро r*R графа G. Це дозволяє частково вирішити задачу мікротрасування, зафіксувавши з якої сторони буде підходити ланцюг до елемента схеми. Достатньою інформацією для побудови з'єднань є інформація про ребра графа (їх суміжність та вага). В традиційному представленні контактів вершинами графа необхідно зберігати інформацію про суміжність вершин для поширення хвилі та інформацію про завантаженість ребер. Ребро в графі G має максимально шість суміжних ребер, а вершина - чотири суміжні вершини. Збільшення числа суміжних сусідів надає більшу можливість формування варіантів зв'язків між елементами для реалізації ланцюгів схеми. Макротрасування з'єднань здійснюється незалежною побудовою мінімальних зв'язувальних дерев (МЗД) для всіх ланцюгів інтегральної схеми. Тоді математичне формулювання задачі макротрасування полягає в наступному: для множини ребер R* на графі G(V,R) необхідно побудувати ліс мінімальних зв'язувальних дерев:



T = { T*_1,...,T*_i ,...T*_S }

де T*_і- МЗД, що відповідає і-му ланцюгу, s - кількість ланцюгів в схемі.

Основними критеріями якості як трасування в цілому так і етапу макротрасування є 100-% реалізація з'єднань схеми та мінімізація сумарної довжини з'єднань. При реалізації одного ланцюга необхідно розв'язати багатокритеріальну дискретну оптимізаційну задачу: для заданої множини ребер R*(e_i) знайти в графі G(V, R) дерево T*_i ( V_і**, R_і**), де V_і** V, R*(e_i) R_і** R, критеріями якості якого є такі функції:

L(T*_i ) = L(T*_{i j} ), K(T*_i ) = K(T*_{i j} ),

LF(T*_i ) =LF(T*_{i j} ), PZR(T*_i) =PZR(T*_{i j} )

де L(T*_i ) - довжина, K(T*_i ) - кількість поворотів, LF(T*_i ) - довжина максимального фрагмента “джерело-контакт”, PZR(T*_i) - вага ребер для дерева T*_i , відповідно L(T*_{i j} ), K(T*_{i j}), LF(T*_{i j} ), PZR(T*_{i j} ) для дерева T*_{i j}, j- варіанти формування дерева T*_i, jN множині натуральних чисел.

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

Як обмеження розглядаються ваги ребер графа. Якщо до початку побудови дерева l (r_ij) = 0, то це означає, що ребро не можна використовувати при побудові дерева. Відповідний фрагмент каналу МКП є заблокованим технологічно.

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

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

Стратегія “Довільний контакт”: за джерело хвилі приймається перший контакт з послідовності контактів ланцюга.

Стратегія “Найближчий до геометричного центру”: якщо контакти рівномірно розташовані в області мінімального прямокутника, то контакт, який знаходиться найближче до геометричного центру прямокутника, визначається як джерело.

Стратегія “Від групи контактів”: якщо контакти нерівномірно розташовані в області мінімального прямокутника, то визначається група контактів, розташованих більш насичено. Серед цієї групи джерело визначається за стратегією “Найближчий до геометричного центру”.

Стратегія “Між групами контактів”: якщо таких груп є більше ніж одна, тоді в межах кожної групи проводять з'єднання, а потім групи з'єднують між собою.

Для визначення груп контактів використовується метод оптимального згортання схеми та розроблений на його основі алгоритм формування n-арного дерева згортання. На кожному рівні об'єднуються всі вершини, які увійшли в пари з найкращим значенням критеріальної функції F_kj для даного рівня, яка визначається як відстань між двома контактами k та j за їх координатами (x_k ,y_k), (x_j ,y_j) :

F_kj=( |x_k-x_j|² + | y_k-y_j|²) .



Під час формування n-арного дерева згортання кожній новоутвореній вершині ставиться у відповідність число, яке назвемо вагою вершини:

м(v_i) = і : K_Lvi ,

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

Одним з недоліків хвильових алгоритмів є значні ресурси пам'яті, необхідні для зберігання інформації про фронт хвилі та пріоритетні напрямки. Для зменшення цього показника розглядаються та аналізуються ряд моделей декомпозиції області розповсюдження хвилі, які дозволяють, залишаючись в межах найкращого рішення, скоротити час пошуку шляху та зменшити обсяг інформації, необхідний для його формування: 1) модель у вигляді прямокутних трикутників; 2) модель у вигляді смуги; 3) модель з введенням проміжних точок. Декомпозиція простору з використанням проміжних точок зменшила час побудови з'єднань в середньому на 33% (для окремих тестів цей показник досягав 66%).

Для зменшення обсягу даних, які необхідно зберігати під час побудови МЗД та зменшення загальної довжини ланцюгів, МЗД будується фрагментами. На першому кроці будується фрагмент між джерелом і найближчим до нього контактом. На подальших кроках для побудови фрагментів МЗД застосовуються такі стратегії: 1. Від джерела до найближчих контактів. 2. Від побудованого фрагмента МЗД до найближчого контакту. 3. Декомпозиція n-арного ланцюга на бінарні фрагменти за критерієм мінімальної відстані між контактами. 4. Декомпозиція області мінімального прямокутника для n-арного ланцюга за критерієм насиченості контактами.

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

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

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

Q(T)= N Ч logM + n²

де N, M - розмір входу, відповідає кількості рядків і стовпців елементів в схемі, n - кількість контактів в ланцюгу. Дослідження ефективності алгоритму “Траса” проведено на прикладі трасування ПЛІС. Контрольними тестами вибрані 13 промислових схем, які розроблені в університеті міста Торонто (Канада). Проведено порівняльний аналіз з результатами макротрасування за іншими алгоритмами.

Тестування кожної схеми проводилось біля 30 разів. В загальному проведено біля 400 пусків виконавчого модуля. Отримані результати показують зменшення ширини каналу на 13-15%, сумарної довжини ланцюгів на 5-9%.

Третій розділ присвячено застосуванню розроблених у другому розділі моделей, алгоритмів та стратегій керування ними для підвищення ефективності методів макротрасування в тривимірному конструктивному просторі. Моделлю МКП інтегральних схем з багаторівневим розміщенням елементів є ДТРП в межах паралелограма. Дискрети мають форму паралелограма і відображають елементи схеми та міжрівневі переходи. Математичною моделлю такого ДТРП обираємо граф G(V,R). Множина вершин V графа G відображає множину WU вузлів ДТРП та множину GT граничних точок в межах паралелограма: V=WU GT. Множина ребер R, на відміну від двовимірного варіанту, складається з двох підмножин: R = R_р R_мр - об'єднання множини ребер R_р, що відповідають фрагментам областей (каналів) з'єднань між двома вузлами (або вузлом і граничною точкою) в межах рівня і множини ребер R_мр, що відповідають міжрівневим переходам.

Задача трасування одного ланцюга ІС в тривимірному просторі формулюється аналогічно з двовимірним варіантом. При побудові дерев на графі в тривимірному просторі використовуються ті ж міркування, що і для двовимірного варіанта.

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

При побудові МЗД застосовуємо хвильові процеси. Процес поширення хвилі базується на суміжності ребер в графі. Традиційно для цього використовувались матриці суміжностей ребер. Для зменшення обсягу даних, що зберігаються під час побудови дерев та прискорення процесу поширення хвилі пропонується формальне визначення суміжності ребер в графовій моделі при формуванні фронту хвилі. Цей підхід є ефективним у випадку регулярного (рівномірного або нерівномірного) розміщення елементів схеми як в дво-, так і в тривимірному просторі. Необхідною інформацією є кількість рядків N та стовпчиків M елементів в схемі та номер ребра. Біжуче ребро Р характеризується трьома координатами X_P, Y_P, Z_P. Суміжні ребра для ребра P обчислюються за формулами:

e = MЧ (N-1) + (Y_P -1)ЧN + X_P +1 + KRRЧZ_P

h = e +1

f = e + N

g = f + 1

a = (N-1)ЧM +NЧ(M-1) + KRRЧZ_P + (Y_P -1)Ч(N-1) + X_P +1 (2)

b = a - KRR

c = a + M

d = c - KRR,

де KRR = ((N-1)ЧM+NЧ(M-1)+(N-1)Ч(M-1)). Номери ще двох суміжних ребер дорівнюють p -1 та p+1.

Переваги формул (2) над матрицею суміжностей граней (ребер) очевидні: 1. Використання формул тільки за потребою для тих ребер, які входять у фронт хвилі. 2. Схема великих розмірів вимагає описувати її матрицею відповідних розмірів. Ця інформація не змінюється на протязі всього процесу побудови ланцюгів і вимагає значних об`ємів оперативної пам`яті на противагу обчислень за формулами. 3. Операція пошуку елемента матриці по часу є довшою ніж математичні операції, які використовуються у наведених вище формулах.

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

Проведено порівняльний аналіз результатів макротрасування ПЛІС в дво- та тривимірному просторі за алгоритмом “Траса” (таблиця 2). Для тривимірного варіанта розглядалось розміщення логічних блоків на чотирьох рівнях (KR=4). Ширина каналу для тривимірного варіанту (поле “Wxyz ”Траса”“) зменшилась в порівнянні з двовимірним (поле “Wxy ”Траса”“) в середньому на 16.2% (поле “%W”), а значення сумарної довжини ланцюгів (поля “Dxy ”Траса”“ та “Dxyz ”Траса”“) в середньому зменшилось на 11.6% (поле “%D”). В таблиці також неведені значення ширини каналу та сумарної довжини ланцюгів деяких схем для тривимірного варіанту, отримані за алгоритмом “IKMB”(поля “Wxyz ”IKMB” та “Dxyz ”IKMB”). Порівняльний аналіз отриманих результатів підтверджує високу ефективність розробленого алгоритму ”Траса”.

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

Для розв'язування задачі багаторівневого призначення використовується метод оптимального призначення фрагментів трас на магістралі каналів. Вводимо множину ресурсів (відрізків магістралей між горизонтальними каналами в межах вертикального каналу):



R = {R₁, R₂,..., R_n}

де R_i = {r_ii+1,r_ii+2,...,r_iq} - підмножина відрізків з і-го каналу до і+1, і+2,..., q каналів; n - кількість каналів. Вводимо подібну множину вертикальних фрагментів дерев:

E = {E₁, E₂,.., E_n}

де E_i= {e_ii+1, e_ii+2,..., е_it}.

Розв'язати задачу призначення - це знайти відображення ER таким чином, щоб при закріпленні ресурсу r_iq R за елементом e_it E:

1) мінімізувати загальну кількість переходів k_i з однієї магістралі на іншу.

F₁^*=k_i, (3)

де і-кількість варіантів відображення;

2) мінімізувати довжину _i незадіяних ресурсів при відображені фрагментів відрізками більшої ніж потрібно довжини.

F₂^*=_i, (4)

3) мінімізувати заплановану довжину горизонтальних фрагментів, необхідних для реалізації переходів між вертикальними складовими.

F₃^*= S_i =d_ij, (5)



де - S_i сума відстаней d_ij між відрізками, які відображають один вертикальний фрагмент.

Одним з можливих підходів до розв'язування поставленої задачі є послідовний перебір реалізацій і вибір оптимальної відносно поставлених функцій мети методом поступок. В роботі розроблено алгоритм БРП багаторівневого призначення фрагментів ланцюгів з врахуванням їх сортування за значенням вагових функцій в межах одного вертикального каналу. Проводиться реалізація алгоритму БРП на етапі мікротрасування ПЛІС. При цьому розглядається ряд стратегій керування алгоритмом призначення, а саме: 1) послідовна для кожного сформованого ланцюга в тому порядку, згідно якого він формувався на етапі макротрасування; 2) послідовна для кожного сформованого ланцюга з початковим призначенням вертикальних або горизонтальних складових; 3) паралельно-послідовна з одночасним закріпленням всіх магістралей каналу за фрагментами ланцюгів, які проходять через даний канал.

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

У п'ятому розділі розглянуті архітектура та принципи взаємодії модулів в розробленій підсистемі “ROUTE” ієрархічного трасування ПЛІС в дво- та тривимірному конструктивному просторі.

Підсистема “ROUTE“ написана на мові програмування Object Paskal для об'єктно-орієнтованого середовища DELPHI і складається близько з 10000 стрічок вихідного тексту. Виконавчий модуль трасування займає 316 Кбайт оперативної пам'яті.

Основними класами, якими оперують модулі підсистеми, визначені: „Контакт”, „Фрагмент”, „Траса”, „Магістраль”, „Канал”, „Рівень” дані яких відображають координати їх розташування, а методи служать для визначення характеристик довжини, пропускної здатності, завантаженості, їх графічного зображення. Класи об'єднані в загальному класі „Трасування”, методи якого розв'язують задачі макротрасування та призначення фрагментів дерев на магістралі каналів.

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

У додатках наведені графічні приклади результатів трасування ПЛІС та акти впровадження.



ВИСНОВКИ

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

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

2. Розвинуті та досліджені стратегії підвищення ефективності методів макротрасування інтегральних схем з декомпозицією дво- та тривимірного простору. Проаналізовані та обґрунтовані стратегії керування алгоритмами визначення джерела хвилі при побудові МЗД.

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

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

5. Проведено дослідження отриманих результатів макротрасування програмованих логічних інтегральних схем при використанні розроблених моделей, стратегій та алгоритмів. Зроблено порівняльний аналіз з результатами макротрасування за іншими алгоритмами. Отримані результати показали зменшення ширини каналу на 13-15% , сумарної довжини провідників на 5-9%.

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

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

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

9. Розроблена підсистема “ROUTE” ієрархічного трасування ПЛІС в дво- та тривимірному просторі на основі розроблених моделей, алгоритмів та стратегій оптимізації макротрасування та призначення. Представлена структура модулів підсистеми та принципи їх спільного функціонування. Використані Web-технології для формування бази даних. Результати роботи впроваджені у навчальний та виробничий процес.



ОПУБЛІКОВАНі праці нА ТЕМу ДИСЕРТАЦІЇ

Мельник Р.А., Коротєєва Т.О. Стратегії та алгоритми макротрасування ПЛМ// Вісник НУЛП “Комп'ютерні системи проектування. Теорія і практика” .- Львів, 2000.- № 398.-С. 129-133.

Мельник Р.А., Коротєєва Т.О. Експериментальне дослідження комплексу макротрасування програмованих матриць // Вісник НУЛП “Комп'ютерна інженерія та інформаційні технології”.- Львів, 2000.- №413. -С.3-7.

Мельник Р.А., Коротєєва Т.О. Керування якістю макротрасування програмованих логічних матриць // Вісник НУЛП “Комп'ютерні системи проектування. Теорія і практика”.- Львів, 2001.- № 415. -C.157-160.

Мельник Р.А., Коротєєва Т.О. Макротрасування в об'ємних моделях ПЛМ // Вісник НУЛП “Комп'ютерна інженерія та інформаційні технології”.-Львів, 2001.- № 433. -С. 68-72.

Мельник Р.А., Коротєєва Т.О. Моделі простору для макротрасування тривимірних програмованих логічних матриць // Вісник НУЛП “Радіоелектроніка та телекомунікація “.- Львів, 2002.- №.440 -С.118-122.

Мельник Р.А., Коротєєва Т.О. Призначення ланцюгів на контакти каналу при трасуванні інтегральних схем // Вісник ДУЛП “Комп'ютерна інженерія та інформаційні технології”. - Львів, 1995.- № 294. -С.82-86.

Melnyk R., Koroteyeva T. A performance-oriented routing tools for field-programmable gate arrays // Proceedings of the Sixth International Conference CADSM' 2001 (The Experience of Designing and Application of CAD Systems in Microelectronics). -Lviv-Slavsko, Ukraine, 2001. -P. 243-244.

Melnyk R., Koroteyeva T. Space models for three dimensional FPGA global routing // Proceedings of the International Conference TCSET'2002 (Modern problems of radio engineering, telecommunications and computer science ).-Lviv-Slavsko, Ukraine, 2002.-P. 374-375.

Мельник Р.А., Коротєєва Т.О. Експериментальний комплекс програм трасування // Тези міжнародної конференції “Україномовне програмне забезпечення.”. - Львів, Україна.- 1995.- С. 28-29.

Мельник Р.А., Коротеева Т.А. Волновые процессы в макротрассировке / Львов:ЛПИ, 1992. -8 с. -Рус.- Деп. в УкрИНТИ, №1321-Ук 92.

Мельник Р.А., Коротеева Т.А. Назначение цепей на магистрали вертикальных каналов / Львов :ЛПИ, 1992.-6 с.-Рус.- Деп. в УкрИНТИ, № 1317-Ук92.

Мельник Р.А., Коротєєва Т.О. Призначення кінцевих координат закріплених відрізків в чотиристоронньому каналі / Львів:ДУЛП, 1995 - 8 с. -Деп. в ДНТБ, №1169-Ук95.

Мельник Р.А., Коротєєва Т.О. Алгоритми призначення кінцевих координат закріплення відрізків в чотиристоронньому каналі / Львів:ДУЛП,1995.-9 с.- Деп. в ДНТБ, №1494- Ук95.

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

...