Разработка и исследование генетических методов расслоения топологии СБИС тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Щеглов, Сергей Николаевич

• Щеглов, Сергей Николаевич
• кандидат технических наук
• 1998

Оглавление диссертации кандидат технических наук Щеглов, Сергей Николаевич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1 АНАЛИЗ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ПО СЛОЯМ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ

1.1. Выбор модели исследования

1.2. Классификация подходов к решению задачи расслоения соединений

1.3. Методы дотрассировочного расслоения

1.3.1. Распределение соединений по слоям методом пробного назначения

1.3.2. Методы учета степени "взаимодействия" связывающих деревьев

1.4. Расслоение совмещенной топологии схемы

1.5. Выводы и рекомендации

2. ИССЛЕДОВАНИЕ МЕТОДОВ ГЕНЕТИЧЕСКОГО ПОИСКА

ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ ПО СЛОЯМ

2.1. Анализ эволюционных процессов

2.1.1. Роль популяции в цепи естественного отбора

2.1.2. Стратегии формирования популяции в задачах САПР

2.1.3. Наследственные факторы и их оценка в оптимизационных задачах

2.2. Структура генетического алгоритма

2.3. Структура основных операторов генетического поиска

2.3.1 Селекция

2.3.2 Кроссинговер

2.3.3. Мутация

2.3.4. Отбор

2.4. Выводы и рекомендации

3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАСПРЕДЕЛЕНИЯ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ ПО СЛОЯМ В СБИС

3.1. Формулировка задачи, основные понятия и определения

3.2. Разработка структурной схемы процесса генетического

поиска для задач расслоения топологии СБИС

3.3 генетический алгоритм распределения трассируемых соединений по слоям

3.3.1 Представление хромосомы

3.3.2 Разработка процедуры определения пересечений

3.3.3 Целевая функция

3.3.4. Генетические операторы и генетический алгоритм

3.4. Теоретические оценки алгоритма

3.5. Выводы и рекомендации

4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННОГО АЛГОРИТМА РАСПРЕДЕЛЕНИЯ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ ПО СЛОЯМ

4.1. Цель экспериментального исследования

4.2. Определение пространственной и временной сложности алгоритма

4.3. Определение управляющих параметров генетического алгоритма решения задачи распределения трассируемых соединений по слоям

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

4.5. Выводы и рекомендации

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

Введение диссертации (часть автореферата) на тему «Разработка и исследование генетических методов расслоения топологии СБИС»

ВВЕДЕНИЕ

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

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

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

Одним из важнейших достижений человечества стало создание интегральных схем. Возникшие в 60-х годах нашего века, интегральные схемы развились, за короткое время, от объединения нескольких транзисторов до интеграции миллионов транзисторов в одной схеме. Первые интегральные схемы (ИС) представляли собой объединение одиночного транзистора с набором сопротивлений, предназначенное для выполнения какой-либо логической функции. Сейчас ИС способны выполнять сложнейшие функции, они проникли во все слои человеческого общества, современное общество не смогло бы возникнуть без использования ИС. В настоящее время, геометрические размеры элементов могут иметь размеры до 0.18 микрона (один микрон = 1.0 х 10~6 метра), для сравнения человеческий

волос в диаметре около 75 микронов. В ближайшие пять лет ожидается уменьшение размеров на 0.1 микрона. Современная технология позволяет разместить 10-15 миллионов транзисторов на схеме размером 25 мм. х 25мм. Такая быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [1-26]. Сейчас, на всех стадиях проектирования топологии сверхбольших ИС (СБИС), интенсивно используют средства автоматизации проектирования и многие фазы могут быть полностью или частично автоматизированы.

Цикл проектирования СБИС включает следующие основные фазы:

• спецификация системы;

• функциональное проектирование;

• логическое проектирование;

• схемное проектирование;

• конструкторское проектирование;

• изготовление;

• сборка, тестирование и контроль.

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

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

Фаза логического проектирования заключается в определении размера слов, распределении регистров и управляющих потоков, арифметических и логических операций. Для логического описания систем используют язык УНБЬ. Логическое описание включает минимизированные булевы функции и описание временных задержек. При логическом проектировании делается моделирование и тестирование системы для проверки корректности построенной системы.

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

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

