Multi-culture diversity based self adaptive particle swarm optimization for optimal floorplanning

Abstract

Floorplanning is the central part of the physical design of “Very Large Scale Integrated (VLSI)” circuit design. It decides the core performance characteristics of the fabricated chip. It is possible to model the floorplanning issue as a multi-objective problem, where a number of objectives satisfied simultaneously. Based on the complexity point of view, it is an NP-hard problem, which means getting an optimal solution is a challenging task. In order to resolve this problem, in this paper, an adversity-based multi-cultureself-adaptive form of Particle Swarm Optimization (PSO) has proposed. Multi-objective optimization approach has applied to minimize the layout area required to place all modules and their total interconnection wire length. The proposed solution has multicultural integration, which provides the ability to explore the solution space faster and efficiently. Diversity-based self-adaptation of parameters provides the optimum balance among the exploration as well as exploitation. Finally, the experimental results showed the advantages in comparison to other variations of PSO in delivering the compact and robust performances.

Keywords

VLSI floorplanning non-overlapping constraints particle swarm optimization adaptiveness chip area interconnection wire length

1. Introduction

Among various stages of chip design, physical design is one of the most critical and challenging areas. Performances obtained in physical design are having a direct effect on final chip performances. In this regard, automation for the physical design of integrated circuits remains an active area of research in terms of the development of efficient algorithms. The technological development in fabrication ability makes possible to integrate more and more devices on our silicon chips forced the automation algorithms to scale up continuously. This number will keep increasing for the future technology generations. Hence, there is a demand to place a number of transistors automatically on a chip which has to occupy a minimum area along with a minimum length of connected wires. There is a rapid improvement has observed in the electronic industry and technology, and efficient chip design has been one of the most attention areas of research. Moreover, the improvement in various dimensions of VLSI design has given possibilities to develop the chip with high composite, reliable, miniature, as well as higher performance. The complexity of design keeps increasing because of an innumerable number of transistors on one chip.

VLSI floorplanning is important in chip design and has obtained a special attention by researchers. In simple word, the process of the floorplanning can be considered as the structure identification that should be placed close together and allocating space with satisfying the several constraints with desires to keep the things closer. On the basis of the area of the hierarchy and the design, an appropriate floorplan is decided upon. The Floorplanning process obtains care of various types of the modules like the macros exploited in the memory, design, other IP cores and their placement requirements, the available potential routing as well as involved area of the complete design. Apart from that structure of IO, the aspect ratio of the design is also considered in floorplanning process. If the quality of the floorplan is bad, there is wastage of die area and congestion in the routing. In a number of design methodologies, performance parameters Speed and Area are prime important things, which could be considered for traded off against each other because of inadequate routing resources, as well as the more routing resources cause, the slower the design. Minimizing the area gives freedom to the design to employ lesser resources, as well as to ensure the sections of the design will close. This generates the shorter length of interconnect, less number of required routing resources, high-speed end-to-end signal paths, along with faster and more consistent place and route times.

The prime aim of floorplanning is to optimize the cost function (such as floorplan area, total interconnection wire lengths, etc.) to reduce the chip cost, occupied area by chip and performance improvement. Floorplanning is a significant phase in VLSI design, and its complexity comes as an NP-hard combinatorial optimization problem where the domain of the solution space gets an exponential increase of circuits scale, and therefore it is not easy to achieve the best solution. Hence, heuristic methods can be the better solution approach to exploring the global solution space. Rectangular dissection usually represents a floorplan. The border of a floorplan is usually a rectangle since this is the most convenient shape for chip fabrication. The rectangle is dissected with several straight lines which mark the borders of the modules. The lines are usually restricted to horizontal and vertical lines only often; modules are restricted to rectangles to facilitate automation. The restriction on the module organization of a floorplan is an important issue. Although in the most general case, the modules can have an arbitrary organization, imposing some restriction on the floorplans may have advantages. In general, there are two forms of Floorplan: (i) slicing floorplan, where floorplan can be bipartitioned into two sliceable floorplans with a horizontal or vertical cut line, (ii) non-slicing floorplan, where, defined modules in the layout cannot be attained by any bisection, either horizontally or vertically.

Usually, total defined Area for floorplan is larger through slicing floorplan representation in comparison to the non-slicing floorplan. Also, depending upon the fixed aspect ratio or the variable aspect ratio, nature of modules can be hard and soft. Hence, there is more concentration in the designing of floorplan with the non-slice approach. There are a number of different approaches have applied previously in the representation of non-slicing floorplans like sequence-based approach, transitive closure graph, corner list approach, as well as tree-based approach, etc. Because of NP-hard complexity involved with floorplanning, application of stochastic algorithms in the designing the better floorplan is an active area of research for EDA community. Simulated annealing (SA) technique applied previously and had been explored very well. Performances of SA algorithm are appreciable with lesser number of modules, but demand computational resources with increasing the number of modules. Another variety of stochastic methods which is a population-based heuristic has become the area of interest by researchers.

Figure 1.

Diagrammatic representation of taxonomy.

Broadly, two categories: evolutionary computation and swarm intelligence have shown the great possibilities among them like genetic algorithm, differential evolution, memetic algorithm, PSO, ABC, etc. are a major contributor. Previous research over these algorithms has a limitation in exploration and exploitation capability so that an optimal solution could achieve. Previous research in the design of VLSI floorplanning algorithms has given less attention in this direction.

Generally, floorplanning design is an overview of the traditional placement problem in that all modules are rectangular rigid modules. Conventional optimization methods are no longer effectual for this overall issue. A floorplan design method ought to be able to take benefit of the freedom of choosing a representative with many options for each flexible module. Hence, to overcome these issues a PSO variant optimization method known as MSAPSO method is proposed.

The main intend of this paper is to propose a novel PSO variant referred as MSAPSO method to solve the problem of floorplanning in VLSI. The proposed method has the multicultural integration that provides the ability to explore the solution space faster and efficiently when compared to the conventional methods.

2. Literature review

Performance parameters and constraints involved in the chip design like chip size, electrical characteristics, timing constraints, etc. are prime important where Floorplanning is considered as a central design flow to optimize the objectives. Research over the chip design is a very active area, and many floorplan tools have been proposed. In many cases, outcomes of floorplan are subjective in terms of “who has defined it” and initial condition environment. Figure 1 demonstrates the taxonomy classification. Here, it classified into general and meta-heuristic approaches.

Figure 2.

Flowchart of PSO.

2.1 General approaches

A floorplanning approach based on Wong-Liu floorplanning algorithm has been proposed [3] and considering the interconnect planning with floorplanning simultaneously. Moving block sequence (MBS) based representation of floorplan has discussed [8] for nonslicing floorplan. The MBS does not apply the extra constraints over the solution space, hence suitable for evolutionary algorithms; hence, an organizational evolutionary algorithm is designed with the intrinsic properties of MBS. A neural network based on Kohonen self-organizing map has applied [9] to the floorplanning where the transformation of the abstract specification of the design has given a set of suitable input vectors, which fed to the network at arbitrary. Parallel computing environment approach has been proposed [13] to maximize the throughput of solution space search. The multiobjective approach has applied [14] for layout area as well as interconnection wirelength of chips by means of PSO. Various important design issues and interconnection structure for 3D design in VLSI has proposed [17], 2.5-D layout solution has proposed [18] for floorplanning to reduce the length of interconnection. With the help of initial placement deliver by Xilinx vendor placer, a solution has proposed [24] for floorplanning. Floorplanning for 3D Ics has proposed [28] in which Through-silicon vias (TSVs) has applied to optimize the delay because of wires and TSVs.

Table 1
Non-overlapping constraint definition

