𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Impact of mixed-parallelism on parallel implementations of the Strassen and Winograd matrix multiplication algorithms

✍ Scribed by F. Desprez; F. Suter

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
277 KB
Volume
16
Category
Article
ISSN
1532-0626

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper we study the impact of the simultaneous exploitation of data‐ and task‐parallelism, so called mixed‐parallelism, on the Strassen and Winograd matrix multiplication algorithms. This work takes place in the context of Grid computing and, in particular, in the Client–Agent(s)–Server(s) model, where data can already be distributed on the platform. For each of those algorithms, we propose two mixed‐parallel implementations. The former follows the phases of the original algorithms while the latter has been designed as the result of a list scheduling algorithm. We give a theoretical comparison, in terms of memory usage and execution time, between our algorithms and classical data‐parallel implementations. This analysis is corroborated by experiments. Finally, we give some hints about heterogeneous and recursive versions of our algorithms. Copyright © 2004 John Wiley & Sons, Ltd.

📜 SIMILAR VOLUMES

A Higher-Order Compact Method in Space a
A Higher-Order Compact Method in Space and Time Based on Parallel Implementation of the Thomas Algorithm
✍ Alex Povitsky; Philip J. Morris 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 143 KB

In this study we propose a novel method to parallelize high-order compact numerical algorithms for the solution of three-dimensional PDEs in a space-time domain. For such a numerical integration most of the computer time is spent in computation of spatial derivatives at each stage of the Runge-Kutta

An efficient implementation of the finit
An efficient implementation of the finite-element time-domain algorithm on parallel computers using a finite-element tearing and interconnecting algorithm
✍ Umesh D. Navsariwala; Stephen D. Gedney 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB 👁 3 views

An efficient algorithm for implementing the finite-element ( ) time-domain FETD method on parallel computers is presented. An unconditionally stable implicit FETD algorithm is combined with the ( ) finite-element tearing and interconnecting FETI method. This domain decomposition algorithm con¨erges