Витиска Николай Иванович. Профессор кафедры «Информационные системы» ГОУВПО «Таганрогский государственный педагогический институт».

Гудилов Сергей Витальевич. Аспирант ГОУВПО «Таганрогский государственный педагогический институт».

Параллельная реализация генетических операторов в многоступенчатой коммутационной сети с кольцевой архитектурой

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

Хромосомы – это альтернативные кодированные решения ГА, состоящие из генов Рi = {g1, g2,…, gv}. Гены могут иметь числовые или функциональные значения. Генетический материал обычно кодируется на основе двоичного алфавита {0,1}, хотя можно использовать десятичные, буквенные и другие алфавиты [1]. Примером закодированной хромосомы длины восемь на основе двоичного алфавита может служить хромосома Рi = (01001101).

Наиболее часто применимыми операторами ГА являются различные виды операторов кроссинговера и мутации. Основная функция оператора кроссинговера (ОК) – создавать хромосомы потомков на основе различного скрещивания родителей относительно точки кроссинговера (ТК), определяемой случайным образом. Оператор мутации (ОМ) необходим для выхода из локальных экстремумов, которые могут привести к потере решения еще на этапе его поиска. Обычно ОМ является одноточечным оператором, который случайно выбирает точку мутации (ТМ) в хромосоме и меняет местами расположенные рядом гены [1].

С целью увеличения производительности применяется разделение вычислительной системы на блоки, выполняющие определенную часть операций. Для соединения большого количества процессоров, блоков или распределенной памяти используются различные коммутаторы. В целях сокращения числа коммутирующих элементов (узлов сети) применяются многоступенчатые сети (Multistage Interconnection Networks), построенные на простых коммутирующих элементах размером 2х2 или более сложных элементах 3х3 и т.д. Состояние коммутирующего элемента определяется посредством кодов управления. При значении кода управления «0» – узел переключается на соединение с верхним выводом, а при «1» – с нижним, как показано на рис. 1.

а) б)

Рис. 1. Коммутирующий элемент 2х2 в состояниях «прямо» а) и «накрест» б)

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

1. Перестроение сети MCRB в режим параллельной передачи с сокращением неиспользуемых ступеней при реализации операторов кроссинговера и мутации

Возможность совмещения передачи данных с реализацией операторов кроссинговера и мутации была исследована в [3] на примере мультипроцессоров UMA с многоступенчатыми сетями. Среди различных многоступенчатых коммутирующих структур, для реализации операторов кроссинговера и мутации была выбрана сеть MCRB (Multistage Chordal Ring Based network) [4], изображенная на рис. 2. Сеть MCRB относится к топологиям на основе функции циклического сдвига [5], при , где h – номер используемой ступени, N – количество портов в сети. Эта топология наиболее близка к условиям выполнения перестановок для реализации вышеуказанных генетических операторов, т.к. структура сети позволяет реализовать ОК в старших ступенях и ОМ в старших и младших ступенях.

а) б)

Рис. 2. Сеть MCRB, развернутая на плоскости а) и в виде группы хордальных колец б)

Для оптимизации управления с учетом условий выполнения генетических операторов, в работе [3] было реализовано перестроение сети MCRB в режим прямой передачи с изменением правил управления коммутирующими элементами. При настройке в этот режим, узлы сети по умолчанию настраиваются для прямой передачи без перестановок. При значении кода управления «0» – узел сети не изменяет своего состояния, а при «1» – узел переключается в противоположное состояние. Применение данного подхода позволило упростить структуру кода управления до отраженного кода (кода Грея) [5], который предпочтительнее обычного двоичного тем, что и изменение кодируемого числа на единицу соответствует изменению кодовой комбинации только в одном разряде. Дополнительным преимуществом данного подхода является возможность исключения из сети всех ступеней, не участвующих в коммутации с приведением сети к четырем ступеням [3].

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

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

Рис. 3. Блокировки в сети MCRB при разделении сети на три области по 5 портов и выполнении двухточечного ОК в двух соседних хромосомах и двухточечного ОМ в оставшемся пространстве

