Title :
An efficient 0-1 linear programming for optimal PLA folding
Author :
Raahemifar, Kaamran ; Ahmadi, Majid
Author_Institution :
Electr. & Comput. Eng. Dept., Ryerson Polytech. Univ., Toronto, Ont., Canada
fDate :
6/23/1905 12:00:00 AM
Abstract :
In this paper we propose a new 0-1 integer linear formulation for optimal PLA folding. An efficient heuristic algorithm is presented which finds optimal PLA folding in polynomial time. The algorithm finds the maximum matching of a given green-edge graph. Then, directions are assigned to each selected edge to minimize certain objective function on a red-edge graph. The existing alternating cycles are verified and eliminated. Finally, the coordinates of each interconnection of PLA are computed. Test results show that the algorithm is efficient and gives the optimal solutions for most cases
Keywords :
VLSI; graph theory; high level synthesis; integrated circuit layout; linear programming; programmable logic arrays; 0-1 integer linear formulation; 0-1 linear programming; green-edge graph; heuristic algorithm; interconnection coordinates computation; maximum matching; objective function minimisation; optimal PLA folding; polynomial time; red-edge graph; Boolean functions; Equations; Heuristic algorithms; Linear programming; Logic design; Logic functions; Programmable logic arrays; Testing; Topology; Very large scale integration;
Conference_Titel :
Electronics, Circuits and Systems, 2001. ICECS 2001. The 8th IEEE International Conference on
Print_ISBN :
0-7803-7057-0
DOI :
10.1109/ICECS.2001.957416
