Created
April 15, 2013 22:24
-
-
Save anonymous/5391777 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* Compile with: g++ -o hist -O3 hist.cpp -fopenmp -Wall */ | |
#include <algorithm> | |
#include <vector> | |
#include <iostream> | |
#include <assert.h> | |
#include "omp.h" | |
#define SIZE_TEST_VECTOR 400000000 | |
#define NBLOCKS 8 | |
#define NBUCKETS 10 | |
typedef unsigned int uint; | |
bool computeBlockHistograms(std::vector<uint>& array, uint numBlocks, uint numBuckets, uint blockSize) { | |
std::vector<uint> blockHistogramsPar1(numBlocks * numBuckets, 0); | |
std::vector<uint> blockHistogramsPar2(numBlocks * numBuckets, 0); | |
std::vector<uint> blockHistogramsSer(numBlocks * numBuckets, 0); | |
assert(array.size() == numBlocks * blockSize); | |
// Perform computation serially | |
for(uint idx = 0; idx < array.size(); idx++){ | |
uint blockNum = idx / blockSize; | |
for(uint divisorIdx = 1; divisorIdx <= numBuckets; divisorIdx++){ | |
if(array[idx] % divisorIdx == 0) | |
blockHistogramsSer[blockNum * numBuckets + (divisorIdx - 1)]++; | |
} | |
} | |
// Perform computation in parallel -- works | |
#pragma omp parallel shared(blockHistogramsPar1) | |
{ | |
#pragma omp for schedule(static) | |
for(uint blockNum = 0; blockNum < numBlocks; blockNum++){ | |
for(uint blockSubIdx = 0; blockSubIdx < blockSize; blockSubIdx++){ | |
uint idx = blockNum * blockSize + blockSubIdx; | |
for(uint divisorIdx = 1; divisorIdx <= numBuckets; divisorIdx++){ | |
if(array[idx] % divisorIdx == 0) | |
blockHistogramsPar1[blockNum * numBuckets + (divisorIdx - 1)]++; | |
} | |
} | |
} | |
} | |
// Peform computation in parallel -- doesn't work with large thread count | |
#pragma omp parallel shared(blockHistogramsPar2) | |
{ | |
#pragma omp for schedule(static, blockSize) | |
for(uint idx = 0; idx < array.size(); idx++){ | |
uint blockNum = idx / blockSize; | |
for(uint divisorIdx = 1; divisorIdx <= numBuckets; divisorIdx++){ | |
if(array[idx] % divisorIdx == 0) | |
blockHistogramsPar2[blockNum * numBuckets + (divisorIdx - 1)]++; | |
} | |
} | |
} | |
for(uint i = 0; i < blockHistogramsSer.size(); i++){ | |
if(blockHistogramsSer[i] != blockHistogramsPar1[i]){ | |
std::cout << 1 << ": " << i << ":: " << blockHistogramsSer[i] << " != " << blockHistogramsPar1[i] << std::endl; | |
return false; | |
} | |
if(blockHistogramsSer[i] != blockHistogramsPar2[i]){ | |
std::cout << 2 << ": " << i << ":: " << blockHistogramsSer[i] << " != " << blockHistogramsPar2[i] << std::endl; | |
return false; | |
} | |
} | |
return true; | |
} | |
void initializeRandomly(std::vector<uint>& array) { | |
srand(0); | |
for (uint i = 0; i < array.size(); i++) | |
array[i] = rand(); | |
} | |
int main(void) | |
{ | |
std::vector<uint> array(SIZE_TEST_VECTOR, 0); | |
initializeRandomly(array); | |
if (computeBlockHistograms(array, NBLOCKS, NBUCKETS, array.size() / NBLOCKS)) | |
std::cout << "Success!" << std::endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment