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

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

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

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

Основная особенность ГА состоит в том, что анализируется не одно решение, а некоторое подмножество квазиоптимальных решений, называемых "хромосомами" или стрингами. Это подмножество носит название "популяция". Для каждой хромосомы должна быть вычислена целевая функция F(n), называемая эволюционной, где n - число элементов в хромосоме. Такие функции вычисляют относительный вес каждой хромосомы. В каждой популяции хромосомы могут подвергаться действиям различных операторов. При этом происходят процессы, аналогичные действиям, которые случаются в естественной генетике. К основным операторам относят: кроссинговер (ОК), инверсию (ОИ), мутацию (ОМ), транслокацию (ОТ), сегрегацию (ОС), кроссмутацию (ОКМ) [8-13].

Генетические алгоритмы успешно используются при проектировании СБИС в задачах размещения [14-15], при решении комбинаторно-логических задач [16] и задач канальной трассировки [17-21]. Генетические алгоритмы в отличие от существующих рассматривают не одно решение, а целый спектр возможных решений, к тому же обладают возможностями выхода из "локальных" оптимумов, что позволяет получать лучшие решения, чем при решении задач канальной трассировки существующими алгоритмами [17-21]. В данной работе описан новый перспективный подход для решения задач канальной трассировки на основе ГА.

Основное отличие предлагаемой методики от известных генетических алгоритмов канальной трассировки заключается в использовании новой архитектуры генетического поиска, модифицированных генетических операторов и способов кодировки, что позволяет исключить возникновение "нелегальных" решений, т.е. решений, в которых возникают наложения участков цепей, и получать более качественные решения за тоже время. Еще одним важным отличием предлагаемого подхода является возможность его использования для решения задач канальной трассировки в современной безсеточной постановке (gridless) [1,5], а также трассировки цепей различной ширины, поскольку в алгоритме используется новый принцип кодирования.

Задача канальной трассировки в классической постановке

Определения и терминология

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

Каждая цепь, т.е. соединение эквипотенциальных контактов, представлена как одиночный горизонтальный сегмент с несколькими вертикальными сегментами, которые соединяют горизонтальный сегмент с контактами цепи [1]. Горизонтальные сегменты располагаются в одном слое, вертикальные - в другом. Соединения между горизонтальными и вертикальными сегментами делаются через переходные отверстия.

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

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

Описание канала

Канал описывается двумя последовательностями Tор и Bоttоm, в которых размещены верхняя и нижняя линейки канала, соответственно [1]. Размер обеих последовательностей равен C - числу колонок в канале. Множество цепей определяется как Nеt={ N1, ..., Nn}, где n - число цепей. Рассмотрим следующий пример: Tор ={ 1, 0, 3, 1, 4, 2, 3, 2} и Bоttоm ={ 6, 4, 6, 6, 3, 0, 5,5 }, где C=8, n=6, Nеt={ 1, 2, 3, 4, 5, 6}, элемент 0 в Tор или в Bоttоm обозначает свободный контакт. На рис. 1 показан эскиз канала с разведенными цепями.

Горизонтальные и вертикальные ограничения

При канальной трассировке не допускаются наложения вертикальных и горизонтальных сегментов цепей. Для решения этой задачи вводятся графы вертикальных и горизонтальных ограничений. Вертикальные ограничения описываются ориентированным графом вертикальных ограничений (ГВО) GV=(ENet, EV), где ENet - множество вершин, соответствующих множеству цепей Net, EV - множество направленных ребер.

Ребро (n, m) e EV существует тогда и только тогда, когда цепь n должна быть расположена выше цепи m для предотвращения наложений вертикальных сегментов цепей. Например, на рис. 2 в ГВО существует путь из вершины 1 в вершину 6, это означает что цепь 1 должна быть размещена выше цепи 6, для того, чтобы не было наложений вертикальных сегментов на 1 и 4 контактах(см. рис.1). Чтобы задача решалась в рамках классической постановки, граф GV должен быть ациклическим, в противном случае задача может быть решена только с введением изломов, а это противоречит условиям классической постановки задачи канальной трассировки.


