DFS: A Simple to Write Yet Difficult to Execute Benchmark
DFS: A Simple to Write Yet Difficult to Execute Benchmark
复制标题
DFS：编写简单但执行困难的基准
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
A. Lumsdaine
中科院分区：
文献类型：
--
作者：
R. Murphy;Jonathan W. Berry;William C. McLendon;B. Hendrickson;Douglas P. Gregor;A. Lumsdaine
许多新兴应用程序都是建立在大型非结构化数据集上的，这些数据集表现出高度不规则（甚至几乎随机）的内存访问模式。示例包括信息学应用程序，以及通常由非结构化图的数据结构表示的其他问题。众所周知，这些应用程序对于传统体系结构执行（串行或并行）的挑战。此工作中提出的深度搜索（DFS）基准使用Boost Graph库在大型幂律图上进行深度优先搜索，代表“小世界”现象。所讨论的图显示了任何两个顶点（小直径很小）之间的平均距离很小，并且具有一些高度的顶点，并具有大量的低度顶点。诸如此类的图表出现在许多领域，包括网络，生物学，社交网络和数据挖掘。这些应用中的许多对研究人员至关重要，并且随着图形尺寸的增长，在传统机器上执行它们的挑战。这项工作中提出的基准是图理论中许多基本算法的基础，对于几种新兴应用至关重要，是记忆密集型的，并且在常规机器上表现出较差的性能。第2节定量地以独立的方式证明了基准的内存特性，表明它非常密集。第3节描述了基准的执行阶段。第4节给出了结论
Many emerging applications are built upon large, unstructured datasets that exhibit highly irregular (or even nearly random) memory access patterns. Examples include informatics applications, and other problems that are often represented by unstructured graph-based data structures. It is well known that these applications are challenging for conventional architectures to execute (either serially or in parallel). The depth first search (DFS) benchmark proposed in this work uses the boost graph library to perform a depth-first search on a large power-law graph, representing "small world" phenomena. The graph in question exhibits a small average distance between any two vertices, a small diameter, and has a few high-degree vertices with a large number of low-degree vertices. Graphs such as this appear in many fields, including networking, biology, social networks, and data mining. Many of these applications are of critical importance to researchers, and the challenge of executing them on conventional machines increases as the graph size grows. The benchmark proposed in this work is used as the basis for many fundamental algorithms in graph theory, is critical to several emerging applications, is memory intensive, and exhibits poor performance on conventional machines. Section 2 quantitatively demonstrates the memory characteristics of the benchmark in an architecture independent fashion, showing that it is extremely memory intensive. Section 3 describes the execution phases of the benchmark. And section 4 presents the conclusions