Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Hybrid Bioinspired Algorithm for Forming Standard Cell Lines in the Design of the VLSI Topology
Authors
	Lebedev B.K.
	Lebedev O.B.
Date of publication
	2018
DOI
	10.31114/2078-7707-2018-1-180-187
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
Library reference
	Lebedev B.K., Lebedev O.B. Hybrid Bioinspired Algorithm for Forming Standard Cell Lines in the Design of the VLSI Topology // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2018. Issue 1. P. 180-187. doi:10.31114/2078-7707-2018-1-180-187
URL of paper
	http://www.mes-conference.ru/data/year2018/pdf/D014.pdf