1

FuzzRoute: A Thermally Efficient Congestion-Free Global Routing
Method for Three-Dimensional Integrated Circuits
DEBASHRI ROY and PRASUN GHOSAL, Indian Institute of Engineering Science and Technology
SARAJU MOHANTY, University of North Texas

The high density of interconnects, closer proximity of modules, and routing phase are pivotal during thelayout of a performance-centric three-dimensional integrated circuit (3D IC). Heuristic-based approaches are
typically used to handle such NP-complete problems of global routing in 3D ICs. To overcome the inherent
limitations of deterministic approaches, a novel methodology for multi-objective global routing based on
fuzzy logic has been proposed in this article. The guiding information generated after the placement phase isused during routing with the help of a fuzzy expert system to achieve thermally efficient and congestion-freerouting. A complete global routing solution is designed based on the proposed algorithms and the results
are compared with selected fully established global routers, namely Labyrinth, FastRoute3.0, NTHU-R,
BoxRouter 2.0, FGR, NTHU-Route2.0, FastRoute4.0, NCTU-GR, MGR, and NCTU-GR2.0. Experiments
are performed over ISPD 1998 and 2008 benchmarks. The proposed router, called FuzzRoute, achievesbalanced superiority in terms of routability, runtime, and wirelength over others. The improvements onrouting time for Labyrinth, BoxRouter 2.0, and FGR are 91.81%, 86.87%, and 32.16%, respectively, for ISPD
1998 benchmarks. It may be noted that, though FastRoute3.0 achieves fastest runtime, it fails to generatecongestion-free solutions for all benchmarks, which is overcome by the proposed FuzzRoute of the current
article. It also shows wirelength improvements of 17.35%, 2.88%, 2.44%, 2.83%, and 2.10%, respectively,
over others for ISPD 1998 benchmarks. For ISPD 2008 benchmark circuits it also provides 2.5%, 2.6%, 1 %,1.1%, and 0.3% lesser wirelength and averagely runs 1.68×, 6.42×, 2.21×, 0.76×, and 1.54× faster than
NTHU-Route2.0, FastRoute4.0, NCTU-GR, MGR, and NCTU-GR2.0, respectively.
Categories and Subject Descriptors: B.7.2 [Integrated Circuits]: Design Aids—Placement and Routing
General Terms: Design, Algorithms, Performance, Experimentation
Additional Key Words and Phrases: VLSI layout design, global routing, fuzzy expert system, fuzzified global
routing
ACM Reference Format:
Debashri Roy, Prasun Ghosal, and Saraju Mohanty. 2015. FuzzRoute: A thermally efficient congestion-free
global routing method for three-dimensional integrated circuits. ACM Trans. Des. Autom. Electron. Syst.
21, 1, Article 1 (November 2015), 38 pages.
DOI: http://dx.doi.org/10.1145/2767127

1. INTRODUCTION

Nanoscale technology permits us to integrate systems with billions of transistors ona single chip. Layout design plays a pivotal role in the design cycle by transforming
the circuit description into geometric description. Recent researches on global routing
One initial work of this approach has been reported in IEEE Annual Symposium on VLSI, 2014 [Roy et al.
2014b].
Authors’ addresses: D. Roy and P. Ghosal (corresponding author), Department of Information Technology, Indian Institute of Engineering Science and Technology, P.O. Botanic Graden, Shalimar, Howrah, West Bengal
711103, India; email: prasung@gmail.com; S. Mohanty, Department of Computer Science and Engineering,
University of North Texas, 1155 Union Circle no. 311366, Denton, TX 76203-5017.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted
without fee provided that copies are not made or distributed for profit or commercial advantage and that
copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights forcomponents of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To
copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work inother works requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.
2015 Copyright is held by the Owner/Author. Publication rights licensed to ACM.
1084-4309/2015/11-ART01 $15.00
DOI: http://dx.doi.org/10.1145/2767127
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:2

D. Roy et al.

Fig. 1. 3D integration structure.

are aimed at optimization of different multi-objective functions related to performance and congestion, thermal issues, proper insertion of thermal vias [Goplen and
Sapatnekar 2005], sensitivity, wirelength, critical, paths or crosstalk [Minz et al. 2005],
etc. Consideration of the net ordering problem in OTC (over the cell) routing is a big
challenge to reach a polynomial-time solution. Some other metaheuristics, like Simulated Annealing- and Genetic Algorithm-based approaches, are also influencing modern trends. But, to the best of our knowledge, no existing complete fuzzified method for
global routing (proven to be an improved way out of the problems with deterministic
approaches) is reported for large-scale problems in global routing of three-dimensional
integrated circuits.
1.1. Global Routing: Trade-Offs and Challenges

Global routing plays a very important role in VLSI physical design to achieve a faster response from any integrated circuits. Approximate connection paths among the nodes of
any net are determined here that lead the global routing problem to be an NP-complete
one. An optimal connectivity for a circuit depends on several constrains imposed during the global routing step and thereby specifying a special performance feature ofthat IC.
Addition of a third dimension has allowed researchers to enrich performance of ICs ina better degree, but have made the problem of global routing more complex. Consideration of third dimension during routing decision-making is a witty and complex measure
to perform in every global routing algorithm. One basic structure of three-dimensional
global routing has been demonstrated pictorially in Figure 1.
1.2. Fuzzy Logic and FLC

Fuzzy logic is a form of multi-valued logic or probabilistic logic that deals with approximate reasoning rather than fixed and exact. In contrast to traditional crisp logic[True/False], they can have varying values that range in degree between 0 and 1.
Linguistic variables are the input or output variables of the system whose values arewords or sentences from a natural language instead of numerical values. A membership
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:3

Fig. 2. A fuzzy logic expert system.

Fig. 3. A fuzzy logic expert system.

function is used to quantify a linguistic term and in fuzzification and defuzzification
procedures.
A fuzzy logic control (FLC) system may be defined as the nonlinear mapping of an
input dataset to a scalar output data. An FLC consists of four main parts: (a) fuzzifier;(b) rules; (c) inference engine; and (d) defuzzifier. These components and the generalarchitecture of an FLC is shown in Figure 2.
The process of fuzzy logic is explained in Figure 3. First, a crisp set of input data aregathered and converted to a fuzzy set using fuzzy linguistic variables, fuzzy linguistic
terms, and membership functions. This step is known as fuzzification. Afterwards, aninference is made based on a set of rules. Lastly, the resulting fuzzy output is mapped
to a crisp output using the membership functions in a defuzzification step.
During the past decade, fuzzy logic control [Zadeh 1973] has been considered as oneof the most promising research areas in the application of industrial process control
to medical diagnosis and securities trading [Pedryz and Gomide 2007; Lughofer 2011].
The main idea behind FLC is to incorporate the expert experience of a human interface indesigning a controller. Several possible ways of FLC implementation are demonstrated
in Abonyi [2003] and Babuska [1998].
The rest of the article is organized as follows. Section 2 summarizes the novelties
of our proposed work, followed by Section 3 providing current state-of-the-art andmotivation behind this work. In Section 4, a formulation of the overall problem ispresented. Description of approaches for prerouting guiding information generation,
as well as the proposed fuzzy logic expert system are described in Section 5. The
proposed heuristic for three-dimensional routing is explained in Section 6. Next, theoverall proposed routing scheme is presented at a glimpse in Section 7. The proposed
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:4

D. Roy et al.

solution approach for fuzzified global routing for all the three categorized types ofnet (that may be considered as the backbone of this work) is covered in Section 8.
Experimental results, like a feasibility study for the global routing model and various
types of comparison studies for a complete fuzzified global router, are given in Section 9.
Section 10 concludes the article by giving important extensions and directions of ourinitiative.
2. NOVEL CONTRIBUTIONS OF THE CURRENT ARTICLE

A complete fuzzified global router is reported using the fuzzy logic concept for routing all
the nets in a netlist in this article. Novelties of this approach lie in many folds, including
providing the solution within a feasible time and with a better degree of reliability. A
standard cell-based design style is used for testing with benchmark circuits. However,the proposed method can easily be extended to mixed cell design also.
An efficient fuzzified expert system has been designed for thermal- and congestionaware global routing in routing space for a fully 3D IC structure. The concept of thermal
sensitivity is adapted from Ghosal et al. [2008]. This article corroborates the overallmodels and procedures of the proposed fuzzified global routing in three-dimensional
space. To the best of our knowledge, the proposed fuzzified approach for multi-pin
global routing in 3D ICs is the first of its kind. The novelties listed next provide an
overview of our contributions.
—Nondeterministic. This approach provides a way out of the alternative to standard
deterministic or heuristic-based approaches to overcome their inherent limitationsin handling complex design problems.
—P solution to NP. Our proposed approach ensures getting a polynomial-time solution
for this NP-complete problem. Time complexity analysis of the proposed algorithms
is reported in Section 9.7.
—Exhibiting feasibility. Depending upon the nature of the complexity and size of the
problem, it is validated as providing a feasible fuzzified global routing model between
a source and destination. The overall feasibility analysis with fuzzy expert system ispresented in Section 9.2.
—Dynamic and portable. It ensures consideration of the dynamic fuzzy expert system and making it portable for all circuits. The fuzzy expert system works dynamically by applying different boundary values for different fuzzy sets depending
upon the input benchmark circuit. Details are lucidly depicted in Sections 5.3 and5.6.
—Superiority. It gets better results with respect to time and reliability than the otherestablished global routers. Comparison with some of those is provided in Tables IV
and V in Section 9.5.
—Robust and extensible. It exhibits the robustness property by providing comparable
results with varying parameter values. Table II in Section 9.4 presents comparable
results for different sets of parameter values. Due to the property of fuzzy-logic-based
multi-objective optimization formulation used in this work, the proposed tool is also
open and extensible to greater numbers of constraints with the primary constraints,
namely thermal and congestion, used in this work. This may be easily achieved bysimply tweaking the formulation of the problem by incorporating other parameters.
—Adaptability. It exhibits a good adaptive property by one proposed obstacle avoidancemechanism. The scheme is described lucidly in Section 8.4.
—Completeness. A sequence of global routing paths is given in terms of subregions
generated for all two-pin and multi-pin intra- as well as inter-layer nets in a netlist.
Extensive analysis on recent ISPD’98 and ’08 benchmarks is presented in Section 9.3
as validation of the proposed technique.
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:5

3. STATE-OF-THE-ART AND MOTIVATION
3.1. Some Existing Global Routing Techniques

