Atbrox is a startup providing technology and services for Search and MapReduce/Hadoop, founded by alumni from Google, IBM, and research.
GPUs (Graphical Processing Units) like the NVIDIA Tesla are fascinating hardware, particularly regarding extreme parallelism (hundreds of cores) and memory bandwidth (tens of gigabytes/second). The main programming languages for GPUs are C-based OpenCL and NVIDIA's CUDA, along with wrappers in many languages; for the following example we use Andreas Klöckner's PyCUDA for Python.
Word Count with PyCUDA and MapReduce
One of the classic MapReduce examples is word frequency count (individual word frequencies), but let us start with an even simpler example — word count, i.e., how many words are there in a potentially big string?
In Python, the default approach would be:
wordcount = len(bigstring.split())Assuming that you didn't have split() or that split() was too slow, what would you do?
How to Calculate Word Count?
If you have the string mystring = "this is a string", you could iterate through it and count spaces:
sum([1 for c in mystring if c == ' '])(Notice the off-by-one error.) You might split it up and parallelize it somehow. However, if there are several spaces in a row, this algorithm fails — and it doesn't use the GPU horsepower.
The MapReduce Approach
Taking mystring = "this is a string", align the string almost with itself: one string containing all characters except the last (mystring[:-1], the prefix) and another containing all characters except the first (mystring[1:], the suffix):
this is a strin # prefix
his is a string # suffixCounting all occurrences where the character in the upper string (prefix) is whitespace and the corresponding character in the lower string (suffix) is non-whitespace gives the exact word count (fixing the off-by-one boundary by checking whether the first character is non-whitespace). This also handles multiple consecutive spaces cleanly, and expresses naturally in Python with map and reduce:
mystring = "this is a string"
prefix = mystring[:-1]
suffix = mystring[1:]
mapoutput = map(lambda x, y: (x == ' ') * (y != ' '), prefix, suffix)
reduceoutput = reduce(lambda x, y: x + y, mapoutput)
total = reduceoutput + (mystring[0] != ' ') # fix off-by-one errorMapReduce with PyCUDA
PyCUDA supports using Python and NumPy with CUDA, and includes pycuda.reduction.ReductionKernel to run MapReduce-style operations directly on GPU arrays. Below is the complete code using the complete works of Shakespeare replicated 100× to 493,820,800 bytes (~0.5 GB) on an NVIDIA Tesla C1060 GPU:
import pycuda.autoinit
import numpy
from pycuda import gpuarray, reduction
import time
def createCudaWordCountKernel():
initvalue = "0"
mapper = "(a[i] == 32)*(b[i] != 32)" # 32 is ASCII code for whitespace
reducer = "a+b"
cudafunctionarguments = "char* a, char* b"
wordcountkernel = reduction.ReductionKernel(
numpy.float32,
neutral=initvalue,
reduce_expr=reducer,
map_expr=mapper,
arguments=cudafunctionarguments,
)
return wordcountkernel
def createBigDataset(filename):
print "reading data"
dataset = file(filename).read()
print "creating a big dataset"
words = " ".join(dataset.split()) # normalize \t and \n to spaces
chars = [ord(x) for x in words]
bigdataset = []
for k in range(100):
bigdataset += chars
print "dataset size = ", len(bigdataset)
print "creating numpy array of dataset"
bignumpyarray = numpy.array(bigdataset, dtype=numpy.uint8)
return bignumpyarray
def wordCount(wordcountkernel, bignumpyarray):
print "uploading array to gpu"
gpudataset = gpuarray.to_gpu(bignumpyarray)
datasetsize = len(bignumpyarray)
start = time.time()
wordcount = wordcountkernel(gpudataset[:-1], gpudataset[1:]).get()
stop = time.time()
seconds = stop - start
estimatepersecond = (datasetsize / seconds) / (1024 * 1024 * 1024)
print "word count took ", seconds * 1000, " milliseconds"
print "estimated throughput ", estimatepersecond, " Gigabytes/s"
return wordcount
if __name__ == "__main__":
bignumpyarray = createBigDataset("dataset.txt")
wordcountkernel = createCudaWordCountKernel()
wordcount = wordCount(wordcountkernel, bignumpyarray)Results
python wordcount_pycuda.py
reading data
creating a big dataset, about 1/2 GB of Shakespeare text
dataset size = 493820800
creating numpy array of dataset
uploading array to gpu
word count took 38.4578704834 milliseconds
estimated throughput 11.9587084015 Gigabytes/s (95.67 Gigabit/s)
word count = 89988104.0Improvement Opportunities
There are plenty of improvement opportunities — in particular replacing bignumpyarray = numpy.array(bigdataset, dtype=numpy.uint8), which took almost all of the host-side setup time (as reader KoppeKTop noted in the original comments, numpy.fromfile(filename, dtype=numpy.int8) is dramatically faster).
It is also interesting to note that this single-GPU reduction doesn't need combiners like distributed Hadoop MapReduce (where a combiner acts like an afterburner on the mapper output for associative and commutative operations).
Amund Tveit — Atbrox Co-founder