Реконфигурируемое устройство аппаратной реализации генетического алгоритма
Владельцы патента RU 2572379:
федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Донской государственный технический университет" (ДГТУ) (RU)
Изобретение относится к вычислительной технике. Технический результат заключается в снижении вычислительных затрат на проведение эволюционного поиска и обеспечении автономности функционирования объекта при принятии решений в изменяющейся среде в автономных интеллектуальных системах. Реконфигурируемое устройство аппаратной реализации генетического алгоритма содержит блок микропрограммного управления, первый вход которого связан с первым входным портом устройства, второй вход которого связан с выходом блока мультиплексоров, блок оценки решения, блок генетических операторов, блок мультиплексоров, блок отбора, блок генерации популяции, блок памяти, блок реконфигурируемого модуля, первый вход которого связан со вторым входным портом устройства, второй вход которого связан с выходом блока мультиплексоров, первый выход которого связан с блоком мультиплексоров, второй выход которого связан с выходным портом устройства, блок реконфигурируемого модуля предназначен для динамической реконфигурации цифровых комбинационных логических схем. 5 ил.
Предлагаемое устройство относится к аппаратным системам, реализующим эволюционные алгоритмы. Устройство может использоваться в эволюционных инструментальных комплексах, исследованиях при проектировании виртуальных аппаратных средств (Virtual Hardware) и в области самоадаптирующихся и реконфигурируемых аппаратных средств (Self-Adapting and Reconfigurable Hardware).
Устройство предназначено для снижения вычислительных затрат на проведение эволюционного поиска и обеспечения автономности функционирования объекта при принятии решений в изменяющейся среде в автономных интеллектуальных системах.
Известно устройство:
"Genetic algorithm machine and its production method, and method for executing a genetic algorithm" Patent number: US 5970487, Application number: US 19970910103 19970813. Универсальная не проблемно-ориентированная аппаратная структура для выполнения генетического алгоритма (ГА), увеличивающая скорость выполнения ГА посредством памяти популяции, первого и второго регистра хромосомы, модуля кроссинговера (crossover), оператора мутации (mutation) и компаратора отбора. Не проблемно-ориентированный аспект аппаратной структуры становится проблемно-ориентированным без изменений состава структуры при включении в структуру схемы проблемно-ориентированной функции фитнесса (функции пригодности) для оценки хромосом, представляющих потенциальное решение задачи. Аппаратная структура таким образом становится пригодной для различных проблемно-ориентированных аспектов схем проблемно-ориентированных функций.
Признаками аналога, совпадающими с признаками заявляемого изобретения, являются:
память популяции, которая хранит родительскую и дочернюю хромосомы в области одного пространства памяти;
селектор для выбора хромосом из числа хромосом в популяции и выполнения операции скрещивания на множестве родительских хромосом для создания новых хромосом и выход новых хромосом как дочерних хромосом;
компаратор отбора для регулирования критерия выживания мутированных хромосом, основанного на вычисленном значении фитнесса;
компаратор отбора, сравнивающий оцененное значение фитнесса в регистре хромосом и регистре наименьшего значения фитнесса и передающий оцененное значение фитнесса и соответствующей оцененной хромосомы к указанной памяти популяции для замены хромосомы с меньшим значением фитнесса в популяции, основываясь на результате сравнения.
Причиной, препятствующей получению технического результата, является наличие совокупности оценочных регистров для объединения и сохранения количества непокрытых элементов, что приводит к усложнению алгоритма управления и вызывает дополнительные временные затраты, связанные с задержкой при записи и считывании на регистрах.
Известно устройство:
RU 2294561C2 2007 г. «Устройство аппаратной реализации вероятностных генетических алгоритмов с параллельным формированием хромосомы».
Признаками аналога, совпадающими с признаками заявляемого изобретения, являются:
блок микропрограммного управления;
блок генерации популяции;
блок мультиплексоров, предназначенный для коммутации блоков устройства между собой;
блок памяти, который хранит родительскую и дочернюю хромосомы в области одного пространства памяти.
Причинами, препятствующими получению технического результата, являются отсутствие операторов мутации, инверсии и кроссинговера, что препятствует использованию устройства в задачах, для решения которых применяются классические эволюционные алгоритмы.
Известно устройство:
NIE Xin, LI Yuan-xiang, KE Peng. Research on the Architecture of Intrinsic Evolvable Digital Circuits, JNIT: Journal of Next Generation Information Technology, Vol. 2, No. 2, pp. 8-14, 2011.
Признаками аналога, совпадающими с признаками заявляемого изобретения, являются:
реконфигурируемый модуль для внутренней эволюции цифровых схем.
Причинами, препятствующими получению технического результата, является применение в качестве универсального реконфигурируемого логического элемента блоков памяти. При использовании блоков памяти для перезаписи их внутреннего содержимого требуется дополнительное время, что снижает производительность системы в целом.
Из известных технических решений наиболее близким по технической сущности к заявляемому объекту является RU 2447503C1 2012 г. «Устройство аппаратной реализации эволюционного алгоритма с нечеткими операторами».
Признаками прототипа, совпадающими с признаками заявляемого изобретения, являются:
блок микропрограммного управления;
блок мультиплексоров, предназначенный для коммутации блоков устройства между собой;
блок памяти, который хранит родительскую и дочернюю хромосомы в области одного пространства памяти;
блок генетических операторов;
блок оценки решения - вычислитель значения функции фитнесса. Используется два вычислителя, чтобы вычислять значение фитнесса индивидуумов параллельно.
Причинами, препятствующими получению технического результата, являются отсутствие реконфигурируемого модуля, что препятствует использованию устройства в самоадаптирующихся и реконфигурируемых эволюционных аппаратных средствах.
Задача, на решение которой направлено заявляемое изобретение: снижение вычислительных затрат на проведение эволюционного поиска и обеспечение автономности функционирования объекта при принятии решений в изменяющейся среде при использовании в автономных интеллектуальных системах, обеспечение возможности использования в качестве аппаратного устройства в эволюционных инструментальных комплексах, в робототехнике, исследованиях в области саморазвивающихся и самоадаптирующихся аппаратных средств, исследованиях в области построения адаптивных систем управления и принятия решений, в области автоматизации управления, повышения эффективности оптимизационных задач и т.п.
Технический результат достигается тем, что в реконфигурируемое устройство аппаратной реализации генетического алгоритма, содержащее блок микропрограммного управления, первый вход которого связан с первым входным портом устройства, второй вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок оценки решения, вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок генетических операторов, вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок мультиплексоров, первый вход которого связан с выходом блока микропрограммного управления, второй вход которого связан с выходом блока оценки решения, третий вход которого связан с выходом блока генетических операторов, четвертый вход которого связан с выходом блока отбора, пятый вход которого связан с выходом блока генерации популяции, шестой вход которого связан с выходом блока памяти, седьмой вход которого связан с выходом блока реконфигурируемого модуля, первый выход которого связан с входом блока микропрограммного управления, второй выход которого связан с входом блока оценки решения, третий выход которого связан с входом блока генетических операторов, четвертый выход которого связан с входом блока отбора, пятый выход которого связан с входом блока генерации популяции, шестой выход которого связан с входом блока памяти, седьмой выход которого связан с входом блока реконфигурируемого модуля, блок отбора, вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок генерации популяции, вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок памяти, вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок реконфигурируемого модуля, первый вход которого связан со вторым входным портом устройства, второй вход которого связан с выходом блока мультиплексоров, первый выход которого связан с блоком мультиплексоров, второй выход которого связан с выходным портом устройства, согласно изобретению введен блок реконфигурируемого модуля, предназначенный для динамической реконфигурации цифровых комбинационных логических схем.
Реконфигурируемое устройство аппаратной реализации генетического алгоритма поясняется чертежами, где
на фигуре 1 приведена структурная схема реконфигурируемого устройства аппаратной реализации генетического алгоритма,
на фигуре 2 приведена структурная схема алгоритма функционирования устройства,
на фигуре 3 приведен пример реализации логической функции «ИСКЛЮЧАЮЩЕЕ ИЛИ» на мультиплексоре 4→1,
на фигуре 4 приведена принципиальная схема реконфигурируемого логического блока,
на фигуре 5 приведена структурная схема реконфигурируемого модуля.
Блок микропрограммного управления содержит модуль памяти микрокоманд для управления устройством и производит управление работой устройства посредством генерации 32-битной команды управления. Каждый бит отвечает за управление работой соответствующего блока или модуля в зависимости от режима функционирования алгоритма, а также производит приоритетную обработку внутренних и внешних прерываний и переход к соответствующему режиму функционирования алгоритма.
Блок оценки решения производит вычисление значения целевой функции для входных значений хромосом и устанавливает на выходе вычисленные значения.
Блок генетических операторов выполняет операции кроссинговера и мутации над хромосомами. Оператор кроссинговера выполняет деления двух хромосом на части и осуществляет обмен. В результате на выходе получаются две новые хромосомы. Оператор мутации выполняет изменение одного гена хромосомы. Номер гена выбирается случайным образом.
Блок мультиплексоров обеспечивает коммутацию между всеми блоками устройства.
Блок отбора выполняет отбор хромосом с лучшим (большим) значением критерия, поступающих на вход блока, при этом на выход устанавливаются адреса хромосом.
Блок генерации популяции выполняет параллельную генерацию бит хромосомы. Параллельная генерация бит хромосомы выполняется посредством применения генераторов псевдослучайной двоичной последовательности.
Блок памяти предназначен для хранения хромосом и значений целевой функции.
Блок реконфигурируемого модуля предназначен для динамической перестройки комбинационных логических схем.
Работает устройство следующим образом (Фиг. 2). Вначале случайно генерируется популяция хромосом (закодированные схемные решения для реконфигурируемого модуля). Каждый бит в хромосоме определяет некоторую архитектурную особенность реконфигурируемой аппаратной системы. Затем каждая хромосома должна быть оценена на степень «пригодности», которая определяет, насколько близко она к решаемой задаче. После этого хромосомы подвергаются различным генетическим операторам, которые создают в популяции новые решения. Этот процесс повторяется до тех пор, пока не будет найдено лучшее решение или не будет прерван на определенном количестве итераций.
В качестве универсального реконфигурируемого логического элемента для реализации комбинационных схем различной сложности в реконфигурируемом модуле используется мультиплексор. При этом управляющие входы мультиплексора используются в качестве информационных, а информационные - в качестве настроечных.
В простейшем случае на базе мультиплексора можно реализовать комбинационное устройство с числом переменных, равным числу управляющих входов n. Если число аргументов логической функции равно n, то число различных сочетаний (наборов) значений аргументов составляет 2", а число различных функций n аргументов равно 22π.
На Фиг. 3 приведен пример реализации логической функции «ИСКЛЮЧАЮЩЕЕ ИЛИ» на мультиплексоре 4→1. Переменные X1 и Х2 подаются на управляющие входы, а настройка на реализуемую функцию производится путем подачи логических уровней «0» и «1» на информационные входы. При всевозможных комбинациях входных переменных X1 и Х2 на выходе мультиплексора появляется «1» только для двух комбинаций X1 Х2 и X1 Х2. Возможна также реализация логических функций с большим числом переменных.
Применение мультиплексоров позволяет реализовать с минимальными аппаратными затратами устройства комбинационного типа непосредственно по таблице истинности, избежав при этом этап минимизации логической функции.
В состав реконфигурируемого логического блока (РЛБ) входят 3 мультиплексора и один 10-битный конфигурационный регистр (Фиг. 4). Мультиплексор Мuх3 используется в качестве универсального реконфигурируемого двухвходового логического элемента. На управляющие входы мультиплексора Мuх3 подаются выходные сигналы с мультиплексоров Mux1 и Мuх2, предназначенных для организации динамически меняющихся связей с другими РЛБ, входящими в состав реконфигурируемого модуля (РМ), структурная схема которого представлена на Фиг. 5.
Реконфигурируемый модуль представляет собой матрицу из РЛБ. Число строк матрицы соответствует количеству информационных входов мультиплексоров Mux1 и Мuх2 в РЛБ. Количество столбцов не ограниченно. Входы первого столбца РЛБ соединены с входами РМ. Входы второго столбца РЛБ соединены шиной с выходами первого и так далее. Каждый логический элемент в РЛБ может быть соединен с любым логическим элементом в предыдущем столбце.
Заявляемое устройство позволяет добиться сокращения времени функционирования алгоритма и требуемых аппаратных ресурсов; применять в автономных системах; использовать в системах реального времени, исследованиях при проектировании "виртуальных аппаратных средств" (Virtual Hardware), "искусственной жизни" (Artificial Life) и "самоадаптирующихся и реконфигурируемых аппаратных средств" (Self-Adapting and Reconfigurable Hardware), исследованиях в области построения адаптивных систем управления и принятия решений, в области автоматизации управления, повышения эффективности оптимизационных задач и т.п.
Заявляемое устройство выполнено в виде единого кристалла ПЛИС. Ниже представлены основные временные характеристики устройства при тактовой частоте 300 МГц:
- инициализация всех необходимых параметров - 55 нс;
- генерация популяции на 256 особей при параллельном вычислении целевой функции и функционировании блока отбора - 0.5 мкс;
- время одного итерационного цикла генетического алгоритма (популяция =256, разрядность хромосомы 32 бит) составляет 1.7 мкс.
Основные параметры проектирования:
- производитель ПЛИС (FPGA): Altera;
- семейство: Arria GX;
- тип кристалла: EP1AGX50;
- максимальная частота функционирования устройства: 300 МГц;
- необходимое количество логических ячеек - 2960;
- необходимый объем внутренней памяти - 20.256 bit.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Патент США US 5970487, 1997 г.
2. Патент РФ RU 2294561 C2, 2007 г.
3. Патент РФ RU 2447503 C1, 2012 г.
4. NIE Xin, LI Yuan-xiang, KE Peng. Research on the Architecture of Intrinsic Evolvable Digital Circuits, JNIT: Journal of Next Generation Information Technology, Vol. 2, No. 2, pp. 8-14, 2011.
Реконфигурируемое устройство аппаратной реализации генетического алгоритма, содержащее блок микропрограммного управления, первый вход которого связан с первым входным портом устройства, второй вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок оценки решения, вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок генетических операторов, вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок мультиплексоров, первый вход которого связан с выходом блока микропрограммного управления, второй вход которого связан с выходом блока оценки решения, третий вход которого связан с выходом блока генетических операторов, четвертый вход которого связан с выходом блока отбора, пятый вход которого связан с выходом блока генерации популяции, шестой вход которого связан с выходом блока памяти, седьмой вход которого связан с выходом блока реконфигурируемого модуля, первый выход которого связан с входом блока микропрограммного управления, второй выход которого связан с входом блока оценки решения, третий выход которого связан с входом блока генетических операторов, четвертый выход которого связан с входом блока отбора, пятый выход которого связан с входом блока генерации популяции, шестой выход которого связан с входом блока памяти, седьмой выход которого связан с входом блока реконфигурируемого модуля, блок отбора, вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок генерации популяции, вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок памяти, вход которого связан с выходом блока мультиплексоров, выход которого связан с блоком мультиплексоров, блок реконфигурируемого модуля, первый вход которого связан со вторым входным портом устройства, второй вход которого связан с выходом блока мультиплексоров, первый выход которого связан с блоком мультиплексоров, второй выход которого связан с выходным портом устройства, отличающееся тем, что в него введен блок реконфигурируемого модуля, предназначенный для динамической реконфигурации цифровых комбинационных логических схем.
