From 97ba6163d9609df945d6b2bd5ef9b3537f3f56ba Mon Sep 17 00:00:00 2001 From: Daniel Friesel Date: Wed, 17 May 2023 16:11:16 +0200 Subject: SCAN-SSA: Add OpenMP variant --- SCAN-SSA/Makefile | 8 +- SCAN-SSA/host/app.c | 2 +- SCAN-SSA/host/omp.c | 203 ++++++++++++++++++++++++++++++++++++++++++++++ SCAN-SSA/run-omp.sh | 23 ++++++ SCAN-SSA/support/common.h | 2 +- SCAN-SSA/support/params.h | 1 - SCAN-SSA/support/timer.h | 4 +- 7 files changed, 236 insertions(+), 7 deletions(-) create mode 100644 SCAN-SSA/host/omp.c create mode 100755 SCAN-SSA/run-omp.sh 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 +#include +#include +#include +#include +#include +#include +#include + +#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 # of untimed warmup iterations (default=1)" "\n -e # of timed repetition iterations (default=3)" - "\n -x Weak (0) or strong (1) scaling (default=0)" "\n" "\nBenchmark-specific options:" "\n -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"); -- cgit v1.2.3