Программные продукты и системы

Введение. Современные тенденции в проектировании сверхбольших интегральных схем (СБИС) обусловлены необходимостью повышения производительности, энергоэффективности и плотности размещения элементов при соблюдении технологических и физических ограничений. Одной из ключевых задач, возникающих на этапе топологического синтеза, является задача размещения фрагментов СБИС [1, 2]. Она требует учета множества параметров, вклю- чая длину межсоединений, плотность и площадь размещения, тепловыделение, энергопотребление, количество пересечений и другие критически важные проектные метрики [3, 4]. Сложность задачи обусловлена ее многокритериальным характером и высокой комбинаторной сложностью, что делает ее решение крайне ресурсоемким при традиционных методах.  В связи с этим поиск и разработка новых эффективных подходов для размещения фрагмен- тов СБИС с учетом влияния различных метрик на качество и эффективность проектных решений являются актуальной и важной задачей для исследователей и инженеров в области микроэлектроники.

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

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

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

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

Обзор существующих подходов

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

Для решения задачи размещения фрагментов СБИС применяется широкий набор методов, охватывающих как традиционные подхо- ды, так и возможные их модификации [1, 2], различающихся по сложности, эффективности и области применения. Отметим, что каждый метод обладает уникальными преимуществами и недостатками, а также ограничениями, которые необходимо учитывать при выборе подхода для данной задачи.

Традиционные методы представляют собой один из наиболее простых и понятных способов решения поставленной задачи, например, случайный поиск [2]. Он основывается на случайном выборе альтернативных решений и их постепенной оценке по заранее заданным кри- териям. При этом данный метод имеет ограниченную эффективность, особенно при решении задач с большим количеством фрагментов, так как его область поиска может быть слишком узкой. Для повышения качества и эффективности проектных решений случайный поиск  часто комбинируется с другими подходами, такими как моделирование отжига или релаксация, что позволяет повысить вероятность на- хождения квазиоптимальных решений.

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

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

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

Основные представители метаэвристик [5, 6] – биоинспирированные методы, включающие,  в частности, такие классы алгоритмов, как эволюционные, генетические и роевые алгорит- мы [7, 8], являющиеся одними из наиболее перспективных для задач размещения фрагментов СБИС. Такие методы вдохновлены процессами, происходящими в природе, и моделируют их для поиска квазиоптимальных решений. Эволюционные методы основываются на принципах естественного отбора, что позволяет им эффективно решать задачи с большой размерностью и высокой сложностью. В свою очередь, генетические алгоритмы используют механизмы наследственности и селекции, что позволяет не только находить качественные решения, но и избегать попадания в локальные минимумы. Роевые методы, такие как алгоритм роя частиц, представляют собой методы коллективного поведения агентов, что позволяет значительно расширить область поиска и увеличить вероятность нахождения квазиоптимальных решений. При этом биоинспирированные методы также имеют свои недостатки, например, склонность к быстрой сходимости  к локальным оптимумам, особенно если параметры алгоритма не настроены под исходные данные схемы. Для улучшения результатов часто используется комбинированный подход, сочетающий преимущества разных методов, например, биоинспирированных алгоритмов  в комбинации с методами локальной оптимизации или точными методами.

Кроме того, активно развиваются гибридные подходы, комбинирующие различные методы с целью повышения качества и эффективности проектных решений [9, 10]. Они включают элементы случайного поиска, эволюционных алгоритмов и методов локальной оптимизации, что позволяет сбалансировать скорость поиска и качество решения. Гибридные методы позволяют повысить качество и эффективность проектных решений, что особенно актуально в задачах большой размерности.

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

Заметим, что значительный вклад в решение задач проектирования микросхем и микро- процессоров в последние годы внесли исследователи из Китая и Японии. В частности, в работе [1] представлен обширный обзор современных методов ускоренного физического размещения СБИС, в котором подробно рассматриваются различные методы, включая метаэвристические, гибридные алгоритмы и нейросетевые модели. Они показывают высокую эффективность при решении задач с ограничениями по плотности, мощности и времени задержки сигналов, что делает их особенно актуальными  в условиях современного проектирования СБИС. В фундаментальном труде [2] освещаются современные проблемы, подходы, методы и алгоритмы при проектировании СБИС, направленные на улучшение характеристик работы и повышение эффективности проектных решений. Авторами предлагается комплексный подход  к разработке современных СБИС, ориентирован- ный на улучшение производительности и снижение энергозатрат. Это исследование дает важное теоретическое обоснование для многих методов, включая те, которые используются  в проектировании СБИС, и может стать ориентиром для дальнейших работ в этой области.

