Адаптивная параметризация метаэвристического алгоритма при размещении компонентов СБИС

Аннотация

В работе рассматривается задача параметризации метаэвристического алгоритма размещения компонентов сверхбольших интегральных схем (СБИС) в условиях усложняющихся топологий и ограничений современных технологических норм. Актуальность исследования обусловлена ростом размерности проектируемых схем, увеличением плотности межсоединений и усложнением структуры пространства проектных решений, что ограничивает эффективность применяемых алгоритмов со статическими параметрами. Постановка задачи включает формирование комплекса проектных метрик, таких как длина соединений, плотность, площадь размещения, индекс пересечений и другие. Фиксированная параметризация метаэвристических алгоритмов не в полной мере учитывает динамику пространства поиска, что ограничивает качество принимаемых проектных решений. На основе анализа комплекса проектных метрик предложена динамическая модель, отражающая текущее состояние поискового процесса, включая уровень структурного разнообразия популяции и признаки стагнации. С учетом предложенной модели разработана структура адаптивного метаэвристического алгоритма с замкнутым контуром параметрического управления, где выполняется корректировка параметров для согласования интенсивности глобального и локального поиска. Научная новизна заключается в оригинальной конфигурации набора метрик (скорость улучшения целевой функции δt, разнообразие популяции Dt, локальная неоднородность ландшафта поиска Ht, индикатор стагнации St) и способе их интеграции в контур параметрического управления. В отличие от ресурсоёмких нейросетевых архитектур, требующих значительных вычислительных затрат и обучающих выборок, предложенная аналитическая модель обеспечивает интерпретируемость процесса адаптации и высокую вычислительную эффективность. Для подтверждения эффективности подхода построена программная подсистема, реализующая процесс моделирования и вычислительного эксперимента. Результаты экспериментов на тестовых топологиях различной размерности и плотности связей показали, что по сравнению с алгоритмами с фиксированной многоэтапной настройкой применение разработанного алгоритма позволило повысить интегральный показатель качества размещения на 8-15 % для структур с низкой плотностью связей и на 12-25 % для структур с высокой плотностью связей, уменьшить дисперсию результатов при множественных итерациях в 1,3-2,2 раза, сократить число циклов стагнации и снизить чувствительность к начальному состоянию популяции. Полученные результаты подтверждают повышение качества и эффективности проектных решений, устойчивость разработанного алгоритма размещения и свидетельствуют о практической применимости предложенного подхода. Статья будет полезна специалистам, занимающимся автоматизацией проектирования и интеллектуальным анализом при разработке.

Abstract

The paper considers the problem of parameterization of a metaheuristic algorithm for placing components of very large-scale integrated circuits (VLSI) under conditions of increasingly complex topologies and constraints of modern technological standards. The relevance of the study is due to the growth in the dimensionality of the designed circuits, an increase in the density of interconnections, and the increasing complexity of the design solution space, all of which limit the effectiveness of applied algorithms with static parameters. The problem statement includes the formation of a set of design metrics, such as wire length, density, placement area, crossing index, and others. Fixed parameterization of metaheuristic algorithms does not fully account for the dynamics of the search space, which limits the quality of the design solutions made. Based on the analysis of the set of design metrics, a dynamic model is proposed that reflects the current state of the search process, including the level of structural diversity of the population and signs of stagnation. Taking into account the proposed model, the structure of an adaptive metaheuristic algorithm with a closed-loop parameter control loop is developed, where parameters are adjusted to coordinate the intensity of global and local search. The scientific novelty lies in the original configuration of a set of metrics (objective function improvement rate δt, population diversity Dt, local landscape heterogeneity Ht, stagnation indicator St) and the method of their integration into the parameter control loop. In contrast to resource-intensive neural network architectures that require significant computational costs and training samples, the proposed analytical model ensures the interpretability of the adaptation process and high computational efficiency. To confirm the effectiveness of the approach, a software subsystem was built that implements the simulation and computational experiment process. The results of the experiments on test topologies of various dimensions and connection densities showed that, compared to algorithms with static parameterization and fixed multi-stage tuning, the application of the developed algorithm made it possible to increase the integral placement quality metric by 8-15% for structures with low connection density and by 12-25% for structures with high connection density, reduce the variance of results over multiple runs by a factor of 1.3-2.2, reduce the number of stagnation cycles, and decrease sensitivity to the initial state of the population. The obtained results confirm the improvement in the quality and efficiency of design solutions, the robustness of the developed placement algorithm, and indicate the practical applicability of the proposed approach. The article will be useful for specialists engaged in design automation and intelligent analysis in VLSI development.