Keywords

1 Introduction

VLSI technology has become an essential part of our daily life. Today’s generation cannot even imagine life without electronic gadgets. With the increasing demand for fast with less power consumption gadgets, researchers are looking after interconnect delays and their need for power, which largely depends on long interconnects. Floorplanning (in the physical design step of the VLSI design cycle) plays an essential role in deciding the interconnect lengths, area, power consumption, and speed of the designed and manufactured chip (silicon die). The process of managing, placing, and arranging the blocks or cuboids and their netlist on the die is called floorplanning. If planning of blocks is done in XY plane, then it is called 2D floorplan. When the third dimension (Z) is added (XYZ space), it is called 3D floorplan. In both cases, the ultimate goal is to arrange the blocks or cuboids so that no modules or cuboids overlap each other and interconnects and other design parameters that cost the die’s performance may be minimized. In most cases, the shape of the manufactured chip or die is rectangular or cuboidal. Most of the floorplanning problem solving is the rectangular (2D) and cuboidal (3D) one in which there should not be any overlapping between the blocks.

Since the floorplanning problem in VLSI is an NP-hard problem, there are many representations and metaheuristic approaches suggested and applied by researchers for optimized floorplanning. With the advancement in time, researchers are looking towards the third dimension due to many advantages. These advantages include shortening of area, interconnects, timing, etc. However, there are challenges too in 3D floorplan design. The main challenge in the 3D representation is the temperature issue. Another challenge is the proper management of 3D interconnects. The present era of technologies is working under 1 micron interconnect vias between different layers of 3D floorplan structure [1]. Much research has commenced on 2D floorplanning than on 3D floorplanning techniques. Hence, there is a lot of opportunities for the researchers in 3D floorplanning. A general 3D floorplan structure is shown in Fig. 1. There can be any number of layers of die in a 3D floorplan structure. All these layers are separated by interconnects, TSVs, and other vias.

Fig. 1
figure 1

A general 3D representation of blocks embedded in various tiers

Full size image

This article mainly focuses on 3D floorplan research and is divided into various sections. Section 2 describes the differences between 2 and 3D representations, including advantages and challenges. Section 3 presents the timeline of research commenced in 3D floorplan. Section 4 describes the design metrics in the 3D floorplan. Section 5 briefly describes some of the important floorplan representations. Section 6 presents the results and discussion of various research articles. Conclusion with the future scope is drawn in the end.

2 2D Versus 3D Floorplan Representation

With extensive improvement in floorplan techniques, a lot of research occurred in the third dimension of the 3D axis, which resulted in the development of 3D floorplan techniques. There are numerous advantages of the 3D floorplan technique over 2D floorplan techniques. Some of them are as follows:

  1. 1.

    Interconnect delays are reduced as wirelength can be evidently reduced by 3D technology.

  2. 2.

    3D packaging can replace long, global wires by using the third dimension to short, vertical, or horizontal interconnects. This helps to decrease the area, circuit delay, system power dissipation, and other die parameters. Studies show that the reduced wire length can lead to up to 30% delay reduction in 3D chip design [2].

  3. 3.

    3D floorplan or packaging can lead to high-bandwidth memory due to the wider and shorter bus widths.

  4. 4.

    Heterogeneous integration is possible in 3D packaging as it allows different circuit layers to be implemented by different process technologies.

Besides numerous advantages of 3D floorplan technology, there are many challenges too in meeting the requirement of the 3D floorplan. Some of these are:

  1. 1.

    Due to an increase in temperature after adding z-direction (blocks get more tightly packed).

    • There are longer interconnect delays.

    • Functional failure due to high temperature.

    • If not designed properly, there is a considerable possibility of accelerated electromigration and thermal runaway. Hence, performance and reliability issues are there.

  2. 2.

    The cooling cost is anticipated to be higher in the 3D floorplan technique as the increased temperature needs powerful cooling solutions like Thermal via solution and 3D IC cooling techniques like Fans, fins, ACs, etc.

  3. 3.

    Complex fabrication.

  4. 4.

    Increased fabrication cost.

  5. 5.

    It is not easy to convert EDA tools for 2D IC technology to 3D IC technology.

