Методы размещения клетки БИС

Авторы: Khushro Shahookar, Pinaki Mazumder
Название в оригинале: VLSI cell placement techniques
Перевод Т.Ю. Вовк
Источник: Khushro Shahookar, Pinaki Mazumder - VLSI cell placement techniques, 1991, p. 59-78,

2.3. Гибридный генетический алгоритм для пропорционального среза декомпозиции.

Выше указанная реализация ГА медленнее, чем алгоритмы общепринятой декомпозиции и занимают очень продолжительный период времени, для образцов, содержащих десятки тысяч ячеек и сетей, поскольку ГА необходимо большое количество поколений чтобы конвертировать хороший комплект решений. Гибридные ГА, выполняющие местную оптимизацию в каждом поколении, способны использоваться для достижения быстрейшей конвергенции, и таким образом, количество поколений может быть значительно сокращено [25]. Несмотря на то, что время прохода может быть сокращено таким образом, оно все еще обычно значительно продолжительнее, чем для других алгоритмов, поскольку каждое инициирование работы местной оптимизации может занять значительное количество времени. Данный раздел представляет эффективный гибрид генетического алгоритма, называемый Генетический алгоритм пропорционального среза (ГПСА), поскольку гиперграфическое последовательное деление пополам, применяющее пропорциональный срез в качестве системы показателей для оценки решений. Технология была разработана Буи и Муном в 1994 году [25], и псевдо-код ГПСА процедуры показан на Рис.2.11.

Алгоритм использует пропорциональный срез в качестве системы показателей для декомпозиции. Пропорциональный срез сегмента (А.В) определен как пропорция r_AB=e(A,B)/(|A|*|B|), где e(A,B) - размер среза сегмента и |A| и |B| определяют размеры блоков А и В

preprocess; /факультативная предварительная обработка /

local_improvement (offspring); /*модифицированный алгоритм Ф-М /

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

2.3.1. Генетическое шифрование.

В показанной выше процедуре ГСПА, хромосома, принадлежащая решению декомпозиции представлена как строка из нулей и единиц таким образом , чтобы количество генов в хромосоме равнялось количеству ячеек в цепм, а ген имел ”allete” 0,если он в Блоке А(говорим) и 1, иначе. Данный тип кодирования, где каждая позиция гена имеет точное значение, называется кодирование , основанное на месторасположении. Рис. 2.12 показывает пример хромосомы, в которой блоки 1,4, 6,95, 98… находятся в в блоке А, а 0,2,3,5,96,97… находятся в блоке В .

Рис.2.12 Кодирование, основанное на месторасположении

2.3.2.Селекция, скрещение и мутация.

Процедура ГСПА использует оператора генетического выбора, в котором индивидуальные строки выбраны согласно их целевым функциональным ценностям, f. Для выбора двух родителей, необходимых для репродукции, используется, предложенная Голдбергом [79] пропорциональная схема выбора . Оператор выбора может быть реализован алгоритмической формой большим количеством способов. Самый простой - создать рулетку систематического отклонения, в которой каждая текущая хромосома в популяции имеет временной интервал колеса рулетки, размером, пропорциональным его пригодности.

Операторы скрещения используются для создания нового “потомка”, комбинированием частей двух “родителей”, хромосом. Одноточечное скрещение довольно обычная вещь, однако Буи и Мун [25] показали. что пятиточечное скрещение дает хорошие результаты. В такой операции скрещения пять точек скрещения выбраны случайным способом на хромосоме, разделяя ее на шесть частей, как показано на Рис. 2.13

Состав из двух “родителей” копируется поочередно к “потомку”. Пусть это будет “Потомок 1”. В другом скрещении , “Потомок 2” создается,копированием полного значения “Родителя 2”(значимость “Родителя1” остается неизменной). ГСПА выбирает лучшего из двух “потомков”. Это объясняется следующим образом. Если два “родителя” являются почти полой копией друг друга, они представляют то же самое решение в огромной степени (только блоки изменены). В таком случае, “Потомок 1” будет иметь очень низкую оценку пригодности и, таким образом, небольшой шанс на выживание.

2.3.3. Локальные усовершенствования.

После того, как были осуществлены операции скрещения и репродукции, для выбора “потомка” применяется алгоритм локального усовершенствования.

Главная цель данного шага получить некоторое видимое улучшение в “потомке”, чем получить локальную оптимальную ценность, используя “потомка” в качестве исходного последовательного разбиения на две части. Примененная процедура локального усовершенствования является модифицированной версией Ф-М алгоритма, который имеет коэффициент сложности О(Р),где Р общее число входов, подключенный к ячейкам. Стандартный алгоритм Ф-М обычно занимает 10 прогонов чтобы конвергироваться к минимальному решению, и затем могут произойти потенциально до ?-1 ячеечных переходов в каждом прогоне, где ? общее число ячеек. Чтобы уменьшить коэффициент усиления процедуры локального усовершенствования, обычно выполняется только один прогон алгоритма Ф-М, и разрешается только фиксированное количество трансферов ячеек. Данные параметры оцениваются, чтобы приблизительно равняться |N|/6. Такая модифицированная версия Ф-М занимает только 5% времени от стандартного времени алгоритма Ф-М. Улучшая процедуру локального усовершенствования, коэффициент усиления процедуры ГСПА значительно уменьшается.

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

Это подтверждается наблюдением затем, что если размер модуля i невелик, то он не потребует много для знаменателя в коэффициенте пропорционального среза, данного в формуле :

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

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

Гибридный генетический алгоритм сравнивает пригодность «потомка» подобному (в рамках битообразного различия) родителю. Если “потомок” лучше, чем “родитель”, в таком случае, он заменяет “родителя”: в ином случае, “потомок” отвергается. Данная стратегия замены называется ?EAR. Тем не менее, спустя некоторое время, ГСПА изменяет стратегию замещения на схему, называемую COMBI. В данной схеме, если ГСПА не в состоянии заменить первого “ родителя”, он снова сравнивается с “родителем”, и только, когда “потомок” не лучше, чем “родитель”, ГСПА отвергает его. Это происходит из-за того, что исключительно схема замещения NEAR приводит к тому, что большое количество неудавшихся перемещений в последнем поколении ГСПА, замедляют конвергенцию. Случается перепад, если “потомок” отвергнут в конце генерации. Семь последовательных перепадов составляют “аут” (бейсбольным бэттерам понравится данное правило)

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