Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Distribution of connections by layers in multi-layer global routing
Authors
	Lebedev O.B.
	Lebedev B.K.
	Schelokov A.N.
Date of publication
	2022
DOI
	10.31114/2078-7707-2022-3-24-31
Abstract
	The paper considers an algorithm for the distribution of compounds by layers in the problem of multilayer global tracing based on bioinspired search methods. The solution of the global tracing problem is based on an approach that includes two stages. At the first stage, the problem of single-layer tracing is solved. On the second – «distribution of connections by layers» is performed. The main goal of the global tracer is to minimize the maximum overflow γ or limit it. As a result of single-layer tracing for each circuit on the graph, a network is built in the form of a Steiner tree. The vias can be located at the vertices of the Steiner tree. Each network is represented as a set of fragments. Each fragment represents a two-terminal connection connecting two vertices of the Steiner tree xi and xj. The task of distributing connections over layers is to transform each network from a given single-layer routing solution to its analogue in an l-layer global routing solution in such a way that, when projected, we obtain the same topology result as for the original network. The solution must satisfy the maximum congestion constraint. At the first stage, independently of each other, each network from the given single-layer routing solution is transformed into its analogue in the l-layer global routing solution with minimization of the cost of interlayer transitions. At the second stage, adaptive search methods are used to redistribute connections across layers to fulfill the maximum congestion limit while minimizing the total number of vias. The solutions obtained in the process of performing global tracing by the proposed algorithm are 2-5% better in comparison with the results achieved by known tracers. The overall time complexity estimate lies within O(n2)-O(n3).
Keywords
	multilayer global tracing, connection distribution by layers, ant colony algorithm, optimization
Library reference
	Lebedev O.B., Lebedev B.K., Schelokov A.N. Distribution of connections by layers in multi-layer global routing // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2022. Issue 3. P. 24-31. doi:10.31114/2078-7707-2022-3-24-31
URL of paper
	http://www.mes-conference.ru/data/year2022/pdf/D050.pdf