[pic]

VLSI Routing for Enhanced Performance through QUANTUM BINARY PARTICLE SWARM OPTIMIZATION

Arkabandhu Chowdhury
(Roll no.- 000810701048)
Souvik Kumar Saha
(Roll no.- 000810701053)

In completion of the final year project under the guidance of Dr. S. K. Sarkar, H.O.D., ETCE.

Introduction to VLSI Routing

The design of Very Large Scale Integrated (VLSI) circuits is one of the broadest areas in which the methods of combinatorial optimization can be applied. In the physical design process of VLSI circuits, the logical structure of a circuit is transformed into its physical layout. Detailed routing is one of the important tasks in this process. A detailed router connects pins of signal nets in a rectangular region under a set of routing constraints, such as the number of layers, the minimal space between the wires and the minimum wire width. The quality of this detailed routing has a strong influence on the performance and production costs of the circuit. The detailed routing in a rectangular region with pins exclusively located on the upper or lower boundary of the routing region is called “channel routing”. It is one of the most commonly occurring routing problems in VLSI circuits. The channel routing problem is NP-complete and, therefore, there is no deterministic algorithm to solve it in a fixed time frame and the problem of finding a globally optimized solution is still open. There have been plenty of results in this topic from the last few decades.

➢ The question that arises naturally is: What is a channel?

A channel is a horizontal routing area with fixed pins on the top and bottom. There are no pins to the right or left, but certain nets may be designated as route-to-the-edge.

Thus we say that there may be “floating pins” to the right or left. Each pin is designated by a number. All pins with the same number must be routed together. Pins with different numbers must be electrically isolated from one another. The input to a channel routing problem is two sets of numbers, one that gives the pin numbers at the top of the channel, and the other that gives the pin numbers at the bottom of the channel. A pin-number of zero designates an empty pin that is never connected to anything.

Classification of VLSI Routing

➢ VLSI routing can be basically of two kinds:-

1. Global routing:-

In the global routing phase, it's required to find an initial and rough solution of the routing problem under consideration. There are no constraints on the higher levels of this router. First, the routing area is divided into coarse regions. Then, the global router processes the net lists and determines through which regions each net will pass through. The exact location of these nets is to be determined in the next phase by the detailed router. The size of the routing regions depends on the routing system. There are bins of a gate array or sea of gates design, routing regions for standard cell design and divisions for more non-uniform block based layouts.

[pic]

Several Cell designs

This division can be represented by a graph G, whose vertexes V represent the routing regions, and the set of edges E represent the connections to neighbouring regions. Given a set of nets to be routed, N, where the ports of each net is located in one of the routing regions V, it's required to connect these nets and determine their routes through the graph G . Every edge e is given a weight to represent its wire capacity (the number of wires that can pass through it) called the boundary capacity or supply capacity (e), and another value to represent the number of wires routed through it called flow (flow(e)).

2. Detailed Routing:-

With up gradation in nanotechnology, the approximations of the global routing phase do not yield good results when considered for high performance techniques. So, most modern applications take detailed routing into account. Here, the inputs are the channels and approximate routing from the global routing phase. With these inputs, the detailed routing determines the exact route and layers for each net. Thus, it is more customized to cater to ASIC (Application Specific Integrated Circuits). The primary objective is to determine a valid routing path minimizing the area (congestion) and meeting timing constraints. Nowadays, additional objectives such as minimizing the number of vias and the power consumption are coming into the frame. Our proposed method of QBPSO also works in the detailed routing domain. Others including switchbox routing and grid graph routing also come under its purview.

Thus, we have several types of VLSI routers as classified below:

[pic]

Classification of VLSI Routers

When we consider the performance analysis of VLSI routing, we take into consideration a number of factors including Netlength, electrical delay and number of vias. But, by far, the most importance performance criterion is the minimization of crosstalk. We now discuss these features of a VLSI circuit in some details.

Features of a VLSI Circuit

1. Crosstalk:-

The inter-wire spacing in a VLSI chip becomes closer as the VLSI fabrication technology rapidly evolves. The coupling capacitance between wires is comparable to or larger than the ground capacitance in MOS technologies if the wire-to-wire spacing is near or less than 1 pm. Coupling capacitance is the main source of crosstalk. In fact, crosstalk between two wires is proportional to their coupling capacitance, which in turn, is proportional to their coupling length (the total length of their overlapping segments) and inversely proportional to their separating distance.