Рис.2

В нашей работе мы будем использовать расширенный граф вертикальных ограничений (РГВО) GRV = (ENеt, ERV), где ENet - множество вершин, соответствующих множеству цепей Net, ERV - множество направленных ребер. Ребро (n, m) eERV, существует тогда и только тогда, когда в ГВО существует путь из вершины n в вершину m. Например, на рис.2 в ГВО есть путь из вершины 4 в вершину 5 через вершину 3. Следовательно в РГВО существует ребро (4,5).

Горизонтальные ограничения представлены неориентированным графом горизонтальных ограничений (ГГО) GH = (ENet,EH), где ENet - множество цепей, EH - множество ребер. Ребро (n, m) e EH существует, тогда и только тогда, когда магистрали для n и m должны быть разными для исключения наложения горизонтальных сегментов n и m. Например, на рис. 2 в ГГО существует ребро (1,4), это означает что цепь 1 не может размещаться на одной магистрали с цепью 4 (см. рис. 1).

Генетический алгоритм для канальной трассировки

Генетический алгоритм - это итерационная процедура, которая обрабатывает группу хромосом (решений) называемую популяцией [8-13]. Число хромосом в популяции называется размером популяции М. Каждая хромосома состоит из генов. Гены размещены в определенных частях хромосомы, которые называются "лоци". Каждый ген-хромосом может быть в нескольких состояниях, называемых "аллелями". Терминология, использованная здесь, заимствована из естественной генетики. Приведем соответствие терминов ГА и классической задачи канальной трассировки.

Фенотип - топология расположения цепей на кристалле.

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

Хромосома - кодированное представление одного варианта топологии. Хромосома состоит из генов.

Ген - элемент хромосомы, задающий некоторый фрагмент топологии.

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

Фитнесс - целевая функция, определяющая качество решения задачи.

Генерация - один цикл работы генетического алгоритма.

Генетический алгоритм требует, чтобы хромосомы оценивались с точки зрения целевой функции задачи. Целевая функция оценивает какие-либо качества решения соответствующего данной хромосоме (длину цепей, число магистралей и т.д.). Как было указано выше, генетический алгоритм обрабатывает популяцию решений, закодированных в хромосомы. В процессе обработки популяции, к ней последовательно применяются различные генетические операторы, такие как кроссинговер, мутация с заданными вероятностями (PC и PM соответственно) и другие операторы. Затем проводится редукция увеличившейся популяции для отбора лучших решений, которые составят следующее поколение, после чего цикл (генерация) повторяется. Число таких циклов называется числом генераций T. Отметим, что может быть построена большое число архитектур реализации генетического поиска. В нашем подходе выбрана стандартная схема генетического поиска.

Структура алгоритма

Для нашего генетического алгоритма принята следующая схема.

Шаг 1. Определение размера популяции M, числа генераций T, вероятности кроссинговера PC и вероятности мутации PM.

Шаг 2. Задание случайным образом начальной популяции П(0) размером M.

Шаг 3. t=0 ( t = 1,2, ..., T ).

Шаг 4. Выбор случайным образом M пар хромосом из популяции П(t) и применение операции кроссинговера к каждой паре с заданной вероятностью PC.

Шаг 5. Применение операции мутации к каждой хромосоме популяции П(t) с заданной вероятностью PM.

Шаг 6. Отбор M хромосом с наилучшим значением целевой функции из получившейся популяции П(t) в новую популяцию П(t+1).

Шаг 7. t=t+1.

Шаг 8. Если t

Шаг 9. Вывод хромосомы с наилучшим значением целевой функции.

Далее в статье рассмотрены генетические операции, применяемые в нашем генетическом алгоритме.

Кодирование хромосомы

Таблица 1
Цепь m 1 1 1 1 1 2 2 2 2 3 3 3 4 4 5
Цепь n 2 3 4 5 6 3 4 5 6 4 5 6 5 6 6
Ген * 0 0 * 0 0 * 0 * 1 0 0 * 0 *

