A Cloud-Friendly Communication-Optimal Implementation for Strassen's Matrix Multiplication Algorithm

Jie ZHOU; Feng YU

doi:10.1587/transinf.2015EDP7065

A Cloud-Friendly Communication-Optimal Implementation for Strassen's Matrix Multiplication Algorithm

Jie ZHOU, Feng YU

Full Text Views

0

Share
Cite this

Summary :

Due to its on-demand and pay-as-you-go properties, cloud computing has become an attractive alternative for HPC applications. However, communication-intensive applications with complex communication patterns still cannot be performed efficiently on cloud platforms, which are equipped with MapReduce technologies, such as Hadoop and Spark. In particular, one major obstacle is that MapReduce's simple programming model cannot explicitly manipulate data transfers between compute nodes. Another obstacle is cloud's relatively poor network performance compared with traditional HPC platforms. The traditional Strassen's algorithm of square matrix multiplication has a recursive and complex pattern on the HPC platform. Therefore, it cannot be directly applied to the cloud platform. In this paper, we demonstrate how to make Strassen's algorithm with complex communication patterns “cloud-friendly”. By reorganizing Strassen's algorithm in an iterative pattern, we completely separate its computations and communications, making it fit to MapReduce programming model. By adopting a novel data/task parallel strategy, we solve Strassen's data dependency problems, making it well balanced. This is the first instance of Strassen's algorithm in MapReduce-style systems, which also matches Strassen's communication lower bound. Further experimental results show that it achieves a speedup ranging from 1.03× to 2.50× over the classical Θ(n³) algorithm. We believe the principle can be applied to many other complex scientific applications.

Publication: IEICE TRANSACTIONS on Information Vol.E98-D No.11 pp.1896-1905

Publication Date: 2015/11/01

Publicized: 2015/07/27

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2015EDP7065

Type of Manuscript: PAPER

Category: Fundamentals of Information Systems

Authors

Jie ZHOU
Zhejiang University
Feng YU
Zhejiang University

Keyword

parallel algorithms, communication-optimal, Strassen's matrix multiplication, cloud computing, MapReduce

Cite this

Copy

Jie ZHOU, Feng YU, "A Cloud-Friendly Communication-Optimal Implementation for Strassen's Matrix Multiplication Algorithm" in IEICE TRANSACTIONS on Information, vol. E98-D, no. 11, pp. 1896-1905, November 2015, doi: 10.1587/transinf.2015EDP7065.
Abstract: Due to its on-demand and pay-as-you-go properties, cloud computing has become an attractive alternative for HPC applications. However, communication-intensive applications with complex communication patterns still cannot be performed efficiently on cloud platforms, which are equipped with MapReduce technologies, such as Hadoop and Spark. In particular, one major obstacle is that MapReduce's simple programming model cannot explicitly manipulate data transfers between compute nodes. Another obstacle is cloud's relatively poor network performance compared with traditional HPC platforms. The traditional Strassen's algorithm of square matrix multiplication has a recursive and complex pattern on the HPC platform. Therefore, it cannot be directly applied to the cloud platform. In this paper, we demonstrate how to make Strassen's algorithm with complex communication patterns “cloud-friendly”. By reorganizing Strassen's algorithm in an iterative pattern, we completely separate its computations and communications, making it fit to MapReduce programming model. By adopting a novel data/task parallel strategy, we solve Strassen's data dependency problems, making it well balanced. This is the first instance of Strassen's algorithm in MapReduce-style systems, which also matches Strassen's communication lower bound. Further experimental results show that it achieves a speedup ranging from 1.03× to 2.50× over the classical Θ(n³) algorithm. We believe the principle can be applied to many other complex scientific applications.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2015EDP7065/_p

Copy

@ARTICLE{e98-d_11_1896,
author={Jie ZHOU, Feng YU, },
journal={IEICE TRANSACTIONS on Information},
title={A Cloud-Friendly Communication-Optimal Implementation for Strassen's Matrix Multiplication Algorithm},
year={2015},
volume={E98-D},
number={11},
pages={1896-1905},
abstract={Due to its on-demand and pay-as-you-go properties, cloud computing has become an attractive alternative for HPC applications. However, communication-intensive applications with complex communication patterns still cannot be performed efficiently on cloud platforms, which are equipped with MapReduce technologies, such as Hadoop and Spark. In particular, one major obstacle is that MapReduce's simple programming model cannot explicitly manipulate data transfers between compute nodes. Another obstacle is cloud's relatively poor network performance compared with traditional HPC platforms. The traditional Strassen's algorithm of square matrix multiplication has a recursive and complex pattern on the HPC platform. Therefore, it cannot be directly applied to the cloud platform. In this paper, we demonstrate how to make Strassen's algorithm with complex communication patterns “cloud-friendly”. By reorganizing Strassen's algorithm in an iterative pattern, we completely separate its computations and communications, making it fit to MapReduce programming model. By adopting a novel data/task parallel strategy, we solve Strassen's data dependency problems, making it well balanced. This is the first instance of Strassen's algorithm in MapReduce-style systems, which also matches Strassen's communication lower bound. Further experimental results show that it achieves a speedup ranging from 1.03× to 2.50× over the classical Θ(n³) algorithm. We believe the principle can be applied to many other complex scientific applications.},
keywords={},
doi={10.1587/transinf.2015EDP7065},
ISSN={1745-1361},
month={November},}

Copy

TY - JOUR
TI - A Cloud-Friendly Communication-Optimal Implementation for Strassen's Matrix Multiplication Algorithm
T2 - IEICE TRANSACTIONS on Information
SP - 1896
EP - 1905
AU - Jie ZHOU
AU - Feng YU
PY - 2015
DO - 10.1587/transinf.2015EDP7065
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2015
AB - Due to its on-demand and pay-as-you-go properties, cloud computing has become an attractive alternative for HPC applications. However, communication-intensive applications with complex communication patterns still cannot be performed efficiently on cloud platforms, which are equipped with MapReduce technologies, such as Hadoop and Spark. In particular, one major obstacle is that MapReduce's simple programming model cannot explicitly manipulate data transfers between compute nodes. Another obstacle is cloud's relatively poor network performance compared with traditional HPC platforms. The traditional Strassen's algorithm of square matrix multiplication has a recursive and complex pattern on the HPC platform. Therefore, it cannot be directly applied to the cloud platform. In this paper, we demonstrate how to make Strassen's algorithm with complex communication patterns “cloud-friendly”. By reorganizing Strassen's algorithm in an iterative pattern, we completely separate its computations and communications, making it fit to MapReduce programming model. By adopting a novel data/task parallel strategy, we solve Strassen's data dependency problems, making it well balanced. This is the first instance of Strassen's algorithm in MapReduce-style systems, which also matches Strassen's communication lower bound. Further experimental results show that it achieves a speedup ranging from 1.03× to 2.50× over the classical Θ(n³) algorithm. We believe the principle can be applied to many other complex scientific applications.
ER -