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

ВВЕДЕНИЕ

1 АНАЛИЗ И ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ И МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ПРИ ПРОЕКТИРОВАНИИ ЭВА НА ОСНОВЕ СБИС

1.1 РАЗВИТИЕ ПОЛУ ЗАКАЗНЫХ МАТРИЧНЫХ СБИС

1.2 ИЕРАРХИЧЕСКИЙ ПОДХОД К ПРОЕКТИРОВАНИЮ ЭВ А

1.3 ЭТАПЫ ПРОЕКТИРОВАНИЯ ЭВ А

1.4 АНАЛИЗ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СХЕМ ДЛЯ ЗАДАЧИ РАЗМЕЩЕНИЯ

1.5 КЛАССИФИКАЦИЯ КРИТЕРИЕВ ЗАДАЧИ РАЗМЕЩЕНИЯ

1.6 АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ

1.6.1 КЛАССИФИКАЦИЯ ТРАДИЦИОННЫХ МЕТОДОВ РАЗМЕЩЕНИЯ

1.6.2 МЕТОД ИМИТАЦИИ ОТЖИГА

1.6.3 МЕТОД ИМИТАЦРШ ЭВОЛЮЦИИ

1.6.4 АНАЛИЗ ДОСТОИНСТВ И НЕДОСТАТКОВ МЕТОДОВ РАЗМЕЩЕНИЯ

При создании современной электронной аппаратуры огромное значение приобретают эффективные методы автоматизированного проектирования, которые позволяют создавать высоконадёжные СБИС в короткие сроки и при сравнительно низких затратах. Стоимость кристаллов СБИС складывается из стоимости проектирования (постоянные затраты) и стоимости производства (переменные затраты). Тенденция к росту степени интеграции СБИС приводит к существенному увеличению трудоёмкости проектирования, что вызывается ростом размерности решаемых при проектировании задач [1, 30, 60, 63].

Производство интегральных схем разбивается на три этапа: проектирование, изготовление, тестирование. В виду значительной сложности ни один из этих этапов не может быть выполнен без средств автоматизированного проектирования. Одним из этапов проектирования СБИС является этап конструкторского проектирования, который включает в себя следующие стадии: компоновка, размещение, трассировка [30, 33, 60, 63].

Разработка методов и алгоритмов для решения задачи размещения осуществляется на протяжении ряда лет, являясь, по-прежнему, актуальной. Это связано, в первую очередь, с тем, что эта задача является ИР-полной, и, как следствие, затруднительна разработка универсального алгоритма, позволяющего находить точное оптимальное решение за приемлемое время. Появление новых, более совершенных средств производства электронной техники, и, как следствие, увеличение степени интеграции цифровых и аналоговых микросхем является побудительной причиной для разработки новых алгоритмов решения задачи размещения. Очень большое значение при разработке новых методов имеет использование методов оптимизации. Существует несколько подходов к решению ЫР - полных задач [1, 9, 33, 34].

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

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

Одним из методов случайно-направленного поиска является метод генетического поиска. В 1975 году американский исследователь Дж. Холланд [32] описал методологию изучения адаптивных систем и их применения для искусственных систем, а также разработал подходы к решению комбинаторно-оптимизационных задач. Идеи Холланда и его учеников оказались плодотворными и эффективными. Сейчас генетические алгоритмы (ГА) хорошо известная и эффективная технология оптимизации, применяемая для различных задач техники, моделирующая естественный процесс эволюции в качестве средства достижения оптимума и основанная на имитации процессов натуральной селекции и генетических преобразований [11].

Достоинства ГА, в сравнении с другими подходами к решению задач комбинаторной оптимизации, заключаются в том, что они начинают работать с несколькими начальными решениями, распараллеливая процесс, и позволяют избежать попадания в локальные оптимумы, при этом комбинируя и наследуя элементы наиболее качественных решений [31, 43, 117].

