Journal of Artificial Evolution and Applications

Volume 2008, Issue 1 514879

Research Article

Open Access

An Improved Particle Swarm Optimizer for Placement Constraints

Sheng-Ta Hsieh,

Sheng-Ta Hsieh

Department of Electrical Engineering National Dong Hwa University Hualien 97401, Taiwan

Department of Communication Engineering Oriental Institute of Technology Taipei County 22061, Taiwan

Search for more papers by this author

Tsung-Ying Sun,

Corresponding Author

Tsung-Ying Sun

[email protected]

Department of Electrical Engineering National Dong Hwa University Hualien 97401, Taiwan

Search for more papers by this author

Chan-Cheng -Liu,

Chan-Cheng -Liu

Department of Electrical Engineering National Dong Hwa University Hualien 97401, Taiwan

Search for more papers by this author

Cheng-Wei Lin,

Cheng-Wei Lin

Department of Electrical Engineering National Dong Hwa University Hualien 97401, Taiwan

Silicon Motion Technology Corporation Jhubei City Hsinchu County 302, Taiwan

Search for more papers by this author

Sheng-Ta Hsieh,

Sheng-Ta Hsieh

Department of Electrical Engineering National Dong Hwa University Hualien 97401, Taiwan

Department of Communication Engineering Oriental Institute of Technology Taipei County 22061, Taiwan

Search for more papers by this author

Tsung-Ying Sun,

Corresponding Author

Tsung-Ying Sun

[email protected]

Department of Electrical Engineering National Dong Hwa University Hualien 97401, Taiwan

Search for more papers by this author

Chan-Cheng -Liu,

Chan-Cheng -Liu

Department of Electrical Engineering National Dong Hwa University Hualien 97401, Taiwan

Search for more papers by this author

Cheng-Wei Lin,

Cheng-Wei Lin

Department of Electrical Engineering National Dong Hwa University Hualien 97401, Taiwan

Silicon Motion Technology Corporation Jhubei City Hsinchu County 302, Taiwan

Search for more papers by this author

First published: 18 March 2008

https://doi.org/10.1155/2008/514879

Citations: 5

Academic Editor: Alex Freitas

Share a link

Email
Wechat
Bluesky

Abstract

This paper presents a macrocell placement constraint and overlap removal methodology using an improved particle swarm optimization (PSO). Several techniques have been proposed to improve PSO, such as methods to prevent the floorplan from falling into the local minimum and to assist in finding the global minimum. The proposed method can deal with various kinds of placement constraints and can process them simultaneously. Experiments employing MCNC and GSRC benchmarks show the difference in the efficiency and robustness of proposed method in the exploration for more optimal solutions through restricted placement and overlap removal compared with other methods. The proposed approach exhibits rapid convergence and leads to more optimal solutions than other related approaches; furthermore, it displays efficient packing with all the constraints satisfied.

1. Introduction

VLSI floorplanning is an important aspect in chip design. It involves the placement of a set of rectangular circuit modules (macrocells) on a chip to minimize the total area and the total interconnecting wire length and without overlap between two modules since larger chip sizes increase production cost while longer wire lengths increase power consumption and decrease system performance.

The physical placement of circuits in VLSI chips or system on chips (SoC′s) has been given constant attention in recent years. Early research on the placement problem applied force to reduce the overlap between cells [1]. However, [2–4] show the generation of overlap-free placements and [5, 6] show the generated layouts with cell overlaps. While allowing overlaps during the process of placement was shown to obtain better floorplanning solutions, this process could not guarantee the entire elimination of overlaps. Later, Vijayan and Tsay [7] proposed the topological overlap removal method, an approach that removes a redundant edge from two critical paths and repeats the process continuously until it makes a significant improvement on the layout area. However, the drawback to this approach was the random selection, if there were two or more edges qualified for removal, it cannot predict which removal will lead to a better placement. Asato and Ali [8] improved this method by removing all redundant edges from one of the constraint graphs following the iteration.

