\$dotat: life/liphe.txt,v 1.3 2008/09/04 16:58:46 fanf2 Exp \$ Some notes on parallel hashlife. ================================ * High level plan The general idea is to use lock-free implementation techniques for the highly-contended data structures, which means that when a thread cannot make progress it does not block but instead saves the current computation's state and finds something else to work on. This means we need no more than one thread per CPU. We do use traditional locks when passing work between CPUs. * Nodes A node can be in one of three states, as follows: - no result (node->result == NULL) - working on result (node->result == &dummy) - result available (node->result has some other value) The dummy node is a global variable whose contents don't matter. The "working" state encompasses both active and suspended work. These are distinguished by a thread's posession of the node or its suspension record (active) or an un-owned suspension record on a work queue (fullly suspended). * Suspensions The calculation for a node proceeds in two stages, either of which can block waiting for a sub-node's calculation to complete. Blocking is implemented by saving the state in a suspension record and going to work on something else. struct susp1 { // pointer to the suspended node node *sq; // the nine sub-squares whose results we are waiting for node *nw, *nn, *ne, *ww, *cc, *ee, *sw, *ss, *se; }; struct susp2 { // pointer to the suspended node node *sq; // the four sub-squares whose results we are waiting for node *nw, *ne, *sw, *se; }; The suspension records need to be traced by the garbage collector. * Getting a result In normal hashlife, the result function either returns a node's cached result immediately, or calculates the result and caches it before returning. That is, its result is always useful to the caller. In this code there is a third possibility that the node is being worked on, in which case the result function returns NULL. This causes the parent node's calculation to be suspended. In order to take possession of a node atomically, we use the compare-and-swap instruction to replace a NULL result with a dummy result. If this fails (because of a collision with another thread) we try again. The following is a small adjustment from normal hashlife; there's a more radical version further below. node *calc(node *sq, int lev) { do { if(sq->result == &dummy) return(NULL); if(sq->result != NULL) return(sq->result); } while(!CAS(sq->result, NULL, &dummy)); // now we own the node and can work on it // XXX see below int down = lev - 1; // calculate stage one node *nw1 = find_nw(sq), *nn1 = find_nn(sq), *ne1 = find_ne(sq), *ww1 = find_ww(sq), *cc1 = find_cc(sq), *ee1 = find_ee(sq), *sw1 = find_sw(sq), *ss1 = find_ss(sq), *se1 = find_se(sq), *nw2 = calc(nw, down), *nn2 = calc(nn, down), *ne2 = calc(ne, down), *ww2 = calc(ww, down), *cc2 = calc(cc, down), *ee2 = calc(ee, down), *sw2 = calc(sw, down), *ss2 = calc(ss, down), *se2 = calc(se, down); // if any of the above collided with another thread, // suspend this node and return NULL if(!nw2 || !nn2 || !ne2 || !ww2 || !cc2 || !ee2 || !sw2 || !ss2 || !se2) return suspend1(sq, lev, nw1, nn1, ne1, ww1, cc1, ee1, sw1, ss1, se1); // calculate stage two node *nw3 = find(nw, nn, ww, cc), *nw4 = calc(nw3, down), *ne3 = find(nn, ne, cc, ee), *ne4 = calc(ne3, down); *sw3 = find(ww, cc, sw, ss), *sw4 = calc(sw3, down); *se3 = find(cc, ee, ss, se), *se4 = calc(se3, down); // if any of the above collided with another thread, // suspend this node and return NULL if(!nw4 || !ne4 || !sw4 || !se4) return suspend2(sq, lev, nw3, ne3, sw3, se3); // set the final result and release ownership of the node return sq->result = find(nw4, ne4, sw4, se4); } I'm not sure if we need a write barrier at the end of the function. * Parallelism The above doesn't have any way of introducing parallelism because the calc() function is too eager. To split the calculation across CPUs we should make it lazier, by suspending before doing any recursion. This should probably be done only for high-level nodes, so that we don't waste too much time on the overhead of suspending and resuming calculations. struct susp0 { // just a pointer to the suspended node node *back; }; // in the above sketch of calc() at the XXX comment // high_lev is some external or class member variable if(lev > high_lev) return suspend0(sq, lev); * Suspending and resuming computations This part is crucial to the efficiency of distributing the work across CPUs as well as the efficiency of each individual thread. There's lots of scope for experimentation here. The most important thing is to avoid contention on the suspension record queues. Thus there should be per-thread queues for efficiency (no locking or memory barriers to access them) plus global queues to distribute work (which are locked with conventional mutexes). If we get the balance right then the global queues should not be too highly-contended, so a simple locking strategy should be OK. This means we can avoid complicated lock-free data structures in the scheduler, which is likely to be complicated enough for other reasons. Perhaps a starting point would be: - allocate queues in blocks of (some number of) suspension records - each level has three queues of susp0, susp1, and susp2 records - when suspendN() fills a block, it puts the block on a global list of blocks and obtains an empty block for future suspensions (or some other heuristic for moving work to other threads) - when resuming we scan a block at a time; if any of the records in the block get re-suspended the new record is put in the current allocation block (different from the block we are resuming) // for N in 0,1,2 struct suspN_block { suspN_block *next; suspN rec[SUSPN_BLOCK_SIZE]; }; When we call the block_resumeN() functions, the current thread owns the block, therefore it owns all the suspension records, therefore it owns all the suspended nodes. Therefore no locking is required. void block_resume0(susp0_block *blk, int lev) { for(int i = 0; i < SUSP0_BLOCK_SIZE; i++) resume0(blk->rec[i].sq, lev); free_block0(blk); } void block_resume1(susp1_block *blk, int lev) { for(int i = 0; i < SUSP1_BLOCK_SIZE; i++) resume1(blk->rec[i].sq, lev, blk->rec[i].nw, blk->rec[i].nn, blk->rec[i].ne, blk->rec[i].ww, blk->rec[i].cc, blk->rec[i].ee, blk->rec[i].sw, blk->rec[i].ss, blk->rec[i].se); free_block1(blk); } void block_resume2(susp1_block *blk, int lev) { for(int i = 0; i < SUSP2_BLOCK_SIZE; i++) resume2(blk->rec[i].sq, lev, blk->rec[i].nw, blk->rec[i].ne, blk->rec[i].sw, blk->rec[i].se); free_block2(blk); } The resume functions are basically suffixes of the calc() function above. It probably makes sense to split it up as follows. The function boundaries are the suspend/resume points. It's a bit like event-driven networking code. node *calc(node *sq, int lev) { do { if(sq->result == &dummy) return(NULL); if(sq->result != NULL) return(sq->result); } while(!CAS(sq->result, NULL, &dummy)); // now we own the node and can work on it // should we be eager or lazy? if(lev > high_lev) return suspend0(sq, lev); else return resume0(sq, lev); } node *resume0(node *sq, int lev) { return resume1(sq, lev, find_nw(sq), find_nn(sq), find_ne(sq), find_ww(sq), find_cc(sq), find_ee(sq), find_sw(sq), find_ss(sq), find_se(sq)); } node *resume1(node *sq, int lev, node *nw1, node *nn1, node *ne1, node *ww1, node *cc1, node *ee1, node *sw1, node *ss1, node *se1) { int down = lev - 1; // calculate stage one node *nw2 = calc(nw1, down), *nn2 = calc(nn1, down), *ne2 = calc(ne1, down), *ww2 = calc(ww1, down), *cc2 = calc(cc1, down), *ee2 = calc(ee1, down), *sw2 = calc(sw1, down), *sn2 = calc(sn1, down), *se2 = calc(se1, down); // if any of the above collided with another thread, // suspend this node and return NULL if(!nw2 || !nn2 || !ne2 || !ww2 || !cc2 || !ee2 || !sw2 || !ss2 || !se2) return suspend1(sq, lev, nw1, nn1, ne1, ww1, cc1, ee1, sw1, ss1, se1); else return resume2(sq, lev, find(nw2, nn2, ww2, cc2), find(nn2, ne2, cc2, ee2) find(ww2, cc2, sw2, ss2), find(cc2, ee2, ss2, se2)); } node *resume2(node *sq, int lev, node *nw1, node *ne1, node *sw1, node *se1) { int down = lev - 1; // calculate stage two node *nw2 = calc(nw1, down), *ne2 = calc(ne1, down), *sw2 = calc(sw1, down), *se2 = calc(se1, down); // if any of the above collided with another thread, // suspend this node and return NULL if(!nw2 || !ne2 || !sw2 || !se2) return suspend2(sq, lev, nw1, ne1, sw1, se1); // set the final result and release ownership of the node return sq->result = find(nw2, ne2, sw2, se2); } Note that after scanning a block, we may have newly suspended computations at the current level and at the level below, plus lower levels if we are low enough to be eager. This means here can be partially-filled blocks at multiple levels, which would not normally be shifted out to the global queues. This can lead to starvation of other threads if some of the partially filled blocks are high level, but the current thread has lots of work to do at low levels, so never fills the high level blocks. This implies we should be able to shift partial blocks onto the global work queues. There's a more general question: what order should we work on the blocks to minimize the chance of re-examining a suspension record too soon? * Hash consing The main hash table will be subject to seriously heavy contention. Perhaps we could use techniques like.. http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-639.html http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf -- eof --