SWARMS OVER-THE-CELL TRACING ALGORITHM
This paper presents a synthesis algorithm of single layer routing sketch in over-the-cell (OTC) field VLSI layout. Develop new mechanisms for solving the problem tracing, using mathematical methods, which lays down the principles of the natural mechanisms of decision-making. For the synthesis of single layer routing sketch uses a new paradigm of combinatorial optimization tree ant colony optimization (T-ACO)), based on the ideas of adaptive behavior of an ant colony and first of all on the idea of indirect exchange - stigmiergy, which allows for the synthesis of a tree. Unlike the canonical paradigm of ant algorithm the ant at a special graph to find solutions G = (X, U) is constructed decision trees. The structure and method of forming a special graph to find solutions G = (X, U) are described. Are offered the principles of interpretation of the ants solutions in the form of a single layer trace sketch. The problem is solved in various productions with different type of trace areas boundaries. Program OTC trace was implemented in C ++ for the IBM PC. In all of these productions was received result close to optimum. When using "broken" border procedures "sticking" and consistent trace OTC able to further reduce the overall density of channels up to 40 %. The proposed router is fully applicable to "gridless" trace of different widths connections. Experimental researches were carried out on IBM PC. The time complexity of the algorithm, obtained by experiment, almost the same as the theoretical research and test problems is considered about O(n 2), where n - number of connections. For the objective of the experiments were used known test problems represented in the literature and the Internet. To provide reliable conclusions was held not one but a series of experiments, experiments. In comparison with existing algorithms improve the results achieved on 2-3 %.