Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Bioinspired VLSI chip planning methods
Authors
	Lebedev B.K.
	Lebedev O.B.
Date of publication
	2016
Abstract
	The planning problem is formulated as follows. There is a set of modules M = {mi | i=1,2,…,n}. The floorplan for the set of modules Ì is a rectangle R divided by vertical and horizontal lines into the set of rectangular blocks r ; each such block contains the module mi . In our work we use a slicing floorplan with a slicing structure. A slicing structure can be represented by a binary tree. The leaves of this tree are the vertices corresponding to regions, and the internal vertices correspond to cuts. The purpose of optimization is minimization of the total area of plan R, at observance of restrictions. In work for the decision of a planning VLSI problem is used new, offered by authors, the swarm intelligence paradigm - an ant tree (trees ant colony optimization (T-ACO)), based on idea of an indirect exchange - stigmiergy, allowing to carry out tree synthesis. Presentation of the optimization problem as a paradigm of T-ACO is based on two key points: the formation of the graph to find solutions G and cultivation of trees on graph G. Graph G = (SCM, U), C = {ci | i = 1,2, ..., nc}, corresponding to the cuts, M = {mi | i=1,2,…,n}- the set of modules, U -the set of edges is constructed in the following manner. In the beginning on the vertices of set C are formed a complete graph. The edges are undirected. Entered the starting vertex S, which are linked with each vertex of C. Further, each vertex ci are linked with all vertices nm of the set M . In general, the search for a solution of the problem is carried out team of ants A = {ak | k = 1,2, ..., nk}. Construction of tree by ants begins with a starting vertex S. Process of finding solutions is iterative. At each iteration of the ant tree algorithm each ant ak grows in the graph G a binary tree, which is the solution of the problem. Each iteration l consists of three phases. In the first phase of each iteration, each ant ak grows its own binary tree Dk. Binary tree is grown on the basis of graph G from the root to the leaves. At each step of growing the tree is selected vertex of the graph G, which is linked with one of the previously selected and included in the tree edges. In the second stage of iteration, each ant lay pheromone on the edges of the tree constructed by him. In the third stage, the total evaporation of pheromone on the edges of the graph G. After all of the steps in the iteration is the agent with the best solution, which is stored. The time complexity of the algorithm - O (n2), where n - the number of modules.
Keywords
	aided design, planning, VLSI, ant colony, ant tree, adaptive behaviour, optimization.
Library reference
	Lebedev B.K., Lebedev O.B. Bioinspired VLSI chip planning methods // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2016. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2016. Part 1. P. 187-193.
URL of paper
	http://www.mes-conference.ru/data/year2016/pdf/D138.pdf