Name Last modified Size Description
Parent Directory -
build/ 16-Aug-1997 18:22 -
The RAW benchmarks for single source shortest path (ssp), multiplicative shortest path (spm) and transitive closure (tc) specialize both the algorithm and the topology of the input graph. In each case we generate computation elements for each node of the input graph and then use the RawCS generator to connect these elements in the same topology as the problem input graph. For the shortest path problems the computation element is a circuit that finds the minimum of its inputs. For the transitive closure problem the computation element is an AND function across its inputs. With the exception of ssp64-mesh, each of the graph benchmark cases is randomly generated with a maximum node in-degree of eight, and an average in-degree of four. For more details read Solving graph problems with dynamic computation structures, by Jonathan Babb, Matthew Frank, and Anant Agarwal.