No label defined (Q4401026)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1182929
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1182929 |
Statements
2 March 1999
0 references
parallel random access machine
0 references
geometric searching
0 references
geometric optimization
0 references
0.8575950264930725
0 references
0.8332074284553528
0 references
The goal of parallel algorithm design is to develop parallel computational methods that run very fast with as few processors as possible, and there is an extensive literature of such algorithms for computational geometry problems. There are several different parallel computing models, and in order to maintain a focus in this chapter, we describe results in the parallel random access machine (PRAM) model, which is a synchronous parallel machine model in which processors share a common memory address space (and all inter-processor communication takes place through this shared memory). Although it does not capture all aspects of parallel computing, it does model the essential properties of parallelism. Moreover, it is a widely-accepted model of parallel computation, and all other reasonable models of parallel computation can easily simulate a PRAM. The PRAM model is subdivided into submodels based on how one wishes to handle concurrent memory access to the same location. The Exclusive-Read, Exclusive-Write (EREW) variant does not allow for concurrent access. The Concurrent-Read, Exclusive Write (CREW) variant permits concurrent memory reads, but memory writes must be exclusive. Finally, the Concurrent-Read, Concurrent-Write (CRCW) variant allows for both concurrent memory reading and writing, with concurrent writes being resolved by some simple rule, such as having an arbitrary member of a collection of conflicting writes succeed. One can also define randomized versions of each of these models (``rand-EREW'', etc.), where in addition to the usual arithmetic and comparison operations, each processor can generate a random number from 1 to \(n\) in one step. In Section 36.1 we give a brief discussion of general techniques for parallel geometric algorithm design. We then partition the research in parallel computational geometry into problems dealing with convexity, arrangements and decompositions, proximity, geometric searching, and visibility, envelopes, and geometric optimization. For the entire collection see [Zbl 0890.52001].
0 references