Pith. sign in

REVIEW 3 major objections 5 minor 52 references

On Optimizing Locality of Graph Transposition on Modern Architectures

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read PoTra splits graph vertices into high- and low-degree groups, transposing graphs up to 8.7x faster on modern CPUs compared to atomic transposition.

desk verdict A genuinely new graph transposition algorithm with an impressive evaluation, but its performance model contradicts its own headline speedups. read the letter →

arxiv 2501.06872 v1 pith:VJI2ZQ45 submitted 2025-01-12 cs.DC cs.ARcs.DScs.PF

Mohsen Koohi Esfahani , Hans Vandierendonck This is my paper · ORCID
classification cs.DCcs.ARcs.DScs.PF
keywords graphtranspositionsparsematrixtransposestructure-awarealgorithmsskeweddegreedistributioncachelocalityatomicmemoryoperationsperformancemodelingshared-memoryparallelism
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Graph transposition — converting a graph between row and column form — is a bottleneck in graph analytics and sparse-matrix computing; earlier fast methods keep per-thread arrays that grow with the vertex count, so they run out of memory on trillion-edge graphs. This paper claims that modern CPUs have made atomic increments cheap enough to use for most vertices, provided the few high-degree vertices are handled separately. Its PoTra algorithm keeps private, cache-resident counters for high-degree vertices, compresses their IDs through a hash table, and uses atomic operations for the many low-degree vertices, limiting extra memory to about cache size. Evaluation on three CPU architectures and 20 graphs up to 128 billion edges reports up to 8.7x speedup over atomic transposition, with average gains of 1.6x on Zen2 and 1.7x on Zen3 and any loss capped near 15%. If correct, this makes trillion-edge graph transposition practical in shared memory and demonstrates a structure-aware design recipe that could transfer to other scatter-heavy graph kernels.

What carries the argument

The carrying mechanism is the HLH (hash-based LDV-HDV) method: sample edges to pick the top repeated endpoints, map them through a hash table to compact per-thread arrays of one-byte low counters plus overflow high counters and private insertion-point arrays, while all other vertices are served by a shared atomic counter array. Its behavior is summarized by the model $$\frac{T_{\text{HLH}}}{|E|} = \frac{|\text{HDV}.E|}{|E|}(t_{w,h}-t_{aw,m})+t_{aw,m}+t_{r,h}$$ where coverage $|\text{HDV}.E|/|E|$ is the fraction of edges whose endpoint is an HDV, $t_{w,h}$ is a cache-hit write to a private counter, $t_{aw,m}$ is a cache-missing atomic write to the shared counter, and $t_{r,h}$ is a cache-hit read for the hash lookup. The model decides when HLH wins and drives the preprocessing probe that selects between HLH and atomic transposition for each graph and machine.

What would settle it

Use hardware performance counters to measure the cache miss rate of PoTra's private HDV low-counter array while transposing a low-locality large graph, such as wdc12 in randomized CSR order on Zen3. A materially nonzero miss rate, or a measured speedup that diverges from the prediction of the performance model, would falsify the cache-residency assumption. A simpler check: rerun HLH with the number of HDV chosen so the private arrays fit in L2 instead of L3, and see whether the observed speedup collapses.

Watch

Extended reading notes

Core claim

The paper's central claim is that graph transposition is governed by two facts earlier work missed: real graphs have a heavily skewed degree distribution, and atomic random writes on recent CPUs cost nearly the same as ordinary writes. PoTra exploits both by separating the few high-degree vertices (HDV) from the many low-degree vertices (LDV). HDV counters and insertion points live in per-thread arrays, compressed by a hash table into a narrow index range small enough to fit in cache, and are updated without atomics; LDV share counters updated with atomic fetch-and-add. A one-byte low counter with an overflow high counter shrinks the HDV arrays further. A performance model ties the time per edge to "coverage" (the fraction of edges pointing at HDV) and to measured cache hit and miss times, and a probe on a fraction of edges chooses between this HLH method and plain atomic transposition. On 20 datasets up to 128 billion edges the paper measures speedups of 0.9–6.2x on Zen2 and 0.9–8.7x on Zen3 over atomic transposition, averaging 1.6–1.7x, with a worst-case average loss of 15.7% when the probe selects the atomic path.

Load-bearing premise

The performance gain assumes the private per-thread counter and insertion-point arrays for high-degree vertices always stay resident in the CPU cache, so every access to them is a fast hit while the shared low-degree atomic accesses effectively always miss; the paper does not directly measure the HDV arrays' hit rate, and if they spill from cache the expected speedup over plain atomic transposition disappears.

