A Fast 3D-BSG Algorithm for 3D Packing Problem

Author

Zhang, Lingyi ; Dong, Sheqin ; Hong, Xianlong ; Ma, Yuchun

Author_Institution

Dept. of Comput. Sci. & Technol., Tsinghua Univ., Beijing

fYear

2007

fDate

27-30 May 2007

Firstpage

2044

Lastpage

2047

Abstract

3D packing is a fundamental problem for VLSI design. It arises from 3D-ICs floorplan design and task schedule in reconfigurable FPGA design. In this paper, we present a novel 3D floorplan representation by improving the 3D bounded slice-surface grid (3D-BSG) structure in two aspects: (1) optimize the evaluation time complexity from O(n³) to O(n²) by using three block relation graphs; (2) handle the infeasible assignment problem of 3D-BSG in linear time by giving the rule of null relation rooms. The effectiveness and efficiency of the fast 3D-BSG are shown by both theoretical analysis and experimental results. The average speedup compared to the original 3D-BSG is 44times high.

Keywords

field programmable gate arrays; integrated circuit layout; 3D bounded slice-surface grid structure; 3D packing problem; VLSI design; evaluation time complexity; fast 3D-BSG algorithm; floorplan design; infeasible assignment problem; reconfigurable FPGA design; task schedule; three block relation graphs; Algorithm design and analysis; Computer science; Electronic design automation and methodology; Field programmable gate arrays; Large-scale systems; Processor scheduling; Three-dimensional integrated circuits; Topology; Upper bound; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2007. ISCAS 2007. IEEE International Symposium on

Conference_Location

New Orleans, LA

Print_ISBN

1-4244-0920-9

Electronic_ISBN

1-4244-0921-7

Type

conf

DOI

10.1109/ISCAS.2007.378499

Filename

4253070