Relative location in non-overlapping	Constraint definition
When $m_{i}$ is left side of $m_{j}$	$xi+wi\leqslant xj$
When $m_{i}$ is right side of $m_{j}$	$xi-wj\geqslant xj$
When $m_{i}$ is below to $m_{j}$	$yi+hi\leqslant yj$
When $m_{i}$ is above to $m_{j}$	$yi-hj\geqslant yj$

Figure 3.

MSAPSO flow diagram.

2.2 Metaheuristic approaches

In [1], authors have proposed an idea to define a better initial point for floorplanning with the use of Genetic Algorithms. An encoding scheme based on normalized postfix for a genetic algorithm (GA) has proposed [2] to solve floorplanning problem. The idea of target distance, which was developed by Etawil and Vannelli has been extended [4] in order to obtain the AR (Attractor-Repeller) model. In [5], a tabu search based circuit bi-partitioning approach has presented, which partitions circuits with the aim of decreasing the size of the cutset between the partitions. Subsequently, they have used tabu search approaches beside with the force directed placement approaches so as to achieve the physical placement of VLSI circuits on regular two-dimensional arrays with the aim of decreasing the placement time. Cell placement problem has been considered [6] through Guided Local Search (GLS) metaheuristic approach where the objective has considered to minimize total bounding box net length. A theoretical upper bound for slicing floorplans has presented [7] with soft modules. Using O-tree representation, the concept of genetic algorithm has applied to the VLSI floorplanning problem [10]. In [11], a nonlinear optimization based two-stage approach has applied, where a two-stage nonlinear-optimization-based methodology have proposed, which is specially designed in order to minimize the wire length when concurrently enforce an aspect ratio constraints on soft modules as well as it handles a zero dead space situation. The ant colony optimization based solution has proposed [12] to minimize the area under floorplanning

Table 2
A solution representation in population for PSO

Module	${m}_{1}$	${m}_{2}$	${m}_{n}$
Left	X1	X2	…	Xn
Corner	Y1	Y2		Yn
Position

Figure 4.

Third order IIR filter.

which includes the clustering constraints. Three-dimensional integration based floorplanning has proposed [15] and handles the complexity of larger solution space because of multiple devices. 3D floorplanning with both 2D blocks and 3D blocks has considered. PSO and GA based a hybrid approach has in applied [16] to obtain the feasible floorplan. Hybridization has applied in hopes of not to trap in local minima and the increment in level of diversity. Memetic algorithm based concept has applied [19] to handle the modular assignment problem. B* tree based floorplanning algorithm has proposed [20]. Conic optimization models for facility layout and VLSI floorplanning problems have presented [21]. Conic Optimization concept has applied to solve the single row facility layout and fixed-outline-floorplanning like [22], fixed boundary floorplanning has achieved through a step size optimization for conjugate gradient minimization. Simulated annealing based concept has applied [23] to reduce the unused area considering the objectives as minimizing area and wire length. In the hope of betterment, two stages based

Table 3

Modules dimensions’ definition along with their connectivity

Module	Length (unit length)	Width (unit length)	Wire connection
B ${}_{1}(+)$	150	100	B ${}_{2}$ , B ${}_{3}$
B ${}_{2}(+)$	200	100	$\times$
B ${}_{3}({\rm D})$	150	50	B ${}_{5}$ , B ${}_{6}$ , B ${}_{8}$
B ${}_{4}(+)$	150	100	B ${}_{1}$
B ${}_{5}(\times)$	200	150	B ${}_{4}$
B ${}_{6}(\times)$	150	150	B ${}_{7}$
B ${}_{7}(+)$	150	100	B ${}_{2}$
B ${}_{8}({\rm D})$	150	50	B ${}_{10}$ , B ${}_{11}$ , B ${}_{13}$
B ${}_{9}(+)$	200	100	B ${}_{4}$
B ${}_{10}(\times)$	200	150	B ${}_{9}$
B ${}_{11}(\times)$	200	150	B ${}_{12}$
B ${}_{12}(+)$	150	100	B ${}_{7}$
B ${}_{13}({\rm D})$	150	50	B ${}_{14}$ , B ${}_{15}$
B ${}_{14}(\times)$	50	150	B ${}_{9}$
B ${}_{15}(\times)$	50	100	B ${}_{2}$ , B ${}_{3}$

Table 4

Performances by different algorithms over IIR filter with population size 20

Trial No.	AWPSO		SAPSO		MSAPSO
	Area	Wire length	Area	Wire length	Area	Wire length
1	78.1900	74.2808*	75.0510	80.5625	63.8732	85.7328
2	80.9560	69.2232*	83.2766	89.3912	56.1783	70.1211
3	64.6390	82.5450	65.9086	80.7263	59.3296	78.5366
4	73.7709	78.2997	61.0657	80.4955	57.6255	64.2705
5	72.1594	82.5072*	66.9589	88.5911*	50.1306	78.2362
6	57.9551	84.8474*	83.4090	103.0203	56.2933	74.1722
7	70.7682	82.5460	74.2509	84.7589	58.0616	67.1821
8	59.0893	83.4225*	61.0809	68.7791	59.0862	69.7000
9	56.4329	88.6992	59.9600	71.5653	55.5702	65.1622
10	72.0453	69.7361*	71.5510	85.5861	62.8057	67.7865
Best Sol	56.4329	88.6992	61.0809	68.7791	55.5702	65.1622
Worst Sol.	73.7709	78.2997	83.4090	103.0203	63.8732	85.7328

Table 5

Statistical performances by algorithms over IIR filter for floorplanned area with population size 20

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean area	68.6006	70.2513	57.8954
Std. Dev.	8.6160	8.7406	3.8677
CI: % 95	63.2604 73.9408	64.8338 75.6688	55.4982 60.2927
CI: % 99	61.5820 75.6192	63.1311 77.3714	54.7448 61.0461

Table 6

Statistical performances by algorithms over IIR filter for floorplanned wire length with population size 20

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean wire length	79.6107	83.3476	72.0900
Std. Dev.	6.5465	9.6140	6.9212
CI: % 95	75.5532 83.6682	77.3888 89.3065	67.8002 76.3798
CI: % 99	74.2780 84.9435	75.5160 91.1792	66.4520 77.7281

solution has been proposed [25]. The first stage carries the cut tree development using a Genetic algorithm and then in second stage convolution has given by the collective adoption of achieved cut tree in the first stage. A hybrid heuristic, based on PSO and GA has been proposed [26] for are duction in area and wirelength under floorplan along with hotspot by distributing the temperature

Table 7

Performance by different algorithm over IIR filter with population size 50

Trial No.	AWPSO		SAPSO		MSAPSO
	Area	Wire length	Area	Wire length	Area	Wire length
1	50.5061	59.9495	64.8718	68.4156	49.9777	67.3009
2	57.7076	62.9554	59.2890	80.3427	53.7672	67.0603
3	61.6688	79.1830	68.6004	81.5842	49.7951	70.7515
4	58.6187	58.8299	77.2647	97.7719	48.5282	82.3895
5	57.6369	91.7388	60.9228	83.6339	51.4713	62.1647
6	60.3494	75.0981	65.4777	75.5233	51.4705	56.3741
7	65.1925	63.7382	64.3336	68.8622	58.2613	69.8281
8	68.0767	74.0219	62.5770	61.3477	45.0654	56.9618
9	60.0118	66.2101	49.5180	80.6585	53.9523	59.6254
10	57.9511	75.9076	65.2273	80.6640	49.1643	65.3892
Best Sol	50.5061	59.9495	49.5180	80.6585	45.0654	56.9618
Worst Sol.	68.0767	74.0219	68.6004	81.5842	58.2613	69.8281

