Реконфигурируемое устройство аппаратной реализации генетического алгоритма

Изобретение относится к вычислительной технике. Технический результат заключается в снижении вычислительных затрат на проведение эволюционного поиска и обеспечении автономности функционирования объекта при принятии решений в изменяющейся среде в автономных интеллектуальных системах. Реконфигурируемое устройство аппаратной реализации генетического алгоритма содержит блок микропрограммного управления, первый вход которого связан с первым входным портом устройства, второй вход которого связан с выходом блока мультиплексоров, блок оценки решения, блок генетических операторов, блок мультиплексоров, блок отбора, блок генерации популяции, блок памяти, блок реконфигурируемого модуля, первый вход которого связан со вторым входным портом устройства, второй вход которого связан с выходом блока мультиплексоров, первый выход которого связан с блоком мультиплексоров, второй выход которого связан с выходным портом устройства, блок реконфигурируемого модуля предназначен для динамической реконфигурации цифровых комбинационных логических схем. 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 аргументов равно 2.

На Фиг. 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.

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



 

Похожие патенты:

Изобретение относится к вычислительной технике. Технический результат заключается в повышении скорости передачи данных.

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

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

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

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

Группа изобретений относится к средствам обработки информации. Технический результат заключается в автоматизации получения данных о расходах на сервере.

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

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

Изобретение относится к устройству управления печатью и способу управления печатью. Технический результат заключается в повышении быстродействия обработки заданий.

Изобретение относится к вычислительной технике, а именно к системам контроля и способам задания настроек контроля качества печатного изделия. Технический результат состоит в осуществлении контроля печатного изделия и достигается за счет применения устройства задания настроек, осуществляющего контроль печатного изделия, над которым выполнялась обработка печати. Причем устройство задания настроек содержит: блок отображения, выполненный с возможностью отображения экрана задания настроек печати для задания настройки печати, связанной с обработкой печати, и экрана задания настроек контроля для задания настройки контроля, связанной с обработкой контроля; блок определения, выполненный с возможностью определения того, задана ли конкретная настройка печати, которая указывает печать конкретного объекта, на экране задания настроек печати; и блок управления, выполненный с возможностью управления блоком отображения для отображения экрана задания настроек контроля в состоянии, когда конкретный объект зарегистрирован в качестве целевого объекта обработки контроля, если блок определения определяет, что конкретная настройка печати задана на экране задания настроек печати. 4 н. и 3 з.п. ф-лы, 15 ил.

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

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

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