После верификации топология схемы преобразуется в набор масок. Использование которого, во время различных технологических процессов, позволяет изготовить твердотельную структуру схемы. Обычно на одной пластине кремния диаметром 20 см. удается разместить несколько сотен чипов.

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

Этап конструкторского проектирования подразделяется на разбиение, планирование, размещение, трассировку, упаковку и верификацию.

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

Задача планирования заключается в определении взаимного расположения блоков друг относительно друга. Задачей размещения является определение конкретного места для каждого блока на кристалле.

Трассировка заключается в конструктивной реализации связей между элементами.

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

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

В настоящее время, в связи с развитием технологии изготовления СБИС, возник ряд новых тенденций, требующих внимания при проектировании СБИС. В связи с уменьшением размеров элементов и уменьшением задержек в них, более 60% общей временной задержки приходится на задержки в межсоединениях. Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов. В чипе, содержащем 10 миллионов транзисторов и

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

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

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

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

Большой вклад в решение задач внесли работы таких учёных как Селютин В. И., Курейчик В. М., Корячко В. П., Норенков И. П., Анисимов В. И., Батищев Д. И., Вермишев Ю. X., Лошаков В. Н., Широ Г. Э., Бершадский А. М., а также зарубежные учёные такие как: N. Sherwani, С. Sechen, М. А.

Breuer, S. В. Akers, H. H. Chen, D. N. Deutsch, R. Joobbani. [1 - 8, 64 - 71, 73 -76]

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

Существует несколько подходов к решению NP - полных задач.

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

Ко второму классу относятся так называемые эвристические алгоритмы, позволяющие получать локальные решения за приемлемое время.

К третьему классу относятся алгоритмы случайного направленного поиска, основанные на принципах моделирования. [51 -100]

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

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

Сравнительно недавно их начали широко применять для решения задач в самых различных областях, в том числе для решения задач проектирования СБИС [38,60-61], [41].

ГА имеют следующие отличия от других оптимизационных и поисковых процедур:

• осуществляют поиск из множества точек, а не из единственной точки;

• используют целевую функцию, а не ее различные приращения, для оценки информации;

• используют не детерминированные, а вероятностные правила;

• дают не одно решение, а целый спектр решений.

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

ЦЕЛЬЮ диссертационной работы является разработка и исследование генетических методов и алгоритмов распределения трассируемых соединений СБИС по слоям.

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

1. Разработка структурной схемы процесса генетического поиска для задач расслоения топологии СБИС.

2. Разработка процедуры формирования популяции и селективного отбора.

3. Разработка процедур оценки качества (фитнесса).

4. Разработка методов кодирования и декодирования хромосом.

5. Исследование генетических алгоритмов распределения топологии трассировки.

Для решения поставленных задач используют следующие МЕТОДЫ ИССЛЕДОВАНИИ: Элементы теории множеств, элементы теории алгоритмов, элементы генетики и генетического поиска.

и

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:

a) разработке архитектуры генетического поиска, ориентированной на решение задач распределения трассируемых соединений по слоям;

b) определении методики решения задачи расслоения топологии;

c) разработке модифицированных генетических операторов, ориентированных на решение задач трассировки.

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

Генетический алгоритм и комплекс программ распределения соединений топологии СБИС.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

Основные теоретические и практические результаты диссертационной работы: использование в госбюджетных работах «Разработка теории и методов построения интегрированных САПР БИС с элементами искусственного интеллекта» (№ ГР 01.9.50004188), «Разработка методов и моделей генетического поиска в интеллектуальных САПР» выполненной в рамках государственной научно-технической программы «Университеты России» (1995-1996 г.г.), хоздоговорной работе «Учебно-методический комплекс. Применение экспертных систем в инженерной практике» выполненной в рамках научно-технической программы «Компьютеризация образования» (1995 г.), «Исследование генетических методов оптимизации» (№ГР 02.9.70001838).

