Created
August 28, 2013 18:48
-
-
Save Dierk/6369753 to your computer and use it in GitHub Desktop.
Massively parallel consistent ant moves
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
| import groovy.transform.Immutable | |
| import groovyx.gpars.dataflow.KanbanFlow | |
| import groovyx.gpars.dataflow.KanbanLink | |
| import groovyx.gpars.dataflow.KanbanTray | |
| import groovyx.gpars.dataflow.ProcessingNode | |
| import static groovyx.gpars.dataflow.ProcessingNode.node | |
| /* | |
| For a general introduction see https://gist.github.com/Dierk/6365780. | |
| This system of ant moves is inspired by the excellent http://www.youtube.com/watch?v=dGVqrGmwOAw . | |
| It does not cover all details of an ant colony simulation but only the core ant moves. | |
| The rest (movement strategies, home, food, pheromons, evaporation, visuals) could be easily added | |
| by extending the KanbanFlow chain. | |
| This approach offers a solution where we neither need persistent datatypes nor software transactional memory (STM) | |
| and certainly no locking. It is all exclusively modelled as KanbanFlow nodes. | |
| Ants cannot look further than one cell in either direction and they cannot look into | |
| the past or future to decide upon movements. So just like with the Game of Life example, the parallel system | |
| works from individual cells that are connected to their direct neighbors. | |
| The tricky part is to provide a consistent world view to the outside in a massively parallel system. | |
| When ants move to a destination cell, they must appear in the destination cell and disappear from the origin. | |
| At no observable time must they appear in both cells or in no cell. | |
| Ants can also be blocked because there already is an ant in the destination cell. | |
| There can be conflicts when two ants are heading for the same destination cell. | |
| The combination of requirements above is usually seen as "the really hard stuff". | |
| It appears to call for transactional support to rollback contentions and the big weaponry of parallel programming. | |
| The solution below goes a different route. I has no shared "world" state (not even an immutable one) where | |
| contentions can possibly occur. | |
| It has a notion of "generations". Generations do not materialize as part of the calculation, though. | |
| Only the observing printer creates the world view of a generation on the fly for reporting. | |
| The idea of "transactions" is replaced with a strategy that roughly comparable to the | |
| "2-phase commit protocol" (2PC), spanning over two generations: | |
| - generation 1: every Ant knows where it is heading towards ("prepare" in 2PC) | |
| - generation 1: every cell can decide where to pull the next ant candidate from ("ready" in 2PC) | |
| - generation 2: when both have a rendezvous, the ant moves at once in this generation ("commit" in 2PC) | |
| (I hope you can see the relation to settlements of a deal or money transfer between accounts.) | |
| At no time is any cell operator changing any state - particularly not the state of neighboring cells! | |
| He can only set his own cell state for the next generation and indicate his pull preference. | |
| @author Dierk Koenig | |
| */ | |
| @Immutable class Ant {int headingX, headingY } // heading is in [-1,0,1] | |
| ProcessingNode makeCellNode() { | |
| def ProcessingNode thisNode = new ProcessingNode() | |
| thisNode.body = { | |
| publish, | |
| inSelf, outSelf, | |
| in1, out1, in2, out2, in3, out3, in4, out4, // in and out meaning depends on wiring sequence | |
| in6, out6, in7, out7, in8, out8, in9, out9 | |
| -> | |
| def my = inSelf.take() | |
| def result = [ // collecting result signal | |
| generation: my.generation + 1, // in this generation | |
| x:my.x, y:my.y, // this cell | |
| ant: my.ant, // contains this ant (may be null) | |
| sx:my.sx, // source x,y (relative) where the next ant will be pulled from. 0,0 == no pull | |
| sy:my.sy // this is used as the rendezvous syncpoint | |
| ] | |
| def all = [in1, out1, in2, out2, in3, out3, in4, out4, in6, out6, in7, out7, in8, out8, in9, out9] | |
| def ins = all.findAll{ it.link.consumerSpec == thisNode } | |
| def outs = all.findAll{ it.link.producerSpec == thisNode } | |
| def signals = ins*.take() | |
| assert signals*.generation.every { it == my.generation } // sanity check | |
| def iAmPointingTo = null | |
| if (my.ant != null){ | |
| iAmPointingTo = signals.find { it.x == wrap(my.x + my.ant.headingX) && it.y == wrap(my.y + my.ant.headingY) } | |
| } | |
| boolean destinationPulls = false | |
| if (iAmPointingTo != null){ | |
| destinationPulls = (my.x == wrap(iAmPointingTo.x + iAmPointingTo.sx) && my.y == wrap(iAmPointingTo.y + iAmPointingTo.sy)) | |
| } | |
| if (destinationPulls) { | |
| result.ant = null // if there was an ant before, it is now elsewhere | |
| } | |
| def cellsWithAntsPointingToMe = signals.findAll { it.ant && wrap(it.x + it.ant.headingX) == my.x && wrap(it.y + it.ant.headingY) == my.y } | |
| def myPullSource = signals.find { it.x == wrap(my.x + my.sx) && it.y == wrap(my.y + my.sy) } | |
| // rendezvous | |
| if (myPullSource != null && myPullSource in cellsWithAntsPointingToMe) { | |
| result.ant = myPullSource.ant // keep the "ant" heading | |
| result.sx = 0 // we will not pull ourselves the next turn but may be pulled | |
| result.sy = 0 | |
| } else { | |
| if (result.ant == null && cellsWithAntsPointingToMe) { // we are empty and a source is given, ready to pull | |
| result.sx = - cellsWithAntsPointingToMe.first().ant.headingX | |
| result.sy = - cellsWithAntsPointingToMe.first().ant.headingY | |
| } | |
| } | |
| def outSignal = result.asImmutable() | |
| publish << outSignal | |
| outs.each { it << outSignal } | |
| outSelf << outSignal | |
| } | |
| return thisNode | |
| } | |
| ProcessingNode makeObserver(KanbanLink funnel) { | |
| return node { signal -> | |
| funnel.downstream << new KanbanTray(link: funnel, product: signal.take()) | |
| } | |
| } | |
| ProcessingNode makePrinter() { | |
| return node { inMap, outMap, inSignal, outSignal -> | |
| def signal = inSignal.take() | |
| def genMap = inMap.take() | |
| def genNumber = signal.generation | |
| def signalsInGeneration = genMap[genNumber] | |
| signalsInGeneration << signal | |
| if ( signalsInGeneration.size() == size * size ) { | |
| genMap.remove genNumber | |
| def board = makeBoard() | |
| for (cell in signalsInGeneration) { | |
| board[cell.y][cell.x] = cell.ant ? '*' : ' ' | |
| } | |
| println "\ngeneration ${genNumber} :\n" + | |
| board.join("\n") + | |
| "\nfuture generations: " + | |
| genMap.collect{ gen, signals -> "${gen}:${signals.size()}" } | |
| } | |
| outMap << genMap | |
| ~outSignal // outSignal will be triggered from the outside | |
| } | |
| } | |
| int getSize() { 10 } | |
| List<List<Integer>> makeBoard() { (0..9).collect { [null] * 10 } } // endless torus world | |
| int wrap(int i) { (i + size) % size } // indexes wrap around in the torus world | |
| startBoard = makeBoard() | |
| [[1,0],[2,1],[0,2],[1,2],[2,2]].each { startBoard[it[0]][it[1]] = new Ant(0,1) } // glider | |
| void seed(KanbanLink link, int x, int y) { | |
| def tray = new KanbanTray(link: link, product: [x:x, y:y, generation: 0, ant: startBoard[x][y], sx: 0, sy:0]) | |
| link.downstream << tray | |
| } | |
| new KanbanFlow().with { | |
| cycleAllowed = true | |
| List<List<ProcessingNode>> cells = (0..<size).collect{ x -> (0..<size).collect { y -> makeCellNode() } } | |
| def field = [ | |
| [-1, -1], [ 0, -1], [ 1, -1], | |
| [-1, 0], [ 1, 0], | |
| [-1, 1], [ 0, 1], [ 1, 1] | |
| ] | |
| ProcessingNode printer = makePrinter() | |
| KanbanLink mapLink = link printer to printer | |
| mapLink.downstream << new KanbanTray(link:mapLink, product: [:].withDefault { [ ] } ) | |
| KanbanLink signalLink = link printer to printer | |
| def currentLink | |
| for (int x in 0..<size) { | |
| for (int y in 0..<size) { | |
| def center = cells[x][y] | |
| currentLink = link center to makeObserver(signalLink) | |
| seed currentLink, x, y | |
| currentLink = link center to center | |
| seed currentLink, x, y | |
| } | |
| } | |
| for (int x in 0..<size) { | |
| for (int y in 0..<size) { | |
| def center = cells[x][y] | |
| field.each { | |
| def senderX = wrap(x + it[0]) | |
| def senderY = wrap(y + it[1]) | |
| def neighborCell = cells[senderX][senderY] | |
| currentLink = link neighborCell to center | |
| seed currentLink, senderX, senderY | |
| } | |
| } | |
| } | |
| start() | |
| sleep 4000 | |
| stop() | |
| } |
BTW: the code above uses a growing thread pool. You can restrict it to a pool of fixed size 10 by changing
new KanbanFlow().with {
to
new KanbanFlow().with {
pooledGroup = new DefaultPGroup(new DefaultPool(true, 10))
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and example output for ants moving downwards.
Note how the second ant is limbing behind at every second generation because the destination cell is occupied.
That is on purpose.