# Word Count with MapReduce on a GPU — A Python Example

- Canonical URL: https://amund.blog/archive-atbrox-mapreduce-gpu-python/
- Author: Amund Tveit (https://amund.blog/about/)
- Published: 2010-08-20
- Tags: GPU, Python, MapReduce, PyCUDA
- Original Source: atbrox.com (http://atbrox.com/2010/08/20/word-count-with-mapreduce-on-a-gpu-a-python-example/)

---

*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](http://mathema.tician.de/software/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:

```python
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:

```python
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**):

```text
this is a strin # prefix
his is a string # suffix
```

Counting 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`:

```python
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 error
```

### MapReduce 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:

```python
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

```text
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.0
```

### Improvement 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*
