Search
  Advanced Search
 
Journal search
Journal cover: COMPEL: The International Journal for Computation and Mathematics in Electrical and Electronic Engineering

COMPEL: The International Journal for Computation and Mathematics in Electrical and Electronic Engineering

ISSN: 0332-1649

Online from: 1982

Subject Area: Electrical & Electronic Engineering

Content: Latest Issue | icon: RSS Latest Issue RSS | Previous Issues

Options: To add Favourites and Table of Contents Alerts please take a Emerald profile

Previous article.Icon: Print.Table of Contents.Next article.Icon: .

latency 2 I/O-bandwidth 2D-array matrix multiplication algorithm


Document Information:
Title:latency 2 I/O-bandwidth 2D-array matrix multiplication algorithm
Author(s):A.K. Oudjida, (CDTA, El-Madania, Algiers), S. Titr, (CDTA, El-Madania, Algiers), M. Hamarlain, (CDTA, El-Madania, Algiers)
Citation:A.K. Oudjida, S. Titr, M. Hamarlain, (2002) "latency 2 I/O-bandwidth 2D-array matrix multiplication algorithm", COMPEL: The International Journal for Computation and Mathematics in Electrical and Electronic Engineering, Vol. 21 Iss: 3, pp.377 - 392
Keywords:Algorithms, Matrix structure
Article type:Research paper
DOI:10.1108/03321640210423298 (Permanent URL)
Publisher:MCB UP Ltd
Abstract:The emergence of the systolic paradigm in 1978 inspired the first 2D-array parallelization of the sequential matrix multiplication algorithm. Since then, and due to its attractive and appealing features, systolic approach has been gaining great momentum to the point where all 2D-array parallelization attempts were exclusively systolic. As good result, latency has been successively reduced a number of times (5N, 3N, 2N, 3N/2), where N is the matrix size. But as latency was getting lower, further irregularities were introduced into the array, making the implementation severely compromised either at VLSI level or at system level. The best illustrative case of such irregularities are the two designs proposed by Tsay and Chang in 1995 and considered as the fastest designs (3N/2) that have been developed so far. The purpose of this paper is twofold: we first demonstrate that N+vN/2 is the minimal latency that can be achieved using the systolic approach. Afterwards, we introduce a full-parallel 2D-array algorithm with N latency and 2N I/O-bandwidth. This novel algorithm is not only the fastest algorithm, but is also the most regular one too. A 3D parallel version with O(log N) latency is also presented.



Fulltext Options:

Login

Login

Existing customers: login
to access this document

Login


- Forgot password?
- Athens/Institutional login

Purchase

Purchase

Downloadable; Printable; Owned
HTML, PDF (420kb)Purchase

To purchase this item please login or register.

Login


- Forgot password?

Recommend to your librarian

Complete and print this form to request this document from your librarian


Marked list


Bookmark & share

Reprints & permissions