Some of the differences between 2D floorplan and 3D floorplan are summarized in Table 1 and Fig. 2.

Table 1 2D versus 3D floorplan
Full size table
Fig. 2
figure 2

Concept of stacking in blocks

Full size image

3 Evolution of 3D Floorplan Techniques

2D floorplan techniques have been extensively used for a long time. In that too, most of the work was done manually, but with the advancement in time, advanced tools and techniques were developed to ease the process of VLSI floorplan. A lot of work is still going on in the 2D floorplan. But researchers are exploring the third dimension in the floorplan. This representation is known as 3D floorplan representation. Many 2D representations in VLSI floorplan have been extended to 3D representation. In this section, only essential and chosen literature has been incorporated. In 2002, Salewski and Barke [3] extended the 2D slicing tree representation to 3D (for the first time in slicing representation) using upper bound. In 2004, 3-Dimensional sub-Transitive Closure Graph (3D-subTCG) was proposed for the first time by Yuh et al. [4]. When checked on 3D benchmarks, this representation algorithm achieved smaller volume in a significantly smaller amount of time. In 2004, Yuh et al. [5] proposed T-tree representation for 3D floorplanning, an extension of 2D B*-Tree representation, and checked on 3D MCNC and 3D GSRC benchmark circuits (described in Sect. 5.5). In 2004, Cong et al. [6] proposed a thermal-driven algorithm that integrates a resistive thermal model, a fast closed-form temperature equation, and a hybrid model for 3D floorplan, which can control the on-chip temperature effectively lowering wirelength and area simultaneously. In 2005, Ma et al. [7] proposed 3-Dimensional Corner Block List (3D CBL), which was the revision of [8] by presenting a triple list coding system to represent the relationship between cuboids. This representation can handle both slicing as well non-slicing floorplan. The results are compared with [3] and [4] and showed an immense improvement. In 2005, Cheng et al. [9] proposed an algorithm, which extended the 2D slicing floorplan to the 3D slicing floorplan. A detailed description of the slicing and non-slicing floorplan is described in Sect. 5.2. In 2006, Dong et al. [10] extended the 2D CBL to 3D CBL, described in Sect. 5.1 of this article. The results of this article were found to be suitable for 3D IC design. In 2006, Wong et al. [11] proposed an algorithm that can decouple capacitance by introducing white spaces in the modules and various layers for better noise immunity and better thermal distribution between the layers and modules, though to counter this, area, wirelength and time has to be compromised. In 2007, Zhang et al. [12] improved 3D BSG (described in Sect. 5.3) by improving time which is linear. The 3D bounded problem is to find the achievable solution by finding the room with a minimum bounded box for the module. In 2007, Li et al. [13] introduced an algorithm using mixed-integer linear programming. Their algorithm could find and remove thermal hotspots without compromising area and wirelength in different layers of 3D structure. In 2010, Falkenstern et al. [14] developed a tool that addresses the concern of IR losses in the P/G mesh network in a 3D floorplan structure. Researchers can use this tool to explore 3D P/G mesh and IR losses for optimized performance in the structure. In 2011, Frantz et al. [15] proposed a genetic algorithm to optimize the design parameters in each tier and between the tiers of 3D structure. In 2011, Nain and Jeske [16] developed an algorithm that deals at the logic gates level within the module, converting the module into a 3D module by splitting the module into different parts, aligning them vertically to reduce the interconnect lengths between the various modules after modification of the modules. In 2013, Li et al. [17] proposed a fast algorithm that simultaneously optimized the module floorplan and placed the TSVs (Through Silicon Vias), optimizing the wirelength of the floorplan. In 2013, Wen et al. [18] proposed cluster-based 3D floorplanning to optimize area, wirelength, and power density where thermal vias were placed at reserved regions. In 2014, Khan et al. [19] proposed a new topological structure for a 3D floorplan and applied a novel algorithm to check the effectiveness of the topological structure. The topological structure is checked on some samples of floorplan problems. In 2015, Chen and Ruan [20] proposed another thermal aware algorithm for 3D floorplan, which splits, clusters, insert vias, and stacked to form a 3D floorplan. When checked on MCNC benchmarks, the algorithm showed promising results. In 2015, Quiring et al. [21] introduced a guided simulated annealing-based algorithm that optimized global interconnect routes, TSVs, and accounts for fixed-outline floorplanning. Results were checked on GSRC benchmarks. Apart from these, some literature had proposed a combination of circuit simulation and synthesis tools for their research as in Song et al. [22] and Chan et al. [23]. A summary of the timeline of 3D floorplan techniques is presented in Table 2.

