Code for heterogeneous computing of product of two sparse matrices
Input: Sparse matrices A and B
Output: Sparse matrix C
set matrix C to ∅
for all a i ∗ in matrix A in parallel do
for all a ik in row a i ∗ do
for all b k j in row b k ∗ do
value ← a ik b k j
if c i j #∈ c i ∗ then
insert ( c i j ← v alue ) to c i ∗
else
c i j ← c i j + value
end if
end for
end for
end for
Input: Sparse matrices A and B
Output: Array o f f set
{1. Set FLOP vector} for i ← 0 to m in parallel do flop [ i ] ← 0 for j ← r pts A [ i ] to r pts A [ i + 1] do rnz ← r pts B [ cols A [ j] + 1] − r pt B [ cols A [ j]] flop [ i ] ← flop [ i ] + rnz end for end for { 2 . Assign rows to thread } flop ps ← ParallelPrefixSum ( flop ) sum flop ← flop ps [ m ] tnum ← omp_get_max_threads () a v e flop ← sum flop / tnum o f f set[0] ← 0 for tid ← 1 to tnum in parallel do o f f set [ tid ] ← lowbnd ( flop ps , a v e flop ∗ tid ) end for o f f set [ t num ] ← m
Input: Sparse matrices A and B
Output: Sparse matrix C
off set ← RowsToThreads ( A, B ) {Determine hash-table size for each thread} tnum ← omp_get_max_threads () for tid ← 0 to tnum in parallel do size t ← 0 for i ← o f f set [ t id] to o f f set [ t id + 1] do size t ← max ( size t , flop [ i ] ) end for {Required maximum hash-table size is N col } size t ← min ( N col , size t ) {Return minimum 2 n so that 2 n > size t } size t ← lowest_p2 ( size t ) end for Symbolic ( r pts C , A, B ) Numeric ( C, A, B )