daphne-project / daphne-project/daphne

Matrix Multiplication Chain Optimization

Open
#412 0 comments 0 reactions 1 assignee Claimed by @Hiebl View on GitHub
Dominant language
C++
Stars
81
Forks
83
PR merge metrics
No merged PRs in 30d

Description

Matrix multiplications are at the heart of most ML algorithms and can be very expensive in terms of runtime. Computational complexity is heavily influneced by how the product is parenthesized. Because the operation is associative, the result obtained will be the same for all possible parenthesized matrix products, if the order of matrices is not change.

For example, for a matrix `X` with dimensions 1000x1000 and a vector 'V' with dimensions 1000x1 the matrix multiplication `Y = (t(X) @ X) @ V;` would result in 2002 MFLOPs of calculation, while `Y = t(X) @ (X @ V);` would result in only 4 MFLOPs of calculation being necessary.

The DaphneDSL parser shall initially create MatMulOps, while a new compiler pass shall identify matrix chains, perform the textbook dynamic programming algorithm to find the minimum cost for the full sequence and rewrite the matrix chain accordingly.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.