From 4052d7b4c0e1a59419f07642b9a33088f5745d28 Mon Sep 17 00:00:00 2001 From: Birte Kristina Friesel Date: Wed, 14 May 2025 13:43:55 +0200 Subject: BFS: AspectC++ (and behaviour model) support --- BFS/Makefile | 29 ++++++++-- BFS/dpu/task.c | 2 +- BFS/host/app.c | 60 ++++++++++---------- BFS/host/mram-management.h | 4 +- BFS/include/common.h | 25 +++++++++ BFS/include/dfatool_host.ah | 27 +++++++++ BFS/include/graph.h | 133 ++++++++++++++++++++++++++++++++++++++++++++ BFS/include/params.h | 67 ++++++++++++++++++++++ BFS/include/timer.h | 8 +++ BFS/include/utils.h | 10 ++++ BFS/support/common.h | 25 --------- BFS/support/graph.h | 133 -------------------------------------------- BFS/support/params.h | 67 ---------------------- BFS/support/timer.h | 31 ----------- BFS/support/utils.h | 10 ---- 15 files changed, 329 insertions(+), 302 deletions(-) create mode 100644 BFS/include/common.h create mode 100644 BFS/include/dfatool_host.ah create mode 100644 BFS/include/graph.h create mode 100644 BFS/include/params.h create mode 100644 BFS/include/timer.h create mode 100644 BFS/include/utils.h delete mode 100644 BFS/support/common.h delete mode 100644 BFS/support/graph.h delete mode 100644 BFS/support/params.h delete mode 100644 BFS/support/timer.h delete mode 100644 BFS/support/utils.h (limited to 'BFS') diff --git a/BFS/Makefile b/BFS/Makefile index d43202f..598de50 100644 --- a/BFS/Makefile +++ b/BFS/Makefile @@ -4,17 +4,34 @@ WITH_ALLOC_OVERHEAD ?= 0 WITH_LOAD_OVERHEAD ?= 0 WITH_FREE_OVERHEAD ?= 0 -COMMON_INCLUDES := support HOST_SOURCES := $(wildcard host/*.c) DPU_SOURCES := $(wildcard dpu/*.c) -COMMON_FLAGS := -Wall -Wextra -g -I${COMMON_INCLUDES} -HOST_FLAGS := ${COMMON_FLAGS} -std=c11 -O3 `dpu-pkg-config --cflags --libs dpu` -DNR_TASKLETS=${NR_TASKLETS} -DNR_DPUS=${NR_DPUS} -DWITH_ALLOC_OVERHEAD=${WITH_ALLOC_OVERHEAD} -DWITH_LOAD_OVERHEAD=${WITH_LOAD_OVERHEAD} -DWITH_FREE_OVERHEAD=${WITH_FREE_OVERHEAD} +aspectc ?= 0 +aspectc_timing ?= 0 +dfatool_timing ?= 1 + +HOST_CC := ${CC} + +COMMON_FLAGS := -Wall -Wextra -g -Iinclude +HOST_FLAGS := ${COMMON_FLAGS} -O3 `dpu-pkg-config --cflags --libs dpu` -DNR_TASKLETS=${NR_TASKLETS} -DNR_DPUS=${NR_DPUS} -DWITH_ALLOC_OVERHEAD=${WITH_ALLOC_OVERHEAD} -DWITH_LOAD_OVERHEAD=${WITH_LOAD_OVERHEAD} -DWITH_FREE_OVERHEAD=${WITH_FREE_OVERHEAD} -DDFATOOL_TIMING=${dfatool_timing} -DASPECTC=${aspectc} DPU_FLAGS := ${COMMON_FLAGS} -O2 -DNR_TASKLETS=${NR_TASKLETS} +ifeq (${aspectc_timing}, 1) + ASPECTC_HOST_FLAGS += -ainclude/dfatool_host_dpu.ah -ainclude/dfatool_host.ah +endif + +ASPECTC_HOST_FLAGS ?= -a0 + +ifeq (${aspectc}, 1) + HOST_CC = ag++ -r repo.acp -v 0 ${ASPECTC_HOST_FLAGS} --c_compiler ${UPMEM_HOME}/bin/clang++ -p . --Xcompiler +else + HOST_FLAGS += -std=c11 +endif + QUIET = @ -ifdef verbose +ifeq (${verbose}, 1) QUIET = endif @@ -27,7 +44,9 @@ bin/dpu_code: ${DPU_SOURCES} ${COMMON_INCLUDES} bin ${QUIET}dpu-upmem-dpurte-clang ${DPU_FLAGS} -o $@ ${DPU_SOURCES} bin/host_code: ${HOST_SOURCES} ${COMMON_INCLUDES} bin - ${QUIET}${CC} -o $@ ${HOST_SOURCES} ${HOST_FLAGS} + ${QUIET}cp ../include/dfatool_host_dpu.ah include + ${QUIET}${HOST_CC} -o $@ ${HOST_SOURCES} ${HOST_FLAGS} + ${QUIET}rm -f include/dfatool_host_dpu.ah clean: ${QUIET}rm -rf bin diff --git a/BFS/dpu/task.c b/BFS/dpu/task.c index 44ec214..5275047 100644 --- a/BFS/dpu/task.c +++ b/BFS/dpu/task.c @@ -12,7 +12,7 @@ #include #include "dpu-utils.h" -#include "../support/common.h" +#include "common.h" BARRIER_INIT(my_barrier, NR_TASKLETS); diff --git a/BFS/host/app.c b/BFS/host/app.c index 9ba7ffb..763ff7a 100644 --- a/BFS/host/app.c +++ b/BFS/host/app.c @@ -3,9 +3,24 @@ * BFS Host Application Source File * */ +#if ASPECTC +extern "C" { +#endif + #include #include +#ifndef ENERGY +#define ENERGY 0 +#endif +#if ENERGY +#include +#endif + +#if ASPECTC +} +#endif + #include #include #include @@ -14,18 +29,11 @@ #include #include "mram-management.h" -#include "../support/common.h" -#include "../support/graph.h" -#include "../support/params.h" -#include "../support/timer.h" -#include "../support/utils.h" - -#ifndef ENERGY -#define ENERGY 0 -#endif -#if ENERGY -#include -#endif +#include "common.h" +#include "graph.h" +#include "params.h" +#include "timer.h" +#include "utils.h" #define DPU_BINARY "./bin/dpu_code" @@ -44,10 +52,6 @@ int main(int argc, char **argv) double tenergy = 0; #endif - printf - ("WITH_ALLOC_OVERHEAD=%d WITH_LOAD_OVERHEAD=%d WITH_FREE_OVERHEAD=%d\n", - WITH_ALLOC_OVERHEAD, WITH_LOAD_OVERHEAD, WITH_FREE_OVERHEAD); - // Allocate DPUs and load binary struct dpu_set_t dpu_set, dpu; uint32_t numDPUs, numRanks; @@ -59,7 +63,7 @@ int main(int argc, char **argv) #if WITH_ALLOC_OVERHEAD stopTimer(&timer, 0); #else - timer.time[0] = 0; + zeroTimer(&timer, 0); #endif #if WITH_LOAD_OVERHEAD @@ -69,7 +73,7 @@ int main(int argc, char **argv) #if WITH_LOAD_OVERHEAD stopTimer(&timer, 0); #else - timer.time[1] = 0; + zeroTimer(&timer, 1); #endif DPU_ASSERT(dpu_get_nr_dpus(dpu_set, &numDPUs)); @@ -86,10 +90,10 @@ int main(int argc, char **argv) uint32_t numNodes = csrGraph.numNodes; uint32_t *nodePtrs = csrGraph.nodePtrs; uint32_t *neighborIdxs = csrGraph.neighborIdxs; - uint32_t *nodeLevel = calloc(numNodes, sizeof(uint32_t)); // Node's BFS level (initially all 0 meaning not reachable) - uint64_t *visited = calloc(numNodes / 64, sizeof(uint64_t)); // Bit vector with one bit per node - uint64_t *currentFrontier = calloc(numNodes / 64, sizeof(uint64_t)); // Bit vector with one bit per node - uint64_t *nextFrontier = calloc(numNodes / 64, sizeof(uint64_t)); // Bit vector with one bit per node + uint32_t *nodeLevel = (uint32_t*)calloc(numNodes, sizeof(uint32_t)); // Node's BFS level (initially all 0 meaning not reachable) + uint64_t *visited = (uint64_t*)calloc(numNodes / 64, sizeof(uint64_t)); // Bit vector with one bit per node + uint64_t *currentFrontier = (uint64_t*)calloc(numNodes / 64, sizeof(uint64_t)); // Bit vector with one bit per node + uint64_t *nextFrontier = (uint64_t*)calloc(numNodes / 64, sizeof(uint64_t)); // Bit vector with one bit per node setBit(nextFrontier[0], 0); // Initialize frontier to first node uint32_t level = 1; @@ -325,7 +329,7 @@ int main(int argc, char **argv) // Calculating result on CPU PRINT_INFO(p.verbosity >= 1, "Calculating result on CPU"); - uint32_t *nodeLevelReference = calloc(numNodes, sizeof(uint32_t)); // Node's BFS level (initially all 0 meaning not reachable) + uint32_t *nodeLevelReference = (uint32_t*) calloc(numNodes, sizeof(uint32_t)); // Node's BFS level (initially all 0 meaning not reachable) memset(nextFrontier, 0, numNodes / 64 * sizeof(uint64_t)); setBit(nextFrontier[0], 0); // Initialize frontier to first node nextFrontierEmpty = 0; @@ -395,7 +399,7 @@ int main(int argc, char **argv) #if WITH_FREE_OVERHEAD stopTimer(&timer, 7); #else - timer.time[7] = 0; + zeroTimer(&timer, 7); #endif // Verify the result @@ -412,9 +416,9 @@ int main(int argc, char **argv) } if (status) { - printf + dfatool_printf ("[::] BFS-UMEM | n_dpus=%d n_ranks=%d n_tasklets=%d e_type=%s n_elements=%d " - "| throughput_pim_MBps=%f throughput_MBps=%f", numDPUs, + "| throughput_pim_MBps=%f throughput_MBps=%f", numDPUs, numRanks, NR_TASKLETS, "uint32_t", numNodes, numNodes * sizeof(uint32_t) / (timer.time[2] + timer.time[3]), @@ -423,12 +427,12 @@ int main(int argc, char **argv) timer.time[2] + timer.time[3] + timer.time[4])); - printf(" throughput_pim_MOpps=%f throughput_MOpps=%f", + dfatool_printf(" throughput_pim_MOpps=%f throughput_MOpps=%f", numNodes / (timer.time[2] + timer.time[3]), numNodes / (timer.time[0] + timer.time[1] + timer.time[2] + timer.time[3] + timer.time[4])); - printf + dfatool_printf (" latency_alloc_us=%f latency_load_us=%f latency_write_us=%f latency_kernel_us=%f latency_sync_us=%f latency_read_us=%f latency_cpu_us=%f latency_free_us=%f\n", timer.time[0], timer.time[1], timer.time[2], timer.time[3], timer.time[4], timer.time[5], timer.time[6], diff --git a/BFS/host/mram-management.h b/BFS/host/mram-management.h index f2ee031..61616da 100644 --- a/BFS/host/mram-management.h +++ b/BFS/host/mram-management.h @@ -2,8 +2,8 @@ #ifndef _MRAM_MANAGEMENT_H_ #define _MRAM_MANAGEMENT_H_ -#include "../support/common.h" -#include "../support/utils.h" +#include "common.h" +#include "utils.h" #define DPU_CAPACITY (64 << 20) // A DPU's capacity is 64 MiB diff --git a/BFS/include/common.h b/BFS/include/common.h new file mode 100644 index 0000000..5f2aa0d --- /dev/null +++ b/BFS/include/common.h @@ -0,0 +1,25 @@ +#ifndef _COMMON_H_ +#define _COMMON_H_ + +#define ROUND_UP_TO_MULTIPLE_OF_2(x) ((((x) + 1)/2)*2) +#define ROUND_UP_TO_MULTIPLE_OF_8(x) ((((x) + 7)/8)*8) +#define ROUND_UP_TO_MULTIPLE_OF_64(x) ((((x) + 63)/64)*64) + +#define setBit(val, idx) (val) |= (1 << (idx)) +#define isSet(val, idx) ((val) & (1 << (idx))) + +struct DPUParams { + uint32_t dpuNumNodes; /* The number of nodes assigned to this DPU */ + uint32_t numNodes; /* Total number of nodes in the graph */ + uint32_t dpuStartNodeIdx; /* The index of the first node assigned to this DPU */ + uint32_t dpuNodePtrsOffset; /* Offset of the node pointers */ + uint32_t level; /* The current BFS level */ + uint32_t dpuNodePtrs_m; + uint32_t dpuNeighborIdxs_m; + uint32_t dpuNodeLevel_m; + uint32_t dpuVisited_m; + uint32_t dpuCurrentFrontier_m; + uint32_t dpuNextFrontier_m; +}; + +#endif diff --git a/BFS/include/dfatool_host.ah b/BFS/include/dfatool_host.ah new file mode 100644 index 0000000..592e6ec --- /dev/null +++ b/BFS/include/dfatool_host.ah @@ -0,0 +1,27 @@ +#pragma once + +#include +#include "dfatool_host_dpu.ah" + +aspect DfatoolHostTiming : public DfatoolHostDPUTiming { + + virtual int getKernel() { return 1; } + + DfatoolHostTiming() { + element_size = sizeof(uint32_t); + } + + advice call("% input_params(...)"): after() { + printf("[>>] BFS | n_dpus=%u\n", NR_DPUS); + } + + advice call("% coo2csr(...)") : after() { + struct CSRGraph *g = tjp->result(); + input_size = g->numNodes; + printf("[--] BFS | n_dpus=%u n_elements=%lu\n", NR_DPUS, input_size); + } + + advice execution("% main(...)") : after() { + printf("[<<] BFS | n_dpus=%u n_elements=%lu\n", NR_DPUS, input_size); + } +}; diff --git a/BFS/include/graph.h b/BFS/include/graph.h new file mode 100644 index 0000000..2a19f67 --- /dev/null +++ b/BFS/include/graph.h @@ -0,0 +1,133 @@ + +#ifndef _GRAPH_H_ +#define _GRAPH_H_ + +#include +#include + +#include "common.h" +#include "utils.h" + +struct COOGraph { + uint32_t numNodes; + uint32_t numEdges; + uint32_t *nodeIdxs; + uint32_t *neighborIdxs; +}; + +struct CSRGraph { + uint32_t numNodes; + uint32_t numEdges; + uint32_t *nodePtrs; + uint32_t *neighborIdxs; +}; + +static struct COOGraph readCOOGraph(const char *fileName) +{ + + struct COOGraph cooGraph; + + // Initialize fields + FILE *fp = fopen(fileName, "r"); + uint32_t numNodes, numCols; + assert(fscanf(fp, "%u", &numNodes)); + assert(fscanf(fp, "%u", &numCols)); + if (numNodes == numCols) { + cooGraph.numNodes = numNodes; + } else { + PRINT_WARNING + (" Adjacency matrix is not square. Padding matrix to be square."); + cooGraph.numNodes = (numNodes > numCols) ? numNodes : numCols; + } + if (cooGraph.numNodes % 64 != 0) { + PRINT_WARNING + (" Adjacency matrix dimension is %u which is not a multiple of 64 nodes.", + cooGraph.numNodes); + cooGraph.numNodes += (64 - cooGraph.numNodes % 64); + PRINT_WARNING + (" Padding to %u which is a multiple of 64 nodes.", + cooGraph.numNodes); + } + assert(fscanf(fp, "%u", &cooGraph.numEdges)); + cooGraph.nodeIdxs = + (uint32_t *) malloc(cooGraph.numEdges * sizeof(uint32_t)); + cooGraph.neighborIdxs = + (uint32_t *) malloc(cooGraph.numEdges * sizeof(uint32_t)); + + // Read the neighborIdxs + for (uint32_t edgeIdx = 0; edgeIdx < cooGraph.numEdges; ++edgeIdx) { + uint32_t nodeIdx; + assert(fscanf(fp, "%u", &nodeIdx)); + cooGraph.nodeIdxs[edgeIdx] = nodeIdx; + uint32_t neighborIdx; + assert(fscanf(fp, "%u", &neighborIdx)); + cooGraph.neighborIdxs[edgeIdx] = neighborIdx; + } + + return cooGraph; + +} + +static void freeCOOGraph(struct COOGraph cooGraph) +{ + free(cooGraph.nodeIdxs); + free(cooGraph.neighborIdxs); +} + +static struct CSRGraph coo2csr(struct COOGraph cooGraph) +{ + + struct CSRGraph csrGraph; + + // Initialize fields + csrGraph.numNodes = cooGraph.numNodes; + csrGraph.numEdges = cooGraph.numEdges; + csrGraph.nodePtrs = + (uint32_t *) + calloc(ROUND_UP_TO_MULTIPLE_OF_2(csrGraph.numNodes + 1), + sizeof(uint32_t)); + csrGraph.neighborIdxs = + (uint32_t *) + malloc(ROUND_UP_TO_MULTIPLE_OF_8 + (csrGraph.numEdges * sizeof(uint32_t))); + + // Histogram nodeIdxs + for (uint32_t i = 0; i < cooGraph.numEdges; ++i) { + uint32_t nodeIdx = cooGraph.nodeIdxs[i]; + csrGraph.nodePtrs[nodeIdx]++; + } + + // Prefix sum nodePtrs + uint32_t sumBeforeNextNode = 0; + for (uint32_t nodeIdx = 0; nodeIdx < csrGraph.numNodes; ++nodeIdx) { + uint32_t sumBeforeNode = sumBeforeNextNode; + sumBeforeNextNode += csrGraph.nodePtrs[nodeIdx]; + csrGraph.nodePtrs[nodeIdx] = sumBeforeNode; + } + csrGraph.nodePtrs[csrGraph.numNodes] = sumBeforeNextNode; + + // Bin the neighborIdxs + for (uint32_t i = 0; i < cooGraph.numEdges; ++i) { + uint32_t nodeIdx = cooGraph.nodeIdxs[i]; + uint32_t neighborListIdx = csrGraph.nodePtrs[nodeIdx]++; + csrGraph.neighborIdxs[neighborListIdx] = + cooGraph.neighborIdxs[i]; + } + + // Restore nodePtrs + for (uint32_t nodeIdx = csrGraph.numNodes - 1; nodeIdx > 0; --nodeIdx) { + csrGraph.nodePtrs[nodeIdx] = csrGraph.nodePtrs[nodeIdx - 1]; + } + csrGraph.nodePtrs[0] = 0; + + return csrGraph; + +} + +static void freeCSRGraph(struct CSRGraph csrGraph) +{ + free(csrGraph.nodePtrs); + free(csrGraph.neighborIdxs); +} + +#endif diff --git a/BFS/include/params.h b/BFS/include/params.h new file mode 100644 index 0000000..f9169bc --- /dev/null +++ b/BFS/include/params.h @@ -0,0 +1,67 @@ + +#ifndef _PARAMS_H_ +#define _PARAMS_H_ + +#include "common.h" +#include "utils.h" + +static void usage() +{ + PRINT("\nUsage: ./program [options]" + "\n" + "\nBenchmark-specific options:" + "\n -f input matrix file name (default=data/roadNet-CA.txt)" + "\n" + "\nGeneral options:" + "\n -v verbosity" "\n -h help" "\n\n"); +} + +typedef struct Params { + const char *fileName; + unsigned int verbosity; +#if NUMA + struct bitmask *bitmask_in; + int numa_node_cpu; +#endif +} Params; + +static struct Params input_params(int argc, char **argv) +{ + struct Params p; + p.fileName = "data/roadNet-CA.txt"; + p.verbosity = 0; +#if NUMA + p.bitmask_in = NULL; + p.numa_node_cpu = -1; +#endif + int opt; + while ((opt = getopt(argc, argv, "f:v:hA:C:")) >= 0) { + switch (opt) { + case 'f': + p.fileName = optarg; + break; + case 'v': + p.verbosity = atoi(optarg); + break; +#if NUMA + case 'A': + p.bitmask_in = numa_parse_nodestring(optarg); + break; + case 'C': + p.numa_node_cpu = atoi(optarg); + break; +#endif + case 'h': + usage(); + exit(0); + default: + PRINT_ERROR("Unrecognized option!"); + usage(); + exit(0); + } + } + + return p; +} + +#endif diff --git a/BFS/include/timer.h b/BFS/include/timer.h new file mode 100644 index 0000000..e85490f --- /dev/null +++ b/BFS/include/timer.h @@ -0,0 +1,8 @@ +#pragma once + +#define N_TIMERS 8 +#define startTimer start +#define stopTimer stop +#define zeroTimer zero +#include "../../include/timer_base.h" +#undef N_TIMERS diff --git a/BFS/include/utils.h b/BFS/include/utils.h new file mode 100644 index 0000000..ccd8fbd --- /dev/null +++ b/BFS/include/utils.h @@ -0,0 +1,10 @@ + +#ifndef _UTILS_H_ +#define _UTILS_H_ + +#define PRINT_ERROR(fmt, ...) fprintf(stderr, "\033[0;31mERROR:\033[0m " fmt "\n", ##__VA_ARGS__) +#define PRINT_WARNING(fmt, ...) fprintf(stderr, "\033[0;35mWARNING:\033[0m " fmt "\n", ##__VA_ARGS__) +#define PRINT_INFO(cond, fmt, ...) if(cond) printf("\033[0;32mINFO:\033[0m " fmt "\n", ##__VA_ARGS__); +#define PRINT(fmt, ...) printf(fmt "\n", ##__VA_ARGS__) + +#endif diff --git a/BFS/support/common.h b/BFS/support/common.h deleted file mode 100644 index 5f2aa0d..0000000 --- a/BFS/support/common.h +++ /dev/null @@ -1,25 +0,0 @@ -#ifndef _COMMON_H_ -#define _COMMON_H_ - -#define ROUND_UP_TO_MULTIPLE_OF_2(x) ((((x) + 1)/2)*2) -#define ROUND_UP_TO_MULTIPLE_OF_8(x) ((((x) + 7)/8)*8) -#define ROUND_UP_TO_MULTIPLE_OF_64(x) ((((x) + 63)/64)*64) - -#define setBit(val, idx) (val) |= (1 << (idx)) -#define isSet(val, idx) ((val) & (1 << (idx))) - -struct DPUParams { - uint32_t dpuNumNodes; /* The number of nodes assigned to this DPU */ - uint32_t numNodes; /* Total number of nodes in the graph */ - uint32_t dpuStartNodeIdx; /* The index of the first node assigned to this DPU */ - uint32_t dpuNodePtrsOffset; /* Offset of the node pointers */ - uint32_t level; /* The current BFS level */ - uint32_t dpuNodePtrs_m; - uint32_t dpuNeighborIdxs_m; - uint32_t dpuNodeLevel_m; - uint32_t dpuVisited_m; - uint32_t dpuCurrentFrontier_m; - uint32_t dpuNextFrontier_m; -}; - -#endif diff --git a/BFS/support/graph.h b/BFS/support/graph.h deleted file mode 100644 index 2a19f67..0000000 --- a/BFS/support/graph.h +++ /dev/null @@ -1,133 +0,0 @@ - -#ifndef _GRAPH_H_ -#define _GRAPH_H_ - -#include -#include - -#include "common.h" -#include "utils.h" - -struct COOGraph { - uint32_t numNodes; - uint32_t numEdges; - uint32_t *nodeIdxs; - uint32_t *neighborIdxs; -}; - -struct CSRGraph { - uint32_t numNodes; - uint32_t numEdges; - uint32_t *nodePtrs; - uint32_t *neighborIdxs; -}; - -static struct COOGraph readCOOGraph(const char *fileName) -{ - - struct COOGraph cooGraph; - - // Initialize fields - FILE *fp = fopen(fileName, "r"); - uint32_t numNodes, numCols; - assert(fscanf(fp, "%u", &numNodes)); - assert(fscanf(fp, "%u", &numCols)); - if (numNodes == numCols) { - cooGraph.numNodes = numNodes; - } else { - PRINT_WARNING - (" Adjacency matrix is not square. Padding matrix to be square."); - cooGraph.numNodes = (numNodes > numCols) ? numNodes : numCols; - } - if (cooGraph.numNodes % 64 != 0) { - PRINT_WARNING - (" Adjacency matrix dimension is %u which is not a multiple of 64 nodes.", - cooGraph.numNodes); - cooGraph.numNodes += (64 - cooGraph.numNodes % 64); - PRINT_WARNING - (" Padding to %u which is a multiple of 64 nodes.", - cooGraph.numNodes); - } - assert(fscanf(fp, "%u", &cooGraph.numEdges)); - cooGraph.nodeIdxs = - (uint32_t *) malloc(cooGraph.numEdges * sizeof(uint32_t)); - cooGraph.neighborIdxs = - (uint32_t *) malloc(cooGraph.numEdges * sizeof(uint32_t)); - - // Read the neighborIdxs - for (uint32_t edgeIdx = 0; edgeIdx < cooGraph.numEdges; ++edgeIdx) { - uint32_t nodeIdx; - assert(fscanf(fp, "%u", &nodeIdx)); - cooGraph.nodeIdxs[edgeIdx] = nodeIdx; - uint32_t neighborIdx; - assert(fscanf(fp, "%u", &neighborIdx)); - cooGraph.neighborIdxs[edgeIdx] = neighborIdx; - } - - return cooGraph; - -} - -static void freeCOOGraph(struct COOGraph cooGraph) -{ - free(cooGraph.nodeIdxs); - free(cooGraph.neighborIdxs); -} - -static struct CSRGraph coo2csr(struct COOGraph cooGraph) -{ - - struct CSRGraph csrGraph; - - // Initialize fields - csrGraph.numNodes = cooGraph.numNodes; - csrGraph.numEdges = cooGraph.numEdges; - csrGraph.nodePtrs = - (uint32_t *) - calloc(ROUND_UP_TO_MULTIPLE_OF_2(csrGraph.numNodes + 1), - sizeof(uint32_t)); - csrGraph.neighborIdxs = - (uint32_t *) - malloc(ROUND_UP_TO_MULTIPLE_OF_8 - (csrGraph.numEdges * sizeof(uint32_t))); - - // Histogram nodeIdxs - for (uint32_t i = 0; i < cooGraph.numEdges; ++i) { - uint32_t nodeIdx = cooGraph.nodeIdxs[i]; - csrGraph.nodePtrs[nodeIdx]++; - } - - // Prefix sum nodePtrs - uint32_t sumBeforeNextNode = 0; - for (uint32_t nodeIdx = 0; nodeIdx < csrGraph.numNodes; ++nodeIdx) { - uint32_t sumBeforeNode = sumBeforeNextNode; - sumBeforeNextNode += csrGraph.nodePtrs[nodeIdx]; - csrGraph.nodePtrs[nodeIdx] = sumBeforeNode; - } - csrGraph.nodePtrs[csrGraph.numNodes] = sumBeforeNextNode; - - // Bin the neighborIdxs - for (uint32_t i = 0; i < cooGraph.numEdges; ++i) { - uint32_t nodeIdx = cooGraph.nodeIdxs[i]; - uint32_t neighborListIdx = csrGraph.nodePtrs[nodeIdx]++; - csrGraph.neighborIdxs[neighborListIdx] = - cooGraph.neighborIdxs[i]; - } - - // Restore nodePtrs - for (uint32_t nodeIdx = csrGraph.numNodes - 1; nodeIdx > 0; --nodeIdx) { - csrGraph.nodePtrs[nodeIdx] = csrGraph.nodePtrs[nodeIdx - 1]; - } - csrGraph.nodePtrs[0] = 0; - - return csrGraph; - -} - -static void freeCSRGraph(struct CSRGraph csrGraph) -{ - free(csrGraph.nodePtrs); - free(csrGraph.neighborIdxs); -} - -#endif diff --git a/BFS/support/params.h b/BFS/support/params.h deleted file mode 100644 index f9169bc..0000000 --- a/BFS/support/params.h +++ /dev/null @@ -1,67 +0,0 @@ - -#ifndef _PARAMS_H_ -#define _PARAMS_H_ - -#include "common.h" -#include "utils.h" - -static void usage() -{ - PRINT("\nUsage: ./program [options]" - "\n" - "\nBenchmark-specific options:" - "\n -f input matrix file name (default=data/roadNet-CA.txt)" - "\n" - "\nGeneral options:" - "\n -v verbosity" "\n -h help" "\n\n"); -} - -typedef struct Params { - const char *fileName; - unsigned int verbosity; -#if NUMA - struct bitmask *bitmask_in; - int numa_node_cpu; -#endif -} Params; - -static struct Params input_params(int argc, char **argv) -{ - struct Params p; - p.fileName = "data/roadNet-CA.txt"; - p.verbosity = 0; -#if NUMA - p.bitmask_in = NULL; - p.numa_node_cpu = -1; -#endif - int opt; - while ((opt = getopt(argc, argv, "f:v:hA:C:")) >= 0) { - switch (opt) { - case 'f': - p.fileName = optarg; - break; - case 'v': - p.verbosity = atoi(optarg); - break; -#if NUMA - case 'A': - p.bitmask_in = numa_parse_nodestring(optarg); - break; - case 'C': - p.numa_node_cpu = atoi(optarg); - break; -#endif - case 'h': - usage(); - exit(0); - default: - PRINT_ERROR("Unrecognized option!"); - usage(); - exit(0); - } - } - - return p; -} - -#endif diff --git a/BFS/support/timer.h b/BFS/support/timer.h deleted file mode 100644 index 63b5567..0000000 --- a/BFS/support/timer.h +++ /dev/null @@ -1,31 +0,0 @@ - -#ifndef _TIMER_H_ -#define _TIMER_H_ - -#include -#include - -typedef struct Timer { - struct timeval startTime[8]; - struct timeval stopTime[8]; - double time[8]; -} Timer; - -static void startTimer(Timer *timer, int i, int rep) -{ - if (rep == 0) { - timer->time[i] = 0.0; - } - gettimeofday(&timer->startTime[i], NULL); -} - -static void stopTimer(Timer *timer, int i) -{ - gettimeofday(&timer->stopTime[i], NULL); - timer->time[i] += - (timer->stopTime[i].tv_sec - - timer->startTime[i].tv_sec) * 1000000.0 + - (timer->stopTime[i].tv_usec - timer->startTime[i].tv_usec); -} - -#endif diff --git a/BFS/support/utils.h b/BFS/support/utils.h deleted file mode 100644 index ccd8fbd..0000000 --- a/BFS/support/utils.h +++ /dev/null @@ -1,10 +0,0 @@ - -#ifndef _UTILS_H_ -#define _UTILS_H_ - -#define PRINT_ERROR(fmt, ...) fprintf(stderr, "\033[0;31mERROR:\033[0m " fmt "\n", ##__VA_ARGS__) -#define PRINT_WARNING(fmt, ...) fprintf(stderr, "\033[0;35mWARNING:\033[0m " fmt "\n", ##__VA_ARGS__) -#define PRINT_INFO(cond, fmt, ...) if(cond) printf("\033[0;32mINFO:\033[0m " fmt "\n", ##__VA_ARGS__); -#define PRINT(fmt, ...) printf(fmt "\n", ##__VA_ARGS__) - -#endif -- cgit v1.2.3