A Near-Optimal Parallel Algorithm for One-Dimensional Gate Assignment in VLSI Layout

Article type: Research Article

Authors: Tsuchiya, K.^{a; b; *} | Takefuji, Y.^{b; c}

Affiliations: [a] Fuji Electric Co., Ltd., 1, Fuji-machi, Hino, Tokyo 191, Japan | [b] Faculty of Environmental Information, Keio University, 5322 Endoh, Fujisawa 252, Japan | [c] Department of Electrical Engineering and Applied Physics, Case Western Reserve University, Cleveland, OH 44106, USA

Correspondence: [*] Correspondence to: Mr. Kazuhiro Tsuchiya.

Abstract: A novel approach to the one-dimensional gate assignment problem is presented in this paper where the problem is NP-hard and one of the most fundamental layout problems in VLSI design. The proposed system is composed of n × n processing elements called the artificial two-dimensional maximum neurons for (n + 2)-gate assignment problems. We have discovered the improved solutions in the benchmark problems over the best existing algorithms. The proposed parallel algorithm is also applicable to other VLSI layout problems.

DOI: 10.3233/ICA-1999-6306

Journal: Integrated Computer-Aided Engineering, vol. 6, no. 3, pp. 249-257, 1999