Результаты работы используются в МГТИ (г. Майкоп). Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций и в цикле лабораторных работ по курсу «Методы генетического поиска».

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на научных семинарах «Генетические алгоритмы» (осень 1994 - весна 1995 г. г. ТРТУ), Всероссийской научно-технической

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

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

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ.

Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложений. Работа содержит 144 стр., включая 33 рис., 10 таб., список литературы из 102 наименований, 8 стр. приложений и актов об использовании.

СОДЕРЖАНИЕ РАБОТЫ.

ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, поставлена цель работы, дано общее описание выполненной работы.

В ПЕРВОЙ ГЛАВЕ произведен выбор модели исследования для решения поставленной задачи. Рассмотрены вопросы, связанные с определением различных аспектов задач трассировки, определением оценочной функции.

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

ВО ВТОРОЙ ГЛАВЕ дано описание основных генетических алгоритмов. Рассмотрены основные генетические операторы, используемые при решении задач генетическими методами.

В ТРЕТЬЕЙ ГЛАВЕ описано решение задачи распределения трассируемых соединений по слоям с помощью генетического алгоритма.

Разработана методика кодирования и декодирования хромосом для задачи расслоения топологии СБИС, с использованием специфических знаний о задаче.

Разработаны принципы формирования исходной популяции и принципы её редуцирования.

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

Приведена теоретическая оценка временной и пространственной сложности алгоритма.

В ЧЕТВЕРТОЙ ГЛАВЕ приведено описание экспериментальных исследований генетического алгоритма распределения трассируемых соединений по слоям.

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

Сделана экспериментальная оценка пространственной и временной сложности алгоритма.

В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.

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

1 АНАЛИЗ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ПО СЛОЯМ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ.

1.1. Выбор модели исследования.

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

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

Основная задача трассировки формулируется следующим образом: по заданной схеме соединений, например как на рис.1, проложить необходимые проводники на плоскости (плате, ТЭЗ, кристалле и т. п.), приведенной на рис.2, чтобы реализовать заданные электрические соединения с учетом заранее заданных ограничений. Основными являются ограничения на ширину проводников и минимальное расстояние между ними.

Схема соединений

Рис.1.1.

Многослойная плата.

Рис. 1.2.

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

Б- аддитивный критерий;

Л - весовой коэффициент; - частный критерий;

р - число частных критериев.

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

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

F

Я , • /, ,

(1.1.)

р

где:

В последовательных методах трассы проводят одну за другой последовательно, при этом проведение какой либо трассы А на (ь1 )-м шаге может затруднить проведение трассы В на ьм шаге, так как она будет являться препятствием для проведения трассы В. Следовательно, особенно актуальным для последовательных алгоритмов трассировки, является ранжирование (упорядочивание) соединений до трассировки. Существуют различные стратегии упорядочивания, основанные, в частности, на длине соединений, степени охвата соединением других соединений и др. Однако объективных оценок эффективности таких методик в настоящее время нет, поэтому наиболее разумными представляются использование нескольких вариантов очередности и выбор из них наилучшего.

Задачу трассировки можно условно представить в виде четырех последовательно выполненных этапов:

- определение перечня соединений;

- размещение по слоям;

» определение порядка соединений;

- трассировка проводников.

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

Таким образом, следует отметить, что трассировка межсоединений элементов на каждом из конструктивных уровней является основной топологической задачей проектирования печатных плат и СБИС. При этом задача трассировки - одна из наиболее важных и трудоемких в общей проблеме автоматизации проектирования ЭВА, причем необходимо отметить,

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

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

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

Структурная схема адаптивной подсистемы, реализующей блочно-иерархический подход к решению задачи распределения соединений по слоям, может быть представлена в следующем виде (рис. 1.3).

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

Оптимизационных задач достаточно много и они могут иметь весьма разнообразный характер. Однако постановка, но не решение, всех оптимизационных задач имеет сходные черты.

Рис. 1.3. Адаптивная подсистема

1. При постановке оптимизационной задачи указывается исходное множество вариантов или, как говорят, решений. Из этого множества решений и выбирается оптимальное решение. Это исходное множество решений называется пространством решений. В дальнейшем его будем обозначать через X.

