Improved Parallel Cell Placement Algorithm Using Bounded Edge-Width Routing Model
Fawaz S. Al–Anzi, Khaled Al-Zamel · International Journal of Computers and Applications · 2000
In this paper, an improved parallel cell pair-interchange placement algorithm implementation using the SIMD computational model is presented. The improved implementation of the algorithm makes use of converting the broadcast step to a p-p packet routing problem, using a bounded edge-width communication model. We show that this model is feasible in the context of the cell placement problem. We also show that by using p-p packet routing in the broadcast step, we can reduce the run time from 0(pN) to 2y/N, where p and N are the average cell connectivity and the circuit size, respectively.