Исследование и разработка параллельных алгоритмов трассировки БИС
Диссертация
На основе теоретических исследований предложена методика, позволяющая производить оценки эффективности выполнения алгоритмов проектирования на МВС. Создан ряд алгоритмов этапов трассировки. На их основе разработаны алгоритмы для узловых процессоров процессорного поля МВС, позволяющие организовать вычислительные процессы: одновременного построения, всех связей деревьев, разнесения фрагментов цепей… Читать ещё >
Содержание
- 1. РАЗРАБОТКА АЛГОРИТМА ПОСТРОЕНИЯ ОРТОГОНАЛЬНЫХ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ НА МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ (МВС)
- 1. 1. АНАЛИЗ АЛГОРИТМОВ ПОСТРОЕНИЯ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ И ОЦЕНКА ИХ УСКОРЕНИЯ НА МВС
- 1. 2. АЛГОРИТМ ПАРАЛЛЕЛЬНОГО ПОСТРОЕНИЯ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ
- 1. 3. ОЦЕНКА УСКОРЕНИЯ ВЫПОЛНЕНИЯ РАЗРАБОТАННОГО АЛГОРИТМА ПОСТРОЕНИЯ ДЕРЕВЬЕВ НА МВС
- 1. 4. ВЫВОДЫ
- 2. РАЗРАБОТКА И ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМА ВЫДЕЛЕНИЯ МНОЖЕСТВ НЕПЕРЕСЕКАЮЩИХСЯ ЦЕПЕЙ НА МВС
- 2. 1. АНАЛИЗ АЛГОРИТМОВ ВЫДЕЛЕНИЯ МНОЖЕСТВ НЕПЕРЕСЕКАЮЩИХСЯ ЦЕПЕЙ И ОЦЕНКА ИХ УСКОРЕНИЯ НА МВС
- 2. 2. АЛГОРИТМ РАСПРЕДЕЛЕНИЯ ЦЕПЕЙ ПО СЛОЯМ НА МВС
- 2. 3. ОЦЕНКА ЭФФЕКТИВНОСТИ ВЫДЕЛЕНИЯ КЛИК ГРАФА НА МВС
- 2. 4. ВЫВОДЫ
- 3. РАЗРАБОТКА АЛГОРИТМА ПАРАЛЛЕЛЬНОЙ ТРАССИРОВКИ СОЕДИНЕНИЙ НА МВС
- 3. 1. АНАЛИЗ АЛГОРИТМОВ ТРАССИРОВКИ., СОЕДИНЕНИЙ И ОЦЕНКА ИХ УСКОРЕНИЯ НА МВС
- 3. 2. ПАРАЛЛЕЛЬНАЯ ТРАССИРОВКА СОЕДИНЕНИЙ НА ОСНОВЕ АЛГОРИТМА ПОСТРОЕНИЯ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ НА МВС
- 3. 3. МОДЕЛИРОВАНИЕ РАБОТЫ АЛГОРИТМА ПАРАЛЛЕЛЬНОЙ ТРАССИРОВКИ ДЛЯ МВС НА ПЕРСОНАЛЬНОМ КОМПЬЮТЕРЕ
- 3. 4. ВЫВОДЫ
- 4. РЕАЛИЗАЦИЯ АЛГОРИТМА ПАРАЛЛЕЛЬНОЙ ТРАССИРОВКИ НА МВС СО СТРУКТУРНО-ПРОЦЕДУРНОЙ РЕАЛИЗАЦИЕЙ ВЫЧИСЛЕНИЙ
- 4. 1. СТРУКТУРА И ОБЩИЕ ПРИНЦИПЫ РАБОТЫ МВС
- 4. 2. ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНОГО ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА И
- СИНТЕЗ БАЗОВОГО НАБОРА МАКРООПЕРАЦИЙ ЗАДАЧИ ТРАССИРОВКИ
- 4. 3. ОЦЕНКА ХАРАКТЕРИСТИК ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА ТРАССИРОВКИ
- 4. 4. АППАРАТНО — ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ САПР СБИС
- 4. 5. ВЫВОДЫ
Список литературы
- Будя А.П., Кононюк А. Е., Куценко Г. П. и др. Справочник по САПР / Под общей ред. Скурихина В. И. — К.: Техника, 1988.- 375с.
- Возрастание роли САПР//Comput.Des. 1995 — 34, N2, с. 52.
- Выбор правильной стратегии разработки / Jani Yushvant, Leshem Gabi // Electron. Des. 1996 — 44, N 2, c. 111 — 117.
- Дракин В.И., Попов Э. В., Преображенский А. Б. Общение конечных пользователей с системами обработки данных. М.: Радио и связь, 1988. — 288 с.
- Жук К.Д., Тимченко A.A., Родионов A.A. и др. Построение современных систем автоматизированного проектирования. К.: Наукова думка, 1983. — 248 с.
- Ильин В.Н., Коган В. А. Разработка и применение программ автоматизации схемотехнического проектирования. М.: Радио и связь, 1984. — 368 с.
- Интеллектуальные системы автоматизированного проектирования больших и сверхбольших интегральных микросхем. /В.А. Мищенко, Л. М. Городецкий, Л. И. Гурский и др.- М.: Радио и связь, 1988.-272с.
- Интегрированная САПР высокоуровневого синтеза БИС, адаптирующаяся к библиотеке модулей / Jon Jer Min, Kuang Shiann -Rong//Proc.Nat.Sei.Comic, Rep.China. A.-1995 — 19, N3, c.220 — 234.
- Каляев A.B., Мелихов A.H., Курейчик В.M., Гузик В. Ф., Калашников В. А. Автоматизация проектирования вычислительных структур ИРУ, 1983 г., 224 с.
- Колин Джонсон Р. Средства автоматизации проектирования, практически исключающие прикладное программирование. Электроника, 1982, т.55, N11, с. 129−140.
- П. Курейчик В.М."Калашников В.А., Лебедев Б. К. Автоматизацияпроектирования печатных плат. Ростов, РТУ, 1984, сб.труд.- 80 с.
- Курейчик В.М., Лебедев Б. К., Боли Л. И. Методические указания по использованию в дипломном проектировании системы автоматизированного проектирования двухслойных печатных плат.-Таганрог, РТИ, 1982. сб. трудов 63 с.
- Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР М.: Радио и связь, 1990 г. 352 с.
- Кузьмин Б.А., Эйдес A.A., Игуров Б. С. Адаптируемые системы автоматизированного проектирования печатных плат. М.: Радио и связь, 1984.
- Мурога С. Системное проектирование сверхбольших интегральных схем Т. 1: Пер. с англ. М.: Мир, 1985 г. 288 с.
- Новые САПР передвигают ключевые решения к началу цикла разработки / Dondlin Mike // Gomput. Des. 1996 -34, N 1, с. 31.
- Новый подход к упорядочению перестановки вентилей в одномерных логических матрицах /У IEEE Prog. Circuits, Devices and Syst. 1995 — 142, N 1, с. 90 — 96.
- Норенков M.П., Маничев В. Б. Основы теории и проектирования САПР М.: Высшая школа, 1990 г., 335 с.
- Ньютон А.Р., Санджованни Винчентелли А.Л. Системы автоматизированного проектирования специализированных ш /'/ ТМИЭР, т.75, N 6, 1987 г. с. 30 — 43.
- Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем. М. .-Высшая школа, 1986.-304с.
- Обучающие машины, системы и комплексы. Справочник / Под ред. А. Я. Савельева. К.: Вища школа, 1986. — 303 с.
- Оценка вычислительных ресурсов для реализации схемцифровой обработки сигналов' // IEEE Trans. Comput. Aid.Des.Integr. Circuits and Syst. 1994 — 13, N 6, с. 669 — 683.
- Оценка компактности размещения БИС на основе SQP -алгоритма // Microelectron. J. 1995 — 26, N 4, с. 351 — 359.
- Паркер Э.С., Хайяти С. Использование экспертных систем и кремниевой компиляции для освоения автоматизации процесса проектирования СБИС // ТИИЭР, т. 75, N 6, 1987 г., с. 43 54.
- Петренко А.И., Семенков О. И. Основы построения систем автоматизированного проектирования. К.:Вища школа, 1984. — 296с.
- Петренко А.И., Цурин О. Ф., Киселев Г. Д. Автоматизация проектирования цифровых устройств. К.: Вища школа, 1978. — 152с.
- Петухов Г. А., Смолич Г. Г., Юлин Б. И. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. M.: Радио и связь, 1987.
- Принципы создания универсального сверхпроизводительного супермакронейрокомпьютера с программируемой самоорганизующейся архитектурой и элементами искусственного интеллекта. (Отчет о НИР) /' НИИ МВС при ТРТИ. N ГР 01.9 110 055 147 — Таганрог, 1991 г., кн.З.
- Проектирование СБИС /М. Ватанабэ, К. Асада, К. Кани, Т. Оцуки: Пер. с япон. М.: Мир, 1988 г., 304 с.
- Разработка и исследование архитектуры, принципов построения и элементной базы высокопроизводительного суперпроцессора для решения задач САПР СБИС. (Отчет о НИР) / НИИ МВС при ТРТИ.-N ГР 01.9/10 54 183 Таганрог, 1991 г., 90 с.
- Решение проблемы совместимости средств САПР / KurpisPeter //' Electron. Des. 1996 — 44, N 2, с. 118 — 119.
- Абрайтис Л.Б. Автоматизация проектирования топологии цифровых интегральных микросхем. М.: Радио и связь, 1985 г., 200 с.
- Абрайтис JI. Б., Шейнаускас P.M., Жилевичус В. А. Автоматизация проектирования ЭВМ М.: Сов. радио, 1978 г., 272 с.
- Автоматизированное конструирование монтажных плат РЭА: Справочник специалиста / А. Т. Абрамов, В. Б. Артемов, В. П. Богданов и др.- Под ред. Л. П. Рябова. М.: Радио и связь, 1986. — 192 с.
- Автоматизация конструирования больших интегральных микросхем /A.M. Петренко, П. П. Сыпчук, А. Я. Тетельбаум и др. -Киев: Вища школа, 1983 г., 312 с.
- Автоматизация проектирования БИС. В 6 кн.: Практич. пособие. Кн. 4. Г. Г. Казеннов, В. М. Щемелинии. Топологическое проектирование нерегулярных БИС /Под ред. Г. Г. Казеннова -M.:Высшая школа, 1990 г., 110с.
- Автоматизация проектирования встроенных систем /У GMD -Вег. 1995 N 245, c. I — XII, 1 — 111.
- Анисимов В.И., Дмитрович Г. Д., Скобельцын К. Т. и др. Диалоговые системы схемотехнического проектирования / Под ред. Анисимова В. И. М.: Радио и связь, 1988. — 288 с.
- Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств Львов: Вща школа, 1981 г., 168 с.
- Большаков A.C. Тенденции развития интеллектуальных инструментов САПР //' 48 науч.-техн. конф. С.-Петерб. гос. ун-та телекоммуникаций: тез. докл. СПб, 1995 г., с. 68.
- Методология выбора средств автоматизации электронного проектирования EDA // Electron. Des. 1995 — 43, N 17, с. 81 — 94.
- Мобильная объектно ориентированная параллельная среда САПР СБИС // IEEE Trans. Comput. — Aid. Des. Integr. Circuits and Syst. — 1994 — 13, N 7, с. 829 — 842.
- Морозов K.K., Одшгоков В-Г. > Курейчик В.M. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры М.: Радио и связь, 1983 г., 280 с.
- Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс: Пер. с англ. М.: Радио и связь, 1988. — 128 с.
- Рябов Л.П. Автоматизированное конструирование монтажных плат РЭА. М.: Радио и-связь, 1986.
- Селютин В.А. Автоматизированное проектирование топологии ВМС. М.: Радио и связь, 1983.
- Сорокопуд В.А. Автоматизированное конструирование микроэлектронных блоков с помощью малых ЭВМ. М.: Радио и связь, 1988.
- Системы автоматизированного проектирования в радиоэлектронике: Справочник/ Е. В. Авдеев и др. Под ред. И. П. Норенкова. М.:Радио и связь, 1986. — 368 с.
- САПР электротехнических установок // Autom. Precision 1995 16, N 8 — с. 44.
- Селютин В.А. Автоматизация проектирования топологии БИС -М.: Радио и связь, 1983 г., 112 с.
- Селютин В. А. Машинное конструирование электронных устройств М.: Сов. радио, 1977 г., 384 с.
- Сервисные программы для разработки заказных БИС и ПЛМ //ELRAD 1995 — N 8, с. 56 -61.
- Системы автоматизированного проектирования: Учебное пособие для вузов: В 9 кн. /Под. ред. И. П. Норенкова М.: Высшая школа, 1986 г.
- Средства управления процессом создания проектов БИС /donlln Mike // Comput. Des. 1995 — 34, N 2, с. 44−45.
- Супер-ЭВМ с программируемой архитектурой инейрокомпьютеры. (Отчет о НИР) / НИИ МВС при ТРТИ. N ГР 01.90 036 910 — Таганрог, 1991 г., кн. 3.
- Цикл проектирования сегодня / Adams Steve // Electron. Compon. News 1995 — 39, N 6, с.1ST.
- W.G. Kao and T. M Perug. Gross Point Assignment with. Global Rerouting for Genetal Architecture Designs IEEE Trans. Computer-Aided Design, vol. 14, no. 3, pp.337- 348 (march, 1995).
- S. Papers On Over-the-Gell Channel Routing with Cell Orientetions Consideration, vol.14, no.6, pp. 766−772 (June, 1995).
- B.A. McCoy and Gabriel Robins Non-Tree Routing, vol.6, no.6, pp. 780−784.
- M.K. Dhodhi, P.H. Mielscher, R.M. Storer Datapath Synthesis Using a Problem-Space Genetic Algorithm, vol. 14, no.8, pp. 934−943 (august, 1995).
- Мизин И.А., Махиборода А.В.Концепция самоопределяемых данных и архитектуры распределенных систем.: Информационные технологии и вычислительные системы, 1995, Ш, с.22−31.
- Программирование на параллельных вычислительных системах. Под ред. Бэбб P.II-M.: Мир, 1991, -376с.
- Cray Balances Vector and MPP. Electronics, 1993, v.66, Я15, p.5.
- Каляев B.A., Левин И. И., Фомин С.3D.' Об оценке эффективности решения 'задач математической физики на многопроцессорныхсистемах. // Электронное моделирование, 1989, N6, с.11−15.
- Каляев A.B. Многопроцессорные системы. М.:Наука. -*1987.
- Parallel channel routlng/25th АСМ/ IEEE Des. Autom. Conf., Anahelm -June 12−15,1988: Proc.- New York -1988.-s.128−133.
- КАЛЯЕВ A.B. и др. Супер-ЭВМ на основе процессора ЕС-2703. Перспективы развития. Конструирование алгоритмов и решение задач математической физики. — М.:Наука.-1987.-с. 177−190.
- Тарасенко Л.Г. Реализация языков программирования на ЭВМ архитектуры потоков данных.СуперЭВМ, вып.2,ВЦКП РАН, 1994, с.108−125.
- Landman В. S., Russo R.L. On a Pin Versus Block Relationship for Partitions at Logic Graphs. IEEE Trans., 1971, V. C-20, N12, pp.1469−1479
- ИВАНОВ E.A. Параллельные алгоритмы на графах.-Кибернетика. -I98I.-3.-c.8I-83.
- Теория и методы автоматизации проектирования вычислительных систем: Пер. с англ. /Под ред. Врейера М.: Мир, 1977 г., 285с.
- Шумков Ю.М., Эйдельпапт В. М. Программное обеопичипие автоматизированного проектирования радиоэлектронных схем.- К.: Техника, 1984. 135 с.
- Эвристический подход к исключению неоптимальных проводных связей // Dr. Dobb’s J. 1995 — 20, N 4, с. 28 — 33.
- Энкарначчо Ж., Шлехтендаль Э. Автоматизированное проектирование. Основные понятия и архитектура систем: Пер. с англ. М.: Радио и связь, 1986. — 288 с.
- LOCUS ROUTE. A parallel global router for standart sells. Rose Jonathan U25th ACM/IEEE Des. Autom. Conf. Anaheim, June12.15, 1988.-Proc. New York -1988.-s.189−195.
- WATANABLA TAKUMI, KITARAWA HITOSHI. SUSIYAMA YOSHI. A parallel adapteble routing algorithm and its implementation on a twodimensional array processor. IEEE Trans. Comput. — Aid. Des. Integr. Circuits and Syst. -1987,b ^-s.241−250
- Ш1МЕВ Ю.Т., MJIMEBA Г. М. Алгоритм и программа для параллельной трассировки соединений при топологическом проектировании ИС.- «25 год полупроводниковой промышленности: Юбилейная научно-техническая конференция „- Ботевград.-б.г.- с.107-III.
- КАЛАШНИКОВ В.А., КУРЕЙЧИК В.М. и др. Автоматизация проектирования печатных плат. Ростов н/д., сб. трудов, 1984.
- Файзулаев В.И., Павлычев В. Н., Драбин В. А. Оценка длины связи в логических цепях ЭВМ. Вопросы радиоэлектроники. Сер. ЭВТ, 1982, Вып.16, с.95−100
- Siegel L.J., Siegel H.J., Swain Р.Н. Performance measures for evaluation algorithms for SIMD machines. IEEE Trans. Software Eng., 1982, N4, pp.319−331
- H.N.GABOW. Efficient algorithms for finding minimum spanning and aerected grafs.-Combinatorica.-1986. -p.109−112.
- BALAS EGON. Finding a maximum clique in an abbitrary grath.-SIAM J.Comput.-1 986.-p. 1054−1068.
- DOSHI K., SHITU A. Optimal grath algorithms on a fixed size linear array.-IEEE Trans.Comput.-1087.-p.460−470.
- NAOR JOSEPH. A fast parallel coloring of planar graths with five colors.- Inf. Process Lett.-198?.-p.51−53.
- МЕЛИХОВ A.H. и др. Применение графов для проектирования дискретных устройств.- М: Наука. -1974. •
- ЖТВИНЕНКО В. А. Методы определения семейств клик графа.
- В кн: Методы и программы решения оптимизационных задач на графах и сетях. Часть 2.- Новосибирск.-1982.-с.90−02.
- HEMMERLING ARMIN. Edge coloredgraths In labyrinth theory. Prep. Ems t-More tz. Arndt-Univ. Greif swalci Math. — 198T.
- Добронравов O.E., Цурин О. Ф., Трофимов Б. М. Интерактивная система проектирования гибридных интегральных схем.- М.: Энергоатомиздат, 1985. 120 с.
- Файзулаев Б.М. Средняя длина и трассировочная способность матричных БИС ЭВМ. Микроэлектроника, 1983, т.12, вып.5, с.457−4631. р И Л О Ж Е II И Е
- Акты об использовании результатов диссертационной работы• -V „УТВЕРЖДАЮ“ ji^y'gx^'VV- Директор НИИ МВС
- Д-ЪН. профессор y&H^S^^^Y'^ Божич В .11.
- Настоящим подтверждается, что результаты диссертационной работы сотрудника НИИ МВС С. А. Хованскова „Исследование и разработка параллельных алгоритмов трассировки СБИС“ использованы при выполнении следующих научно-технических работ:
- Разработка и исследование архитектуры, принципов построения и элементной базы • высокопроизводительного универсального суперпроцессора со cTpyicrypHoii организацией вычислений“ N ГР 01.9.10
- При этом использованы следующие конкретные результаты диссертационной работы.
- По теме N ГР 01.9.70 3 041:1. параллельный алгоритм выделения клик графа на МВС-2. теоретические оценки времени работы и эффективности решения задачи выделения на МВС.
- Проведенные исследования позволили обосновать эффективность применения МВС СПРВ в качестве ускорителя решения задач САПР54 183−1. СБИС.
- Завлабораторией 250, к.т.н.
- Зав.отделом 26, д.т.н., профессор1. И.А.Каляев1. И ЛI. Левин
- УТВЕРЖДАЮ» Замдиректора ^"Супер ЭВМ"4 К Т
- Об использовании результатов кандидатской диссертации
- Хованскова Сергея Андреевича «Исследование и разработка параллельных алгоритмов трассировки СБИС» в НИР .
- Проведенные исследования позволили обосновать эффективность применения МВС СПРВ в качестве ускорителя решения задач САПР1. СБИС.1. А К Тоб использовании в учебном процессе результатов диссертационной работы Хованскова С.А.
- Зав.кафедрой КЭО д.т.н., профессор1. Л. А. Болио й1404 .92.