Parallel prefix computation on extended multi-mesh network.

DOI10.1016/S0020-0190(02)00317-4MaRDI QIDQ1853159zbMATH OpenFDO

Authors Prasanta K. Jana, B. Damodara Naidu, Shailendra Kumar, Monish Arora, Bhabani P. Sinha

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0020-0190(02)00317-4

zbMATH Keywords

Associative binary operationMulti-mesh networkParallel algorithmPrefix computationTime complexity

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Review text

A parallel algorithm for prefix computation of \(N=n^{4}\) elements on an \(n\times n\) extended multi-mesh network is presented. The network is a modified version of an earlier multi-mesh network with a 4-regular structure. The algorithm takes \(O(N^{1/4})\) time on \(N\) processors (\(13N^{1/4}-5\) communication steps and \(\log N+4\) arithmetic/logic steps).

Recommendations

• Fast parallel algorithm for prefix computation in multi-mesh architecture
• Efficient parallel prefix algorithms on multiport message-passing systems
• scientific article; zbMATH DE number 3876584
• \(O(\log n)\) numerical algorithms on a mesh with wormhole routing
• scientific article; zbMATH DE number 1185587

Cites work

• A new network topology with multiple meshes
• Depth-size trade-offs for parallel prefix computation
• Faster optimal parallel prefix sums and list ranking
• scientific article; zbMATH DE number 4155887 (Why is no real title available?)
• Limited width parallel prefix circuits
• OPTIMAL PARALLEL PREFIX ON MESH ARCHITECTURES
• Parallel Prefix Computation
• Parallel Solution of Recurrence Problems

Cited in

(4)

• Efficient parallel prefix algorithms on multiport message-passing systems
• Scaling multiple addition and prefix sums on the reconfigurable mesh.
• scientific article; zbMATH DE number 1185587 (Why is no real title available?)
• Fast parallel algorithm for prefix computation in multi-mesh architecture

This page was built for publication: Parallel prefix computation on extended multi-mesh network.

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