Editorial extensions

If this is right

  • Graphs with 100+ billion edges can be transposed in shared memory without the out-of-memory failures that affect the per-thread-array baselines ScanTrans and MergeTrans.
  • On low-locality graphs (e.g., randomly relabeled), PoTra achieves 1.4–3.5x speedups by keeping frequently accessed HDV counters in cache and avoiding cacheline migration.
  • Energy consumption tracks the speedup: the relative difference between speedup and energy reduction is about 8%, so the faster run also uses proportionally less processor energy.
  • The method is not universally faster: on Sapphire Rapids at 128 threads, HLH needs roughly 80% coverage to match atomic transposition, while at 4–16 threads (higher clock frequency) it gains up to 1.8x.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • This HDV/LDV split is a template for other scatter-heavy graph kernels: any algorithm that increments per-destination counters could compress the hot destinations into cache-resident private arrays and leave the long tail to atomics.
  • The model implies a portable autotuning rule: measure the gap between a cache-missing atomic write and a cache-hit write; if that gap exceeds the hash-lookup cost, the HLH-style variant should win — the probe step could be replaced by this direct measurement.
  • The one-byte low-counter design suggests counter width could be chosen from the graph's own degree distribution (e.g., 2 or 4 bytes for denser graphs), further shrinking private arrays and raising coverage.
  • The Sapphire Rapids result yields an architectural prediction: on processors where atomic writes to memory are as cheap as cached writes, structure-aware HLH-style methods lose their advantage and plain atomic transposition becomes the natural default.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper presents PoTra, a structure-aware parallel graph transposition algorithm for shared-memory machines. PoTra separates vertices into high-degree (HDV) and low-degree (LDV) sets: HDV counters and insertion points are kept in small per-thread arrays sized to fit in cache, while LDV data is protected by atomic updates to a shared array. A hash table maps vertex IDs to compressed HDV indices. PoTra also includes a preprocessing step that samples the graph to identify HDVs and probes the execution time of the atomic baseline versus the HLH method to decide which to run. The paper proposes a simple per-edge performance model (Eqs. 2 and 3) that links hit/miss access times and HDV edge coverage, and it evaluates PoTra on three CPU architectures and 20 real-world/synthetic graphs with up to 128 billion edges, reporting speedups up to 8.7x over the Atomic baseline and an average loss bounded by 15.7% when PoTra loses.

Significance. The empirical study is extensive: three architectures, 20 graphs, four locality representations, and comparisons against Atomic, ScanTrans, and MergeTrans. The source code is publicly available, which is a notable strength. The idea of exploiting the skewed degree distribution to keep frequently accessed counters in cache while using atomics for the remainder is well motivated and, if validated, could be useful for other irregular algorithms. However, the paper's central explanatory mechanism—the performance model—is numerically inconsistent with the reported speedups, and the cache-residency premise of the design is not directly measured. The empirical speedup may be real, but the model as stated cannot account for it, so the paper's claim that the model explains the results is not supported.

major comments (3)
  1. [Section IV-B, Eq. (3) vs Section V-C and Table IV] Equation (3) imposes an upper bound on the speedup of HLH over Atomic that is inconsistent with the reported results. Since t_w,h >= 0 and t_r,h >= 0, Eq. (3) gives T_HLH/|E| >= (1 - coverage) * t_aw,m, while Eq. (2) gives T_Atomic/|E| <= t_aw,m (because t_aw,h <= t_aw,m). Therefore the maximum speedup Equation (3) can predict is 1/(1 - coverage). Table IV reports coverage 22.2% for clueweb12 CSR and 70.6% for wdc14 CSR, which bound the predicted speedup at 1.28x and 3.4x respectively. Yet Section V-C reports speedups of 6.2x on Zen2 and 8.7x on Zen3 for clueweb12. This is a factor-of-6.8 discrepancy and implies either that the model omits a dominant effect (most plausibly contention/cache-line bouncing on hot atomic counters, which are repeatedly updated by all threads in Atomic GT and are not captured by the random-access microbenchmark of Section III-B), or that the coverage values in Table IV do not correspond to the configurations used in the speedup measurements. The paper must reconcile this contradiction before the model can be used to explain the algorithm's performance.
  2. [Section IV-A, 'we expect it remains in cache'] The HLH design and Equation (3) assume that the per-thread HDV low-counter and IP arrays remain resident in cache, so every HDV access costs t_w,h, while shared LDV accesses always miss (t_aw,m). This is a load-bearing assumption: if private HDV arrays spill out of cache due to thread contention, hash-table traffic, or the 1-byte low-counter overflow path, the gain of HLH over Atomic is reduced or eliminated. The paper does not report any measurement of HDV array hit rates (e.g., with hardware performance counters), so the core mechanism is not verified. I would like to see measured cache hit rates for the HDV arrays under the reported workloads, or at least a sensitivity analysis showing how the speedup degrades as the assumption is relaxed.
  3. [Section IV-C, Step 0 (probing)] The probe that selects between Atomic and HLH is described only as 'measures the execution time of HLH and Atomic for a small number of edges,' but the manuscript gives no details on the probe size, the method for choosing a representative subset of edges, or the criteria for switching. Since the reported average speedup includes graphs for which PoTra deliberately falls back to Atomic, the probe's accuracy directly affects the central claims. Please specify the probe protocol, quantify its overhead, and discuss how robust the selection is to variance in the probe measurement.
