Implementation and Analysis of Block Dense Matrix Decomposition on Network-on-Chips

The decomposition of a dense matrix into lower and upper triangular matrices is an important linear algebra kernel that used in scientific and engineering applications. To decompose large matrices efficiently, the matrix is divided into sub-matrices as blocks. The block matrix decomposition is introduced for parallel hardware platforms, e.g. supercomputers, multicore processors and GPUs. Recently, the Network-on-Chip (NoC) paradigm is proposed as a promising multicore architecture for future Chip Multiprocessors (CMPs) with hundreds or even thousands of cores. The communication bottleneck of traditional bus or crossbar based on-chip interconnect is alleviated in the NoC architecture. However, the implementation and analysis of parallel block matrix decomposition in a NoC platform has not been well addressed. We design an NoC platform based on state-of-the-art systems. A block matrix decomposition algorithm is implemented on the NoC platform. Evaluation results are presented using a cycle accurate full system simulator. We achieve parallel efficiency of 74.8% with a 64-node NoC, which outperforms other three multiprocessor systems (30.5%, 67% and 50% respectively). We also analyzed the impact of block size, cache behavior and network pressure of the platform.