 Open Access
 Total Downloads : 14
 Authors : Prabha. J, D.Gracia Nirmala Rani, S.Rajaram
 Paper ID : IJERTCONV1IS06113
 Volume & Issue : ICSEM – 2013 (Volume 1 – Issue 06)
 Published (First Online): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
B* tree based Thermal Aware Non Sliceable Floorplanning
PRABHA. J
PG Student, Dept. of ECE Thiagarajar College of Engineering Madurai, India
jprabha@tce.edu
D.GRACIA NIRMALA RANI
Assistant Professor, Dept. of ECE Thiagarajar College of Engineering Madurai, India
gracia@tce.edu
S.RAJARAM
Associate Professor, Dept. of ECE Thiagarajar College of Engineering Madurai, India rajaram_siva@tce.edu
Abstract Scaling have increased power density which further increases the maximum temperature of the chip. This maximum temperature can be decreased thus reducing the impact of temperature on Hotspots using Thermal Aware Floorplanning. This paper involves temperature aware design which alleviates the problems in submicron technologies. This paper makes use of the simulated annealing algorithm to determine the global optimum solution. The floorplaning makes use of B* tree representation
proposed Thermal Aware Floorplanning Algorithm. Section V ends with results and discussion.
II. PROBLEM FORMULATION

Cost Function
Let B = {b1, b2, , bm} be a set of m rectangular modules with block biof width Wi, height Hi, area Ai, and an original power density P , 1 <i <m. The aspect ratio is given by H /W .
which is optimum for nonsliceable floorplan. The ultimate aim of i i i
this paper is to minimize the maximum temperature of the chip.

INTRODUCTION

Power density has increased in recent years due to scaling thus creating difficulty in maintaining the reliability of the system [1]. Most of the power aware design does not reduce power design in hotspots [2]. Thus, Thermal aware floorplanning can be used to reduce the maximum temperature of the chip [3].
The temperature can be reduced using lateral Spreading of heat in which the hot blocks are placed beside the colder blocks [4, 5]. Hotspot tool developed by Skadron et al. can be used to calculate the temperature distribution among various blocks of the chip.
The Parquet tool designed by Han et al. uses the objective function adding temperature as one of the factor. This paper uses the combination of Normalized Polish Expression for floorplan representation and Genetic Algorithm for Optimization. The performance impact of the proposed algorithm is not addressed in this paper [7]. The temperature aware floorplanning by Lixia et al. makes use of B* tree representation and Simulated Annealing. In our proposed work, the fixed outline thermal aware floorplan is obtained.
The paper is organized as follows: Section II gives the problem definition. Section III explains the B* tree representation and the Simulated Annealing algorithm. Section IV discusses the
Each module is free to rotate. Let (xi, yi) denote the coordinates of the bottomleft corner of the rectangle bi on a chip. A floorplan F is an assignment of (xi, yi) to the bottom left corners for each bi such that no two modules overlap.
The objective function is given by
(1)
Where , and are the weights of the area, wirelength and the
highest temperature respectively.

PROPOSED APPROACH

Motivation
Thermalaware Floorplanning problem is considered a generalization of the quadratic assignment which is classied as an NPhard problem [9]. Therefore, it is difcult to nd thermally optimized solutions, especially when the number of functional units increases. The lack of proposals capable of dealing with an elevated number of functional units in a short time motivates this work. The proposed Thermal aware floorplanning method provides a multiobjective solution.

B* Tree Representation
Chang et al. [14] presented a binary tree based representation for a left and bottom compacted placement called B*Tree.
Given a placement P, we can construct a unique B*Tree in linear time by using a recursive procedure similar to the depth first search (DFS) algorithm. The root of a B*Tree corresponds to the module on the bottomleft corner. The left child nj of a node ni denotes the module mj that is the lowest adjacent module on the righthand side of mi as xj=xi+wi.
temperature rise at block i due to one unit of power dissipated at block j:
Rij=Tij/Pj (2)
such that we can get a transfer thermal resistance matrix as Rt. For any power distribution on the floorplan, we can calculate each blocks temperature by using the following equation:
The right child nkof a node ni denotes the module mkthat is the lowest visible module above mi and with the same x coordinate
Rt
11
Rt
Rt ….
12
Rt ….
Rt
1m
Rt
T1 Rt
T
11
R
t
2
Rt ….
12
Rt ….
Rt P1
t
1m
P
R 2
as mi as xk=xi.
Rt 21 22
2m
21 22
2m
: : :
: : : : : : :
t t
t t t
t
Rm1 Rm2
….
Rmm Tm Rm1 Rm2
….
RmmPm
(3)
Where Pi is the power consumption and Ti is the temperature of the functional block i. The transfer thermal resistance matrix can be obtained from Hotspot, given the floorplan for a set of blocks.
Fig.1. B* tree representation for nonsliceable floorplan