2. Некоторые решения априорно отвергаются в качестве возможных оптимальных решений. Иначе говоря, на пространстве решений задаются ограничения, которым должны удовлетворять оптимальные решения. Эти ограничения выделяют в пространстве решений X некоторое подмножество Б тех решений, которые удовлетворяют заданным

ограничениям О. Это множество решений называется множеством допустимых решений.

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

4. Критерий оптимальности представляет собой отображение (т.е. функцию), определенное на множестве допустимых решений и принимающее в качестве значений вещественные неотрицательные числа. Обозначим это отображение, т.е. критерий, через С). Тогда

(2:8->К+,

где - множество неотрицательных вещественных чисел.

5. Зная функцию С) можно задать два способа сравнения. При первом способе решение X считается лучшим, чем решение У, если

СКхХИу).

В этом случае говорят, что оптимизационная задача состоит в минимизации критерия О1, т.е. требуется найти такое допустимое решение

х е Б, что

(2(х*)=тт СКу) /уеБ.

_ *

Таким образом критерий в х принимает минимальное значение. При втором способе решение X считается лучшим, чем решение У, если

<3(х)>(2(у).

В этом случае говорят, что оптимизационная задача состоит в максимизации критерия С), т.е. требуется найти такое допустимое решение

х еБ, что

(3(х*)=тах д(у)/уе8. Обычно требуемое правило сравнения указывается коротко с помощью записи

(3(х)-»тт5

для задачи минимизации или

(Хх)-^тах,

для задачи максимизации.

6. Итак, оптимизационная задача имеет структуру, описываемую кортежом:

<ХА(2>,

где X - пространство решений,

О - ограничения, выделяющие в X область допустимых решений

С):8—»И* - критерий оптимизации, требование оптимизации СХх)->тт или (^)(х)->тах.

Решение х е8, удовлетворяющее требованию оптимизации, т.е.

С)(х*)=тт5 Q(y) /уеЭ или С)(х*)=тах, Q(y) /уе8 называется оптимальным.

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

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

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

1.2. Классификация подходов к решению задачи расслоения

соединений.

Существует несколько подходов к решению КР-полных задач САПР (см. табл. 1.1).

Таблица 1.1

Классификация подходов к решению ИР-полных задач САПР.

№ п/п Подход к решению ЫР-полных задач Методы оптимизации Полнота

1 Сокращение объема перебора Метод ветвей и границ, Динамическое программирование, Метод отсечения и др. Р,№

2 Поиск локального оптимума Эвристические Р

3 Случайный поиск Метод сужающихся окрестностей, Моделирование отжига Р

4 Случайно-направленный поиск Генетические алгоритмы Р

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

Подходы, относящиеся ко второй категории, включают прием, который можно назвать "снижение требований". Он заключается в отказе от поиска оптимального решения и в нахождении вместо этого хорошего решения за приемлемое время. Алгоритмы, основанные на этом приеме, обычно называют эвристическими, поскольку они используют различные разумные соображения без строгих обоснований. Методы, применяемые для построения алгоритмов такого типа, сильно зависят от специфики задачи. Наиболее широко применяют метод "локальнго поиска", когда заранее выработанное множество локальных операций используется для последовательного улучшения начального решения до тех пор, пока такое улучшение возможно, в противном случае оказывается достигнутым локальный оптимум [20].

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

В последнее время для решения задач САПР разработано несколько методов оптимизации, в которых для преодоления барьеров локального

оптимума применяются случайные правила поиска. Эти методы образуют третью область, которая в силу непрерывности оптимизационного поиска обладает наибольшими перспективами развития. Алгоритм случайного оптимизационного поиска имеет две составляющие [83]:

1. Механизм оптимизации, который выполняет случайный перебор возможных решений.

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

При разработке алгоритма для конкретной задачи САПР необходимо решить две проблемы:

1. Представление решения для алгоритма перебора.

2. Построение целевой функции.

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

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

Алгоритмическое распределение соединений по слоям (расслоение) может выполняться до, после и в процессе трассировки отдельных соединений.

Классификация основных подходов размещения по слоям трассируемых соединений представлена на рис.1.4.

Классификация алгоритмов расслоения соединений.

Рис. 1.4

1.3. Методы дотрассировочного расслоения.

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

