An efficient algorithm for hexagon/triangle placement by extending the application of the sequence pair representation

Author

Wei, Yaoguang ; Dong, Sheqin ; Hong, Xianlong

Author_Institution

Graduate Sch., Tsinghua Univ., Shenzhen

Volume

2

fYear

2005

fDate

24-0 Oct. 2005

Firstpage

852

Lastpage

855

Abstract

The Y architecture has recently received much attention due to its many potential advantages. To fully utilize the virtues of Y architecture, a non-Manhattan hexagon/triangle placement (HTP for short) paradigm suitable for the Y architecture was proposed recently. This paper extend the application of sequence pair (SP for short) representation to HTP problem and present a new efficient HTP packing algorithm in BBL mode, based on the SP representation and FAST-SP algorithm together with some packing rules. Two benchmarks transformed from MCNC ami33 and ami49 are developed. Experimental results show that we have obtained the best results ever reported in the literature with less runtime. In addition, two coordinate systems adapting to the Y architecture are first presented

Keywords

integrated circuit interconnections; network routing; MCNC ami33; MCNC ami49; Y architecture; hexagon placement; packing algorithm; sequence pair representation; triangle placement; Algorithm design and analysis; Application software; Computer architecture; Computer science; Electronic mail; Geometry; Routing; Runtime; Throughput; Wire;

fLanguage

English

Publisher

ieee

Conference_Titel

ASIC, 2005. ASICON 2005. 6th International Conference On

Conference_Location

Shanghai

Print_ISBN

0-7803-9210-8

Type

conf

DOI

10.1109/ICASIC.2005.1611439

Filename

1611439