Since crosstalk can cause inadvertent logic transitions, it is usual to specify the upper bound of the allowable crosstalk (called crosstalk constraint) for each net in the design specification. Accordingly, it is important to minimize the crosstalk or to satisfy the crosstalk constraints for fast and safe VLSI design. Routing problems with crosstalk constraints are more difficult to solve than conventional routing problems because the coupling capacitance between wire segments are not only decided by how each individual wire is routed, but also by the relative positions of the wire segments. Now, since crosstalk depends not only on the coupling capacitance between the nets, but also on the frequency of the signals travelling in the nets, in order to simplify our proposed algorithm, we have assumed that the circuit operates at a high frequency. Thus, crosstalk can be expressed as the sum of crosstalks in all nets, which, in turn, is proportional to the length of parallel segments adjacent to each net.

2. Netlength:-

A channel has two open ends, the left and right sides of the rectangle. The other two sides (viz., the upper and lower sides of the rectangle) have two rows of terminals. The terminals are aligned vertically in columns. For the integrated circuits, typically the horizontal segments and the vertical segments are made through contact windows, called the “via holes”. A set of terminals that need to be electrically connected together is called a net. In other words, the collection of all pins with the same number is called a net. In the simplest algorithms, each net is given a single horizontal segment which runs from the first occurrence of a pin to the last occurrence. Vertical segments are added to connect the horizontal segment to the pin. If Net A appears at the top of column x and Net B appears at the bottom of column x, then the horizontal segment for Net A must be routed above the horizontal segment form Net B. If this is not done, the vertical segments of Net A and Net B will short together. The terminals of the same net are assigned the same number. The unconnected terminals are assigned number zero. Previous attempts to minimize the net length has included inception of a function which considers the length of each net with a quadratic growth. Thus, an increased “pressure” has been put for the net length to be minimized. In some sequential algorithms, doglegging has been used where a routing path of a net is split into two or more horizontal segments on different tracks.

3. Electrical Delay:-

Electrical delay is defined as the time it takes for signals to propagate through the circuit. As integrated circuit features decrease, electrical delay is increasingly governed by the routing delay (rather than delay within the logic cells) and as a consequence needs to be considered in the routing process. Previous attempts at minimizing the electrical delay has included a new measure of the netlength to better reflect the electrical delay in submicron regime. Decreasing the number of vias has also been linked to decrease of the electrical delay.

4. Channel and Switchbox Routing Problem:-

The channel routing problem (CRP) is the problem of computing a feasible route for the nets so that the number of tracks required (and hence the channel area) is minimized. We say that a routing solution is feasible if all the nets can be assigned without any conflict. We assume that in a feasible routing solution, the routing wires do not extend beyond the left and right ends of the channel. Therefore, in order to minimize the routing area, the horizontal wire segments of the nets need to be distributed amongst a minimum number of tracks. This process of assignment of the horizontal wire segments to tracks is guided by two important constraints, viz., the horizontal constraints and the vertical constraints. For a channel routing problem with crosstalk constraints, the horizontal wire segments in the initial routing solution are re-assigned to tracks to satisfy the crosstalk constraints and to minimize the total crosstalk in the nets. Re-assigning the horizontal wire segments changes the relative positions of the horizontal wire segments and the lengths of the vertical wire segments, which in turn, change the values of the crosstalks in the nets. Since the assignment process re-assign wire segments to existing rows, channel height does not change after the assignment process. For a switchbox routing problem (SRP) with crosstalk constraints, the assignment process is carried out iteratively between the horizontal and vertical wire segments in order to satisfy the crosstalk constraints and to minimize the total crosstalk in the nets. The iterative assignment process continues until no more improvement can be obtained on the values of the crosstalks.

[pic]

The VLSI channel (left) and switchbox (right) routing problem and possible routing solutions.

Problem Formulation

The VLSI routing problem is defined as follows. Consider a rectangular routing region with pins located on two parallel boundaries (channel) or four boundaries (switchbox). The pins that belong to the same net need to be connected subject to certain constraints and quality factors. The interconnections need to be made inside the boundaries of the routing region on a symbolic routing area consisting of horizontal rows and vertical columns. Two layers are available for routing in our model. We define a segment to be an uninterrupted horizontal or vertical part of a net. Thus, any connection between two pins will consist of one or more net segments and is referred to as an interconnection. A connection between two net segments on different layers is called a via. New measures of netlength are needed that reflect the electrical delay better than the commonly used minimization of the sum of the lengths of all nets. One such measure is accomplished by minimizing a nonlinear function of the lengths of the nets. Under many technologies, a first order approximation to the electrical delay is the product of the resistance and capacitance of the interconnection. With a fixed width for the interconnection, this product is a quadratic function of the length of the interconnection. Hence, rather than minimizing the sum of the lengths of the nets, we minimize a quadratic function of their individual lengths. Crosstalk between two parallel routed net segments decreases as their separating distance increases. Since it can be assumed that crosstalk between two nonadjacent net segments will be shielded by other nets between them, we simplify the computation by considering crosstalk only between adjacent net segments. We note that the algorithm can be easily extended to consider crosstalk between nonadjacent net segments as well.

