Dynamic partitioning for concurrent waveform relaxation-based circuit simulation

A new dynamic circuit partitioning algorithm for the waveform relaxation method is presented. Such an algorithm dynamically changes the partitioning as the simulation proceeds through the simulation interval. The proposed algorithm is suitable for implementation on a multicomputer. Experimental results show that the algorithm decreases the runtimes for circuits where good static partitioning is difficult to find. This is true both in the ideal case, i.e., when communication overhead for the repartitioning is not included and the load is distributed as evenly as possible among the processors, and in the real-world case, when all the partitioning overhead and load imbalance are included in actual measured run times.