Matrix Multiplication Algorithm Selection with Support Vector Machines

We present a machine learning technique

for the algorithm selection problem, specifically

focusing on algorithms for dense matrix multiplication.

Dense matrix multiplication is a core component

of many high-performance computing and machine

learning algorithms [1], but the performance of matrix

multiplication algorithms can vary significantly based

on input parameters and hardware architecture. We

build performance models for multiple machines using

support vector machines (SVMs) [2] and show that only

a sparse exploration of the input space is sufficient to

accurately predict the best choice of algorithm over a

wide range of possible inputs.  We find that by using this

classifier-based approach to choose the best algorithm

to use at runtime, we are able to achieve as much as

a 26% increase in average performance over choosing

a single algorithm a priori. This is within 1.5% of the

performance possible with a perfect algorithm selector.

 

Technical Report