Cited By
View all- Bae SShinn TTakaoka T(2016)An efficient parallel algorithm for the maximum convex sum problemProceedings of the Australasian Computer Science Week Multiconference10.1145/2843043.2843049(1-7)Online publication date: 1-Feb-2016
Efficient parallel algorithms for the maximum subarray problem
Pages 45 - 50
Abstract
Parallel algorithm design is generally hard. Parallel program verification is even harder. We take an example from the maximum subarray problem and and show those two problems of design and verification.
The best known communication steps for a mesh architecture for the maximum subarray problem is 2n − 1. We give a formal proof for the parallel algorithm on the mesh architecture based on Hoare logic. The main part of the proof is to establish several space/time invariants with three indices (i; j; k). The indices (i; j) pair specifies the invariant at the (i; j) grid point of the mesh and k specifies the k-th step in the computation. Then ignoring additive constants, the communication steps are improved to (3/2)n steps and finally n steps, which is optimal in terms of communication steps. Also the first algorithm is implemented on a Blue Gene parallel computer and performance measurements conducted are shown.
References
[1]
C. E. R. Alves, E. N. Caceres and S. W. Song: BPS/CGM Algorithms for Maximum Subsequence and Maximum Subarray, EuroPVM/MPI 2004, LNCS 3241: 139--146 (2004)
[2]
Jon Louis Bentley: Perspective on Performance. Commun. ACM 27(11): 1087--1092 (1984)
[3]
Sung Eun Bae: Sequential and Parallel Algorithms for Generalized Maximum Subarray Problem. Ph. D thesis. University of Canterbury (2007)
[4]
Sung Eun Bae and Tadao Takaoka: Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem. I-SPAN 2004: 247--253 (2004)
[5]
C. A. R. Hoare. An axiomatic basis for computer programming. Communications of the ACM, 12(10):576--580 (1969).
[6]
S. Owicki and D. Gries: Verifying properties of parallel programs: An axiomatic approach. Communications of the ACM, 19(5):279--285 (1976)
[7]
Tadao Takaoka: Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication. Electr. Notes Theor. Comput. Sci. 61: 191--200 (2002)
[8]
Hisao Tamaki, Takeshi Tokuyama: Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication. SODA 1998: 446--452 (1998)
Index Terms
- Efficient parallel algorithms for the maximum subarray problem
Recommendations
Improved Algorithms for the K-Maximum Subarray Problem
The maximum subarray problem is to find the contiguous array elements having the largest possible sum. We extend this problem to find K maximum subarrays. For general K maximum subarrays where overlapping is allowed, Bengtsson and Chen presented $$O\...
A Parallel Maximum Subarray Algorithm on GPUs
SBAC-PADW '14: Proceedings of the 2014 International Symposium on Computer Architecture and High Performance Computing WorkshopThis paper presents a parallel algorithm for the maximum sub array problem implemented on a machine with GPUs. Given a sequence of numbers, the maximum subsequence is a contiguous subsequence with maximum sum. The maximum sub array problem is a 2-D ...
Abstract state machines capture parallel algorithms: Correction and extension
We consider parallel algorithms working in sequential global time, for example, circuits or parallel random access machines (PRAMs). Parallel abstract state machines (parallel ASMs) are such parallel algorithms, and the parallel ASM thesis asserts that ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- Australian Comp Soc: Australian Computer Society
- Datacom: Datacom
- IBM Research - Australia: IBM Research - Australia
- SERL: Software Engineering Research Lab, Auckland University of Technology
- Auckland University of Technology
- Univ. of Western Sydney: University of Western Sydney
- The University of Auckland, New Zealand
- CORE - Computing Research and Education
- Colab: Collaboratory of Design & Creative Technologies, Auckland University of Technology
- IITP: Institute of IT Professionals New Zealand
Publisher
Australian Computer Society, Inc.
Australia
Publication History
Published: 20 January 2014
Qualifiers
- Research-article
Acceptance Rates
AusPDC '14 Paper Acceptance Rate 7 of 14 submissions, 50%;
Overall Acceptance Rate 26 of 48 submissions, 54%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 214Total Downloads
- Downloads (Last 12 months)83
- Downloads (Last 6 weeks)10
Reflects downloads up to 18 Jan 2025
Other Metrics
Citations
Cited By
View all- Bae SShinn TTakaoka T(2016)An efficient parallel algorithm for the maximum convex sum problemProceedings of the Australasian Computer Science Week Multiconference10.1145/2843043.2843049(1-7)Online publication date: 1-Feb-2016
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in