Force Directed Graph Drawing Algorithms for Macro Cell

Abstract— Macro cells are used more and more in current designs as they provide the benefit of reusability directly resulting in the decrease of design cost and time. However, there lies a gap in the EDA industry for Macro cell placement tools. This paper would like to introduce the idea of using graph-drawing algorithms as the basis for a Macro cell placement tool in order to obtain successful layouts. Index Terms— design automation, Macro cell, placement tool, force directed algorithm,

graph drawing I. INTRODUCTION The past few years have seen an exponential rise in the growth rate of the semi-conductor industry. The increase in usage and demand of electronic devices among consumers has resulted in the need to provide better and faster design methods. The designers are pushed to their limits in meeting these demands whilst juggling the constraints of power and performance of ever shrinking circuits. To help designers meet their targets, EDA (Electronic Design Automation) tools are used to help fully or partially automate the design processes. One of such important backend processes is the placement component. The placement problem simply is the problem of finding the ideal locations for each cell in a circuit achieving as many or all of the placement objectives. The two main objectives that every placement tool has to achieve are, • overlap free layout • fit in the given placement area. Other objectives may include minimization of wirelength, area, congestion, run time etc. The optimal solution will be one that satisfies all of the given criteria. Achieving such a placement solution is far from possible and even the simplest of cell placement problems are defined to be NP- hard. The consequence of falling short of a good placement could result in an unroutable design, a slower and/or larger chip etc. This will cost time and money to either manually correct the placement or start the design from the beginning. The input to the placement component consists of the description of all the cells including their size and pin Manuscript received March 13, 2008. This research is jointly funded by the Department of Engineering and Technology of Manchester Metropolitan University, UK, and the ORSAS (Overseas Research Students Awards Scheme). Meththa Samaranayake is with the Department of Engineering and Technology, Manchester Metropolitan University, John Dalton Building, Chester Street, Manchester M1 5GD, UK (phone: +44 (0) 1612473683; e- mail: Meththa.t.samaranayake@student.mmu.ac.uk). Helen Ji is with the Department of Engineering and Technology, Manchester Metropolitan University, John Dalton Building, Chester Street, Manchester M1 5GD, UK (e-mail: h.ji@mmu.ac.uk). John Ainscough is with the Department of Engineering and Technology, Manchester Metropolitan University, John Dalton Building, Chester Street, Manchester M1 5GD, UK (e-mail: j.ainscough@ mmu.ac.uk ). locations and a netlist. On successful placement, the output will hold the locations of the cells that are non-overlapping and fitted into the placement area. In the past, designs mainly carried standard cells that were...

Website: www.iaeng.org | Filesize: -
No of Page(s): 6
Download Force Directed Graph Drawing Algorithms for Macro Cell ... - IAENG.pdf