In high-performance VLSI circuits, the on-chip power densities play a dominant role,
due to the increased scaling of technology and increasing number of components, frequencies and bandwidths. Consumed power, usually converted into dissipated heat,affects the performance and reliability of a chip. Generation of hotspots is a critical issue in the VLSI physical design phase. Several works have been reported [Zhang et al.
2005, 2006; Ghosal et al. 2009, 2010a, 2010b, 2010c, 2010d] have experimented onthermal-aware placement and routing for 2D as well as 3D integrated circuits. Pathak
and Lim [2009] have presented a novel algorithm on 3D Steiner routing by an NLPbased approach for thermal-aware global routing in 3D stacked ICs. The complexity ofa Steiner-tree-based approach becomes very high with multi-net.
In Kastner et al. [2002], a concept of pattern routing was developed to guide subsequent maze routing. A global routing was proposed in Zhang et al. [2008], where afast maze routing was presented by introducing the virtual capacity concept. A historybased cost-function-driven multi-source and sink maze routing was proposed in Gao
et al. [2008], and negotiated congestion routing was proposed in Roy and Markov [2008].
The bounded maze routing concept was used in Dai et al. [2012] and Liu et al. [2013] for3D global routing to achieve significant wirelength and congestion on the most recent
benchmarks.
In the case of inter-die routing, one ILP-based technique has been introduced by
Chang et al. [2011]. Similarly, an integer-programming-based approach was proposedby Wu et al. [2009]. Their proposed approach optimizes wirelength and via cost without
going through a layer assignment phase. In Cho et al. [2009], 2D-to-3D mapping wasdone by a layer assignment powered by progressive via- or blockage-aware integer
linear programming. All these are global routing approaches in three-dimensional
space. In Das et al. [2003], authors designed some routing-and-placement-specific tools
for 3D ICs.
Among the different global routers reported so far, Chang et al. [2011] and Wu et al.
[2009] optimize wirelength and via cost without going through a layer assignment
phase, unlike Cho et al. [2009]. Several other global routers were proposed in Zhang
et al. [2008], Gao et al. [2008], and Roy and Markov [2008]. Recent global routing
benchmarks like ICCAD’09 [Moffitt 2009], ISPD’08 [Nam et al. 2008], and ISPD’11[Viswanathan et al. 2011] consider only the 3D situation for metal layers. A multipledevice layer, that is, a fully 3D strategy, has not been replicated in benchmark until now.
3.2. Thermal Issues: Its Impact and Modeling

Localized regions of high heat flux, called hotspots, are becoming significant withincreased scaling of process technology along with increase in total power dissipation.
The problem is quite severe in the case of three-dimensional integrated circuits, due tothe close proximity of neighboring modules. The temperature of hotspots is generally
above average die temperature. Uniformity of power dissipation is quite desirable toachieve certain optimized chip performance. In some recent works like Ghosal et al.
[2008, 2010c, 2010d]; authors have expressed their concern over this issue in achieving
an optimized thermal-aware placement in 3D ICs.
Thermal issues have always been an increasingly big concern throughout the layout
design of 3D ICs. Recent researches like Gupta et al. [2008] and Lu and Pan [2009]
show its present importance during routing. In Gupta et al. [2008], authors have proposed one thermal-aware global routing technique to reduce the probability of failureof chips due to interconnect failures by routing more wires in the colder regions of
the chip and less in the hotter regions. Then, a reliability-aware global routing with
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:6

D. Roy et al.

thermal considerations was reported in Lu and Pan [2009] to reduce the probabilityof interconnect failures by thermal-driven minimum spanning tree construction andthermal-driven maze routing. Some thermal-aware placement techniques and models
are also described later.
Voltage drop is another issue affecting the thermal profile of the chip, though it has
not been considered during the present formulation. As its impact is strongly correlatedwith thermal effects, it may be taken in account in future work.
3.3. Application-Specific Fuzzy Logic Implementation

Fuzzy systems have been attracting research for the past decade, due to their property
as an universal approximator [Wang 1992; Castro and Delgado 1996]. Application of
fuzzy logic is being implemented extensively in diverse fields like medicine [Kanthi
et al. 2013], frequency control [Sabahi et al. 2014], vehicle path planning [Huang et al.
2014], etc. Sait and Ali [1999] had proposed a fuzzy simulated evaluation algorithm forplacement. One source-destination-only fuzzified global routing model for VLSI layout
design has been reported in Roy and Ghosal [2013]. A 2-pin-only global router has also
been presented in Roy et al. [2014a]. But no such notable contribution has been found
to apply fuzzy logic in designing a complete global router for 3D ICs which is able
to route an entire netlist consisting of two/multi-pin intra/inter-layer nets as well as
critical nets.
3.4. Scope and Relevance of Present WorkIn the modern era, the design complexity of different problems is increasing in exponential order. Due to their very large problem size, such problems have seemed
unsolvable in feasible time, even by some heuristics. So, considering the decision only
in a deterministic way leads the complexity of the problem to NP-completeness. Global
routing has also been facing such problems recently. In our proposed approach, we have
tried to achieve a degree of reliability for each solution of global routing. Since fuzzy
systems have already been recognized as universal approximators used to formulate
our pioneering work. In the fuzzified approach, the search space is decreased for aparticular solution, and so is the time and design complexity. This is possible only for
global routing. Detailed routing is not applicable here as fine-tuning is necessary, andthis can only be done in a deterministic way.
As the presently proposed technique was not motivated by any subtle shortcomingof a particular established global router, our initial thrust was given to a feasibility
study of the proposed method and thereby identify and establish its applicability. The
total algorithm was preferred first for implementation over widely accepted benchmark
suites (ISPD’98 [Alpert 1998] and ISPD’08 [Nam et al. 2008]).
Here thermal optimization has been done during the placement phase by an efficient
thermal placer with certain necessary modifications introduced. Based upon the modeland depending upon the thermal influence of each module on the overall thermal profileof the entire layout area, the modules have been categorized in three different classes[Ghosal et al. 2008]. Thermal sensitivity of a module is defined as its effect on theoverall thermal scenario. When the circuit is in operation, that is, during the dynamic
scenario as the switching occurs, then, depending upon the nature of variation, thermal
sensitivity measures to what degree a module is responsible for changing the overall
thermal profile of the chip. Depending on the strength of effect, the modules are classified into three different classes of sensitivity. These three classes of modules, namely
strongly or highly sensitive, moderately sensitive, and weakly sensitive, obtained bythis thermal sensitivity analysis have been used in the next phase of layout, that is,routing as a guiding factor. By these means, an intelligent technique has been developed
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:7

Fig. 4. Geometric description of problem statement.

to route the nets while avoiding hotspots and thermally sensitive areas. Here, no “thermal via” or “thermal wire” insertion has been considered.
4. PROBLEM FORMULATION FOR FUZZIFIED GLOBAL ROUTER
4.1. Description of Problem

Let P = { p1 , p2 , p3 , . . . , pk} be a set of pins of a k-pin net distributed across L layers and
L be the number of layers available. Let M = {m1 , m2 , m3 , . . . , mr } be a set of modules
spread over the routing layer, where (xi , yi ) are the bottom-left coordinates of module
mi . The thermal sensitivity (SI) of a module is in the range of 0 to 1, and the congestion
ratio (CR) for each module is in the range of 0 to 1. Also, α, β are two cost factor
coefficients, where α + β = 1.
A weighted cost factor is generated from the thermal sensitivity and congestion ratio
information incorporated with the α and β values.
4.2. Geometric Description with Example

Standard cell-based design style has been used for the implementation. So, the totalrouting layer is represented as a grid structure. The routing layout is divided into
subregions, where each subregion is composed of certain grids. One subregion is themain routing unit here. In Figure 4, one net is shown on one device layer. Here,P = { p1 , p2 , p3 , p4 , p5 , p6 , p7 , p8 }. So, that multi-pin net is spread over eight modules,
darkened in that figure. The routing path needs to be determined for M depending on
α and β values and some constraints.
4.3. Definition and Formulation of Weighted Cost Factor

Thermal sensitivity and congestion are two considered constraints. The probability ofgetting selected as the next followed subregion is determined by the routing eligibility
for each subregion. The relationship between routing eligibility and the two constraints
is represented by a weighted cost factor, namely the. ineligibility factor (IF).
The ineligibility factor is inversely proportional to routing eligibility. Formulation of
IF may be represented as a standard minimization problem, as stated in (1).
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:8

D. Roy et al.

minimize IF = SI × α + CR × β
subject to α + β = 11 ≥ α, β ≥ 0
1 ≥ SI ≥ 0
1 ≥ CR ≥ 0.

(1)

4.4. Objective

The objective is to build a fuzzified global router that is able to route by determining
the routing region with minimum wirelength for the total netlist, depending upon theweighted cost function maintaining two constraints, namely thermal sensitivity andcongestion ratio for each net.
5. APPROACH FOR PREROUTING INFORMATION GENERATION

Our proposed routing procedure is a fuzzified approach to find one in-between solution of deterministic and heuristic-based approaches. Prior to the routing step, someprerouting information are generated that will help in subsequent routing steps. One
main purpose of these globally routed paths will be to avoid the more heated and congested portion of the layout. This constraint-based approach takes the decision during
the routing procedure from some prerouting guiding information. This guiding information is generated from a proposed fuzzy expert system and rule base. Every fuzzy
expert system has two parts: (a) premise, that is, the input part; and (b) consequent,that is, the output part. Different definitions and assignments of fuzzy terms and theguiding information generation procedure are described next.
5.1. Linguistic Variables: Thermal Sensitivity and Congestion Ratio

Unlike numerical variables that take numerical values, linguistic variables take linguistic values. In any fuzzy-based logic, recognizing proper linguistic variables plays
an important role. In this fuzzified global routing procedure, thermal sensitivity andcongestion ratio are the two linguistic variables in the premise part. Ineligibility factor(IF) is the only linguistic variable in the consequent part. Here, the linguistic values
to be taken are: (a) high; (b) moderate; and (c) weak for the premise part.
5.2. Fuzzification of Thermal Sensitivity, Congestion Ratio and Ineligibility Factor

In the fuzzy logic concept, linguistic variables vary within [0,1]. Here, all derived fuzzy
sets from three linguistic variables in both the premise and consequent part are shownin Figure 5.
In the consequent part, a total 9 fuzzy sets are present. Only one rule base is sufficientfor this purpose. For the rule base, there are total of 9, that is, all possible fuzzy sets(i th I, where i = 1 . . . 9), for this particular linguistic variable.
5.3. Grade of Membership Function

