Найти

Результаты поиска

• ПОДХОД К КОДИРОВАНИЮ РЕШЕНИЙ В ЭВОЛЮЦИОННЫХ МЕТОДАХ ДЛЯ СОЗДАНИЯ ИНСТРУМЕНТАЛЬНОЙ ПЛАТФОРМЫ ПРОЕКТИРОВАНИЯ

  Э. В. Кулиев, А. А. Лежебоков, М. М. Семенова, В.А. Семенов

  2020-07-20

  Аннотация ▼

  Рассмотрены актуальные вопросы и проведен анализ проблемы трехмерной инте-
  грации и трехмерного моделирования, возникающей на этапе конструкторского проекти-
  рования в ходе решения задачи оптимального планирования компонентов больших и сверх-
  больших интегральных схем и корпусных устройств электронной вычислительной аппара-
  туры. Представлены и достаточно детально описаны основные преимущества примене-
  ния принципов трехмерной интеграции, позволяющие эффективно организовывать произ-
  водство персонифицированной электроники, оптимально планировать конфигурацию
  больших и сверхбольших интегральных схем с учетом тепловых и энергетических характе-
  ристик. В ходе выполнения исследований авторами разработан подход к кодированию ре-
  шений на основе интеллектуального механизма, который характеризуется наличием
  встроенных средств контроля допустимых решений. Одним из таких средств, экспери-
  ментально доказавших свою эффективность, является встроенный механизм «смертель-
  ных мутаций», учитывающий статусы генов и заранее заданные ограничения на итоговую
  конфигурацию корпуса проектируемого устройства. В работе предложен ряд общих под-
  ходов и конкретных алгоритмов решения задачи планирования, основывающихся на ре-
  зультатах исследований авторского коллектива и современных подходах к решению
  NP-полных задач. Важнейшим практически значимым результатом исследований обозна-
  ченной проблемы является разработанная программно-инструментальная платформа
  проектирования на современном кроссплатформенном языке программирования Java. Вы-
  бранная технология разработки позволяет использовать все основные достоинства со-
  временных многоядерных и многопроцессорных архитектур, по использованию программ-
  ной многопоточности для реализации параллельных схем решения комбинаторных задач.
  Программно-инструментальная платформа обладает дружественным интерфейсом, что
  позволяет эффективно управлять процессом решения задачи планирования компонентовбольших и сверхбольших интегральных схем трехмерной интеграции, путем визуализации
  ключевых показателей работы алгоритмов на графиках и в блоках текстовой статисти-
  ки. Разработанное прикладное программное обеспечение позволило провести серию вычис-
  лительных экспериментов, на основе наборов случайных данных также, как и наборах от-
  крытых данных бенчмарков для подобного рода задач. Результаты экспериментальных
  исследований позволили подтвердить теоретические оценки временной сложности и эф-
  фективности предложенных подходов и алгоритмов, в том числе генетического алгорит-
  ма, который использует предложенный в работе новый механизм кодирования решений.

• ПОИСКОВЫЙ ПОПУЛЯЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СБИС

  Б. К. Лебедев , О.Б. Лебедев , В. Б. Лебедев

  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).

• МНОГОМЕРНЫЙ ПОИСК В ЗАДАЧЕ РАЗМЕЩЕНИИ ЭЛЕМЕНТОВ СБИС НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

  Е. В. Данильченко , В.И. Данильченко , В.М. Курейчик

  2021-07-18

  Аннотация ▼

  Все крупные производители идут к уменьшению габаритов современных микроэлектрон-
  ных устройств. Это приводит к переходу на новые нормы проектирования и изготовления
  СБИС. Известные алгоритмы автоматизированного проектирования не в полной мере способ-
  ны реализовывать новые требования при проектировании СБИС. В связи с этим, при решении
  задач конструкторского проектирования появляется необходимость в разработке новых ме-
  тодик решения данного класса задач. Одним из таких методик может стать гибридная мно-
  гомерная система поиска, основанная на генетическом алгоритме (ГА). Описывается автома-
  тизированный подход к проектированию СБИС на основе генетического алгоритма, позволяю-
  щий создать алгоритмическую среду в области многомерного генетического поиска для реше-
  ния NP полных задач, в частности размещения элементов СБИС. Цель данной работы заключа-
  ется в нахождении путей размещения элементов СБИС на основе генетического алгоритма.
  Научная новизна заключается в разработке модифицированного многомерного генетического
  алгоритма для автоматизированного проектирования сверхбольших интегральных схем. По-
  становка задачи в данной работе заключается в следующем: оптимизировать размещение
  элементов СБИС путем применения, многомерного модифицированного ГА. Практическая цен-
  ность работы заключается в создании подсистемы, позволяющей использовать разработан-
  ные многомерные архитектуры, методы и алгоритмы для эффективного решения задач кон-
  структорского проектирования СБИС, а также проводить сравнительный анализ с сущест-
  вующими аналогами. Принципиальное отличие от известных подходов в применении новых мно-
  гомерных генетических структур в автоматизированном проектировании СБИС, кроме того в
  работе праведен модифицированный генетический алгоритм. Приведенные результаты вычис-
  лительного эксперимента, показали преимущества предложенного в работе многомерного
  подхода к решению задач размещения элементов СБИС по сравнению с существующими анало-
  гами. Таким образом, проблема создания методов, алгоритмов и программного обеспечения для
  автоматизированного размещения элементов СБИС в настоящее время имеет особую акту-
  альность. Ее решение позволит улучшить качественные характеристики проектируемых уст-
  ройств, сократит сроки и затраты на проектирование.