Tree machines and divide-and-conquer algorithms

F.J. Peters

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

4 Citaten (Scopus)

Samenvatting

A tree machine consists of a number of processors (each with its own memory) mutually connected via communication branches so as to form a binary tree. Two processors may communicate only via a common communication link. Such a tree machine is a completely general, concurrent processing engine and can be used for problems decomposed in a hierarchical way. Implementation of divide-and-conquer algorithms on a tree machine is discussed. Algorithms for which a tree machine can be effective are characterized. Examples are shown and it is proven that for a class of k-dimensional divide-and-conquer algorithms the running time may be reduced from 0(N logk−1 N) on a sequential machine to 0(kN) on a tree machine.
Originele taal-2Engels
TitelCONPAR 81: Conference on Analysing Problem Classes and Programming for Parallel Computing (Nürnberg, Germany, June 10-12, 1981)
RedacteurenW. Brauer, P. Brinch Hansen, C. Moler, W. Händler
Plaats van productieBerlin
UitgeverijSpringer
Pagina's25-36
Aantal pagina's12
ISBN van elektronische versie978-3-540-38715-2
ISBN van geprinte versie3-540-10827-0, 978-3-540-10827-6
DOI's
StatusGepubliceerd - 1981

Publicatie series

NaamLecture Notes in Computer Science
Volume111
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'Tree machines and divide-and-conquer algorithms'. Samen vormen ze een unieke vingerafdruk.

Citeer dit