Table 8

Statistical performances by algorithms over IIR filter for floorplanned area with population size 50

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean area	59.7720	63.8082	51.1453
Std. Dev.	4.7336	7.0295	3.5983
CI: % 95	56.8381 62.7059	59.4513 68.1652	48.9151 53.3756
CI: % 99	64.3715 77.1550	58.0820 69.5345	48.2142 54.0765

Table 9

Statistical performances by algorithms over IIR filter for floorplanned wire length with population size 50

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean wire length	70.7633	77.8804	65.7845
Std. Dev.	10.3125	10.0765	7.7335
CI: % 95	55.9160 63.6280	71.6349 84.1259	60.9913 70.5778
CI: % 99	62.3627 79.1638	69.6721 86.0887	59.4848 72.0843

Table 10

Performance by different algorithms over IIR filter with population size 100

Trial No.	AWPSO		SAPSO		MSAPSO
	Area	Wire length	Area	Wire length	Area	Wire length
1	45.8323	64.1937	60.9136	76.2358	48.2581	57.2170
2	62.0098	71.2037	62.0029	79.4830	42.3243	56.4045
3	60.0022	78.0883	60.2289	74.2653	42.9494	58.2103
4	45.8404	61.4721	56.2346	63.0170	46.2126	59.1588
5	49.4831	73.2310	54.2013	77.7769	42.1076	61.2418
6	47.2209	55.4989	69.6760	75.5646	51.1347	53.6202
7	51.5899	59.2527	62.2221	83.2012	47.1431	57.2369
8	61.6449	70.4185	64.5178	73.1193	51.3756	61.1167
9	54.1422	82.6664	59.1744	69.1193	45.0931	59.1923
10	59.5511	85.4674	60.7559	76.4001	50.8812	65.0766
Best Sol	47.2209	55.4989	56.2346	63.0170	42.3243	56.4045
Worst Sol.	59.5511	85.4674	69.6760	75.5646	51.3756	61.1167

uniformly over the chip. The initialfloorplanwas achieved through B*-tree, and later a PSO-GA has applied to optimize the placement. A variation of VLSI floorplanning problem called designing test cite chips, where the placement of the rectangular macros takes place without overlap and contains no wire among macros, has discussed [27].

Figure 5.

Floorplan for IIR filter using MSAPSO with population size equal to 20.

Figure 6.

Floorplan for IIR filter using SAPSO with population size equal to 20.

Table 11

Statistical performances by algorithms over IIR filter for floorplanned area with population size 100

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean area	53.7317	60.9927	46.7480
Std. Dev.	6.6182	4.2567	3.6322
CI: % 95	[49.6297 57.8337]	[58.3544 63.6311]	[44.4967 48.9992]
CI: % 99	[48.3405 59.1229]	[57.5252 64.4602]	[43.7892 49.7067]

Figure 7.

Floorplan for IIR filter using MSAPSO with population size equal to 50.

Figure 8.

Floorplan for IIR filter using SAPSO with population size equal to 50.

Table 12

Statistical performances by algorithms over IIR filter for floorplanned wire length with population size 100

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean wire length	70.1493	74.8183	58.8475
Std. Dev.	10.0508	5.5856	3.1420
CI: % 95	[63.9197 76.3788]	[71.3562 78.2803]	[56.9001 60.7950]
CI: % 99	[61.9619 78.3367]	[70.2682 79.3683]	[56.2880 61.4070]

Figure 9.

Floorplan for IIR filter using AWPSO with population size equal to 50.

Figure 10.

Comparative area convergence performance in IIR filter with population size 50.

3. Problem statements

Let us assume that there is total “ $N$ ” number of modules, $M=$ { $m_{1},m_{2},\ldots,m_{N}$ } define the membership in the floorplan. Each module $m_{i}$ is characterized by their width and height, 1 $\leqslant I\leqslant N$ . The main objective of the floorplanning is to provide the position for the all these modules in such a manner that there is no overlap and minimize the cost metric which is a function of floorplan area and total interconnection wirelength. A weighted sum approach applied to integrate the various objectives (with different units) to deliver the outcome as a scalar quantity.

Table 13
Dimensions of each module with their forward path wire connection

Module	Length (unit length)	Width (unit length)	Wire connection
A ${}_{1}(+)$	150	100	M ${}_{1}$
M ${}_{1}({\rm x})$	200	150	A ${}_{2}$
A ${}_{2}(+)$	150	100	A ${}_{3}$ , A ${}_{4}$
A ${}_{3}(+)$	150	100	M ${}_{2}$
M ${}_{2}({\rm x})$	200	150	A ${}_{6}$ , A ${}_{4}$
A ${}_{4}(+)$	150	100	D ${}_{2}$ , M ${}_{5}$
A ${}_{5}(+)$	150	100	M ${}_{3}$
A ${}_{6}(+)$	150	100	D ${}_{1}$ , M ${}_{4}$
M ${}_{3}({\rm x})$	200	150	A ${}_{7}$
M ${}_{4}({\rm x})$	200	150	A ${}_{7}$
M ${}_{5}({\rm x})$	200	150	A ${}_{8}$
A ${}_{7}(+)$	150	100	A ${}_{8}$
A ${}_{8}(+)$	150	100	$\times$
D ${}_{1}$	50	50	A ${}_{1}$ , A ${}_{5}$
D ${}_{2}$	50	50	A ${}_{6}$ , A ${}_{3}$

Figure 11.

Comparative wire length convergence performance in IIR filter with population size 50.

3.1 Non-overlapping constraint

It is a very important constraint in the floorplanning and required an absolute zero violation to make the floorplan feasible. Any two modules $m_{i}$ as well as $m_{j}$ are considered as nonoverlap, if at least one of the following

Table 14
Performance by algorithms over Lattice filter with population size 20

Trial No.	AWPSO		SAPSO		MSAPSO
	Area	Wire length	Area	Wire length	Area	Wire length
1	63.4004	87.1385*	59.3433	79.7497	59.6035	83.0240
2	72.0082	93.6431	66.1713	85.0653*	55.6992	65.4310
3	75.4073	101.5417*	69.5143	92.9372*	56.1583	68.1808
4	69.7891	92.8159*	81.3876	108.2928*	56.5108	72.2854
5	54.4638	82.8825	81.4570	114.7479	58.7022	76.6257
6	63.5733	105.1818	68.0021	83.5659	52.7918	75.2547
7	58.9404	88.7154	72.2170	83.4497	62.0839	71.3641
8	70.2662	74.8979	79.0388	75.1491	56.8351	79.4229
9	66.7124	81.6585*	54.7573	74.9689	57.2991	75.7348
10	65.8552	87.8438*	76.7473	102.2909	60.2941	71.5880
Best Sol	54.4638	82.8825	54.7573	74.9689	55.6992	65.4310
Worst Sol.	72.0082	93.6431	81.4570	114.7479	59.6035	83.0240

Table 15

Statistical performances by algorithms over Lattice filter for floorplanned area with population size 20

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean area	66.0416	70.8636	57.5978
Std. Dev.	6.2648	9.1313	2.6513
CI: % 95	62.1587 69.9246	65.2040 76.5232	55.9545 59.2411
CI: % 99	60.9383 71.1450	63.4253 78.3019	55.4380 59.7576

Table 16

Statistical performances by algorithms over Lattice filter for floorplanned wire length with population size 20

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean wire length	89.6319	90.0217	73.8911
Std. Dev.	9.1064	14.0118	5.2196
CI: % 95	83.9877 95.2761	81.3371 98.7064	70.6560 77.1263
CI: % 99	82.2138 97.0500	78.6077 101.4358	69.6393 78.1430

Table 17

