[SYSTEMDS-2285] Sparsity estimators for matrix multiply chains

• Type: Epic
• Status: Closed
• Priority: Major
• Resolution: Done
• Fix Version/s: SystemDS 2.0
• Epic Name: Sparsity estimators for matrix multiply chains
• Assignee: Matthias Boehm
• Reporter: Matthias Boehm
• Created: 29/Apr/18 04:54
• Updated: 14/May/21 10:44
• Resolved: 14/May/21 10:44

Description

This epic aims to introduce a framework for different sparsity estimators for matrix multiplications and chains of matrix multiplications. These estimators are important for (1) advanced optimizers that depend on sparsity estimates, and (2) runtime operations in terms of effective output format choices and output preallocation. Initially, we will compare existing estimators and extend them as needed.

Sub-Tasks

• Framework abstraction for sparsity estimators: Closed
• Basic average and worst-case sparsity estimators: Closed
• Sparsity estimators based on density maps: Closed
• Sparsity estimators based on hashing: Closed
• Sparsity estimators based on dynamic density maps: Closed
• Sparsity estimators based on layered graphs: Closed
• Exploiting structural properties for corrections: Closed
• Sparsity estimators based on boolean matrix multiply: Closed
• Sparsity estimators based on matrix histograms: Closed
• Sparsity estimator based on sampling: Closed
• Improve matrix histogram via zero-count exploitation: Closed
• Improve performance of density map estimator: Closed
• Utililty for determining exact output nnz w/o matrix product: Closed
• Extended matrix histograms for matrix product chains: Closed
• Support for operations other than mm: Closed
• Performance features sparsity estimators: Closed
• Integrate MNC sparsity estimator in mmchain optimization: Closed