The recent approach, conducted by Alupoaei and Katkoori, proposed a macrocell overlap removal algorithm that was based on the ant colony optimization (ACO) method [9]. Each ant in the colony generated a placement based on the macrocells’ relative positions and information regarding the optimal placement obtained by previous colonies. The disadvantage to this macrocell movement procedure was that the initial relationship between macrocells would influence the final result directly, plus the result could be trapped in the local minimum.

All the approaches mentioned above have their advantages and disadvantages; however, none of them is able to cover placement constraint problems. Due to in the analog design, designers are also interested in a particular kind of placement constraint called symmetry, some recent literature on this problem can be found in [10, 11]. The floorplanner in [12] can handle alignment constraints which may appear in bus-based routing. The floorplanners in [4, 13, 14] can handle preplaced constraints, where some modules are fixed in position. Different approaches are used to handle the different kinds of constraints, but there are no unified methods that can handle all constraints simultaneously.

As opposed to these previously mentioned methods,this paper utilizes particle swarm optimization (PSO) with an overlap detection and removal mechanism to search for the optimal placement solution. PSO is a swarm intelligence method that roughly models the social behavior of swarms. The advantage with this behavioral model is the search process which allows stochastic return of particles towards previously successful regions in the search space. This method has been proven to be efficient on a plethora of problems in science and engineering.

In order to make PSO more capable when dealing with placement problems, a turnaround factor [15] is adopted to extend the particles’ search space. A disturbance mechanism [16] is also introduced to prevent the solution from falling into the local minimum. Furthermore, the proposed method can handle several kinds of placement constraints simultaneously, including boundary, preplaced, range, abutment, alignment, and clustering. Users can dictate a mixed set of constraints and their preferred way of arrangement for the assigned macrocell. The proposed floorplanner will then be able to place these macrocells based on the given criteria.

Section 2 contains the definition of various placement constraint problems; Section 3 describes the original PSO methodology; Section 4 presents the proposed methods; and Section 5 presents the experimental results, which aside from the comparisons with ACO and B^*-tree in unconstrained conditions, also contains the experiment results of situations involving different kinds of randomly selected multiconstraints in floorplanning. Section 6 of the paper contains the conclusion.

2. Placement Constraints

2.1. Cell Definition

During floorplanning, information is given to a set of macrocells; the information includes their width, length, and cell numbers. In this paper, the floorplanning problem is addressed with a number of placement constraints, other than the module information, some placement constraints are given between the modules. The goal of proposed method is to plan all macrocells’ positions on a chip such that all the placement constraints can be satisfied and the area and interconnection cost minimized.

In this paper, the notation c(i, x, y) is used to denote the ith cell’s location, where x and y are presented, ith cell’s position on x-axis and y-axis, respectively. Note that, the cell positions are defined as the cell’s lower left corner. Figure 1 illustrates these definitions.

Details are in the caption following the image — **Figure 1**
Open in figure viewer PowerPoint

Cell definition.

2.2. Relative and Absolute Constraints

In general, placement constraints can be classified as relative and absolute. A relative placement constraint describes the relationship between two modules, and an absolute placement constraint describes the relationship between a module and the chip. Using relative placement constraints, users can restrict the horizontal or vertical distance between two modules to a certain range of values; using absolute placement constraints, the placement of a module is modified with respect to the whole chip, like restricting a cell to a certain distance from the boundary of the chip. Modules classified under either kind of constraints can be set as restriction conditions for particle movement during the PSO evolution process. Details of the definition and applications will be described in the following section.

2.3. General Use Placement Constraints

Using the above specifications for absolute and relative placement criteria, many different kinds of placement constraints can be created. In this section, a few commonly used constraints will be picked up and show how each can be specified using a combination of the relative and absolute placement constraints.

2.3.1. Alignment

To align modules A, B, C, and D horizontally (Figure 2), the following constraints can be imposed:

()

The horizontal axes of each module to be restricted the same; they will thus align horizontally. A similar definition can be applied to their vertical alignment.

2.3.2. Abutment

To abut modules A, B, and C horizontally (Figure 3), the following constraints can be imposed:

()

