DFQ-BFS
所属分类：GPU/显卡
开发工具：Cuda
文件大小：0KB
下载次数：0
上传日期：2023-08-28 12:39:18
上 传 者：
sh-1993
说明： 日期23：用于提高宽度可扩展性的去中心化前沿队列-首次在GPU上搜索，
(DATE 23: A Decentralized Frontier Queue for Improving Scalability of Breadth- First-Search on GPUs,)
文件列表:
bin/ (0, 2023-08-28)
bin/bfs (831432, 2023-08-28)
data/ (0, 2023-08-28)
data/Amazon0302.dat (12755664, 2023-08-28)
design/ (0, 2023-08-28)
design/global-q/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/(del/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/(del/our-sep/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/(del/our-sep/lower-bound/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/(del/our-sep/lower-bound/bfs (835984, 2023-08-28)
design/global-q/atomic-sa(-)/(del/our-sep/lower-bound/bfs.cu (9462, 2023-08-28)
design/global-q/atomic-sa(-)/(del/our-sep/upper-bound/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/(del/our-sep/upper-bound/bfs (835984, 2023-08-28)
design/global-q/atomic-sa(-)/(del/our-sep/upper-bound/bfs.cu (9465, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/lower-bound/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/lower-bound/bfs (839856, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/lower-bound/bfs.cu (9664, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/ombre-bound/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/ombre-bound/bfs (840088, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/ombre-bound/bfs.cu (9672, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/ombre-bound/bfs_ (840088, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/ombre-bound/bfs_r (840088, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/ombre-bound/bfsr (839856, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/upper-bound/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/upper-bound/bfs (835992, 2023-08-28)
design/global-q/atomic-sa(-)/gun-sep/upper-bound/bfs.cu (9511, 2023-08-28)
design/global-q/atomic-sa(-)/non-sep/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/non-sep/lower-bound/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/non-sep/lower-bound/bfs (831632, 2023-08-28)
design/global-q/atomic-sa(-)/non-sep/lower-bound/bfs.cu (7597, 2023-08-28)
design/global-q/atomic-sa(-)/non-sep/ombre-bound/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/non-sep/ombre-bound/bfs (831744, 2023-08-28)
design/global-q/atomic-sa(-)/non-sep/ombre-bound/bfs.cu (8620, 2023-08-28)
design/global-q/atomic-sa(-)/non-sep/upper-bound/ (0, 2023-08-28)
design/global-q/atomic-sa(-)/non-sep/upper-bound/bfs (827496, 2023-08-28)
design/global-q/atomic-sa(-)/non-sep/upper-bound/bfs.cu (7402, 2023-08-28)
design/global-q/atomic-sa(-)/our-sep(+)/ (0, 2023-08-28)
... ...
# DFQ-BFS: A Decentralized Frontier Queue for Improving Scalability of Breadth-First-Search on GPUs
## 1. Getting started Instructions.
- Clone this project
`git clone git@github.com:NTUDSNLab/DFQ-BFS.git`
- Hardware:
- `CPU x86_64` (Test on Intel(R) Core(TM) i9-10900K CPU @ 3.70GHz)
- `NVIDIA GPU (arch>=86)` with device memory >= 12GB.(Support NVIDIA RTX3080(sm_86). Note that we mainly evaluate our experience on RTX3090. The execution time could be different with different devices.
- OS & Compler:
- `Ubuntu 18.04`
- `CUDA = 11.6`
- `nvcc = 11.6`
- Important Files/Directories
- `data/`: contains all datasets that we want to compare with.
- `bin/`: contains all binaries from different designs (including baseline with name started with `1_`) that we want to compare with. Note that all the source codes of each binary can be found in the `design/` directory.
- `design/`: contains all the source codes organized by tree structure, each sub-directory name describing the design choice.
- `plot.py`: The python script that traversal all the datasets in `data/` with all binaries in `bin/`, and also plot their runtime speedup with a histogram.
**noting that the first two lines
\# Nodes: #node Edges: #edge
\# FromNodeId ToNodeId
are necessary!!!**
the following is the example:
```
# Nodes: 239 Edges: 502
# FromNodeId ToNodeId
0 1
0 2
0 3
...
```
## 2. Environment Setup
### 1) Pick up the implementation you want in `design/` and compile it
```
cd design/implementation/you/want/
nvcc -O3 --compiler-options -Wall -Xptxas -v bfs.cu -o bfs
```
### 2) copy it into `design/bin`
```
cd $dir_with_desired_feature
cp bfs design/bin
```
### 3) unzip dataset under 'data/' or download it from [SNAP](http://snap.stanford.edu/data/index.html)
```
tar xvf data.tar
```
### 4) run the python script
```
python plot.py
```
### 5) check the result png file
## How to Cite This Work
Thanks for your citation
```bibtex
@inproceedings{hsieh2023decentralized,
title={A Decentralized Frontier Queue for Improving Scalability of Breadth-First-Search on GPUs},
author={Hsieh, Chou-Ying and Cheng, Po-Hsiu and Chang, Chia-Ming and Kuo, Sy-Yen},
booktitle={2023 Design, Automation \& Test in Europe Conference \& Exhibition (DATE)},
pages={1--6},
year={2023},
organization={IEEE}
}
```
近期下载者：
相关文件：
收藏者：