➢ Resulting from these considerations, three objectives are used in this work to assess the quality of the routing:-

• Netlength

• Number of Vias

• Parallel Routed Net Segments and Crosstalk

Hence, as common in VLSI layout design, the routing problem belongs to the domain of multi-objective optimization. We use an objective function that is composed of terms which represent our three objectives combined with weight factors. Our goal is to minimize the sum of these terms by measuring the cost of the solution with respect to user-defined weights for each of the objectives. We have used a Quantum Binary Particle Swarm Optimizer algorithm in order to minimize this sum. First let us have a brief description of our algorithm.

Overview of the Algorithm

1. Classical PSO:-

Particle swarm optimizer (PSO), introduced by Kennedy and Eberhart in 1995 [11][12] is one of the most useful and important optimizing technique. Its very idea has been derived from the flocking nature of birds or fish. Usually optimization problems can be expressed as

Min(fx), x =[x1,x2,...........,xD]

where D is the number of the parameters to be optimized.

In PSO, each particle with its corresponding position and velocity in the D dimensional problem space represents a potential solution. Every particle flies through the space by exchanging useful information of fitness values of others and thereby finding the global best position (with the least fitness value). It also takes into account its personal best position so far in the search process and combining these two results the particle updates its velocity according to a pre-defined inertia weight on its personal best as well as global best position. Thus every particle has a tendency to fly towards better search area over the course of search process. The velocity Vid and position Xid updates of dthdimension of the ithparticle are presented below:

Vid=w* Vid + c1* rand1 id *(pbest id – X id) + c2* rand2 id *(gbestd – X id) (1)

X id = X id + V id (2)

where c1 and c2 are the acceleration constants, rand1id and rand2id are two uniformly distributed random numbers in the range [0,1]. X i = (X i1, X i2, ......... , X iD) is the position of the ithparticle; pbesti = (pbest i1, pbest i2, ......... , pbest iD) is the best previous position yielding the best fitness value pbesti for the ithparticle; gbest = (gbest1, gbest2, ......... , gbestD)is the best position discovered by the whole population; V i = (V i1, V i2, ......... , V iD) represents the rate of the position change (velocity) for particle i. w is the inertia weight used to balance between the global and local search abilities.

Classical PSO contains two main variants: global PSO and local PSO. In the local version of PSO, each particle’s velocity is adjusted according to its personal best and the best performance achieved so far within its neighborhood instead of learning from the personal best and the best position achieved so far by the whole population in the global version. The velocity updating equation becomes:

Vid=w* Vid + c1* rand1 id *(pbest id – X id) + c2* rand2 id *(lbestd – X id) (3)

Where lbesti = (lbest i1, lbest i2, ......... , lbest iD) is the best position achieved within its neighbourhood.

[pic]

Particle initialization in the search space

[pic]

Geographical & Social Neighbourhood

[pic]

Global Neighbourhood

[pic]

Particles Adjusting Their Positions

Focusing on improving the local version of PSO, different neighborhood structures are proposed and discussed [13][14][15][16][17]. Except these local PSO variants, some variants that use multi-swarm [18], subpopulation [19] can also be included in the local version PSOs if we treat the sub-groups as special neighborhood structures. In the existing local versions of PSO with different neighborhood structures and the multi-swarm PSOs, the swarms are predefined or dynamically adjusted according to the distance. Hence, the freedom of the swarms is limited.

Binary PSO Algorithm:-

Discrete Binary Particle swarm optimizer (BPSO) is introduced by Kennedy and Eberhart in 1995 [20]. In the binary version of PSO each particle is represented by a string of zeroes and ones. In case of binary PSO, the particle’s personal best and global best is updated as in continuous version [21]. The major difference between binary PSO with continuous version is in the way velocity is defined. Velocity is updated in similar way as in continuous version but the velocity is mapped from real value to the range [0,1]. Sigmoid function is used as the normalized function to do the mapping. Velocity mapping for the ith particle for dth dimension can be defined as:

