DUET: Coordinated GPU-DPU Acceleration for Graph Counting

DUET is a hybrid graph counting framework that coordinates an RTX 4090 GPU and UPMEM DPUs from a CPU-side host controller. DUET targets degree-skewed graphs such as Amazon0302 and lets the CPU host coordinate work between the two engines for better load balance.

The CPU host builds both engines, prepares a consistent root split, starts both sides concurrently, collects their outputs, and reports a synchronized hybrid result.

---

🚀 Key Features

• Hybrid GPU-DPU execution for Amazon0302.
• Shared renumbered vertex IDs across the GPU and DPU engines.
• CPU-side orchestration for synchronized two-engine execution.
• DUET GPU Engine for RTX 4090 execution.
• DUET DPU Engine for UPMEM execution.
• CPU-side split metadata generation from preprocessed CSR metadata.
• Automatic DPU CSR copy when the DPU-side input file is missing.
• Per-run logs and JSON summary for experiment collection.

---

📁 Directory Structure

DUET/
|-- DUET-GPU/              # GPU-side graph counting engine
|   |-- data/              # GPU Engine graph files
|   |-- datasets/          # Dataset and preprocessing scripts
|   |-- gpu_kernels/       # CUDA kernels
|   |-- include/           # GPU Engine headers
|   |-- main.cc
|   |-- tc_challenge.cu
|   `-- Makefile
|-- DUET-DPU/              # DPU-side graph counting engine
|   |-- data/              # DPU Engine CSR binary files
|   |-- dpu/               # UPMEM DPU kernels
|   |-- host/              # DPU host-side logic
|   |-- include/           # DPU Engine headers and graph macros
|   `-- makefile
|-- duet_host.py           # DUET CPU Host controller
|-- controller_hybrid.py   # Compatibility wrapper for duet_host.py
`-- README.md

---

🛠 Requirements

• Linux environment
• NVIDIA CUDA toolchain
• RTX 4090 or compatible CUDA GPU
• UPMEM SDK v2025.1.0
• GNU Make and C/C++ compiler
• Python 3

---

⚙️ Build and Run Instructions

DUET is normally launched through the CPU host:

cd ~/DUET
python3 duet_host.py

The CPU host builds and runs both engines. The default graph macro is AM0302, and the default pattern is CLIQUE3.

To inspect the generated build and run commands without executing them:

python3 duet_host.py --dry-run --no-build

The available DPU-side graph and pattern macros are defined in:

DUET-DPU/include/common.h

GPU-side pattern support is implemented in the DUET GPU Engine kernels.

---

📥 Input Format

DUET uses a degree-renumbered undirected CSR graph. The preprocessing script generates all files needed by both engines.

Input edge list:

src dst [weight]

Only the first two columns are used. Self-loops are ignored. The graph is treated as undirected.

Generated DUET GPU Engine files:

DUET-GPU/data/amazon0302_adj.meta.txt
DUET-GPU/data/amazon0302_adj.vertex.bin
DUET-GPU/data/amazon0302_adj.edge.bin
DUET-GPU/data/amazon0302_adj.bin
DUET-GPU/data/amazon0302_adj_hybrid_config.txt

The CPU host copies the CSR binary to the DPU Engine path when needed:

DUET-DPU/data/amazon0302_adj.bin

The DPU-compatible CSR binary uses the following layout:

• node_num as 4 bytes
• edge_num as 4 bytes
• row_ptr[] as (node_num + 1) * 4 bytes
• col_idx[] as edge_num * 4 bytes

The GPU Engine GraphMiner files use the same renumbered IDs and sorted CSR rows, so both engines operate on a consistent graph view.

---

⚙️ Preprocessing

Run preprocessing once before the hybrid experiment:

cd ~/DUET/DUET-GPU

python3 datasets/prepare_amazon.py \
  datasets/amazon0302_adj.tsv \
  --output ./data/amazon0302_adj

If the dataset is not present, place Amazon0302 under:

DUET-GPU/datasets/amazon0302_adj.tsv

One common source is the GraphChallenge/SNAP Amazon0302 edge list:

cd ~/DUET/DUET-GPU/datasets
wget https://graphchallenge.s3.amazonaws.com/snap/amazon0302/amazon0302_adj.tsv

The preprocessing stage:

• compacts active vertices,
• drops vertices that cannot participate in useful work,
• sorts vertices by non-increasing degree,
• assigns small IDs to high-degree vertices,
• writes GPU Engine binary files,
• writes the DPU-compatible CSR .bin,
• writes a hybrid config file for the CPU host.

After preprocessing, vertex ID 0 is the highest-degree vertex.

---

🧠 Hybrid Execution

Run DUET from the repository root:

cd ~/DUET
python3 duet_host.py

The CPU host will:

1. Read the preprocessed GPU Engine metadata.
2. Load split metadata from amazon0302_adj_hybrid_config.txt.
3. Generate GPU and DPU root lists.
4. Build the DUET DPU Engine.
5. Build the DUET GPU Engine.
6. Start both engines concurrently.
7. Parse timing and triangle-count outputs.
8. Print a DUET summary.

Useful run modes:

# Show the plan and generated commands without running the engines.
python3 duet_host.py --dry-run --no-build

# Reuse already-built binaries.
python3 duet_host.py --no-build

# Force clean rebuild before running.
python3 duet_host.py --clean

# Show tunable options.
python3 duet_host.py --help

---

🧩 Workload Coordination

DUET separates policy from execution. The GPU and DPU engines expose execution paths for assigned roots, while the CPU host is responsible for deciding which roots should be sent to each side.

A simple degree-based split can be used as a coarse initial policy, but it is not the intended upper bound of DUET. Finer-grained policies can further divide work using root-level workload estimates, measured feedback, or task chunks so that GPU and DPU execution times are better balanced.

The CPU host validates that both engines use the same renumbered graph and records the selected split in the run summary.

---

📈 Evaluation

DUET can be evaluated by rerunning the CPU host with different split policies or DPU configurations. Each run writes logs and a JSON summary under duet_runtime/logs/, which can be collected for tables and figures.

The most important reported values are:

• GPU execution time,
• DPU execution time,
• parallel execution time,
• total triangle count,
• selected split metadata.

The JSON summary is intended to be the stable artifact for post-processing.

---

🧩 Extending Graphs and Patterns

DUET keeps graph and pattern configuration close to the two execution engines.

Adding a Graph

1. Prepare the graph into DUET's CSR/GraphMiner files under DUET-GPU/data/.
2. Ensure the DPU-compatible CSR binary is available under DUET-DPU/data/.
3. Add or reuse a graph macro in DUET-DPU/include/common.h.

For Amazon0302, the DPU Engine uses:

#elif defined(AM0302)
#define DATA_NAME "amazon0302_adj"
#define N (1<<20)
#define M (1<<23)

The DATA_NAME must match the base name of the binary graph file.

Adding a Pattern

Pattern definitions are configured in DUET-DPU/include/common.h, and DPU pattern kernels are implemented under DUET-DPU/dpu/. GPU-side support should be added to the DUET GPU Engine kernels when the pattern also needs GPU execution.

The current DUET package is organized around Amazon0302 hybrid execution, with triangle counting (CLIQUE3) as the main end-to-end path.

---

📊 Output Files

DUET writes run-time artifacts under:

duet_runtime/
|-- amazon0302_adj_roots_gpu.txt
|-- amazon0302_adj_roots_dpu.txt
`-- logs/
    |-- *_amazon0302_adj_gpu.log
    |-- *_amazon0302_adj_dpu.log
    `-- *_amazon0302_adj_summary.json

The JSON summary records:

• graph metadata,
• split metadata,
• GPU root count,
• DPU root count,
• GPU triangle count and kernel time,
• DPU triangle count and cycle time,
• total triangle count,
• parallel kernel time,
• load-balance hint.

---

🙏 Acknowledgments

DUET builds on graph counting ideas and implementation experience from GPU graph mining systems and UPMEM-based Processing-In-Memory graph processing. The DPU-side engine is influenced by prior PIM graph matching work, including PimPam, while DUET focuses on CPU-coordinated collaboration between a discrete GPU and UPMEM DPUs.