В данной работе используется представление хромосомы, основанной на топологическом описании канала, т.е. хромосома описывает взаимное расположение цепей. Для этого каждой паре цепей (m,n), где m ё n, ставится в соответствие ген, который может принимать три состояния: 0 - если цепь m должна располагаться выше n, 1 - если цепь m должна располагаться ниже n и * - если их взаимное расположение не имеет значения или определяется из взаимного расположения остальных цепей (это происходит, если цепи не имеют горизонтальных ограничений). Для нашего примера (см. рис.1) хромосома будет иметь вид, показанный в табл.1.

В строке таблицы, обозначенной как "Ген", записано значение гена в хромосоме, задающей расположение, показанное на рис. 1. Очевидно, что длина хромосомы при таком кодировании

где N - число цепей.

Как мы видим, длина хромосомы получается достаточно большой (для примера на рис. 1 она равна 15), что не приемлемо. Поэтому для уменьшения длины хромосомы используется анализ РГВО и ГГО. Уменьшение длины получается за счет того, что взаимное расположение некоторых пар цепей уже зафиксировано в РГВО, и изменение этого расположения приводит к образованию нарушений в канале, т.е. к наложению вертикальных сегментов цепей в канале, что ведет к образованию "мертвой" хромосомы (т.е. такой, из которой не может быть получено решение, удовлетворяющее заданным требованиям). Второй прием, позволяющий уменьшить длину хромосомы, основывается на том, что если цепи не имеют горизонтальных ограничений, то их взаимное положение либо не важно, либо определяется из соотношений с остальными цепями. Такие соотношения отмечены знаком "*". Следовательно, длина хромосомы

L=NGO-NRVO,

где NGO - число горизонтальных ограничений; NRVO - число вертикальных ограничений в РГВО.

В примере для пар цепей (1,6), (2,5), (3,4), (3,5), (3,6), (4,6) взаимное расположение жестко задано РГВО, а взаимное расположение цепей в парах (1,2), (1,5), (2,4), (2,6), (4,5), (5,6)

Цепь m 1 1 2
Цепь n 3 4 3
Ген 0 0 0
не имеет значения, поскольку цепи в этих парах не конфликтуют по горизонтали. Поэтому в примере хромосома будет выглядеть следующим образом :

Ее длина будет равна 3.

Получение из хромосомы эскиза канала с разведенными цепями

Для получения из хромосомы эскиза канала с разведенными цепями используется граф топологии ( ГТ ). ГТ - это ориентированный граф

GT = ( Nеt, ET ),

где Net - множество цепей; ET - множество направленных ребер, описывающих взаимное расположение цепей в канале.

Ребро ( m, n ) e ET, существует тогда и только тогда, когда цепь m должна быть расположена в канале выше цепи n, т.е. на магистрали с меньшим номером. ГТ строится из хромосомы по следующему алгоритму.

Шаг 1. Преобразуем РГВО GRV в ГТ GT.

Шаг 2. i=1.

Шаг 3. Если ребро ( mi , ni ) не принадлежит GT , то это ребро добавляется к GT.

Шаг 4. Проверяем для всех вершин k существование пути из вершины mi к вершине k, при условии, что k = 1, ... , N, k ё mi и k ё ni и не существует ребра ( mi, k ) в GT. Если такой путь существует, то добавляем ребро ( mi, k ) к GT.

Шаг 5. Если i # L, то увеличиваем i на 1 и переходим к Шагу 3.

Шаг 6. Считаем построение ГТ завершенным.

Канал восстанавливается из хромосомы следующим образом.

Шаг 1. Строим по хромосоме ГТ GT.

Шаг 2. i=0.

Шаг 3. Находим вершины, у которых есть только исходящие дуги. Размещаем их на магистрали с номером i или на магистрали с меньшим номером, если это возможно, и удаляем эти вершины из графа.

