Solving the gate packing problem using a concurrent network

The layout problem of gate matrices and one-dimensional logic arrays is composed of two major tasks: to find a permutation of gates which minimises the number of tracks required and to layout/pack gates based on the ordering. A parallel algorithm is presented which can pack n gates within O(1) time, whereas the conventional near-optimum algorithm needs O(n/sup 2/) time. The simulation results show that the increase of the problem size does not degrade the solution quality.<>