Другой метод случайно-направленного поиска - метод имитации отжига. В 1953 году Метрополис [11] сделал попытку применить идею процесса отжига, заимствованную из физики, к проблемам численных методов на основе имитационного моделирования. В 1983 году Кирпатрик использовал эту идею для решения комбинаторно-оптимизационных задач. С тех пор этот метод широко используется при решении технических задач, проводятся исследования и разработки его модификаций [102]. Алгоритм имитации отжига обладает высокой способностью выходить из локальных ям и сходиться к глобальному минимуму, но при этом имеет один недостаток: большая временная сложность. Алгоритм генетического поиска обладает иными качествами: быстрой сходимостью, простотой реализации и иногда может сходиться к локальному оптимуму [102].

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

Ввиду вышеизложенного, разработка алгоритмов, позволяющих найти приемлемое по качеству и по трудоёмкости решение задачи размещения блоков о

ЭВА, является АКТУАЛЬНОЙ ПРОБЛЕМОЙ, стоящей перед разработчиками САПР.

ЦЕЛЬЮ диссертационной работы является разработка параллельного генетического алгоритма для решения задачи размещения блоков ЭВА, используя ресурсы заданной локальной компьютерной сети.

Для достижения поставленной задачи было сделано следующее:

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

2) разработан генетический механизм распределения блоков ЭВА по макрообластям на основе матрицы связности графа с целью уменьшения объёма обрабатываемой информации;

3) предложен метод распараллеливания процесса решения между узлами локальной вычислительной сети;

4) реализован генетический алгоритм получения решения в блочном виде на основе анализа коэффициента связности кластеров;

5) построен механизм обмена решениями-эмигрантами между различными узлами сети на этапе макроэволюции;

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

МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на использовании элементов теории множеств, теории графов, теории алгоритмов, теории комбинаторной оптимизации, элементов теории статистических вычислений.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем: а) разработан механизм альтернативного покрытия с возможностью задания различных вариантов ориентации и размеров кластеров; б) определена процедура заполнения поля кластера элементами, позволяющая концентрировать линии связи внутри кластера в) построена схема распараллеливания процесса размещения между узлами локальной вычислительной сети; г) использован этап макроэволюции для объединения решений различных узлов сети и нахождения глобального оптимума; д) получена вероятностная оценка поведения целевой функции в зависимости от размера популяции.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

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

- алгоритм и программа последовательного размещения элементов на поле отдельного кластера;

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе, проводимой Таганрогским НИИ связи по теме «Разработка автоматизированных рабочих мест оператора». В Таганрогском Радиотехническом Университете использованы при выполнении г/б НИР № 12352д в 2000 г. и гранта Минобразования № 12390 в 2001 г. механизм распределённого между несколькими вычислителями поиска решения задачи трассировки; при выполнении г/б НИР № 06.01.018 и грантов РФФИ №№ 0001-00125,01-01-00044 применена методика выбора размера популяции. Предложенные структуры генетических операторов использованы при выполнении работ по гранту РФФИ № 99-01-0050. При выполнении г/б НИР № 12353 (№ 1.04.01) учтены практические исследования вероятностного поведения целевой функции. Материалы диссертации также использованы в учебном процессе на кафедре САПР ТРТУ в цикле практических занятий по курсу «Математическое моделирование».

АПРОБАЦИЯ основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на научных семинарах ТНИИС (1998-2001 г.), на Всероссийской научно-технической конференциях студентов и аспирантов «Новые информационные технологии. Информационное, программное и аппаратное обеспечение» (г. Таганрог,

1999 г.), на международной научно-технической конференции «Интеллектуальные САПР» (г. Дивноморск, 1999 г.), на Всероссийской научно-технической конференциях студентов и аспирантов конференции «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог,

2000 г.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 10-ти печатных работах. Отчёты зарегистрированы.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 159 стр., а также 19 рис., список литературы из 136 наименования, 19 стр. приложений и актов об использовании.

4.7. ВЫВОДЫ И РЕКОМЕНДАЦИИ

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