where w_A and w_B are the widths of modules A and B, respectively. In this formulation, the horizontal axes of each module are the same; so they will align horizontally. It also restricts module B to being placed next to module A on the right-hand side, and so on. The end result is their horizontal abutment.

2.3.3. Preplace Constraint

To preplace module A with its lower left corner at axis (x₁, y₁) and module B with its lower left corner at axis (x₂, y₂) (Figure 4), the following constraints can be imposed:

()

Module A is restricted to be x₁ units from the left boundary and y₁ units from the bottom boundary. A similar definition can be applied to module B. Each restricted module will be preplaced with its lower left corner in the final packing.

2.3.4. Range Constraint

To restrict the position of module A in the range {(x_A, y_A) | x₁ ≤ x_A ≤ x₂, y₁ ≤ y_A ≤ y₂} (Figure 5), the following constraints can be imposed:

()

In this formulation, module A is restricted to be x₁ to x₂ units from the left boundary and to be y₁ to y₂ units from the bottom boundary, restricting module A to the designated rectangular region.

2.3.5. Boundary Constraint

To place module A along the left boundary and place module B along the bottom boundary in the final packing (Figure 6), the following constraints can be imposed:

()

In this formulation, module A is restricted to be 0 units from the left boundary, so module A will be abut with the left boundary in the final packing. Module B is restricted to be 0 units from the bottom boundary, so module B will abut with the bottom boundary as required.

2.3.6. Clustering Constraint

To cluster modules A and B around C at a distance of most units away vertically (Figure 7), the following constraints can be imposed:

()

In this formulation, the vertical distances of A and B from C are restricted to be at most a certain unit in vertical directions, so they will cluster around C at a vertical distance of at most h_C units away. The horizontal distances of A and B from C can also be restricted in a similar way.

3. Particle Swarm Optimization (PSO)

The PSO is a population-based optimization technique that was proposed by Eberhart and Kennedy [17] in 1995, in which the population is referred to as a swarm. The particles exhibit the ability of fast convergence to local and/or global optimal positions over a small number of generations.

A swarm in PSO consists of a number of particles. Each particle represents a potential solution to the optimization task. All of the particles iteratively discover a probable solution. Each particle generates a position according to the new velocity and the previous positions of the cell. This is compared with the best position generated by previous particles in the cost function and the best one is kept; each particle accelerates in the direction of not only the local best solution but also the global best position. If a particle discovers a new probable solution, other particles will move closer to explore the region in more details [18].

Let s denote the swarm size. In general, there are three attributes, current position x_i, current velocity v_i, past best position Pbest_i, and global best position Gbest, as the main guidelines for each particle in the search space. Each particle in the swarm is iteratively updated according to the aforementioned attributes. Assuming that the objective function f is to be minimized so that the particle contains N dimensions, the new velocity of every particle is updated using

()

For all j ∈ 1, …, N, v_i,j is the velocity of the jth dimension of the ith particle, w is the inertia weight of velocity [19], c₁ and c₂ denote the acceleration coefficients, r₁ and r₂ are elements from two uniform random sequences in the range (0, 1), and t is the number of generations. The new position of the ith particle is calculated as follows:

()

The past best position of each particle is updated by

()

The global best position Gbest found by all particles during previous three steps is defined as

()

4. PSO Algorithm for Macrocell Overlap Removal and Placement

The first step to using PSO as a way to handle the macrocell overlap removal and placement is defining each macrocell’s position as a dimension of a particle. That is, 20 dimensional particles can be used to optimize placement problems whose circuit contains 20 macrocells. The definition of the macrocells’ position is stated in the previous section. While a swarm consists of a number of particles, the particle’s movement will lead the module to find another potential or superior solution for placement. For the initial state of the placement, each module was randomly generated in the floorplanning and overlap was allowed. After a number of generations, the distance between each of the modules will shrink, meaning the chip size will get smaller. The overlap between the two modules will be eliminated by proposed overlap detection and removal mechanism.

4.1. Handling Placement Constraints by PSO