1.3.1. Распределение соединений по слоям методом пробного назначения.

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

Одним из способов упрощения этой задачи является предположение о том, что на одиночном слое каждый проводник вычерчивается в виде прямой линии, соединяющей два определенных контакта (рис. 1.5). Теперь, если в нашем распоряжении имеются, например, три слоя, то задача размещения по слоям превращается в задачу отыскания такого расположения проводников на этих трех слоях, чтобы в каждом из них число взаимных пересечений было минимальным. Поскольку окончательная конфигурация любого проводника включает в себя горизонтальные и вертикальные отрезки, тогда тот факт, что прямые (евклидовы) линии, проведенные между парой контактов, пересекаются, еще не означает, что должны непременно пересечься соответствующие им минимальные «манхеттеновы» пути (рис. 1.6)

Задача размещения по слоям

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Щеглов, Сергей Николаевич

4.5. Выводы и рекомендации

1. Экспериментально определены пространственные и временные сложности алгоритма распределения трассируемых соединений по слоям, подтвердившие, в целом, теоретические оценки.

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

3. Проведено сравнение представленного алгоритма с существующими, которое показало преимущество представленного алгоритма. Представленный алгоритм распределения трассируемых соединений по слоям находит решения, сравнимые с результатами существующих алгоритмов, кроме того он позволяет сократить время решения на 10-15%.

ЗАКЛЮЧЕНИЕ

1. Представлены области применения и даны постановки задач распределения трассируемых соединений по слоям с учетом возможностей современных технологий, указан класс решаемых задач. Проведен анализ существующих подходов к решению задач расслоения топологии СБИС. На основе проведенного анализа для решения задач распределения трассируемых соединений по слоям выбран генетический метод в качестве перспективного. Он позволяет получать качественные результаты за приемлемое время.

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

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

II II ч» количество нелегальных решении и тем самым улучшить качество получаемых решений. Разработана методика декодирования хромосомы, исключающая возможность нарушения конструкторских ограничений. Разработана целевая функция, оценивающая основные показатели распределения соединений по слоям (число требуемых пар-плоскостей, максимальное количество соединений в одном слое). Определены генетические операторы, схема генетического алгоритма, метод формирования начальной популяции. Найдены теоретические оценки пространственной и временной сложности разработанного алгоритма распределения трассируемых соединений по слоям.

4. Для разработанного алгоритма создан пакет программ на языке Borland С++ под Windows 95, которые позволяют эффективно использовать все богатство генетического инструментария.

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

6. Проведенные исследования показали, что применение генетического алгоритма распределения трассируемых соединений по слоям позволяет сократить сроки проектирования на 8-14% и улучшить качество получаемых решений на 5-10%.

Список литературы диссертационного исследования кандидат технических наук Щеглов, Сергей Николаевич, 1998 год

ЛИТЕРАТУРА

1. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Norwell, Kluwer Academic Publishers, 1995, 538 p.

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

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

4. Селютин В.А. Автоматизированное проектирование топологии БИС. М., Радио и связь, 1983. 112 с.

5. Разработка САПР. Под ред. А.В. Петрова. М., Высшая школа, 1990.

6. Абрайтис Л.А. Автоматизация проектирования топологии цифровых интегральных микросхем. М., Радио и связь, 1985. 200 с.

7. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.,"Наука", 1974, 304 с.

8. Казенов Г.Г., Сердобинцев Е.В. Проектирования топологии матричных БИС. М., Высш. шк., 1990, с.112.

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

10. Селютин В.А. Машинное конструирование электронных устройств. М., Советское радио, 1977.

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

12. Курейчик В.М. Математическое обеспечение КТП с применение САПР. М., Радио и связь, 1990, с.352.

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

14. Деньдобренко Б.П., Малика A.C. Автоматизация проектирования радиоэлектронной аппаратуры. М., Высш. шк., 1980. с.384.

15. Сквозное автоматизированное проектирование микроэлектронной аппаратуры / З.Ю. Готра, В.В. Григорьев, JI.M. Смеркло, В.М. Эйдельнант. М., Радио и связь, 1989. с.280.