minor comments (5)
  1. [Abstract and Section I] The abstract and introduction state that PoTra achieves 'up to 8.7 times speedup compared to previous works' and 'compared to the state-of-the-art GT.' The body (Section V-C) reports speedup over the Atomic GT baseline; previous works (ScanTrans and MergeTrans) are only compared in Figure 6 on smaller graphs. Please rephrase to distinguish speedup over Atomic from speedup over previous algorithms.
  2. [Section V-H] The phrase 'accounts for enery consumed' contains a typo: 'enery' should be 'energy'.
  3. [Section V-D] The sentence 'depends on the difference of between taw,m and tw,h' has a duplicated preposition; it should read 'the difference between t_aw,m and t_w,h'.
  4. [Section V-G and Table IV] Table IV's caption says 'coverage of the top 1 million selected HDV,' but the performance model in Eq. (3) uses coverage as a general parameter. The paper should clarify whether the coverage values used in the model and in the speedup discussion are exactly the Table IV values, or whether a different k from Equation (1) was used in the actual runs.
  5. [Section II-B, Algorithm 1] In Step 1, the comment says 'Calculating degrees' but the operation counts the in-degree of destination vertices; consider clarifying that this degree is with respect to the transposed graph.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the speedups are measured against Atomic GT, the model parameters are independent inputs, and the probing step is adaptive selection rather than a fitted prediction.

full rationale

The paper's central claim, up to 8.7x speedup, is an experimentally measured comparison of PoTra against Atomic GT on specific machines and datasets, not a quantity derived from a model that was fit to the same measurements. The performance model in Section IV-B (Equations 2 and 3) is instantiated using independently measured memory-access times from the Section III-B microbenchmark and measured edge coverage from Table IV; these parameters are reported separately from the final speedups, and there is no evidence that any parameter was retro-fitted to reproduce the 8.7x result. The Step 0 probing mechanism measures actual runtime on a small edge fraction and selects Atomic or HLH; this is legitimate adaptive algorithm selection, and the reported PoTra runtime is the measured runtime of the selected method including probing overhead, so it is not a model prediction that reduces to its inputs. The self-citations present in the paper, such as SAPCo Sort [16], LaganLighter [26], the locality analysis [12], and the MS-BioGraphs dataset papers [24,25], are used as implementation components, dataset sources, or background metrics; none is invoked as an unverified uniqueness theorem or as the justification for the central speedup claim. The skeptic objection that Equation 3 bounds the clueweb12 speedup at roughly 1.28x while Section V-C reports 6.2x-8.7x is an internal consistency and verification concern about an omitted contention term or a measurement mismatch; it is a correctness risk, not a circular derivation, because the model being unable to explain the result does not make the result an input to the model. No load-bearing step in the paper reduces by construction to a fitted value, a self-citation, or a definitional equivalence, so the circularity score is 0.

Assumptions & free parameters 6 free parameters · 6 assumptions · 0 invented entities

The central algorithm rests on architecture-derived parameters (k, alpha, d) and on strong cache-residency assumptions for HDV arrays. The paper does not report the exact values used for alpha and d, nor the probe fraction, so independent reimplementation requires guessing these. No new physical entities are introduced.

