BFS: AspectC++ (and behaviour model) support

6 files changed, 270 insertions, 0 deletions

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 <sys/time.h>
+#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 <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/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 <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;
+#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