Student Posters Repository

Hierarchical matrix (H-matrix) is an approximated form to represent N*N correlations o N objects. H-matrix construction is done by partitioning a matrix into submatrices, followed by calculating element values of these submatrices. This research is proposes implementations of the matrix partitioning using task parallel languages, Cilk Plus and Tascell. The matrix partitioning is divided into two steps: cluster tree construction by dividing objects into clusters hierarchically, and block cluster tree construction by finding out all cluster pairs that satisfy an admissiblity condition from the cluster tree. Because the cluster tree constructed and traversed in these steps is unpredictably unbalanced, it is expected that we can parallelize these both steps efficiently using task parallel languages. To obtain sufficient parallelism in the cluster tree construction, I not only execute recursive calls in parallel, but also parallelized inside of each recursive step. In the block cluster tree construction, I assigned each workers its own space to store the cluster pairs without using locks. As a result, comparing to a sequential implementation in C, I achieved up to a 12.2-fold speedup by Cilk Plus and a 14.5-fold speedup using Tascell.