Y. S. Kuo
ABSTRACT
The folding of programmable logic array (PLA) is considered. We develop a heuristic algorithm for optimal block folding. The algorithm is based on the column intersection graph associated with the PLA. Then the techniques of graph partitioning and two-objective linear programming are applied. Test results will be demonstrated to show the effectiveness of the algorithm.
- 1.G. D. Hachtel, A. R. Newton and A. L. Sangiovanni-Vincentelli "An Algorithm for optimal PLA Folding", IEEE Trans on CAD of Integrated Ciucuits and Systems, Vol. CAD-i, No. 2, pp. 63-77, April 1982.Google Scholar
- 2.G. D. Hachtel, A. R. Newton and A. L. Sangiovanni-Vincentelli, "Techniques for Programmable Logic Array Folding", in Proc. of 19th Design Automation Conference, pp. 147-155, 1982. Google ScholarDigital Library
- 3.J. R. Egan and C. L. Liu, "Bipartite Folding and Partitioning of a PLA", IEEE Trans. on Computer-Aided Design, Vol. CAD-3, NO. 3, pp. 191-199, July 1984.Google Scholar
- 4.B. W. Kernighan and S. Lin, "An Effective Heuristic Procedure for Partitioning graphs", Bell System Technical Journal, pp. 291-307, Feb. 1970.Google ScholarCross Ref
- 5.T. C. Hu and Y. S. Kuo, "Optimum Reduction of Programmable Logic Array", in Proc. of 20th Design Automation Conference, pp. 553-558, 1983. Google ScholarDigital Library
- 6.T. C. Hu, Integer Programming and Network Flows. Reading, MA: Addison-Wesley, 1969.Google Scholar
- 7.D. E. Knuth, The Art of Computer Programming, Vol. 1/Fundamental Algorithms, Second Edition, Addison-Wesley, 1973. Google ScholarDigital Library
Index Terms
- A heuristic algorithm for PLA block folding
Recommendations
An efficient algorithm for bipartite PLA folding
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 ...
Bipartite Folding and Partitioning of a PLA
A more restricted definition of a PLA folding is introduced, which is called bipartite folding. The additional constraints of a bipartite folding force the resulting PLA to have a more uniform structure. This structure of a column bipartite folding is ...
Graph theoretic algorithms for the PLA folding problem
Graph theoretic properties of the PLA folding problem which not only give insight into the various folding problems but also provide efficient algorithms for solving the problems are presented. This work is based on the transformation of the PLA into ...
Comments