Для авторов
Найти
Результаты поиска
Найдено результатов: 4.
-
МЕТОДИКА СОЗДАНИЯ ТОПОЛОГИЧЕСКИХ ОГРАНИЧЕНИЙ ПРИ ВЫСОКОЙ УТИЛИЗАЦИИ РЕСУРСОВ ПЛИС
К.Н. Алексеев , Д.А. Сорокин , А.Л. Леонтьев2022-11-01Аннотация ▼Рассмотрена проблема достижения высокой реальной производительности реконфи-
гурируемых вычислительных систем при решении вычислительно трудоёмких задач различ-
ных предметных областей. Величину реальной производительности реконфигурируемых сис-
тем определяют параметры выполняемых на них программ, основной компонентой которых
являются вычислительные структуры обработки данных, реализованные в виде конфигура-
ционных файлов ПЛИС. При этом одним из ключевых параметров любой вычислительной
структуры является тактовая частота ее работы, которая непосредственно влияет на её
производительность. Однако достижение высоких тактовых частот сопряжено с рядом
проблем, которые современные средства САПР не решают. Причина кроется в неоптималь-
ном топологическом размещении функциональных узлов вычислительной структуры на поле
примитивов ПЛИС, особенно при высокой утилизации ресурсов. Это приводит к повышенной
нагрузке на коммутационную матрицу ПЛИС и, как следствие, связи между примитивами
ПЛИС, имеющими функциональную зависимость, оказываются значительно длиннее, чем
это допустимо. Кроме того, излишняя длина связей наблюдается при трассировке соедине-
ний между примитивами, которые расположены на разных кремниевых кристаллах ПЛИС
или же физически разделены встроенными периферийными устройствами. В настоящей
статье описывается методика, которая позволяет рационализировать размещение элемен-
тов вычислительной структуры на поле примитивов ПЛИС, минимизировать длину трасс
между примитивами, а также минимизировать число трасс между физически разделенны-
ми топологическими областями ПЛИС. Работоспособность предложенной методики пока-
зана на примере решения тестовой задачи «КИХ-фильтр» на реконфигурируемом компьюте-
ре «Терциус». Проиллюстрированы основные проблемы при достижении целевой тактовой
частоты и описан способ их преодоления. Применение методики позволило увеличить так-
товую частоту и тем самым поднять производительность «Терциус» на 25% без перера-
ботки функциональной схемы вычислительной структуры задачи. Текущие исследованияэффективности предложенной методики позволяют утверждать, что автоматизирован-
ные средства создания топологических ограничений на её основе позволят существенно со-
кратить время разработки программ с требуемыми характеристиками для реконфигури-
руемых вычислительных систем. -
РАЗРАБОТКА БИОЭВРИСТИК ДЛЯ СОЗДАНИЯ ИНТЕЛЛЕКТУАЛЬНОЙ ПОДСИСТЕМЫ ПРИНЯТИЯ ЭФФЕКТИВНЫХ РЕШЕНИЙ NP- ТРУДНЫХ И NP-СЛОЖНЫХ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ
Д.В. Заруба , Э.В. Кулиев , Д. Ю. Запорожец , М. М. Семенова2021-11-14Аннотация ▼Статья посвящена решению новых актуальных проблем, возникших в условиях со-
временного развития информационных и нанометровых технологий в области проектиро-
вания, а также разработке новых инновационных методов, обеспечивающих получение
эффективных решений за полиномиальное время. В статье рассматривается проблема
решения NP-сложных задач. Приведено описание процедуры измерения сложности задачи.
Описаны особенности NP- трудных и NP-сложных комбинаторно-логических задач. При-
ведены основные различия между задачами, а также проблемы, с которыми приходится
сталкиваться при решении такого вида задач. Представлена общая схема принятия реше-
ний, состоящая из формулировки проблемы; принятие решения; сигнала в автоматических
системах и обратной связи. На втором этапе (формирование и выбор вариантов решений)
решение основывается на биоинспирированном алгоритме поиска решений задачи комми-
вояжёра. Для решения поставленной задачи был разработан модифицированный биоинспи-
рированный алгоритм, основанный на поведении муравьиной колонии. В отличие от других
методов оптимизации, метаэвристические алгоритмы могут находить глобальные опти-
мальные решения для задач, где существует много локальных решений из-за их случайного
характера. Эти причины привели к широкому использованию таких алгоритмов при реше-
нии различных задач оптимизации. Биоинспирированные алгоритмы становятся новой
революцией в области решений оптимизационных задач. Представлена постановка задачи
коммивояжера, а также решение поставленной задачи на основе муравьиного алгоритма.
Алгоритмы, такие как генетические алгоритмы и PSO могут быть очень полезными, но
они все еще имеют некоторые недостатки в решении проблем мультимодальной оптими-
зации. Эти алгоритмы способны находить оптимальные решения независимо от физиче-
ской природы проблемы. В рамках экспериментальных исследований был произведен анализ
работы биоинспирированных алгоритмов: алгоритм стаи летучих мышей бактериальный
алгоритм и муравьиный алгоритм. -
ПОИСКОВЫЙ ПОПУЛЯЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СБИС
Б. К. Лебедев , О.Б. Лебедев , В. Б. Лебедев2020-11-22Аннотация ▼В работе рассматривается поисковый популяционный алгоритм размещения компо-
нентов СБИС. По аналогии с процессом возникновения и формирования кристаллов из ве-
щества, процесс порождения решения путем последовательного проявления и конкретиза-
ции решения на базе интегральной россыпи альтернатив назван методом кристаллизации
россыпи альтернатив. Решение Qk задачи размещения представляется в виде биективного
отображения Fk=A→P, каждому элементу множества A соответствует один единст-
венный элемент множества P и наоборот. Лежащая в основе алгоритма метаэвристика
кристаллизации россыпи альтернатив выполняет поиск решений с учетом коллективной
эволюционной памяти, под которой подразумевается информация, отражающая историю
поиска решения и памяти поисковой процедуры. Отличительной особенностью используе-
мой метаэвристики является учет тенденции к использованию альтернатив из наилучших
найденных решений. Предложены компактные структуры данных для хранения интерпре-
таций решений и памяти. Алгоритм, связанный с эволюционной памятью, стремится к
запоминанию и многократному использованию способов достижения лучших результатов.
Разработанный алгоритм относится к классу популяционных алгоритмов. Итерационный
процесс поиска решений включает три этапа. На первом этапе каждой итерации конст-
руктивным алгоритмом формируется nq решений Qk. Работа конструктивного алгоритма
базируется на базе показателей основной интегральной россыпи альтернатив – матрицы
R, в которой хранятся интегральные показатели решений, полученных на предыдущих
итерациях. Процесс назначения элемента в позицию включает две стадии. На первой ста-
дии выбирается элемент, а на второй стадии – позиция pj. При этом должно выполняться
ограничение: каждому элементу соответствует одна позиция pj. Рассчитывается оценка
ξk решения Qk и оценка полезности δk множества позиций Pk выбранных агентами. В рабо-
те используется циклический метод формирования решений. В этом случае наращивание
оценок интегральной полезности δk в основной интегральной россыпи альтернатив B вы-
полняется после полного формирования множества решений Q. На втором этапе итера-
ции производится наращивание оценок интегральной полезности δk в основной интеграль-
ной россыпи альтернатив – матрице R. На третьем этапе итерации осуществляетсяснижение оценок полезности δk интегральной россыпи альтернатив R на априори заданную величину δ*. Работа алгоритма завершается после выполнения заданного числа итера-
ций. Сравнительный анализ с другими алгоритмами решения производился на стандартных
тестовых примерах (бенчмарках) корпорации IBМ, при этом решения, синтезируемые ал-
горитмом CAF, превосходят по эффективности решения известных методов в среднем на
6%. Временная сложность алгоритма – О(n2)-О(n3). -
ПОДХОД К КОДИРОВАНИЮ РЕШЕНИЙ В ЭВОЛЮЦИОННЫХ МЕТОДАХ ДЛЯ СОЗДАНИЯ ИНСТРУМЕНТАЛЬНОЙ ПЛАТФОРМЫ ПРОЕКТИРОВАНИЯ
Э. В. Кулиев, А. А. Лежебоков, М. М. Семенова, В.А. Семенов2020-07-20Аннотация ▼Рассмотрены актуальные вопросы и проведен анализ проблемы трехмерной инте-
грации и трехмерного моделирования, возникающей на этапе конструкторского проекти-
рования в ходе решения задачи оптимального планирования компонентов больших и сверх-
больших интегральных схем и корпусных устройств электронной вычислительной аппара-
туры. Представлены и достаточно детально описаны основные преимущества примене-
ния принципов трехмерной интеграции, позволяющие эффективно организовывать произ-
водство персонифицированной электроники, оптимально планировать конфигурацию
больших и сверхбольших интегральных схем с учетом тепловых и энергетических характе-
ристик. В ходе выполнения исследований авторами разработан подход к кодированию ре-
шений на основе интеллектуального механизма, который характеризуется наличием
встроенных средств контроля допустимых решений. Одним из таких средств, экспери-
ментально доказавших свою эффективность, является встроенный механизм «смертель-
ных мутаций», учитывающий статусы генов и заранее заданные ограничения на итоговую
конфигурацию корпуса проектируемого устройства. В работе предложен ряд общих под-
ходов и конкретных алгоритмов решения задачи планирования, основывающихся на ре-
зультатах исследований авторского коллектива и современных подходах к решению
NP-полных задач. Важнейшим практически значимым результатом исследований обозна-
ченной проблемы является разработанная программно-инструментальная платформа
проектирования на современном кроссплатформенном языке программирования Java. Вы-
бранная технология разработки позволяет использовать все основные достоинства со-
временных многоядерных и многопроцессорных архитектур, по использованию программ-
ной многопоточности для реализации параллельных схем решения комбинаторных задач.
Программно-инструментальная платформа обладает дружественным интерфейсом, что
позволяет эффективно управлять процессом решения задачи планирования компонентовбольших и сверхбольших интегральных схем трехмерной интеграции, путем визуализации
ключевых показателей работы алгоритмов на графиках и в блоках текстовой статисти-
ки. Разработанное прикладное программное обеспечение позволило провести серию вычис-
лительных экспериментов, на основе наборов случайных данных также, как и наборах от-
крытых данных бенчмарков для подобного рода задач. Результаты экспериментальных
исследований позволили подтвердить теоретические оценки временной сложности и эф-
фективности предложенных подходов и алгоритмов, в том числе генетического алгорит-
ма, который использует предложенный в работе новый механизм кодирования решений.
1 - 4 из 4 результатов
