Graph Traversal

From View

Jump to: navigation, search

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.

Personal tools