An Efficient Datapath Placement Algorithm to Minimize Track Density Using Spectral Method
Gwang-Su Seong · Journal of the Institute of Electronics Engineers of Korea · 2000
In this paper, we propose an efficient datapath placement algorithm to minimize track density. Here, we consider each datapath element as a cluster, and merge the most strongly connected two clusters to a new cluster until only one cluster remains. As nodes in the two clusters to be merged are already linearly ordered respectively, we can merge two clusters with connecting them. The proposed algorithm produces circular linear ordering by connecting starting point and end point of the final cluster, and n different linear ordering by cutting between two contiguous elements of the circular linear ordering. Among the n different linear ordering, the linear ordering to minimize track density is final solution. In this paper, we show and utilize that if two clusters are strongly connected in a graph, the inner product of the corresponding vectors mapped in d-dimensional space using spectral method is maximum. Compared with previous datapath placement algorithm GA/S , the proposed algorithm gives similar results with much less computation time.