Parallel circuit simulation using hierarchical relaxation

Described is a class of parallel algorithms for circuit simulation based on hierarchical relaxation that has been implemented on the Cedar multiprocessor. The Cedar machine is a reconfigurable, general-purpose supercomputer that was designed and implemented at the University of Illinois. A hierarchical circuit simulation scheme is developed to exploit the hierarchical organization of Cedar. The new algorithm and a number of key issues, such as multilevel circuit partitioning, data partitioning, cluster algorithm selection, and cluster algorithm implementation, are described. Performance results on a variety of different configurations of Cedar that illustrate the benefits of the hierarchical over the nonhierarchical approach are also presented