Both relative and absolute placement constraints can be set as a particle’s movement constraints and can be included in the PSO algorithm. Because of the combination of horizontal and vertical vectors into the particles’ moving vector, in this paper, a constraints handling process is instituted in the proposed floorplanner to guarantee that each macrocell’s arrangement will follow the placement constraints. Therefore, each particle can move according to the original PSO algorithm, but any moving vector that violates the setting rules (placement constraints) will be stopped by the constraints handling process; the movement of particles could be limited to one or both directions and the moving vectors could be reduced in each move to comply with the placement constraints.

Here, the two general kinds of placement constraints, absolute and relative, are taken into consideration. For relative placement constraint, users can restrict the horizontal or vertical distance between two modules to a certain value, or to a certain range of values.

In this paper, a master-slave concept is introduced to define the relationship between cells. For a set constrained macrocells, one of them will be defined as master; the others will be slaves. All the slave cells will be moved only after the master cell has moved. Furthermore, the movement strategy of slave cells will also obey the cell’s relationship defined by the constraints. For example, if cell A and cell B are both constrained to vertical alignment, and cell A is defined as the master cell, then cell B will be moved only after cell A has moved, and the x-axis of cell B will be set according to cell A’s current position. Absolute placement constraint is similarly specified except it does not involve or need the master-slave concept.

4.2. Overlap Detection and Removal Mechanism

Before the global best position Gbest is updated to move the macrocell to a new position, the proposed floorplanner should detect if the current macrocell overlaps with any existing macrocells. The horizontal distance d_h and vertical distance d_v between two macrocells depicted in Figure 8 are measured via the macrocells’ center. Then, they are compared with the half sum of two the macrocells’ height s_h and half sum of the two macrocells’ width s_w to estimate the occurrence of overlap using

()

The area with an existing macrocell will be regarded as a forbidden region. If a macrocell is moved to intersect a forbidden region (overlaps with another macrocell), this macrocell will be eliminated and restored to its former location. The macrocells’ new position will be updated until it is overlap-free. This process requires more time for computation (particle movement), but it will guarantee that each macrocell’s placement is overlap-free.

4.3. Turnaround Factor for Particles’ Movement

In the original PSO, the moving vector (velocity) of each particle is decided according to its past best solution and the global best solution. This procedure makes sense in evolutional computing, where all new generations would inherit past generations’ experience or ability and move all particles toward the global best solution.

In some applications, such as placement, the optimal solution will change in each time slot. The original PSOs will ignore some of the better solutions that are beyond the particles in the searching space, and continue to drive particles toward a specific direction according to previous experiences. Particles will miss the optimal solution in the current slot and spend more time on turning particles in the right direction, and toward to the global optimal solution. Figure 9 shows the particles’ searching behavior, driven by (7) in a two-dimensional search space. It would lead particles to some searching spaces and skip the areas which have already been searched before in previous generations. This searching behavior is more suited to applications whose optimal solution is fixed at a specific position, but not time varying or dynamic. In different applications, the algorithm should be modified to be more suitable under the circumstances.

For example, in order to prevent macrocells from overlapping, all areas with existing macrocells will be regarded as a forbidden region; that is, each rearrangement of a macrocell must be overlap-free. Thus, particles may not be able to find feasible solution by moving forward (according to previous experience) in the current generation. Therefore, to search for better placement solutions, particles should not move only forwards, but also backwards to find possible solutions.

To enhance the particles’ searching ability and save evolution time, the velocity update equation is modified as follows:

()

where T denotes the turnaround factor [15]. Normally, the T would be set at 1 (moving forward). The particle’s movement will follow the original PSO. If the particle can not find a feasible solution however, the T of the regenerated macrocell will be switched to −1 (moving backward) for this generation. After feasible solutions have been found, the particles will then follow in the current direction in its successive generations to find better solutions. Thus, T must be restored to 1. Particles will then continue the solution searching by moving according to the original PSO. Figure 10 illustrates the extended searching space possible with proposed method.

The turnaround factor can extend the particles’ searching space from the usual frontal 180 degrees to a full 360 degrees. It can stop particles from missing the solutions located behind them or located in already explored areas.

4.4. Disturbance Mechanism

