summaryrefslogtreecommitdiff
path: root/BFS/support
diff options
context:
space:
mode:
Diffstat (limited to 'BFS/support')
-rw-r--r--BFS/support/common.h26
-rw-r--r--BFS/support/graph.h116
-rw-r--r--BFS/support/params.h46
-rw-r--r--BFS/support/timer.h27
-rw-r--r--BFS/support/utils.h11
5 files changed, 226 insertions, 0 deletions
diff --git a/BFS/support/common.h b/BFS/support/common.h
new file mode 100644
index 0000000..ced324c
--- /dev/null
+++ b/BFS/support/common.h
@@ -0,0 +1,26 @@
+#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
new file mode 100644
index 0000000..f89ff5c
--- /dev/null
+++ b/BFS/support/graph.h
@@ -0,0 +1,116 @@
+
+#ifndef _GRAPH_H_
+#define _GRAPH_H_
+
+#include <assert.h>
+#include <stdio.h>
+
+#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
new file mode 100644
index 0000000..9bf9158
--- /dev/null
+++ b/BFS/support/params.h
@@ -0,0 +1,46 @@
+
+#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 <F> input matrix file name (default=data/roadNet-CA.txt)"
+ "\n"
+ "\nGeneral options:"
+ "\n -v <V> verbosity"
+ "\n -h help"
+ "\n\n");
+}
+
+typedef struct Params {
+ const char* fileName;
+ unsigned int verbosity;
+} Params;
+
+static struct Params input_params(int argc, char **argv) {
+ struct Params p;
+ p.fileName = "data/roadNet-CA.txt";
+ p.verbosity = 1;
+ int opt;
+ while((opt = getopt(argc, argv, "f:v:h")) >= 0) {
+ switch(opt) {
+ case 'f': p.fileName = optarg; break;
+ case 'v': p.verbosity = atoi(optarg); break;
+ 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
new file mode 100644
index 0000000..f8cd5fc
--- /dev/null
+++ b/BFS/support/timer.h
@@ -0,0 +1,27 @@
+
+#ifndef _TIMER_H_
+#define _TIMER_H_
+
+#include <stdio.h>
+#include <sys/time.h>
+
+typedef struct Timer {
+ struct timeval startTime;
+ struct timeval endTime;
+} Timer;
+
+static void startTimer(Timer* timer) {
+ gettimeofday(&(timer->startTime), NULL);
+}
+
+static void stopTimer(Timer* timer) {
+ gettimeofday(&(timer->endTime), NULL);
+}
+
+static float getElapsedTime(Timer timer) {
+ return ((float) ((timer.endTime.tv_sec - timer.startTime.tv_sec)
+ + (timer.endTime.tv_usec - timer.startTime.tv_usec)/1.0e6));
+}
+
+#endif
+
diff --git a/BFS/support/utils.h b/BFS/support/utils.h
new file mode 100644
index 0000000..ddb1e2c
--- /dev/null
+++ b/BFS/support/utils.h
@@ -0,0 +1,11 @@
+
+#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
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-03-11 12:10:57 +0000