[pic] (4)

Velocity is updated as in equation (2).

[pic]

(5)

where w represents the inertia factor and φ1 ,φ2 two positive integer to give the weightage for local best and global best of particles.

New position of particle can be found using the following equation.

[pic] (6)

So, the velocity vi,d(t) component become the probability parameter for xi,d(t) to be set (1) or clear (0).

Quantum Discrete PSO:-

The main problem lies in the binary version of the PSO proposed by Kennedy and Eberhart lies in the parameter selection [22]. Some parameter effect is found to be opposite to that of the real valued PSO. For binary PSO small value of vmax promotes exploration. Choosing the inertia factor is the major difficulty in case of binary PSO. For binary PSO, values of w less than1 prevent convergence. For values of −1< w < 1, velocity component becomes 0 over time. If w is greater than 1 velocity increases over time and all bits become 1. If inertia factor is not chosen properly the PSO particles or dynamics may not converge. A new variant of binary version of PSO is proposed by Yang in 2004 [23]. In this version two different populations are maintained.

A population of quantum particle vectors:

[pic]

where [pic] (7)

A population of discrete particle vectors:

[pic]

where [pic] (8)

M represents the number of particle and N is the dimension of each particle.

Position update is done by flipping rule:

[pic] (9)

Quantum populations are updated as follow:

[pic]

where [pic]

and [pic] (10)

where w is the inertia factor and c1, c2 are the acceleration coefficients.

The problem regarding non-convergence of binary PSO can be overcome with this algorithm.

=================================================================

Some Benchmarks used for Channel Routing

------------------------------------------------------------------------------------------

Routing constraints:

- Manhattan geometry
- Two layers
- Layer change through vias
- No crossing of nets
- Perimeter of channel is not used for routing

Quality factors of routing results:

- Number of rows
- Net length
- Number of vias

Benchmarks:

(1) Yoshimura-Kuh channel

0 1 4 5 1 6 7 0 4 9 10 10
2 3 5 3 5 2 6 8 9 8 7 9

(2) Joo 6_12

2 1 4 5 1 6 7 10 4 9 10 10
3 1 5 3 5 2 6 8 9 8 7 9

(3) Joo 6_13

1 6 1 10 2 9 3 5 5 4 7 0 11 8 10 4 11 8
2 5 4 9 5 4 1 4 3 0 6 3 9 0 0 7 0 7

(4) Joo 6_16

1 6 1 8 2 7 3 5 5 4 7
2 5 4 7 5 4 1 4 3 8 6

(5) Burstein's difficult channel

1 2 2 4 5 8 10 9 9 6 7 3
2 4 5 8 8 10 9 7 6 3 3 1

(0 ... pin is not occupied)

Results:

[pic]

Routing solution of Joo6_16

[pic]

Routing layout of Burnstein’s Difficult Channel

[pic]

[pic]

Average convergence behaviour of behaviour for Burnstein’s Difficult Channel

[pic]

Distribution of the number of generations needed to achieve the best result of Burnstein’s Difficult Channel

[pic]

Plot of Net Lengths (in multiples of wavelengths λ) of various benchmarks (1-5)

[pic]

Plot of Columns, rows and vias of various benchmarks (1-5)

Table showing the results for various benchmarks:

| | | | | |
|Benchmark |Columns |Rows |Netlength |Vias |
|Yoshimura-Kuh channel |12 |6 |38 |12 |
|Joo 6_12 |12 |4 |40 |14 |
|Joo 6_13 |18 |8 |16 |16 |
|Joo 6_16 |11 |6 |81 |12 |
|Burstein's difficult channel |12 |4 |33 |8 |

Conclusions and Open Problem:-

The topics we have handled in this work were not completely covered. There are several unanswered questions that remain open and deserve to be researched. In the routing algorithm, for example: What is the order of nets that should be used in routing? How can we improve the memory requirements of our algorithm? Can we estimate congestion in the model? How can specific rules be established to improve the quality of the routed layout? How can we handle variable width in routing? What can be the other applications of QPSO? This has opened a door for more questions that deserves the attention of researchers in this field. All these questions are left as open questions for further research and work.

Acknowledgement:-

Special thanks to Prof. Dr. S. K. Sarkar (Jadavpur University) for his constant guidance and support. Finally, the authors wish to thank the Electronics and Telecommunications Department, Jadavpur University, for providing the facilities crucial to this work.

References:-

