Speedup improvement on general connectivity computation by algorithmic techniques and parallel processing

Abstract

Algorithmic techniques and parallel processing are proposed to speed up general connectivity computation, which was shown to be effective but time-consuming. A new algorithm, called Concurrent Group Search Algorithm (CGSA), will divide N(N-1)/2 vertex pairs into N-1 groups. Within each group, general connectivities of all pairs can be calculated concurrently. Our placement results show that this technique can provide speedup of up to 12 times for one circuit. In addition, since each group is independent of the others, group computations are parallelized on a 16-node IBM SP2. Speedup of 14 times over its serial counterpart is observed. Combining the two approaches could result in the total speedup of up to 170 times, reducing CPU time from over 200 hours to 1.2 hour for a circuit. This new development makes it more practical to apply our general connectivity concept to large industrial design within short time period.