Блокировки на элементах 3,0, 3,3, 2,6, 2,7 и 1,10 возникают в случае использования одного и того же соединения или при необходимости переключения правильно настроенного элемента. Также, показана невозможность создания соединения с порта 7 на порт 2 по причине отсутствия возможных траекторий после элемента 2,3. Следовательно, создать универсальную сеть на основе оригинальной сети MCRB для одновременной обработки хромосом количеством более двух – невозможно, т.к. необходимо наличие обратных соединений между узлами сети. Наличием таких соединений отличается сеть Augmented MCRB [4], изображенная на рис. 4.

Рис. 4. Сеть Augmented MCRB в режиме прямой передачи

В сети AMCRB для организации коммутации с применением коммутирующих элементов 3х3 необходимо учесть, что число их возможных состояний, а также размер кода управления будут больше. Для сокращения разнообразия кодов управления – мы можем применить использованный ранее принцип настройки кода управления по умолчанию [3, 6]. На рис. 5 показаны четыре различных состояния управления элементом, достаточных для реализации операторов кроссинговера и мутации.

Рис. 5. Виды коммутации узлов сети Augmented MCRB при различных кодах управления

Структура сети AMCRB позволяет реализовать генетические операторы в любых ступенях, следовательно, функции старшей ступени могут быть реализованы дополнительными соединениями в остальных ступенях. В результате, мы можем отказаться от использования старшей ступени, содержащей группу самых длинных соединений и создать более компактную сеть. На рис. 6 показана возможность параллельной обработки трех хромосом в сокращенной сети Augmented MCRB с условиями и упрощениями, аналогичными показанному на рис. 3 неудачному примеру для сети MCRB.

Рис. 6. Обработка трех хромосом в сокращенной сети Augmented MCRB

На рис. 6 показаны два варианта организации коммутируемых соединений между похожими портами a2X>b2X и a2Y>b2Y. Первая траектория проходит через узлы 3,2>2,6>1,8>0,7, а вторая – через узлы 3,3>2,7>1,7>0,8.

Заключение

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

2. Появилась возможность создания соединения по более чем одной траектории, что позволяет использовать альтернативные траектории и повышает отказоустойчивость сети Augmented MCRB.

3. Для сокращенной сети Augmented MCRB показаны возможности одновременной обработки более чем двух хромосомом произвольного размера.

На примере данной работы показаны различные способы оптимизации многоступенчатых сетей, позволяющие расширить их область применения. Многоступенчатые сети позволяют создавать соединения до окончания подготовки кодированного массива хромосом и по настроенным каналам произвести требуемые перестановки совместно с передачей данных в другие специализированные устройства для дальнейшей обработки. Сокращенная сеть MCRB найдет применение в компактных стационарных и автономных системах с постоянным размером входных данных или системах с ограничениями на объем оборудования. Сокращенная сеть Augmented MCRB подходит для решения широкого круга задач с применением ГА при динамически изменяющихся размерах данных для обработки. В сочетании с оптимизацией, применение многоступенчатых сетей в качестве дополнительной коммутационной сети позволит создавать надежные системы возможностью быстрой реконфигурации для параллельного выполнения проблемно-ориентированных программ.

Литература

1. В.В. Курейчик. Эволюционные методы решения оптимизационных задач. Таганрог: Изд-во ТРТУ, 1999. 99 с.

2. И.А. Каляев, И.И. Левин, Е.А. Семерников, В.И. Шмойлов. Реконфигурируемые мультиконвейерные вычислительные структуры. Ростов-на-Дону: Изд-во ЮНЦ РАН, 2008. 393 с.

3. Н.И. Витиска, С.В. Гудилов. Исследование аппаратной реализации основных операторов генетических алгоритмов в многоступенчатых сетях. // Вестник компьютерных и информационных технологий. – Издательство «Машиностроение», 2010. - № 9. С 43 – 48.

4. A.C. Aljundi, J.L. Dekeyser, M.T. Kechadi, I.D. Scherson. A universal performance factor for multi-criteria evaluation of multistage interconnection networks // Future Generation Computer Systems, August 2006. ISSN 0167-739X. P. 794–804.

5. И.С. Потемкин. Функциональные узлы цифровой автоматики. Энергоатомиздат, 1998. 320 С. ISBN: 5-283-01478-9.

6. Н.И. Витиска, В.В. Гудилов, С.В. Гудилов. Отображение операторов кроссинговера и мутации в сети MCRB. // Информационные технологии и вычислительные системы. 2011. - №1 . С 35 – 41.