A heuristic algorithm for ordering the columns in one-dimensional logica arrays

The authors focus on the ordering of the columns to minimize the necessary number of tracks in one-dimensional logic array. They use a column-orientation approach to this problem. Each net is converted into a complete graph (or clique). The weighted graph using such topological transformation is unique. The necessary number of tracks can be evaluated by the cut of the two seeds of orderings, the left seed vertex and the right seed vertex. The authors find the minimal track assignments by minimizing the cut of the seed vertex. Additionally, a useful concept called the overriding property is introduced. It determines the local optimal assignments for two or more columns with the above property. The author´s algorithm works well with either a uni- or bidirectional approach to select the seed of ordering. Results obtained by the proposed algorithm and the simulated annealing approach are compared