1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <iostream>
#include <string>
#include <vector>
#include <omp.h>
#include <math.h>
#include <cstring>
#include <cstdlib>
#include "psearch.h"
#include "utilityfunctions.h"
#include "pBinarySearch.h"
#include "Zone.h"
using namespace std;
int pBinarySearch(char *sortedData,int ndata, char *keyword, char (*addresses)[ADDRESS_LEN], int maxCount)
{
return pBinarySearchSub(sortedData,ndata,keyword,addresses,maxCount,0);
}
int pBinarySearchSub(char *sortedData,int ndata, char *keyword, char (*addresses)[ADDRESS_LEN], int maxCount, int current_count)
{
if(current_count < maxCount)
{
vector <char*> keys;
vector <Zone*> zones;
get_keys(sortedData,keys,ndata * ENTRY_LENGTH);
const int chunk = (int)ceil((double)keys.size() / NT1);
/*in parallel each processor determines if the keyword being searched is in it's zone.
if it is, it adds this zone to zones vector.*/
#pragma omp parallel num_threads(NT1)
{
int low = omp_get_thread_num() * chunk;
//if last thread, high is last key, if not it's key at end of chunk
int high = (omp_get_thread_num() + 1 ) * chunk < keys.size() ?
(omp_get_thread_num() + 1 ) * chunk - 1 : keys.size() - 1;
//if only 1 element and it corresponds to key
if(high == low && (memcmp(keys[low],keyword,KEYWORD_LEN) == 0))
{
#pragma omp critical
{
//add it to addresses and increment current_count
if(current_count < maxCount)
{
/*we retest here because another thread might have modified current_count
since the thread passed the first if (line 22).
ie: say current_count = 6 and maxCount = 7. Thread 1 gets to line 22 and evaluates
6 < 7 to true and gets into this zone. Then say thread 2 arrives just after it, then
it also evals 6 < 7 to true. Now if both these threads find a solution, they add it to addresses
and in the end we are with current_count at 8.
*/
memcpy(addresses[current_count],keys[low] + KEYWORD_LEN,ADDRESS_LEN);
current_count++;
}
}
}
else
if(high < low)
{/* high < low happens only when the chunk size is such that the last thread is inactive.
for example, if we have 10 keys and 6 processors, ceil(10/6) = 2, hence the 5 first
processors will be used leaving last one idle. in this case, proc 6 (with id 5) has
low = 10 and high = 9.
Here we don't want to do anything*/}
else
if((memcmp(keyword,keys[low],KEYWORD_LEN) >= 0) && (memcmp(keyword,keys[high],KEYWORD_LEN) <= 0))
{//check if keyword is in the processors zone
//add it to zones vector
Zone* z = new Zone(low,high);
#pragma omp critical
zones.push_back(z);
}
}//end omp parallel
/*after this region, either each proc checked one element and added the address if necessary
to the addresses array
OR
it checked if the element was in it's zone and put that zone in the zones vector*/
//make recursive calls to the function on each zone found earlier.
if(!zones.empty())
for(unsigned int i = 0; i < zones.size() ; ++i)
{
int zone_l = zones[i]->getLow();
char* subSortedData = (char*)malloc(sizeof(char)*zones[i]->getSize()*ENTRY_LENGTH);
//copy into subsorteddata, the da ta contained between low and high
//ie from sortedData + zone_l * ENTRY_LENGTH to sortedData + zone_h
memcpy(subSortedData,sortedData + zone_l * ENTRY_LENGTH,zones[i]->getSize()*ENTRY_LENGTH);
current_count = pBinarySearchSub(subSortedData,zones[i]->getSize(),keyword,addresses,maxCount, current_count);
}
}
return current_count;
} |