В работе [6] рассматриваются применения современных метаэвристик, охватывающих как многокритериальные алгоритмы, так и адаптивные модели, ориентированные на поддержку интеллектуальных систем.

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

Отметим, что ни один из рассмотренных методов не может гарантировать нахождение гло- бального оптимума за полиномиальное время, что подчеркивает необходимость разработки новых, модифицированных и более эффективных подходов при проектировании СБИС.

Постановка задачи размещения

Задача размещения – это процесс многокритериальной оптимизации, связанной с обработкой больших объемов данных и выбором метрик оценки качества проектных решений. Основная цель решения – нахождение квазиоптимального распределения элементов в решетке, плоскости или линейке.

Критерии размещения делятся на метрические (длина проводников, количество изгибов), ориентированные на параметры, и топологические, учитывающие взаимное расположение соединений, число пересечений и используемых слоев [3, 4]. Существенным фактором также является надежность, включающая тепловую и электромагнитную совместимость, временные задержки и плотность компоновки.

В данном исследовании под фрагментами СБИС понимаются функционально завершенные участки схемы, включающие в себя груп- пы логических или аналоговых компонентов, объединенных по функциональному признаку. Такие фрагменты представляют собой логически связанные блоки, размещаемые на кристалле как единые структурные элементы [2, 11]. Их использование позволяет сократить сложность задач размещения и упростить последующую трассировку за счет предварительного структурирования схемы.

После размещения фрагментов основным этапом является трассировка соединений. Для ее учета в алгоритмах размещения применяются такие критерии, как общая длина соединений, количество соединений, пересечений проводников, коротких соединений.

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

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

Дано множество фрагментов СБИС C = {c1, c2, …, cn}, где n – количество фрагментов, которые необходимо разместить на плоскости. Каждому фрагменту ci соответствуют фиксированные выводы, размещение которых требуется организовать на плоскости. Также задано множество соединений E = {e1, e2, …, em}, где каждое соединение ei Í C представляет собой пару фрагментов, которые должны быть соединены проводниками.

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

В задаче размещения фрагментов СБИС каждому фрагменту схемы присваивается координата на прямой, определяющая его положение [2]:

где  то есть все фрагменты размещаются вдоль прямой на фиксированном уровне y0, а координата xi определяет положение фрагмента ci.

Допустимая область размещения определяется длиной L и фиксированной координатой по вертикали [2]:

Целевая функция вычисляется как суммарная длина межсоединений, рассчитываемая по модели половинного периметра (Half-Perimeter Wire Length, HPWL) [11]:

где величина HPWL(e) соответствует приближенной оценке длины межсоединения и вычисляется как сумма граничных координат, входящих в соединение e [2]:

где xi – координата фрагмента ci на плоскости; ei Í C – множество фрагментов, связанных  в одном соединении. Такая формализация позволяет учитывать длину межсоединений и способствует упрощению последующей трассировки.

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

Минимальная допустимая длина соединения e ограничивает протяженность линейного сегмента для каждого соединения, что соответствует ограничениям технологического процесса. Эта величина рассчитывается на основе следующего выражения:

Ограничение по области размещения устанавливает границы, в пределах которых должны располагаться все фрагменты [2, 10]. Формально это ограничение выражается следующим образом:

Плотность размещения описывается функцией r = (x), которая задает ее по координате x. Эта плотность не должна превышать установленного значения [3, 4]:

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

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

Линейные сегменты – это кратчайший путь межсоединений, который не содержит межслойных переходов и не занимает горизонтальных трасс (рис. 1) [12].

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

Каждый линейный сегмент li, образующий соединение между двумя фрагментами, опре- деляется как евклидово расстояние между точками (xi1, yi1) и (xi2, yi2):

где (xi1, yi1) и (xi2, yi2) – координаты выводов фрагментов, соединенных сегментом li.

