Routing algorithm.
Area of application.
The given method can be used in such tasks:
- Designing of printed-circuit-boards and integrated microcircuits
- Graph and network management, layout
computation - Computer graphics
Description.
This algorithm concerns to routers with no routers grid. The execution of connections is made originally at macro level. Connection is the line that connects two points. Plane, accessible to realization of connections, is broken on regions. If, for example, two rectangular components are located beside, region is a part of a plane, located between these components.
In limits of region each connection is described by a code. The code except for number of connection consists of three numbers. The first number is type of connection. Type determines what two parts of border from four parts are connected by this connection. Two following numbers are numbers of the contacts, determining end points lying on border of region. At realization of the next connection code descriptions of other connections are taken into account.
At macro level the sequence of regions, through which line will be carried out, is determined. This determination is carried out on the basis of two criteria, which are length of a connection and minimum of crossings between connections. Crossings between connections are caused by their topological properties. The mathematical methods of optimum control can be used to improve topological properties of connections and by that reduce number of crossings. In the experimental program the determination of an optimum way was carried out with the help of a method of Dynamic programming. It provides high speed. Other optimization method may be used too. Can be constructed graph, in which the vertices correspond to connections, and the edges correspond to crossings between them. The distribution of connections on layers is reduced to cutting of graph.
At the following stage the shape of a connection is determined within the borders of region. Thus all other connections located on the given region are taken into account. It achieved uniformity of accommodation of connections. In such tasks, as the designing of printed-circuit-boards, thus is achieved high density of wire. In the graphic with the help of this method it is possible to realize gradient filling and more complex color patterns. The given method is used in the program " Images Generator ". The description of the program is http://www.imagesgenerator.com. The address to load program is http://www.imagesgenerator.com/ImagesGeneratorSetup.zip . Program is executed in VB. ActiveX DLL, which can be used in the other programs, is executed.
VIDEO 'Method of topological routing' http://youtu.be/iJx4CYlOxoo
Examples.
example 1.
 |
In figure the result of use of the program " Images Generator " is given. Program may be loaded here. |
example 2.
 |
In figure the result of use of the experimental program, in which the method of Dynamic programming is used, is given. The program is executed in a Fortran
|
example 3.
Experimental program, in which the described method is used, can be loaded from this address http://www.imagesgenerator.com/res/IMAGES/star.zip. Program is executed in Qbasic.
Proceedings.
The scientific works with the description of the given algorithm are published in the several editions of former Soviet Union, among which central and academic editions are. They are
-
Panasjuk S. L. Algorithm of routing with determination of an optimum way by a method Dynamic Programming. // Electronic industry. 1981. Part 4,-P. 14-18.
-
Panasjuk S. L. Algorithm of routing of connections in the channel. // Microelectronics. 1985. V.14 - № 6. P. 490-496.
-
Panasjuk S. L. Automatic designing of topology of irregular structures. // Microelectronics. 1985. V.14 - № 6.- P. 497-500.
Or in Russian: -
Панасюк С. Л. Алгоритм трассировки с определением оптимального пути методом Динамического программирования. // Электронная промышленность. 1981. Вып. 4, -С. 14 -18.
-
Панасюк С. Л. Алгоритм трассировки соединений в канале. // Микроэлектроника. 1985. Т.14 -№6. -С. 490-496.
-
Панасюк С. Л. Автоматическое проектирование топологии нерегулярных структур. // Микроэлектроника. 1985. Т.14 -№6. -С. 497-500.