An efficient algorithm for bipartite PLA folding

Author

Liu, Chun-Yeh ; Saluja, Kewal K.

Author_Institution

Dept. of Electr. & Comput. Eng., Wisconsin Univ., Madison, WI, USA

Volume

12

Issue

12

fYear

1993

fDate

12/1/1993 12:00:00 AM

Firstpage

1839

Lastpage

1847

Abstract

Programmable logic arrays (PLAs) provide a flexible and efficient way of synthesizing arbitrary combinational functions as well as sequential logic circuits. They are used in both LSI and VLSI technologies. The disadvantage of using PLAs is that most PLAs are very sparse. The high sparsity of the PLA results in a significant waste of silicon area. PLA folding is a technique which reclaims unused area in the original PLA. This paper proposes a column bipartite folding algorithm based on matrix representation. Heuristics are used to reduce the search space and to speed up the search processes. The algorithm has been implemented in C programming language on a SUN-4 workstation. The program was used to study several large PLAs of varying sizes. The experimental results show that in most cases the proposed algorithm finds optimal solution in a reasonable CPU time

Keywords

C language; VLSI; circuit layout CAD; logic CAD; logic arrays; C programming language; CPU time; LSI; SUN-4 workstation; VLSI; bipartite PLA folding; column bipartite folding algorithm; combinational functions; logic design; matrix representation; programmable logic arrays; search processes; search space; sequential logic; sparsity; Circuit synthesis; Combinational circuits; Computer languages; Large scale integration; Programmable logic arrays; Sequential circuits; Silicon; Sparse matrices; Very large scale integration; Workstations;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.251147

Filename

251147