Для количественной оценки фрагментации соединений на уровне межсоединительной топологии в задаче размещения фрагментов СБИС используется метрика, отражающая общее количество линейных сегментов, формирующих электрические связи между фрагментами:

где n – общее число линейных сегментов, возникающих при соединении фрагментов.

Для агрегирования нескольких критериев  в единую целевую функцию применяется аддитивная свертка векторного критерия:

где fВ – целевая функция, объединяющая суммарную длину межсоединений и количество линейных сегментов. Коэффициенты a, b определяют приоритет каждого критерия в общей оценке. Отметим, что предложенная метрика также может быть использована в сочетании  с другими критериями для повышения качества и эффективности проектирования в зависимости от технологических и топологических параметров задачи [13].

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

Модифицированный алгоритм на основе модели поведения стволовых клеток

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

Алгоритм включает инициализацию на- чальной популяции стволовых клеток, которая формируется на основе заданного множества агентов, а на последующих итерациях ее численность постепенно увеличивается путем добавления новых агентов в соответствии с заранее установленным процентом. Параметры, такие как размер исходного множества агентов, доля добавляемых на каждой итерации агентов и стратегия развития популяции, задаются лицом, принимающим решения (ЛПР). Требования к ЛПР включают экспертные знания в проектировании СБИС и способность выявлять ключевые параметры для текущей задачи, что влияет на эффективность и качество проектных решений в целом.

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

где  – приоритетный агент в текущей итерации; k – номер итерации и x – коэффициент подстройки, задается ЛПР в интервале [0; 1]. В рамках данного исследования x = 0,9 [12].

Процесс самообновления продолжается до тех пор, пока не будет найден агент, обладающий наибольшей адаптивностью среди всех представителей популяции:

где xij описывает положение агента в пространстве; mij и mqj – случайно инициализированные агенты [12]. Если , тогда j(t) примет случайное значение в интервале [–1, 1].

Представим псевдокод процедуры самообновления агентов, реализующий стохастическое обновление их координат на основе случайно выбранных направлений в пространстве:

import random

def самообновление (агенты, ξ,  вариант = 1):

  # Определение коэффициента  подстройки

  коэффициент = 0.9 if вариант == 1 else 0.1

  # Поиск приоритетного агента  с максимальной приспособленностью

  лучший = max (агенты, key=lambda a: a["приспособленность"])

  for агент in агенты:

      if агент == лучший:

          continue  # приоритетный агент не обновляется

      # Выбор случайного агента для обновления

      μ_ij = агент["позиция"]

      μ_qj = random.choice(агенты)["позиция"]

      # Вычисление дельты  и случайного множителя φ

      τ = [μi - μq for μi, μq in zip(μ_ij, μ_qj)]

      φ = [random.uniform(-1, 1)  for _ in τ]

      # Обновление позиции агента

      новое положение = [μ + f * t for μ, f, t in zip(μ_ij, φ, τ)]

      агент ["позиция"] = новое  положение

  return агенты

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

С учетом данных модификаций формула вычисления интенсивности самообновления агентов примет следующий вид:

где x – начальный коэффициент подстройки, находящийся в интервале [0; 1]; Xi – параметр ограничения роста количества агентов; Z – относительная частота успешных мутаций в интервале [–X, X], задаваемая ЛПР.

Согласно правилу мутации Реченберга, если соотношение успешно выполненных мутаций к общему числу составляет менее 1/5, то параметр m(t) уменьшается. В противном случае параметр m(t) увеличивается, что ускоряет процесс поиска.

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

Def правило Реченберга (успешные  мутации, общее число, ξ_= prev, X):

    Z = успешные мутации / общее число

    if Z < 1/5:

        μ = X * 0.85

    elif Z > 1/5:

        μ = X / 0.85

    else:

        μ = X

    ξ_new = μ * ξ_prev

  return ξ_new

В качестве еще одной модификации алгоритма, в отличие от базовой модели, где распределение агентов происходит случайно  и равномерно, предлагается каждое положение агента с возможностью самообновления сохранять в массив, отсортированное по возрастанию значения целевой функции. Здесь для упорядочивания и разнообразия распределения агентов применяется специальная процедура, при реализации которой размещение происходит следующим образом [5, 12]:

где a, b – первый и второй распределенные агенты; d, w – два положительных симметричных случайных значения (d, w > 0).