Module Cooling Strategy
The principle used in the proposed thermal aware floorplanning is lateral spreading of heat. When a hot module is placed besides a cold module, then diffusion of heat takes place which reduces the overall temperature [6]. Fig. 2 depicts the module cooling strategy. The hot modules designated as H1 and H2 are separated in thermal aware floorplanning.
Fig.2. Module cooling strategy
The temperature of the chip depends on the power consumption of each functional block and the relative positions of the functional blocks. This will result in more spreading of heat, thus reducing hotspot temperatures.

Thermal Modelling Tool
Skadron et al. developed the HotSpot software tool, which calculates the temperature distribution among different blocks in a CPU chip.
Hotspot generates the thermal RC circuit dynamically when initialized with a CPU floorplan.HotSpot uses the fourthorder RungeKutta method (rk4) to solve the differential equations that describe the RC circuit, and returns the maximum temperature of blocks at each step.
The basic idea is that, we define the transfer thermal resistance Rij of functional block i with respect to block j as the


PROPOSED THERMAL AWARE FLOORPLANNING
Thermal aware floorplanning makes use of the simulated Annealing Algorithm. The algorithm starts by randomly choosing an initial B*Tree. The perturbation process converts one feasible B*Tree to another. We then do the placement for the corresponding B*Tree and evaluate the cost function. The move is accepted if the cost of the current solution is less than the previous one or with a probability that is a decreasing function of annealing temperature (Boltzmann functions) as defined in the algorithm. For all other cases, the move is rejected.
We terminate the annealing process if the number of accepted moves is less than 5% of all moves made at a certain temperature or the temperature is low enough i.e. less than the threshold. At last, we transform the resulting B*Tree, i.e. the solution with the lowest value of cost function, to the corresponding final admissible placement.
The method used for theral aware floorplanning in this paper is given in the flowchart as shown in fig. 3.
Fig.3. Flowchart of the proposed Thermal aware floorplanning

RESULTS AND DISCUSSION
Skadron et al. developed the HotSpot software tool, which calculates the temperature distribution among different blocks in a CPU chip. The algorithm was written in C++ and was simulated with Intel core i5 processor and 4 GB RAM. The MCNC benchmark circuits namely apte, hp, Xerox, ami33, ami49 were used to test the correctness of the tool. The MCNC benchmark circuit hp that is flipped diagonally is shown in fig. 4(a). The blocks labeled as Unit 8 and Unit9 is taken as the hotspots. These blocks have the temperature greater than the average die temperature. The MCNC benchmark circuit characteristics are shown in table 1.
Circuit
Block#
Net#
Pin#
Pad#
Apte
9
97
214
73
Xerox
10
203
696
2
Hp
11
83
264
45
ami33
33
123
480
42
ami49
49
408
931
22
Table I. MCNC benchmark circuit Characteristics
The input block/net/pl files and the randomly generated experimentally tested ptrace file were taken as input. The thermal aware floorplanner was run first with area weight as 0.35, wirelength weight as 0.30 and the temperature weight as 0.35.
Fig.4. (a) MCNC benchmark circuit hp (b) Thermal distribution of the hp circuit based on the power density (c) Output Thermal aware floorplan using Simulated annealing algorithm for the hp circuit.
The maximum temperature of the floorplan was reduced significantly with only slight increase in area and wirelength.
The hotspots are placed apart so that the peak temperature is reduced. This is done in the thermal aware floorplanning using simulated annealing algorithm. Fig. 4(c) depicts the output floorplan that is thermal aware with their thermal distribution. This shows that the peak temperature is reduced resulting in the elimination of hotspots.
The MCNC benchmark circuits ami33 and ami49 shows reduction in the peak temperature of the chip whereas the apte circuit shows a slight increase in temperature. The results have
also shown that the proposed algorithm reduces the chips maximum and average temperature. The reduction in temperature is shown in Fig. 6.
Fig. 5 (a) MCNC benchmark circuit xerox (b) Thermal distribution of the xerox circuit based on the power density (c) Output Thermal aware floorplan using Simulated annealing algorithm for the xerox circuit.
Table II. Comparison between existing approach and proposed approach
Circui Existing Approach Proposed Approach
t [7] (Randomly Selecting
modules)
Area (in mm2
)
Wire lengt
h (in mm)
Temp eratur e (in
Â°C)
Area (in mm2)
Wire lengt
h (in mm)
Temp eratur e (in
Â°C)
apte
48.6
6
417
78
48.36
465
79.11
hp
9.78
162
89
9.363
167
88.85
ami33
1.27
68
87
1.156
70
58.85
ami49
38.8
6
898
95
35.54
907
87.85
Fig. 6 Graph showing reduction in peak and average temperature in Existing and Proposed Approach