The membership function is the characteristic function for fuzzy sets. In this proposed
global routing procedure, an overlapping trapezoidal nature is best suited because
moderately sensitive information with a higher grade of membership value may also
be considered as a highly sensitive information with a lesser grade of membershipvalue. A Gaussian function is not well fitted here because of its different response ateach point and only one maximum response. But, our problem specification is that of
having a particular response over a range.
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:9

Fig. 5. Derived fuzzy sets from linguistic variables.

Fig. 6. The graph corresponding to the grade of membership values for sensitivity and congestion ratio.

The grade of membership values (shows in Figure 6) for three fuzzy sets corresponding to a linguistic variable of the premise part will be found according to Eqs. (2), (3),and (4).
μch = 0f or x < l3
=1
f or l4 ≤ x ≤ 1= (x − l3 )/(l4 − l3 ) f or l3 < x < l4 .
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

(2)

1:10

D. Roy et al.

Fig. 7. Graphic representation of guiding information generation.

μcm = 0=1
= (x − l1 )/(l2 − l1 )= (l4 − x)/(l4 − l3 )μcw = 0=1
= (l2 − x)/(l2 − l1 )f or x < l1 & x > l4
f or l2 ≤ x ≤ l3
f or l1 < x < l2
f or l3 < x < l4 .

(3)f or x > l2
f or 0 ≤ x ≤ l1
f or l1 < x < l2 .

(4)

The different boundary values l1 , l2 , l3 , l4 in Eqs. (2)–(4) are dynamic for the premisepart and generated in the guiding information generation algorithm. The step-by-stepprocedure for determining l1 , l2 , l3 , l4 for thermal sensitivity and congestion informationis stated in Section 5.4.1. Similarly, for the consequent part, a total of nine trapezoids
are in [0,1] range and the boundary values of each are also dynamically generated
depending upon the proposed rule base (described later).
5.4. Guiding Information Generation

The fuzzified global routing approach bifurcates in guiding information generationand in the main routing procedure. The first part corresponds to generation of relevant
information regarding a specific unit of layout, called the subregion, and generatinga fuzzy expert system. The overall procedure of guiding information generation ispresented in Figure 7.
This part is executed immediately after the placement phase for each layer separately. The procedure works here as guided routing which will be further fed to thefuzzy expert system to take a decision during global routing between a source and destination. In Algorithm 1, the procedure Generate Guiding Info() generates the guiding
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:11

ALGORITHM 1: Guiding information generation for global router.
Generate Guiding Info( )Input : S = Set of sensitivity information for each module,
P = Total placement information,
O = Obstacle information,
V = Parameter values,
L = Layer number
Output: GI = Generated guiding information
begin
Layerwise Place Info(); /* Particular placement information for L layer from P */Num T er = Total Terminals(P); /* Calculating number of terminals for layer L */Get Subregion Information(P);SRN = Total Subregion(L); /* Number of subregions in layer L */for i ≤ SRN do
AC = Area Covered(O); /* Calculating total area covered by obstacles for i th subregion oflayer L */WSn = Weighted Sensitivity(O, S); /* Calculating weighted sensitivity for each subrefori th subregion of layer L*/
AC
;
CR =
Total Area()
WSn
SR =
;
T otal Area()
IF = SR × V → α + CR × V → β;
Add to GuidingInfo(); /* Add C R, SR and IF to GI */end
Get GuidingInfo(); /* Add mean and variance of CR and SR to GI for all subregions*/
end

information as mentioned. This algorithm is called from the Generate Routing Path()with a particular layer number. During execution of this algorithm, the total layout
is divided into a number of subregions for that particular layer. The grid size of thelayout is scalable and can be controlled by the user. Then, for each subregion, a normalized weighted average sensitivity ratio and normalized congestion ratio are generated.
Mean and variance for all subregions are used to determine the boundary values ofmembership functions for the corresponding fuzzy sets.
The boundary values of highly sensitive (HS), moderately sensitive (MS), weakly
sensitive (WS), highly congested (HC), moderately congested (MC), and weakly congested(WC) are determined during guiding information generation, as described next.
5.4.1. Description of the Algorithm. Due to the standard cell structure, the implementation of this algorithm is quite simple. The congestion estimation and total area
estimation for each subregion may be calculated easily from obstacle information (O)and placement information (P) for that specific layer. After the layer-wise placement
information is obtained, the area covered by obstacles (AC) and the weighted sensitivity (W Sn) are calculated. Congestion and sensitivity ratio (CR and SR) information are
also determined for each subregion.

Classification of sensitivity information. The mean(s ) and variance (vs ) of thermal
sensitivity for that particular layer are determined by Eqs. (5) and (6), where N = the
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:12

D. Roy et al.

total number of subregions and sr = average sensitivity information of the r th
subregion.
1 (sr ).
N(5)

1 (sr − s )2 .
N

(6)

N

s =

r=1
N

vs =

r=1

√
The standard deviation for thermal sensitivity of the total region is (ds ) = vs . Hence,r th subregion will be recognised as highly sensitive (HS), moderately sensitive (MS), or
weakly sensitive (WS). The boundary values are found according to Eqs. (2) and (3),and (4) are stated follows.
3ds
2
ds

(2) l2 = s −2ds(3) l3 = s +23ds(4) l4 = s +2(1) l1 = s −Now the classifications for each subregion according to thermal sensitivity would be
as follows.
3ds, the subregion is HS2
3ds(2) s + ds < sr < s +, the subregion is HS with higher grade of membership and2
MS with lower grade of membershipds< sr < s + ds , the subregion is MS with higher grade of membership and HS(3) s +2
with lower grade of membershipds
ds< sr ≤ s + , the subregion is MS(4) s −22ds(5) s − ds < sr < s − , the subregion is MS with higher grade of membership and2
WS with lower grade of membership
3ds(6) s −< sr < s − ds , the subregion is WS with higher grade of membership and2
MS with lower grade of membership3ds, the subregion is WS(7) 0 < sr ≤ s −2(1) sr ≥ s +So, coarsely, the classification can be presented as follows.
(1) sr ≥ s + ds , the subregion is HS(2) s − ds < sr < s + ds , the subregion is MS(3) 0 < sr ≤ s − ds , the subregion is WS
Classification of congestion ratio information. Consequently, the mean(o ) andvariance(vo ) of congestion ratio information are stated in Eqs.(7) and (8), where N = the
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:13

total number of subregions and or = the average congestion information of the r th
subregion.
1 (or ).
N(7)

1 (or − o )2 .
N

(8)

N

o =

r=1
N

vo =

r=1

deviation for congestion information of the total region(do ) =√ Similarly, the standard
vo . Hence the r th subregion will be recognized as highly congested (HC), or moderately
congested (MC), or weakly congested (WC). Here also, the boundary values are according
to Eqs. (2)–(4) and would be as follows.
3do
.
2
do
(2) l2 = o − .
2do(3) l3 = o + .
2
3do(4) l4 = o +.
2(1) l1 = o −Now the classifications for each subregion according to congestion ratio information
are as follows.
3do, the subregion is HC.
23do(2) o + do < or < o +, the subregion is HC with higher grade of membership and2
MC with lower grade of membership.
do< or < o + do , the subregion is MC with higher grade of membership and(3) o +2
HC with lower grade of membership.
dodo< or ≤ o + , the subregion is MC.
(4) o −22do(5) o − do < or < o − , the subregion is MC with higher grade of membership and2
WC with lower grade of membership.
3do(6) o −< or < o − do , the subregion is WC with higher grade of membership and2
MC with lower grade of membership.
3do(7) 0 < or ≤ o −, the subregion is WC.
2(1) or ≥ o +Here, coarse classification will be as follows.
(1) or ≥ o + do , the subregion is HC.
(2) o − do < or < o + do , the subregion is MC.
(3) 0 < or ≤ o − do , the subregion is WC.
So, before routing is started, prior information is generated related to each subregion
that guides the global routing procedure further. And the total guiding information is
dynamic in nature, that is, the specified boundary values are determined during the
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:14

D. Roy et al.

execution of the routing procedure. Different dynamic fuzzy sets with different boundary values may be produced per layer present in the three- dimensional placement.
5.5. Proposed Rule BaseA rule base is an important factor during constructing a fuzzy expert system to define
behavior of the system. There exist several rule models for this purpose. A TS model
is computationally efficient and works well in optimization and adaptive techniques.
The consequent part of the rules are not fuzzy, so less intuitive. The Mamdani model
is computationally less efficient, but intuitive and well suited for human input. So, it
has widespread acceptance. In the expert system this model is used to generate a rulebase for total fuzzification of the process. The ineligibility weight factor is determinedby a mathematical function. So, a conversation between the mathematical function to
fuzzy sets is required.
Here, the TS model rule structure is IF sr is Aj and or is Bk THEN z = f (.). The
representation of mathematical function f (.) follows Eq. (9), where α + β = 1.
f (.) =

(α × sr + β × or ).
(α + β)(9)The ineligibility weight factor (μr ) of the consequent part depends upon the sensitivity ratio (sr ) and congestion ratio (or ). The formula for stating the corresponding weightfactor is formulated in Eq. (10).
μr = f (α, sr , β, or ) =(α × sr + β × or ).
(α + β)(10)Here α + β = 1. The preferable values for α, β are determined according to the requirement of the objective function. Definition of the fuzzy set for each rule in theconsequent part is generated by putting the lower and upper limits for each fuzzy setof the premise part in the preceding function to determine the lower and upper limits,
respectively. In this way the proposed rule base can be represented according to the
Mamdani model. The proposed rule base consists of 9 rules with 9 fuzzy sets corresponding to a linguistic variable of the consequent part and 6 fuzzy sets corresponding
to two linguistic variables of the premise part. The rule base considers all possible
rules with all fuzzy sets of the premise part. The procedure of converting the TS modelto the Mamdani is represented in Figure 8 and Eq. (11) for better understanding. The
membership function’s characteristics of trapezoidal fuzzy sets in the consequent partfor the rule base are shown in Figure 9. The proposed rule base is stated in Table I.
a1 × α + a2 × β,α+βb1 × α + b2 × βb=,α+βc1 × α + c2 × β,c=α+βd1 × α + d2 × β
d=
.
α+β

a=

(11)

5.6. Proposed Fuzzy Expert System

In Algorithm 2, the Fuzzy Expert System() procedure constructs different fuzzy expert
systems for different layers with same proposed rule base but different membershipfunctions. Here, fuzzy sets for the antecedent or premise part and consequent part
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

Fig. 8. Conversion procedure from TS model to Mamdani model.

