Balanced computation of two-dimensional transforms on a tree machine

DOI10.1016/0893-9659(90)90134-WMaRDI QIDQ2277820zbMATH OpenOpenAlexFDO

Authors Allen Gorin, Louis Auslander, Allan J. Silberger

Publication date 1990

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0893-9659(90)90134-w

zbMATH Keywords

balanced parallel algorithmtree-structured parallel computer

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Distributed algorithms (68W15)

Review text

This paper describes the idea of a balanced parallel algorithm, and then applies it to the design and analysis of 2D transforms on a tree- structured parallel computer. A balanced algorithm is one that is written as a sequence of separate computation and communication stages, which is furthermore sized so that these stages require equal time.

Recommendations

• A Maximally Parallel Balancing Algorithm for Obtaining Complete Balanced Binary Trees
• Two-dimensional FFT algorithms on hypercube and mesh machines
• Banyan models for the parallel implementation of the fast Fourier transform algorithm
• Publication:4720677
• Tree-based parallel algorithm design

Cites work

• Dynamically Restructurable Fault-Tolerant Processor Network Architectures
• Efficient detection of determinacy races in cilk programs

Cited in

(1)

• The balanced binary tree technique on mesh-connected computers

This page was built for publication: Balanced computation of two-dimensional transforms on a tree machine

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277820)