Efficient Parallel Algorithms for the Maximum Subarray Problem

Takaoka, Tadao

Parallel algorithm design is generally hard. Parallel program verification is even harder. We take an example from the maximum subarray problem 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.

Cite as: Takaoka, Tadao (2014). Efficient Parallel Algorithms for the Maximum Subarray Problem. In Proc. Twelfth Australasian Symposium on Parallel and Distributed Computing (AusPDC 2014) Auckland, New Zealand. CRPIT, 152. Javadi, B. and Garg, S. K. Eds., ACS. 45-50

(from crpit.com) (local if available)