Speedup improvement on general connectivity computation byalgorithmic techniques and parallel processing

摘要

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