1 Introduction

A three-dimensional IC is an Integrated Circuit manufactured by laying several vertical silicon wafers or die. The different layers are connected either by Through Silicon Vias (TSVs) or by Cu-Cu interconnects [1, 2]. While the Cu-Cu interconnection with silicon generates sheer force between them, there is a high chance of failure when IC is heated and hence TSVs are widely used to connect these different layers. 3-D integration provides a higher device density as well as higher bandwidth. It is also possible to integrate heterogeneous technologies in a layered die stack structure, which counteracts system-on-chip integration. Other benefits of 3-D ICs include smaller footprints; lower interconnect delays, higher performance, as well as lower power consumption. 3-D IC changes the wirelength distribution from 2-D layout. There are two approaches used to design 3-D ICs, via-first and via-last. The TSVs in the Via-first approach only interfere with the device layers, while in the Via-Last approach: the TSVs interact not only with the device layers but also with the metal layers.

The inputs to 3D-ICs are:

  1. 1.

    A set of blocks with a specific shape and size,

  2. 2.

    A list of number of terminals on each block and,

  3. 3.

    The netlist describing the interconnections between these blocks.

2 Problem formulation

We have focused our work in Four-Layer 3D-IC, where we have partitioned the set of blocks in four different layers such that their area difference is as small as possible.

Let \(B = \{{b}_{1}, {b}_{2}, . . . , {b}_{n}\}\) be a set of ‘n’ modules. The module \({b}_{i}\) could be represented by \(({W}_{i},{ H}_{i}), 1 \le i\le n\), where \({W}_{i}\) is its width and \({H}_{i}\) is its height.

Let \(\eta = \{{N}_{1}, {N}_{2}, . . . , {N}_{m}\}\) be the set nets, where 'm' denotes the total number of nets that link the blocks,

Taking \({L}_{i}\) as the estimated length of net \({N}_{i}\), \(1 \le i\le m\). The placement objective is to identify a group of rectangles represented by \(R = \{{r}_{1}, {r}_{2}, . . . , {r}_{n}\}\) for each block represented by set \(B\) such that,

  1. 1.

    Each block \({b}_{i}\) can be placed either in the four layers.

  2. 2.

    Each \({b}_{i}\) block can be put in the rectangle \({r}_{i}\), which has the dimensions \(({W}_{i},{ H}_{i})\).

  3. 3.

    No two modules overlap each other, that i \(s{ r}_{i}\cap {r}_{j}=\Phi , 1\le i,j\le n\).

  4. 4.

    The total area occupied by \(R\) is minimized.

  5. 5.

    The total wirelength determined by \(\sum_{i=1}^{m}{L}_{i},\) is minimized.

  6. 6.

    The total number of TSVs should be minimized.

2.1 Area optimization

VLSI floor planning consists solely of the arrangement of non-overlapping rectangles. The arrangement of blocks on a chip is divided into two types: slicing floorplan and non-slicing floorplan. The sequence-pair (SP) approach was used to investigate the non-slicing floorplan in this work. Murata et al [3] have demonstrated that the SP's searching space results in an effective rectangular packing of the modules. Tang et al [4] proposed a method called Fast Longest Common Subsequence (fast LCS) to encode a sequence pair to its corresponding floorplan.

2.2 TSVs optimization

The 3D-IC design problem involves division of the circuit netlist into multiple parts (in our case two or four parts) such that there are some connections between these parts. The number of edges in the two parts of the circuit is the number of TSVs in the 3D-IC and this number can be calculated as follows:

$$T=\sum_{i=1}^{k}\sum_{j=1}^{k}{T}_{ij} ,(i\ne j)$$
(1)

where \(i\),\(j\) are the edge's vertices. \(T = total \,number\, of\, TSVs\).

$$ T_{{ij}} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {if\quad i{\text{th}}\,node\,{\text{in}}\,{\text{bottom}}\,{\text{layer}}\,{\text{has}}\,{\text{a}}\,{\text{connection}}\,{\text{with}}\,j{\text{th}}\,{\text{node}}\,{\text{of}}\,{\text{top}}\,{\text{layer}}} \hfill \\ {0,} \hfill & {{\text{otherwise}}} \hfill \\ \end{array} } \right. $$

The design problem in first stage is a partitioning problem where the netlist, say \(V\) is to partition into \({V}_{1}, { V}_{2}, { V}_{3}\,\&\,{ V}_{4}\), such that,

$$ V_{i} \cap V_{j} = \emptyset \quad {\text{and}}\quad \bigcup\limits_{i,j = 1}^{4} {V_{i} \cup j = V} ,\quad i \ne j $$
(2)

As the problem involves bipartitioning of a circuit, so equality condition must be satisfied as

$$ Number\,of\,nodes\,in\,partition\,1\, \cong \,number\,of\,nodes\,in\,partition\,2 .$$
(3)

2.3 Wirelength estimation

In 3-D floorplanning, there is a high chance that all the terminals of a net may lie in multiple layers and hence the lateral wirelength calculation becomes necessary. In this paper we have estimated the total lateral wirelength by first calculating wirelength on each individual dies then summing up them. Also, in our proposed technique, the wirelength of a net (say n) on a particular die is calculated by the half perimeter wirelength of all its terminals on that die and any TSV of n in the same die or die above/below it. In figure 1, the lateral wirelength of a 3D net n is obtained by summing up the estimated wirelength of subsets n1, n2 & n3 [5].

