English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Sparse general matrix multiplication (SpGEMM) is a fundamental building blockin numerous scientific applications. One critical task of SpGEMM is to computeor predict the structure of the output matrix (i.e., the number of nonzeroelements per output row) for efficient memory allocation and load balance,which impact the overall performance of SpGEMM. Existing work either preciselycalculates the output structure or adopts upper-bound or sampling-based methodsto predict the output structure. However, these methods either take muchexecution time or are not accurate enough. In this paper, we propose a novelsampling-based method with better accuracy and low costs compared to theexisting sampling-based method. The proposed method first predicts thecompression ratio of SpGEMM by leveraging the number of intermediate products(denoted as FLOP) and the number of nonzero elements (denoted as NNZ) of thesame sampled result matrix. And then, the predicted output structure isobtained by dividing the FLOP per output row by the predicted compressionratio. We also propose a reference design of the existing sampling-based methodwith optimized computing overheads to demonstrate the better accuracy of theproposed method. We construct 625 test cases with various matrix dimensions andsparse structures to evaluate the prediction accuracy. Experimental resultsshow that the absolute relative errors of the proposed method and the referencedesign are 1.56\% and 8.12\%, respectively, on average, and 25\% and 156\%,respectively, in the worst case.

Predicting the Output Structure of Sparse Matrix Multiplication with Sampled Compression Ratio