From 3de4b495fb176eba9a0eb517a4ce05903cb67acb Mon Sep 17 00:00:00 2001 From: Juan Gomez Luna Date: Wed, 16 Jun 2021 19:46:05 +0200 Subject: PrIM -- first commit --- BS/baselines/cpu/Makefile | 4 ++ BS/baselines/cpu/README | 9 ++++ BS/baselines/cpu/bs_omp.c | 110 ++++++++++++++++++++++++++++++++++++++++++++++ BS/baselines/cpu/timer.h | 59 +++++++++++++++++++++++++ 4 files changed, 182 insertions(+) create mode 100644 BS/baselines/cpu/Makefile create mode 100644 BS/baselines/cpu/README create mode 100644 BS/baselines/cpu/bs_omp.c create mode 100755 BS/baselines/cpu/timer.h (limited to 'BS/baselines/cpu') 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 +#include +#include +#include +#include +#include +#include +#include +#include +#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 + +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)); } -- cgit v1.2.3