Fig. 9. Plotted membership functions of 9 fuzzy sets of the consequent part in the rule base.
Table I. The Proposed Original Rule Basefor Inter-Layer Net Routing
1.
2.
3.
4.
5.
6.
7.
8.
9.

If sr is HS and or is HC then μr is 1st I
If sr is HS and or is MC then μr is 2th I
If sr is HS and or is WC then μr is 3th I
If sr is MS and or is HC then μr is 4th I
If sr is MS and or is MC then μr is 5th I
If sr is MS and or is WC then μr is 6th I
If sr is WS and or is HC then μr is 7th I
If sr is WS and or is MC then μr is 8th I
If sr is WS and or is WC then μr is 9th I

ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:15

1:16

D. Roy et al.

Fig. 10. Modeling of fuzzy expert system for three-dimensional structure.

ALGORITHM 2: Modeling the fuzzy expert system.
Fuzzy Expert System( )Input: GI = Information of premise and consequent part)begin
Mem Fun Premise(); /* Build membership functions for premise part from GI */Mem Fun Consequent(); /* Build membership functions for consequent part from GI */Gen Rule Base(); Build a rule base with 9 rules */end

are obtained from the generated guiding information. This fuzzy expert system produces a crisp output for the consequent part, depending upon the inserted values in
the antecedent part and parameter values. Here the proposed fuzzy expert system
works dynamically by considering different boundary values for different fuzzy sets fordifferent circuits. The total fuzzifcation and defuzzification are done inside the expert
system according to the membership function and the proposed rule base. The block
diagram of the proposed expert system is presented in Figure 10.
6. PROPOSED 3D PLACEMENT TECHNIQUE
6.1. Thermal-Aware Modeling

Thermal effects have prominent impact on performance and reliability of a chip. Dueto closer proximity of the modules in a 3D multilayered structure, 3D ICs are significantly dependent on thermal parameters, that is, power dissipation issues. In theirrelevant work, Tsai and Kang [2000] have successfully addressed this issue in the caseof standard cell placement and have come up with an efficient placement techniqueto reduce hotspots (generated by high heat flux in localized regions) during placement
without compromising traditional design metrics, such as area and wirelength. Moreover, in their paper they have first successfully pointed out that it is the power density(and not the power dissipation) that may be treated as the most effective measurement
parameter to account for thermal effects.
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:17

6.1.1. Analytical Die Temperature Model. As power density of the modules is a very effective parameter [Tsai and Kang 2000] in thermal profiling of a placed layer compared to
power dissipation by the module itself, it was really necessary to figure out a directly
measurable parameter that can be taken as a measure of this effect and originates asa direct after-effect of this issue. In another pioneering work, Im and Banerjee [2000]
have successfully modeled this thermal effect and have shown that the die temperature
is solely dependent upon the power density and that the change in this temperature
is linearly dependent on this. Therefore, the change in die temperature may be considered as a directly measurable parameter to characterize the thermal profile of thedie.
A simple analytical model has been proposed to estimate the change in temperaturein each active layer of 3D chips. The temperature rise (above the ambient temperature)of the j th active layer in an n-layer 3D chip may be expressed asj   n
 Pk 
Ri.
(12)
T j =A
k=i
i=1

where n is the total number of active layers, Ri represents thermal resistance between
the i th and (i − 1)th layers, and Pk is the power dissipation in the kth layer. Assuming
identical power dissipation (P) in each layer and identical thermal resistance (R)between layers, the temperature rise of the uppermost (nth) layer in an n-layer 3Dchip can be expressed as
 
 

R 2
P
R
n + R1 −
n .
(13)
Tn =
A
2
2
where R1 is mostly due to the package thermal resistance between the first layer andthe heat sink and R is the thermal resistance between the i th and the (i − 1)th layers,respectively.
6.1.2. Dynamic Thermal Modeling. In the proposed thermal arrangement during placement, the non-uniformity of thermal conditions of modules was modeled in terms of
the intrinsic parameter of placement, called T hermalBound, reported in Ghosal et al.
[2009]. The probabilistic switching of modules is considered to satisfy a Poisson distribution [Press et al. 2001]. Hotspots are generally workload dependent and theirduration may vary with switching activity of the circuits. The Poisson distribution
counts the number of discrete occurrences of an event during a specified time interval.
In Ghosal et al. [2009], switching of a module is considered as an occurrence of an event
where λ denotes the average number of switchings for a set of logic modules. Therefore
the probability of a module switching exactly k times is given bye−λ × λk.
(14)k!
where k is a nonnegative integer. It is clear that ξ accounts for the number of switchingsof the corresponding module and lies between [0,1]. The actual number of times amodule switches for average values λ is given by ξ (k, λ)×k. In absence of any probabilityof switching, a module will switch exactly k times in a period of k cycles.
ξ (k, λ) =6.2. Proposed Algorithm

To date design solutions for implementing a pure 3D integrated circuit, are still not
readily available. Available benchmarks in 3D also come with multiple metal layers
only in spite of multiple device layers. Due to this unavailability, some 2D-to-3D placer
tools have been used to study the feasibility of the proposed approach. The output of one
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:18

D. Roy et al.

ALGORITHM 3: Generation of full 3D placed circuits from standard benchmark circuits.
Modified 3D Placement( )Input : N = Number of cells to be placed,
L = Number of layers available,
Ar = Aspect ratio of the chip,
St = sub-matrix order,
It = Maximum iteration limit
Output: Thermally optimized 3D placement
begin
Generate 3D(); /* Generate 3D matrix of minimum dimension satisfying constraints */Allocate 3D(); /* Allocate cells with corresponding power density values */while optimization possible = yes dofor layer number = 1 to L do
Layer Therm Opt(); /* Layer wise thermal optimization */end
Inter Layer Therm Opt(); /* Thermal optimization across all the layers */if optimized = no thenFind Layers(); /* Determine the layers where 2D optimization is necessary */else
Stretch Layers(); /* Stretching routing regions in each layers to eliminate
overlapping in cells */
end
end
end

efficient thermal-aware 3D placer, reported in Ghosal et al. [2010b, 2010c], has beenused in the present work with some necessary and suitable modification. An intelligent
heuristic has been proposed for this placement migration. In this proposed approach,an efficient overlap elimination technique has been introduced as a post-placement
procedure to optimize and improve the placement results. Pseudocode of the proposed
placement algorithm has been presented in Algorithm 3.
7. PROPOSED SCHEME FOR GLOBAL ROUTINGThe overall flow of the proposed fuzzified global routing tool for 3D ICs may be represented as in the flowchart in Figure 11. This fuzzified routing technique proceeds bydesigning a fuzzy logic expert system for generating guiding information that helps indecision-making during the actual global routing phase. The placed region of an individual layer is divided into subregions. The proposed heuristic is based on a sensitivity
information value for each node (that signifies the thermal response) and congestion
information to specify the congestion-driven technique for routing.
For each subregion, the crisp values of sensitivity and congestion information aretransformed in two fuzzy sets. These are used to generate a crisp output by passing
through a rule-base-based on the Mamdani model and by the defuzzification method.
Thus the total fuzzy expert system works for generating the guiding ineligiility factor
generation for each subregion. During decision-making of the routing procedure, thesubregion with minimum ineligibility factor is favoured.
Our proposed routing procedure does not allow detours and the global routing paths
are generated in units of subregions. The unroutable nets will again start from theguiding information generation step during the rip-up-and-reroute procedure. Specific
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:19

Fig. 11. Overall flow of the proposed fuzzified global router for 3D ICs.

geometric paths are generated during detailed routing. Another aspect of the proposed
global routing is that if one subregion is selected during routing of a particular net,
then that specific subregion will never be retraced again for the same net. After routing
one net, the ineligibility factor gets increased by a factor for the subregions which the
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:20

D. Roy et al.

ALGORITHM 4: Global routing path generation for fuzzified router.
Intra Layer Routing( )Input : Src = Source Coordinate,
D = Destination Coordinate,
GI = Guiding Information,
V = Parameter value
Output: Favoured subregions(Subregion)
begin
MDSrc = MD(Src, D); /* Manhattan distance between Src and D containing subregions */MD = MDSrc;
PSrc = Src; /* Setting a pivot subregion */ Fuzzy Expert System (GI);
while MD > 0 do
Explore Neighbour(); /* Explore four neighbors around pivot subregion */NInfo = Get Info(); /* Sensitivity, congestion information of each neighbors */IF = Defuzz(); /* Defuzzified value by centroid method using rule base */if Nbour Not Visited() then/* Check whether a neighbor is visited or not */PSrc = Select Neighbour(); /* Select neighbor with min IF and set as new pivot */end
MD = MD(PSrc, D);
end
endrouted path has gone through, and either vertical or horizontal capacity gets decreased
for that subregion.
Different nets of a particular netlist are processed sequentially for the sake of easy
implementation. One prerouted net will contribute to increasing congestion ratio information in this sequential order of global routing.
(1) Two-pin intra-layer nets. Here connections are made in a normal fuzzified way
according to Algorithm 4.
(2) Two-pin inter-layer nets. Multilayered two-pin connections are made by inserting
pseudo-terminal points.
—First, the backbone tree construction goes across multiple layers that specify thepseudo-terminals for each layer and inject vias for inter-layer communication.
Determination of pseudo-terminals is based on the sensitivity and congestion
ratios of the subregions containing the source and destination terminal.
—The second step consists of connecting the pseudo-terminal points to the source aswell as the destination containing subregions in that particular layer by two-pin
intra-layer net connection in a fuzzified way, according to Algorithm 4.
(3) Multi-pin nets. Multilayered or single-layered Steiner tree construction is done byinsertion of a pseudo-terminal. The three steps are as follows.
—First, numbers of clusters are generated by an automatic cluster determination
technique [Bandyopadhyay 2005] (required for larger nets) by a simulated annealing method. The centers of clusters act as Steiner points during generation of
intra-cluster Steiner trees for each layer. Connection between the cluster centerand each terminal is done by Algorithm 4.
—Second, the backbone tree construction is done across multiple layers that specify
the pseudo-terminals for each layer and inject vias for inter-layer communication.
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:21

Fig. 12. The proposed thermally efficient congestion-free global routing approach for 3D ICs.