In this paper, the PSO placement procedure is incorporated with a disturbance mechanism [16], the mutation-like evolutionary strategy, to prevent particles from being trapped in the local optimum.

Because each macrocell has a unique length-height ratio, after numbers of generations, the gap and free space between each macrocell should become smaller as each cell moves closer together. But it is almost unavoidable for the solution to fall into the local minimum during each particle’s search for a better placement solution.

Hence, a disturbance mechanism was added into the PSO process to prevent the search from falling into the local minimum and to escape from the trap to find the global minimal. The disturbance mechanism will pick up a particle randomly and disturb its position information; a randomly selected macrocell will be reordered in the enclosed rectangle of the floorplan while the disturbance mechanism is active. The placement process was then redone to achieve a better placement solution. Figure 11 shows that the macrocell has been replaced by disturbance mechanism.

The selected macrocell will keep following the PSO iteration and continue to find new placement solutions. The disturbance mechanism will cause a slight rearrangement of the floorplan and prevent the solution from falling into the local minimum.

It takes many tries for the particles to find the best solution for the following generation. After the disturbance mechanism activates, the removed macrocell will create an empty space for other macrocells, so it can also reduce the PSO iteration time and help other macrocells find the next solution. The disturbance mechanism provides two advantages with a single process. The pseudocode of the disturbance mechanism for placement is presented Algorithm 1.

Algorithm 1: Pseudocode of disturbance mechanism for placement.

if disturbance mechanism activated
random select a particle (macrocell) and place it randomly
in the searching space (enclosing rectangle of the
floorplanning)
if overlap
restore the particle’s position
else
update the particle’s position
endif
endif

4.5. Objective Function

In general, the objective functions are dependent on the application’s demands. In this paper, the focus will be smaller chip size and shorter wire length also. Just as chip size gets smaller, the wire length should also be shorter. Therefore, we defined the objective function f as follows:

()

where D_h and D_v are the horizontal distance and the vertical distance with coordinates (0, 0), respectively, and i is produced by a random integer generator with a result of either 1 or 0. The function

can make cells get as close as possible, while the function value gets smaller. The function D_h + D_v + |D_h − D_v| can arrange cells in a uniform distribution. Both cost functions are integral parts and must work alternately in PSO evolution. Adopting the first one only will form a tight cell arrangement but the side effect is a placement that forms an arced contour, on the other hand, adopting the second one only will create results with better contours but will lead to loose cells arrangements.

4.6. PSO for Placement Constraint and Overlap Removal

The dimension numbers N denote the number of macrocells and the particle number is defined as 1 ≤ i ≤ s. The macrocells were randomly placed on the floorplan and overlap was allowed initially. The x_i represents the macrocells’ current positions and the initial state of v_i,j, Pbest_i, and Gbest were set to 0. After that, particles are moved by (11) and (8); vectors violating movement restraints are cut off with the constraints handling process. The overlap detection and removal mechanism will also eliminate any cells that overlap with other macrocells. Then, the new local best position would be updated with (9) and the global best position would be updated with (10). In order to guarantee that each constrained macrocell would not violate placement constraints, all constrained modules are set to have higher priority in each movement during the earlier generations to ensure that all set constraints were reached, in other words, if a nonconstrained module overlaps with a constrained module, this nonconstrained module would be removed and regenerated. Thus, all the particles would keep moving to find a better solution until it reached the goal or met the termination condition. The pseudocode of improved PSO for macrocell overlap removal and placement is presented in Algorithm 2. The dimension of each particle will be 2^*N since there are 2 parameters (x- and y-axes) per cell.

Algorithm 2: Pseudocode.

Create and initiate a 2^*N-dimensional PSO: P
Repeat:
Disturbance mechanism
Execute PSO to update P by (11) and (8)
Constraints handling process
Overlap detection and removal by (12)
for each particle i ∈ [1, …, s]
iff(x_i) < f(Pbest_i)
thenPbest_i = x_i
iff(Pbest_i) < f(Gbest)
thenGbest = Pbest_i
endfor
Until termination condition is reached

4.7. Time Complexity