2. Произведены экспериментальные исследования поведения целевой функции в зависимости от размера популяции. Определён оптимальный размер популяции, равный 10 п, где п - число размещаемых блоков ЭВА. Данный размер популяции обеспечивает быстрое достижение целевой функцией значения, близкого к оптимальному, но в то же время не приводит к зацикливанию алгоритма.

3. Произведены экспериментальные исследования для определения оптимального уровня миграции. Сделан вывод об оптимальном размере миграции, равном (6,5 - 7) % от размера популяции.

4. Произведена оценка временной сложности разработанного параллельного алгоритма размещения элементов СБИС. Получена полиномиальная зависимость третьей степени.

5. Определена эффективность параллельного алгоритма в сравнении с таким же числом независимых процессов размещения. Положительный эффект составляет повышение значения целевой функции на (15 - 20) %.

ЗАКЛЮЧЕНИЕ

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

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

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

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

5. Разработан алгоритм параллельного генетического размещения элементов, основанный на применении понятия миграции особей. Определён оптимальный размер миграции, равный 6,5 - 7 % от размера популяции.

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

7. Произведены экспериментальные исследования для определения оптимального размера популяции. Рекомендованный размер популяции позволяет гарантированно достигать 35% окрестности оптимума целевой функции.

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

1. Автоматизация проектирования БИС. Петренко А.И., СынчукП.П., Тетельбаум А.Я. и др. - Киев: Виша школа, 1983.

2. Автоматизированное проектирование СБИС на базовых кристаллах. Петренко А.И., Лошаков В.М., Тетельбаум А.Я. и др. М: Радио и связь, 1988.

3. Адлер Ю.П. Введение в планирование эксперимента. М.: Металлургия, 1969.

4. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж: ВГТУ, 1995.

5. Берштейн Л.С., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных интеллектуальных системах. Ростов н/Д.: Издательство РГУ, 1999.

6. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. М: Наука, 1986.

7. Быстродействующие матричные БИС и СБИС. Теория и проектирование. Под общей редакцией Файзулаева Б.Н. и Шагурина И.П. М.: Радио и связь, 1989.

8. Васюков А.Н., Комаров Ю.А., Янович И.А. Логико-алгебраические методы решения геометрических задач и разработка программного обеспечения САПР. Киев: Нукова думка, 1991.

9. Ведерникова О.Г. Разработка и исследование комбинированного генетического алгоритма генетического поиска и имитации отжига для задачи размещения элементов СБИС: Дис. к.т.н. Ростов н/Д РГА сельхозмашиностроения, 1999.

10. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ. Пер. с англ. / Под ред. КоваликаЯ. М., Радио и связь, 1990.

11. Генетическая оптимизация нейронных сетей. Терехов С.А., Воленко Е.В., Квичанский A.B., Щукин Н.В. Снежинск.: Изд-во РФЯЦ-ВНИИ ТФ, 2000.

12. Гренандер У. Случайные процессы и статистические выводы Пер. с англ. и доп. Яглоба А.М. М.: Изд.-во иностранной литературы, 1961.

13. Гурский Л.И. и Степанец В.Я. Проектирование микросхем. М.: Радио и связь, 1986.

14. ГэриМ., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

15. Девис У. Операционные системы. М.: Мир, 1990.

16. ЕргинА.А. Применение генетического алгоритма для настройки нейронных сетей. // Радиоэлектроника, электротехника и энергетика. Седьмая Междунар. науч.-техн. конф. студентов и аспирантов: Тез. докл. В 3-х т. М.: Издательство МЭИ, 2001. Т.1.-стр. 253.

17. Зайченко Ю.П. Исследование операций. Киев.: Вища школа, 1975.

18. Зинченко JI.А. Алгоритмы численно-аналитического моделирования и средства программной поддержки САПР электронных устройств. -Таганрог: Изд-во ТРТУ, 1999.

