aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorHans-Nikolai Viessmann2016-07-12 16:24:45 +0100
committerHans-Nikolai Viessmann2016-07-12 16:24:45 +0100
commit5af21293df2bec349b2c3c89f781d9454594b4e0 (patch)
treec6a35bae3f7fc0d8164d7041916099fd5e698ce8
parent81ac41a1b864376f3c9fed5bbc6e4a461245bac9 (diff)
downloadopenspl-16-5af21293df2bec349b2c3c89f781d9454594b4e0.tar.gz
openspl-16-5af21293df2bec349b2c3c89f781d9454594b4e0.zip
Added code examples for Correlation stuff
-rw-r--r--README.md3
-rw-r--r--exercise1-correlation/dataflow-simulated/README.md4
-rw-r--r--exercise1-correlation/dataflow-simulated/correlationSAPI.h268
-rw-r--r--exercise1-correlation/dataflow-simulated/cpu-code.c276
-rw-r--r--exercise1-correlation/original/correlation.c191
-rw-r--r--exercise1-correlation/split/controlflow.c192
-rw-r--r--exercise1-correlation/split/dataflow.c91
-rw-r--r--exercise1-correlation/timeseries-times.dat9
8 files changed, 1034 insertions, 0 deletions
diff --git a/README.md b/README.md
index 00941e2..a82f905 100644
--- a/README.md
+++ b/README.md
@@ -5,3 +5,6 @@ Links
=====
- Main website: http://cc.doc.ic.ac.uk/opensplss/
+- Web IDE: http://webide2.maxeler.com/
+ Username: openspl_2016_4
+ Password: KyhcAj
diff --git a/exercise1-correlation/dataflow-simulated/README.md b/exercise1-correlation/dataflow-simulated/README.md
new file mode 100644
index 0000000..5ca0e16
--- /dev/null
+++ b/exercise1-correlation/dataflow-simulated/README.md
@@ -0,0 +1,4 @@
+This code does not work without the correlation.max file
+
+This code is evidently proprietary meaning that we can
+not look at the source code ---- WTF.
diff --git a/exercise1-correlation/dataflow-simulated/correlationSAPI.h b/exercise1-correlation/dataflow-simulated/correlationSAPI.h
new file mode 100644
index 0000000..e31f2fe
--- /dev/null
+++ b/exercise1-correlation/dataflow-simulated/correlationSAPI.h
@@ -0,0 +1,268 @@
+/**\file */
+#ifndef SLIC_DECLARATIONS_correlation_H
+#define SLIC_DECLARATIONS_correlation_H
+#include "MaxSLiCInterface.h"
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+#define correlation_numVectorsPerBurst (4)
+#define correlation_maxNumTimeseries (6000)
+#define correlation_maxNumVariables (6000)
+#define correlation_numTopScores (10)
+#define correlation_numPipes (12)
+
+
+
+/*============================ Action loadLMem ============================*/
+
+/*------------------------- Basic Static Interface ------------------------*/
+
+
+/* Run the action 'loadLMem'. */
+
+void correlation_loadLMem(
+ uint64_t param_numBursts, /* [in] Link to "numBursts". */
+ int32_t *param_CorrelationKernel_loopLength, /* [out] Link from "CorrelationKernel_loopLength". */
+ const void *instream_in_memLoad /* [in] The array is size of (param_numBursts * 384) bytes. */
+);
+
+
+/* Schedule to run the action 'loadLMem' on an engine and return immediately.
+ * The status of the run can be checked either by ::max_wait or ::max_nowait;
+ * note that one of these *must* be called, so that associated memory can be released.*/
+
+max_run_t *correlation_loadLMem_nonblock( /* Returns a handle on the execution status, or NULL in case of error. */
+ uint64_t param_numBursts, /* [in] Link to "numBursts". */
+ int32_t *param_CorrelationKernel_loopLength, /* [out] Link from "CorrelationKernel_loopLength". */
+ const void *instream_in_memLoad /* [in] The array is size of (param_numBursts * 384) bytes. */
+);
+
+
+/*----------------------- Advanced Static Interface -----------------------*/
+
+
+/* Structure containing parameters for executing action 'loadLMem' */
+
+typedef struct {
+ uint64_t param_numBursts; /* [in] Link to "numBursts". */
+ int32_t *param_CorrelationKernel_loopLength; /* [out] Link from "CorrelationKernel_loopLength". */
+ const void *instream_in_memLoad; /* [in] The array is size of (param_numBursts * 384) bytes. */
+} correlation_loadLMem_actions_t;
+
+
+/* Run the action 'loadLMem'. */
+
+void correlation_loadLMem_run(
+ max_engine_t *engine, /* [in] The engine on which the actions will be executed. */
+ correlation_loadLMem_actions_t *interface_actions /* [in, out] Structure containing the parameters for the action. */
+);
+
+
+/* Schedule to run the action 'loadLMem' on an engine and return immediately.
+ * The status of the run can be checked either by ::max_wait or ::max_nowait;
+ * note that one of these *must* be called, so that associated memory can be released.*/
+
+max_run_t *correlation_loadLMem_run_nonblock( /* Returns a handle on the execution status, or NULL in case of error. */
+ max_engine_t *engine, /* [in] The engine on which the actions will be executed. */
+ correlation_loadLMem_actions_t *interface_actions /* [in, out] Structure containing the parameters for the action. */
+);
+
+
+/* Group run of action 'loadLMem'. */
+
+void correlation_loadLMem_run_group(
+ max_group_t *group, /* [in] Group to use for executing action. */
+ correlation_loadLMem_actions_t *interface_actions /* [in, out] Structure containing the parameters for the action. */
+);
+
+
+/* Schedule the actions to run on the first device available in the group and return immediately.
+ * The status of the run must be checked with ::max_wait.
+ * Note that use of ::max_nowait is prohibited with non-blocking running on groups:
+ * see the ::max_run_group_nonblock documentation for more explanation. */
+
+max_run_t *correlation_loadLMem_run_group_nonblock( /* Returns a handle on the execution status, or NULL in case of error. */
+ max_group_t *group, /* [in] Group to use for executing action. */
+ correlation_loadLMem_actions_t *interface_actions /* [in, out] Structure containing the parameters for the action. */
+);
+
+
+/* Array run of action 'loadLMem'. */
+
+void correlation_loadLMem_run_array(
+ max_engarray_t *engarray, /* [in] The array of devices to use. */
+ correlation_loadLMem_actions_t *interface_actions[] /* [in, out] Array of structures containing the parameters for the actions. */
+);
+
+
+/* Schedule to run the array of actions on the array of engines, and return immediately.
+ * The length of interface_actions must match the size of engarray.
+ * The status of the run can be checked either by ::max_wait or ::max_nowait;
+ * note that one of these *must* be called, so that associated memory can be released. */
+
+max_run_t *correlation_loadLMem_run_array_nonblock( /* Returns a handle on the execution status, or NULL in case of error. */
+ max_engarray_t *engarray, /* [in] The array of devices to use. */
+ correlation_loadLMem_actions_t *interface_actions[] /* [in, out] Array of structures containing the parameters for the actions. */
+);
+
+
+/* Converts a static-interface action struct into a dynamic-interface max_actions_t struct.
+ * Note that this is an internal utility function used by other functions in the static interface. */
+
+max_actions_t* correlation_loadLMem_convert( /* Returns the dynamic-interface actions to run, or NULL in case of error. */
+ max_file_t *maxfile, /* [in] The maxfile to use. */
+ correlation_loadLMem_actions_t *interface_actions /* [in] The interface-specific actions to run. */
+);
+
+
+/* Auxiliary function to evaluate expression for "CorrelationKernel_loopLength". */
+
+int correlation_loadLMem_get_CorrelationKernel_loopLength(void);
+
+
+
+/*============================= Action default ============================*/
+
+/*------------------------- Basic Static Interface ------------------------*/
+
+
+/* Run the action 'default'. */
+
+void correlation(
+ uint64_t param_numBursts, /* [in] Link to "numBursts" -> The size of data of one correlation step in number of bursts. */
+ uint64_t param_numSteps, /* [in] Link to "numSteps" -> The number of (full) correlation steps. */
+ uint64_t param_numVariables, /* [in] Link to "numVariables" -> The number of (input) variables. */
+ uint64_t param_outputLastStep, /* [in] Link to "outputLastStep" -> Non-zero iff all correlations of the last step shall be returned. */
+ double param_windowSize, /* [in] Link to "windowSize" -> The window size. */
+ const double *instream_in_precalculations, /* [in] The array is size of (2 * param_numSteps * param_numVariables). */
+ const double *instream_in_variable_pair, /* [in] The array is size of (2 * param_numSteps * param_numVariables). */
+ double *outstream_out_correlation, /* [out] The array is size of (10 * 12 * param_numSteps * param_CorrelationKernel_loopLength) +
+ (param_outputLastStep==0 ? param_numBursts * 48 : 0). */
+ uint32_t *outstream_out_indices /* The array is size of (2 * 10 * 12 * param_numSteps * param_loopLength). */
+);
+
+
+/* Schedule to run the action 'default' on an engine and return immediately.
+ * The status of the run can be checked either by ::max_wait or ::max_nowait;
+ * note that one of these *must* be called, so that associated memory can be released.*/
+
+max_run_t* correlation_nonblock( /* Returns a handle on the execution status, or NULL in case of error. */
+ uint64_t param_numBursts, /* [in] Link to "numBursts" -> The size of data of one correlation step in number of bursts. */
+ uint64_t param_numSteps, /* [in] Link to "numSteps" -> The number of (full) correlation steps. */
+ uint64_t param_numVariables, /* [in] Link to "numVariables" -> The number of (input) variables. */
+ uint64_t param_outputLastStep, /* [in] Link to "outputLastStep" -> Non-zero iff all correlations of the last step shall be returned. */
+ double param_windowSize, /* [in] Link to "windowSize" -> The window size. */
+ const double *instream_in_precalculations, /* [in] The array is size of (2 * param_numSteps * param_numVariables). */
+ const double *instream_in_variable_pair, /* [in] The array is size of (2 * param_numSteps * param_numVariables). */
+ double *outstream_out_correlation, /* [out] The array is size of (10 * 12 * param_numSteps * param_CorrelationKernel_loopLength) +
+ (param_outputLastStep==0 ? param_numBursts * 48 : 0). */
+ uint32_t *outstream_out_indices /* The array is size of (2 * 10 * 12 * param_numSteps * param_loopLength). */
+);
+
+
+/*----------------------- Advanced Static Interface -----------------------*/
+
+
+/* Structure containing parameters for executing action 'default'. */
+
+typedef struct {
+ uint64_t param_numBursts; /* [in] Link to "numBursts" -> The size of data of one correlation step in number of bursts. */
+ uint64_t param_numSteps; /* [in] Link to "numSteps" -> The number of (full) correlation steps. */
+ uint64_t param_numVariables; /* [in] Link to "numVariables" -> The number of (input) variables. */
+ uint64_t param_outputLastStep; /* [in] Link to "outputLastStep" -> Non-zero iff all correlations of the last step shall be returned. */
+ double param_windowSize; /* [in] Link to "windowSize" -> The window size. */
+ const double *instream_in_precalculations; /* [in] The array is size of (2 * param_numSteps * param_numVariables). */
+ const double *instream_in_variable_pair; /* [in] The array is size of (2 * param_numSteps * param_numVariables). */
+ double *outstream_out_correlation; /* [out] The array is size of (10 * 12 * param_numSteps * param_CorrelationKernel_loopLength) +
+ (param_outputLastStep==0 ? param_numBursts * 48 : 0). */
+ uint32_t *outstream_out_indices; /* The array is size of (2 * 10 * 12 * param_numSteps * param_loopLength). */
+} correlation_actions_t;
+
+
+/* Run the actions 'default'. */
+
+void correlation_run(
+ max_engine_t *engine, /* [in] The engine on which the actions will be executed. */
+ correlation_actions_t *interface_actions /* [in, out] Structure containing the parameters for the action. */
+);
+
+/* Schedule to run the action 'default' on an engine and return immediately.
+ * The status of the run can be checked either by ::max_wait or ::max_nowait;
+ * note that one of these *must* be called, so that associated memory can be released.*/
+
+max_run_t *correlation_run_nonblock( /* Returns a handle on the execution status, or NULL in case of error. */
+ max_engine_t *engine, /* [in] The engine on which the actions will be executed. */
+ correlation_actions_t *interface_actions); /* [in, out] Structure containing the parameters for the action. */
+
+
+/* Group run of action 'default'. */
+
+void correlation_run_group(
+ max_group_t *group, /* [in] Group to use for executing action. */
+ correlation_actions_t *interface_actions /* [in, out] Structure containing the parameters for the action. */
+);
+
+
+/* Schedule the actions to run on the first device available in the group and return immediately.
+ * The status of the run must be checked with ::max_wait.
+ * Note that use of ::max_nowait is prohibited with non-blocking running on groups:
+ * see the ::max_run_group_nonblock documentation for more explanation. */
+
+max_run_t *correlation_run_group_nonblock( /* Returns a handle on the execution status, or NULL in case of error. */
+ max_group_t *group, /* [in] Group to use for executing action. */
+ correlation_actions_t *interface_actions /* [in, out] Structure containing the parameters for the action. */
+);
+
+
+/* Array run of action 'default'. */
+
+void correlation_run_array(
+ max_engarray_t *engarray, /* [in] The array of devices to use. */
+ correlation_actions_t *interface_actions[] /* [in, out] Array of structures containing the parameters for the actions. */
+);
+
+
+/* Schedule to run the array of actions on the array of engines, and return immediately.
+ * The length of interface_actions must match the size of engarray.
+ * The status of the run can be checked either by ::max_wait or ::max_nowait;
+ * note that one of these *must* be called, so that associated memory can be released. */
+
+max_run_t *correlation_run_array_nonblock( /* Returns a handle on the execution status, or NULL in case of error. */
+ max_engarray_t *engarray, /* [in] The array of devices to use. */
+ correlation_actions_t *interface_actions[] /* [in, out] Array of structures containing the parameters for the actions. */
+);
+
+
+/* Converts a static-interface action struct into a dynamic-interface max_actions_t struct.
+ * Note that this is an internal utility function used by other functions in the static interface. */
+
+max_actions_t* correlation_convert( /* Returns the dynamic-interface actions to run, or NULL in case of error. */
+ max_file_t *maxfile, /* [in] The maxfile to use. */
+ correlation_actions_t *interface_actions /* [in] The interface-specific actions to run. */
+);
+
+/* Auxiliary function to evaluate expression for "CorrelationKernel_loopLength". */
+
+int correlation_get_CorrelationKernel_loopLength(void);
+
+
+/* Initialise a maxfile. */
+max_file_t* correlation_init(void);
+
+/* Error handling functions */
+int correlation_has_errors(void);
+const char* correlation_get_errors(void);
+void correlation_clear_errors(void);
+/* Free statically allocated maxfile data */
+void correlation_free(void);
+/* returns: -1 = error running command; 0 = no error reported */
+int correlation_simulator_start(void);
+/* returns: -1 = error running command; 0 = no error reported */
+int correlation_simulator_stop(void);
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+#endif /* SLIC_DECLARATIONS_correlation_H */
+
diff --git a/exercise1-correlation/dataflow-simulated/cpu-code.c b/exercise1-correlation/dataflow-simulated/cpu-code.c
new file mode 100644
index 0000000..7f02a45
--- /dev/null
+++ b/exercise1-correlation/dataflow-simulated/cpu-code.c
@@ -0,0 +1,276 @@
+/**
+ * File: correlationCPUCode.c
+ * Purpose: calling correlationSAPI.h for correlation.max
+ *
+ * Correlation formula:
+ * scalar r(x,y) = (n*SUM(x,y) - SUM(x)*SUM(y))*SQRT_INVERSE(x)*SQRT_INVERSE(y)
+ * where:
+ * x,y,... - Time series data to be correlated
+ * n - window for correlation (minimum size of 2)
+ * SUM(x) - sum of all elements inside a window
+ * SQRT_INVERSE(x) - 1/sqrt(n*SUM(x^2)- (SUM(x)^2))
+ *
+ * Streams:
+ *
+ * Action 'loadLMem':
+ * ------------------
+ * [in] memLoad - content which LMem will be initialized with
+ *
+ *
+ * Action 'default':
+ * -----------------
+ *
+ * [in] precalculations - {SUM(x), SQRT_INVERSE(x)} for all timeseries for every timestep
+ *
+ * [in] data_pair - {..., x[i], x[i-n], y[i], y[i-n], ... , x[i+1], x[i-n+1], y[i+1], y[i-n+1], ...} for all timeseries for every timestep;
+ * IF (i-n)<0 => x[i-n]=0
+ *
+ * [out] correlation - numPipes * CorrelationKernel_loopLength * topScores correlations for every timestep
+ *
+ * [out] indices - pair of timeseries indices for each result in correlation stream
+ *
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <math.h>
+#include <time.h>
+#include <inttypes.h>
+#include <sys/time.h>
+
+
+#include "correlationSAPI.h"
+
+
+//Time measuring
+double gettime(void) {
+ struct timeval tv;
+ gettimeofday(&tv, NULL);
+ return tv.tv_sec + 1e-6 * tv.tv_usec;
+}
+
+// Calculate number of bursts for initializing LMem
+size_t calcNumBursts (size_t numTimeseries) {
+
+ size_t numVectors = 0;
+ for (size_t i = 1; i <= numTimeseries; ++i)
+ numVectors += (i + (correlation_numPipes - 1)) / correlation_numPipes;
+
+ return (numVectors + (correlation_numVectorsPerBurst-1)) / correlation_numVectorsPerBurst;
+}
+
+
+//Calculate top correlations
+void topCorrelations (double* correlations, uint32_t* indices, uint64_t numCorrelations, double* correlations_top, uint32_t* indices_top, int numTopScores) {
+
+ for (uint64_t step=0; step<numCorrelations-1; ++step) {
+ for (uint64_t i=0; i<numCorrelations-step-1; ++i) {
+ if (correlations[i]<correlations[i+1]) {
+ double temp_corr = correlations[i];
+ uint32_t temp_in1 = indices[2*i];
+ uint32_t temp_in2 = indices[2*i+1];
+
+ correlations[i] = correlations[i+1];
+ indices[2*i] = indices[2*(i+1)];
+ indices[2*i+1] = indices[2*(i+1)+1];
+
+ correlations[i+1] = temp_corr;
+ indices[2*(i+1)] = temp_in1;
+ indices[2*(i+1)+1] = temp_in2;
+
+ }
+ }
+ }
+
+ memcpy(correlations_top, correlations, numTopScores*sizeof(double));
+ memcpy(indices_top, indices, 2*numTopScores*sizeof(uint32_t));
+}
+
+
+void prepare_data_for_dfe (double** data, uint64_t sizeTimeseries, uint64_t numTimeseries, uint64_t numTimesteps, double windowSize, double* precalculations, double* data_pairs) {
+
+ if (numTimeseries > correlation_maxNumTimeseries) {
+ fprintf(stderr, "Number of Time series should be less or equal to %d. Terminating!\n", correlation_maxNumTimeseries);
+ fflush(stderr);
+ exit(-1);
+ }
+
+ if (windowSize <2) {
+ fprintf(stderr, "Window size must be equal or greater than 2. Terminating!\n");
+ fflush(stderr);
+ exit(-1);
+ }
+
+ if (numTimesteps > sizeTimeseries) {
+ fprintf(stderr, "Number of Time steps should be less or equal to size of Time series. Terminating!\n");
+ fflush(stderr);
+ exit(-1);
+ }
+
+ int64_t old_index;
+ double old, new;
+
+ double** sums = (double**) malloc (numTimesteps*sizeof (double*));
+ double** sums_sq = (double**) malloc (numTimesteps*sizeof (double*));
+ double** inv = (double**) malloc (numTimesteps*sizeof (double*));
+
+ for (uint64_t i=0; i < numTimesteps; i++) {
+ sums[i] = (double*) malloc (numTimeseries*sizeof(double));
+ sums_sq[i] = (double*) malloc (numTimeseries*sizeof(double));
+ inv[i] = (double*) malloc (numTimeseries*sizeof(double));
+ }
+
+ // 2 DFE input streams: precalculations and data pairs
+ for (uint64_t i=0; i<numTimesteps; i++) {
+
+ old_index = i - (uint64_t)windowSize;
+
+ for (uint64_t j=0; j<numTimeseries; j++) {
+ if (old_index<0)
+ old = 0;
+ else
+ old = data [j][old_index];
+
+ new = data [j][i];
+
+ if (i==0) {
+ sums [i][j] = new;
+ sums_sq [i][j] = new*new;
+ }
+ else {
+ sums [i][j] = sums [i-1][j] + new - old;
+ sums_sq [i][j] = sums_sq [i-1][j] + new*new - old*old;
+ }
+
+ inv [i][j] = 1/sqrt((uint64_t)windowSize*sums_sq[i][j] - sums[i][j]*sums[i][j]);
+
+ //Precalculations REORDERED in DFE ORDER
+ precalculations [2*i*numTimeseries + 2*j] = sums[i][j];
+ precalculations [2*i*numTimeseries + 2*j + 1] = inv [i][j];
+
+ //Data pairs REORDERED in DFE ORDER
+ data_pairs[2*i*numTimeseries + 2*j] = new;
+ data_pairs[2*i*numTimeseries + 2*j + 1] = old;
+ }
+ }
+
+ for (uint64_t i=0; i<numTimesteps; i++) {
+ free (sums[i]);
+ free (sums_sq[i]);
+ free (inv[i]);
+ }
+
+ free (sums);
+ free (sums_sq);
+ free (inv);
+
+}
+
+void random_data (double** data, uint64_t numTimeseries, uint64_t sizeTimeseries) {
+
+ srand(time(NULL));
+
+ for (uint64_t i=0; i<numTimeseries; i++) {
+ for (uint64_t j=0; j<sizeTimeseries; j++) {
+ data[i][j] = ((double)rand()/(double)RAND_MAX);
+ }
+ }
+}
+
+
+int main () {
+
+ uint64_t numTimesteps = 10; // not limited by DFE
+ uint64_t numTimeseries = 200; // DFE supports 200 - 6000, Simulation supports 250 - 6000
+ double windowSize = 9;
+
+ uint64_t sizeTimeseries = 100; // number of elements in the timeseries
+
+ uint64_t numBursts = calcNumBursts (numTimeseries);
+ int32_t loopLength = correlation_get_CorrelationKernel_loopLength();
+ double start_time, reorder_time, DFE_time, sort_time, total_time;
+
+
+ /*===================== INITIALIZING =====================*/
+
+ double** data = (double**) malloc (numTimeseries*sizeof (double*));
+ for (uint64_t i=0; i < numTimeseries; i++)
+ data[i] = (double*) malloc (sizeTimeseries*sizeof(double));
+
+ printf("Generating data!\n");
+ random_data (data, numTimeseries, sizeTimeseries);
+
+ double* precalculations = (double*) malloc (2 * numTimeseries * numTimesteps * sizeof(double));
+ double* data_pairs = (double*) malloc (2 * numTimeseries * numTimesteps * sizeof(double));
+
+ void* in_memLoad = (void*) malloc (numBursts * 384);
+ memset(in_memLoad,0,numBursts*384);
+
+ // DFE outputs
+ double* out_correlation = (double*) malloc (numTimesteps * loopLength * correlation_numTopScores * correlation_numPipes * sizeof(double));
+ uint32_t* out_indices = (uint32_t*) malloc (2 * numTimesteps * loopLength * correlation_numTopScores * correlation_numPipes * sizeof(uint32_t));
+
+ // Top correlations for every timestep
+ double* correlations_final = (double*) malloc (correlation_numTopScores*numTimesteps*sizeof(double));
+ uint32_t* indices_final = (uint32_t*) malloc (2 * correlation_numTopScores*numTimesteps*sizeof(double));
+
+
+ /*==================== REORDERING DATA for the DFE ====================*/
+
+ printf("Reordering data for the DFE.\n");
+ start_time = gettime();
+ prepare_data_for_dfe (data, sizeTimeseries, numTimeseries, numTimesteps, windowSize, precalculations, data_pairs);
+ reorder_time = gettime() - start_time;
+
+ /*==================== Computation ====================*/
+
+ printf("CORRELATE!\n");
+ start_time = gettime();
+
+ //Executing loadLMem action
+ correlation_loadLMem(numBursts, &loopLength, in_memLoad);
+ printf("LMem initialized!\n");
+
+ //Executing correlation action
+ correlation(numBursts, numTimesteps, numTimeseries, 0, windowSize, // scalar inputs
+ precalculations, data_pairs, // streaming reordered inputs
+ out_correlation, out_indices // streaming unordered outputs
+ );
+
+ DFE_time = gettime() - start_time;
+ printf("DFE done!\n");
+
+ //CPU sorting outputs
+ int correlations_per_step = loopLength * correlation_numTopScores * correlation_numPipes; // number of correlations in output per timestep
+ start_time = gettime();
+
+ printf("Sorting outputs.\n");
+ for (uint64_t i=0; i<numTimesteps; i++) {
+ topCorrelations (&out_correlation[i*correlations_per_step], &out_indices[2*i*correlations_per_step], correlations_per_step,
+ &correlations_final[i*correlation_numTopScores], &indices_final[i*correlation_numTopScores], correlation_numTopScores);
+ }
+ sort_time = gettime() - start_time;
+
+ total_time = reorder_time + DFE_time + sort_time;
+
+ printf("TimeSeries: %" PRIu64 ", TimeSteps: %" PRIu64 "\n", numTimeseries, numTimesteps);
+ printf("Data reordering time: %.5lfs\n", reorder_time);
+ printf("DFE execution time: %.5lfs\n", DFE_time);
+ printf("Sorting time: %.5lfs\n", sort_time);
+ printf("Total execution time: %.5lfs\n", total_time);
+
+ //Deallocating memory
+ free (out_indices);
+ free (out_correlation);
+ free (in_memLoad);
+ free (data_pairs);
+ free (precalculations);
+ free (correlations_final);
+ free (indices_final);
+
+ for (uint64_t i=0; i<numTimeseries; i++)
+ free (data[i]);
+ free (data);
+ return 0;
+}
diff --git a/exercise1-correlation/original/correlation.c b/exercise1-correlation/original/correlation.c
new file mode 100644
index 0000000..8d19b6c
--- /dev/null
+++ b/exercise1-correlation/original/correlation.c
@@ -0,0 +1,191 @@
+/**
+ * File: correlation.c
+ *
+ * Correlation formula:
+ * scalar r(x,y) = (n*SUM(x,y) - SUM(x)*SUM(y))*SQRT_INVERSE(x)*SQRT_INVERSE(y)
+ * where:
+ * x,y,... - Time series data to be correlated
+ * n - window for correlation (minimum size of 2)
+ * SUM(x) - sum of all elements inside a window
+ * SQRT_INVERSE(x) - 1/sqrt(n*SUM(x^2)- (SUM(x)^2))
+ *
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <math.h>
+#include <time.h>
+#include <inttypes.h>
+#include <sys/time.h>
+#include <string.h>
+
+#define correlation_maxNumTimeseries (6000)
+#define correlation_numTopScores (10)
+
+
+//Time measuring
+double gettime(void) {
+ struct timeval tv;
+ gettimeofday(&tv, NULL);
+ return tv.tv_sec + 1e-6 * tv.tv_usec;
+}
+
+//Generating random data
+void random_data (double** data, uint64_t numTimeseries, uint64_t sizeTimeseries) {
+
+ srand(time(NULL));
+
+ for (uint64_t i=0; i<numTimeseries; i++) {
+ for (uint64_t j=0; j<sizeTimeseries; j++) {
+ data[i][j] = ((double)rand()/(double)RAND_MAX);
+ }
+ }
+}
+
+//Calculate top correlations
+void topCorrelations (double* correlations, uint32_t* indices, uint64_t numCorrelations, double* correlations_top, uint32_t* indices_top, int numTopScores) {
+
+ for (uint64_t step=0; step<numCorrelations-1; ++step) {
+ for (uint64_t i=0; i<numCorrelations-step-1; ++i) {
+ if (correlations[i]<correlations[i+1]) {
+ double temp_corr = correlations[i];
+ uint32_t temp_in1 = indices[2*i];
+ uint32_t temp_in2 = indices[2*i+1];
+
+ correlations[i] = correlations[i+1];
+ indices[2*i] = indices[2*(i+1)];
+ indices[2*i+1] = indices[2*(i+1)+1];
+
+ correlations[i+1] = temp_corr;
+ indices[2*(i+1)] = temp_in1;
+ indices[2*(i+1)+1] = temp_in2;
+
+ }
+ }
+ }
+
+ memcpy(correlations_top, correlations, numTopScores*sizeof(double));
+ memcpy(indices_top, indices, 2*numTopScores*sizeof(uint32_t));
+}
+
+
+void correlation (double** data, uint64_t sizeTimeseries, uint64_t numTimeseries, uint64_t numTimesteps, uint64_t windowSize, double* correlations, uint32_t* indices) {
+
+ if (numTimeseries > correlation_maxNumTimeseries) {
+ fprintf(stderr, "Number of Time series should be less or equal to %d. Terminating!\n", correlation_maxNumTimeseries);
+ fflush(stderr);
+ exit(-1);
+ }
+
+ if (windowSize <2) {
+ fprintf(stderr, "Window size must be equal or greater than 2. Terminating!\n");
+ fflush(stderr);
+ exit(-1);
+ }
+
+ if (numTimesteps > sizeTimeseries) {
+ fprintf(stderr, "Number of Time steps should be less or equal to size of Time series. Terminating!\n");
+ fflush(stderr);
+ exit(-1);
+ }
+
+ uint64_t numCorrelations = (numTimeseries*(numTimeseries-1))/2;
+
+ double* sums = (double*) calloc (numTimeseries,sizeof(double));
+ double* sums_sq = (double*) calloc (numTimeseries, sizeof(double));
+ double* sums_xy = (double*) calloc (numCorrelations, sizeof(double));
+ double* correlations_step = (double*) calloc (numCorrelations, sizeof(double)); // all correlations in current step
+ uint32_t* indices_step = (uint32_t*) calloc (2*numCorrelations, sizeof(uint32_t)); // corresponding indices for correlations_step
+ double* correlations_top = (double*) malloc (correlation_numTopScores*sizeof(double)); // top correlations in current step
+ uint32_t* indices_top = (uint32_t*) malloc (2*correlation_numTopScores*sizeof(uint32_t)); // corresponding indices for correlations_top
+
+ uint64_t index_correlation;
+
+ for (uint64_t s=0; s<numTimesteps; s++) {
+
+ index_correlation = 0;
+
+ for (uint64_t i=0; i<numTimeseries; i++) {
+
+ double old = s>=windowSize ? data[i][s-windowSize] : 0;
+ double new = data [i][s];
+
+ sums[i] += new - old;
+ sums_sq[i] += new*new - old*old;
+ }
+
+ for (uint64_t i=0; i<numTimeseries; i++) {
+
+ double old_x = s>=windowSize ? data[i][s-windowSize] : 0;
+ double new_x = data [i][s];
+
+ for (uint64_t j=i+1; j<numTimeseries; j++) {
+
+ double old_y = s>=windowSize ? data[j][s-windowSize] : 0;
+ double new_y = data [j][s];
+
+ sums_xy[index_correlation] += new_x*new_y - old_x*old_y;
+
+ correlations_step[index_correlation] = (windowSize*sums_xy[index_correlation]-sums[i]*sums[j])/
+ (sqrt(windowSize*sums_sq[i]-sums[i]*sums[i])*sqrt(windowSize*sums_sq[j]-sums[j]*sums[j]));
+
+ indices_step[2*index_correlation] = j;
+ indices_step[2*index_correlation+1] = i;
+
+ index_correlation++;
+
+ }
+ }
+ topCorrelations (correlations_step, indices_step, numCorrelations, correlations_top, indices_top, correlation_numTopScores);
+
+ memcpy(&correlations[s*correlation_numTopScores], correlations_top, correlation_numTopScores*sizeof(double));
+ memcpy(&indices[2*s*correlation_numTopScores], indices_top, 2*correlation_numTopScores*sizeof(uint32_t));
+
+ }
+
+ free(sums);
+ free(sums_sq);
+ free(sums_xy);
+ free(correlations_step);
+ free(indices_step);
+ free(correlations_top);
+ free(indices_top);
+}
+
+
+int main () {
+
+ uint64_t numTimesteps = 10;
+ uint64_t numTimeseries = 400; //200
+ double windowSize = 9;
+
+ uint64_t sizeTimeseries = 100;
+
+ double time;
+
+ double** data = (double**) malloc (numTimeseries*sizeof (double*));
+ for (uint64_t i=0; i < numTimeseries; i++)
+ data[i] = (double*) malloc (sizeTimeseries*sizeof(double));
+
+ double* correlations = (double*) malloc (numTimesteps*correlation_numTopScores*sizeof(double));
+ uint32_t* indices = (uint32_t*) malloc (2*numTimesteps*correlation_numTopScores*sizeof(uint32_t));
+
+ printf("Generating random data.\n");
+ random_data (data, numTimeseries, sizeTimeseries);
+
+ printf("Correlate.\n");
+ time = gettime();
+ correlation (data, sizeTimeseries, numTimeseries, numTimesteps, windowSize, correlations, indices);
+ printf("TimeSeries: %" PRIu64 ", TimeSteps: %" PRIu64 "\n", numTimeseries, numTimesteps);
+ printf("Total correlation time: %.5lfs\n", gettime()-time);
+
+ //Deallocating memory
+ free (correlations);
+ free (indices);
+ for (uint64_t i=0; i<numTimeseries; i++)
+ free (data[i]);
+ free (data);
+
+ return 0;
+}
diff --git a/exercise1-correlation/split/controlflow.c b/exercise1-correlation/split/controlflow.c
new file mode 100644
index 0000000..7e9375f
--- /dev/null
+++ b/exercise1-correlation/split/controlflow.c
@@ -0,0 +1,192 @@
+/**
+ * File: correlationCPUCode.c
+ * Purpose: calling correlationSAPI.h for correlation.max
+ *
+ * Correlation formula:
+ * scalar r(x,y) = (n*SUM(x,y) - SUM(x)*SUM(y))*SQRT_INVERSE(x)*SQRT_INVERSE(y)
+ * where:
+ * x,y,... - Time series data to be correlated
+ * n - window for correlation (minimum size of 2)
+ * SUM(x) - sum of all elements inside a window
+ * SQRT_INVERSE(x) - 1/sqrt(n*SUM(x^2)- (SUM(x)^2))
+ *
+ */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <math.h>
+#include <time.h>
+#include <inttypes.h>
+#include <sys/time.h>
+#include <string.h>
+
+#define correlation_maxNumTimeseries (6000)
+#define correlation_numTopScores (10)
+
+// Function is from correlation_data.c
+void correlation_data_flow (uint64_t numTimesteps, uint64_t numTimeSeries, uint64_t windowSize,
+ double* precalculations, double*data_pairs,
+ double* correlations, uint32_t* indices);
+
+
+//Time measuring
+double gettime(void) {
+ struct timeval tv;
+ gettimeofday(&tv, NULL);
+ return tv.tv_sec + 1e-6 * tv.tv_usec;
+}
+
+
+void correlation_control_flow (double** data, uint64_t sizeTimeseries, uint64_t numTimeseries, uint64_t numTimesteps, double windowSize, double* precalculations, double* data_pairs) {
+
+ if (numTimeseries > correlation_maxNumTimeseries) {
+ fprintf(stderr, "Number of Time series should be less or equal to %d. Terminating!\n", correlation_maxNumTimeseries);
+ fflush(stderr);
+ exit(-1);
+ }
+
+ if (windowSize <2) {
+ fprintf(stderr, "Window size must be equal or greater than 2. Terminating!\n");
+ fflush(stderr);
+ exit(-1);
+ }
+
+ if (numTimesteps > sizeTimeseries) {
+ fprintf(stderr, "Number of Time steps should be less or equal to size of Time series. Terminating!\n");
+ fflush(stderr);
+ exit(-1);
+ }
+
+ int64_t old_index;
+ double old, new;
+
+ double** sums = (double**) malloc (numTimesteps*sizeof (double*));
+ double** sums_sq = (double**) malloc (numTimesteps*sizeof (double*));
+ double** inv = (double**) malloc (numTimesteps*sizeof (double*));
+
+ for (uint64_t i=0; i < numTimesteps; i++) {
+ sums[i] = (double*) malloc (numTimeseries*sizeof(double));
+ sums_sq[i] = (double*) malloc (numTimeseries*sizeof(double));
+ inv[i] = (double*) malloc (numTimeseries*sizeof(double));
+ }
+
+ // 2 DFE input streams: precalculations and data pairs
+ for (uint64_t i=0; i<numTimesteps; i++) {
+
+ old_index = i - (uint64_t)windowSize;
+
+ for (uint64_t j=0; j<numTimeseries; j++) {
+ if (old_index<0)
+ old = 0;
+ else
+ old = data [j][old_index];
+
+ new = data [j][i];
+
+ if (i==0) {
+ sums [i][j] = new;
+ sums_sq [i][j] = new*new;
+ }
+ else {
+ sums [i][j] = sums [i-1][j] + new - old;
+ sums_sq [i][j] = sums_sq [i-1][j] + new*new - old*old;
+ }
+
+ inv [i][j] = 1/sqrt((uint64_t)windowSize*sums_sq[i][j] - sums[i][j]*sums[i][j]);
+
+ //Precalculations REORDERED in DFE ORDER
+ precalculations [2*i*numTimeseries + 2*j] = sums[i][j];
+ precalculations [2*i*numTimeseries + 2*j + 1] = inv [i][j];
+
+ //Data pairs REORDERED in DFE ORDER
+ data_pairs[2*i*numTimeseries + 2*j] = new;
+ data_pairs[2*i*numTimeseries + 2*j + 1] = old;
+ }
+ }
+
+ for (uint64_t i=0; i<numTimesteps; i++) {
+ free (sums[i]);
+ free (sums_sq[i]);
+ free (inv[i]);
+ }
+
+ free (sums);
+ free (sums_sq);
+ free (inv);
+
+}
+
+void random_data (double** data, uint64_t numTimeseries, uint64_t sizeTimeseries) {
+
+ srand(0);
+
+ for (uint64_t i=0; i<numTimeseries; i++) {
+ for (uint64_t j=0; j<sizeTimeseries; j++) {
+ data[i][j] = ((double)rand()/(double)RAND_MAX);
+ }
+ }
+}
+
+
+int main () {
+
+ uint64_t numTimesteps = 10;
+ uint64_t numTimeseries = 200;
+ uint64_t windowSize = 9;
+
+ uint64_t sizeTimeseries = 100; // number of elements in the timeseries
+
+ double start_time, reorder_time, dataflow_time, total_time;
+
+
+ /*===================== INITIALIZING =====================*/
+
+ double** data = (double**) malloc (numTimeseries*sizeof (double*));
+ for (uint64_t i=0; i < numTimeseries; i++)
+ data[i] = (double*) malloc (sizeTimeseries*sizeof(double));
+
+ printf("Generating data!\n");
+ random_data (data, numTimeseries, sizeTimeseries);
+
+ double* precalculations = (double*) malloc (2 * numTimeseries * numTimesteps * sizeof(double));
+ double* data_pairs = (double*) malloc (2 * numTimeseries * numTimesteps * sizeof(double));
+
+ // Correlations_data_flow outputs
+ double* correlations = (double*) malloc (correlation_numTopScores*numTimesteps*sizeof(double));
+ uint32_t* indices = (uint32_t*) malloc (2 * correlation_numTopScores*numTimesteps*sizeof(double));
+
+
+ /*==================== SPLIT CONTROL FLOW ====================*/
+
+ printf("SPLITING CONTROL FLOW.\n");
+ start_time = gettime();
+ correlation_control_flow (data, sizeTimeseries, numTimeseries, numTimesteps, windowSize, precalculations, data_pairs);
+ reorder_time = gettime() - start_time;
+
+ /*==================== SPLIT DATA FLOW ====================*/
+
+ printf("CORRELATE!\n");
+ start_time = gettime();
+ correlation_data_flow (numTimesteps, numTimeseries, windowSize, precalculations, data_pairs, correlations, indices);
+ dataflow_time = gettime() - start_time;
+
+ total_time = reorder_time + dataflow_time;
+
+ printf("TimeSeries: %" PRIu64 ", TimeSteps: %" PRIu64 "\n", numTimeseries, numTimesteps);
+ printf("Data reordering time: %.5lfs\n", reorder_time);
+ printf("Dataflow execution time: %.5lfs\n", dataflow_time);
+ printf("Total execution time: %.5lfs\n", total_time);
+
+ //Deallocating memory
+ free (data_pairs);
+ free (precalculations);
+ free (correlations);
+ free (indices);
+
+ for (uint64_t i=0; i<numTimeseries; i++)
+ free (data[i]);
+ free (data);
+ return 0;
+}
diff --git a/exercise1-correlation/split/dataflow.c b/exercise1-correlation/split/dataflow.c
new file mode 100644
index 0000000..59ffeee
--- /dev/null
+++ b/exercise1-correlation/split/dataflow.c
@@ -0,0 +1,91 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <math.h>
+#include <time.h>
+#include <sys/time.h>
+#include <string.h>
+
+#define correlation_maxNumTimeseries (6000)
+#define correlation_numTopScores (10)
+
+//Calculate top correlations
+void topCorrelations (double* correlations, uint32_t* indices, uint64_t numCorrelations, double* correlations_top, uint32_t* indices_top, int numTopScores) {
+
+ for (uint64_t step=0; step<numCorrelations-1; ++step) {
+ for (uint64_t i=0; i<numCorrelations-step-1; ++i) {
+ if (correlations[i]<correlations[i+1]) {
+ double temp_corr = correlations[i];
+ uint32_t temp_in1 = indices[2*i];
+ uint32_t temp_in2 = indices[2*i+1];
+
+ correlations[i] = correlations[i+1];
+ indices[2*i] = indices[2*(i+1)];
+ indices[2*i+1] = indices[2*(i+1)+1];
+
+ correlations[i+1] = temp_corr;
+ indices[2*(i+1)] = temp_in1;
+ indices[2*(i+1)+1] = temp_in2;
+
+ }
+ }
+ }
+
+ memcpy(correlations_top, correlations, numTopScores*sizeof(double));
+ memcpy(indices_top, indices, 2*numTopScores*sizeof(uint32_t));
+}
+
+void correlation_data_flow (uint64_t numTimesteps, uint64_t numTimeseries, uint64_t windowSize, double* precalculations, double* data_pairs, double* correlations, uint32_t* indices) {
+
+ uint64_t numCorrelations = (numTimeseries*(numTimeseries-1))/2;
+ uint64_t index_correlation;
+
+ double* sums_xy = (double*) calloc (numCorrelations, sizeof(double));
+ double* correlations_step = (double*) calloc (numCorrelations, sizeof(double)); // all correlations in current step
+ uint32_t* indices_step = (uint32_t*) calloc (2*numCorrelations, sizeof(uint32_t)); // corresponding indices for correlations_step
+ double* correlations_top = (double*) malloc (correlation_numTopScores*sizeof(double)); // top correlations in current step
+ uint32_t* indices_top = (uint32_t*) malloc (2*correlation_numTopScores*sizeof(uint32_t)); // corresponding indices for correlations_top
+
+ for (uint64_t s=0; s<numTimesteps; s++) {
+
+ index_correlation = 0;
+
+ for (uint64_t i=0; i<numTimeseries; i++) {
+
+ double old_x = data_pairs[2*s*numTimeseries + 2*i + 1];
+ double new_x = data_pairs[2*s*numTimeseries + 2*i];
+
+ for (uint64_t j=i+1; j<numTimeseries; j++) {
+
+ double old_y = data_pairs[2*s*numTimeseries + 2*j + 1];
+ double new_y = data_pairs[2*s*numTimeseries + 2*j];
+
+
+ sums_xy[index_correlation] += new_x*new_y - old_x*old_y;
+
+ correlations_step[index_correlation] = (windowSize*sums_xy[index_correlation]-
+ precalculations[2*s*numTimeseries + 2*i]*precalculations[2*s*numTimeseries + 2*j])*
+ precalculations[2*s*numTimeseries + 2*i+1]*precalculations[2*s*numTimeseries + 2*j+1];
+
+ indices_step[2*index_correlation] = j;
+ indices_step[2*index_correlation+1] = i;
+
+ index_correlation++;
+
+ }
+ }
+ topCorrelations (correlations_step, indices_step, numCorrelations, correlations_top, indices_top, correlation_numTopScores);
+
+ memcpy(&correlations[s*correlation_numTopScores], correlations_top, correlation_numTopScores*sizeof(double));
+ memcpy(&indices[2*s*correlation_numTopScores], indices_top, 2*correlation_numTopScores*sizeof(uint32_t));
+
+ }
+
+ free(sums_xy);
+ free(correlations_step);
+ free(indices_step);
+ free(correlations_top);
+ free(indices_top);
+
+}
+
diff --git a/exercise1-correlation/timeseries-times.dat b/exercise1-correlation/timeseries-times.dat
new file mode 100644
index 0000000..5d78821
--- /dev/null
+++ b/exercise1-correlation/timeseries-times.dat
@@ -0,0 +1,9 @@
+timeseries,timesteps,time(s)
+100,10,1.92703
+100,50,8.84720
+100,100,17.10251
+50,10,0.16128
+200,10,27.67527
+
+Using DFE (Simulated):
+200,10,10.846