Performance by different algorithm over Lattice filter with population size 50

Trial No.	AWPSO		SAPSO		MSAPSO
	Area	Wire length	Area	Wire length	Area	Wire length
1	60.5103	78.7427	59.9249	81.0934	48.1395	61.3613
2	59.0688	72.2639	59.9681	93.7555	45.3329	69.6878
3	56.7391	78.1908	71.2921	79.7812	51.1213	55.7424
4	50.2386	76.0747	69.2499	76.1859*	43.8446	70.2485
5	53.1862	72.3884	57.4645	84.4618	51.9747	75.2217
6	63.2028	73.1279	68.0698	73.2763	54.3758	66.7888
7	64.3282	88.3564	53.9536	71.8922	52.6538	67.1996
8	50.6154	65.0640	50.9643	86.5416	54.0721	80.8200
9	52.5349	62.9183	62.3356	87.0982	58.7481	74.9351
10	54.7932	75.8643*	64.9604	88.0334	48.6573	78.5649
Best Sol	50.6154	65.0640	50.9643	86.5416	43.8446	70.2485
Worst Sol.	64.3282	88.3564	64.9604	88.0334	58.7481	74.9351

Table 18

Statistical performances by algorithms over Lattice filter for floorplanned area with population size 50

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean area	56.5217	61.8183	50.8920
Std. Dev.	5.0815	6.6652	4.4900
CI: % 95	53.3722 59.6713	57.6872 65.9495	48.1091 53.6749
CI: % 99	52.3824 60.6611	56.3888 67.2478	47.2345 54.5495

Figure 12.

Floorplan for IIR filter using MSAPSO with population size equal to 100.

Figure 13.

Diversity and corresponding inertia weight in MSAPSO with population size equal to 100.

constraints satisfied in terms of their position in rectilinear coordinate as given in Table 1, where positions are represented in x and $y$ -axis

Table 19

Statistical performances by different algorithms over Lattice filter for floorplanned wire length with population size 50

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean wire length	74.2991	82.2119	70.0570
Std. Dev.	7.1653	7.0289	7.7333
CI: % 95	69.8580 78.7402	77.8554 86.5685	65.2638 74.8502
CI: % 99	68.4622 80.1360	76.4862 87.9377	63.7574 76.3566

Figure 14.

Floorplan for IIR filter using SAPSO with population size equal to 100.

Figure 15.

Diversity and corresponding inertia weight in SAPSO with population size equal to 100.

direction, $w_{i}$ is the width of ‘ $i^{\rm th}$ ’ module in $x$ -axis direction while ‘ $h_{i}$ ’ is the height of ‘ $i^{\rm th}$ ’ module in $y$ -axis direction.

Table 20

Performance by algorithms over Lattice filter with population size 100

Trial No.	AWPSO		SAPSO		MSAPSO
	Area	Wire length	Area	Wire length	Area	Wire length
1	64.0138	72.6111*	59.5916	78.2544	46.9636	64.5304
2	49.2818	68.3875	59.8266	72.7216	50.2898	60.2993
3	56.4982	79.1531	60.2447	72.5018	45.5462	69.4123
4	43.5629	61.4049	52.8135	82.6729	50.4258	64.2413
5	62.1890	54.8458	63.1119	70.6166	48.5208	72.9954
6	50.0528	69.5377	55.8910	73.1162	42.7720	60.4474
7	47.7361	62.5969	67.0314	79.7602	48.2664	63.5368
8	51.1127	67.1647	58.7980	82.3933	44.8267	59.3916
9	46.8699	65.1343	59.7658	78.3054	41.2620	64.8118
10	52.2285	76.6673	59.0010	85.9569	46.1646	56.8727
Best Sol	43.5629	61.4049	55.8910	73.1162	42.7720	60.4474
Worst Sol.	56.4982	79.1531	67.0314	79.7602	48.5208	72.9954

Table 21

Statistical performances by algorithms over Lattice filter for floorplanned area with population size 100

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean area	52.3546	59.6075	46.5038
Std. Dev.	6.6234	3.7840	3.0249
CI: % 95	48.2493 56.4598	57.2622 61.9529	44.6289 48.3786
CI: % 99	46.9591 57.7500	56.5251 62.6900	44.0397 48.9679

Figure 16.

Floorplan for IIR filter using AWPSO with population size equal to 100.

3.2 Wire length and area estimation

From automation point of view estimation of wire length among two connecting modules is computed by calculating Euclidean distance among their centers. Total wire lengths

Table 22
Statistical performances by algorithms over Lattice filter for floorplanned wire length with population size 100

Performance parameters	AWPSO	SAPSO	MSAPSO
Mean wire length	67.7503	77.6299	63.6539
Std. Dev.	7.2824	5.1939	4.8141
CI: % 95	63.2367 72.2640	74.4107 80.8492	60.6701 66.6377
CI: % 99	61.8181 73.6826	73.3989 81.8609	59.7323 67.5755

Figure 17.

Diversity and inertia weight in AWPSO with population size equal to 100.

Figure 18.

Comparative area convergence performance in IIR filter with population size 100.

in floorplan are considered as the sum value of wire length required for all individual connections. Mathematically, estimation of wire length between centres of modules is given by Eq. (1).