Table 2 Timeline of 3D floorplan techniques
Full size table

4 Design Metrics for 3D Floorplan

A researcher must keep in mind the design metrics of the chip while designing and implementing the technique/representation. Keeping in mind the design metrics, the performance of the chip can be significantly enhanced. We can define the VLSI floorplan problem to propose, design, and plan the shapes, positions, routability, orientation, etc., of modules to optimize the chip’s performance (size, speed, power, etc.). The ultimate goal of the researcher in the VLSI floorplan is to:

  • Minimize area or volume.

  • Minimize total wire length.

  • Minimize delays.

  • Maximize routability.

  • Minimize heat dissipation and problems arising due to it.

  • Maybe others like noise, interference, bandwidth, etc.

Some of the precautions that should be taken by a researcher during the planning, designing of the chip in the VLSI Floorplanning design step are as follows:

  1. 1.

    The size of the chip should be as small as possible.

  2. 2.

    The shape of the designed floorplan should be as square (cube) as possible.

  3. 3.

    In most cases, larger modules are placed at the side or corner of the chip, though it depends on the chip’s functionality.

  4. 4.

    If possible, modules with high pad I/O terminals should be planned on the outer edge of the chip to reduce the wirelength and its resulting problems.

  5. 5.

    If possible, modules with I/O terminals (not pad I/O terminals) should be in the interior of the chip. It can result in reduced wirelength and size of the chip, which enhances the chip’s performance.

  6. 6.

    Modules with higher heating effects should be kept near the sides and towards heat sinks as much as possible to reduce the impact of heating issues like thermal runaway, etc.

  7. 7.

    Modules with higher connectivity should be placed as close as possible if some significant parameter is not affected.

Some of the essential terminologies involved in 3D VLSI floorplan structure are described in the following subsections.

4.1 Cuboid (Module/Block)

A cuboid is a definition of a circuit being laid out or a constituent (or primitive) cell in the 3D representation of the VLSI Floorplan. Each cuboid in a chip has a unique module name. Some of the types of the cuboid (Module/Block) are as follows.

4.1.1 Hard Cuboid/Block

A hard cuboid/block has features like width, height, depth, and volume that remain constant, and its Input–Output pin locations are defined. It is not flexible in shape but is free to rotate.

4.1.2 Soft Cuboid/Block

A soft cuboid/block has changeable dimensions (width, height, and depth) and I/O terminal locations [3]. But the volume/area of the soft cuboid/block is always fixed. If V(i), w(i), h(i), and d(i) represent the volume, width, height, and depth of ith cuboid, respectively, and ‘r’ denotes the shape flexibility (range of aspect ratios with height, width, and depth), then it should meet the following conditions:

$$ \frac{1}{r} \le \frac{w(i)}{{h(i)}} \le r,\quad \frac{1}{r} \le \frac{d(i)}{{h(i)}} \le r,\quad \frac{1}{r} \le \frac{w(i)}{{d(i)}} \le r $$

Equivalently, shape flexibility can be defined by the following condition:

$$ \frac{{\max \left( {w(C),d(C),h(C)} \right)}}{{\min \left( {w(C),d(C),h(C)} \right)}} \le r $$

4.1.3 Supermodule

A supermodule is a sub-floorplan that contains one or more modules. In the slicing floorplan, every internal node represents a supermodule [9].

4.1.4 Preplaced Module

A preplaced module is a special kind of constraint module, and it has no freedom to move. It is also considered as an obstacle constraint [9].

4.2 Mosaic Floorplan

When the floorplan is left with no empty spaces or volumes, then the floorplan is known as a mosaic floorplan. In a 3D mosaic floorplan, there are three surfaces: front, back, and top surface. All surfaces in either direction are connected as a 2D mosaic floorplan. Any placement of 3D modules can be added with 3D dummy modules to fill all empty space and then be represented as a 3D mosaic floorplan [24].

