Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/113239
Title: Speedup improvement on general connectivity computation by algorithmic techniques and parallel processing
Authors: Shen, Zhaoxuan
Song, Jianjian 
Zhuang, Wenjun 
Issue Date: 1997
Citation: 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.
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.
Source Title: Proceedings of the Conference on High Performance Computing on the Information Superhighway, HPC Asia'97
URI: http://scholarbank.nus.edu.sg/handle/10635/113239
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

48
checked on Nov 8, 2019

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.