Many-Core Graph Workload Analysis - heirman.net

1 Many-Core Graph Workload AnalysisStijn EyermanIntel CorporationKontich, HeirmanIntel CorporationKontich, Du BoisIntel CorporationKontich, B. FrymanIntel CorporationHillsboro, OR, HurIntel CorporationHillsboro, OR, Graph applications have specific characteristics thatare not common in other application domains and thereforerequire thorough Analysis to guide future Graph processinghardware design. In this paper, we analyze multiple graphapplications on current multi and Many-Core processors, andprovide conclusions and recommendations for future designs.

2 Werestate well-known characteristics of Graph applications, such asa low compute to memory ratio and irregular memory accesspatterns, but we also provide new important insights on executinggraph applications on Many-Core main novel observations are (i) some memory streams doshow locality, while others show no locality, (ii) thread imbalancebecomes a major problem with many threads, and (iii) manythreads are required to saturate high-bandwidth memories. Thefirst observation calls for a selective memory access policy, whereaccesses with locality are cached and prefetched, while accesseswithout locality can remain uncached to save cache capacity, andcan fetch only one element from memory instead of a full cacheline to save on memory bandwidth.

3 The last two observationsare contradicting: more threads are needed, but they are notused efficiently due to thread imbalance. Our recommendationis therefore to thoroughly revise the Graph Analysis algorithmsto provide more scalable parallelism to be able to exploitthe potential of Many-Core architectures with high-bandwidthmemory. In addition, providing a few high-performance corescan speed up sections with low Terms Graph applications, Workload Analysis , Many-Core processorsI. INTRODUCTIONG raph applications for analyzing big data sets are gainingimportance.

4 Many data sets can be represented as graphs,where each vertex corresponds to an object and each edgerepresents a relation between two objects. Examples are socialnetworks, road networks, physics models and co-preferencegraphs. These graphs can be very large with millions to billionsof vertices and a multiple thereof of edges. Furthermore, thereality modeled by these graphs changes quickly, so the graphsneed to be constantly updated, after which the Analysis has torun again, ideally presenting results ( , recommendations)in real time.

5 Therefore, researchers and industry are lookingat developing high performing Graph Analysis software andhardware [9], [11], [14], [21], [25]. Graph applications are different from the conventional high-performance scientific applications in that they are highlyirregular [18]. This is because graphs are inherently sparse:the number of edges is a small fraction of the total amount ofpossible connections. Therefore, the edges are not representedas a sparse adjacency matrix, but instead as a list of neighborsfor each vertex. This list of neighbors has no regularity,causing scattered accesses all over the Graph data behavior ruins memory locality and the predictabilityof memory accesses and branch outcomes.

6 Therefore, caches,prefetchers and branch predictors have a low hit rate, elimi-nating the main performance boosting techniques of today shigh-performance processors. Designing processors that areoptimized for high-performance Graph Analysis is therefore achallenging this paper, we analyze the performance of Graph analysiskernels on recent multi and Many-Core hardware (Intel Xeonand Xeon Phi), and project how a potential future many-corearchitecture would perform. We analyze the main performancebottlenecks, and make some recommendations on how futuregraph Analysis targeted processors can optimize performancefor these findings confirm existing insights, such as irregularaccesses, and poor cache, prefetcher and branch predictorefficiency, but we also gain new insights as these applicationsenter the Many-Core era.

7 Our main novel findings are: Some of the memory accesses do show locality, andbenefit from caching and prefetching. A mechanism tohandle accesses with and without locality differently hasthe potential to largely improve cache efficiency, whilekeeping its performance benefits. Because of the high cache miss rate, most applicationsare memory bound. Providing high-bandwidth (on-chip)memory can therefore boost performance, but in orderto saturate this bandwidth, access latency has to be keptlow, and a sufficient amount of threads need to be activeto generate many concurrent accesses.

8 At high thread counts, algorithms that scale well oncurrent hardware start to scale worse because of loadimbalance and limited parallel tasks. Algorithms shouldbe revised to exploit more parallelism. Additionally, afew high-performance cores can accelerate phases of theapplication with low RELATEDWORKA. Graph Application Frameworks and Benchmark SuitesSeveral Graph frameworks have been developed that relievethe programmer from Graph representation and data distribu-tion details, in order to increase productivity.

9 Graphlab [17]SC18, November 11-16, 2018, Dallas, Texas, USA978-1-5386-8384-2/18/$ 2018 IEEEis a vertex-centric framework, where Graph algorithms mustbe expressed as a program running on a vertex, and onits edges and neighbors. GraphBlas [14] uses sparse matrixoperations to perform Graph algorithms. SociaLite [24] isa database oriented Graph framework, where operations arespecified in a declarative language. Galois [21] is a frameworkfor parallelizing irregular applications, and is therefore idealfor Graph applications.

10 Giraph [3] runs on top of Hadoop and ismessage based, while GraphX [11] is part of Apache Spark,running in-memory distributed Graph applications. Satish etal. [23] compare multiple frameworks, and conclude thatGalois performs closest to a native implementation in C++,which performs lack of a standard benchmark suite for Graph ap-plications has inspired multiple concurrent benchmark suiteproposals: GAP [5], GraphBIG [19] and CRONO [1] haveall been proposed in 2015. Pollard and Norris [22] havecompared multiple benchmarks and frameworks, and concludethat on average, the GAP benchmark suite performs best on amulticore processor.