Determination of pseudo-terminals is based on the sensitivity and congestion
ratios of the subregions. One obstacle avoidance heuristic is used here during
insertion of inter-layer vias.
—The third step connects each cluster center or single terminal with the backbone
tree, that is, the pseudo-terminal points in that particular layer by two-pin net
connection in a fuzzified way, as stated in Algorithm 4.
The detailed working principle of the total procedure is described later. One obstacle
avoidance heuristic is used here during insertion of inter-layer vias.
8. PROPOSED FUZZIFIED APPROACH FOR GLOBAL ROUTINGThe proposed procedure Generate Routing Path() generates a total routing path for
all nets in terms of subregions for a netlist of a circuit in Algorithm 5. It takes theoutput of Algorithm 3 for a circuit as its input and produces a global routing path as
output for the netlist of the same circuit. At the start of Algorithm 5, the generation ofsubregion information, guiding information, and building of the fuzzy expert system isdone through two procedures, Generate Guiding Info() and Fuzzy Expert System(), perlayer. Then it heads towards the routing procedure. The proposed algorithm recognises
several types of nets and performs the global routing accordingly. The functional-level
block diagram for the total router is presented in Figure 12.
8.1. Two-Pin Intra-Layer Net Routing

In Algorithm 5, the procedure Generate Routing Path() first recognises all twopin intra-layer nets and performs global routing in a fuzzified way as stated in
Algorithm 4. Here, the Intra Layer Routing() procedure generates the favoured subregions for connections between two pins. During the decision-making of selection of thenext favoured subregion, one subregion is never reselected for the same net routing.
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:22

D. Roy et al.

ALGORITHM 5: Algorithm for generation of routing path for a netlist.
Generate Routing Path( )Input : S = Set of sensitivity information for each module,
P = The total placement information,
N = Netlist,
V = Parameter values
Output: Routing path in terms of favoured subregions
begin
L = No of Layers(P);for layer number = 1 to L do
Generate Guiding Info(S, P, V ); /* Guiding information generation for all layers */Fuzzy Expert System(); /* Build distinct fuzzy expert systems for all layers */end
for net ∈ N do
if intra layer two pin net thenIntra Layer Routing(); /* Generate routing path from source to destination */else if inter layer two pin net then
Backbone Tree(); /* Determine pseudo terminal positions by constructing backbone
tree */
Pseudo Terminal Insertion(); /* Insertion of pseudo terminals and via */Connect All Pins(); /* Connecting source and destination pins to the pseudoterminal points */else/* For multi-pin intra and inter layer nets */Automatic Cluster Generation(); /*Generate Automatic number of clusters withmultiple pins for all layers */Backbone Tree(); /* Determine pseudo terminal positions by constructing backbone
tree */
Pseudo Terminal Insertion(); /* Insertion of pseudo terminals and via */Connect All Pins(); /* Connecting all pins of a net to the pseudo terminal points */
end
end
end

When the destination is a set of terminals, then this algorithm finds a favoured
path for each terminal belonging to the destination set from the specific source. Heredecision-making is done using the generated fuzzy expert system depending upon
different layers. One scenario of two-pin intra-layer net routing is shown pictorially in
Figure 13.
8.2. Two-Pin Inter-Layer Net Routing

Next, all two-pin inter-layer nets are sorted out in Algorithm 5. To route all thoserecognised nets, two steps are followed.
8.2.1. Backbone Tree Construction and Determination of Pseudo-Terminal. The backbone tree
performs inter-layer connection during connection between two intra-layer pins. The
backbone tree generation process is done by the Backbone Tree() function in Algorithm 5. Inter-layer vias are the technology to build a backbone tree here. A via insertion procedure can be done in two ways, as shown in Figure 14. The position of a
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:23

Fig. 13. A scenario of source-to-target intra-layer global routing.

Fig. 14. Insertion of pseudo-terminal during inter-layer two-pin net routing: (a) normal approach; (b) proposed approach.

via insertion point should be inclined to the direction of a more sensitive or congested
terminal.
In the figure, the normal approach shows a general method of the via insertion
strategy during connection between an inter-layer source and destination. But thesignificance of our proposed approach lies in providing the more sensitive and congested
terminal, giving a closer path for heat dissipation (through the via) while still giving
less sensitive and congested ones some favour.
One example case may be taken, as shown in Figure 14, where the main priority is given to the highly sensitive terminal by placing the via position near to it inboth approaches. But in the proposed approach, the moderately sensitive terminal
also gets some extend of favour, which is not given in the normal approach. So, here
in the proposed technique, as a backbone tree determination strategy, the combined
sensitivity-congestion information for two terminals is used as stated in Eqs. (15)–(17).
scrl =

srl × α + crl × β
.
α+β

(15)

The average weight (scrl ) for the r th subregion in the lth layer is determined in Eq. (15)where α, β are the two constraints provided by the user specification, and srl and crl
are the sensitivity and congestion information of the r th subregion residing on the lth
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:24

D. Roy et al.

layer. The x-coordinate (xb) of the backbone for all layers for a particular two-pin net isdetermined in Eq. (16) and the y-coordinate(yb) of the same is determined in Eq. (17).
Here, srci is the subregion containing the source terminal residing on the i th layer anddest j is same for the destination terminal residing on the j th layer. The scsi and scdj
are the average weight for the source- and destination-containing subregions. Thenthe backbone may be drawn through the (xb, yb) point intersecting all the layers in
between.
srci → x × scsi + dest j → x × scdj
.
(16)
xb =
scsi + scdj
yb =srci → y × scsi + dest j → y × scdj.
scsi + scdj

(17)

Next, the final positions of pseudo-terminals are determined. In one layer, if there isno obstacle in the (xb, yb) point, that point works as a pseudo-terminal and participatesin routing of that layer and one electrical via is inserted into that point according to
the function Pseudo Teminal Insertion(). But if the point(xb, yb) falls on any obstacle
in any layer, then one obstacle avoidance strategy has been introduced that considers
weight factor information as the impacting factor during its avoidance technique.
8.2.2. Connecting Source and Destination to Backbone Tree. Connection between source anddestination with the pseudo-terminals caused by the insertion of the backbone tree isdone by the Fuzzified Intra Layer Routing() procedure again. In the Connect All Pins()
procedure, all routed subregion information is generated and returned to the user.
8.3. Multi-Terminal Net Routing

Lastly, the multi-terminal nets are recognized in Algorithm 5. The intra- and interlayer multi-pin nets are handled in quite a similar approach during execution of therouting procedure. Multi-pin inter-layer nets may be considered as a generalizationof multi-pin intra-layer nets with a single layer. So, the solution approach also takes
this generalization concept. The three steps defined next are called repeatedly for each
multi-pin net having inter- or intra-layer connection (for intra-layer nets, the layer
number will be one).
8.3.1. Automatic Cluster Determination and Connection within Clusters. This step is mainly
required to process a large net to a smaller one, that is, by making clusters of terminals
with nearer proximity give the larger net a smaller look.
As the total procedure is fuzzified and aimed at escaping the bound of the deterministic approach, here one fuzzy clustering approach was used. For better degree of
reliability, the automatic number of fuzzy cluster determination technique using simulated annealing, proposed in Bandyopadhyay [2005], has been selected. The center ofthe generated cluster works as pseudo-terminal for that layout and can be used further
for routing.
Now, for each terminal(t) of the lth layer, the corresponding home subregion(r) andits combined sensitivity-congestion ratio (scrl ) from generated guiding information aredetermined. The combined value is determined according to Eq. (15), where α and βcome from parameter values (V ). For a typical implementation, the selected values
may be α as 0.4 and β as 0.6 for congestion-aware routing, and α as 0.6 and β as 0.4 forthermal-aware routing.
The distance measure between two terminals is the Manhattan distance (MD) measurement in terms of subregions. Here automatically determined clusters may be ofdifferent sizes. Suppose that for the lth layer the automatically determined number ofclusters is Nl and the vertex of the i th cluster in the lth layer is vil , where i ∈ {1...Nl }.
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:25

Now, for each cluster, the Intra Layer Routing() procedure is called that connects all
the terminals of the cluster with the center vertex of the cluster.
For a large net also, the number of clusters is generally small. So, the number of
inserted pseudo-terminals does not affect the cost significantly. Total automatic cluster
determination and a connection within the clusters procedure is abstracted within the
Automatic Cluster Generation() function in Algorithm 5.
8.3.2. Backbone Tree Construction and Determination of Pseudo-Terminals. Construction of
backbone trees is mandatory for inter-layer via connections. In connecting points, vias
are inserted in a particular layer whose position depends upon the behaviour of thegenerated cluster or terminals. The position of a via insertion point should be inclined
to the direction of larger and more sensitive or congested clusters or terminals.
So, the backbone tree determination strategy combines both sensitivity-congestion
information for each cluster or terminal and the size of the clusters (stated in Eqs. (18)–(20)).
In Eq. (18), the total summation of sc for each cluster is determined, where cil → i thcluster in the lth layer.
scil =
scrl .
(18)∀r∈i

The x-coordinate (xb) of the backbone for all layers for a particular net is determinedin Eq. (19) and the y-coordinate(yb) in Eq. (20). Here vxil → x-coordinate of the center ofcluster i in the lth layer, N → total layer number and Nl → automatically determinedcluster number in the lth layer and vyil → y-coordinate of the center of cluster i in thelth layer. Then the backbone may be drawn through an (xb,yb) point intersecting all thelayerss. Eqs. (19) and (20) are generalized from Eqs. (16) and(17).
 N  Nll=1
i=1 (scil × vxil )
xb =
.
(19)
 N  Nl
sc
il
l=1
i=1
 N  Nl(sc
il × vyil )
l=1
i=1
yb =
.
(20)
 N  Nll=1
i=1 scil
The earlier described backbone tree construction procedure is done in the Backbone Tree() procedure. Here, determination of the final position of the pseudo-terminals
stage is done layer-wise. In one layer, if there is no obstacle in the (xb, yb) point, thenthat point works as a pseudo-terminal. That pseudo-terminal also participates in routing of that layer and one electrical via is inserted into that point according to function
Pseudo Teminal Insertion().
But if the point (xb, yb) falls on any obstacle in any layer, then one obstacle avoidance
strategy is used that also considers the cluster size and combined sensitivity-congestion
ratio information as the impacting factor during its avoidance technique. The avoidance
scheme is described later. One example case is shown pictorially in Figure 15 for better
understanding. In this figure, it is clear that the insertion point of the pseudo-terminal
is inclined to more congested and more sensitive terminals to be connected to minimize
heat dissipation as well as wirelength.
8.3.3. Connecting Clusters to Backbone Tree. Connection between each cluster centerwith the pseudo-terminal caused by the insertion of the backbone tree is done in a
Connect All Pin() procedure that calls the Intra Layer Routing() procedure internally.
Ultimately, in Algorithm 5 the Generate Routing Path() procedure will return
favoured subregions as a global routing path.
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:26

D. Roy et al.

