A Fast Algorithm for VLSI Building Block Placement

Author

Ning Xu ; Feng Huang ; Zhonghua Jiang

Author_Institution

Sch. of Comput. Sci. & Technol., Wuhan Univ. of Technol.

fYear

2006

Firstpage

2157

Lastpage

2160

Abstract

A block placement representation called sequence pair was introduced by Murata (1995). Many algorithms that are based on sequence pairs use simulated annealing where the generation and evaluation of a large number of sequence pairs is required. This paper presents a new approach to evaluate a sequence pair based on ant colony optimization in a pair of weighted-constraint graphs. The method is a significant improvement compared to the original O(M²) algorithm (Murata, 1995). Experimental results show that our approach can estimate the area of a placement faster

Keywords

VLSI; circuit complexity; graph theory; integrated circuit layout; simulated annealing; VLSI building block placement; ant colony optimization; block placement representation; fast algorithm; sequence pair; simulated annealing; weighted-constraint graph; Ant colony optimization; Application software; Computational modeling; Computer science; Constraint optimization; Integrated circuit interconnections; Integrated circuit technology; Simulated annealing; Systems engineering and theory; Very large scale integration; Ant Colony Optimization; Sequence Pair; The Longest Path; VLSI Placement;

fLanguage

English

Publisher

ieee

Conference_Titel

Computational Engineering in Systems Applications, IMACS Multiconference on

Conference_Location

Beijing

Print_ISBN

7-302-13922-9

Electronic_ISBN

7-900718-14-1

Type

conf

DOI

10.1109/CESA.2006.313483

Filename

4105736