Transitive closure on the imagine stream processor
Gorden Griem, Leonid Oliker · eScholarship (California Digital Library) · 2003
The increasing gap between processor and memory speeds is a well-known problem in modern computer architecture. The Imagine system is designed to address the processormemory gap through streaming technology. Stream processors are best-suited for computationally intensive applications characterized by high data parallelism and producerconsumer locality with minimal data dependencies. This work examines an efficient streaming implementation of the computationally intensive Transitive Closure (TC) algorithm on the Imagine platform. We develop a tiled TC algorithm specifically for the Imagine environment, which efficiently reuses streams to minimize expensive off-chip data transfers. The implementation requires complex stream programming since the memory hierarchy and cluster organization of the underlying architecture are exposed to the Imagine programmer. Results demonstrate that limited performance of TC is achieved primarily due to the complicated datadependencies of the blocked algorithm. This work is an ongoing effort to identify classes of scientific problems wellsuited for streaming processors. 1. ALL-PAIRS SHORTEST PATH The problem of finding all the shortest paths in a graph is one of the most important optimizations in operations research as it arises in many applications, most notably network routing and distributed computing. Let G = (V, E) be a directed graph with N nodes and M arcs, where the length of the arc(i,j) is denoted by lij. The Transitive Closure (TC), or all-pairs shortest path, computes the length of a minimum-length path between all pairs of nodes. The classical sequential approach for solving this problem is the O(N 3) dynamic programming methodology of the Floyd-Warshall algorithm [5] shown Figure 1. The algorithm consisting of three nested loops where the inner two can be parallelized and executed in any order. A matrix length of dimension N × N holds the best known shortest distances between every pair of nodes. Initially, length(i, j) contains the length of arc (i, j) if it exists, 0 if i = j, and ∞ other-