19. Интегральные микросхемы энергонезависимой памяти 28F008SA, 28F008SA-L. По материалам INTEL CORPORATION пер. Затишного В.В. М.: Совместное изд. МП «Бином» и ТОО «Конкорд», 1992.

20. Канторович Л.В., Залгаллер В.А. Расчёт рационального раскроя промышленных материалов. Л. Ленгизиздат, 1951.

21. Кнышев Д.А., Кузелин М.О. ПЛИС фирмы «Xilinx»: описание структуры основных семеств. М.: изд. дом «Додэка-ХХ1», 2001.

22. Ковалев A.B. Разработка и исследование методов проектирования цифровых заказных СБИС. Автореферат диссертации на соискание учёной степени кандидата технических наук. Таганрог: ТРТУ, 2001.

23. Кононов A.B., Севастьянов C.B. О сложности нахождения предписанной раскраски графа. // Дискретный анализ и исследование операций. -Новосибирск: Издательство института математики, 2000. стр. 21-46.

24. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. Определения, теоремы, формулы. М.: Изд-во «Наука». Главная редакция физико-математической литературы, 1978.

25. КорнеевВ.В., Киселев A.B. Современные микропроцессоры. М.: Нолидж, 2000.

26. КорнеевВ.В. Параллельные вычислительные системы. М.: Нолидж, 1999.

27. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. Москва.: Энергоатомиздат, 1987.

28. Курейчик В.В. Концепция оптимизации на основе моделирования эволюции // Новые информационные технологии. Разработка и аспекты применения. Таганрог: изд-во ТРТУ, 2000; стр.49-51.

29. Курейчик В.М. Генетические алгоритмы: Монография. Таганрог: изд-воТРТУ, 1998.

30. Курейчик В.М. Математическое описание конструкторского и технологического проектирования с применением САПР. Москва: Радио и связь, 1990.

31. Курейчик В.М., Глушань В.М., Щербаков Л.И, Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990.

32. Лебедев Б.К. Разбиение на основе коллективной адаптации. // "Известия ТРТУ", №3, 1999.

33. Линский В. Комбинаторика для программистов. / Пер. с польского Евстигнеева В.А., Логиновой O.A. М.: Мир, 1988.

34. Майк Гурвиц. Безотказные сети и системы. // LAN № 3 1998 стр. 37-39.

35. Маргелов A.B., Никифоров A.M. Ячейка коммутирующей среды для одновременной трассировки цепей. // Материалы межд. научн.-техн. конф. ИСАПР Известия ТРТУ № 2, 2000. стр. 244-246.

36. Маргелов A.B., Никифоров A.M. Ячейки коммутирующих сред для поиска кратчайших трасс. // Материалы межд. научн.-техн. конф. ИСАПР Известия ТРТУ № 3, 1999. стр. 304.

37. Мелихов А.Н., Берштейн JI.C., КурейчикВ.М. Применение графов для проектирования дискретных устройств. Москва: "Наука". Главная редакция физико-математической литературы, 1974.

38. Методы разбиения схем РЭА на конструктивно законченные части. / Под ред. Морозова К.К. Москва, Советское радио, 1978.

39. Молчанов И.Н. Введение в алгоритмы параллельных вычислений. Киев: Наукова думка, 1990.

40. Мячев A.A. Спецификация многопроцессорных систем компании Intel // Открытые системы №3 1995г. стр. 20-21.

41. Никифоров A.M. Выбор критериев размещения. // Материалы межд. научн.-техн. конф. ИСАПР Известия ТРТУ № 3, 1999. стр. 300-301.

42. Никифоров A.M. Выделение буквы из слитного рукописного текста. // IV Всероссийская научная конференция студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления". -Таганрог: ТРТУ, 8-9 октября 1998г. стр. 78.

43. Никифоров A.M. Оценка качества размещения. // Известия ТРТУ № 3, 1999. стр. 206-209.