free parameters (6)
  • k (number of high-degree vertices) = Determined by Eq. 1; examples in Table IV use top 1 million HDV
    k controls how many vertices get private counters. It is chosen from cache size, record size, load factor, data size, and thread count, not fitted to target speedup, but it is a tunable design parameter.
  • alpha (hash table load factor) = Not specified
    Desired load factor in Eq. 1 directly affects k and hash table size; the value used in experiments is not reported.
  • d (per-HDV data size) = Implied 1 byte for low counters plus overflow counters and IP entries; not precisely specified
    Data size per HDV in the private arrays determines how many HDVs fit in cache. The paper motivates 1-byte low counters but does not give the full d used in Eq. 1.
  • Sampling fraction for HDV identification = 1% of |V| edges sampled
    Section IV-C states 'randomly selecting 1% of |V| number of samples from the edges array'. This is a hand-chosen heuristic.
  • Probe fraction for method selection = Not specified ('a small number of edges')
    The probing step measures execution time of Atomic and HLH on a sample of edges; no fraction is given, so overhead and representativeness cannot be independently assessed.
  • LDV counter width = 1 byte with overflow to high counters
    Section III-D shows more than 84% of vertices have degree below 256, motivating 1-byte counters. This is a design choice that trades overflow handling for cache space.
assumptions (6)
  • domain assumption Real-world graphs have skewed degree distributions with many low-degree and few high-degree vertices.
    Invoked in Section IV-A to justify splitting vertices into LDV and HDV; the evaluation datasets support this, but it limits generality to synthetic or uniform graphs.
  • domain assumption Atomic random memory accesses are nearly as fast as non-atomic accesses on modern CPUs.
    Measured in Section III-B on five CPU models; the entire HLH design relies on this being true on target architectures.
  • ad hoc to paper Private HDV arrays remain resident in the CPU cache during processing.
    Assumed in Eq. 3 (t_w,h for HDV edges) and in Section IV-A ('we expect it remains in cache'). Not validated by hit-rate measurements.
  • ad hoc to paper Shared LDV counter accesses are cache misses in the HLH model.
    Eq. 3 assigns t_aw,m to all LDV edges. In practice some LDV accesses will hit, which the model ignores.
  • domain assumption The sampled 1% of vertices identifies the true high-degree vertices of the transposed graph.
    Section IV-C uses sampling to pick HDV. If sampling misses actual high-degree vertices, coverage drops and the algorithm may pick Atomic anyway, but the method's edge coverage claim is sensitive to this.
  • ad hoc to paper Hash table lookup cost is modeled as a single cache hit t_r,h with no collisions.
    Eq. 3 includes |E| * t_r,h and assumes no collisions; hash table collisions and cache misses are not modeled.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Optimizing Locality of Graph Transposition on Modern Architectures." pith.science (2026). https://pith.science/paper/VJI2ZQ45

@misc{pith2026250106872,
  author       = {Pith},
  title        = {Pith review of: On Optimizing Locality of Graph Transposition on Modern Architectures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VJI2ZQ45}},
  note         = {Machine review of arXiv:2501.06872}
}
read the original abstract

This paper investigates the shared-memory Graph Transposition (GT) problem, a fundamental graph algorithm that is widely used in graph analytics and scientific computing. Previous GT algorithms have significant memory requirements that are proportional to the number of vertices and threads which obstructs their use on large graphs. Moreover, atomic memory operations have become comparably fast on recent CPU architectures, which creates new opportunities for improving the performance of concurrent atomic accesses in GT. We design PoTra, a GT algorithm which leverages graph structure and processor and memory architecture to optimize locality and performance. PoTra limits the size of additional data structures close to CPU cache sizes and utilizes the skewed degree distribution of graph datasets to optimize locality and performance. We present the performance model of PoTra to explain the connection between cache and memory response times and graph locality. Our evaluation of PoTra on three CPU architectures and 20 real-world and synthetic graph datasets with up to 128 billion edges demonstrates that PoTra achieves up to 8.7 times speedup compared to previous works and if there is a performance loss it remains limited to 15.7%, on average.

Figures

Figures reproduced from arXiv: 2501.06872 by the authors.

