Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Graph500 is a competition for supercomputers that uses a different benchmark "Traversed Edges Per Second", which is supposed to measure some notion of the communication bandwidth ability of the computer.
However, I don't understand how this benchmark works since there doesn't seem to be a basic explanation on the site. At a basic level, how does TEPS work, and why?
The benchmark measures the performance of some very simple graph traversal algorithms on very large graphs. These algorithms need to be executed in parallel in order to take advantage of the supercomputers' parallel computation architecture.
The benchmark's algorithms themselves do not attempt to completely solve any practical problem, but they are typical of code which will form part of such solutions. The techniques used by benchmark writers to speed up their benchmarks will therefore also be of use in speeding up solutions to real-world problems.
Graph traversal problems, by their nature, are tricky to efficiently compute in parallel. A typical solution involves creating some kind of fringe (or work-list) of already-processed nodes and to follow each edge from each node in that fringe in some order to identify not-yet-processed nodes and add them to the fringe for later processing.
The order in which the fringe is traversed is important, and varies from algorithm to algorithm. But doing any traversal algorithm in parallel presents coordination issues.
Since the underlying data structure is a graph, not a tree, there will be multiple paths to any given node. Edges in the fringe will often connect back to nodes already processed, and these nodes must not be processed again; otherwise, the traverse will never terminate. In an undirected graph, edges can be followed from either end, so it's guaranteed that every node in the fringe will be in an edge which connects back to a previously processed node: the edge that was used to add the node to the fringe. (An edge which points back to a previously traversed node is called a back link.)
In addition, it's very likely that multiple nodes in the current fringe connect to the same as-yet-unprocessed node. This new node has not yet been processed, but it must only be added to the fringe once. (These edges are called cross links.) The graphs in the TEPS benchmarks have not been cleaned, so it's also possible for two nodes to be connected with more than one edge, or even for an edge to connect a node to itself.
So the algorithm needs to maintain information, at least a single bit but typically a bit more, which allows the processing loop to decide whether to add the node to the fringe.
At a high level, the traverse can be done in parallel by dividing the nodes in the fringe between different processing threads executing on different cores or processors. But it's not trivial for memory to be accessed at the same time by multiple processors. There must be some type of communications channel which the data flows through, and it's not practical to connect every bank of memory to every processor. Typically, each processor (or small group of processors) will be directly connected to a high-speed associative cache which contains a copy of recently referenced memory regions; these various caches need to be synchronised with each other (in the case that two processors are consulting the same datum) and with the memory itself. (That's a bit of a simplification, since there are often multiple levels of caches.)
If you could divide the problem up so that different processes were working on disjoint parts of the graph, coordination would be relatively simple. That's how large matrix computations are usually handled; the matrices are split into rectangular regions which can be (mostly) processed independently of each other. But graphs do not exhibit the same planar regularity. Edges fly around the entire graph and so multiple processors are constantly having to access data recently or even concurrently modified by different processors.
That's a lot of data moving around inside the supercomputer. Most of the work is more or less invisible to the programmer, since the "hardware" (or microcode) takes care of many of the synchronisation details. But the hardware cannot be aware of the details of the program being executed, and it is often the case that the programmer needs to interact with the caches and communications channels in order to minimize synchronisation overhead. Different computer architectures have different mechanisms for implementing this interaction, and the speed of a program will depend on the underlying data architecture and the skill of the programmer in arranging for the right data to be available in the right place before it is actually needed.
Another synchronisation problem is inherent in the irregularity of the graph data structure. In a matrix, it is likely that two rectangular regions of the same size will take roughly the same amount of time to process, making it relatively easy to divide the various computations equally between the available processors. This is not the case with graphs. You can divide the fringe into equally-sized subsets, but the number of unique descendant nodes in each subset will probably vary wildly. Real-life graphs do have clusters and concentration points (hot spots), but nothing in the data structure reveals this. It's discovered when a part of the graph turns out to require enormous computational resources, or practically none. So more interprocessor coordination is required in order to ensure that all the processors always have something to do.
In short, a good parallel solution will require both a carefully-designed high-level interprocess communication architecture as well as algorithms which can take advantage of whatever underlying data flow architecture is available on the hardware. These issues are much more apparent in graph algorithms than in more regular mathematical computations, which is why it was considered important to have a benchmark suite which specifically addresses graph algorithms.
There is a brief high-level overview in the second section of the TEPS document (which is where most of this information comes from), so I've just added a few glosses based on the comment stream to the original question.
To start with, the benchmark suite does not start with a tree. It starts with a large graph, and each benchmarked task constructs a tree, which is a connected subset of the graph.
As indicated by the benchmark overview, the benchmark consists of six phases, three of which are timed to produce the benchmark metric:
The benchmark randomly generates a large list of weighted edges. The number of such edges in the list is defined by the problem size. An algorithm is provided for this step, because just using a uniform random number generator to produce the pair of nodes for each edge would not produce a realistic graph. The algorithm specifies a particular non-uniformity, with parameters, so that all benchmark runs should produce graphs with similar shapes. (The weights, however, are selected uniformly in the interval (0, 1).)
The specified algorithm produces clusters whose node identifiers are themselves numerically clustered, and whose edges are clustered in the edge list. That's not realistic, and it could be exploited to artificially speed up processing. So the benchmark requires that the node identifiers be randomly shuffled, and then that the edge list itself be randomly shuffled, all of which should destroy exploitable shuffling.
A graph is completely specified by a list of edges, but a sequential edge list is an awful data structure to work with. So the first timed processing step turns the edge list into whatever graph data structure the benchmarker feels is convenient for their architecture and algorithms. The TEPS specification places no requirements on the datastructure, but it does require that every subsequent benchmark task (of which there are 128) start with exactly the same graph datastructure and nothing more. Thus, any information collected during one benchmark task cannot be recycled to speed up subsequent tasks. This preprocessing step is timed, because otherwise it might be used to offload computations specific to the tasks to be solved. Thus, the cost of the preprocessing step is amortised over the other tasks.
Once the graph has been preprocessed, 64 nodes are randomly selected to be used as root nodes for each of the following tasks. This is obviously not a very time-consuming problem, but the benchmark does require that the nodes be selected randomly from the set of nodes with at least one edge. (Since the edges were generated randomly, the number of edges connecting to each node will vary. In theory, it's possible that a random graph be so concentrated that there are fewer than 64 connected nodes. In practice, it's hard to imagine this actually happening, but the document does define what is to be done in that case. (Use the connected nodes no matter how few there are, rather than regenerating the entire graph.)
Generating the random list after preprocessing means that the preprocessing cannot be biased in favour of the root nodes which will be used.
The bulk of the benchmark consists of two straight-forward tasks, which can be found in any introductory text on graph algorithms (at least in their single-threaded form). Indeed, they will show up over and over again as the textbook advances, because they are basic building blocks for many of the more complicated graph problems.
The first of these algorithmic tasks is to construct a breadth-first search tree from each of the 64 root nodes. I understand from the comments that the word "search" is confusing, so I want to note that it is possible to search for more than one object. (In Casablanca, when Capt. Renault says "Major Strassen has been shot. Round up the usual suspects," he does not expect the door-to-door search to terminate when the first dissident is found.) In this case, the search is for all the nodes which are connected to the selected root node (which is likely to be less than all of the nodes in the graph, because no attempt was made to generate a connected graph).
The result of each of the search tasks is not just a list of nodes. It's a tree which can be traversed from the root in order to reach each of those nodes. (It's represented as a list of pairs $<node, parent>$.) Because this tree is created with a breadth-first traverse, the path length from the root to each node is minimal; in other words, the tree is well-balanced. This fact is useful in many algorithms which start with the construction of such a tree, so this benchmark is definitely evaluating a (part of) real-world algorithms.
The tree can be used to verify that all the nodes in the set are reachable from the root node in the original graph. The TEPS benchmark does not require full verification, I suppose because it would require an independent implementation of the same algorithm, but partial verification is at least possible and mandatory. But only the search is timed.
Once all 64 search trees have been constructed, the same 64 root nodes are used to find single-source shortest path trees. This is a very similar problem, which also constructs a tree from each root node to all connected nodes, but the tree is much more constrained, because it uses the edge weights which were generated in step 2. Each path to a node in the shortest-path tree must have the minimum total weight of all possible paths paths from the original graph.
If all the edge weights were equal, it would be same as the first problem, but since the weights are assigned randomly, this is not going to be the case. The solution to this problem also involves something like a breadth-first search, but instead of being organised into successive fringes, in which each fringe can be checked in arbitrary order, the traverse must check the fringe in order by increasing total weight. This creates additional communications issues when the algorithm is executed in parallel; a single-threaded solution would typically use a priority queue to produce a stream of nodes sorted by their distance from the root, but centralising node traverse between different processors through a single priority queue would create an intense memory hotspot. (I don't know the best solution to this problem.)
Again, each of the 64 subtasks in this step is timed.
Finally, the benchmark is computed. The assumption is that the cost of a particular subtask should be proportional to the number of edges traversed during the execution of that subtask, so the task implementations must record both the time taken and the number of edges traversed. As mentioned above, because the graph is undirected, it's expected that each edge will be traversed twice, once from each of the nodes it connects, unless the edge connects a node to itself. To correct for this difference, edges which connect two nodes are counted as "half-edges" (That is, each such edge, which is likely the vast majority of the edges traversed, is counted as 0.5 instead of 1.) The raw time and the edge count are converted into a rate by dividing the edge count by the time, giving a measure of edges per time interval; there will be 129 of these which are consolidated using a harmonic mean (and several other statistics specified in the document).
