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
|
//sortedDATA est un char* contenant des entrées les unes à la suite des autres
//une entrée = mot clé + addresse (collés)
//on cherche keyword parmi les clés et on renvoies les addresses
//correspondantes à chaque fois qu'on trouve keyword
//on cherche au plus maxCount occurence de la clé.
int pBinarySearch(char *sortedData,int ndata, char *keyword, char (*addresses)[ADDRESS_LEN], int maxCount)
{
int current_count = 0;
vector <char*> keys;
vector <Zone*> zones;
//on extrait les clés qu'on met dans le vector keys
//zones contiendra des zones ou le mot clé existe
get_keys(sortedData,keys,ndata * ENTRY_LENGTH);
const int chunk = (int)ceil((double)keys.size() / NT1);
while(current_count<=maxCount)
{
#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 : keys.size() - 1;
//if only 1 element and it corresponds to key we save
//the address and increment counter
if(high == low && memcmp(keys[low],keyword,KEYWORD_LEN))
{
#pragma omp critical
{
memcpy(addresses[current_count],keys[low] + 16,ADDRESS_LEN);
current_count++;
}
}
else
//if keyword is in processors zone, we create a zone object that contains high
//and low limits of the zone to be explored nex
if(memcmp(keyword,keys[low],KEYWORD_LEN) >= 0 && memcmp(keyword,keys[high],KEYWORD_LEN) <= 0)
{
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*/
if(!zones.empty())
for(unsigned int i = 0; i < zones.size() ; ++i)
{//for every zone in zones, we recursively call the function...
int zone_l = zones[i]->getLow();
char* subSortedData = (char*)malloc(sizeof(char)*zones[i]->getSize()*ENTRY_LENGTH);
//copy into subsorteddata, the data contained between low and high
//ie from sortedData + zone_l to sortedData + zone_h
memcpy(subSortedData,sortedData + zone_l,zones[i]->getSize()*ENTRY_LENGTH);
current_count += pBinarySearch(subSortedData,zones[i]->getSize(),keyword,addresses,maxCount - current_count);
}
}
return current_count;
} |
Recherche dichotomique en parallèle
Répondre avec citation
Envoyé par JolyLoic
...
A méditer: La solution la plus simple est toujours la moins compliquée
Partager