# Domain-Specific Languages for Algorithmic Graph Processing: A Systematic Literature Review
## 3 Results
### Result Synthesis
#### 3.2.4 RQ4. Target Platforms, Scalability, and Computational Performance  
All surveyed studies that describe a DSL for algorithmic graph processing (IC1) include empirical evaluation to validate their results. This generally involves running DSL implementations of a number of commonly used graph algorithms against large-scale graphs. Graph algorithms that come up most often in evaluations are SSSP (Single-Source Shortest Path), PageRank, BFS, Triangle Counting, Connected Components, and Betweenness Centrality. Performance is validated in one of two ways: either by comparing DSL running times against those of state-of-the-art solutions or by comparing the performance of compiler-generated code against hand-tuned implementations and showing the performance speedup of applying certain compiler optimizations. DSLs that target more than one platform will generally run different benchmarks for each target. This heterogeneity of target platforms may be at the level of the memory architecture (shared-memory/distributed-memory), target language (Java, C, C++, Python, PL/SQL), or hardware architecture. Table 3 recapitulates the programming languages generated via the compilers of surveyed DSLs, as well as the memory architectures they target. While 40% of surveyed DSLs target both a shared-memory and a distributed-memory runtime, 40% exclusively target a single-machine environment. Among these, GraphIt targets different hardware architectures (CPU, GPU, Swarm, and HammerBlade), albeit all in a parallel, shared-memory context. The remaining 20% are vertex-centric DSLs intended for a distributed environment. Hardware architectures targeted by each DSL can be found in Table 4. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**DSL**} & \multicolumn{4}{c}{**Target Language**} & \multicolumn{4}{c}{**Target Memory Architecture**} \\ \cline{2-9}  & **C/C++** & **CUDA** & **Java** & **PL/SQL** & **Shared-Memory** & **Distributed** & **RDBMS** \\ \hline Elkir & ✓ & & & & ✓ & & & ✓ & \\ Green-Marl & ✓ & & & ✓ & ✓ & ✓ & ✓ & ✓ \\ Falcon & ✓ & ✓ & & & ✓ & ✓ & \\ Graphit & ✓ & ✓ & & & ✓ & & \\ StarPlat & ✓ & ✓ & & & ✓ & ✓ & \\ YGB & ✓ & & & & ✓ & & \\
[33] & ✓ & & & & ✓ & & \\ Palgol & ✓ & & & & & ✓ & \\ Frogel & ✓ & & ✓ & & & ✓ & \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Overview of the target languages and memory architectures supported with surveyed DSLs. Existing surveys identify scalability as a key factor in graph analytics [11; 13; 14]. As such, DSL benchmarks validate performance through large input graphs, with a size scale between \(10^{7}\) and \(10^{10}\) (the size of a graph being measured by the number of its edges). Table 4 provides an overview of graphs used for benchmarking. For each DSL and each target platform, it lists the graph types used and provides the size of the largest one. While the performance of PGX Algorithm is not directly tackled in the literature, the PGX Algorithm frontend maps to the Green-Marl compiler and, therefore, has the same implementation. The following types of graphs are commonly encountered: social networks, web graphs, road networks, R-MAT graphs, and random graphs. Social networks [70] (such as the Twitter, LiveJournal, or Friendster graphs) represent relationships between entities. Social networks typically exhibit small-world [71] and scale-free [72; 73] properties, namely high local clustering, a small diameter, and power-law degree distributions [74]. Another scale-free network example is web graphs [75], whose vertices correspond to pages and whose edges correspond to hyperlinks on the World Wide Web. In contrast, road networks (such as the US road network) have large diameters and bounded degrees. R-MAT graphs are scale-free networks that are synthetically generated, based on the Recursive Matrix (R-MAT) method [76]. Finally, random graphs are created by randomly connecting a set of isolated vertices following a given model (e.g., the Erdos-Reyni model [77]).