In this paper, the time complexity of the proposed floorplanner is O(N_d/N_p(n − 1) + d + c), where N_d is the dimensions of particles, N_p the number of particles in the swarm, n is the number of macrocells, (n − 1) is overlap detection and removal (compare one macrocell with others), d is the disturbance mechanism, and c is the constraints handling process. Thus, N_d equals to n. The number of particles is typically less than n, since the number of particles in a swarm has no need to surpass a constant limit, and the activating probability of disturbance mechanism is much smaller than n². Thus, the overall time complexity of the algorithm is O(n²).

5. Experiments

The experiments in this study employed GSRC and MCNC benchmarks [20] for the proposed placement constraints and overlap removal procedures and compared the results with other related researches. All the macrocells were set as hard IP modules and without rotation. The simulation programs were written in Matlab [21], and the results were obtained on Pentium 4 1.7 GHz with 512 MB RAM. The initial parameters of w, c₁, and c₂ for the proposed method and [19] were empirically set as 0.12, 0.25, and 0.25, respectively. Both their particle numbers were set as ten and the termination condition was set at 100 generations. The algorithm and parameters of ACO and B^*-tree were complete following the original setting of [9] and [4], respectively. Each floorplanner was run 25 times for each of the benchmarks and their average outcomes of wire length, chip area, and run time were recorded.

The experimental results of placements are shown in Table 1. Compared with related methods, the proposed method is more efficient in finding solutions with respect to chip area or wire length and can prevent solutions fall into the local minimum. The convergence of [19] is quite acceptable. Good solutions can be found after reasonable computation time. The ACO method allows overlap in the initial stage; this means it not only has to execute the ACO procedure, detect and remove overlaps, but must also deal with constraint graphs for each macrocell. However, the ACO method shows impressive results for the floorplan. In the B^*-tree structure, all macrocells are overlap-free, saving detection time to find and remove overlapping cells, but it would then spend more time arranging the cells after one cell was removed, exchanged, or placed. In a minority of cases, it displays more efficiency with placement. Once the cell number was increased, however, the computation burden of this method would increase nonlinearly, furthermore, it would likely fall into the local minimum. In unconstrained cases, the proposed method expressed more optimal results for wire length and chip area, and shorter run times than ACO [9], PSO [19], and B^*-tree [4].

Table 1. Compared proposed method with other approaches without placement constraints.

		Proposed method			PSO [19]			100 Colony 200 Ants			B^*-tree [4]
Circuits	Cells							Ant Colony [9]
		Area	Wire	Run	Area	Wire	Run	Area	Wire	Run	Area	Wire	Run
		(mm²)	(mm)	time	(mm²)	(mm)	time	(mm²)	(mm)	time	(mm²)	(mm)	time
ami49	49	51.46	179.28	1m52s	58.75	212.75	1m57s	63.32	218.36	7m58s	50.71	208.38	1m49s
n_{_}50	50	0.27	12.8	1m40s	0.39	17.85	1m50s	0.41	18.01	7m12s	0.27	14.97	1m40s
n_{_}100	100	0.24	24.17	3m43s	0.41	35.07	3m51s	0.45	40.36	15m01s	0.27	31.75	11m39s
n_{_}200	200	0.24	47.74	8m48s	0.42	71.93	8m55s	0.46	73.68	45m59s	0.28	84.01	1h36m12s
n_{_}300	300	0.38	89.84	15m43s	0.40	132.91	15m59s	0.57	119.43	1h24m1s	0.49	204.44	5h26m50s

Because there are hundreds of combinations for placement constraints mentioned in Section 2, it was not possible to present every case here. In placement constraints simulation, the constraint types were selected by a random number generator. The constrained macrocells are selected by its serial number. For example, if the user wants to have 8 constrained macrocells in the GSRC n100 benchmark, cells sb0 to sb7 would be chosen. The placement constraint experimental results are shown in Table 2. Even when restricted to different numbers of macrocells during placement, the proposed method exhibited reasonable outcomes for chip size, wire length and run times, and fit all selected constraints. Furthermore, the proposed method has no cases of constraint violations in each experiment. Only little fluctuation in computation times in the proposed method when using different restricted cells can also be observed. The proposed floorplanner is more robust than related research in being more adaptable to various placement requirements. The final five multiconstraint floorplanning results in GSRC n100 were illustrated in Figures 12–16.

