A numerical engine for distributed sparse matrices
Jacob White, Ricardo Telichevesky · 1994
In fields as diverse as electronic circuit design, fluid dynamics, and structural analysis, the behavior of complex systems is modeled by large, sparsely coupled systems of differential equations. Numerical solution of such systems is computationally expensive because even the most efficient algorithms evaluate and factor large sparse matrices hundreds or thousands of times, and on most general purpose computers sparse matrix operations are inefficient. Part of the problem is that accessing sparse matrix elements is complicated, resulting in a poor utilization of computational resources. The irregular non-zero pattern makes it very difficult to parallelize the operations; and the non-uniform data access time makes pipelining very inefficient. This thesis suggests exploiting the infrequent change in matrix structure by developing a symbolic compiler, and a special purpose parallel computer that uses compiler clues to accelerate sparse data access. The compiler combines partitioning, scheduling, and storage allocation algorithms in order to exploit locality of reference, achieve a high degree of parallelism, and simplify the operand access in the sparse matrix, which in turn insures efficient pipelining. Each processing element contains a specialized datapath consisting of multiple interleaved memories and functional units, and a microprogrammed control unit capable of initiating several datapath operations per clock cycle. Extensive behavioral and register transfer level (RTL) emulation of the execution of SIMLAB, a circuit simulation program, suggests that the combination of these hardware and software techniques yield a high degree of utilization of computational resources both in the assembly of circuit equations using device models and in its associated sparse matrix solution. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)