44. Никифоров A.M., Кулаков A.A., Шпак В.Ф. Вопросы синхронизации параллельных процессов в комплексе АСОР. // Вопросы специальнойрадиоэлектроники. Серия «Общие вопросы радиоэлектроники». Выпуск 2. Москва Таганрог: ТНИИС, 2001. стр. 89-91.

45. Норенков И.П., Маничев В.Б. Основы теории проектирования САПР. -М.: Высшая школа, 1990.

46. О разрезании произвольного конечного графа на подграфы. Кодачигов В.И., Карелин В.П., Пашкевич А.П., Курейчик В.М. // в кн.: Цифровые модели и интегрирующие структуры. / Под ред. Каляева A.B. -Таганрог: Радиотехнический институт, 1970.

47. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М: Мир, 1985.

48. Петров A.B., Черненький В.М. Проблемы и принципы создания САПР. -М.: Высшая школа, 1990.

49. Петров Д.Ф. Генетика с основами селекции. М.: Высшая школа, 1971.

50. Петухов Г.А., Смолич Г.Г., Юлин Б.И. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. М.: Радио и связь, 1987.

51. Поляк Б.Т. Введение в оптимизацию. М.: Наука. Главная редакция физико-математической литературы, 1983.

52. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учебное пособие. / Под общ. ред. Останина А.Н. Минск: Вышэйшая школа, 1989.

53. Разработка САПР. / Под ред. A.B. Петрова М.: Радио и связь, 1986.

54. РябецМ.Н. Разработка и исследование генетических алгоритмов компоновки по критериям числа внешних связей и задержки распространения сигналов: Дис. к.т.н. Таганрог: ТРТУ, 2000.

55. СвамиМ., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ.- М.: Мир, 1984.

56. Системы автоматизированного проектирования: В 9-ти кн. Кн. 6. Автоматизация конструкторского и технологического проектирования. Учебное пособие для втузов. / Под ред. Норенкова И.П. М.: Высшая школа, 1986.

57. Стоян Ю.Г., Панасенко A.A. Периодическое размещение геометрических объектов. Киев: Наукова думка, 1978.

58. Тютин A.A. Автоматизация технического этапа проектирования микроэлектронных ЦВМ. Киев: РИО ИК АН УССР, 1972.

59. Тютин A.A. Улучшенный алгоритм размещения интегральных схем на плате. Киев: РИО ИК АН УССР, 1972.

60. Файзуллин А.З. Определение функции пригодности индивида популяции в генетическом алгоритме упаковки. // Всероссийская научная конференция студентов и аспирантов. Таганрог. 25-27 октября. 1995.

61. Файзуллин А.З. Разработка и исследование генетических методов размещения двумерных геометрических объектов: Дис. к.т.н. Таганрог: ТРТУ, 1996.

62. Хоровиц П., Хилл У. Искусство схемотехники. В 3-х т. М.: Мир, 1993.

63. Цифровые сигнальные процессоры. Материалы конференции. М.: РАН, 2000.

64. Чефранов А.Г. Параллельное программирование: Учебное пособие. -Таганрог: Изд-во ТРТУ, 2000.

65. ШпакВ.Ф., Кулаков A.A., Никифоров A.M. Программные аспекты реализации АСУ специального назначения. // Вопросы специальной радиоэлектроники. Серия «Общие вопросы радиоэлектроники». Выпуск 2. Москва Таганрог, ТНИИС, 2001. стр. 31-36.

66. Эвоинформатика. Теория и практика эволюционного моделирования. Букатова И.Л. и др. М. Наука, 1991.

67. Ячейка коммутирующей среды. Курейчик В.М., Маргелов А.В., Никифоров A.M., Маргелов А.А. / Свидетельство на полезную модель. №№ 12865, 13109, 13265. Москва 2000, 2001.

68. A fast transistor-chaining algorithm for CMOS cell layout. Hwang C.-Y., Hsieh Y.-C., LinY.-L. and Hso Y.-C. // IEEE Trans on CAD №7 vol.9 pp. 781-786.

