HiCAM

Accelerating Parallel Triangle Counting via Bit-Efficient Content-Addressable Memory on FPGA

HiCAM compresses graph adjacency lists into tuples and uses DSP-based content-addressable memory for parallel set intersection. This project provides the single-channel and four-channel FPGA designs, host applications, and graph preprocessing code.

Links

• Archived artifact and prebuilt U250 bitstream — Zenodo
• Evaluation datasets — Google Drive
• Environment setup

Setup

Configure AMD Vitis 2021.2, AMD XRT, and the target platform using the environment guide. Run the following commands from this repository's root.

Download and extract the datasets from the link above. Set the path to the directory containing the processed files:

export HICAM_DATASET_DIR=/path/to/hicam_dataset/processed_dataset

For a graph named facebook_combined, that directory must contain:

facebook_combined_row.bin
facebook_combined_col.bin
facebook_combined_virt_edgelist.txt

The host also accepts <name>_edgelist.txt when the virtual edge-list file is absent. Keep matching row, column, and edge-list files together.

Single-channel design

Software emulation

No FPGA board is needed for software emulation; Vitis, XRT, and the development platform are required.

make build TARGET=sw_emu PLATFORM=xilinx_u55c_gen3x16_xdma_3_202210_1
make run TARGET=sw_emu PLATFORM=xilinx_u55c_gen3x16_xdma_3_202210_1 \
  DATASET_DIR="$HICAM_DATASET_DIR" DATASET_NAME=facebook_combined

make build builds the host, kernels, xclbin, and emulation configuration. make run sets XCL_EMULATION_MODE and copies emconfig.json into the run directory. Use TARGET=hw_emu in both commands for DSP RTL hardware emulation.

U250 hardware

make build TARGET=hw PLATFORM=xilinx_u250_gen3x16_xdma_3_1_202020_1
unset XCL_EMULATION_MODE
make run TARGET=hw PLATFORM=xilinx_u250_gen3x16_xdma_3_1_202020_1 \
  DATASET_DIR="$HICAM_DATASET_DIR" DATASET_NAME=facebook_combined

PLATFORM accepts an installed platform name or a full .xpfm path. The default single-channel clock target is 280 MHz; override it with FREQ=<MHz> when building. Use separate build directories or clean the relevant target/platform before changing compile settings, because make does not track compiler-flag changes.

Prebuilt bitstream

Download HiCAM_artifact.zip from Zenodo. It contains the U250 single-channel 275 MHz bitstream:

mkdir -p artifacts
unzip HiCAM_artifact.zip -d artifacts
make host
unset XCL_EMULATION_MODE
./streaming_tc_host \
  -x artifacts/HiCAM/prebuilt_bitstream/tc_v6_275mhz.xclbin \
  --dataset_dir "$HICAM_DATASET_DIR" --dataset_name facebook_combined

The bitstream requires the matching U250 deployment platform. Build the host against the XRT installation on the machine where it will run.

Four-channel U250 design

The four-channel design replicates the pipeline across four DDR banks. Compile the shared kernel objects, then link and build its host:

make kernels TARGET=hw PLATFORM=xilinx_u250_gen3x16_xdma_3_1_202020_1
SKIP_TOOL_SETUP=1 PLATFORM=xilinx_u250_gen3x16_xdma_3_1_202020_1 \
  bash multi_tc_kernels/build_4ch.sh
unset XCL_EMULATION_MODE
./multi_tc_kernels/build_4ch/streaming_tc_host_4ch \
  -x multi_tc_kernels/build_4ch/streaming_tc_4ch.xclbin \
  --dataset_dir "$HICAM_DATASET_DIR" --dataset_name facebook_combined

The script accepts all (default), host, or link. Optional environment variables are PLATFORM, FREQ (default 250), XO_DIR, OUT_DIR, and CXX. A single-channel xclbin cannot be used with the four-channel host.

Both hosts print accelerator and CPU triangle counts, and return a nonzero status on a count mismatch. Use --device_id to select a board and --dataset_name to select another downloaded graph.

Prepare your own graph

Install NumPy as described in the environment guide. The Python preprocessor normalizes the graph, packs tuples, splits high-degree vertices, and writes host-ready data:

python3 data_prep/prepare_graph.py \
  --dataset-dir /path/to/raw_graphs --files my_graph.txt \
  --output-dir dataset --max-length 1904 --workers 1

This produces dataset/my_graph_row.bin, dataset/my_graph_col.bin, and dataset/my_graph_virt_edgelist.txt. Run the host with --dataset_dir dataset --dataset_name my_graph. Input uses integer vertex IDs and two-column edges; the parser also handles the .mtx and .edges forms used in the linked dataset collection. Use the 1904-tuple limit for this design.

The C++ preprocessor provides the same data format and parallel preprocessing:

mkdir -p build
g++ -O3 -std=c++17 -fopenmp data_prep/prepare_graph.cpp -ltbb -o build/prepare_graph
OMP_NUM_THREADS=8 ./build/prepare_graph \
  --edge-list /path/to/raw_graphs/my_graph.txt \
  --output-dir dataset --dataset-name my_graph --max-length 1904

These preprocessors do not calculate an independent triangle-count oracle. data_prep/tuple_csr.py supplies the shared tuple encoding/decoding routines; its standalone CLI is for already oriented edge lists and does not perform virtual-node splitting.

Source layout

Path	Contents
host/	Single-channel host
kernels/, src/, packet_types.hpp	HLS pipeline, HLS CAM, shared types
tuple_list_k_dsp/src/	DSP RTL CAM
rtl/, scripts/	RTL kernel interface and IP packaging
multi_tc_kernels/	Four-channel host, connectivity, build script, configuration generator
data_prep/	Python and C++ graph preprocessing
common/	Host command-line and logging utilities
Makefile, utils.mk, streaming_tc*.cfg	Single-channel build and connectivity

The single-channel pipeline has 16 CAM instances; the four-channel design has 64. Each CAM holds 120 tuples. Software emulation uses the HLS CAM; hardware emulation and hardware builds select DSP RTL by default. The packaging script generates the RTL IP metadata from source during the build.

License

Project source is provided under the MIT License. Third-party files retain their own license notices.