Document Type

Technical Report

Publication Date

9-12-1994

Abstract

The nondeterministic divide partitions a vector into two non-empty slices by allowing the point of division to be chosen nondeterministically; i.e., by the underlying implementation. Support for high-level divide-and-conquer programming provided by the nondeterministic divide is investigated. A diva algorithm is a recursive divide-and-conquer sequential algorithm on one or more vectors of the same range, whose division point for a new pair of recursive calls is chosen nondeterministically before any computation is performed and whose recursive calls are made immediately after the choice of division point; also, access to vector parameters is only permitted during activations in which these parameters have unit length. The notion of a diva algorithm is formulated as a diva call, a restricted call on a sequential procedure. Numerous applications of diva calls are given. Diva calls are shown to support both reasoning based on strong induction and hierarchical reasoning based on binding free variables. Asymptotically optimal strategies are described for translating a diva call into code for a variety of parallel computers. Diva calls separate logical correctness concerns from implementation concerns. Numerous advantages of diva calls over the use of general reduction operators are identified.

Share

COinS