论文标题
迈向实现精确三角计数的客观指标
Towards an Objective Metric for the Performance of Exact Triangle Count
论文作者
论文摘要
图形算法的性能通常是根据每秒遍历边缘数量（TEP）来测量的。但是，对于诸如精确三角计数之类的图形操作，此性能指标是不足的。在三角计数中，与过去的图形挑战条目的结果所证明的，具有相似数量边缘的图形的执行时间可能明显不同。我们讨论了对图形操作的客观性能度量的需求以及这样的度量标准的所需特征，以便更准确地捕获执行的工作量与执行代码的硬件的功能之间的交互。以确切的三角算作为例，我们得出一个指标，该指标捕获了许多实现中某些技术如何改善性能。我们证明，我们提出的指标可用于评估和比较三角计数的多种方法，使用SIMD方法作为针对标量基线的案例研究。
The performance of graph algorithms is often measured in terms of the number of traversed edges per second (TEPS). However, this performance metric is inadequate for a graph operation such as exact triangle counting. In triangle counting, execution times on graphs with a similar number of edges can be distinctly different as demonstrated by results from the past Graph Challenge entries. We discuss the need for an objective performance metric for graph operations and the desired characteristics of such a metric such that it more accurately captures the interactions between the amount of work performed and the capabilities of the hardware on which the code is executed. Using exact triangle counting as an example, we derive a metric that captures how certain techniques employed in many implementations improve performance. We demonstrate that our proposed metric can be used to evaluate and compare multiple approaches for triangle counting, using a SIMD approach as a case study against a scalar baseline.