Шаг 4. i = i + 1.

Шаг 5. Если граф топологии GT не пустой возвращаемся к Шагу 3.

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

Шаг 7. Возвращаем полученный образец размещения цепей в канале шириной i.

Например, пусть задана хромосома А=000. Рис. 1 показывает полученный образец трассировки, который является оптимальным решением для примера. Если A=010 (отличие от предыдущего решения заключается в том, что цепь 4 располагается выше цепи 1), то эскиз канала с разведенными цепями для такой хромосомы показан на рис. 3.

Целевая функция оценки хромосомы

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

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

F(A)=(UsedTrаck(A)+2)*С+

TоtаlVertSeg(A),

где C - число контактов.

Программная функция UsedTrаck(A) определяет число магистралей, занимаемых каналом, полученным при восстановлении из хромосомы A, а программная функция TоtаlVertSeg(A) определяет длину вертикальных сегментов цепей в полученном решении.

Длина вертикальных сегментов цепи определяется как расстояние между контактами и переходными отверстиями, которые соединяют вертикальные и горизонтальные сегменты. Например, для канала на рис.1 число занятых магистралей равно 4, длина вертикальных сегментов равна 22. Таким образом целевая функция хромосомы F(A)=(4+2)*8+22=70, а для канала, показанного на рис. 3, F(A)=72.

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

Кроссинговер и мутация

Согласно структуре генетического алгоритма все хромосомы(случайно полученные решения) оцениваются описанной выше целевой функцией. Далее, согласно процедуре селекции, производится построение списка упорядоченных хромосом. На основе анализа этого списка производиться подбор пар хромосом на основе элитной селекции (хромосома с лучшим значением ЦФ и случайно выбранная хромосома). После подбора пар применяется ОК с вероятностью РC к каждой паре хромосом. Исходные хромосомы называются "родители", а хромосомы, полученные после соответствующих операторов ГА - "потомки". Алгоритм применения ОК реализован следующим образом.

Шаг 1. i=0.

Шаг 2. Выбрать хромосому с лучшим значением ЦФ, как первого родителя.

Шаг 3. Выбрать произвольно второго родителя.

Шаг 4. Сгенерировать случайное число rnd в интервале [0,1].

Шаг 5. Если rnd < PC, то применить ОК к выбранным хромосомам и добавить получившихся потомков к популяции.

Шаг 6. i = i + 1.

Шаг 7. Если i < M, то перейти к шагу 2.

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

Рассмотрим пример реализации ОК. Пусть вертикальная линия означает точку разреза ОК:

Родитель 1: 0 | 1 | 0 Значение ЦФ: 72,

Родитель 2: 1 | 0 | 1 Значение ЦФ: 77,

________________________________

Потомок 1: 0 | 0 | 0 Значение ЦФ: 70,

Потомок 2: 1 | 1 | 1 Значение ЦФ: 77.

Потомок 1(потомок 2) получен с учетом родителя 1 (родителя 2), как первого родителя и родителя 2 (родителя 1), как второго. В данном случае получен потомок (потомок 1) с лучшим значением ЦФ, чем значение ЦФ родителей. Топология трассировки, соответствующая родителю 1, показана на рис. 3, и родителю 2 - на рис. 4. Топология трассировки, соответствующая потомку 1, показана на рис. 1, а потомок 2 после декодирования хромосомы аналогичен родителю 2.

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

Шаг 1. i=0.

Шаг 2. Сгенерировать случайное число rnd в интервале [ 0, 1 ].

Шаг 3. Если rnd < PM, то применить ОМ к i-ой хромосоме популяции M.

Шаг 6. i = i + 1.

Шаг 7. Если i < M, то перейти к Шагу 2.

Смысл оператора мутации - это введение добавочных изменений в популяцию. В нашей структуре ГА выбрана "точечная" мутация. Она заключается в изменении одного произвольного гена в хромосоме с вероятностью PM. Это происходит следующим образом. Один из генов хромосомы выбирается случайно и затем меняет свое значение на противоположное. Следующий пример показывает реализацию этого механизма:

