Matrix Multiplication Algorithm Selection with Support Vector Machines

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 2015
Accession Number
AD1003136

Entities

People

  • Armando Fox
  • David Eliahu
  • James Demmel
  • Omer Spillinger

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Air Platforms
  • Autonomy
  • Human Systems

DTIC Thesaurus Topics

  • Accuracy
  • Algebra
  • Algorithms
  • Boundaries
  • Classification
  • Computer Languages
  • Computer Science
  • Computers
  • Electrical Engineering
  • High Performance Computing
  • Information Science
  • Linear Algebra
  • Machine Learning
  • Statistics
  • Supervised Machine Learning
  • Three Dimensional
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Linear Algebra
  • Neural Network Machine Learning.
  • Parallel and Distributed Computing.

Technology Areas

  • AI & ML
  • AI & ML - Neural Networks
  • Space