Parallel Algorithms: Third DIMACS Implementation Challenge, October 17-19, 1994Sandeep Nautam Bhatt American Mathematical Soc., 1. jan. 1997 - 162 sider This volume is the result of the Third DIMACS Implementation Challenge that was conducted as part of the 1993-94 Special year on Parallel Algorithms. The Implementation Challenge was formulated in order to provide a forum for a concerted effort to study effective algorithms for combinatorial problems and to investigate opportunities for massive speed-ups on parallel computers. The challenge invluded two problem areas for research study: tree searching, algorithms, used in game search and combinatorial optimization, for example, and algorithms for sparse graphs. Participants at sites in the US and Europe undertook projects from November 1993 through October 1994. The workshop was held at DIMACS in November 1994. Participants were encouraged to share test results, to rework their implementations considering feedback at the workshop, and to submit a final report for the proceedings. Nine papers were selected for this volume. |
Innhold
Parallel implementation of algorithms for finding connected components | 23 |
Connected components algorithms for meshconnected parallel computers | 40 |
MARIOS PAPAEFTHYMIOU AND JOSEPH RODRIGUE 69 | 59 |
Finding friendsoffriends clusters quickly | 69 |
A practical comparison of Nbody algorithms | 81 |
Parallel algorithms for geometric dominance problems | 97 |
The Socrates massively parallel chess program | 117 |
Concurrent data structures and load balancing strategies for parallel | 141 |
Andre utgaver - Vis alle
Vanlige uttrykk og setninger
abort adjacency matrix applications B&B algorithm Barnes-Hut Barnes-Hut algorithm cells chess program Cilk cluster coarse-grain program comparison-pair Computer Chess Computer Science concurrent write operations connected components algorithms data structure dense graphs DIMACS dimensions edge list efficient execution Figure finding connected components fine-grain program game tree global phase grid implementation input points interactions Jamboree search kd-tree label d(u load balancing load balancing strategies MasPar MasPar MP-1 massively parallel mesh multipole negamax number of edges number of nodes number of processors O(log optimal parallel algorithms parallel computer parallel programs parent partial locking particle performance physical processor planar PMTA pointer doubling pointer jumping PRAM algorithm priority queues problem Proc random graphs remote edges rooted star running search algorithm sequential algorithms serial shortest-paths Socrates sparse graphs speedup StarTech Subsection techniques tertiary graphs thread total number transposition table treap tree loop tree search update vertex vertices