16. Системы автоматизированного проектирования в радиоэлектронике. Под ред. И.П. Норенкова. М., Радио и связь, 1986.

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

18. Карберри П.П. Персональные компьютеры в автоматизированном проектировании. М., Машиностроение, 1989. с. 144.

19. Сорокопуд В. А. Автоматизированное конструирование микроэлектронных блоков с помощью малых ЭВМ. М., Радио и связь, 1988. с.128.

20. Ульман Дж. Д. Вычислительные аспекты СБИС. М., Радио и связь, Москва, 1990.

21. Автоматизация проектирования БИС. Под ред. Г.Г. Казенова, М., Высшая школа, 1990.

22. Ведерникова О.Г., Чернышев Ю.О. Исследование алгоритма имитации отжига для решения задач размещения при проектировании БИС. Изд-во Таганрог, ун-та, 1995.

23. Курейчик В.М., Родзин С.И. Контролепригодное проектирование и самотестирование СБИС: проблемы и перспективы. М., Радио и связь, 1994. с.76.

24. Петренко А.И., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизация конструирования электронной аппаратуры (топологический подход).

Киев: Вища школа, 1980. 175 с.

25. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВМ. Изд-во Сарат. ун-та, 1983. 120 с.

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

27. J.Heisterman and T.Lengauer. The efficient solution of integer programs for hierarchical global routing. IEEE Transactions on Computer Aided Design, CAD 10(6), Jane 1991. pp. 748-753.

28. C.Chang , M.Sarrafzadeh, and C.K. Wong. A powerful global router: Based on sterner min-max trees. Proceedings of IEEE International Conference on Computer Aided Design, November 7-10 1989. pp. 2-5.

29. S.Burman, H. Chen, and N. Sherwani. Improved global routing using X-geometry. Proceedings of 29th Annual Allerton Conference on Communications, Computing, and Control, October 1991.

30. J.M. Ho, G. Vijayan, and C.K. Wong. A new approach to the rectilinear Sterner tree problem. IEEE Transactions on Computer Aided Design, 9(2), February 1985. pp. 185-193.

31. J.Cong. Pin Assignment With Global Routing. Proceedings Of International Conference on Computer Aided Design, 1989. pp. 302-305.

32. J.Cong and B.Preas. A new algorithm for standard cell global routing. Proceedings of IEEE International Conference on Computer Aided Design, 1988. pp. 176-179.

33. Sechen C. VLSI Placement and Global Routing Using Simulated Annealing. Kluwer, B.V., Devenler, The Netherlands.

34. Лебедев О.Б. Глобальная трассировка на основе экспертных систем. // Тезисы докладов на Всероссийской научно - технической конференции с участием зарубежных представителей. Геленджик, 1992. с. 54

35. Deutsch, D.N. A dogleg channel routing, in Proc. 13th Design Automation Conf. 1976.

36. Deutsch, D.N. Compacted channel routing. Proc. of IEEE International Conf. on CAD, 1985. pp. 223-225.

37. Burstein, M. Channel routing, Layout Design and Verification. Elsevier Science, 1986. pp. 133-167.

38. Liu, X., Sakamoto, A., Shimamoto, T. Restrictive Channel Routing with Evolution Programs. Trans. EEICE, vol.E76-A, no.10,1993. pp.1738-1745.

39. Yoshimura, T. And Kuh, E.S. Efficient algorithms for channel routing. IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.1, no.l, 1982. pp.25-35.

40. Лебедев Б.К. Канальная трассировка на основе динамических принципов и методов минимизации комбинаторной размерности. Межведомственный тематический научный сборник «Интеллектуальные САПР», выпуск 5, Таганрог, 1995. с. 11-21.

41. Rahmani, А.Т. and Опо N. A Genetic Algorithm for Channel Routing Problem, in Proc. 5th Intl. Conf. on GAs, 1993. pp. 494-498.

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

43. Давиденко В.Н. Алгоритм задачи канальной трассировки, основанный на методе генетического поиска. Известия ТРТУ, № 3, Таганрог, 1996. стр. 46-49.

44. Помазанов В.М., Крыжановский Ю.М., Клименкова Т.И. Алгоритмы и программы комплекса трассировки.- «Обмен опытом в радиопромышленности», 1971, вып.7, с.29-31.