$\displaystyle\text{Wire length}(F)=\sum\nolimits_{k=1}^{n}\sum\nolimits_{m=1,% \#k}^{n}C_{k,m}d_{k,m}$ (1)

where, $c_{ij}$ is the connectivity among blocks $i$ and $j$ ; $d_{ij}$ is the Manhattan distances among the centers of rectangles of blocks $i$ and $j$ .

Area estimation: Total defined area by the floorplan is estimated as the minimum area of a rectangle, which is closed all the blocks.

Figure 19.

Comparative wire length convergence performance in IIR filter with population size 100.

Figure 20.

Lattice filter.

Figure 21.

Floorplan for Lattice filter using MSAPSO with population size equal to 20.

Figure 22.

Floorplan for Lattice filter using SAPSO with population size equal to 20.

Figure 23.

Floorplan for Lattice filter using AWPSO with population size equal to 20.

3.3 Objective function formulation

Objective function defines the mathematical relationship between objectives of interest and can be represented as cost factor which has to minimize. Until the objective function does not imbed the parameters properly, it is difficult to have an optimal solution at the end. In other words, objective function directs the direction in which the solution has to evolve. In this paper, objectives contain two parameters: area and interconnection wirelength, hence a weighted sum have defined as shown in Eq. (2). The constraint of non-overlapping can be mapped by increasing the cost factor by applying a high-value penalty as according to the number of violations to increase the cost value.

The cost function which encloses the area and wirelength together for a floorplan F is the weighted sum of the area and wirelength as defined in Eq. (2).

$\displaystyle\text{cost}(F)=\alpha\times\text{Area}(F)+(1-\alpha)\times\text{% Wire length}(F)+\textit{PF}\times\textit{Tv},0\leqslant\alpha\leqslant 1$ (2)

$\alpha$ is the weight assigned to the area and ( $1-\alpha$ ) is the weight for wirelength. PF is the penalty factor while Tv is the total number of violations in non-overlapping.

In this paper, floorplanning is considered as a minimization problem, where a parameter which has to minimize is the cost as defined in Eq. (2). Hence, the solution which has a higher value of cost, carry lesser fitness, while the solution has low-cost value, carry higher fitness.

4. Particle swarm optimization (PSO)

The conventional PSO is a heuristic technique, which processes a population of possible solutions to the issue under consideration to explore the search space with social influences. Here, each member of the population has position changing factor in terms of velocity which is a function of memory (remember the best-achieved solution in the past), global best achieved at present and some random perturbation. This mechanism provides facilities for an individual to get something new their status as well as be bound with the population. Mathematical modeling can be represented by defining the three populations. Assuming that there is D number of parameters in the problem, hence the search space is D dimensional. For the i-th member of the population three D-dimensional vectors can be represented by the velocity vector $Vi=[vi1,vi2,\ldots,viD]$ , a position vector say $Xi=[xi1,xi2,\ldots,xiD]$ , and the best previously visited position in terms of memory vector as $Pi=[pi1,pi2,\ldots,piD]$ . Define ‘g’ as the index of the optimal particle in the population that is the g-th particle is the optimal, ‘n’ is the optimal seen by that particular individual.

Figure 24.

Floorplan for Lattice filter using MSAPSO with population size equal to 50.

Figure 25.

Diversity and inertia weight in MSAPSO with population size equal to 50.

Figure 26.

Floorplan for Lattice filter using SAPSO with population size equal to 50.

Figure 27.

Diversity and inertia weight in SAPSO with population size equal to 50.

Figure 28.

Floorplan for Lattice filter using AWPSO with population size equal to 50.

Figure 29.

Diversity and inertia weight in AWPSO with population size equal to 50.

Figure 30.

Comparative area performance in Lattice filter with population size 50.

Figure 31.

Comparative wire length performance in Lattice filter with population size 50.

Figure 32.

Floorplan for Lattice filter using MASPSO with population size equal to 100.

Let the superscripts indicate the iteration number, and subsequently the individual is evolved according to the Eqs (3) and (4).

$\displaystyle V(n+1)id=\chi[w*Vnid+C_{1}r1(Pnid-Xnid)+C_{2}r2(Pngd-Xnid)]$ (3) $\displaystyle X(n+1)id=Xnid+V(n+1)id$ (4)

where, $C_{1}$ represents cognitive parameter and $C_{2}$ represents social parameter, $\chi$ represents constriction factor, ‘ $w$ ’ represents inertia weight. In Eq. (3), the inertia weight $w$ , plays critical role in the convergence behavior of the population. To control the impact of the previous velocities on the current one, the inertia weight is provided. Technically, the parameter ‘ $w$ ’ tries to make the trade-off between the larger jump for global exploration and small change for local exploration abilities. A large inertia weight value presents the chance of exploring the new area in the hope of the global solution while a small one tends to refine the quality of achieved solution by exploring local region. To locate the optimum solution, an appropriate value for the inertia weight ‘ $w$ ’ usually offers a decrease of the number of iterations needed by balancing the global and local exploration. For PSO’s convergence characteristics, the parameters $C_{1}$ and $C_{2}$ are not considered very critical. Nevertheless, the optimal choice can help in faster convergence as well as the alleviation of local minima. The parameters $r$ 1 and $r$ 2 random values and are very important to define and maintain the diversity in the population, and they are selected randomly through uniform distribution in the range of [0, 1].

The performance of PSO is highly dependent upon the value of parameters chosen. However, there is no way potential to calculate the optimal values for these parameters. Therefore, an optimal option is to develop the adaptive environment thus that according to requirement it can opt the suitable value.

4.1 Multi-culture self-adaptive PSO (MSAPSO)

In this paper, a multi-culture concept called “multi-culture self-adaptive particle swarm optimization (MSAPSO)” is applied to evolve the individual population independently and later exploit to form a better community to search the solution space efficiently. This approach is inspired very much by present human society, where at fundamental level two things happen (i) the independent existence of a number of separate population, and they get their progress under the same environment up to a certain period of time. (ii) with respect to objectives, a number of individuals are selected from the different population and form a new population to achieve the objectives. For instance, the recruitment of employees by a company from various places, as well as the selection of the political leader in the democratic country. Similar way rather than working under monoculture formed by one population as in conventional PSO, multiculture environment has proposed, where a number of different environments created by a different set of population independently. Each population has evolved socially independently to generate the multiculture and later among all best individuals is selected to finish the task. This is a dual stage process where first stage finds some potential solution discovered from different regions of solution space, and later in the second phase, each individual contributes more efficiently to find a global solution. In this paper proposed MSAPSO has followed the same concept to solve the problem of floorplanning. With proposed method better quality solution achieved along with the very high value of consistency not only that, require the small size of the population.

Algorithm 1: Pseudo code of PSO
For a define size of population N, Initialization position population $P_{\textit{pop}}$ and velocity population $V_{\textit{pop}}$ through random uniform distribution. Define inertia weight $w$ and global constant $C1$ and cognition constant $C2$ .
1.	Self best population $S_{\textit{pop}}=P_{\textit{pop}}$
2.	Evaluate the fitness of position population. $f_{v}=f({P_{\textit{pop}}})$
3.	$f_{\textit{best}}\leftarrow\max\{{f_{v}}\}$
4.	${\rm G}_{\textit{best}}\leftarrow\textit{member from }P_{\textit{pop}}\textit{% has }f_{\textit{best}}$
5.	While termination does not meet {do
6.	For $i-1$ to $N$
7.	Update new velocity population $V_{\textit{pop}}(i)\leftarrow f(w,V_{\textit{pop}(i)},C1,S_{\textit{pop},}C2,G% _{\textit{best}})$
8.	Update new position $P_{\textit{pop}(i)}\leftarrow P_{\textit{pop}(i)}+V_{\textit{pop}(i)}$
	{Update self best}
9.	If $f({S_{\textit{pop}(i)}})\leqslant f({P_{\textit{pop}(i)}})$
10.	$S_{\textit{pop}(i)}=P_{\textit{pop}(i)}$
11.	End if
	{Update global best}
12.	$G_{\textit{best}}\leftarrow\textit{member has }\max\{f(P_{\textit{pop}})\}{\rm G% }_{\textit{best}}\leftarrow\textit{member has }\{{f({P_{\textit{pop}}})}\}$
13.	End for
14.	End While

Figure 33.

Diversity and inertia weight in MSAPSO with population size equal to 100.

Figure 34.

Floorplan for Lattice filter using SAPSO with population size equal to 100.

Figure 35.

Diversity and inertia weight in SAPSO with population size equal to 100.

Figure 36.

Floorplan for Lattice filter using AWPSO with population size equal to 100.

Figure 37.

Diversity and inertia weight in AWPSO with population size equal to 100.

Figure 38.

Comparative area performance in Lattice filter with population size 100.

The working principle of MSAPSO has shown in Fig. 3. Here ‘POP’s’ are the initial random population, which is evolved by the SADPSO process individually and independently for a fewer number of iterations (say 50) and create the multi-culture new population (NPOP). Even though the process of creating the NPOP is same for all POP, because of difference in leadership and different community surrounding, each NPOP has different characteristics. Through the fitness-based selection process, among all members from all NPOP, better members are selected to form a new population SPOP, which has the same size as POP has. In SPOP, there are a number of good candidates, which do not only have higher fitness but also are different, hence the high level of diversity exists. Finally, over SPOP, SAPSO has applied till terminating criteria does not meet. Hence, the Final Population (FPOP) is attained.

Generally, the memetic algorithms are represented as a population-based meta-heuristics method. An evolutionary framework is composed and a set of local search algorithms that are activated within the generation cycle of the external framework. Hence, the proposed MSAPSO approach is entirely different from the memetic algorithm.

The working principle of MSAPSO is computed on the basis of Eq. (5):

$\displaystyle w_{i}^{({t+1})}=w_{i}^{(t)}+\left[{r_{i}^{({t+1})}\ast({w_{i}^{(% t)}-w_{i}^{({t-1})}})\ast\partial_{i}^{({t+1})}}\right]$ (5)

where, $r_{i}^{({t+1})}$ is independent uniformly distributed random variables at iteration $({t+1})^{\rm th}$ within the range [0, 1] and $\partial_{i}^{({t+1})}$ represents the self-improvement ratio of $({t+1})^{\rm th}$ iteration and is given in Eq. (6),

$\displaystyle\partial_{i}^{({t+1})}=\frac{\textit{fit}({X_{i}^{({t-1})}})-% \textit{fit}({X_{i}^{(t)}})}{\textit{fit}({X_{i}^{({t-1})}})}$ (6)

where, $\textit{fit}({X_{i}^{(t)}})$ and $\textit{fit}({X_{i}^{({t-1})}})$ indicate the fitness function of $i^{\rm th}$ particle in $t^{\rm th}$ and $({t-1})^{\rm th}$ iterations respectively.

Figure 39.

Comparative wire length performance in Lattice filter with population size 100.

4.1.1 Solution representation in MSAPSO

In all natural computing method, representation of solution in the population is very important and can be deciding factor for success or failure of outcomes. In this paper, left corner co-ordinates value of block position is considered to represent the individual block as shown in Table 3. In result, the dimension of the problem is equal to the twice number of modules involved.

Algorithm 2: Pseudo code of MSAPSO
1.	Define the number of different population ( $P$ )
	$C_{\textit{POP}}=$ [];
2.	For $k=1$ to $P$
3.	Initialize a Population and apply SAPSO
4.	Strore the final population ontained from step 3, $N_{\textit{POP}(K)}$ .
	$C_{\textit{POP}}\leftarrow$ [ $C_{\textit{POP}}$ ; $N_{\textit{POP}(K)}$ ]
5.	End For
6.	Evalute the fitness of each member from $C_{\textit{POP}}$ :
	$f_{v}\leftarrow f(C_{\textit{POP}})$
7.	select the best N member from $C_{\textit{POP}}$ to form new population $S_{\textit{POP}}$
8.	Apply SAPSO over $S_{\textit{POP}}$

4.2 Comparison of multi-culture PSO with other variants

The major benefits of the PSO algorithm are simple, robustness to control parameters, easy implementation, as well as computational effectiveness while compared with other heuristic optimization algorithms. However, it suffers from major drawbacks such as in high-dimensional space, easy to fall into local optimum as well as rate in the iterative process, it has a low convergence. Similarly, in AWPSO the premature convergence is the reason of not having optimally adaptiveness in inertia weight, and monoculture environment is the reason for the remarkable difference in the performance with different time execution in independent trials. In the design of the SAPSO algorithm, a number of independent trials must be given to defining the final quality of performances statistically. High level of performance inconsistency imposes a serious limitation on the practical use, and it has become an issue of those problems where time and accuracy are prime important. Increasing the population size can help to solve this problem a very little and also imposes a computational issue. In order to deal with these problems, MSAPSO are exploited. Here, a number of different environments are created by a diverse set of population independently. In subsequent section, the detail description of the AWPSO and SAPSO are presented.

4.2.1 Adaptive weight PSO (AWPSO)

The high value of the inertia weight in the beginning and lower value at a later stage is considered as better strategies to maintain the balance between global and local exploration. Hence a Linear decreasing value for ‘ $w$ ’ (1.2 to 0.1) with time can be taken as means to make inertia weight adaptive as it shown in Eq. (7). Initially, a large value of inertia promotes a larger change, in result global exploration of the search space, and gradually decreases it to get more refined solutions.

$\displaystyle w=M_{xw}-n\ast({M_{xw}-M_{nw}})/({\lfloor{0.75\ast M_{xn}}% \rfloor})$ (7)

where $M_{nw}$ and $M_{xw}$ is minimum and maximum weight value, ‘n’ is iteration number as well as $M_{xn}$ is the maximum number of allowed iterations.

Algorithm 3: Pseudo code of AWPSO

Define minimum and maximum value of inertia weight and the number of iteration n

\begin{cases}\{\text{PSO }\ldots\ldots\\ \text{For }j=1\!\!:n\\ \text{ Change in the inertia weight with each iteration }\\ \quad w\leftarrow M_{xw}-n\frac{(M_{xw}-M_{nw})}{\lfloor 0.75M_{xn}\rfloor}\\ \qquad\text{For }i=1\text{ to }N\\ \{\text{PSO}\ldots\ldots\\ \end{cases}

4.2.2 Diversity based self-adaptive PSO (SAPSO)

Diversity available in the population is very important from an exploration point of view. If there is information available about present diversity in the population, associated parameters involved in exploration can assign more optimal value. In PSO, ‘ $w$ ’ is prime important. Hence there is a need to make the diversity-based self-adaptiveness of ‘ $w$ ’, so that depends upon the state of the population, more appropriate assignment can be given. Literally, for higher diversity, there is need of higher value of $w$ , where as lower diversity, required a lower value for $w$ . Technically, there is a requirement of smooth and limiter characteristics of $w$ value in function of diversity.

On the basis of Eq. (8), a self-adaptive provision has proposed for inertia weight, according to diversity status of solution population.

$\displaystyle w_{f}=1/{({1+1.5\ast e^{-2.5\ast f}})}$ (8)

where $f$ represents current diversity status of the population that can estimate froma mean eucline distance of each solution with others and given by Eq. (9).

$\displaystyle f={({d_{g}-d_{\min}})}/{({d_{\max}-d_{\min}})}$ (9)

where, mean $d_{g}$ represents distance value for the optimal solution.

By Eq. (10), Mean Euclidean distance is calculated

$\displaystyle d_{i}=\frac{1}{N-1}\sum\limits_{j=1,j\neq i}^{N}{\sqrt{\sum% \limits_{k=1}^{D}{({x_{i}^{k}-x_{j}^{k}})^{2}}}}$ (10)

In Eq. (11), the cognitive and social constant also has to change as population moves one state to another.

$\displaystyle C_{i}({n+1})=C_{i}(n)\pm\delta,i=1,2.\;\;\delta\in[0.05\;1]$ (11)

Depends upon the value of $f$ , four different states of the population has considered.

Embryo stage [0.8 $<f<$ 1],

Exploration state [0.5 $<f\leqslant$ 0.8],

Exploitation state [0.2 $<f\leqslant$ 0.5],

Convergence state [0 $<f\leqslant$ 0.2].

Algorithm 4: Pseudo code of SAPSO

{PSO ……

For

j=1

n

Estimate the mean Eucline distance di of each member of current population with others

Diversity status

S\leftarrow f(d_{g},d_{\max},d_{\min})

Inertia weight for current population

W\leftarrow 1/(1+xe^{-y\times S})

Update in social and cognition constant through random perturbation

For

i=1

N

{PSO ……

5. Experimental result

For the different circuit, the experiment was done to define the corresponding floorplanning. For each one of the three methods, there are three different population size contains, 20, 50 and 100 numbers of the solution have applied independently. To estimate the more accurate performance statistically, 10 different trials have given to each case and various statistical characteristics, including “confidence interval (CI)” for 95% and 99% estimated. In each trial, 500 number of iterations permitted to evolve the solution. For AWPSO, inertia weight change linearly from 1.2 to 0.1, and C1 and C2 both are taken equal to 2. For MSAPSO, in the first stage, there is total 10 independent population, and each population has evolved for 50 iterations. In second stage best members are selected and evolved up to 500 iterations. MATLAB computing environment has taken to develop and execute the solution.

5.1 Test case1: 3rd order IIR filter

The “Infinite Impulse Response (IIR)” filters are basic elements of “Digital Signal Processing (DSP)”. Moreover, the IIR filters are digital filters with the infinite impulse response. Here, the impulse response is “infinite” since there is feedback in the filter. Third order IIR filter as demonstrated in Fig. 4 has taken for the first experimental case; whose modules dimension and their connectivity definition have presented in Table 2.

5.1.1 Performance evaluation of different algorithms with population size 20

In this section, the performance evaluation of proposed and conventional algorithms over IIR filters with population size 20. Here, the evaluation has been done for both the floorplanned Area and the wirelength.

For a population size of 20, all the three algorithms performances for 10 independent trials have shown in Table 4. AWPSO could not converge properly and violate the non-overlapping constraint for 6 trials, as shown with ‘*’. SAPSO has performed comparatively better, and in only one trial, it could not converge properly. Performance of MSAPSO is properly converged for all the cases, not only that obtained statistical parameters are also appealing as shown in Tables 5 and 6. In Table 5, the proposed method is 0.5% better than the conventional SAPSO approach and 5.5% better than the conventional AWPSO approach. Similarly, the proposed approach is 28% better than the conventional SAPSO approach and 0.5% better than the conventional AWPSO approach, and the result is shown in Table 6.

Obtained floorplan using MSAPSO and SAPSO have shown in Figs 5 and 6. It is observed that there is a dead space. This happens because diversity has lost and there is not enough exploration takes place in both algorithms. The level of diversity can be increased with a higher value of population size.

5.1.2 Performance evaluation of different algorithms with population size 50

In this section, the performance evaluation of various algorithms has been presented. Here, the experimentation is performed over the IIR filter with population size 50 for both the floorplanned Area and the wire length.

To understand the effect of population size, the experiment was repeated with population size equal to 50 and 100. There is clear benefit appeared as shown in Tables 7 and 8 and observe that MSAPSO has delivered the better performances. Table 8 summarizes the proposed method is 48% better than the SAPSO method and 23% better than the AWPSO method. Table 9 summarizes the proposed MSAPSO method is 23% better than the SAPSO method and 25% better than the AWPSO method.

From the analysis of Figs 7 to 9, it is clear that there is a reduction in dead zone observed in comparing to dead zone appeared with a population size of 20. Comparative convergence characteristics for the area and wirelength have shown in Figs 10 and 11. In both cases, there is more fluctuation at the beginning of AWPSO, while the performance of MSAPSO in the second stage is very smooth.

5.1.3 Performance evaluation of different algorithms with population size 100

The performance evaluation of the proposed and conventional method is presented. Here, the algorithm is compared with population size 100 for both the floorplanned wirelength and area.

If population size has increased up to 100, there is a huge dead zone reduction achieved withMPSAPSO, in comparison to other algorithms as shown in Tables 10 to 12 and their corresponding floorplan appeared in Figs 12, 15 and 17. Variation in Inertia weight is also observed. Table 11 explains that the proposed method is 14% and 45% better than the SAPSO and AWPSO methods. In Table 12, the proposed method is 43% better than the SAPSO and 68% better than the AWPSO.

In Figs 13 and 14, in the beginning, there is a higher value of diversity hence larger value of “ $w$ ” and nearly follow the pattern defined by diversity. In AWPSO, as appear in Fig. 15, there is a high value of diversity occurs even at the end.

Comparative performances for the area and wirelength convergence characteristics also have shown in Figs 18 and 19. It is observed that MASPSO has shown more stability in comparison to others.

5.2 Test case 2: Lattice filter

The Lattice filter is exploited in extensively in DSP as well as in implementing the adaptive filters.

Another very useful circuit lattice filter as shown in Fig. 20 has taken for the second experiment. Modules size definition and their connectivity have given in Tables 12 and 13.

5.2.1 Performance analyses of different algorithms with population size 20

In this section, the performance analysis of the proposed and conventional algorithms with population size 20 is presented. Here, the comparison is performed for floorplanned Area and wirelength.

Table 15 states that the proposed method is 70% better than the conventional SAPSO method and 57% better than the AWPSO method. Table 16 summarizes that the proposed method is 62% better than the conventional SAPSO method and 42% better than the AWPSO method.

5.2.2 Performance analyses of different algorithms with population size 50

The performance analysis of the proposed and conventional algorithms with population size 50 for Lattice filter is presented. Here, the analysis for both the Floorplanning ara and wirelength is performed.

Table 18 summarizes that the proposed method is 32% better than the SAPSO and 11% better than the AWPSO method. Table 19 explians that the proposed method is 10% better than the SAPSO and 0.79% better than the AWPSO method.

5.2.3 Performance analyses of different algorithms with population size 100

The performance analysis of the proposed and conventional algorithms with population size 100 for Lattice filter is performed.

In Table 21, the proposed method is 20% and 54% better than the conventional SAPSO and AWPSO method. Table 22 summarizes that the proposed method is 7.3% better than the SAPSO method and 33% better than the AWPSO method.

For the lattice filter, the experiment was repeated for three different populations, and their performances have shown in Tables 13 to 21, and obtained floorplan along with their convergence characteristics are available in Figs 21 to 39. In all cases, MSAPSO outperformed the other form of adaptiveness.

6. Conclusion

The problem of floorplanning in VLSI is a critical and very challenging task. In this research, a new variant of PSO, which is based on adaptiveness as according to diversity available in population as well as to increase the diversity, multiculture concept has applied to solve the non-slice type of floorplanning. There is a remarkable performance obtained by MSAPSO in all cases, including with low value of population size. The proposed method has delivered the high level of consistency along with high efficiency in compactness of floorplanning. Two very important circuits, IIR filter, and lattice filter have examined in details and their comparative performances obtained. From the results of the proposed method, it is clearly stated that the time taken for convergence is less for proposed method than the conventional GA used [1, 2, 10]. However, the local search is difficult for the Tabu search method used [5], but the proposed method overcomes this drawback. For finding global maxima, the conventional GA used [26, 27] is not guaranteed. The Simulated Annealing used [23] required branch and bound, yet the proposed method does not require. The proposed method does not easily fall into local optimum but the conventional PSO method used [15, 16] easily fall into a local optimum.

Footnotes

Acknowledgments

This research has completed in EDA division of Manuro Tech Research Pvt. Ltd. Bangalore, India. Authors would like to appreciate the associates for their valuable discussion and suggestions.

Authors’ Bios

	Vinay Kumar S.B currently working as Assistant Professor in the Dept of ECE, School of Engineering and Technology, Jain University, Bangalore. He obtained his Bachelor degree in Electronics and Communication Engineering from Coorg Institute of Technology, ponnampet in 2009, Visvesvaraya Technological University, Belgaum and Master degree (M. tech) in Signal processing and VLSI, Jain University, Bangalore. He is pursuing Ph.D. in Electronics and Communication Engineering, Jain University, Bangalore. My research interest includes VLSI, Reverse logic, DSP and Embedded Systems. He has altogether 10 international journals to his credit and also he presented 5 international conference and 8 technical papers in national conference. He has altogether 3 sponsored projects funded by KSCST (Karnatake State Council for Science and Technology), IISc, Bangalore and 3 NGO projects – Science and Engineering Fair by Agastya International Foundation-Anveshana.
	P. V. Rao Currently working as Professor and PG Coordinator in the Dept of ECE, Vignana Bharathi Institute of Technology, Hyderabad. Telangana State, India. He did B.Sc in 1986, B.E in Electronics from Marathwada University in 1991, and M.E In Digital Electronics from Karnatak University in 1999, Ph.D in Low Power VLSI Signal Processing, from DR. MGR University, Chennai in 2011. His research area interest is Low Power VLSI, Signal and Image Processing, Biomedical Image Processing and Nano-Sensors. 3 Research scholars awarded Ph.D under his supervision and currently 6 Research scholars perusing Ph.D of VTU, Belagavi and Jain University, Bengaluru. He Published 39 International Journals and 20 papers presented in International and 15 in National conferences. He is Life member of FIETE, MISTE, ITES and IMAPs and also Reviewer and Editor for Peered Journals Springer, Telkomnika, EURASIP, IJCT BORJ, ARJECE and Inder science. He was Program Chair for 7 International Conferences and many national conferences and workshops.
	Manoj kr. Singh is having background of R&D in Nanocomputing, Evolutionary computation, Neural network etc. He is involved heavly in designing of intelligent solution. Currently he is holding the post of director in Manuro Tech. Research Pvt. Ltd. Bengaluru, Karnataka.

References

Eguchi

Suzuki

Yamane

and Oshima

, An application of genetic algorithms to Floorplanning of VLSI, Rough Sets and Current Trends in Computing, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 1424 (1999), 263–270.

Valenzuela

L.C.

and Wang

P.Y.

, A genetic algorithm for VLSI Floorplanning, Parallel Problem Solving from Nature PPSN VI, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 1917 (2000), 671–680.

Chen

and Wong

D.F.M.

, Integrated Floorplanning and interconnect planning, layout optimization in VLSI design, Network Theory and Applications, Springer, Boston, MA, 8 (2001), 1–18.

Anjos

M.F.

and Vannelli

, An Attractor-Repeller approach to floorplanning, Mathematical Methods of Operations Research 56(1) (2001), 3–27.

Emmert

J.M.

Lodha

and Bhatia

D.K.

, On using Tabu search for design automation of VLSI systems, Journal of Heuristics 9(1) (2001), 75–90.

Faroe

Pisinger

and Zachariasen

, Guided local search for final placement in VLSI design, Journal of Heuristics 9(3) (2001), 269–295.

Yang

Song

Yang

H.H.

and Xie

, A theoretical upper bound for IP-Based Floorplanning, Computing and Combinatorics, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 3595 (2005), 411–419.

Liu

Zhong

and Jiao

, Moving block sequence and organizational evolutionary algorithm for general Floorplanning, Computational Intelligence and Security, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 3801 (2005), 238–246.

Zamani

M.S.

and Hellestrand

G.R.

, A new neural network approach to the floorplanning of hierarchical VLSI designs, Neural Networks for Communications and Control, From Natural to Artificial Neural Computation, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 930 (2005), 1128–1134.

10.

Tang

and Sebastian

, A genetic algorithm for VLSI Floorplanning using O-Tree representation, Applications of Evolutionary Computing, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 3449 (2005), 215–224.

11.

Luo

Anjos

M.F.

and Vannelli

, A nonlinear optimization methodology for VLSI fixed-outline floorplanning, Journal of Combinatorial Optimization 16(4) (2005), 378–401.

12.

Chiang

, Ant colony optimization for vlsi floorplanning with clustering constraints, Journal of the Chinese Institute of Industrial Engineers 26(6) (2009), 440–448.

13.

Fang

Chang

and Chen

, A parallel simulated annealing approach for Floorplanning in VLSI, Algorithms and Architectures for Parallel Processing, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 5574 (2009), 291–302.

14.

Chen

and Guo

, A discrete PSO for multi-objective optimization in VLSI Floorplanning, Advances in Computation and Intelligence, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 5821 (2009), 400–410.

15.

Cong

and Ma

, Thermal-aware 3D Floorplan, three dimensional integrated circuit design, Part of the Series Integrated Circuits and Systems (2009), 63–102.

16.

Chen

Guo

and Chen

, A PSO-based intelligent decision algorithm for VLSI floorplanning, Soft Computing, Fuzhou, China, 14(12) (2009), 1329–1337.

17.

Pavlidis

V.F.

and Friedman

E.G.

, Physical design issues in 3-D integrated technologies, VLSI-SoC: Design methodologies for SoC and SiP, IFIP Advances in Information and Communication Technology, Rhodes Island, India, Springer, 313 (2010), 1–21.

18.

Deng

Y.S.

and Maly

W.P.

, Floorplanning for Integration, 2.5-D 3-Dimensional VLSI (2010), 83–116.

19.

Potti

and Pothiraj

, GPGPU Implementation of Parallel memetic algorithm for VLSI Floorplanning problem, Trends in Computer Science, Engineering and Information Technology, Communications in Computer and Information Science, Springer, Berlin, Heidelberg, 204 (2011), 432–441.

20.

Rani

D.G.N.

and Rajaram

, Performance driven VLSI Floorplanning with B*Tree representation using differential evolutionary algorithm, Trends in Network and Communications, Communications in Computer and Information Science 197 (2011), 445–456.

21.

Anjos

M.F.

and Liers

, Global approaches for facility layout and VLSI Floorplanning, International Series in Operations Research & Management Science, Springer, Boston, MA, 166 (2011), 849–877.

22.

Lim

Song

and Shin

, Integrated circuit Floorplanning by using an analytical algorithm, Convergence and Hybrid Information Technology, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 7425 (2012), 404–411.

23.

Anand

Saravanasankar

and Subbaraj

, Customized simulated annealing based decision algorithms for combinatorial optimization in VLSI floorplanning problem, Computational Optimization and Applications 52(3) (2012), 667–689.

24.

Beckhoff

Koch

and Torreson

, Automatic Floorplanning and interface synthesis of island style reconfigurable systems with GoAhead, Architecture of Computing Systems – ARCS, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 7767 (2013), 303–316.

25.

Kureichik

V.M.

Lebedev

B.K.

and Lebedev

V.B.

, VLSI Floorplanning based on the integration of adaptive search models, Journal of Computer and Systems Sciences International 52(1) (2013), 80–96.

26.

Sivaranjani

and Kumar

A.S.

, Thermal-aware non-slicing VLSI Floorplanning using a smart decision-making PSO-GA based hybrid algorithm, Circuits, Systems, and Signal Processing 34(11) (2013), 3521–3542.

27.

Aharoni

Boni

and Freund

, Rectangle placement for VLSI testing, Integration of AI and OR Techniques in Constraint Programming, Lecture Notes in Computer Science, Springer, Cham, 9075 (2015), 18–30.

28.

Ahmed

M.A.

Mohapatra

and Chrzanowska-Jeske

, TSV- and delay-aware 3D-IC floorplanning, Analog Integrated Circuits and Signal Processing 87(2) (2016), 235–248.

Multi-culture diversity based self adaptive particle swarm optimization for optimal floorplanning

Abstract

Keywords

1. Introduction

Table 1 Non-overlapping constraint definition

Table 2 A solution representation in population for PSO

Table 13 Dimensions of each module with their forward path wire connection

Table 14 Performance by algorithms over Lattice filter with population size 20

Table 22 Statistical performances by algorithms over Lattice filter for floorplanned wire length with population size 100

4.2 Comparison of multi-culture PSO with other variants

4.2.1 Adaptive weight PSO (AWPSO)

5.1 Test case1: 3rd order IIR filter

5.1.1 Performance evaluation of different algorithms with population size 20

5.1.2 Performance evaluation of different algorithms with population size 50

5.1.3 Performance evaluation of different algorithms with population size 100

5.2 Test case 2: Lattice filter

5.2.1 Performance analyses of different algorithms with population size 20

5.2.2 Performance analyses of different algorithms with population size 50

5.2.3 Performance analyses of different algorithms with population size 100

6. Conclusion

Footnotes

Acknowledgments

Authors’ Bios

References

Table 1
Non-overlapping constraint definition

Table 2
A solution representation in population for PSO

Table 13
Dimensions of each module with their forward path wire connection

Table 14
Performance by algorithms over Lattice filter with population size 20

Table 22
Statistical performances by algorithms over Lattice filter for floorplanned wire length with population size 100