NDLI: Searching for the Optimal Data Partitioning Shape for Parallel Matrix Matrix Multiplication on 3 Heterogeneous Processors

Content Provider	IEEE Xplore Digital Library
Author	DeFlumere, A. Lastovetsky, A.
Copyright Year	2014
Description	Author affiliation: Sch. of Comput. Sci. & Inf., Univ. Coll. Dublin, Dublin, Ireland (DeFlumere, A.; Lastovetsky, A.)
Abstract	Parallel Matrix-Matrix Multiplication (MMM) is a fundamental part of the linear algebra libraries used by scientific applications on high performance computers. As heterogeneous systems have emerged as high performance computing platforms, the traditional homogeneous algorithms have been adapted to these heterogeneous environments. Although heterogeneous systems have been in use for some time, it remains an open problem of how to optimally partition data on heterogeneous processors to minimize computation, communication, and execution time. While the question of how to subdivide these MMM problems among heterogeneous processors has been studied, the underlying assumption of this prior study is that the data partition shape, the layout of the data within the matrix assigned to each processor, should be rectangular, i.e. that each processor should be assigned a rectangular portion of the matrix to compute. Our previous work in this area questioned the optimality of this traditional rectangular shape and studied this partition shape problem for two processors. In that work, we proposed a novel mathematical method for transforming partition shapes to decrease communication cost and an analytical technique for determining the optimal shape. In this work, we extend this technique to apply to three and more heterogeneous processors. While applying this method to two processors is relatively straightforward, the complexity grows immensely when considering three processors. With this complexity in mind, we propose a hybrid of experimental and analytical techniques. We postulate that a small number of partition shapes are potentially optimal, and perform extensive testing using a computer aided method to apply our previously developed analytical technique, without finding a counterexample. We identified six data partition shapes which are candidates to be the optimal three processor shape.
Starting Page	17
Ending Page	28
File Size	364444
Page Count	12
File Format	PDF
e-ISBN	9781479941162
DOI	10.1109/IPDPSW.2014.8
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-05-19
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Matrix Partitioning Program processors Transmission line matrix methods Shape High Performance Computing Computational modeling Software algorithms Parallel Matrix Multiplication Partitioning algorithms Finite element analysis Heterogeneous Computing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Partitioning for Parallel Matrix-Matrix Multiplication with Heterogeneous Processors: The Optimal Solution

A high performance sparse Cholesky factorization algorithm for scalable parallel computers

High Performance Computing for Finite Element in Cloud

Topology-Aware Optimization of Communications for Parallel Matrix Multiplication on Hierarchical Heterogeneous HPC Platform

Towards Optimal Matrix Partitioning for Data Parallel Computing on a Hybrid Heterogeneous Server

Determination of the optimal shape of matrix elements partitioning on three abstract heterogeneous processors

Column-based matrix partitioning for parallel matrix multiplication on heterogeneous processors based on functional performance models (2011)

On partitioning FEM graphs using diffusion

Simultaneous Input and Output Matrix Partitioning for Outer-Product--Parallel Sparse Matrix-Matrix Multiplication

Searching for the Optimal Data Partitioning Shape for Parallel Matrix Matrix Multiplication on 3 Heterogeneous Processors

Similar Documents

Partitioning for Parallel Matrix-Matrix Multiplication with Heterogeneous Processors: The Optimal Solution

A high performance sparse Cholesky factorization algorithm for scalable parallel computers

High Performance Computing for Finite Element in Cloud

Topology-Aware Optimization of Communications for Parallel Matrix Multiplication on Hierarchical Heterogeneous HPC Platform

Towards Optimal Matrix Partitioning for Data Parallel Computing on a Hybrid Heterogeneous Server

Determination of the optimal shape of matrix elements partitioning on three abstract heterogeneous processors

Column-based matrix partitioning for parallel matrix multiplication on heterogeneous processors based on functional performance models (2011)

On partitioning FEM graphs using diffusion

Simultaneous Input and Output Matrix Partitioning for Outer-Product--Parallel Sparse Matrix-Matrix Multiplication

Searching for the Optimal Data Partitioning Shape for Parallel Matrix Matrix Multiplication on 3 Heterogeneous Processors