[ fromfile: threads.xml id: parallellife ]

Revisiting Conway's Game of Life from Section 9.10, we will parallelize the computation using a QtConcurrent mapReduce() algorithm. For this to work, we must first break up the puzzle into smaller pieces. We define each piece as a LifeSlice, shown in Example 17.23.

[ . . . . ]
struct LifeSlice {
    LifeSlice() {};
    LifeSlice(QRect r, QImage i) : rect(r), image(i) {}
    QRect rect;
    QImage image;
};
[ . . . . ]

A LifeSlice consists of a QImage with a QRect indicating which piece it came from. This is the argument and return type of the mapping function (Example 17.24). Do not use QPixmap in LifeSlice.^[103]

[ . . . . ]
struct LifeFunctor : public std::unary_function<LifeSlice, LifeSlice> {
    LifeSlice operator() (LifeSlice slice);
};

LifeSlice LifeFunctor::operator()(LifeSlice slice) {    
    QRect rect = slice.rect;
    QImage image = slice.image;
    QImage next = QImage(rect.size(), QImage::Format_Mono);
    next.fill(DEAD);
    int h = rect.height();  int w = rect.width();

    for (int c=0; c<w; ++c) {
        for (int r=0; r<h; ++r) {
            int x = c+rect.x();
            int y = r+rect.y();
            bool isAlive = (image.pixelIndex(x, y) == ALIVE);
            int nc = neighborCount(image, x, y);
            if (!isAlive && nc == 3)
                 next.setPixel(c, r, ALIVE);
            if (!isAlive) continue;
            if (nc == 2 || nc == 3)
                next.setPixel(c,r, ALIVE);
        }
    }
    slice.image = next;
    return slice;
}

Deriving a unary function object, LifeFunctor from the Standard Library template unary_function gives our functor additional type "traits", used by generic algorithms to get the argument and return type of the functor. This functor defines an operator() that takes a LifeSlice argument and returns a LifeSlice value.

The return type of the mapping function must be the (second) argument type of the reduce function Example 17.25.

[ . . . . ]
void stitchReduce(QImage& next, const LifeSlice &slice) {
    if (next.isNull()) 
        next = QImage(boardSize, QImage::Format_Mono);
    QPainter painter(&next);
    painter.drawImage(slice.rect.topLeft(), slice.image);   
}

The reduce function must somehow take together the partial results produced by each of the worker threads and reassemble them back into a coherent QImage. As in the collage example, the maping function uses the high-level QPainter API to draw one image onto another, avoiding the need for nested loops of individual pixel assignments.

The main loop Example 17.26 must break up the problem into smaller pieces, send them to a QtConcurrent blockingMappedReduced(), and send the results to the LifeWidget.

[ . . . . ]

void LifeMainWindow::calculate() {
    int w = boardSize.width();
    // This might not be optimal but it seems to work well...    
    int segments = QThreadPool::globalInstance()->maxThreadCount() * 2; 
    int ws = w/segments;                    
    LifeFunctor functor;                    
    while (m_running) {
        qApp->processEvents();              
        m_numGenerations++;
        QList<LifeSlice> slices;            
        for (int c=0; c<segments; ++c) {
            int tlx = c*ws;
            QRect rect(tlx, 0, ws, boardSize.height());
            LifeSlice slice(rect, m_current);    
            slices << slice;                
        }
        m_current = QtConcurrent::blockingMappedReduced(slices, functor,
                    stitchReduce, QtConcurrent::UnorderedReduce );  
        m_lifeWidget->setImage(m_current);
    }
}

The qApp->processEvents() is required in this loop for the main event loop to receive and process other GUI events. If you comment that line out and try running the application, you notice that as soon as the calculations start, there is no way to stop or quit.

This program gets 10 frames per second (fps) with four threads, compared to 4fps with one thread, on a 1024x768 board. Not quite a factor of 4, but with a larger life board, you might observe better improvements. Keep in mind, there is a synchronization point that cannot be avoided after each generation is computed.