Fig. 15. Insertion of pseudo-terminal and backbone tree construction during multi-terminal inter-layer net
routing.

8.4. Obstacle Avoidance Scheme during Determination of Pseudo-Terminal

The position of a pseudo-terminal, after avoiding an obstacle, depends upon the total
weight factor of clusters falling on four possible sides of obstacles. Here, the position of
the pseudo-terminal is skewed toward more congested, sensitive, and large clusters, sothat congestion does not further increase to that side.
By injecting the pseudo-terminal, a vertical via position is actually inserted to help
the electrical signal to pass quickly from the more sensitive and congested regions toother layers that may be favourable for routing. One example of a determination of apseudo-terminal in an obstacle avoidance scheme is shown in Figure 16. The scheme
is stated next.
(1) The weight factor related to cluster size and combined sensitivity-congestion ratio
for the i th cluster in the lth layer is wil as stated in Eq. (21), where nil = numberof terminals in the i th cluster in the lth layer and scikl = the average sensitivitycongestion ratio of the corresponding subregion where the kth terminal belongs in
the i th cluster in the lth layer.
nil
scikl .
(21)
wil = nil ×
k=1(2) Next, suppose the bottom-left corner of the obstacle is (xo ,yo ) and length and widthof the obstacle is ho and wo , respectively. The coordinates of the four corner points
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:27

Fig. 16. Insertion of pseudo-terminal in presence of obstacle during backbone tree construction.

of the obstacle counterclockwise are then (xo ,yo ),(xo + wo ,yo ), (xo + wo ,yo + ho ), and(xo ,yo + ho ).
(3) We need to calculate the four components (m1 , m2 , m3 , m4 ), where(a) m1 = (xo + wo − xb) × vxil >xb wil ;(b) m2 = (xb − xo ) × vxil ≤xb wil ;(c) m3 = (yo + ho − yb) × vyil >yb wil ;(d) m4 = (yb − yo ) × vyil ≤yb wil .
(4) After determining the maximum value (m) among the four components according
to Eq. (22), the final pseudo-terminal (xb , yb ) position will be determined.
m = max{ m1 , m2 , m3 , m4 }.

(22)

So here four conditions may arise(a) if m = m1 then xb = xo + wo and yb = yb;(b) if m = m2 then xb = xo and yb = yb;(c) if m = m3 then xb = xb and yb = yo + ho ;(d) if m = m4 then xb = xb and yb = yo .
(5) Ultimately, the determined point (xb , yb ) works as the pseudo-terminal for thatparticular layer.
As a result of the obstacle avoidance scheme, the upper and lower layer of the
obstacle-containing layer require to add two pseudo-terminals and some extra wire asshown in Figure 16. But this overhead does not much affect the out-come, as at present
three-dimensional technology supports a maximum of up to 6–8 layers.
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:28

D. Roy et al.

Fig. 17. The fuzzification and defuzzification with respect to rule base.

This total step-by-step approach for avoiding obstacles is done in the Pseudo
Terminal Insertion() procedure, if required.
9. RESULTS AND DISCUSSION
9.1. Experimental Framework

Proposed algorithms have been implemented in C, Java, MatLab 7.14.0, MCR, MatLab
Builder JA, and Swing. The GUI is designed in GUIDE and the fuzzy expert system isimplemented using the MatLab fuzzy toolbox. The experiments were performed on astandard desktop environment of 4GB memory with an Intel chip running at 2.30GHz.
The ISPD’98 (IBM-PLACE 2.0) benchmark suite [Alpert 1998] (for fixed die placement)
is used. Later, the experiments were also implemented for ISPD’07 [Nam et al. 2007]
and ISPD’08 [Nam et al. 2008] 3D benchmarks on an 8-core 2.0GHz Intel Xeon-based
server with 8GB memory. Two different frameworks have been taken for comparability
with other standard routers for different benchmark suites.
9.2. Feasibility Study of the Proposed Model

Figure 17 shows a snapshot of the implemented fuzzy expert system of a total implementation using the fuzzy toolbox in MatLab. For the crisp input set [0.638 0.641],
the proposed rule base produces a crisp output value of 0.631. The different activatedfuzzy sets for the premise part by two crisp inputs are the highlighted trapezoids thatfall on the crisp line in the first two grids. For the consequent part, those highlighted
trapezoids are on the crisp output line in the last grid. From the snapshots of Figure 18,
it is clear that, using a rule base, the expert system produces quite accurate output, as
the change of ineligibility factor is quite smooth here. The α and β values can actually
be user specified, though we have taken α = 0.5 and β = 0.5 in presented experimental
result.
9.3. Implementation

After prior success in a feasibility study of the proposed approach, the total global
routing implementation over standard benchmarks is performed.
In Table III, experimental results for IBM benchmarks for standard cells are reported. The implementation aims to minimize the time complexity for 3D ICs in a fuzzified way. 3D placement is generated by the proposed method for these 2D benchmarks.
From the experimental results, it is clear that significantly less time is required for routing. The main concern of the algorithm is the time required for the guiding information
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:29

Fig. 18. Change of ineligibility factor with sensitivity, congestion for proposed rule base.

Table II. Variation in Resulting Metrics for IBM 02 (for 6 layers) with Different α and β Values

α
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
.9
1.0

β
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
.1
0.0

Guiding Info. Gen Time(sec.)
80.0
88.0
72.0
83.0
76.0
85.0
91.0
76.0
74.0
76.0
80.0

Routing Time(sec.)
4.0
4.0
10.0
10.0
4.0
4.0
11.0
4.0
10.0
4.0
4.0

Wirelength
167561
167091
166934
162913168014
166922
166242
185364161371166171172575

ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:30

D. Roy et al.
Table III. Experimental Benchmark Statistics for ISPD’98 Benchmarks
Benchmark

ibm01

ibm02

ibm07

ibm08

ibm09

ibm10

ibm11

ibm12

# Net

11507

18429

44394

47944

50393

64227

67016

67739

# Layer

Guiding Info. Gen. Time(sec.)

Routing Time(sec.)

3
4
5
6
7
8

93.0
85.0
56.0
36.0
28.0
16.0

4.0
3.0
3.0
3.0
2.0
1.0

3
4
5
6
7
8

140.0
121.0
90.0
85.0
74.0
60.0

10.0
6.0
5.0
4.0
4.0
2.0

3
4
5
6
7
8

280.0
268.0
251.0
247.0
240.0
220.0

30.0
27.0
26.0
22.0
22.0
20.0

3
4
5
6
7
8

342.0
337.0
323.0
307.0
305.0
297.0

36.0
32.0
27.0
26.0
24.0
21.0

3
4
5
6
7
8

358.0
345.0
313.0
294.0
283.0
278.0

39.0
35.0
32.0
28.0
23.0
22.0

3
4
5
6
7
8

547.0
519.0
489.0
485.0
480.0
472.0

54.0
42.0
35.0
33.0
32.0
32.0

3
4
5
6
7
8

423.0
402.0
380.0
372.0
370.0
367.0

87.0
85.0
77.0
74.0
67.0
57.0

3
4
5
6
7
8

646.0
623.0
609.0
605.0
589.0
582.0

132.0
128.0
123.0
120.0
102.0
96.0

ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:31

Fig. 19. Variation in guiding information generation time and routing time for different ISPD’98 benchmark
circuits (see Table III) with different numbers of layers.

generation phase. With a greater number of device layers in 3D placement, the routing
time decreases for larger circuits. This characteristic conforms to the concept of 3D ICs.
This work is aimed at comparing the fuzzified approach with other fool-proof routers
based on an heuristics-based approach. The implementation is enriched consequently.
Experimental results for different IBM benchmarks with different device layers arereported in Table III. For different numbers of device layers, variations of guiding
information generation time as well as routing time are plotted in Figure 19.
Variation of routing time with an increasing number of device layers for all benchmark circuits has been studied (see Table III) and plotted in Figure 20. Results showthat routing time is significantly lower than guiding information generation time.
Moreover, it even decreases with an increase in device layers for more availability ofrouting space in 3D ICs.
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:32

D. Roy et al.

Fig. 20. Variation in routing time with available number of layers for different ISPD’98 benchmark circuits(see Table III).

ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:33

Some important observations may be put in the form following Lemmas 9.1 and 9.2,
and Observation 9.1.
LEMMA 9.1. Better routing time may be achieved with a greater number of layers in
3D ICs.
PROOF. With an increased number of device layers, routing space increases vertically.
So some distant terminals of each net will be nearer and can be connected through vias.
This leads to a decrease of routing time for the total netlist.
LEMMA 9.2. Time to generate guiding information decreases with an increasing number of device layers in 3D ICs.
PROOF. An increasing number of device layers makes the layout area smaller andassigns fewer terminals for each layer. So, a lesser number of terminals will makeeach layer less complicated. Calculating sensitivity and congestion information will beeasier for each layer during guiding information generation. Eventually, total guiding
information generation time will decrease for a netlist with a greater number of device
layers.
OBSERVATION 9.1. The rate of increase in routing time is much slower than the rate ofincrease in guiding information generation time with an increasing number of nets.
9.4. Variation of Parameter Values

Here, α and β are the two controlling parameters which determine the objective function and therefore the final fuzzy expert system. An exhaustive analysis with variable
α and β values for certain benchmarks has been presented in Table II. Two extreme
scenarios can be named as follows.
(1) α = 0.0 and β = 1.0→ Totally Congestion-Aware Routing(2) α = 1.0 and β = 0.0→ Totally Thermal-Aware Routing
It is clear from Table II that guiding information generation time varies within 72–91
seconds, routing time varies within 4–11 seconds, and wirelength varies within 161,
371–172, 575. Apparently, for a certain benchmark the variation in the result is not
drastic for a variable set of parameter values. This quality signifies robustness of the
proposed global router.
9.5. Comparison for ISPD’98 Benchmarks

The authors have performed the simulation of FuzzRoute in (mentioned in Section
9.1) in a desktop environment to match the experimental framework descriptions withother established global routers to be compared. Tables IV and V show performance of
FuzzRoute for ISPD’98 benchmarks. Comparisons are made with some fool-proof
published academic global routers, namely Labyrinth [Kastner et al. 2002], FastRoute3.0 [Zhang et al. 2008], NTHU-R [Gao et al. 2008], BoxRouter 2.0 [Cho et al.
2009], and FGR [Roy and Markov 2008]. We cannot run our comparison against Dai
et al. [2012] and Liu et al. [2013] because of the unavailability of the results with
ISPD’98 benchmarks there.
First, the result shows that FuzzRoute is able to route through all the benchmarks.
Second, it achieves good runtime. It can finish routing all benchmarks within reasonable time on our platform. The improvements on routing time over Labyrinth, FastRoute3.0, NTHU-R, BoxRouter 2.0, and FGR are 91.81%, −10.29%, −34.91%, 86.87%,
and 32.16%, respectively. Among all quoted global routers, FastRoute3.0 achieves
fastest runtime. But it fails to generate congestion-free solutions for all benchmarks
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:34