Хромосома (до применения ОМ): 0 ( 1 ) 0

Значение ЦФ: 72

Хромосома(после применения ОМ): 0 ( 0 ) 0

Значение ЦФ: 70

Выбранная точка мутации показана в скобках. После применения ОМ, в данном случае, получается хромосома с лучшим значением ЦФ. На рис. 3 показана топология канала, соответствующего хромосоме до применения ОМ, а на рис. 1 - после применения ОМ.

Экспериментальные результаты

Генетический алгоритм канальной трассировки реализован на языке Си++ для IBM-совместимых PC.

Теоретическая временная сложность алгоритма составляет:

T*(M*PC*2)*PM*O(N2),

где T - число поколений; M - размер популяции; PC -вероятности кроссинговера; PM - вероятность мутации; O(N2) - временная сложность декодирования хромосомы; N - число цепей.

Таблица 2
Номер теста Число контактов Число цепей Оптималь-
ное число магистралей		 Оптимальная длина цепей Среднее отклонение от оптимального результата в %
0 80 51 8 773 0.0006%
1 80 38 10 1072 0.0000%
2 80 36 9 1076 0.0005%
3 80 37 10 1134 0.0000%
4 100 66 10 1282 0.9204%

В экспериментах, проведенных для оценки существующих канальных трассировщиков, решающих задачу в аналогичной постановке [2,4,17,18], оценивалось только минимальное число магистралей, полученных алгоритмом, а такой параметр, как длина соединений, не учитывался. Для определения оптимальной длины соединений нами использовался динамический алгоритм [7], который находит оптимальное решение по числу магистралей и длине соединений. Алгоритм [7] для решения стандартных тестов использоваться не может из-за его большой пространственной и временной сложности. Поэтому для экспериментальной проверки алгоритма были разработаны примеры. Для этих примеров были найдены оптимальные результаты по числу магистралей и длине соединений. Параметры выбранных тестов (число контактов, число цепей, оптимальное число магистралей и оптимальная длина цепей) представлены в табл. 2.

Затем к этому же набору тестов был применен генетический алгоритм. Было проведено по 100 испытаний для каждого примера с различными начальными установками генератора случайных чисел. Испытания проводились при следующих установках генетических параметров: M=50, T=20, PC=1,00 и PM=0,10, которые были выбраны после соответствующего анализа. В экспериментах был применен "элитный" отбор, т.е. из популяции, полученной после проведения ОК и ОМ, выбирается M хромосом с наименьшим значением ЦФ.

Во всех случаях были получены оптимальные решения по числу магистралей. Среднее отклонение от оптимального результата по длине соединений составило менее 1%. Результаты представлены в табл. 2 в графе "Среднее отклонение от оптимального результата".

Затем был проведен ряд экспериментов для выбора таких генетических параметров, как PM (вероятность мутации) и PC (вероятность кроссинговера), при которых среднее отклонение от оптимального результата будет минимально. Подбор параметров осуществлялся на тесте 4, для которого было получено наибольшее отклонение от оптимального результата (см. табл.2). Первоначально был проведен подбор оптимального значения PC. Для этого PM была зафиксирована равной 0,1, а PС изменялась от 0 до 1 с шагом 0,1. Наименьшее среднее отклонение от оптимального результата (0,9204%) было получено при вероятности кроссинговера равной 1 (рис. 5).

После этого, была зафиксирована PС равная 1, а PM изменяла значение от 0 до 1 с шагом 0,10. Полученные результаты показаны на рис. 6. Эксперименты показали, что наименьшее среднее отклонение от оптимального результата (0,80%), полученное в результате 100 испытаний для каждого значения PM, были при PM равной 0,3.

Таблица 3
Тест EA EP GA1 GA2
Ex1 12 12 12 12
Ex3b 17 17 17 17
Ex3c 18 18 18 18
Ex4b 17 17 17 17
Ex5 20 20 20 20

