An important trend in modern supercomputing is a frequent usage of co-processors, such as GPUs and Intel Xeon PHIs. The recent generation of Intel Knights Landing processors provide high performance computational power with a large amount of high-bandwidth memory, what makes them a perfect platform for graph-processing. The presented study describes implementation approaches to large-scale graph processing on Intel KNL processors; as a sample problem, the transitive closure computation is discussed. Based on the joint analysis of algorithm properties and architecture features, the performance tuning has been performed, including graph storage format optimizations, e cient usage of memory hierarchy and vectorization. As a result, an optimized algorithm implementation for the transitive closure problem solution has been developed. The proposed implementation has been studied using di erent approaches, aimed at demonstrating advantages and disadvantages of Intel KNL architecture in solving graph-processing problems.
An interest to large-scale graph processing is recently growing rapidly, since
graph data structure perfectly emulate real-world objects and connections
between them. Some examples of such objects are social and infrastructural (energy
and transport) networks, micro-biology, databases and social models, etc. The
mentioned problems have an important common property { the corresponding
graphs have very large size (up to millions vertices and billions edges); as a
result, a parallel approach is required to process those data-structures in a
reasonable amount of time. Transitive closure computation is one of the fundamental
graph-processing problems, which can be used to evaluate vertex connectivity.
The transitive closure computation problem can be applied in several already
mentioned application elds, for example, in database systems modeling [
Computing the transitive closure of graph G means obtaining graph G+ = (V; E+), where an edge (v; w) from G belongs to E+ if and only if vertex w is reachable form vertex v in graph G. As a result, the transitive closure problem solution requires jV j2 storage space, so it can't be calculated using modern computers computational node's memory even for medium-sized graphs (starting with around 220 vertices). For this reason the generalization of the transitive closure problem is used in current paper: only the speci ed pairs of vertices (u1; v1); (u2; v2); : : : ; (un; vn) are checked to belong to the transitive closure. The amount of the pairs required to check n becomes an additional exible algorithm parameter: varying it may greatly a ect the overall algorithm performance. 3
Current section uses the following notations to evaluate the complexity of
reviewed algorithms: jV j corresponds to the count of vertices in input graph G, jEj
- to the count of edges. The transitive closure computation problem in directed
graph G can be solved using three di erent traditional approaches, described
below.
1. The transitive closure computation can be reduced to the shortest paths
computation in a corresponding graph with identical weights. Consequently,
it can be solved with Floyd-Warshall algorithm, introduced in [
There are already many e cient implementations of mentioned algorithms for di erent parallel architectures, including multicore central processors, coprocessors and graphic accelerators (GPUs). The brief review of these implementations is following.
Breadth- rst searche can be considered as one of the most well-studied
graphprocessing algorithms. Not only BFS algorithm allows solving the transitive
closure problem with repeated calls from each vertex of the input graph, but it is
also a very important building-block of Purdom's algorithm. The rst approach
to parallel BFS implementation on co-processors (GPU) was discussed in [
Some e cient approaches to parallel implementation of Floyd-Warshall
algorithm for GPUs are discussed in [
Purdom's algorithm implementations on parallel architectures are less
wellstudied; an approach to implementation for central processors is described in
[
Based on computational complexity estimates, the most suitable approach to
solve the transitive closure problem is Purdom's algorithm. However, during the
selection of the most suitable algorithm for particular parallel architecture, it
parallel algorithm's properties have to be studied. For this purpose, information
graphs, introduced in [
Figure 1 (left) demonstrates information graph of Purdom's algorithm. The presented graph is rather complicated and therefore includes two subgraphs, each one corresponding to an important algorithm building-block: breadth- rst 1 Divide and Conquer Strong Components (DCSC, also known as Forward-Bakward or Forward-Backward-Trim algorithms), a family of algorithms based on recursive partitioning of graph into disjoint sets, which on the lowest level of the recursion contain a single strongly connected component in the each set. search (BFS) and strongly connected components (SCC) computation. Informational graph of parallel queue-based breadth- rst search is demonstrated on gure 1 (right), while gure 2 showes information graph of Forward-BackwardTrim algorithm, used as the main algorithm for parallel SCC computation in current paper.
The reviewed information graphs vividly demonstrate that Purdom's algorithm has a signi cant parallelism potential (O(jEj) or O(jV j) operations) on each level. Since O(jEj) and O(jV j) values are extremely huge for large-scale graphs, this algorithm can be reliably chosen for Intel KNL architecture.
Intel Knights Landing (KNL) is one of the newest architectures of Intel Xeon Phi coprocessors. These processors are equipped with up to 72 cores, each one with a relatively low clock signal rate of 1.3-1.5 GHs and an ability to e ciently execute up to 4 threads (hyperthreading technology). As a result, Intel KNL processor is able to achieve up to 6 TFLOPs performance on single precision computations and 2.6 TFLOPs on double precision. Target processor's memory architecture is even more important than peak performance for graph-processing, since graph problems are usually memory-bound. Intel KNL has two memory levels: highbandwidth MCDRAM memory with 16 GB capacity and 400 GB/s bandwidth, and DDR4 memory with 384 GB capacity (in the best available con guration) and 90 GB/s bandwidth. Processor's cores are grouped by pairs into tiles; each tile shares common 1 MB L2 cache, while each core has its own 64 KB L1 cache.
AVX-512 vector instructions support is an another important new feature of Intel KNL generation processors. These instructions allow simultaneous processing of 16 single precision variables, and, what is more important, introduce gather and scatter operations support, which is crucial during indirect memory accesses vectorization. 6
Current section describes Purdom's algorithm implementation approach for Intel KNL architecture. The developed algorithm can be divided into 4 separate stages (steps):
2. creation of intermediate representation graph G , 3. computing an answer for all vertex pairs, related to the same strongly connected component, 4. computing an answer for the rest pairs, using parallel BFS in the intermediate representation graph G .
If required, intermediate representation graph can be saved to hard drive after stage 1, so later the transitive closure can be found more e ciently (no repeated SCC computation). In current section, some implementation approaches for each algorithm stage will be described together with optimizations for each step.
Parallel Forward-backward-Trim algorithm is implemented according to the
approach described in [
The third stage contains veri cation of input pairs of vertices for the property, if these vertices belong to the same strongly connected component. This stage has a relatively small computational complexity O(n) and, moreover, can be e ciently parallelised (veri cation for each pair is independent). The last step includes obtaining an answer for the rest pairs of vertices, which appear to belong to di erent components. This step is based on BFS searches, performed from each source-vertex in intermediate representation graph. It is important to notice, that edges list format is also used for intermediate representation graph storage, since those graphs usually have low diameter compared to original input graphs.
To investigate the implementation bottlenecks, it is necessary to measure execution times for each stage, while comparing the values between each other. For di erent graph types and di erent numbers of input pairs, these values may di er a lot; in the next table, RMAT, SSCA-2 and random uniform graphs with 223 vertices and average vertex-degree 32 are used, among with 10k pairs of vertices to be checked. Table 2 demonstrates the percentage of time, spent on each execution stage for the most optimized algorithm version.
For the whole algorithm it is very important to use high-performance MCDRAM memory, what can be achieved by two di erent approaches: for small and medium scaled graphs, the program can be executed only in MCDRAM memory space. For the graphs which size exceeds 16 GB, only the important arrays (like distances arrays on stage 1 or intermediate representation graph data) can be stored in MCDRAM memory. In the next section a performance comparison for MCDRAM and usual DDR4 memory modes is demonstrated. 7
Current section includes the performance analysis for Purdom's algorithm. The rst important e ciency metric is the algorithm's performance dependance from the size of the input graph G. The performance is de ned with TEPS (traversed edges per seconds) metric, which demonstrates the graph-processing e ciency with the increase of graph size. Usually, the performance decreases because of the less and less e cient usage of the cache hierarchy with the growing graph size. An edge is called \traversed" during algorithm execution when it's corresponding data is loaded from memory. The described dependency is demonstrated on gure 3 for several versions of the developed algorithm: the basic non-optimized version(where all graphs are stored in edges list format), version with the intermediate representation graph optimization (when it is stored in the adjacency list format), version with input graph edges reordering, and version with MCDRAM memory and vectorization usage.
Since Intel KNL provides hyperthreading technology support, it is necessary to check on practice if the usage of 4x threads provides a signi cant performance increase. In current paper, launching 272 threads on 68 cores provides the best achieved performance. An another important metric is an acceleration of the most optimized developed parallel algorithm, compared to the sequential versions (for KNL and usual multi-core CPUs). On this gure multi-core Intel(R) Xeon(R) CPU E5-2697 v3 CPUs have been used for testing. The comparison demonstrated on gure 4 allows evaluating how e ciently the parallel algorithm utilizes parallel resources of the target architecture.
In the conclusion, it is important to research the sources of possible bottlenecks in the developed algorithm, since it allows to prove that the algorithm is implemented e ciently, and, moreover, to highlight Intel KNL architecture advantages and disadvantages for graph-processing. Since transitive closure computation belongs to memory-bound problem category, it is necessary to study the achieved memory throughput during the program execution. During SCC and BFS stages, the memory throughput achieved is approximately 200 GB/s, which is half of the maximum MCDRAM bandwidth. Generating the intermediate representation step has much lower memory throughput used, since on this step the program operates with complex map and vector data structures scattered in the memory, and, as a result, has poor data locality. 8
In current paper, a parallel implementation of the transitive closure computation problem for Intel KNL processors has been proposed and discussed in details. To solve the problem, Purdom's algorithm has been selected, since it has an optimal computational complexity and non-demanding memory requirements among the reviewed algorithms. Moreover, presented information graphs demonstrate that the selected algorithm have signi cant parallelism resources, which can be e ciently utilised on a highly-parallel architecture, such Intel KNL.
Based on the algorithm selection, its basic version for Intel KNL architecture has been implemented. After that, a lot of optimizations, including graph edges sorting, reducing the amount of data loaded from processor memory, usage of MCDRAM memory and vectorization has been applied to tune the performance of the proposed implementation. As a result, a high-performance and scalable parallel implementation of Purdom's algorithm has been developed. This implementation demonstrates almost a 50x acceleration compared to sequential implementation on Intel KNL, and a 5x acceleration compared to sequential implementation on Intel(R) Xeon(R) CPU E5-2697 v3.
Moreover, it was shown that Intel KNL is capable of processing very large graphs with a size up to 134 million vertices and 42 billion edges, what signi cantly exceeds other coprocessors results.
Acknowledgments. The results were obtained in the Lomonosov Moscow State University with the nancial support of the Russian Science Foundation (agreement № 17-71-20114).