69. Abonamah A.A., Sibai F.N. and Sharma N.K. Conflict resolution and fault-tree path selection in multicast-connected cube-based networks. // IEEE Trans on Computers. March 1994. Vol.43 № 3. pp.374-380.

70. Agrawal P., Robinson S.H. and Szymanski T.G. Automatic modeling of switch-level networks using partial orders. // IEEE Trans on CAD №7 vol.9 pp. 696-707.

71. Altera Corporation. MAX+PLUS II Getting Started. / MAX+PLUS II CD-ROM. USA. 1999.

72. Analog devices. Designers' reference manual. Data Sheets and Application Notes. 2001.

73. Anil K. Jain, Jianchang Mao, Mohiuddin K.M. Artificial Neural Networks: A Tutorial // Computer, Vol.29, No.3, March/1996, pp. 31-44.

74. Ashok Bindra. Extremely Parallel Processor Sets New Benchmark. // Electronic Design № 17 2001 pp.29-30.

75. Barjee P M. Jones. A Parallel Simulated Annealing Algorithm for Standart Cell Hyper Cube Computer. // Proc. Int Conf. on CAD 1986, pp. 156-159.

76. Bhide S., JohnN. and KabukaM.R. A Boolean neural network approach for the traveling salesman problem. // IEEE Trans on Computers №1, vol. 43. 1994 pp. 1271-1278.

77. Biswas N.N. On covering distant minterms by the CAMP algorithm. // IEEE Trans on CAD №7 vol.9. 1989. pp. 786-789.

78. BrownS., Rose J. Architecture of FPGAs and CPLDs: A Tutorial. / Department of Electrical and Computer Engineering, University of Toronto. 1999.

79. Burns S.W., JhaN.K. Total self-checking checker for parallel unordered coding Scheme. // IEEE Trans on Computers. April 1994. Vol. 43 № 4. pp. 490-495.

80. Cotter D., Tatham M.C. «Dead reckoning» a primitive and efficient self-routing protocol for ultrafast mesh networks. // Electronic Design; vol.3; 2001 pp. 135-142.

81. DeM., SinhaB.P. Fast parallel algorithm for ternary multiplication using multi-valued I L technology. // IEEE Trans on Computers. May 1994. Vol.43 № 5. pp.603-607.

82. Devadas S., A. R. Newton "Topological Optimization of Multiple Level Array Logic On Uni- and Multi-Processor" // Proceedings IEEE International Conference on CAD. 1986, pp. 38-41.

83. Eisemann H. and Johannes F.M. Generic global placement and floor planning. // in Proc IEE/ACM Int Conf CAD 1998 pp. 269-274.

84. FeldtR. Generating diverse software versions with genetic programming: an experimental study. //IEE Proceedinds Software vol. 145; № 6; December 1998; United Kingdom; pp.228-236.

85. Fiduccia C.M. and Rappoport K.J. Perfect shifters. // IEEE Trans on Computers. March 1994. Vol.43 № 3. pp.340-349.

86. Fiduccia C.M. Bused hypercubes and other pin-optimal permutation networks. // IEEE Trans Parallel Distrib. Syst. Jan 1992, Vol.3, № 1, pp. 14-21.

87. Fitch J.P., Sokhansanj B. Genomic engineers: moving beyond DNA sequence to function.//Proceedings of IEEE. №12 vol.88, 2000. pp. 341-365.

88. Foster Y. Designed and building parallel programs. Addison-Wesley, 2000.

89. Goldberg A.V., Maggs B.M. and Plotkin S.A. A parallel algorithm for reconfiguring a multibutterfly network with faulty switches. // IEEE Trans on Computers. March 1994. Vol.43 № 3. pp. 321-339.

90. Goldberg D.E. Genetic algorithms in search, optimization & machine learning. University of Alabama. Addison-Wesley, 1989.

91. Guaranteeing synchronous message deadlines with time token medium access control protocol. Agrawal G., Chen B., Zhao W., Davari S. // IEEE Trans on Computers. March 1994. Vol.43 № 3. pp. 327-339.

