No label defined (Q3801042)

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 4068238
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4068238

      Statements

      0 references
      1987
      0 references
      parallelity
      0 references
      SIMD
      0 references
      bibliography
      0 references
      complexity measures
      0 references
      model of parallel computers
      0 references
      network machine
      0 references
      single instruction stream multiple data stream
      0 references
      parallel RAM
      0 references
      circuits
      0 references
      Turing machines
      0 references
      parallel computation hypothesis
      0 references
      exercises
      0 references
      subject index
      0 references
      This book does not try to completely cover the whole area of parallel computation which is still too much in development. Large parts of the literature on parallel computation are not reflected here (like parallel algorithms for various specific problems, random parallel computation, relativizations) or are mentioned only very briefly (like the theory around NC). Instead the author restricts himself to clarify the foundations of parallel computation theory by discussing the problem: What are reasonable parallel computers and what are the right complexity measures to be used? The model of parallel computers used throughout the book is a network of processors (network machine) with modifiable structure, i.e., the interconnections are determined at runtime. The processors are RAMs with instruction sets varying according to our wishes from a restricted arithmetic up to sets of arbitrary polynomial time Turing-computable, functions. The most natural and most important complexity measures are time, space (number of registers used throughout a computation), wordsize and number of processors. Many variants of this model which is essentially a single instruction stream multiple data stream model are considered. It turns out that the popular shared memory parallel RAM is a submodel of the network machine of practically the same computational power as that of the network machine. Various simulations by fixed structure models (based on hypercubes, shuffle exchange, cube connected cycles, cube connected lines), circuits, Turing machines are studied, and, making use of Ajtai- Komlós-Szemerédi's parallel sorting network the author proves the existence of a ``feasible'' universal network which can simulate any network machine at modest costs. All these investigations are accompanied by the question of what the right parallel machines are. As in the case of sequential machines where all reasonable models are mutually polynomially time related the author uses the parallel computation hypothesis (PCH) as a criterion for a model to be reasonable. The PCH reads: Parallel time and Turing machine space are polynomially related. As P is not expected to be in SPACE(Pol(log n)) the PCH implies that P-complete problems like the circuit value problem do not allow exponentially faster computations by making use of parallel computations. A main objective of the book is to defend the unit cost hypothesis: The unit cost measure of time is ``valid'' for parallel processors. Under the unit cost measure of time each instruction would be charged with one time unit, even if it requires polynomial time to be computed by a Turing machine. The PCH supports the unit cost hypothesis in the following way. Since \[ network-TIME-WORDSIZE(T,W)\subseteq DSPACE(T(W+\log T)+S), \] where S is the space required for a Turing machine to compute a single instruction of a processor of the network, the PCH is still valid if W and S are polynomially bounded by T and the network time is understood to be unit cost. In a similar way the extended parallel computation thesis which relates hardware and time to space and reversals, respectively, is used to make precise the notion of a good parallel model and to defend the unit cost hypothesis. Finally, in connection with the alternating Turing machines a new parallel computation thesis valid also for unbounded fan-in circuits and sublogarithmic time is formulated: ``In a parallel machine with unbounded fan-in communication, time and address complexity are simultaneously equivalent to alternations and time on an alternating Turing machine, the former to within a constant, and the latter a polynomial.'' This new thesis coming from a comparison of alternating Turing machines with unbounded fan-in circuits shows that parallel time does not match alternating time if time and address complexity are considered simultaneously. This contrasts to the usual understanding of alternating time to be the right choice for ``parallel time'' which is suggested by the PCH. This book presents the foundations of parallel computation theory in a clear manner and will therefore be of interest for all people being interested in foundational work in computation theory. Those who want to use the book for graduate courses find some exercises at the end of each chapter. A reference list of 134 items and a good subject index make the book easily usable.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references