SCAN-SSA: Add OpenMP variant

7 files changed, 236 insertions, 7 deletions

diff --git a/SCAN-SSA/Makefile b/SCAN-SSA/Makefile
index 00af65c..1ac9ecc 100644
--- a/SCAN-SSA/Makefile
+++ b/SCAN-SSA/Makefile
@@ -5,7 +5,8 @@ TYPE ?= INT64
 ENERGY ?= 0
 UNROLL ?= 1
 
-HOST_SOURCES := $(wildcard host/*.c)
+HOST_SOURCES := $(wildcard host/app.c)
+OMP_SOURCES := $(wildcard host/omp.c)
 DPU_SOURCES := $(wildcard dpu/*.c)
 
 COMMON_INCLUDES := support
@@ -30,7 +31,10 @@ bin/dpu_code: ${DPU_SOURCES}
 bin/host_code: ${HOST_SOURCES}
 	${QUIET}${CC} ${HOST_FLAGS} ${HOST_SOURCES} -o $@
 
+bin/omp_code: ${OMP_SOURCES}
+	${QUIET}${CC} ${HOST_FLAGS} -fopenmp ${OMP_SOURCES} -o $@
+
 clean:
-	${QUIET}${RM} -f bin/dpu_code bin/host_code
+	${QUIET}${RM} -f bin/dpu_code bin/host_code bin/omp_code
 
 .PHONY: all clean
diff --git a/SCAN-SSA/host/app.c b/SCAN-SSA/host/app.c
index 2d1b186..8354245 100644
--- a/SCAN-SSA/host/app.c
+++ b/SCAN-SSA/host/app.c
@@ -286,7 +286,7 @@ int main(int argc, char **argv) {
                 input_size / (timer.time[1] + timer.time[2] + timer.time[3] + timer.time[4]));
             printf("[::] n_dpus=%d n_tasklets=%d e_type=%s block_size_B=%d b_unroll=%d n_elements=%d | ",
                 nr_of_dpus, NR_TASKLETS, XSTR(T), BLOCK_SIZE, UNROLL, input_size);
-            printall(&timer);
+            printall(&timer, 5);
         } else {
             printf("[" ANSI_COLOR_RED "ERROR" ANSI_COLOR_RESET "] Outputs differ!\n");
         }
diff --git a/SCAN-SSA/host/omp.c b/SCAN-SSA/host/omp.c
new file mode 100644
index 0000000..efa5360
--- /dev/null
+++ b/SCAN-SSA/host/omp.c
@@ -0,0 +1,203 @@
+/**
+* app.c
+* SCAN-SSA Host Application Source File
+*
+*/
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <stdint.h>
+#include <unistd.h>
+#include <getopt.h>
+#include <assert.h>
+
+#include "../support/common.h"
+#include "../support/timer.h"
+#include "../support/params.h"
+
+#define XSTR(x) STR(x)
+#define STR(x) #x
+
+#define NR_DPUS 1
+
+extern int omp_get_num_threads();
+
+// Pointer declaration
+static T* A;
+static T* C;
+static T* C2;
+
+// Create input arrays
+static void read_input(T* A, unsigned int nr_elements, unsigned int nr_elements_round) {
+    srand(0);
+    printf("nr_elements\t%u\t", nr_elements);
+    for (unsigned int i = 0; i < nr_elements; i++) {
+        A[i] = (T) (rand());
+    }
+    for (unsigned int i = nr_elements; i < nr_elements_round; i++) {
+        A[i] = 0;
+    }
+}
+
+// Compute output in the host (slow reference implementation)
+static void scan_host(T* C, T* A, unsigned int nr_elements) {
+    C[0] = A[0];
+    for (unsigned int i = 1; i < nr_elements; i++) {
+        C[i] = C[i - 1] + A[i];
+    }
+}
+
+// Compute output in the host (OMP implementation)
+static void scan_omp(T* C, T* A, unsigned int nr_elements, unsigned int nr_threads) {
+    unsigned int i;
+    unsigned int elem_per_block = nr_elements / nr_threads;
+    T accum = 0;
+    T tmp[nr_threads];
+
+    // parallel block-wise scan
+#pragma omp parallel for
+    for (i=0; i < nr_threads; i++) {
+        unsigned int start_index = elem_per_block * i;
+        unsigned int stop_index = start_index + elem_per_block;
+        C[start_index] = A[start_index];
+        for (unsigned int j = start_index + 1; j < stop_index; j++) {
+            C[j] = C[j - 1] + A[j];
+        }
+    }
+
+    // sequential scan
+    tmp[0] = 0;
+    for (i=1; i < nr_threads; i++) {
+        unsigned int start_index = elem_per_block * i;
+        accum += C[start_index-1];
+        tmp[i] = accum;
+    }
+
+    // parallel block-wise add
+#pragma omp parallel for
+    for (i=0; i < nr_threads; i++) {
+        unsigned int start_index = elem_per_block * i;
+        unsigned int stop_index = start_index + elem_per_block;
+        for (unsigned int j = start_index; j < stop_index; j++) {
+            C[j] += tmp[i];
+        }
+    }
+}
+
+/*
+ * "SCAN" := [a1, a1, ..., an] -> [a1, a1 + a2, ..., a1 + a2 + ... + an]
+ * From the paper:
+ * SCAN-SSA has three steps:
+ * * (copy data to the DPU) (timer 1)
+ * * compute the partial scan operation locally inside each DPU (timer 2)
+ * * retrieve last element of each local scan from the DPUs, do a local (complete) scan on the last elements, and push them to the next DPU (timer 3)
+ * * finish the scan operation in each DPU (add sum [a1 ... ax] to a(x+1), ..., a(x+m) for DPU size m) (timer 4)
+ * * (retrieve results from DPU) (timer 5)
+ */
+
+// Main of the Host Application
+int main(int argc, char **argv) {
+
+    struct Params p = input_params(argc, argv);
+
+    unsigned int i = 0;
+
+    unsigned int nr_threads = 0;
+#pragma omp parallel
+#pragma omp atomic
+    nr_threads++;
+
+    const unsigned int input_size = p.input_size * nr_threads; // Total input size (weak or strong scaling)
+
+    // Input/output allocation
+    A = malloc(input_size * sizeof(T));
+    C = malloc(input_size * sizeof(T));
+    C2 = malloc(input_size * sizeof(T));
+    T *bufferC = C2;
+
+    // Create an input file with arbitrary data
+    read_input(A, input_size, input_size);
+
+    // Timer declaration
+    Timer timer;
+
+    // Loop over main kernel
+    for(int rep = 0; rep < p.n_warmup + p.n_reps; rep++) {
+
+        // Compute output on CPU (performance comparison and verification purposes)
+        if(rep >= p.n_warmup)
+            start(&timer, 0, 0);
+        scan_host(C, A, input_size);
+        if(rep >= p.n_warmup)
+            stop(&timer, 0);
+
+        // Compute output on CPU (OMP)
+        if(rep >= p.n_warmup)
+            start(&timer, 1, 0);
+        scan_omp(C2, A, input_size, nr_threads);
+        if(rep >= p.n_warmup)
+            stop(&timer, 1);
+
+        // Check output
+        bool status = true;
+        for (i = 0; i < input_size; i++) {
+            if(C[i] != bufferC[i]){ 
+                status = false;
+#if PRINT
+                printf("%d: %lu -- %lu\n", i, C[i], bufferC[i]);
+#endif
+            }
+        }
+        if (status) {
+            printf("[" ANSI_COLOR_GREEN "OK" ANSI_COLOR_RESET "] Outputs are equal\n");
+            printf("[::] n_threads=%d e_type=%s n_elements=%d "
+                "| throughput_cpu_ref_MBps=%f throughput_cpu_omp_MBps=%f\n",
+                nr_threads, XSTR(T), input_size,
+                input_size * sizeof(T) / timer.time[0],
+                input_size * sizeof(T) / timer.time[1]);
+            printf("[::] n_threads=%d e_type=%s n_elements=%d "
+                "| throughput_cpu_ref_MOpps=%f throughput_cpu_omp_MOpps=%f\n",
+                nr_threads, XSTR(T), input_size,
+                input_size / timer.time[0],
+                input_size / timer.time[1]);
+            printf("[::] n_threads=%d e_type=%s n_elements=%d | ",
+                nr_threads, XSTR(T), input_size);
+            printall(&timer, 1);
+        } else {
+            printf("[" ANSI_COLOR_RED "ERROR" ANSI_COLOR_RESET "] Outputs differ!\n");
+        }
+    }
+
+	/*
+    // Print timing results
+    printf("CPU ");
+    print(&timer, 0, p.n_reps);
+    printf("CPU-DPU ");
+    print(&timer, 1, p.n_reps);
+    printf("DPU Kernel Scan ");
+    print(&timer, 2, p.n_reps);
+    printf("Inter-DPU (Scan) ");
+    print(&timer, 3, p.n_reps);
+    printf("DPU Kernel Add ");
+    print(&timer, 4, p.n_reps);
+    printf("DPU-CPU ");
+    print(&timer, 5, p.n_reps);
+    printf("\n");
+	*/
+
+    #if ENERGY
+    double energy;
+    DPU_ASSERT(dpu_probe_get(&probe, DPU_ENERGY, DPU_AVERAGE, &energy));
+    printf("DPU Energy (J): %f\t", energy);
+    #endif	
+
+
+
+    // Deallocation
+    free(A);
+    free(C);
+    free(C2);
+	
+    return 0;
+}
diff --git a/SCAN-SSA/run-omp.sh b/SCAN-SSA/run-omp.sh
new file mode 100755
index 0000000..244ab1e
--- /dev/null
+++ b/SCAN-SSA/run-omp.sh
@@ -0,0 +1,23 @@
+#!/bin/bash
+
+set -e
+
+# T: data type
+# -w: number of un-timed warmup iterations
+# -e: number of timed iterations
+# -i: input size (number of elements, not number of bytes!)
+
+echo "prim-benchmarks SCAN-SSA (dfatool edition)"
+echo "Started at $(date)"
+echo "Revision $(git describe --always)"
+
+for nr_threads in 1 2 4 6 8 12 16 20 24 32; do
+	for i in 2048 4096 8192 16384 65536 262144 1048576 3932160 15728640 31457280; do
+		for dt in UINT32 UINT64 INT32 INT64 FLOAT DOUBLE; do
+			echo
+			if make -B TYPE=${dt} bin/omp_code; then
+				OMP_NUM_THREADS=$nr_threads bin/omp_code -w 0 -e 100 -i ${i} || true
+			fi
+		done
+	done
+done
diff --git a/SCAN-SSA/support/common.h b/SCAN-SSA/support/common.h
index 1c419da..0bdf7ca 100644
--- a/SCAN-SSA/support/common.h
+++ b/SCAN-SSA/support/common.h
@@ -58,7 +58,7 @@ typedef struct {
 #ifndef ENERGY
 #define ENERGY 0
 #endif
-#define PRINT 0 
+#define PRINT 0
 
 #define ANSI_COLOR_RED     "\x1b[31m"
 #define ANSI_COLOR_GREEN   "\x1b[32m"
diff --git a/SCAN-SSA/support/params.h b/SCAN-SSA/support/params.h
index cdc075d..8d51c98 100644
--- a/SCAN-SSA/support/params.h
+++ b/SCAN-SSA/support/params.h
@@ -17,7 +17,6 @@ static void usage() {
         "\n    -h        help"
         "\n    -w <W>    # of untimed warmup iterations (default=1)"
         "\n    -e <E>    # of timed repetition iterations (default=3)"
-        "\n    -x <X>    Weak (0) or strong (1) scaling (default=0)"
         "\n"
         "\nBenchmark-specific options:"
         "\n    -i <I>    input size (default=3932160 elements)"
diff --git a/SCAN-SSA/support/timer.h b/SCAN-SSA/support/timer.h
index 194569f..5411254 100644
--- a/SCAN-SSA/support/timer.h
+++ b/SCAN-SSA/support/timer.h
@@ -56,8 +56,8 @@ void stop(Timer *timer, int i) {
                       (timer->stopTime[i].tv_usec - timer->startTime[i].tv_usec);

 }

 

-void printall(Timer *timer) {

-    for (int i = 0; i <= 5; i++) {

+void printall(Timer *timer, int maxt) {

+    for (int i = 0; i <= maxt; i++) {

         printf(" timer%d_us=%f", i, timer->time[i]);

     }

     printf("\n");