Item Details

The Nondeterministic Divide

Charlesworth, Arthur
Format
Report
Author
Charlesworth, Arthur
Abstract
The nondeterministic divide partitions a vector into two non-empty slices by allowing the point of division to be chosen nondeterministically. 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 components is only permitted during activations in which the vector parameters have unit length. The notion of a diva algorithm is formulated precisely as a diva call, a restricted call on a sequential procedure. Diva calls are proven to be intimately related to associativity. Numerous applications of diva calls are given and strategies are described for translating a diva call into code for a variety of parallel computers. Thus diva algorithms separate logical correctness concerns from implementation concerns. Note: Abstract extracted from PDF file via OCR
Language
English
Date Received
20121030
Published
University of Virginia, Institute for Parallel Computation, 1990
Published Date
1990
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online