Реализация процедуры приоритетного распределения агентов в разработанном алгоритме представляется в виде псевдокода:

import numpy as np

from scipy.stats import beta

def приоритетное_распределение(агенты, δ = 2.0, ω = 2.0):

  # Сортировка агентов по значению целевой функции (возрастание)

  агенты.sort(key=lambda a: a.оценка)

  новые_агенты = []

  for i in range(len(агенты) - 1):

      a = агенты[i].позиция

      b = агенты[i + 1].позиция

      # Генерация точки между a и b  по бета-распределению

      r = beta.rvs(δ, ω)  # значение  в интервале [0, 1]

      новая_позиция = a + r * (b - a)

 # Создание нового агента в промежутке

      агент = Агент(позиция=новая_ позиция)

      новые_агенты.append(агент)

  return новые_агенты

return новые_агенты

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

Модифицированный генетический  алгоритм

Для оценки эффективности рассматриваемых метрик в работе предлагается модифицированный генетический алгоритм.

Выбор генетического алгоритма [14] обусловлен его эффективностью при решении сложных, NP-сложных, трудных задач. Он позволяет решать проблему преждевременной сходимости к локальному оптимуму, поддерживая генетическое разнообразие популяции  и повышая вероятность нахождения глобального экстремума. Это достигается за счет исполь- зования стохастических операторов мутации  и кроссовера, которые способствуют исследованию менее очевидных областей пространства решений [5, 7].

В качестве модификации генетического алгоритма предлагается использовать эволюционную стратегию, основанную на объединении двух моделей Ж.Б. Ламарка и Х. де Фриза [5], что позволяет расширить пространство поиска и повысить качество и эффективность проектных решений.

Представим параллельную реализацию модифицированного генетического алгоритма  в виде псевдокода:

1. Сгенерировать начальную популяцию из N хромосом длиной L. # N – размер популяции, L – длина хромосомы.

2. Для каждой эпохи t = 1 . . . T: # T – общее число поколений

   а) Адаптация по Ламарку: для каждой хромосомы xi:

        если rand() < padapt:

            # padapt – вероятность локальной адаптации

            выполнить градиентный шаг: xi ← xi − α∇f(xi) # α – скорость обучения

            если f(xновый_i) > f(xi):

                # новая версия xi принимается, только если она улучшает приспособленность

                обновить xi ← xi_новый.

   б) Создание потомков: повторять до получения 2N особей:

        выбрать 2 родителя (турнирная селекция);

        применить кроссовер с pcross: # pcross – вероятность кроссовера

            одноточечный обмен генетическим материалом.

    Мутация по де Фризу: для каждого потомка:

            если rand() < pmut:

                # pmut – вероятность мутации

                изменить случайный ген: gj ← gj + r, где r ∼ U(−1, 1) # gj – значение случайного гена, r – случайное число из равномерного распределения

            добавить потомков в новую популяцию.

    в) Отобрать N лучших особей по f(x) для следующего поколения.

3. Вывести особь с максимальным значением функции приспособленности f(x).

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

Программная реализация

Для проведения вычислительного экспе- римента использовался комплексный подход  с применением стандартных и специально разработанных программных средств [15]. Исходные данные включали схемы проектирования  и макеты, полученные из стандартных тестовых наборов, таких как ISPD-08, IBM-13  и CCPA-16, приведенных в таблице 1 [16, 17].

