Premium
Waveform relaxation on parallel processors
Author(s) -
Smart David W.,
Trick Timothy N.
Publication year - 1988
Publication title -
international journal of circuit theory and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.364
H-Index - 52
eISSN - 1097-007X
pISSN - 0098-9886
DOI - 10.1002/cta.4490160408
Subject(s) - waveform , computer science , parallel computing , relaxation (psychology) , multiprocessing , overhead (engineering) , speedup , parallelism (grammar) , algorithm , psychology , social psychology , telecommunications , radar , operating system
Waveform relaxation algorithms for the simulation of digital MOS circuits exhibit natural parallelism which can be exploited on parallel processors. This paper addressed the question of how much the circuit simulation run‐time can be reduced by using this natural parallelism. the parallel waveform relaxation methods examined in this paper are based on the Gauss‐Seidel and Gauss‐Jacobi relaxation methods, and window‐level and time‐point level parallelization strategies. the different methods are evaluated using an actual multiprocessor implementation of the algorithms, and by using a program which estimates speed‐ups, neglecting overhead. the method giving the best performance is a function of the circuit being simulated and the number of processors used. When sufficiently many processors are available, the Gauss‐Jacobi method with time‐point pipelining offers the best speed‐up potential. Speed‐ups close to one order of magnitude should be possible using this method for 1000‐node for 32 processors.