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

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
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00000232
Contributor : Frédéric Suter <>
Submitted on : Friday, September 16, 2005 - 11:51:37 AM
Last modification on : Wednesday, August 7, 2019 - 12:18:05 PM

Links full text

Identifiers

Collections

Citation

Frédéric Suter, Frédéric Desprez. Impact of mixed-parallelism on parallel implementations of the Strassen and Winograd matrix multiplication algorithms. Concurrency and Computation: Practice and Experience, Wiley, 2004, 16 (8), pp.771-797. ⟨10.1002/cpe.791⟩. ⟨inria-00000232⟩

Share

Metrics

Record views

343