Table 2. The proposed method with different placement constraints.

Circuits	Cells	4 macrocells in 2 random			8 macrocells in 4 random			12 macrocells in 4 random
		selected constraints			selected constraints			selected constraints
		Area (mm²)	Wire (mm)	Run time	Area (mm²)	Wire (mm)	Run time	Area (mm²)	Wire (mm)	Run time
ami49	49	50.7	186.29	2m30s	51.91	177.672	2m51s	52.21	186.82	3m2s
n_{_}50	50	0.28	13.47	2m26s	0.29	13.65	3m21s	0.3	13.86	3m56s
n_{_}100	100	0.27	25.91	5m5s	0.27	26.17	5m23s	0.28	26.42	5m50s
n_{_}200	200	0.28	52.11	10m59s	0.28	52.47	11m18s	0.28	52.95	12m25s
n_{_}300	300	0.42	97.12	18m58s	0.43	97.09	20m6s	0.43	97.79	20m35s

6. Conclusions

This paper presents a method to handle various placement constraints in floorplanning. Two techniques are introduced, which are the turnaround factor and the disturbance mechanism, to improve capability of the algorithm. When it was applied to problems without constraints, the proposed method exhibited more efficiency and robustness when searching for the solution than ACO, PSO, and B^*-tree. In order to perform a wide optimal solution search, the overlap between macrocells was allowed in the initial stage, the proposed method can guarantee that all the overlaps will be eliminated in the final floorplan. The experimental results proved that the proposed method can lead to more optimal solutions within reasonable computation times for hard IP modules in unconstrained placement. Furthermore, the propose method also has ability to deal with constrained placement problems. Several benchmarks were adopted for testing and the results were very reliable. Placements with all the constraints satisfied can be obtained efficiently by the proposed method.

7. Future Works

The authors’ future works will focus on finding ways to apply their method to different architecture in order to enhance the efficiency of floorplanning, and deal with soft IP module placement problems.

References

