Hybrid Bioinspired Algorithm for Forming Standard Cell Lines in the Design of the VLSI Topology

Lebedev B.K., Lebedev O.B. (Taganrog Institute of Technology, Southern Federal University)
Abstract - A hybrid one-dimensional package algorithm based on the integration of the ant algorithm and genetic search is proposed to solve the problem of placing standard cells in the design of the VLSI topology. Integrable algorithms are based on the use of collective evolutionary memory, which has different principles of its organization. In this regard, the integration of metaheuristics of the ant algorithm and genetic evolution provides a broader overview of the search space and a higher probability of localizing the global extremum of the problem. The connecting link of this approach is the data structure describing the solution of the problem. The paper proposes an approach to the construction of data structures that provide the possibility of simultaneous use in ant and genetic algorithms. Interpretation of the decision formed by the ant is a route on the solution search graph, Transformation of the route into the list is trivial. Interpretation of the solution formed by the genetic algorithm is a chromosome whose structure is identical to the list structure. To obtain a solution, the chromosome is decoded using a standard packing procedure. The composite architecture of the multi-agent bionic search system is proposed to solve the problem of one-dimensional packaging based on the integration of the ant algorithm and genetic evolution. The structure of the ant algorithm serves as the supporting structure of the hybrid algorithm. Mechanisms of genetic evolution are used to modify the population of solutions formed at each iteration by an ant colony. Described are search procedures in the space of solutions, methods of deposition and evaporation of pheromone, mechanisms of genetic search. Unlike the canonical paradigm of the ant algorithm, an ant on the vertices of the search graph G = (X, U) constructs a route with a partition into parts. This made it possible to reduce the combinatorial complexity of the problem. To conduct objective experiments, we used well-known test problems presented in the literature and the Internet. The tasks on which the developed algorithm was tested are available in the OR-objects library (http://www.ms.ic.ac.uk/info.html). To draw up reliable conclusions, not one, but a series of experiments-experiments was carried out. The developed hybrid algorithm allowed to obtain optimal solutions for all set tasks. The temporal complexity of the algorithm, obtained experimentally, practically coincides with the theoretical studies and for the considered test problems is O(n2)- О(n3).

Keywords - VLSI; placement of standard cells; one-dimensional packing; ant algorithm; genetic search; hybridization; optimization

Гибридный биоинспирированный алгоритм формирования линеек стандартных ячеек при проектировании топологии СБИС

Лебедев Б.К., Лебедев О.Б. (Таганрогский технологический институт Южного Федерального Университета, г. Таганрог)
Аннотация - Предлагается гибридный алгоритм одномерной упаковки, основанный на интеграции муравьиного алгоритма и генетического поиска для решения задачи размещения стандартных ячеек при проектировании топологии СБИС. Описываются поисковые процедуры в пространстве решений, способы отложения и испарения феромона, механизмы генетического поиска. Для проведения объективных экспериментов были использованы известные тестовые задачи, представленные в библиотеке OR-объектов (http://www.ms.ic.ac.uk/info.html). Временная сложность алгоритма, полученная экспериментальным путем, совпадает с теоретическими исследованиями и для рассмотренных тестовых задач составляет О(n2)- О(n3). Разработанный алгоритм позволил получить оптимальные решения для всех задач набора.

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