1. Jens Lienig, A Parallel Genetic Algorithm for Performance-Driven VLSI Routing, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 1, NO. 1, APRIL 1997 2. Pal R. K. (2000). Multi-Layer Channel Routing:Complexity and Algorithms, Narosa Publishing House, New Delhi (Also published from CRC Press, Boca Raton, USA and Alpha Science International Ltd., UK). 3. Sachin S. Sapatnekar, A Timing Model Incorporating the Effect of Crosstalk on Delay and its Application to Optimal Channel Routing, Ieee Transactions On Computer-Aided Design Of Integrated Circuits And Systems, VOL. 19, NO. 5, MAY 2000 4. Mihai Banu and Vladimir Prodanov, Recent Advances in VLSI Routing, CMOS Emerging Tech. Workshop, 2006, Banff, Canada 5. Moustafa A. Sayed and Ehab Y. Abdel Maksoud, Interconnect Synthesis in High Speed Digital VLSI Routing, Int. J. Open Problems Compt. Math., Vol. 2, No. 3, September 2009 6. D. Zhou and R.-M. Li., Design and verification of high-speed VLSI physical design. Computer Science and Technology, 20(2):147-165, 2005. 7. C. W. Sham and E. F. Young, Congestion prediction in early stages. Proc. 5th Int. Workshop on System level interconnect prediction (SLIP '05), New York, NY, USA, pp. 91-98, 2005. 8. David Szeszler, Combinatorial Algorithms in VLSI Routing, PhD Dissertation, 2005 9. Achira Pal et al., Graphs - The Tool to Visualize the Problems in VLSI Channel Routing, Assam University Journal of Science & Technology, Physical Sciences and Technology Vol. 7 Number II 73-83, 2011 10. Szkaliczki T., Polynomial Algorithms in VLSI Routing, PhD. dissertation, BME (1996). 11. R. C. Eberhart, and J. Kennedy, "A new optimizer using particle swarm theory", Proc. of the Sixth Int. Symposium on Micromachine and Human Science, Nagoya, Japan. pp. 39-43, 1995 12. J. Kennedy, and R. C. Eberhart, "Particle swarm optimization ". Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ. pp. 1942-1948, 1995 13. J. Kennedy, "Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance". Proc. of IEEE Congress on Evolutionary Computation (CEC 1999), Piscataway, NJ. pp. 1931-1938, 1999 14. J. Kennedy and R. Mendes, "Population structure and particle swarm performance ". Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002),Honolulu, Hawaii USA. 2002 15. P. N. Suganthan, "Particle swarm optimizer with neighborhood operator," Proc. of the IEEE Congress on Evolutionary Computation (CEC 1999), Piscataway, NJ, pp. 1958-1962, 1999. 16. X. Hu and R. C. Eberhart, "Multiobjective optimization using dynamic neighborhood particle swarm optimization," Proc. IEEE Congress on Evolutionary Computation, Hawaii, pp. 1677-1681, 2002. 17. R. Mendes, J. Kennedy, and J. Neves, "The fully informed particle swarm: simpler, maybe better”. IEEE Transactions on Evolutionary Computation, 8(3):204 - 210, June 2004 18. T. M. Blackwell and J. Branke, "Multi-swarm optimization in dynamic environments". LNCS No. 3005: Proceedings of Applications of Evolutionary Computing: EvoWorkshops2004: EvoBIO, EvoCOMNET, EvoHOT, EvoISAP, EvoMUSART, and EvoSTOC, Coimbra, Portugal. pp. 489-500, 2004 19. M. Løvbjerg, T. K. Rasmussen and T. Krink, "Hybrid particle swarm optimiser with breeding and subpopulations ". Proc. of the Genetic and Evolutionary Computation Conference, (GECCO 2001), 2001. 20. Kennedy J., Eberhart R.C., "A discrete binary version of the particle swarm algorithm", IEEE International Conference on Systems, Man, and Cybernetics, 1997. 21. J. Kennedy, "Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance". Proc. of IEEE Congress on Evolutionary Computation (CEC 1999), Piscataway, NJ. pp. 1931-1938, 1999. 22. A. P. Engelbrecht, "Fundamentals of Computational Swarm Intelligence", Wiley, 2005. 23. Shuyuan Yang Min Wang Licheng jiao, "A quantum particle swarm optimization", Evolutionary Computation, 2004. CEC2004.

-----------------------
Graph Search

Steiner

Iterative

Hierarchical

Greedy

Left-Edge

River

Switchbox

Channel

Maze

Line Probe

Line Expansion

Restricted

General Purpose

Clock

Specialized

Power/Gnd

Routers

Detailed

Global

Maze