Topic: parallel algorithms

topics > computer science > Group: parallel processing


algorithmic complexity analysis
models of parallel computation
non-deterministic processing
parallel control statements
specification and design of distributed systems
vector processing

Subtopic: complexity of parallel algorithm up

Quote: measure performance in parallel computing by "work", the total number of operations, and "depth", the longest chain of sequential dependencies [»blelGE3_1996]

Subtopic: non-deterministic up

Quote: a non-deterministic algorithm generates tasks for all branches; easy way to parallel programming [»reynJC5_1970, OK]

Subtopic: data parallel up

Quote: parallel algorithms are usually data-parallel; i.e., they perform parallel operations for each instance of a collection of values [»blelGE3_1996]

Subtopic: automatic parallelization up

Quote: use pointer and region interfaces to automatically parallelize divide and conquer programs; decreases complexity while increasing the compiler's efficiency; excellent performance

Subtopic: multiple readers, writers up

Quote: several readers can share the work of processing messages; with several writers, messages can be generated anywhere [»huntJG1_1979]

Subtopic: shared memory up

Quote: efficient, unidirectional bitvector analysis for parallel programs with shared memory; optimal for interference [»knooJ5_1995]
Quote: bitvector analysis can ignore the various interleavings of parallel components; parallel-meet over all paths (PMOP) is equivalent to parallel bitvector maximal fixed point [»knooJ5_1995]
Quote: unidirectional bitvector analysis used for liveness, reaching def, def-use, code motion, partial dead code, and strength reduction; works for parallel programs [»knooJ5_1995]

Subtopic: implementation up

QuoteRef: brinP11_1978 ;;936 implements semaphores/message buffer, resource scheduler, process arrays, abstract data types, monitor, coroutines, path expressions

Subtopic: scheduling algorithm up

Quote: equi-partition partitions processors evenly among unfinished jobs and preempts on job completion; two competitive; optimal [»edmoJ5_1999]

Subtopic: distributed algorithm up

Quote: Recycler multiprocessor garbage collector with low pause times; loosely synchronized, concurrent reference counting; local, concurrent cycle detection [»bacoDF6_2001]

Subtopic: processor tree up

Quote: algorithm for parallel merge sort with a tree of processes [»dewiDJ_1982, OK]

Subtopic: cycle detection up

Quote: local, concurrent cycle detection in O(n) with reduced constant factors

Subtopic: broadcast up

Quote: with high-bandwidth broadcast can perform a parallel nested-loops, relational join algorithm [»dewiDJ_1982]

Subtopic: synchronization up

Quote: Euclid's algorithm synchronizes two cyclic processes such that both variables remain positive

Related Topics up

Group: algorithms   (6 topics, 94 quotes)

Topic: algorithmic complexity analysis (10 items)
Topic: models of parallel computation (33 items)
Topic: non-deterministic processing (19 items)
Topic: parallel control statements (12 items)
Topic: specification and design of distributed systems (14 items)
Topic: vector processing
(15 items)

Updated barberCB 3/06
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.