Group: algorithms
Topic: algorithmic complexity analysis
Topic: models of parallel computation
Topic: nondeterministic processing
Topic: parallel control statements
Topic: specification and design of distributed systems
Topic: vector processing
 
Subtopic: complexity of parallel algorithm
Quote: measure performance in parallel computing by "work", the total number of operations, and "depth", the longest chain of sequential dependencies [»blelGE3_1996]
 Subtopic: nondeterministic
Quote: a nondeterministic algorithm generates tasks for all branches; easy way to parallel programming [»reynJC5_1970, OK]
 Subtopic: data parallel
Quote: parallel algorithms are usually dataparallel; i.e., they perform parallel operations for each instance of a collection of values [»blelGE3_1996]
 Subtopic: automatic parallelization
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
Quote: several readers can share the work of processing messages; with several writers, messages can be generated anywhere [»huntJG1_1979]
 Subtopic: shared memory
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; parallelmeet over all paths (PMOP) is equivalent to parallel bitvector maximal fixed point [»knooJ5_1995]
 Quote: unidirectional bitvector analysis used for liveness, reaching def, defuse, code motion, partial dead code, and strength reduction; works for parallel programs [»knooJ5_1995]
 Subtopic: implementation
QuoteRef: brinP11_1978 ;;936 implements semaphores/message buffer, resource scheduler, process arrays, abstract data types, monitor, coroutines, path expressions
 Subtopic: scheduling algorithm
Quote: equipartition partitions processors evenly among unfinished jobs and preempts on job completion; two competitive; optimal [»edmoJ5_1999]
 Subtopic: distributed algorithm
Quote: Recycler multiprocessor garbage collector with low pause times; loosely synchronized, concurrent reference counting; local, concurrent cycle detection [»bacoDF6_2001]
 Subtopic: processor tree
Quote: algorithm for parallel merge sort with a tree of processes [»dewiDJ_1982, OK]
 Subtopic: cycle detection
Quote: local, concurrent cycle detection in O(n) with reduced constant factors
 Subtopic: broadcast
Quote: with highbandwidth broadcast can perform a parallel nestedloops, relational join algorithm [»dewiDJ_1982]
 Subtopic: synchronization
Quote: Euclid's algorithm synchronizes two cyclic processes such that both variables remain positive [»dijkEW_1977]

Related Topics
Group: algorithms (6 topics, 94 quotes)
Topic: algorithmic complexity analysis (10 items)
Topic: models of parallel computation (33 items)
Topic: nondeterministic processing (19 items)
Topic: parallel control statements (12 items)
Topic: specification and design of distributed systems (14 items)
Topic: vector processing (15 items)