Figure 1
figure 1

Wirelength estimation model: a net divided into subnets and summing up individual subnet wirelength [5].

Full size image

To estimate the wirelength due to TSVs we have taken the TSV size as 3 μm as in [2] unless otherwise specified.

Hence,

$${W}_{T}=T\times 3\, \upmu \mathrm{m}$$
(4)

where T is the total number of TSVs.

2.4 Combined area, wirelength and TSVs optimization

While the purpose of traditional 3D-IC design methods is to reduce the number of TSVs, integrating it with the area and wirelength reduction makes this work much harder. Designing multi-objective 3D-ICs is substantially more complicated. One of the most challenging aspects of multi-objective optimization is that there is no one best solution for every target in the solution space. Additionally, adopting an ideal solution for one goal may necessitate receiving a suboptimal result for another. Hence, it is difficult to define what constitutes a good answer. The formulation of a good solution is adopted as it appears in [6]:

  1. 1.

    Allow for more precise handling of the trade-offs between goals.

  2. 2.

    Produce partitioning that is predictable.

  3. 3.

    Provide a method for dealing with objectives that correspond to amounts of various types.

In this case, a design technique is required that can optimize objective \(T\), the number of TSVs, minimization of objective \(A,\) the total area occupied by the modules in two/four-layer and minimizing objective \(W,\) the total wirelength. However, the three objectives are dissimilar objectives, which means that optimizing \(T\) alone does not necessarily imply that \(A\) and \(W\) are optimized and vice-versa. That is why we adopt a combination-based formulation for multi-objective optimization: The combined objective will be a scalar combined metric \({C}^{c}\) given by the following equation:

$${C}^{c}=\lambda *\frac{A}{norm(A)}+\left(1-\lambda \right)*\frac{W}{norm(W)}+\mathrm{T}$$
(5)

where \({C}^{c}, \lambda , A, L, T, norm\left(A\right) and norm(L)\) are Combined objective function, weight given to area (0–1), Total area occupied by the modules in different layers of 3D IC, Total wirelength of 3D IC, Total number of TSVs, normalized area and normalized wirelength respectively.

Minimizing equation (5) seeks to calculate a 3D layout that is as close as possible to any of the best in terms of any beginning goal. The area weight may be used to traverse the distance between each objective's best solution locations, resulting in a predictable structure based on the area weight as well as fine-tuned management of the trade-off between the three objectives.

In the present work, a P-PSO algorithm [7] for the optimization of multimodal continuous functions is proposed. P-PSO is used for global optimization by updating particle locations to achieve quick convergence. To determine the layout in each of the two layers the sequence pair (SP) technique with Longest Common Sequence (LCS) has been used. Firstly, the given netlist has been partitioned into four partitions and then four different types of operations are allowed to perturb the bi-partitioned circuit and in the given sequence pair to another sequence pair listed as:

  • Op1: Swap two module names in all the partitions.

  • Op2: Swap two module names in only one sequence of each partition.

  • Op3: Swap two module names in both sequences of each partition.

  • Op4: Rotate a module in each partition.

The fundamental PSO method generates a swarm of particles, each particle representing a potential result to the optimization problem; searches throughout the search space are generated. The particles are initially given a random velocity and position in the search space. Each particle's goal is to find the best global solution to the optimization problem. With the help of classical PSO, we can only get the perturbation operation Op4 as it gives only one best particle in any iteration. Op1–Op3 require two different particles to perform. To overcome this drawback we have defined two distinct sets of arms with the same number of particles. The two parallel PSOs run at the same time to search inside their respective search areas, yielding two distinct particles, one for each search space.

3 Experimental results

We simulated the proposed 3-D floorplans which are, wirelength and TSV co-optimization. We used the MCNC and GSRC hard benchmark suites [10] as our test cases. We have the unit in the MCNC and GSRC benchmarks to 1 μm. The TSV size is 3 μm as in [2] unless otherwise specified. The IO pad locations are assigned randomly. For a fair comparison, the four-layered results were obtained and compared with [2, 8, 9]; the comparison results are shown in table 1.

Table 1 4-Layered 3D IC parameters optimization comparison of results on MCNC & GSRC benchmark circuits.
Full size table

4 Summary

3D integrated circuits (3D-ICs) are a new technology that is more promising. 3D-ICs have a tiny footprint and vertical linkages between dies, allowing for shorter wirelength between gates. As a result, they have lower connection latency and power consumption. The 3D Partitioning and Layer Assignment stage is the first of several in the design flow of 3D integrated circuits. This step is crucial since the outcome will have an impact on the performance of succeeding processes. This issue is NP-hard, much like other partitioning problems. The implementation of iterative heuristics [8] was used to handle this essential problem. When attempting to tackle this problem, several factors have been considered. Layer assignment, TSV reduction, wirelength optimization and area balance are some of these considerations. To do these objectives, we have proposed Parallel PSO (P-PSO). The results obtained were compared and found to be giving better solutions when compared to other algorithms. As shown in table 1 as compared to SA [9] the average wirelength has an average improvement of 52.35% and the TSV count has an average improvement of 29.64%. Our results show an average improvement of 8.36% over the area occupied by the three-layered 3D IC and an average improvement of 14% over TSV count as compared to the results with Tabu Search [8].