Tightly-coupled multithreaded computation of a power flow analysis algorithm

In this research, we designed a multithreaded parallel algorithm for a power flow analysis algorithm on multicore computers. The original algorithm is highly sequential. From an analysis, it has limited parallelism in a sequence of task phases. We invented a parallelization technique called asynchronous software pipelining to transform a sequence of tightly-coupled inner loops within a sequential loop into a parallel loop to achieve effective speedup. The parallel loop is to be executed on multicore computers. Synchronization transformations were devised and applied to reduce and equalize communication loads of tightly-coupled task phases in iterations of multiple threads. More task phase overlapping is achieved with a direction-reversing transformation to hide more communication latencies in addition. As a result, iterations divided in multiple threads can be executed in a compact schedule with little synchronization waiting latencies. Experimental results show that the parallel algorithm has little extra execution overhead and much reduced waiting latencies, and thus achieves effective speedup.