Figure 1
Figure 1. CSR and CSC presentations of a sample graph [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. [Zen2, CSR] Memory footprint of ScanTrans [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Rate of random “Write” and “Atomic Write” accesses [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (9 more)
Figure 5
Figure 5. Figure 5: Performance model of Atomic vs HLH method [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 6
Figure 6. Figure 6: [Zen2, CSR] Speedup of ScanTrans, MergeTrans, and [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 7
Figure 7. Figure 7: [Zen2-3, CSR and CSR Rnd.] Speedup of PoTra over Atomic GT. [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]
Figure 8
Figure 8. Figure 8: [Zen2-3, CSR and CSR Rnd.] Speedup of PoTra over Atomic GT. [PITH_FULL_IMAGE:figures/full_fig_p009_8.png]
Figure 9
Figure 9. Figure 9: [Zen2-3, CSC and CSC Rnd.] Speedup of PoTra over Atomic GT. [PITH_FULL_IMAGE:figures/full_fig_p009_9.png]
Figure 10
Figure 10. Figure 10: [Sapphire Rapids, CSR and CSR Rnd.] Speedup of [PITH_FULL_IMAGE:figures/full_fig_p010_10.png]
Figure 12
Figure 12. Figure 12: [Zen2, CSR Rnd.] Execution time decomposition [PITH_FULL_IMAGE:figures/full_fig_p010_12.png]
Figure 13
Figure 13. Figure 13: [Zen2] Execution time of sorting TABLE IV: [Zen2] Sampling time and coverage Dataset Direction Time(s) Coverage% g500 CSR 0.4 39.6 g500 CSC 0.4 39.6 clueweb12 CSR 0.4 22.2 clueweb12 CSC 0.4 0.5 wdc14 CSR 0.7 70.6 wdc14 CSC 0.7 0.6 eu-2015 CSR 0.7 21.4 eu-2015 CSC 0.7 …
Figure 14
Figure 14. Figure 14: [Zen2,Zen3, CSR, CSR Rnd.] Speedup and energy reduction of PoTra compared to Atomic [PITH_FULL_IMAGE:figures/full_fig_p012_14.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 50 canonical work pages

  1. [1]

    Ultra-large-scale repository analysis via graph compression,

    P . Boldi, A. Pietri, S. Vigna, and S. Zacchiroli, “Ultra-large-scale repository analysis via graph compression,” in 2020 (SANER). London, ON, Canada: IEEE Computer Society, 2020, pp. 184–194

    work page 2020

  2. [2]

    On overcoming HPC challenges of trillion-scale real-world graph datasets,

    M. Koohi Esfahani, P . Boldi, H. V andierendonck, P . Kilpatrick, and S. Vigna, “On overcoming HPC challenges of trillion-scale real-world graph datasets,” in 2023 IEEE International Conference on Big Data (BigData’23). IEEE Computer Society, 2023

    work page 2023

  3. [3]

    BUbiNG: Massive crawling for the masses,

    P . Boldi, A. Marino, M. Santini, and S. Vigna, “BUbiNG: Massive crawling for the masses,” ACM Trans. Web , vol. 12, no. 2, Jun. 2018

    work page 2018

  4. [4]

    The software heritage graph dataset: Public software development under one roof,

    A. Pietri, D. Spinellis, and S. Zacchiroli, “The software heritage graph dataset: Public software development under one roof,” in 2019 IEEE/ACM 16th International Conference on Mining Software Reposi- tories (MSR) , 2019, pp. 138–142

    work page 2019

  5. [5]

    The graph structure in the web – analyzed on different aggregation levels,

    R. Meusel, S. Vigna, O. Lehmberg, and C. Bizer, “The graph structure in the web – analyzed on different aggregation levels,” The Journal of Web Science, vol. 1, no. 1, pp. 33–47, 2015

    work page 2015

  6. [6]

    Parallel transposition of sparse data structures,

    H. Wang, W. Liu, K. Hou, and W.-c. Feng, “Parallel transposition of sparse data structures,” in Proceedings of the 2016 International Conference on Supercomputing , ser. ICS ’16. New Y ork, NY , USA: Association for Computing Machinery, 2016

    work page 2016

  7. [7]

    Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der V orst, Templates for the Solution of Algebraic Eigenvalue Problems , Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der V orst, Eds. Society for Industrial and Applied Mathematics, 1987

    work page 1987

  8. [8]

    Sparskit: a basic tool kit for sparse matrix computations - version 2,

    Y . Saad, “Sparskit: a basic tool kit for sparse matrix computations - version 2,” 1994

    work page 1994

Show all 52 references
  1. [9]

    Scrambled linear pseudorandom number generators,

    D. Blackman and S. Vigna, “Scrambled linear pseudorandom number generators,” ACM Trans. Math. Softw. , vol. 47, no. 4, Sep. 2021

    2021

  2. [10]

    Layered Label Propaga- tion: A multiresolution coordinate-free ordering for compressing social networks,

    P . Boldi, M. Rosa, M. Santini, and S. Vigna, “Layered Label Propaga- tion: A multiresolution coordinate-free ordering for compressing social networks,” in Proceedings of the 20th International Conference on World Wide Web. ACM, 2011

    2011

  3. [11]

    Rabbit Order: Just-in-time parallel reordering for fast graph analysis,

    J. Arai, H. Shiokawa, T. Y amamuro, M. Onizuka, and S. Iwamura, “Rabbit Order: Just-in-time parallel reordering for fast graph analysis,” in 2016 IEEE International Parallel and Distributed Processing Sympo- sium (IPDPS) . USA: IEEE, 2016, pp. 22–31

    2016

  4. [12]

    Locality analysis of graph reordering algorithms,

    M. Koohi Esfahani, P . Kilpatrick, and H. V andierendonck, “Locality analysis of graph reordering algorithms,” in 2021 IEEE International Symposium on Workload Characterization (IISWC’21) . USA: IEEE Computer Society, 2021, pp. 101–112

    2021

  5. [13]

    The WebGraph framework I: Compression techniques,

    P . Boldi and S. Vigna, “The WebGraph framework I: Compression techniques,” in Proceedings of the 13th International Conference on World Wide Web , ser. WWW ’04. New Y ork, NY , USA: Association for Computing Machinery, 2004, p. 595–602

    2004

  6. [14]

    Acceleration of pagerank with customized precision based on mantissa segmentation,

    T. Gr ¨utzmacher, T. Cojean, G. Flegar, H. Anzt, and E. S. Quintana-Ort ´ı, “Acceleration of pagerank with customized precision based on mantissa segmentation,” ACM Trans. Parallel Comput. , 2020

    2020

  7. [15]

    Software-de fi ned fl oating-point number formats and their application to graph processing,

    H. V andierendonck, “Software-de fi ned fl oating-point number formats and their application to graph processing,” in Proceedings of the 36th ACM International Conference on Supercomputing , ser. ICS ’22. New Y ork, NY , USA: Association for Computing Machinery, 2022

    2022

  8. [16]

    SAPCo Sort: Optimizing degree-ordering for power-law graphs,

    M. Koohi Esfahani, P . Kilpatrick, and H. V andierendonck, “SAPCo Sort: Optimizing degree-ordering for power-law graphs,” in 2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). IEEE Computer Society, 2022

    2022

  9. [17]

    UbiCrawler: A scalable fully distributed web crawler,

    P . Boldi, B. Codenotti, M. Santini, and S. Vigna, “UbiCrawler: A scalable fully distributed web crawler,” Softw. Pract. Exper . , vol. 34, no. 8, p. 711–726, Jul. 2004

    2004

  10. [18]

    Graph structure in the web: Aggregated by pay-level domain,

    O. Lehmberg, R. Meusel, and C. Bizer, “Graph structure in the web: Aggregated by pay-level domain,” in Proceedings of the 2014 ACM Conference on Web Science . ACM, 2014

    2014

  11. [19]

    Graph structure in the web — revisited: A trick of the heavy tail,

    R. Meusel, S. Vigna, O. Lehmberg, and C. Bizer, “Graph structure in the web — revisited: A trick of the heavy tail,” in Proceedings of the 23rd International Conference on World Wide Web . ACM, 2014

    2014

  12. [20]

    Friendster: The online gaming social network,

    F. social network, “Friendster: The online gaming social network,” 2011. [Online]. Available: https://archive.org/details/friendster-dataset-201107

    2011

  13. [21]

    What is twitter, a social network or a news media?

    H. Kwak, C. Lee, H. Park, and S. Moon, “What is twitter, a social network or a news media?” in Proceedings of the 19th International Conference on World Wide Web , ser. WWW ’10. New Y ork, NY , USA: Association for Computing Machinery, 2010, p. 591–600

  14. [22]

    Introducing the graph 500,

    R. C. Murphy, K. B. Wheeler, B. W. Barrett, and J. A. Ang, “Introducing the graph 500,” Cray Users Group , 2010

    2010

  15. [23]

    Smooth kronecker: Solving the combing problem in kronecker graphs,

    V . Anand, P . Mehrotra, D. Margo, and M. Seltzer, “Smooth kronecker: Solving the combing problem in kronecker graphs,” ser. GRADES- NDA ’20. ACM, 2020

    2020

  16. [24]

    MS-BioGraphs: Sequence similarity graph datasets,

    M. Koohi Esfahani, P . Boldi, H. V andierendonck, P . Kilpatrick, and S. Vigna, “MS-BioGraphs: Sequence similarity graph datasets,” CoRR, vol. abs/2308.16744, 2023. [Online]. Available: https://doi.org/ 10.48550/arXiv.2308.16744

    2023 doi arXiv

  17. [25]

    Dataset announcement: MS-BioGraphs, trillion-scale public real- world sequence similarity graphs,

    ——, “Dataset announcement: MS-BioGraphs, trillion-scale public real- world sequence similarity graphs,” in IISWC’23. IEEE Computer Society, 2023

    2023

  18. [26]

    On designing structure-aware high-performance graph algorithms,

    M. Koohi Esfahani, “On designing structure-aware high-performance graph algorithms,” Ph.D. dissertation, Queen’s University Belfast, 2022

    2022

  19. [27]

    Selective Parallel Loading of Large-Scale Compressed Graphs with ParaGrapher,

    M. Koohi Esfahani, M. D’Antonio, S. I. Tauhidi, T. S. Mai, and H. V andierendonck, “Selective Parallel Loading of Large-Scale Compressed Graphs with ParaGrapher,” Tech. Rep., 2024. [Online]. Available: https://blogs.qub.ac.uk/DIPSA/ParaGrapher

    2024

  20. [28]

    OpenMP: an industry standard api for shared- memory programming,

    L. Dagum and R. Menon, “OpenMP: an industry standard api for shared- memory programming,” IEEE Computational Science and Engineering , vol. 5, no. 1, pp. 46–55, 1998

    1998

  21. [29]

    Mining top- k frequent itemsets through progressive sampling,

    A. Pietracaprina, M. Riondato, E. Upfal, and F. V andin, “Mining top- k frequent itemsets through progressive sampling,” Data Mining and Knowledge Discovery , 2010

    2010

  22. [30]

    Two fast algorithms for sparse matrices: Multiplication and permuted transposition,

    F. G. Gustavson, “Two fast algorithms for sparse matrices: Multiplication and permuted transposition,” ACM Trans. Math. Softw. , 1978

    1978

  23. [31]

    Parallelizing the sparse matrix transposition: Reducing the programmer effort using transactional memory,

    M. A. Gonzalez-Mesa, E. D. Gutierrez, and O. Plata, “Parallelizing the sparse matrix transposition: Reducing the programmer effort using transactional memory,” Procedia Computer Science , vol. 18, pp. 501– 510, 2013, 2013 International Conference on Computational Science

    2013

  24. [32]

    Ef fi cient out-of-core and out- of-place rectangular matrix transposition and rotation,

    P . Godard, V . Loechner, and C. Bastoul, “Ef fi cient out-of-core and out- of-place rectangular matrix transposition and rotation,” IEEE Transac- tions on Computers , vol. 70, no. 11, pp. 1942–1948, 2021

    1942

  25. [33]

    Ef fi cient parallel out-of-core matrix transposition,

    S. Krishnamoorthy, G. Baumgartner, D. Cociorva, C.-C. Lam, and P . Sadayappan, “Ef fi cient parallel out-of-core matrix transposition,” International Journal of High Performance Computing and Networking , vol. 2, no. 2-4, pp. 110–119, 2004

    2004

  26. [34]

    Parallel and cache- effi cient in-place matrix storage format conversion,

    F. Gustavson, L. Karlsson, and B. K ˚agstr¨om, “Parallel and cache- effi cient in-place matrix storage format conversion,” ACM Transactions on Mathematical Software (TOMS) , vol. 38, no. 3, pp. 1–32, 2012

    2012

  27. [35]

    Scalescan: Scalable density-based graph clustering,

    H. Shiokawa, T. Takahashi, and H. Kitagawa, “Scalescan: Scalable density-based graph clustering,” in Database and Expert Systems Ap- plications. Cham: Springer International Publishing, 2018, pp. 18–34

    2018

  28. [36]

    How do graph relabeling algorithms improve memory locality?

    M. Koohi Esfahani, P . Kilpatrick, and H. V andierendonck, “How do graph relabeling algorithms improve memory locality?” in 2021 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). USA: IEEE Computer Society, 2021, pp. 84–86

    2021

  29. [37]

    PowerLyra: Differentiated graph computation and partitioning on skewed graphs,

    R. Chen, J. Shi, Y . Chen, and H. Chen, “PowerLyra: Differentiated graph computation and partitioning on skewed graphs,” in Proceedings of the Tenth European Conference on Computer Systems , ser. EuroSys ’15. New Y ork, NY , USA: Association for Computing Machinery, 2015

    2015

  30. [38]

    Thrifty Label Propagation: Fast connected components for skewed-degree graphs,

    M. Koohi Esfahani, P . Kilpatrick, and H. V andierendonck, “Thrifty Label Propagation: Fast connected components for skewed-degree graphs,” in 2021 IEEE CLUSTER . USA: IEEE Computer Society, 2021, pp. 226– 237

    2021

  31. [39]

    MASTIFF: Structure-aware minimum spanning tree/forest,

    ——, “MASTIFF: Structure-aware minimum spanning tree/forest,” in 36th ACM International Conference on Supercomputing . New Y ork, NY , USA: Association for Computing Machinery, 2022

    2022

  32. [40]

    LOTUS: Locality optimizing triangle counting,

    ——, “LOTUS: Locality optimizing triangle counting,” in 27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP 2022) . ACM, 2022, p. 219–233

    2022

  33. [41]

    Exploiting in-hub temporal locality in SpMV-based graph pro- cessing,

    ——, “Exploiting in-hub temporal locality in SpMV-based graph pro- cessing,” in 50th International Conference on Parallel Processing , ser. ICPP 2021. New Y ork, NY , USA: Association for Computing Machinery, 2021

    2021

  34. [42]

    Navigating the maze of graph analytics frameworks using massive graph datasets,

    N. Satish, N. Sundaram, M. M. A. Patwary, J. Seo, J. Park, M. A. Has- saan, S. Sengupta, Z. Yin, and P . Dubey, “Navigating the maze of graph analytics frameworks using massive graph datasets,” in Proceedings of the 2014 ACM SIGMOD International Conference on Management of Dat...

    2014

  35. [43]

    VEBO: A vertex- and edge-balanced ordering heuristic to load balance parallel graph processing,

    J. Sun, H. V andierendonck, and D. S. Nikolopoulos, “VEBO: A vertex- and edge-balanced ordering heuristic to load balance parallel graph processing,” CoRR, vol. abs/1806.06576, pp. 1–13, 2018

    2018 arXiv

  36. [44]

    SDS-Sort: Scalable dynamic skew- aware parallel sorting,

    B. Dong, S. Byna, and K. Wu, “SDS-Sort: Scalable dynamic skew- aware parallel sorting,” in Proceedings of the 25th ACM International Symposium on High-Performance Parallel and Distributed Computing , ser. HPDC ’16. New Y ork, NY , USA: Association for Computing Machinery, 2016...

    2016

  37. [45]

    Engineering a cache- oblivious sorting algorithm,

    G. S. Brodal, R. Fagerberg, and K. Vinther, “Engineering a cache- oblivious sorting algorithm,” ACM J. Exp. Algorithmics , 2008

    2008

  38. [46]

    An exper- imental comparison of cache-oblivious and cache-conscious programs,

    K. Y otov, T. Roeder, K. Pingali, J. Gunnels, and F. Gustavson, “An exper- imental comparison of cache-oblivious and cache-conscious programs,” ser. SPAA ’07. ACM, 2007

    2007

  39. [47]

    Numa-aware graph-structured ana- lytics,

    K. Zhang, R. Chen, and H. Chen, “Numa-aware graph-structured ana- lytics,” SIGPLAN Not. , vol. 50, no. 8, p. 183–193, Jan. 2015

    2015

  40. [48]

    Graphgrind: Addressing load imbalance of graph partitioning,

    J. Sun, H. V andierendonck, and D. S. Nikolopoulos, “Graphgrind: Addressing load imbalance of graph partitioning,” in Proceedings of the International Conference on Supercomputing , ser. ICS ’17. New Y ork, NY , USA: Association for Computing Machinery, 2017

    2017

  41. [49]

    Energy-ef fi cient cache-aware scheduling on heterogeneous multicore systems,

    S. Z. Sheikh and M. A. Pasha, “Energy-ef fi cient cache-aware scheduling on heterogeneous multicore systems,” IEEE Transactions on Parallel and Distributed Systems , vol. 33, no. 1, pp. 206–217, 2022

    2022

  42. [50]

    Architecture-aware precision tuning with multiple number representa- tion systems,

    D. Cattaneo, M. Chiari, N. Fossati, S. Cherubin, and G. Agosta, “Architecture-aware precision tuning with multiple number representa- tion systems,” in 2021 58th ACM/IEEE Design Automation Conference (DAC), 2021, pp. 673–678

    2021

  43. [51]

    A gpu architecture aware fi ne-grain pruning tech- nique for deep neural networks,

    K. Choi and H. Y ang, “A gpu architecture aware fi ne-grain pruning tech- nique for deep neural networks,” in Euro-Par 2021: Parallel Processing. Cham: Springer International Publishing, 2021, pp. 217–231

    2021

  44. [52]

    Deact: Architecture-aware virtual memory support for fabric attached memory systems,

    V . R. Kommareddy, C. Hughes, S. D. Hammond, and A. Awad, “Deact: Architecture-aware virtual memory support for fabric attached memory systems,” in 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA) , 2021, pp. 453–466

    2021

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.