**2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS 2022)**

May 22-24, 2022**DOI: 10.1109/ISPASS55109.2022.00015****Authors’ Copy (PDF)**

While counting sort has a better complexity than comparison-based sorting algorithms, its parallelization suffers from high performance overhead and/or has a memory complexity that depends on the numbers of threads and elements.

In this paper, we explore the optimization of parallel counting sort for degree-ordering of real-world graphs with **power-law** degree distribution and we introduce the **Structure-Aware Parallel Counting (SAPCo) Sort** algorithm that leverages the skewed degree distribution to accelerate sorting.

The evaluation for graphs of up to 3.6 billion vertices shows that SAPCo sort is, on average, **1.7-33.5** times faster than state-of-the-art sorting algorithms such as counting sort, radix sort, and sample sort.

**For a detailed explanation of the algorithms, please refer to Chapter 5 of the On Designing Structure-Aware High-Performance Graph Algorithms thesis.**

**BibTex**

```
@INPROCEEDINGS{10.1109/ISPASS55109.2022.00015,
author={Koohi Esfahani, Mohsen and Kilpatrick, Peter and Vandierendonck, Hans},
booktitle={2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)},
title={{SAPCo Sort}: Optimizing Degree-Ordering for Power-Law Graphs},
year={2022},
volume={},
number={},
pages={},
publisher={IEEE Computer Society},
doi={10.1109/ISPASS55109.2022.00015}
}
```

**Code Availability**

The source-code of SAPCo is available on **LaganLighter Repository** (alg1_sapco_sort.c and relabel.c files). A sample execution of this source code for “Twitter-MPI” graph is shown in the following:

**Related Posts**

- On Designing Structure-Aware High-Performance Graph Algorithms (PhD Thesis)
- LaganLighter Source Code
- MASTIFF: Structure-Aware Minimum Spanning Tree/Forest – ICS’22
- SAPCo Sort: Optimizing Degree-Ordering for Power-Law Graphs – ISPASS’22 (Poster)
- LOTUS: Locality Optimizing Triangle Counting – PPOPP’22
- Locality Analysis of Graph Reordering Algorithms – IISWC’21
- Thrifty Label Propagation: Fast Connected Components for Skewed-Degree Graphs – IEEE CLUSTER’21
- Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing – ICPP’21
- How Do Graph Relabeling Algorithms Improve Memory Locality? ISPASS’21 (Poster)