Graph Traversal
From View
Contents |
Description
Graph Traversal applications must traverse a number of objects and examine characteristics of those objects. Applications typically involve indirect lookups and little computation.
Uniprocessor Mapping
An algorithm that requires little processing and sequential access of successive graph nodes may be equivalent to pointer chasing, without much chance for more efficient processing. Often, though, the reality is better: there may be locality in accesses to the graph, or there might be some processing per node that can reduce the effective cost of finding later nodes.
Parallel Mapping
Elaboration
Variations:
o Searching: Searching generally requires a single (or even partial) pass through the objects
Auto-Tuning:
none known.
How Current Computer Architectures Fail:
o Many searching algorithms end up depending almost entirely on random memory access latency.