4.3 Benchmark Circuits

Benchmark circuits are used to check whether the proposed floorplan is feasible or not. Benchmarks are used as a standard to check floorplan representations and heuristics applied on floorplan representations. Any new model or new research on the VLSI floorplan should use these benchmarks to check and compare their results with others. Most of the literature has used the Beasley and Okp benchmarks (Table 3). Also 2D MCNC (Microelectronics Center of North Carolina) (Table 4) and the 2D GSRC (Gigascale Systems Research Center) (Table 5) benchmark circuits are used as layers with insertion of white spaces, vias, and TSVs. Other benchmark circuits include 3D MCNC and 3D GSRC [5], ISPD98 Circuit Benchmark [25].

Table 3 Characteristics of Beasley and Okp Benchmarks
Full size table
Table 4 Characteristics of MCNC benchmarks
Full size table
Table 5 Characteristics of GSRC benchmarks
Full size table

4.4 Stacking in 3D Floorplan

The concept of stacking is extensively used in designing a 3D structure to minimize temperature, area, wirelength, etc. Most of the research literature has used layering and stacking of modules for the efficient performance of die. In this technique, different modules in a circuit are divided into various layers to form stacks that may be designed as thermal, white space aware for optimal performance. For example, in Fig. 2, a particular floorplan (set of modules) is divided into four parts, each containing a set of modules as layers. These layers are stacked vertically as per optimal performance in terms of area, wirelength, white spaces, temperature, etc.

4.5 White Spaces

A desirable and willingly introduced space in the floorplan to reduce the heating problem, capacitance and inductance coupling, and other undesirable issues in the 3D floorplan is known as White space. Researchers aggressively use the technique of introducing white spaces in the VLSI floorplan technique. The thorough usability of white space is described in Wong et al. [11], Tsai et al. [26], Li et al. [27].

4.6 Ideal Volume/Area

Ideal Volume (IV)/Area (IA) or Minimum Volume/Area is the minimum volume/area taken by all blocks (Vi)/(Ai) in the minimum possible cuboid/rectangle of the floorplan. It is simply the addition of individual volumes/areas of all n blocks in the floorplan.

$$ \begin{aligned} IV & = \sum {\left( {W_{i} *H_{i} *D_{i} } \right)} \\ IA & = \left( {W_{i} *H_{i} } \right) \\ \end{aligned} $$

where i = 0 to n, Wi is width, Hi is height, and Di is the depth of an individual block. Ideal area is calculated when modules are stacked in layers (tiers) in 3D floorplan representation.

4.7 Dead Space

When n blocks of the chip are packed in minimum possible volume in non-overlapping manner (so that there is no possibility of moving the blocks without compromising the characteristics of the chip), it has still some space not occupied by any blocks, that space is known as Dead Space (DS). It is measured in percentage of FS as:

$$ {\text{DS}} = \left( {{\text{FS}} - {\text{IV}}} \right){\text{/FS}}\;*\;100. $$

\(\begin{gathered} \begin{array}{*{20}l} {{\text{where}}\;{\text{FS:}}} \hfill & {{\text{Floorplan}}\;{\text{Space}}\;({\text{Implemented/Used}}\;{\text{Volume}})} \hfill \\ {\text{IV:}} \hfill & {{\text{Minimum}}\;{\text{Space}}\;{\text{or}}\;{\text{Ideal}}\;{\text{Volume}}} \hfill \\ \end{array} \hfill \\ {\text{Space}}\;{\text{utilization}}\;{\text{is}}\;{\text{defined}}\;{\text{as:}}\;\;{\text{100}} -{\text{DS}}{.} \hfill \\ \end{gathered}\)

4.8 Temperature

Temperature plays an important role in the performance of the chip. At higher temperatures, transistor performance degrades because the mobility of electrons decreases and resistivity increases. Hence, reliability decreases according to Arrhenius equation: MTF = MTFoe(Ea/KbT) [9]. It is this design parameter where dead space can be useful. Since dead spaces are empty spaces, it can help in better regulation of temperature.

Another thing to keep in mind is that the different modules dissipate different amounts of heat. Some may dissipate more, while others may do less. Hence, the proper distribution of these modules according to their heat dissipation characteristics will result in better overall chip performance.