Входные данные тестовых наборов (http:// www.swsys.ru/uploaded/image/2025-4/1.jpg) включают элементы схемы, которые необходимо разместить, а также фрагменты их взаимосвязи. На основе этих данных формируются параметры C и E, учитывающие структуру  и характеристики, заложенные в тестовых на- борах.

Таблица 1

Характеристики тестовых наборов  ISPD-08, IBM-13 и CCPA-16

Table 1

Properties of the ISPD-08, IBM-13,  and CCPA-16 test sets

Геометрические параметры, такие как размеры области размещения и максимально допустимая плотность, также определяются в рамках каждого теста и напрямую влияют на ограничения задачи (координаты и плотность размещения). Например, в ISPD-08 область размещения задается как 10×10 мм², а допустимая плотность – до 1 000 фрагментов на см². Кроме того, каждый тест содержит спецификацию минимально допустимой длины проводника e, определяющей технологические ог- раничения. Эта длина входит в расчет целевой функции и накладывает нижнюю границу на величину HPWL для каждого соединения, что обеспечивает соответствие проектируемых схем реальным производственным стандартам.

Серия экспериментов была проведена на программном комплексе, разработанном с использованием языка программирования Python. Программа используется для моделирования процедуры размещения фрагментов СБИС  с учетом различных ограничений. Вычислительный эксперимент проведен с использованием библиотек Tkinter для графического интерфейса и numpy для численных операций. Вычисления проведены в интерактивной среде Windows 10 Pro, с процессором Intel Core i7  (4.2 ГГц), 32 Гб оперативной памяти.

В рамках серии экспериментов проведена комплексная оценка влияния различных оптимизационных алгоритмов (генетических, имитации отжига, муравьиной колонии и колоний стволовых клеток) и проектных метрик на эффективность решения задачи размещения фраг- ментов СБИС. Эксперименты охватывают как тестовые макеты, так и реальные проектные данные, позволяя проанализировать эффективность и качество проектных решений.

В таблице 2 приведены основные параметры, ограничения и требования при проведении серии экспериментов.

Таблица 2

Параметры и ограничения

Table 2

Parameters and constraints

Результаты вычислительного  эксперимента

Для оценки эффективности различных биоэвристических методов оптимизации размещения фрагментов проведена серия экспериментов и представлены обобщенные результаты (http://www.swsys.ru/uploaded/image/2025-4/2.jpg). В эксперименте использовались генетический алгоритм [5, 7], имитация отжига [18], стволовых клеток [5, 12] и муравьиной колонии [5, 7, 19].

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

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

Далее проведено исследование влияния различных метрик на качество и эффективность проектных решений (http://www.swsys.ru/uploa- ded/image/2025-4/3.jpg). Положительная средняя динамика снижения значений по всем метрикам свидетельствует об эффективности примененного алгоритма размещения.

На рисунке 3 представлены результаты сравнительного анализа различных метрик.

Каждая группа отражает степень улучшения соответствующей метрики.

На рисунке 4 приведено сравнение времени работы поисковых алгоритмов.

Из графиков видно, что генетический алгоритм продемонстрировал наименьшее время выполнения, варьирующееся от 9,3 до 10,8 мс в первом эксперименте и от 8,9 до 10,2 мс  во втором. Метод стволовых клеток показал со- поставимые результаты, с диапазоном времени от 9,5 до 11,0 мс в первом эксперименте и от 9,2 до 10,7 мс во втором. Алгоритм имитации отжига продемонстрировал время выполнения от 11,2 до 13,1 мс в первом эксперименте и от 10,8 до 13,0 мс во втором. Муравьиный алгоритм показал наибольшее время работы, находящийся в пределах от 12,3 до 14,2 мс в первом эксперименте и от 12,0 до 14,0 мс во втором.

В результате проведенного анализа выяснилось, что применение метрики линейных сегментов позволяет достичь умеренного, но устой- чивого снижения энергопотребления (до 15 %), времени расчета (на 12 %) и тепловыделения (на 8 %) по сравнению с рассматриваемыми метриками. Такой результат связан с повышенной точностью топологических особенностей соединений, влияющих на распределение сигналов и тепловую нагрузку. Отметим, что эффективность данной метрики может варьироваться в зависимости от архитектуры схемы  и характера проектных ограничений.

Заключение

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

Разработанные и модифицированные алгоритмы размещения фрагментов СБИС показали высокую эффективность при решении задачи размещения с учетом различных проектных метрик. Создана программная среда и проведен вычислительный эксперимент на тестовых наборах ISPD-08, IBM-13 и CCPA-16. Сравнительный анализ с известными подходами показал, что предложенные методы поз- воляют в среднем снизить индекс суммарной длины межсоединений до 28 %, энергопотребление – на 22 %, тепловыделение – до 14 %, повысить плотность размещения на 18 % и сокра- тить время расчета до 12 %. Полученные данные подтверждают эффективность комплексного подхода к проектированию и обосно- ванность включения дополнительных метрик  в проектную процедуру размещения.

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

Список литературы

1. Qiu Y., Xing Y., Zheng X. et al. Progress of placement optimization for accelerating VLSI physical design. Electronics, 2023, vol. 12, no. 2, art. 337. doi: 10.3390/electronics12020337.

2. Taur Y., Ning T.H. Fundamentals of Modern VLSI Devices. Cambridge, Cambridge Univ. Press, 2009, 622 p. doi: 10.1017/CBO9781139195065.

3. Сидоров А.А., Николаев В.В. Метрики в проектировании СБИС. Казань: изд-во Казан. ун-та, 2018. 250 с.

4. Иванова Н.Н. Метрики и методы оптимизации в проектировании СБИС. Тверь: изд-во ТвГТУ, 2024. 340 с.

5. Гладков Л.А., Кравченко Ю.А., Курейчик В.В., Родзин С.И. Интеллектуальные системы: модели и методы метаэвристической оптимизации. Чебоксары: Среда, 2024. 228 с.

6. Yin P.-Y. Applications of modern metaheuristics in intelligent systems. Applied Sci., 2022, vol. 12, no. 19, art. 9746. doi: 10.3390/app12199746.

7. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: изд-во МГТУ им. Н.Э. Баумана, 2021. 448 с.

8. Курейчик В.В., Родзин С.И. Вычислительные модели эволюционных и роевых биоэвристик (обзор) // Информационные технологии. 2021. Т. 27. № 10. С. 507–520.

9. Тарасов В.Б., Гладков Л.А., Лейба С.Н. Разработка и программная реализация гибридного алгоритма решения оптимизационных задач автоматизированного проектирования // Программные продукты и системы. 2018. Т. 31. № 3. С. 569–580. doi: 10.15827/0236-235X.123.569-580.

10. Plummer J.D., Griffin P.B. Integrated Circuit Fabrication: Science and Technology. Cambridge, Cambridge Univ. Press, 2023, 680 p.

11. Bykovsky N.V., Harutyunyan R.V., Nasedkin A.V. Numerical modeling and optimization results for the placement of irregularly shaped elements on a multidimensional switching field with complex topology. T-Comm, 2024, vol. 18, no. 9, pp. 48–54. doi: 10.36724/2072-8735-2024-18-9-48-54.

12. Данильченко В.И., Данильченко Е.В., Курейчик В.М. Метаэвристический метод оптимизации на основе модели поведения стволовых клеток // Изв. ЮФУ. Технич. науки. 2022. № 2. С. 14–20.

13. Семенов Н.А., Иванов В.К., Думина Д.С. Определение весовых коэффициентов для аддитивной фитнес-функции генетического алгоритма // Программные продукты и системы. 2020. Т. 33. № 1. С. 47–53. doi: 10.15827/0236-235X.129.047-053.

14. Абас В.М.А. Приближенные методы оптимального размещения элементов электрических и электронных цепей // Изв. вузов. Северо-Кавказский регион. Технич. науки. 2021. № 2. С. 18–26. doi: 10.17213/1560-3644-2021-2-18-26.

15. Кулиев Э.В., Лежебоков А.А., Семенова М.М., Семенов В.А. Подход к кодированию решений в эволюционных методах для создания инструментальной платформы проектирования // Изв. ЮФУ. Технич. науки. 2020. № 2. С. 169–179. doi: 10.18522/2311-3103-2020-2-169-179.

16. De Souza L.A.M., Da Silva J.E.H., Chaves L.J., Bernardino H.S. A benchmark suite for designing combinational logic circuits via metaheuristics. Applied Soft Comput., 2020, vol. 91, art. 106246.

17. Govia L.C.G., Jurcevic P., Wood C.J. et al. A randomized benchmarking suite for mid-circuit measurements. NJP, 2023, vol. 25, art. 123016. doi: 10.1088/1367-2630/ad0e19.

18. Hemmak A. Optimal adjusting of simulated annealing parameters. Military Technical Courier, 2024, vol. 72, no. 1, pp. 80–93. doi: 10.5937/vojtehg72-47242.

19. Родзин С.И., Скобцов Ю.А., Эль-Хатиб С.А. Биоэвристики: теория, алгоритмы и приложения. Чебоксары: Среда, 2019, 224 с.

References

1. Qiu, Y., Xing, Y., Zheng, X. et al. (2023) ‘Progress of placement optimization for accelerating VLSI physical design’, Electronics, 12(2), art. 337. doi: 10.3390/electronics12020337.

2. Taur, Y., Ning, T.H. (2009) Fundamentals of Modern VLSI Devices. Cambridge, Cambridge Univ. Press, 622 p. doi: 10.1017/CBO9781139195065.

3. Sidorov, A.A., Nikolaev, V.V. (2018) Metrics in VLSI design. Kazan, 250 p. (in Russ.).

4. Ivanova, N.N. (2024) Metrics and optimization methods in VLSI design. Tver, 340 p. (in Russ.).

5. Gladkov, L.A., Kravchenko, Yu.A., Kureichik., V.V., Rodzin, S.I. (2024) Intelligent Systems: Models and Metaheuristic Optimization Methods. Cheboksary, 228 p. (in Russ.).

6. Yin, P.-Y. (2022) ‘Applications of modern metaheuristics in intelligent systems’, Applied Sci., 12(19), art. 9746. doi: 10.3390/app12199746.

7. Karpenko, A.P. (2021) Modern Search Optimization Algorithms. Algorithms Inspired by Nature. Moscow, 448 p. (in Russ.).

8. Kureichik, V.V., Rodzin, S.I. (2021) ‘Computational models of evolutionary and swarm-based bioheuristics (review)’, Information Technologies, 27(10), pp. 507–520 (in Russ.).

9. Tarasov, V.B., Gladkov, L.A., Leyba, S.N. (2018) ‘Development and software implementation of a hybrid algorithm for solving optimization problems in automated design,’ Software & Systems, 31(3), pp. 569–580 (in Russ.). doi: 10.15827/0236-235X.123.569-580.

10. Plummer, J.D., Griffin, P.B. (2023) Integrated Circuit Fabrication: Science and Technology. Cambridge, Cambridge Univ. Press, 450 p.

11. Bykovsky, N.V., Harutyunyan, R.V., Nasedkin, A.V. (2024) ‘Numerical modeling and optimization results for the placement of irregularly shaped elements on a multidimensional switching field with complex topology’, T-Comm, 18(9), pp. 48–54. doi: 10.36724/2072-8735-2024-18-9-48-54.

12. Danilchenko, V.I., Danilchenko, E.V., Kureichik, V.M. (2022) ‘Metaheuristic optimization method based on the stem cell behavior model’, Izv. SFedU. Eng. Sci., (2), pp. 14–20 (in Russ.).

13. Semenov, N.A., Ivanov, V.K., Dumina, D.S. (2020) ‘Determination of weight coefficients for additive fitness function of genetic algorithm’, Software & Systems, 33(1), pp. 47–53 (in Russ.). doi: 10.15827/0236-235X.129.047-053.

14. Abas, V.M.A. (2021) ‘Approximate methods for optimal placement of electrical and electronic circuit elements’, Univ. News. North-Caucas. Reg. Tech. Sci. Ser., (2), pp. 18–26 (in Russ.). doi: 10.17213/1560-3644-2021-2-18-26.

15. Kuliyev, E.V., Lezhebokov, A.A., Semenova, M.M., Semenov, V.A. (2020) ‘An approach to solution encoding in evolutionary methods for developing a design tool platform’, Izv. SFedU. Eng. Sci., (2), pp. 169–179 (in Russ.). doi: 10.18522/2311-3103-2020-2-169-179.

16. De Souza, L.A.M., Da Silva, J.E.H., Chaves, L.J., Bernardino, H.S. (2020) ‘A benchmark suite for designing combinational logic circuits via metaheuristics’, Applied Soft Comput., 91, art. 106246.

17. Govia, L.C.G., Jurcevic, P., Wood, C.J. et al. (2023) ‘A randomized benchmarking suite for mid-circuit measurements’, NJP, 25, art. 123016. doi: 10.1088/1367-2630/ad0e19.

18. Hemmak, A. (2024) ‘Optimal adjusting of simulated annealing parameters’, Military Technical Courier, 72(1), pp. 80–93. doi: 10.5937/vojtehg72-47242.

19. Rodzin, S.I., Skobtsov, Yu.A., El-Khatib, S.A. (2019) Bioheuristics: Theory, Algorithms and Applications. Cheboksary, 224 p. (in Russ.).