PrIM -- first commit

4 files changed, 182 insertions, 0 deletions

diff --git a/BS/baselines/cpu/Makefile b/BS/baselines/cpu/Makefile
new file mode 100644
index 0000000..e907fc8
--- /dev/null
+++ b/BS/baselines/cpu/Makefile
@@ -0,0 +1,4 @@
+all:
+	gcc bs_omp.c -o bs_omp -fopenmp
+run:
+	./bs_omp 262144 16777216
diff --git a/BS/baselines/cpu/README b/BS/baselines/cpu/README
new file mode 100644
index 0000000..ce82830
--- /dev/null
+++ b/BS/baselines/cpu/README
@@ -0,0 +1,9 @@
+Binary Search (BS)
+
+Compilation instructions:
+
+    make
+
+Execution instructions
+
+    ./bs_omp 2048576 16777216
diff --git a/BS/baselines/cpu/bs_omp.c b/BS/baselines/cpu/bs_omp.c
new file mode 100644
index 0000000..3ad83ed
--- /dev/null
+++ b/BS/baselines/cpu/bs_omp.c
@@ -0,0 +1,110 @@
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <unistd.h>
+#include <getopt.h>
+#include <assert.h>
+#include <time.h>
+#include <stdint.h>
+#include "timer.h"
+
+#define DTYPE uint64_t
+/*
+* @brief creates a "test file" by filling a bufferwith values
+*/
+void create_test_file(DTYPE * input, uint64_t  nr_elements, DTYPE * querys, uint64_t n_querys) {
+
+  uint64_t max = UINT64_MAX;
+  uint64_t min = 0;
+
+  srand(time(NULL));
+
+  input[0] = 1;
+  for (uint64_t i = 1; i < nr_elements; i++) {
+        input[i] = input[i - 1] + (rand() % 10) + 1;
+  }
+
+  for(uint64_t i = 0; i < n_querys; i++)
+  {
+	querys[i] = input[rand() % (nr_elements - 2)];
+  }
+}
+
+/**
+* @brief compute output in the host
+*/
+uint64_t binarySearch(DTYPE * input, uint64_t input_size, DTYPE* querys, unsigned n_querys)
+{
+
+	uint64_t found = -1;
+	uint64_t q, r, l, m;
+	
+       #pragma omp parallel for private(q,r,l,m)
+     	for(q = 0; q < n_querys; q++)
+      	{
+		l = 0;
+		r = input_size;
+		while (l <= r) 
+		{
+	    		m = l + (r - l) / 2;
+
+	    		// Check if x is present at mid
+	     		if (input[m] == querys[q])
+			{	
+		    		found += m;
+				break;
+			}
+	    		// If x greater, ignore left half
+	    		if (input[m] < querys[q])
+			    	l = m + 1;
+
+	    		// If x is smaller, ignore right half
+			else
+		    		r = m - 1;
+		
+		}
+       	}
+
+      	return found;
+}
+
+  /**
+  * @brief Main of the Host Application.
+  */
+  int main(int argc, char **argv) {
+
+    Timer timer;
+    uint64_t input_size = atol(argv[1]);
+    uint64_t n_querys = atol(argv[2]);
+
+    printf("Vector size: %lu, num searches: %lu\n", input_size, n_querys);
+	
+    DTYPE * input = malloc((input_size) * sizeof(DTYPE));
+    DTYPE * querys = malloc((n_querys) * sizeof(DTYPE));
+
+    DTYPE result_host = -1;
+
+    // Create an input file with arbitrary data.
+    create_test_file(input, input_size, querys, n_querys);
+	
+    start(&timer, 0, 0);
+    result_host = binarySearch(input, input_size - 1, querys, n_querys);   
+    stop(&timer, 0);
+
+
+    int status = (result_host);
+    if (status) {
+        printf("[OK] Execution time: ");
+	print(&timer, 0, 1);
+	printf("ms.\n");
+    } else {
+        printf("[ERROR]\n");
+    }
+    free(input);
+
+
+    return status ? 0 : 1;
+}
+
diff --git a/BS/baselines/cpu/timer.h b/BS/baselines/cpu/timer.h
new file mode 100755
index 0000000..969ef97
--- /dev/null
+++ b/BS/baselines/cpu/timer.h
@@ -0,0 +1,59 @@
+/*

+ * Copyright (c) 2016 University of Cordoba and University of Illinois

+ * All rights reserved.

+ *

+ * Developed by:    IMPACT Research Group

+ *                  University of Cordoba and University of Illinois

+ *                  http://impact.crhc.illinois.edu/

+ *

+ * Permission is hereby granted, free of charge, to any person obtaining a copy

+ * of this software and associated documentation files (the "Software"), to deal

+ * with the Software without restriction, including without limitation the 

+ * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or

+ * sell copies of the Software, and to permit persons to whom the Software is

+ * furnished to do so, subject to the following conditions:

+ *

+ *      > Redistributions of source code must retain the above copyright notice,

+ *        this list of conditions and the following disclaimers.

+ *      > Redistributions in binary form must reproduce the above copyright

+ *        notice, this list of conditions and the following disclaimers in the

+ *        documentation and/or other materials provided with the distribution.

+ *      > Neither the names of IMPACT Research Group, University of Cordoba, 

+ *        University of Illinois nor the names of its contributors may be used 

+ *        to endorse or promote products derived from this Software without 

+ *        specific prior written permission.

+ *

+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 

+ * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH

+ * THE SOFTWARE.

+ *

+ */

+

+#include <sys/time.h>

+

+typedef struct Timer{

+

+    struct timeval startTime[4];

+    struct timeval stopTime[4];

+    double         time[4];

+

+}Timer;

+

+void start(Timer *timer, int i, int rep) {

+    if(rep == 0) {

+        timer->time[i] = 0.0;

+    }

+    gettimeofday(&timer->startTime[i], NULL);

+}

+

+void stop(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);

+}

+

+void print(Timer *timer, int i, int REP) { printf("%f\t", timer->time[i] / (1000 * REP)); }