1 Quinn N. and Breuer M. A., A forced directed component placement procedure for printed circuit boards, IEEE Transactions on Circuits and Systems. (1979) 26, no. 6, 377–388, https://doi.org/10.1109/TCS.1979.1084652.
10.1109/TCS.1979.1084652
Google Scholar
2 Murata H., Fujiyoshi K., Nakatake S., and Kajitani Y., VLSI module placement based on rectangle-packing by the sequence-pair, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. (1996) 15, no. 12, 1518–1524, https://doi.org/10.1109/43.552084.
10.1109/43.552084
Web of Science® Google Scholar
3 Guo P.-N., [email protected], Takahashi T., [email protected], Cheng C.-K., and [email protected], Yoshimura T., [email protected], Floorplanning using a tree representation, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. (2001) 20, no. 2, 281–289, https://doi.org/10.1109/43.908471.
10.1109/43.908471
Web of Science® Google Scholar
4 Chang Y. C., Chang Y. W., Wu G. M., and Wu S. W., B^∗-trees: a new representation for nonslicing floorplans, Proceedings of the 37th on Design Automation Conference (DAC ′00), June 2000, Los Angeles, Calif, USA, 458–463.
Google Scholar
5 Sigl G., Doll K., and Johannes F. M., Analytical placement: a linear or a quadratic objective function?, Proceedings of the 28th Design Automation Conference (DAC ′91), June 1991, San Francisco, Calif, USA, 427–432.
Google Scholar
6 Mo F., Tabbara A., and Brayton R. K., A force-directed macro-cell placer, Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD ′00), November 2000, San Jose, Calif, USA, 177–180, https://doi.org/10.1109/ICCAD.2000.896470.
10.1109/ICCAD.2000.896470
Google Scholar
7 Vijayan J. and Tsay R.-S., A new method for floor planning using topological constraint reduction, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. (1991) 10, no. 12, 1494–1501, https://doi.org/10.1109/43.103499.
10.1109/43.103499
Web of Science® Google Scholar
8 Asato B. and Ali H. H., An improved floor planning algorithm using topological constraint reduction, Proceedings of the IEEE 38th Midwest Symposium on Circuits and Systems (MWSCAS ′95), August 1995, Rio de Janeiro, Brazil, 310–313, https://doi.org/10.1109/MWSCAS.1995.504439.
10.1109/MWSCAS.1995.504439
Google Scholar
9 Alupoaei S. and Katkoori S., [email protected], Ant colony system application to macrocell overlap removal, IEEE Transactions on Very Large Scale Integration (VLSI) Systems. (2004) 12, no. 10, 1118–1123, https://doi.org/10.1109/TVLSI.2004.832926.
10.1109/TVLSI.2004.832926
Web of Science® Google Scholar
10 Balasa F. and Lampaert K., Symmetry within the sequence-pair representation in the context of placement for analog design, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. (2000) 19, no. 7, 721–731, https://doi.org/10.1109/43.851988.
10.1109/43.851988
Web of Science® Google Scholar
11 Balasa F., Maruvada S. C., and Krishnamoorthy K., Efficient solution space exploration based on segment trees in analog placement with symmetry constraints, Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD ′00), November 2002, San Jose, Calif, USA, 497–502, https://doi.org/10.1109/ICCAD.2002.1167578.
10.1109/ICCAD.2002.1167578
Google Scholar
12 Tang X. and Wong D. F., Floorplanning with alignment and performance constraints, Proceedings of the 39th Design Automation Conference (DAC ′02), June 2002, New Orleans, La, USA, 848–853, https://doi.org/10.1109/DAC.2002.1012740.
10.1109/DAC.2002.1012740
Google Scholar
13 Murata H., Fujiyoshi K., and Kaneko M., VLSI/PCB placement with obstacles based on sequence-pair, Proceedings of the International Symposium on Physical Design (ISPD ′97), April 1997, Napa, Calif, USA, 26–31.
Google Scholar
14 Young F. Y. and Wong D. F., Slicing floorplans with pre-placed modules, Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD ′98), November 1998, San Jose, Calif, USA, 252–258.
Google Scholar
15 Lin C.-L., Hsieh S.-T., Sun T.-Y., and Liu C.-C., PSO-based learning rate adjustment for blind source separation, Proceedings of International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS ′05), December 2005, Hong Kong, 181–184, https://doi.org/10.1109/ISPACS.2005.1595376.
10.1109/ISPACS.2005.1595376
Google Scholar
16 Sun T.-Y., Hsieh S.-T., and Lin C.-W., Particle swarm optimization incorporated with disturbance for improving the efficiency of macrocell overlap removal and placement, Proceedings of the International Conference on Artificial Intelligence (ICAI ′05), June 2005, Las Vegas, Nev, USA, 122–125.
Google Scholar
17 Eberhart R. and Kennedy J., A new optimizer using particle swarm theory, Proceedings of 6th International Symposium on Micro Machine and Human Science, October 1995, Nagoya, Japan, 39–43.
Google Scholar
18 Gudise V. G. and Venayagamoorthy G. K., Comparison of particle swarm optimization and backpropagation as training algorithms for neural networks, Proceedings of the IEEE Swarm Intelligence Symposium (SIS ′03), April 2003, Indianapolis, Ind, USA, 110–117, https://doi.org/10.1109/SIS.2003.1202255.
10.1109/SIS.2003.1202255
Google Scholar
19 Shi Y. and Eberhart R., A modified particle swarm optimizer, Proceedings of IEEE World Congress on Computational Intelligence, May 1998, Anchorage, Alaska, USA, 69–73, https://doi.org/10.1109/ICEC.1998.699146.
10.1109/ICEC.1998.699146
Google Scholar
20 http://vlsicad.cs.binghamton.edu/benchmarks.html.
Google Scholar
21 http://www.mathworks.com/.
Google Scholar

Citing Literature

All articles

An Improved Particle Swarm Optimizer for Placement Constraints

Abstract

1. Introduction