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.h34
-rw-r--r--BFS/support/utils.h11
5 files changed, 0 insertions, 233 deletions
diff --git a/BFS/support/common.h b/BFS/support/common.h
deleted file mode 100644
index ced324c..0000000
--- a/BFS/support/common.h
+++ /dev/null
@@ -1,26 +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 f89ff5c..0000000
--- a/BFS/support/graph.h
+++ /dev/null
@@ -1,116 +0,0 @@
-
-#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
deleted file mode 100644
index f4f12e7..0000000
--- a/BFS/support/params.h
+++ /dev/null
@@ -1,46 +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 <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 = 0;
- 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
deleted file mode 100644
index 80719cf..0000000
--- a/BFS/support/timer.h
+++ /dev/null
@@ -1,34 +0,0 @@
-
-#ifndef _TIMER_H_
-#define _TIMER_H_
-
-#include <stdio.h>
-#include <sys/time.h>
-
-typedef struct Timer {
- struct timeval startTime[5];
- struct timeval stopTime[5];
- double time[5];
-} 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);
-}
-
-static void printAll(Timer *timer, int maxt) {
- for (int i = 0; i <= maxt; i++) {
- printf(" timer%d_us=%f", i, timer->time[i]);
- }
- printf("\n");
-}
-
-#endif
diff --git a/BFS/support/utils.h b/BFS/support/utils.h
deleted file mode 100644
index ddb1e2c..0000000
--- a/BFS/support/utils.h
+++ /dev/null
@@ -1,11 +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
-
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-01 06:12:58 +0000