[SL] Re: sugerscape

[Andrew Begel <abegel@alum.mit.edu> (by way of vanessa@media.mit.edu (VanessaColella))]

You've got the right idea. StarLogo is only pretending to be parallel.
The unit of parallelism is the "command". A command is any primitive that
doesn't return a value. In cases where a command might take too long
(i.e. fd, or any command that takes a list-to-run, i.e. repeat, if,
ifelse, etc...) we divide the time up more finely.

On every "round," we give each turtle a chance to run one command and as
many reporters as it needs. A reporter is a primitive that returns a
value (like numbers, math operations, count-turtles-here, etc...). If I
had a command like:

jump 3 + 4

each turtle would compute 3 + 4 = 7 and then run jump, each in one round.

If and Ifelse are special in that their predicate (a reporter) is
evaluated in the same round as the first command in the consequent
(whatever list got run). This lets you be able to run code while the
predicate is still valid. That's why your first if statement to kill the
turtles failed. Each turtle was running the whole if statement in one
round, thereby only letting one turtle see the predicate as true. The
second one split the operation into two rounds and worked. This is known
as split-phase computing. You can see that we used it in the life sample
project.

Some of this information is in the StarLogo documentation on our website.

Andy Begel



>I think I've got a simple case of the same difficulty mentioned in your
>'sugerscape' letter:
>
>I'd like to check a conclusion about just HOW parallel Starlogo is.
>
>I set up some turtles and, on the procedure GO I had them wandering around,
>sometimes bumping into each other. I wanted each crash to be fatal to both
>turtles. So, in the GO procedure, I wrote:
>
>A)   if count-turtles-here > 1 [ die ]
>
>But only one from each pair of 'crashing' turtles actually died.
>
>So I made a turtles-own variable 'crash', initially set to 0, and replaced
>the
>above with:
>
>B)   if count-turtles-here > 1 [setcrash 1]
>     if crash > 0 [die]
>
>Now 'crashing' turtles died in pairs!
>
>Apparently each turtle executes each 'line', one turtle at a time; thus in
>case
>A), above, the first turtle in a 'crash' saw that there were 2 turtles on
>that
>spot, and died - so that when the second turtle in the crash (executing
>the same
>line) checked 'count-turtles-here' there was only 1 - himself.
>
>In case B) no-one dies in the first line so both turtles set 'crash' to 1;
>then
>in the next line both die.
>
>This *seems* right, but I'd appreciate it if you'd verify (or contradict) my
>conclusion about the inner workings of StarLogo. Sorry if this seems too
>elementary, but I'm still trying to get the real implications of 'parallel'
>processing into my old brain.
>
>Thanks,
>Neal Carpenter
>
>
>Andrew Begel (by way of Vanessa Colella ) wrote:
>
>> >You wrote:
>> >> Thank's for the sugerscape gradient search algorithm. It works fine :-)
>> >> I have augmented it in the following way:
>> >>
>> >> [snip]
>> >>
>> >> But there is a curious bug, I can't solve:
>> >> According to the code above, turtles can only move to unoccupied patches.
>> >> This works fine for a few, but not for say 1000 turtles! So sometimes
>> >> turtles move to occupied patches. The more turtles there are, the higher
>> >> the probabiliy that this can happen.
>> >> What is also strange, is that sometimes :-) the turtles move to a patch
of
>> >> the with the same chemical concentration, as the one it is on. This
should
>> >> not occur, since the  "if valmax > chemical" should prevent that.
>> >>
>> >> Does anyone have a clue? (I'm using version 2.02 & T1)
>> >
>> >Hmm... It seems that you are discovering the delights of
>> >parallel programming!
>> >You should revise your lessons about critical sections and
>> >mutual exclusion.  ;-)
>> >
>> >When you do something like:
>> >    if test then action
>> >in a parallel mode, there is always the risk that another process
>> >changes the value returned by the test AFTER you actually did the
>> >test and BEFORE you execute the action.
>>
>> Actually, StarLogo guarantees that the predicate of an if or ifelse
>> statement will be true while the first command in the consequent or
>> alternative runs.
>>
>> ie. if count-turtles-here > 0 [fd 1 setc yellow] [bk 1 setc blue]
>>
>> The fd 1 and bk 1 execute while there are no turtles here, but the setc
>> yellow and setc blue might run after some other turtle has already moved
>> to the old spot (which invalidates the predicate).
>>
>> It's for this reason that the idiom:
>>
>> turtles-own [the-turtle]
>>
>> to go
>> if count-turtles-here > 0
>>    [setthe-turtle one-of-turtles-here
>>     do stuff with turtle
>>    ]
>> end
>>
>> exists. The reason is that you need to grab one of the turtle's who's in
>> order to ask it to do things later in the consequent clause of the if
>> statement. Otherwise after the first command, one-of-turtles-here might
>> report that there are no more turtles if they've all left the spot.
>>
>> Anyway, my guess for the problem with sugarscape is that each turtle is
>> checking to see which spot they should go to (and make sure that there is
>> no turtle already there), but there is no guarantee that two turtles
>> won't think the same destination is desirable. :) You have two turtles
>> near the top of a gradient, and they might both want to go to the top on
>> the same step. If you alter your code a bit:
>>
>> uphill-sugar dist
>> if valmax > chemical  ;; if the biggest value is not the value right here,
>> go there
>>   [seth dirmax
>>    fd distmax]
>> wait 1
>> end
>>
>> change it to:
>>
>> uphill-sugar dist
>> if valmax > chemical
>>   [seth dirmax
>>    if count-turtles-at dx dy = 0
>>      [jump distmax]
>>   ]
>> wait 1
>> end
>>
>> This way you might turn the right direction, but right before you move,
>> you check if another turtle has dropped into the spot before you could.
>> If so, you don't move. Since StarLogo guarantees the atomicity of the
>> count-turtles-at and the jump distmax, you should be ok.
>>
>> Note: I used jump instead of fd, because jump takes one time unit, while
>> fd <n> takes n time units.
>>
>> Andy
>>
>> Andrew Begel
>> Dept. of Computer Science
>> UC Berkeley
>
>
>
>


Andrew Begel
Dept. of Computer Science
UC Berkeley