# AccuGraph

**Repository Path**: GPGPM/AccuGraph

## Basic Information

- **Project Name**: AccuGraph
- **Description**: No description available
- **Primary Language**: Verilog
- **License**: MulanPSL-1.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2021-01-31
- **Last Updated**: 2023-11-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# AccuGraph
AccuGraph is a novel graph-specific accelerator that can simultaneously process atomic vertex updates for massive parallelism while ensuring the correctness

# About
graph processing for many graph algorithms (e.g., BFS, PageRank, and WCC) shows significant, common features for their atomic operations: 1) incremental–the atomic operations follow the commutative and associative law, 2) simplex–all atomic operations are similar. Instead of enforcing sequential execution of conflicting operations as traditional designs, this unique observation enables to execute massive conflicting vertex updates in an accumulative manner. Through simultaneously processing multiple atomic operations and merging the results in parallel, these vertex updates can be fully parallelized without changing final results. In this paper, we are addressing how we can design

AccuGraph, a novel accelerator that executes atomic operations in an accumulative manner. AccuGraph simultaneously processes multiple atomic operations for parallelizing the conflicting vertex updates while ensuring the correctness. A specialized accumulator is provided to remove the sequentiality in atomic opeartions through merging their results in parallel. Considering that the real-world graphs generally follow sparse and power-law topology, the accumulator is designed to distinguish the process of lowdegree and high-degree vertices. Internally, it executes multiple low-degree vertices in parallel for efficient edge-level parallelism, and limits the vertex parallelism for the highdegree vertices to avoid frequent synchronizations.

# Build
To build AccuGraph, please see the [Xilinx SDAccel guide][xilinx-sdaccel-guide] for a specific walkthrough.

# Citing AccuGraph
if you use AccuGraph in your work, please cite our paper:
```
@inproceedings{Yao2018AccuGraph,
  title={An Efficient Graph Accelerator with Parallel Data Conflict Management},
  author={Yao, Pengcheng and Zheng, Long and Liao, Xiaofei and Jin, Hai and He, Bingsheng},
  booktitle={Parallel Architectures and Compilation Techniques (PACT), 2018 ACM 27th International Conference on},
  year={2018},
  organization={ACM}
}
```

[xilinx-sdaccel-guide]: https://github.com/Xilinx/SDAccel-Tutorials