Generation of symbolic layout in one-dimensional logic array (Q1109793)

The paper focuses on the ordering of the columns to minimize the necessary number of tracks in one-dimensional logic arrays. A column- orientation approach is used for this problem. Each net is converted into a complete graph (or clique). The weighted graph for a given netlist to be constructed using such topological transformation is unique. The necessary number of tracks can be evaluated by the cut of two seeds of ordering, left seed vertex and right seed vertex. Using this concept, the minimal track assignments can be found by minimizing the cut of the seed vertex. Additionally, a useful concept, overriding property is introduced. It determines the local optimal assignments for two or more columns with the above property. The minimum track numbers and optimal track assignments are obtained by finding the maximum cliques in the weighted graph and these theoretical clues are compared with experimental results. The experimental results indicate that this algorithm provides better solutions to finding the minimum number of tracks compared with Fujii's and Othuski's.