Fast 3D Block Parallelisation for the Matrix Multiplication Prefix Problem

For exploiting the power of supercomputers like the HLRB II cluster, developing parallel algorithms becomes increasingly important. The matrix prefix problem belongs to a class of issues lending themselves for parallelisation. We compare the tree-based parallel prefix scheme, which is adapted from a recursive approach, with a sequential multiplication scheme where only the individual matrix multiplications are parallelised. We show that this fine-grain approach outperforms the parallel prefix scheme by a factor of 2−3 and also leads to less memory requirements. Unlike the tree-based scheme, the fine-grain approach enables many options in the choice of the number of parallel processors and shows a better speedup performance when increasing the matrix sizes. The usage of the fine-grain approach in a quantum control algorithm instead of the coarse-grain approach allows us both to deal with systems of higher dimensions and to choose a finer discretisation.