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
      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

      Identifiers