D. Roy et al.
Table IV. Comparison of CPU Time in Seconds between Published Global Routers and FuzzRouteon ISPD’98 Benchmark Circuits

Labyrinth
FGR
Benchmark [Kastner
FastRoute3.0
NTHU-R
BoxRouter 2.0[Roy and
ISPD ’98 et al 2002] [Zhang et al. 2008] [Gao et al. 2008] [Cho et al. 2009] Markov 2008] FuzzRoute
ibm01
ibm02
ibm07
ibm08
ibm09
ibm10

21.2
34.5
228.1
238.7
505
588

0.64
0.85
1.68
1.82
1.67
3.61

4.17
7.44
15.89
13.17
11.59
33.72

33
36
86
90
273
352

10
13
18
18
20
92

3.0
4.0
22.0
26.0
28.0
33.0

Total
Norm

1615.5
13.92

10.27
0.088

85.98
.74

870
7.5

171
1.474

116.0
1

Table V. Comparison of Wirelength between Published Global Routers and FuzzRouteon ISPD’98 Benchmark Circuits
NTHU-R
FGR
BenchmarkLabyrinth
FastRoute3.0[Gao et al. BoxRouter 2.0[Roy and
ISPD ’98 [Kastner et al. 2002] [Zhang et al. 2008] 2008] [Cho et al. 2009] Markov 2008] FuzzRoute
ibm01
ibm02
ibm07
ibm08
ibm09
ibm10

77K
205K
449K
470K
481K
680K

64221
17222336902340593541491358283863321
17053136628840516941546458079362659
171110365790405634413862590141

63332
16891836618040471441305357879546276
166922357121382855403647595465

Total
Norm

2362K
1.21

2010K
1.03

2001K
1.03

2009K
1.03

1993K
1.02

1952K
1

(e.g., ibm01 and ibm09), whereas FuzzRoute can achieve 100% congestion-free routability for all the circuits in much less time than other specified routers.
Third, in terms of total wirelength, FuzzRoute is not only comparable to others
but much better, with improvements of 17.35%, 2.88%, 2.44%, 2.83%, and 2.10% overLabyrinth, FastRoute3.0, NTHU-R, BoxRouter 2.0, and FGR, respectively.
9.6. Comparison for ISPD’07 and ’08 3D Benchmarks

Tables VI, VII, and VIII, show performance of FuzzRoute for ISPD’07 and ’08 3D benchmark suites [Nam et al. 2007, 2008]. In Tables VI and VII, FuzzRoute identifies 2.5%,
2.6%, 1%, 1.1%, and 0.3% less wirelength and on average runs 1.68×, 6.42×, 2.21×,
0.76×, and 1.54× faster than NTHU-Route 2.0 [Chang et al. 2010], FastRoute 4.0 [Xuet al. 2009], NCTU-GR [Dai et al. 2012], MGR [Xu and Chu 2011], and NCTU-GR 2.0[Liu et al. 2013], respectively. It is clear from the result set that FuzzRoute can perform the total routing operation much faster than the existing state-of-the-art tools. It
result in a slower CPU time compared to MGR, but provides 1% wirelength improvement. Similarly, 1.3% larger wirelength results in much faster execution compared to
FastRoute 4.0.
FuzzRoute achieves overflow-free solutions for maximum benchmarks of ISPD’07
and ’08. Four of them, namely newblue3, newblue4, newblue7, and bigblue4, generate
overflows, represented in Table VIII. FuzzRoute shows comparable results with 0.2%,−0.4%, 2.1%, 0.2%, and 0.3% improvement in the case of total overflow with NTHURoute 2.0, FastRoute 4.0, NCTU-GR, MGR, and NCTU-GR 2.0, respectively.
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:35

