CountingTrianglePIM

Please refer to the repository PIM-TC for the most up-to-date version of the code.

---

The code was tested using the UPMEM SDK version 2024.1.0 on both real hardware and the provided functional model.

Modifying the Makefile

• Adjust the number of tasklets per DPU by modifying NR_TASKLETS. This value must be a power of 2. The best-performing configuration uses 16 tasklets.
• Set the number of DPUs by modifying NR_DPUS. This should be computed based on the number of colors ($C$) using the formula:

  NR_DPUS = Binom(C+2, 3)
  

• Change the number of threads used by the host processor via NR_THREADS. The optimal setting matches the number of available CPU threads.

Running the Code

After compiling (make), navigate to the bin directory and execute:

./app -s seed -M sample_size -p keep_percentage -k Misra_Gries_dictionary_size -t nr_most_frequent_nodes_sent -c nr_colors -f path_to_graph_file

Parameters:

• -s seed: Seed for random number generation (random if not specified).
• -M sample_size: Sample size inside the DPUs (defaults to max allowed if not given).
• -p keep_percentage: Probability of keeping an edge (default: 1, meaning no edges are ignored).
• -k Misra_Gries_dictionary_size: Max dictionary size for Misra-Gries per thread (ignored if not set).
• -t nr_most_frequent_nodes_sent: Number of top frequent nodes sent to the DPUs (ignored if Misra-Gries is disabled, default: 5).
• -c nr_colors (Required): Number of colors used for graph coloring, also determining the number of DPUs.
• -f path_to_graph_file (Required): Path to the graph file in COO format.

Other Modifications

• The WRAM buffer size can be adjusted in dpu_util.h by modifying WRAM_BUFFER_SIZE. Do not exceed 2048 bytes.