92. Hussey A., Carrington D. Comparing the MVC and PAC architectures: a formal perspective. // IEE Proc Software Engineering vol.144; №4 August 1997; pp. 224-136.

93. JayarmanR., RubenbarR. Floor planning by annealing on hypercube Multiprocessor. // Proc. Int Conf. on CAD 1987, pp. 346-349.

94. Kitchenham B.A., Stell J. The danger of using axioms in software metrics // IEE Proc Software vol. 144; № 5-6 Oct-December 1997; pp. 279-285.

95. Kravitz S.A., RutenbarR. Placement by Simulated Annealing on Multiprocessor. // IEE Trans on CAD 6, 1987, pp. 534-549.

96. Lagman A., Najjar W.A. and Srimani P.K. An analysis of edge fault tolerance recursively decomposable regular network. // IEEE Trans on Computers. April 1994. Vol.43 № 4. pp. 470-475.

97. Lakshman T.V. and Wei V.K. Distributed computing on regular networks with anonymous nodes. // IEEE Trans on Computers №2, vol. 43. 1994 pp. 211-218.

98. Limitations and challenges of CAD technology for CMOS VLSI (Invited Paper). Bryant R.E., Cheng K.-T. and others. // Proceedings of IEEE. March 2001. pp. 341-365.

99. Liou W.T., Tan J. J.-M. and Lee R.C.T. Minimum rectangular partition problem for simple rectilinear polygons. // IEEE Trans on CAD №7 vol.9 pp. 720-733.

100. Lyaw I.-P. and Koppelman D.M. Analysis of banyan networks offered traffic with geometrically distributed message lengths. // IEEE Proc Communications vol. 142 №5 pp.285-291.

101. MAXIM Spezial-Electronic KG. Programm'96. / Kao Optical Products, 1996.

102. MaziaszR.L. and Hayes J.P. Layout optimization of static CMOS functional Cells. // IEEE Trans on CAD №7 vol.9 pp. 708-719.

103. On-Chip wiring design challenges for gigahertz operation (Invited Paper). DeutschA., CoteusP.W. and others. // Proceedings of IEEE. April 2001. pp. 529-555.

104. OstermanM.D. and PechtM. Placement for reliability and routability of convectively cooled PWB'S. // IEEE Trans on CAD №7 vol.9 pp. 734-744.

105. Parhi K.K., Wu F.H. and Genesan K. Sequential and parallel neural network vector quantizers. // IEEE Trans on Computers №1, vol. 43. 1994 pp. 104-109.

106. Pei Tong-Bi and Zukowski Charles. Putting routing tables in silicon. // IEEE Network. 1992. vol. 6 № 1. pp. 42-50.

107. Practical handbook of Genetic Algorithms. Complex Coding Systems. / Edited by Lance D. Chambers. CRC Press LLC, 1999.

108. PVM: Parallel Virtual Mashine. A users' guide and tutorial for networked parallel computing. A1 Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Robert Manchek, Vaidy Sunderam. MIT press, 2000.

109. Rao V.B. and Trick T.N. Network Partitioning and Ordering for MOS VLSI Circuits. // IEEE transaction on CAD on integrated circuits and system №1 1987 pp.128-144.

110. Solwen Howard. Toward gigabit LANs on FDDI Fiber. // IEEE Network. 1992. vol. 6 № l.pp. 8-10.

111. Supowit K.J. Finding a maximum planar subset of a set of nets in a channel // IEEE transaction on CAD on integrated circuits and system №1 1987 pp.93-94.

112. Swaminathen R. and VeeramaniD. Decomposition of {0,1} matrices. // IEEE Trans on Computers. May 1994. Vol.43 № 5. pp.629-633.

113. ValenzanoA., Demartini C., and CiminieraL. MAP&TOP Communications. Addison-Wesley Publishing Co, 1992.

114. XILINX. General documents. USA : Xilinx optical libraiy, 1998.