A Compositional Framework for Developing Parallel Programs on Two-Dimensional Arrays

Computations on two-dimensional arrays such as matrices and images are one of the most fundamental and ubiquitous things in computational science and its vast application areas, but development of efficient parallel programs on two-dimensional arrays is known to be hard. In this paper, we propose a...

Full description

Saved in:
Bibliographic Details
Published in:International journal of parallel programming 2007-12, Vol.35 (6), p.615-658
Main Authors: Emoto, Kento, Hu, Zhenjiang, Kakehi, Kazuhiko, Takeichi, Masato
Format: Article
Language:English
Subjects:
Algorithms
Arrays
Design
Informatics
Information science
Libraries
Nickel
Optimization
Parallel processing
Science
Studies
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Computations on two-dimensional arrays such as matrices and images are one of the most fundamental and ubiquitous things in computational science and its vast application areas, but development of efficient parallel programs on two-dimensional arrays is known to be hard. In this paper, we propose a compositional framework that supports users, even with little knowledge about parallel machines, to develop both correct and efficient parallel programs on dense two-dimensional arrays systematically. The key feature of our framework is a novel use of the abide-tree representation of two-dimensional arrays. The presentation not only inherits the advantages of tree representations of matrices where recursive blocked algorithms can be defined to achieve better performance, but also supports transformational development of parallel programs and architecture-independent implementation owing to its solid theoretical foundation - the theory of constructive algorithmics. [PUBLICATION ABSTRACT]
ISSN:0885-7458
1573-7640
DOI:10.1007/s10766-007-0043-4