  We propose a new graph-theoretic benchmark in this paper. The benchmark is
developed to address shortcomings of an existing widely-used graph benchmark.
We thoroughly studied a large number of traditional and contemporary graph
algorithms reported in the literature to have clear understanding of their
algorithmic and run-time characteristics. Based on this study, we designed a
suite of kernels, each of which represents a specific class of graph
algorithms. The kernels are designed to capture the typical run-time behavior
of target algorithms accurately, while limiting computational and spatial
overhead to ensure its computation finishes in reasonable time. We expect that
the developed benchmark will serve as a much needed tool for evaluating
different architectures and programming models to run graph algorithms.