CONCLUSION

This paper has implemented the novel thermal aware floorplanning method using simulated annealing algorithm. Simulated annealing is used to find the optimum solution no matter where the initial solution begins. The optimized floorplan is obtained that separates the two hot modules thus decreasing the overall die temperature. The future scope of this work is to apply hybrid evolutionary algorithms for the non sliceable thermal aware floorplanning.
REFERENCES

Y. Liu, R.P. Dick, L. Shang, and H. Yang, Accurate temperature dependent integrated circuit leakage power estimation is easy, DATE
07: Proceedings of the Conference on Design, Automation and Test ,
Europe, pp. 15261531, 2007.

K. Skadron, M. Stan, M.R. Huang, S. Velusamy, K. Sankaranarayanan and D. Tarjan, Temperature aware microarchitecture, International Symposium on Computer Architecture, pp. 213, 2003.

K. Sankaranarayanan, S.Velusamy, M.R. Stan and K. Skadron, A case for thermalaware floorplanning at the microarchitectural level, Journal of Instructionlevel Parallelism, pp. 816, 2005.

K. Skadron, M. Stan, M.R. Huang, S. Velusamy and K. Sankaranarayanan, A case for thermal aware floorplanning at the microarchitectural level, Journal of Instructionlevel Parallelism, pp. 1 16, 2005.

W. Huang, M.R. Stan, K. Skadron, K. Sankaranarayanan, S. Ghosh and S. Velusamy, Compact thermal modeling for temperatureaware design, 41st Annual Conference (DAC), pp. 878883, 2004.

W.L. Hung, C. AddoQuaye, T. Theocharides, Y. Xie, N. Vijaykrishnan and M.J. Irvin, Thermal aware floorplanning using genetic algorithms, International Symposium on Quality Electronic Design (ISQED), pp. 634 639, March 2005.

Lixia Qi, Yinshui Xia, Lunyao Wang, Simulated Annealing Based ThermalAware Floorplanning International Conference on Electronics, Communications and Control (ICECC), pp. 463 466, Sept 2011.

Y. Han, I. Koren and C.A. Moritz, Temperature aware floorplanning,
Workshop on Temperature Aware Microarchitectures, 2005.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman, 1979.

D. F.Wong, and C. L. Liu, A New Algorithm for Floorplan Design,
Proc. DAC, pp. 101107, 1986.

H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, Rectangle Packing Based Module Placement, Proc. ICCAD, pp. 472479, 1995.

S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani, Module Placement on BSGStructure and IC Layout Applications, Proc. ICCAD, pp. 484491, 1996.

P.N. Guo, C.K. Cheng, and T. Yoshimura, An OTree Representation of NonSlicing Floorplan and Its Applications,Proc.DAC, pp. 268273, 1999.

Y.C. Chang, Y.W. Chang, G.M. Wu and S.W. Wu, B* trees: a new representation for nonslicing floorplans, Proceedings of the 37th Annual design Automation Conference, pp. 458463, 2000.

W. Huang, S. Ghosh, S. Velusamy, K. Sankaranarayanan, K. Skadron, and M. R. Stan, Hotspot: a compact thermal modeling methodology for earlystage VLSI design, IEEE Transactions on VLSI System , Vol.14, No.5, pp. 501513, May 2006.

YingChieh Chen, Yiming Li, Temperatureaware floorplanning via geometric programming Mathematical and Computer Modeling, Vol.51, No.78, pp. 927934, April 2010.

Srinivasan J., Adve S.V., Bose P., and Rivers J., The Impact of Technology Scaling on Lifetime Reliability. Proceedings of International Conference on Dependable Systems and Networks, June 2004.

Skadron K., Stan M., Huang W., Velusamy S., Sankaranarayanan K., and Tarjan D., Temperatureaware microarchitecture: Modellingand implementation, Association for Computing Machinery Transactions on Architecture and Code Optimization, Vol. 1, pp. 94, 2004.

Hotspothowto, Available: [Online] [http://lava.cs.virginia.edu/HotSpot/HotSpotHOWTO.htm].

Mcncbenchmark, Available: [Online] [http://vlsicad.eecs.umich.edu/BK/MCNCbench/], 2006.