A new approach for the forward and backward substitutions of parallel solution of sparse linear equations based on dataflow architecture

摘要

The authors present a novel parallel computational method for solving the forward and backward substitutions (F/B) of sparse linear equations. The architectural model is a multiprocessor hypertube based on the MIT Tagged Token Dataflow Architecture (TTDA). Communication overhead is considered. Differences of the operating time units with respect to subtraction, multiplication, and division are modeled. A processor scheduling algorithm is introduced. In the algorithm, a highly sparse operational sequence matrix C is developed. From the C matrix, the minimal completion time, the critical path, and the scheduling of the processors for the proposed parallel F/B can be determined. A detailed explanation of the implementation of the TTDA in the proposed method is provided. A number of power systems have been examined, and a number of scenarios have been simulated to test the performance of the proposed method. The results are presented and discussed.