In 3D floorplanning, it becomes a significant and severe issue. The main focus of researchers in 3D floorplanning is mainly on reducing temperature via various techniques such as proper managing of blocks, introducing white spaces, introducing thermal vias by dividing floorplan into various layers. Li et al. [13] proposed different Thermal via techniques for better heat flow management through the floorplan. The main idea is to apply algorithms to find hot areas (or hot spots) in the floorplan. In these hot areas, thermal vias can be inserted, which helps in heat flow management. It can be better understood with the hot area problem, where encroachment of modules produces hot areas in the floorplan. Modules are placed as far as possible in the minimum possible area/volume to curb this problem. As shown in Fig. 3, a hot area is recognized at a particular layer location. Then a white space is created by moving blocks and inserting thermal vias at that location. This technique is extensively used, which highly enhances the performance of the chip.

Fig. 3
figure 3

Insertion of thermal vias at the high-temperature area

Full size image

For thermal modeling of floorplan, each tier is usually modeled as a resistive network with current sources. This model of current and resistance can be used to determine the temperature of a particular stack. Compared to actual simulated results, this model has less than an error of 2% [28].

If the structure is divided into various tiers, where the top layer is used as a heat sink, then the maximum temperature of each layer can be calculated [6, 29] as:

$$T=\sum_{i=1}^{k}\left[ R\left(i\right) \sum_{j=1}^{i}P\left(j\right)\right]+R\left(b\right) \sum_{i=1}^{k}P(i)$$

\(\begin{array}{*{20}l} {{\text{where}}} \hfill & {R(i){:}\;\;{\text{Thermal}}\;{\text{resistance}}\;{\text{of}}\;{\text{the}}\;i{\text{th}}\;{\text{layer}}} \hfill \\ {} \hfill & {R(b){:}\;\;{\text{Thermal}}\;{\text{resistance}}\;{\text{of}}\;{\text{the}}\;{\text{bottom}}\;{\text{layer}}} \hfill \\ {} \hfill & {P(i){:}\;\;{\text{Power}}\;{\text{density}}\;{\text{at}}\;i{\text{th}}\;{\text{layer}}.} \hfill \\ \end{array}\)

5 3D Floorplan Representations and Techniques

Many representations and techniques have been described in different research articles. Some of the techniques involve using algorithmic techniques of 2D as intra-tier and its extended version that is applied between various tiers of 3D floorplan (inter-tier) [15, 16]. Some of the intra-tier (within the layer) techniques are:

  • Rotation of blocks (swapping width and height of blocks)

  • Deletion and insertion of blocks

  • Movement of blocks

  • Swapping of blocks

  • Invert blocks

Some of the 3D techniques (inter tier (between the layers)) that can be used while designing algorithmic tools are:

  • Swap blocks between two tiers (layers)

  • Deletion and insertion of blocks between tiers

  • Movement of blocks between tiers

  • Slack movement to minimize interconnects and chip temperature.

The above-mentioned steps are usually used in optimization techniques for the optimized result that can be deterministic, evolutionary, swarm, and other optimization techniques.

Though there are many representations for 3D floorplan, only some of the crucial (volume-based) models for 3D floorplan structure are briefed in the following sub-sections.

5.1 3D CBL

3D CBL [7] is a revised version of 2D CBL [8, 30]. In 3D Corner Block List representation, every cube is divided into various cuboidal rooms (Fig. 4). Each room is assigned with no more than one cuboid. In this representation, the root of the tree is placed at the upright corner of the 3D floorplan.

Fig. 4
figure 4

Corner block insertion technique

Full size image

5.2 3D Slicing Floorplan

Similar to 2D slicing floorplan [31] representation, 3D representation [9] can be presented as slicing floorplan. The main difference between the two is that in 3D representation, one more cut, ‘Z’, is added other than ‘X’ and ‘Y’ (‘H’ or ‘V’) cut. As shown in Fig. 5, initially, the ‘X’ cut has to be made, then the ‘Y’ cut is made, resulting in the separation of ‘1’ and ‘3’ cuboids. In the same way, other cuboids can be represented or separated.

Fig. 5
figure 5