Для сравнения нашего алгоритма с аналогичными были использованы стандартные тесты Ex1, Ex3b, Ex3c, Ex4b и Ex5 из работы [2]. Для всех этих тестов были найдены оптимальные решения по числу магистралей алгоритмом. Минимальное число магистралей, найденное различными алгоритмами канальной трассировки, представлено в табл.3. Сравнение по длине соединений провести не представляется возможным, т.к. эти алгоритмы не оптимизируют этот параметр.

В табл.3 EA - алгоритм канальной трассировки, описанный в работе [2], EP - эволюционный алгоритм, описанный в - [7], GA1 - генетический алгоритм, описанный в - [11], GA2 - представленный алгоритм.

Заключение

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

Литература

  1. N. Shervani. Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, USA, 1995. 538 p.
  2. Yoshimura, T. and Kuh, E.S. Efficient algorithms for channel routing, IEEE Trans. Comput.-Aided Des. Integrated Circuits & Syst., vol.1, no.1, pp.25-35,1982.
  3. Burstein M. Channel routing, Layout Design and Verification, pp. 133-167, Elsevier Science, 1986.
  4. Shimamoto T. and Sakamoto A. Neural computation for channel routing using Hopfield neural network model, Trans. IEICE, vol.E72, no.12, 1989, pp.1360-1366.
  5. Hsiao-Ping Tseng and K. Sechen. A Gridlless Multi-layer Channel Router Based on a Combined Constraint Graph and Tile Expansion Approach. ISPD-96, 1996, pp. 210-217.
  6. Казенов Г.Г, Марченко А.М. Абстрактный эволюционный алгоритм синтеза СБИС, Известия ТРТУ, №3, Таганрог, 1996, с. 112.
  7. Лебедева Б.К. Канальная трассировка на основе динамических принципов и методов минимизации комбинаторной размерности. Межведомственный тематический научный сборник "Интеллектуальные САПР", вып. 5, Таганрог, 1995, с. 11-21.
  8. J. Holland. Adaptation in natural and artificial systems. University of Michigan Press Ann Arbor, USA, 1975.
  9. Goldberg D.E. Genetic Algorithm in Search, Optimization & Machine Learning, Addison-Westley, 1989.
  10. Davis L (Ed). Handbook of Genetic Algorithms. Van Nostrand Reinhoed, New Jork, USA, 1991.
  11. Батищев Д.И. Генетические алгоритмы решения экстремальных задач, Учебное пособие, Воронеж, 1995.
  12. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, 1992.
  13. Курейчик В.М. Генетические алгоритмы и их применение в САПР, Интеллектуальные САПР. Межведомственный тематический научный сборник, Таганрог, 1995, с. 7-11.
  14. Cohoon J.P. and Paris W.D. Genetic placement, IEEE Trans. Comput.-Aided Des. Integrated Circuits & Syst., vol.6, no.6, 1987, pp.956-964.
  15. 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.
  16. 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 Engineering, Design and Control, Plymouth, UK, 1996, pp. 294-296.
  17. Liu X., Sakamoto A., Shimamoto T. Restructive Channel Routing with Evolution Programs, Trans. IEICE, vol.E76-A, no.10, 1993, pp.1738-1745.
  18. Rahmani A.T. and Ono N. A Genetic Algorithm for Channel Routing Problem, in Proc. 5th Intl. Conf. on GAs, 1993, pp. 494-498.
  19. Davidenko V.N., Kureichik V.M., and Miagkikh V.V. Genetic Algorithm for Restrictive Channel Routing Problem, Proc. of the 7th International Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1997, pр. 636-642.
  20. J. Lieng, K. Thulasiraman A Genetic Algorithm for Channel Routing in VLSI Circuits, Evolutionary Computation, 1(4), MIT, 1994, pp. 293-311.
  21. Лебедев Б.К. Канальная трассировка на основе генетических процедур, Известия ТРТУ, №3, Таганрог, 1997, с. 53-60.