Table VI. Comparison of CPU Time in Minute between Published Global Routers and FuzzRouteon ISPD’07/’08 3D Benchmark Circuits
NCTU-GR MGR
Benchmark
NTHU-Route2.0 FastRoute4.0 [Dai et al. [Xu and NCTU-GR2.0
ISPD ’07/’08 #Layer [Chang et al. 2010] [Xu et al. 2009] 2012] Chu 2011] [Liu et al. 2013] FuzzRoute
adaptec1
adaptec2
adaptec3
adaptec4
adaptec5
bigblue1
bigblue2
bigblue3
bigblue4
newblue1
newblue2
newblue3
newblue4
newblue5
newblue6
newblue7
Total
Norm

6
6
6
6
6
6
6
8
8
6
6
6
6
6
6
8

4.86
1.42
6.16
2.08
11.95
6.93
6.47
3.91
52.63
4.07
1.17
64.97
52.01
10.88
10.34
50.08
289.93
1.680

3.31
0.95
3.69
1.25
6.70
4.22
12.12
2.06
93.25
12.01
0.85
15.99
65.23
9.82
8.78
868.741108.97
6.428

3.90
1.45
4.88
2.28
9.07
6.35
11.18
4.38
65.37
3.63
0.90
131.43
40.92
15.03
9.67
71.52
381.96
2.214

4.93
1.04
4.83
1.41
7.95
5.04
6.00
2.89
21.31
4.51
0.80
19.99
15.64
6.54
7.04
21.31
131.23
0.761

2.30
0.64
2.96
1.18
4.97
3.44
3.45
1.78
63.55
1.93
0.63
63.34
17.48
4.62
4.02
74.53
250.82
1.544

1.73
0.32
2.12
3.72
4.73
2.97
1.95
3.31
56.29
1.18
0.74
64.80
3.02
2.79
3.82
18.93
172.51
1

From an overall analysis of different dominating matrices of performance characterization for different standard benchmarks, it is clear that FuzzRoute is competitive with state-of-the-art tools, though it can provide an different kind of solution for
NP-complete problems in a possibilistic way (implementing fuzzy logic), unlike using
heuristics only.
9.7. Time Complexity Analysis

It is verified that the time complexity of generating guiding information is O(l × m× n),
where l the total number of layers, m the number of subregions in the x direction, andn the number of subregions in y direction of the layout. To perform global routing foreach net, the time complexity would be O(l × (m + n)). Hence, the total global routing
procedure for connecting two-pin, multi-pin, and critical nets requires that much of thecomplexity be multiplied by the number of nets, and in addition with the time required
to process a fuzzy expert system for each layer.
With respect to a two-pin intra-layer net, the proposed fuzzified approach will resultin linear time complexity of O(m + n). So, the proposed approach presents better timecomplexity than typical maze routing approaches, which is O(m× n) when l = 1. Hence,
our proposed fuzzy-logic-based two-pin net routing will give linear time complexity
instead of the quadratic time complexity of maze routing. Here, an optimal solution isachieved satisfying certain constraints without any guarantee of finding an optimum
solution, whereas maze routing concentrates the solution quality on optimum routing
path finding.
10. CONCLUSION AND FUTURE DIRECTION

This article highlights the paramount aspect of the global routing problem in 3D ICs
by achieving a prominent degree of reliability and routability with a reasonable timecomplexity. The total methodology of the designed multi-objective global router has
ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:36

D. Roy et al.
Table VII. Comparison of Wirelength between Published Global Routers and FuzzRouteon ISPD’07/’08 3D Benchmark Circuits

MGR
Benchmark NTHU-Route2.0
FastRoute4.0
NCTU-GR[Xu and
NCTU-GR2.0
ISPD’07/’08 [Chang et al. 2010] [Xu et al. 2009] [Dai et al. 2012] Chu 2011] [Liu et al. 2013] FuzzRoute
adaptec1
adaptec2
adaptec3
adaptec4
adaptec5
bigblue1
bigblue2
bigblue3
bigblue4
newblue1
newblue2
newblue3
newblue4
newblue5
newblue6
newblue7
Total
Norm

53.49
52.31
131.11121.73155.5556.35
90.59
130.76231.0446.53
75.85
106.49130.46231.73177.01353.352144.35
1.025

53.73
52.17
130.82
121.24155.8156.64
91.18
130.04230.2446.33
75.12
108.40130.46230.94177.87353.382144.37
1.026

53.50
51.69
130.35120.67
154.7056.56
89.40
129.66223.9945.99
74.88
104.28126.79230.31
176.87338.632108.27
1.009

52.28
51.69
128.92119.96153.2355.82
88.92
128.75225.7345.58
74.46
107.22128.54228.00174.86
349.022112.98
1.011

52.35
51.30
128.34120.17151.8555.33
86.71
127.67227.10
45.62
74.51
106.8
129.27225.94171.10341.902095.96
1.003

52.31
50.23
128.65120.96152.03
54.89
86.21
126.34226.6545.37
74.44
105.36128.97226.78170.56340.482090.23
1

Table VIII. Comparison of Overflow between Published Global Routers and FuzzRouteon ISPD’07 / ’08 3D Benchmark Circuits
MGR
Benchmark
NTHU-Route2.0
FastRoute4.0
NCTU-GR[Xu and
NCTU-GR2.0
ISPD ’07/’08 [Chang et al. 2010] [Xu et al. 2009] [Dai et al. 2012] Chu 2011] [Liu et al. 2013] FuzzRoutenewblue3
newblue4
newblue7
bigblue4
Total
Norm

31454
138
62
162
31816
1.002

31276
136
54
130
31596
0.995

31808
134
114
164
32220
1.021

31026
136
56
134
31352
0.988

31526
132
54
132
31844
1.003

31426
132
56
134
31748
1

been verified successfully for two-pin, multi-pin, and critical intra- and inter-layernets for 3D ICs. It may also be considered as a new type of guided global routing
approach (using fuzzy logic) for standard cells. The procedure is tested on ISPD’98
and ’08 benchmark suites and compared with some well-known global routers. Designof a fool-proof global routing solution for 3D ICs considering other metrics as well,further comparison with other state-of-the-art tools in the ISPD’11 benchmark suite,
extension to mixed-size cell placements, and consideration of voltage drop impact as
another working constraint may be considered as some possible future extensions of
the present work.

ACKNOWLEDGMENTS
The authors are thankful to Dr. S. Das of IIEST Shibpur for his help in using a specific computing resource.

ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

FuzzRoute: A Global Routing Method for 3D Integrated Circuits

1:37

REFERENCES
J. Abonyi. 2003. Fuzzy model identification. In Fuzzy Model Identification for Control. Birkhauser, Boston,MA, 87–164.
C. J. Alpert. 1998. The ISPD98 circuit benchmark suite. In Proceedings of the ACM International Symposiumon Physical Design (ISPD’98). 80–85.
R. Babuska. 1998. Fuzzy Modeling for Control, 1st Ed. Kluwer Academic, Norwell, MA.
S. Bandyopadhyay. 2005. Automatic determination of the number of fuzzy clusters using simulated annealing with variable representation. In Proceedings of the 15th International Conference on Foundations ofIntelligent Systems (ISMIS’05). 549–602.
J. L. Castro and M. Delgado. 1996. Fuzzy systems with defuzzification are universal approximators. IEEE
Trans. Syst. Man Cybernet. B Cybernet. 26, 1, 149–152.
C. J. Chang, P. J. Huang, T. C. Chen, and C. N. J. Liu. 2011. ILP-based inter-die routing for 3D ICs. In
Proceedings of the 16th Asia and South Pacific Design Automation Conference (ASPDAC’11). 330–335.
Y.-J. Chang, Y.-T. Lee, J.-R. Gao, P.-C. Wu, and T.-C. Wang. 2010. NTHU-route 2.0: A robust global router for
modern designs. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 29, 12, 1931–1944.
M. Cho, K. Lu, K. Yuan, and D. Z. Pan. 2009. BoxRouter 2.0: A hybrid and robust global router with layer
assignment for routability. ACM Trans. Des. Autom. Electron. Syst. 14, 2, 32:1–32:21.
K.-R. Dai, W.-H. Liu, and Y.-L. Li. 2012. NCTU-GR: Efficient simulated evolution-based rerouting andcongestion-relaxed layer assignment on 3D global routing. IEEE Trans. VLSI Syst. 20, 3, 459–472.
S. Das, A. Chandhakasan, and R. Reif. 2003. Design tools for 3D integrated circuits. In Proceedings of the
Asia and South Pacific Design Automation Conference the (ASPDAC’03). 53–56.
J.-R. Gao, P.-C. Wu, and T.-C. Wang. 2008. A new global router for modern designs. In Proceedings of the
Asia and South Pacific Design Automation Conference (ASPDAC’08). 232–237.
P. Ghosal, H. Rahaman, and P. Dasgupta. 2009. Uniform thermal distributions in placement of standard
cells and gate arrays: Algorithms and results. In Proceedings of the 13th IEEE/VSI VLSI Design andTest Symposium (VDAT’09). 69–78.
P. Ghosal, H. Rahaman, and P. Dasgupta. 2010a. An experimental study of interconnection length in 3D and2D VLSI. In Proceedings of the IEEE Latin American Symposium on Circuits and Systems (LASCAS’10).
P. Ghosal, H. Rahaman, and P. Dasgupta. 2010b. Cell level thermal placement in 3D ICs. In Proceedings of
the Annual IEEE India Conference (INDICON’10). 1–4.
P. Ghosal, H. Rahaman, and P. Dasgupta. 2010c. Minimizing thermal disparities during placement in
3D ICs. In Proceedings of the 13th IEEE International Conference on Computational Science andEngineering (CSE’10). 160–167.
P. Ghosal, H. Rahaman, and P. Dasgupta. 2010d. Thermal aware placement in 3D ICs. In Proceedings of
2nd International Conference on Advances in Recent Technologies in Communication and Computing(ARTCom’10). 66–70.
P. Ghosal, T. Samanta, H. Rahaman, and P. Dasgupta. 2008. Thermal-aware placement of standard cells andgate arrays: Studies and observations. In Proceedings of the IEEE Computer Society Annual Symposium
on VLSI (ISVLSI’08). 369–374.
B. Goplen and S. S. Sapatnekar. 2005. Thermal via placement in 3D ICs. In Proceedings of the International
Symposium on Physical Design (ISPD’05). 167–174.
A. Gupta, N. D. Dutt, F. J. Kurdahi, K. S. Khouri, and M. S. Abadir. 2008. Thermal aware global routingof VLSI chips for enhanced reliability. In Proceedings of the 9th International Symposium on Quality
Electronic Design (ISQED’08). 470–475.
C. J. Huang, Y. W. Wang, H. M. Chen, H. W. Tsai, J. J. Jian, . L. Cheng, and J. J. Liao. 2014. Application of cellular automata and type-2 fuzzy logic to dynamic vehicle path planning. Appl. Soft Comput. 19, 333–342.
S. Im and K. Banerjee. 2000. Full chip thermal analysis of planar (2-D) and vertically integrated (3D) highperformance ICs. In International Electronic Devices Meeting Technical Digest (IEDM’00). 727–730.
M. Kanthi, H. S. Mruthyunjaya, and V. I. George. 2013. Fuzzy logic control for active ankle foot orthosis. In
Proceedings of the IEEE International Conference on Fuzzy Systems (FUZZ’13). 1–6.
R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh. 2002. Pattern routing: Use and theory for increasing
predictability and avoiding coupling. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 21, 7, 777–790.
W.-H. Liu, W.-C. Kao, Y.-L. Li, and K.-Y. Chao. 2013. NCTU-GR 2.0: Multithreaded collision-aware global routing with bounded-length maze routing. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 32, 5, 709–722.
K. Lu and D. Z. Pan. 2009. Reliability-aware global routing under thermal considerations. In Proceedings ofthe 1st Asia Symposium on Quality Electronic Design (ASQED’09). 313–318.
E. Lughofer. 2011. Evolving Fuzzy Systems - Methodologies, Advanced Concepts and Applications. Springer.

ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.

1:38

D. Roy et al.

J. Minz, E. Wong, and S. K. Lim. 2005. Thermal and crosstalk-aware physical design for 3D system-onpackage. In Proceedings of the Electronic Components and Technology Conference (ECTC’05). 824–831.
M. D. Moffitt. 2009. Global routing revisited. In Proceedings of the International Conference on ComputerAided Design (ICCAD’09). 805–808.
G.-J. Nam, C. Sze, and M. Yildiz. 2008. The ISPD global routing benchmark suite. In Proceedings of theInternational Symposium on Physical Design (ISPD’08). 156–159.
G.-J. Nam, M. Yildiz, D. Z. Pan, and P. H. Madden. 2007. ISPD placement contest updates and ISPD 2007
global routing contest. In Proceedings of the International Symposium on Physical Design (ISPD’07). 167.
M. Pathak and S. K. Lim. 2009. Performance and thermal-aware Steiner routing for 3-D stacked ICs. IEEE
Trans. Comput.-Aid. Des. Integr. Circ. Syst. 28, 9, 1373–1386.
W. Pedryz and F. Gomide. 2007. Fuzzy Systems Engineering: Toward Human-Centric Computing. John
Wiley and Sons, Hoboken, NJ.
W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling. 2001. Numerical Recipes: The Art of
Scientific Computing. Cambridge University Press, London.
D. Roy and P. Ghosal. 2013. A fuzzified approach towards global routing in VLSI layout design. In
Proceedings of the IEEE International Conference on Fuzzy Systems (FUZZ’13). 1–8.
D. Roy, P. Ghosal, and N. Das. 2014a. A thermal and congestion driven global router for 3D integrated
circuits. In Proceedings of the Students’ Technology Symposium (TechSym’14). 303–308.
D. Roy, P. Ghosal, and S. P. Mohanty. 2014b. FuzzRoute: A method for thermally efficient congestion freeglobal routing in 3D ICs. In Proceedings of the IEEE Computer Society Annual Symposium on VLSI(ISVLSI’14). 71–76.
J. A. Roy and I. L. Markov. 2008. High-performance routing at the nanometer scale. IEEE Trans.
Comput.-Aid. Des. Integr. Circ. Syst. 27, 6, 1066–1077.
K. Sabahi, S. Ghaemi, and S. Pezeshki. 2014. Application of type-2 fuzzy logic system for load frequency
control using feedback error learning approaches. Appl. Soft Comput. 21, 1–11.
S. M. Sait and H. Y. H. Ali. 1999. Fuzzy simulated evolution algorithm for multi-objective optimization of
VLSI placement. In Proceedings of the Congress on Evolutionary Computation (CEC’99).
C.-H. Tsai and S.-M. Kang. 2000. Cell-level placement for improving substrate thermal distribution. IEEE
Trans. Comput.-Aid. Des. Integr. Circ. Syst. 19, 2, 253–266.
N. Viswanathan, C. J. Alpert, C. Sze, Z. Li, G.-J. Nam, and J. A. Roy. 2011. The ISPD-2011 routability-driven
placement contest and benchmark suite. In Proceedings of the ACM International Symposium on
Physical Design (ISPD’11). 141–146.
L. X. Wang. 1992. Fuzzy systems are universal approximators. In Proceedings of the IEEE International
Conference of Fuzzy Systems (FUZZ’92). 1163–1170.
T. H. Wu, A. D. Jeffrey, and T. Linderoth. 2009. GRIP: Scalable 3D global routing using integer programming.
In Proceedings of the 46th ACM/IEEE Design Automation Conference (DAC’09). 320–325.
Y. Xu and C. Chu. 2011. MGR: Multi-level global router. In Proceedings of the International Conference on
Computer-Aided Design (ICCAD’11). 250–255.
Y. Xu, Y. Zhang, and C. Chu. 2009. FastRoute 4.0: Global router with efficient via minimization. In
Proceedings of the Asia and South Pacific Design Automation Conference (ASPDAC’09). 576–581.
L. A. Zadeh. 1973. Outline of a new approach to the analysis of complex systems and decision processes.
IEEE Trans. Syst. Man Cybernet. SMC-3, 1, 28–44.
T. Zhang, Y. Zhan, and S. S. Sapatnekar. 2006. Temperature-aware routing in 3D ICs. In Proceedings of the
Asia and South Pacific Design Automation Conference (ASPDAC’06). 309–314.
T. Zhang, Y. Zhan, S. S. Sapatnekar, J. Cong, and Y. Zhang. 2005. Thermal-driven multilevel routing for 3-D
ICs. In Proceedings of the Asia and South Pacific Design Automation Conference (ASPDAC’05). 121–126.
Y. Zhang, Y. Xu, and C. Chu. 2008. FastRoute3.0: A fast and high quality global router based on virtual
capacity. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design(ICCAD’08). 344–349.
Received November 2014; revised April 2015; accepted April 2015

ACM Transactions on Design Automation of Electronic Systems, Vol. 21, No. 1, Article 1, Pub. date: November 2015.