Please use this identifier to cite or link to this item:
|Speedup improvement on general connectivity computation by algorithmic techniques and parallel processing
|Shen, Zhaoxuan,Song, Jianjian,Zhuang, Wenjun (1997). Speedup improvement on general connectivity computation by algorithmic techniques and parallel processing. Proceedings of the Conference on High Performance Computing on the Information Superhighway, HPC Asia'97 : 724-727. ScholarBank@NUS Repository.
|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.
|Proceedings of the Conference on High Performance Computing on the Information Superhighway, HPC Asia'97
|Appears in Collections:
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.