45. Hightower D.W. The interconnection problem: a tutorial. - "Computer", 1974, v.7, No. 4, p.18-32.

46. Давиденко В.Н. Генетический алгоритм канальной трассировки. Межведомственный тематический научный сборник «Интеллектуальные

47

48

49

50

51

52

53

54

55

56

57

58

59

САПР», выпуск 5, Таганрог, 1995. с. 155-156.

М. Брейер. Теория и методы автоматизации проектирования вычислительных систем.-М.: Мир, 1977.-283

Hashimoto, A. and Stevens, J. Wire routing by optimization channel assignment within large apertures. Proceedings of the 8th Design Automation Workshop, 1971. pp. 155—163.

Weissman J Boolean algebra, map coloring, and interconnections.- "The Mathematical Monthly", 1962, p. 608-613.

Tseng, H.P., and Sechen, K. A Gridlless Multi-layer Channel Router Based on a Combined Constraint Graph and Tile Expansion Approach. ISPD-96, 1996. pp. 210-217.

Ho J. Layer assignment for multichip moduls. IEEE Trans. CAD, Vol. 9, no. 12, December, 1990.

Казенов Г.Г, Марченко A.M. Абстрактный эволюционный алгоритм

синтеза СБИС. Известия ТРТУ, №3, Таганрог, 1996. стр. 112.

Развитие канального подхода в конструировании МЭА / Яковлев Н.Н.,

Баранский В.А. и др. Свердловск, Изд-во Урал, ун-та, 1987.

Luk, W. К. A greedy switchbox router. Integration, The VLSI Journal, 3,

1985. pp. 129-149.

M. Marek-Sadowska. Switchbox routing: a retrospective. Integration, The VLSI Journal, 13, 1992. pp. 39-65.

Pyke R.B. A gridless switchbox router, in Proc. Custom Integrated Circuits Conf., 1987. pp. 629-632.

Joobbani R., Siewiorek D.P. WEAVER: A Knowledge-Based Routing Expert, in Proc.22nd Design Automation Conf., 1985. pp. 266-272. Shin H., Sangiovanni-Vincentelli A. MIGHTY: A 'Rip-Up and Reroute' Detailed Router. Proc. IEEE International Conference on Computer Aided Design, November 1986. pp. 2-5

Lin Y., Hsu Y., Tsai F. A detailed router based on simulated evolution. IEEE

Trans. Computer Aided Design, № 5, 1988. pp. 38-41.

60. Cong J., and Liu C.L. Over-the-Cell Channel Routing, IEEE Trans. Computer Aided Design , vol. 9, № 4,1990. pp. 408 - 418.

61. Cong J., Preas В., and Liu C.L. Physical Model and Efficient Algorithms for Over-the-Cell Routing in Standard Cell Design, IEEE Trans. Computer Aided Design, vol. 12, № 5, 1993. pp. 723-734.

62. Kodres U.R. Formulation and solution of circuit card design problems through use of a graph methods. - "Advances in Electronic Circuit Packaging", 1962, v.2, No 7, p. 121-142.

63. Weissman J. The mathematical basis of the Automatics Etched Interconnection Design Program.- "IRE International Convention Record", 1962, p. 126-133.

64. Holland, John H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.

65. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company Inc., Massachusetts, 1989. 412 p.

66. Davis L.D. Handbook of Genetic Algorithms. Van Nostrand Reinold, New York, 1991.

67. Goldberg D.E., Kalyanmoy D. A comparative analysis of selection schemes used in genetic algorithms. In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. Mogan Kaufmann, San Mateo, CA, 1991.

68. Syswerda G. Uniform Crossover in Genetic Algorithms. Proc. of the 3-rd Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1989. p. 2-9.

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

70. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution

Programs. Springer-Verlag, 1992.

71. Kureichik V.M. et all. Some new features in Genetic Solution of the Traveling Salesman Problem. Proc. of the Second Intl. Conf. Adaptive Computing in Engeneering, Design and Control, Plymouth, UK, 1996. pp. 294-296.

