Efficient parallel algorithms for the maximum subarray problem
Tadao Takaoka · 2014
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.