Chaotic linear system solvers in a variable-grain data-driven multiprocessor system.

摘要

Linear systems are important problems in many scientific applications. While asynchronous methods are effective solutions to linear systems, they are difficult to realize due to the chaotic behavior of the algorithms. In this paper, we investigate the implementation as well as the performance of an asynchronous method, namely chaotic relaxation, in our Variable-grain TaggedToken Data-flow (VTD) System. We compare asynchronous methods with synchronous methods executed on both the fine-grain and the coarse-grain execution models. New high-level dataflow language constructs axe introduced in order to express asynchronous operations. A new firing rule that deviates from the single assignment rule of functional languages is proposed to support the implementation of asynchronous computations in the VTD system. In addition to the conventional speedup measure, we then define new performance measurements, called Growth Factor, Scalability Factor, and Robustness to characterize the system performance from the machine and application viewpoints. Simulation results indicate that asynchronous methods axe more efficient than synchronous methods and that the coarse-grain execution mode is more efficient that the fine-grain execution mode in our VTD system.