3D slicing floorplan representation and equivalent floorplan

Full size image

5.3 3D BSG

A 2D BSG [32] is revised to 3D BSG in [12] with some revision in terminologies. A room in 3D BSG is a cubic space in x, y, z directions. Any room in 3D BSG is denoted by its left-front-bottom corner (x, y, z), and edges connecting any two rooms share some units between them. Structure with ‘a’ rooms in x-direction, ‘b’ rooms in the y-direction, and c rooms in the z-direction is expressed as 3D-BSGa*b*c (Fig. 6).

Fig. 6
figure 6

Extension of 2D BSG to 3D BSG representation

Full size image

5.4 3D B*-Tree

A binary tree representation in the floorplan can be extended to 3D B*-Tree representation via applying B*-Tree representation in each tier of the floorplan. It means that the 2D B*-tree representation proposed by Chang et al. [33] is designed at each tier. Due to the layering of the floorplan in the 3D model, area and wirelengths are significantly reduced, which in turn reduces the adverse effects that arise due to long wirelength [14]. Figure 7 shows the binary representation in each tier with a total of two tiers.

Fig. 7
figure 7

A 2 tier with B*-Tree representation in each tier

Full size image

5.5 T-Tree Representation

T-Tree [5] representation is an extension of B*-Tree representation [33] in which there is one more dimension added. The children of T-Tree represent the geometric relationship with the parent node. As shown in Fig. 8, node ‘ni’ is the parent node, and node ‘nj’, ‘nk’, and ‘nl’ are the children of ‘ni’. In T-Tree representation, there is a maximum of three children. These three child nodes take either x, y, or z position in floorplan placement. In Fig. 8, node ‘nj’ (Being in left direction) takes the block in the x-direction of the parent node, ‘nk’ (Middle direction) places the block in the z-direction of the parent node, and ‘nl’ (Right direction) places the block in the y-direction of the parent node.

Fig. 8
figure 8

A T-Tree representation for 3D structure

Full size image

6 Results and Discussions

The implementation of the 3D floorplan in the floorplan part of the VLSI Design cycle is quite vast than the 2D floorplan since there are many research areas in which a researcher can work. It is clear from Table 2 that most of the research articles are using the simulated annealing method as an optimization technique [4, 6, 8–10, 20, 21]. A few have worked on genetic algorithms, as in [15]. Some literature has extended/revised 2D floorplan representation. Some has used 2D floorplan representations in various tiers to form 3D structure. The technique of dividing modules into different layers has also been incorporated [16]. The parameters range is quite vast, including the area (in layers), vias, volume, wirelength, timing, temperature, power consumption, etc. Researchers’ proposed work is checked on many types of benchmark circuits (Briefed in Sect. 4.3). Some have worked on some sample tests. Most researchers have implemented their algorithms in the C++ language. For reference, Table 6 shows the result comparison of 3D floorplan representation of some literature, in which parameters used are volume, dead space, and time, and results were checked on Beasley and Okp benchmark circuits. It has been found that with the passing years, results have improved, though there is continuous research going on to improve thermal distribution in the 3D floorplan technique.

Table 6 Result comparison of research articles that have used Beasley and Okp Benchmarks for their research. (Time in seconds and dead space is in percentage)
Full size table

7 Conclusion and Future Work

This article presents a comprehensive view of recent trends in 3D floorplan representation and techniques. The authors have explored a lot of research articles (including 2D floorplan), and only important and relevant 3D floorplan techniques and sources have been incorporated in this article. Various parameters, techniques, representations with benchmark circuits have been briefed. It can be deduced that compared to 2D floorplan techniques, 3D is quite vast and is less examined. Hence, much research work can be commenced due to higher opportunities for the researchers in this field.

It can be inferred from Table 2 that different optimization techniques have not been tested thoroughly on the new and revised 3D floorplan techniques, which were extensively used in 2D designs. Many research articles have tested their algorithms on some test samples and not on benchmark circuits. Researchers can verify and test the results on the standard benchmarks using existing and new optimization techniques. These algorithms can be tested within the blocks, layers, volume (as whole), area, volume (modules), temperature, wirelengths, vias, etc. Also, immense research is going on in cooling techniques of 3D floorplan techniques.