72. Курейчик B.M. Генетические алгоритмы и их применение в САПР. Интеллектуальные САПР, меж. сб., Таганрог, 1995. стр. 7-11.

73. Чернышев Ю.О., Курейчик В.В. Генетические алгоритмы размещения / XXII International School And Conference On Computer Aided Design, CAD-95, Gurzuff, 1995. c. 329-330.

74. Щеглов C.H. и др. Исследование генетических методов оптимизации. // Депонир. В ВНТИ № ГР 02.9.70001.838, Таганрог, 1996.

75. Cohoon J.P. and Paris W.D. Genetic placement. IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.6, № 6,1987. pp.956-964.

76. Goodman, E. Tetelbaum, A. and Kureichik, V. (1994). A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems. Case Center Technical Report #940702, Michigan State University

77. Chan, H.M. and Mazumder, P. A genetic algorithm for macro cell placement. Technical report, Department of Electrical Engineering and Computer Science, University of Michigan, 1989

78. Kureichik, V.M. Genetic Algorithms In CAD. Proc. Russia Conf. AI in CAD, Gelendzik, September 1993.

79. Родзин С.И. Проектирование самотестируемых СБИС с применением метода генетического поиска. Известия ТРТУ, №3, Таганрог, 1997. стр. 84-86.

80. Lin S.C., Goodman Е.Р., Punch W.F. A Genetic Algorithm Approach to Dynamic Job Shop Scheduling Problems. Proc. of the 7th International Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1997. pp. 481-488.

81. Ikonen I., Biles W.E., Kumar A., Wissel J.C. and Ragade R.K. A Genetic Algorithm for Packing Three-Dimensional Non-Convex Objects Having Cavities and Holes. Proc. of the 7th International Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1997. pp. 591598.

82. Schnecke V., Vornberger O. A Genetic Algorithms for VLSI Design Automation. Proc. of the Second Intl. Conf. Adaptive Computing in Engeneering, Design and Control, Plymouth, UK, March 1996. pp. 53-58.

83. Батищев Д И., Власов C.E., Булгаков И.В. Плотное размещение разногабаритных объектов на плоскости с помощью генетических алгоритмов. XXIII International School and Conference on Computer Aided Design.Yalta-Gurzuff, 1996. 354 с

84. Марченко A.M., Плис А.П. Алгоритм удаления циклов в графе вертикальных ограничений задачи трассировки многослойного канала. Известия ТРТУ № 2, Таганрог, 1998.

85. Asano Т., Kitahashi Т., Tanaka К., Horino Н. and Amano N. A WireRouting Scheme Based on Trunk-Division Methods. IEEE Trans. On Computers, vol. 26, pp. 764-772, 1977.

86. Preas B. Channel Routing With Non-Terminal Doglegs. Proc. ED AC Conference, March 1990. pp. 451-458.

87. Лебедев Б.К. Канальная трассировка на основе генетических процедур. Известия ТРТУ, №3, Таганрог, 1997. с. 53-60.

88. Мину М. Математическое программирование. М., Наука, 1990.

89. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.

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

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

92. Яблоков В.А. Фенетика. М.: Наука, 1980 г. -132 с.

93. Джеральд Ф. Джойс. "Направленная молекулярная эволюция". Журнал "В мире науки". №2,3 1993 г. стр.32/всего 160 стр. Издательство "Мир". Москва

94. Ауэрбах Ш. Проблемы мутагенеза. Пер. с англ. Гнездицкой Э.В., Маршак М.И., Полукаровой Л.Г. Под ред. Шапиро Н.И. М.:Мир, 1978 г.-464 стр.

95. Бейсон Ж. Генетика. Пер с франц. Назарова В.И., М.: Атомиздат, 1978 г.

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

97. Лэнгсам Й., Огенстайн М., Тетельбаум А. Структура данных для персональных ЭВМ. М., Мир, 1989. 568 с.

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

99. Львовский E.H. Статистические методы построения эмпирических формул: Учеб.пособие для втузов. М., Высшая школа, 1988. 239 е.: ил.

100. Митропольский А.К. Техника статистических вычислений. М., Наука., 1971.576 е.: ил.

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

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