Mixed-Mode Scheduling for Parallel LU Factorization of Sparse Matrices on the Reconfigurable HERA Computer

X. Wang and S.G. Ziavras (USA)


Reconfigurable architecture, SIMD/MIMDmixed-mode computing, Floating-point arithmetic,Parallel LU factorization, Bock-Diagonal-Borderedmatrices, Sparse matrices


HERA (HEterogeneous Reconfigurable Architecture) is an FPGA-based mixed-mode reconfigurable computing system that we have designed and implemented for the simultaneous execution of a variety of parallel processing modes. These modes are SIMD (Single-Instruction, Multiple-Data), MIMD (Multiple-Instruction, Multiple Data) and M-SIMD (Multiple-SIMD). Each processing element (PE) is centered on a single-precision IEEE 754 floating-point unit (FPU) and supports dynamic switching between SIMD and MIMD at runtime. Mixed-mode parallelism has the potential to best match the characteristics of subtasks in any application, thus resulting in sustained high performance. In this paper, we present our SIMD, MIMD and mixed-mode implementations on HERA of parallel LU factorization for sparse Block-Diagonal-Bordered (BDB) matrices. Experimental results with matrices of size up to 5000 x 5000 show that mixed-mode scheduling can improve the performance by up to 24.7% compared to the SIMD implementation and 22.2% compared to the MIMD implementation. We also show that HERA outperforms a commercial PC with a 2GHz Pentium IV processor for all the test matrices.

Important Links:

Go Back