Portable relaxation-based circuit simulation on MIMD machines

Parallel CAD programs have been extensively reported in the literature. Unfortunately, they are not widely used in industry. One reason for this lack of use is that they are usually developed for a specific machine and are not easily ported to other parallel machines. While code portability is straightforward, the issue of performance portability is a rather difficult one to resolve. This dissertation attempts to bridge the gap between code portability and performance portability for a numerically intensive application program, specifically circuit simulation. Waveform relaxation is an effective algorithm to simulate large digital circuits designed today and is used as the main simulation algorithm. The parallel processing issues under investigation include circuit partitioning, task granularity modification, scheduling and allocation. The difficulty of addressing these issues by using generic parallel processing techniques is that circuit simulation problems tend to have highly irregular computational structures. The use of high-level waveforms generated from logic or timing simulators is introduced as a way of improving both speed and performance portability. Speedups of three to ten have been achieved using a combination of high-level information and event-driven waveform relaxation on eight processors as compared to the sequential program. Based on the knowledge acquired during the course of this research, an advanced framework for portable parallel circuit simulation is proposed. By taking the machine characteristics and the input stimuli into consideration, this research serves as a major step forward in performance portability.U of I OnlyETDs are only available to UIUC Users without author permissio