Introductory Gunk Examples for HLSIM

by David DeRoure

This document is provided to help newcomers to HLSIM get started with Gunk programming, and is intended to supplement the HLSIM manual. It contains hints, utilities, example Gunk programs and a summary of the HLSIM programming techniques used in the examples.

Please contact me on dder@martigny.ai.mit.edu if you have any questions or comments. New versions of any of these examples, additional examples, new library code or more hints are all very welcome.

Running the examples

The file naming convention is as follows:

First release of Gunk program foo is in foo1.scm. This needs to be subjected to the Gunk compilation process (cps, cbf).
The definitions used by the Gunk program (if any) are in foo1d.scm. This needs to be compiled normally (cf).
The simulation setup is in foo1s.scm. This is usually interpreted.

The simulation can be compiled and run "manually" by evaluating the appropriate expressions in the simulation setup file (e.g. from emacs). Loading the file into Scheme (with HLSIM installed) results in a small (1000 processor) simulation being run automatically, which is useful for testing.

Gunk hints

The communications model seems tough at first. Play with Comm to get a feel for how often collisions occur, and you can experiment with various time delays (the communication delay in the simulator is 100 units). Many of these examples flash the processor when a collision is detected, which is a useful diagnostic technique. When you understand the nature of the model, you can either fight it or accept it, but my advice is not to get hungup on comms!
Gunk programs can take a long time to "converge" (and cannot easily tell when they've done so). Try Commcheck to see just how long it really takes for every processor to find all its neighbors, a behavior which is characteristic of many Gunk programs.
How do you know when your Gunk program is working exactly as intended? Sometimes it helps to try it on a (more) regular grid, where the behavior is (more) predictable. See Utilities.
The mean neighborhood density can be critical to the behavior of many algorithms. In 2D the density for n processors and neighborhood radius r is just under n pi r^2. Try your algorithms with different densities, perhaps using a simulation with variable density (see Utilities).
Move procedures into a separate definitions file for modularity and speed (but remember they are then treated as primitives by the simulator for timing purposes). For example, the code to maintain data structures can be compiled separately, with the actual structures stored in the per-processor state. This approach is used in some of the examples, such as TD. In the extreme case, the Gunk program just contains the comms handling code and the per-processor state, but you must question whether this is a useful simulation.
Random process IDs are useful (and will be supported by Gunk chips too). They provide a way of resolving conflicts, giving priority to the lower or higher. See the Max example for an easy way of establishing local groups of processors.
Potential gradients are useful - they provide a sense of direction (and are a popular basis for line drawing). Using a "hopcount" from the source is an effective way of modeling these, as shown by Potential.
Some of these examples use a single event loop for both receiving and transmitting (e.g. Max), others use two loops which are run as parallel threads (e.g. Neighbors), one has multiple threads and an event re-distributor (Track). Multiple threads can provide a better organization of code. Don't be afraid of asynchrony or non-determinism: Gunk's like that, and non-deterministic programs can still have deterministic results.
Think "in paradigm". Apply conservation principles; e.g. hopcounts count down from a source (c.f. decreasing ion concentration) not up (cf. a tape measure). Think equilibria, think feedback. Simulate failure, use redundancy.
Don't forget there can be more than 2 dimensions!

Utilities library

These examples also use club5d.scm or util1d.scm, which are libraries of support routines. The file club5d.scm is part of the club example in the HLSIM documentation (with useful procedures such as color-me and make-sim/1), and util1d.scm is simply an extension of it (the examples that use club5d.scm will also work with util1d.scm). One advantage of util1d.scm is that it contains alternative make-sim routines, so that you can test your Gunk code with different processor distributions:

make-sim/j distributes the processors on a fixed grid, each offset by a random component within its cell (the optional j argument is the "jiggly" factor which controls the random component and defaults to 0.5). This distribution can be useful during development: it is often difficult to predict the behavior of Gunk programs, and it is therefore difficult to know when your Gunk program is working as intended, but running it with this distribution has more predictable behavior.
make-sim/f distributes the processors with a neighborhood density that varies across the space, by applying a function f to distort the distribution (f defaults to sqrt). This is useful for exploring the behavior of your Gunk program across a spectrum of mean neighborhood density, which appears to be critical for many algorithms. Functions based on expt are particularly useful for varying the distribution; e.g. (lambda (x) (expt x 0.6)). The "jiggly" example illustrated uses sqrt.
make-sim/c constructs a simulation which satisfies a constraint. The constraint is specified by providing a predicate which is applied to the number of neighbors for each processor; the default predicate returns true if the processor has more than one neighbor. The simplistic algorithm involves repeated passes over the simulation, randomly relocating processors which fail the predicate, until every processor satisfies it. This is a general solution but may fail to terminate quickly or at all (better solutions are invited!) In the "clumpy" example illustrated, each processor has more than two neighbors.

util1d.scm also contains utilities to identify processors close to a given point or in a given region.

Example Gunk Programs

Comm

comm1.scm is provided to give a "feel" for the communications model: processors broadcast after random delays, flashing cyan, and when a message is detected a processor flashes green (message received) or red (collision detected). It is also useful for experimenting with different delays, synchronization, back-off strategies etc. It uses the usual definitions in club5d.scm. There is an example simulation setup in comm1s.scm. See also comm2.scm and comm2s.scm for a simple variation which demonstrates propagation of a color from a "source" processor (this is illustrated here).

Illustration shows 10k processors, radius 0.012, simulation in progress.

Max

max1.scm is a simple example where each processor is assigned a random id and random color, which are then broadcast repeatedly; when a processor hears from a higher id than its own, it assumes that id and color. It does not have its own definitions file but uses the usual definitions in club5d.scm. There is an example simulation setup in max1s.scm. This program runs for a long time and you will probably want to interrupt it. See synchro1.scm and synchro1s.scm for a (flashy) variation on this theme (illustrated here). Could Max form the basis for establishing a network of wires using the borders of the regions?

Illustration shows 10k processors, radius 0.012, simulation in progress.

Neighbors and Commcheck

neighbors1.scm is a simple example where each processor changes color to indicate the number of neighbors it detects. It does not have its own definitions file but uses the usual definitions in club5d.scm. There is an example simulation setup in neighbors1s.scm. This program runs for a long time and you will probably want to interrupt it.

commcheck1.scm is a test program for the simulator and is like Neighbors in reverse. Each processor starts with the complete list of its neighbors computed during simulation setup, then removes neighbors from the list when it receives messages from them; the length of the list of neighbors remaining to be "discovered" is represented by the color, so it is easy to see when all neighbors have been discovered (this takes a long time!) There is an example simulation setup in commcheck1s.scm.

Bnawki

bnawki1.scm is an extension of Neighbors. Each processor has a boolean state, indicated by its color, which changes according to the number of neighbors and their states. The current rules provide `peer pressure'. It uses its own definitions file bnawki1d.scm as well as the usual definitions in club5d.scm. There is an example simulation setup in bnawki1s.scm. An idea for Bnawki2: try fixing the state of some cells (e.g. with simulation.find-processors-in-region in util1d.scm) and see if you can establish rules which cause these to be accepted or rejected (cf. pathogens) by the evolving cells. (Yes, Bnawki is a bizarre name, but there's a reason...)

Illustration shows 10k processors, radius 0.02, isolated processors hidden.

TD

td1.scm is also an extension of Neighbors. Each processor has a state (0..6) indicated by its color, and it attempts to choose a state which is different than all its neighbors. It uses its own definitions file td1d.scm as well as the usual definitions in club5d.scm. There is an example simulation setup in td1s.scm. (TD stands for "time division", as this algorithm was originally implemented as the basis for an approach to communication in which each processor has a time slot, i.e. color).

Illustration shows 10k processors, radius 0.012, simulation in progress.

Potential

pot1.scm is a simple example of one processor establishing a potential gradient by broadcasting a message with a value which decreases as the message is propagated (note that counting down rather than up models conservation). The colored bands indicate processors which record similar potentials. This example does not have its own definition file but makes use of club5d.scm. There is an example simulation setup in pot1s.scm.

Illustration shows 10k processors, radius 0.02.

Multiple potentials

npot1.scm is an extension of potential to multiple potential sources, with the colors indicating the sum of the potentials at each processor. This example can easily be extended to sources of different types (cf. different ions) and is a useful basis for line construction experiments. It uses its own definitions file npot1d.scm, as well as definitions in util1d.scm. There is an example simulation setup in npot1s.scm.

Illustration shows 10k processors, radius 0.025, V=25.

Beacons

beacons1.scm introduces multiple messages sent from multiple sources over a period of time: several processors each issue a series of colored packets, which propagate to varying distances. The message format is more "commsy", separating payload from hopcount (or TTL). This example brings in timing issues and is useful for exploring the effects of changing neighborhood density. It uses definitions in beacons1d.scm in addition to the those in util1d.scm. There is an example simulation setup in beacons1s.scm.

Illustration shows 10k processors, radius 0.02, variable density.

Find

find1.scm has two message types: those traveling out from a source in search of the destinations and then, when they reach a destination, those traveling back along the path from the destination to the source. This example does not have its own definitions file but uses those in util1d.scm. There is an example simulation setup in find1s.scm.

Illustration shows 10k processors, radius 0.02, 2 destinations, simulation in progress.

Track

track1.scm is an extended version of Find and is based on the same algorithm. It does not have its own definitions file but uses those in util1d.scm. There is an example simulation setup in track1s.scm.

Illustration shows 3k processors, radius 0.05, 3 sources and destinations, simulation in progress.

This example demonstrates three things:

It is coded in receptor-producer style, in which receptors deal with incoming messages and these can cause state changes in the processor/cell, and meanwhile the producers (coded separately) emit broadcasts at a rate which depends on the state of the cell. In this way, broadcasts are decoupled from receives: the programmer no longer thinks of broadcasts occurring as the direct result of an action triggered by the arrival of a message.
It demonstrates the use of an event re-distributor to improve the modularity of code. Without this, there is only one point in the code which deals with receives, and this constrains the organization of code. The event re-distributor re-signals received messages to other events (in this case, the receptors) and these can be handled in various places (e.g. in different threads, or in multiple instances of the same thread).
It uses the HLSIM sensor features. An image (illustrated) is projected onto the simulation, containing red, green and blue regions and their intersections. On start-up, processors identify their RGB value and hence their role. In this example, processors can be red (dealing with `red' messages), and/or green and/or blue; each processor runs up to three threads according to its color.

Some HLSIM programming idioms used in the examples

Parallel loops

Some of the examples use parallel loops, i.e. loops executing on separate threads. By default these execute asynchronously. The loops can share state via top-level variables or a shared lexical environment.

(define (tx-loop) ...)
(define (rx-loop) ...)

(parallel (tx-loop) (rx-loop))

Transmit loop with bounded delays

This transmit loop guarantees to attempt the next broadcast within the time given to random, and the average interval between broadcasts is half this time.

(define (tx-loop)
  (wait (make-timeout-event (random 6000)))
  (broadcast ...)
  (tx-loop))

Transmit loop with unbounded delays

This transmit loop rolls dice. The average interval between broadcasts attempts is prescribed, but there is no maximum.

(define (tx-loop)
  (wait (make-timeout-event 500))
  (if (zero? (random 6)) (broadcast ...))
  (tx-loop))

Instead of wait, both techniques can also be used with select; e.g.

(define (tx-loop)
  (let ((timeout (make-timeout-event 500)))
    (select
      (timeout (if (zero? (random 6)) (broadcast ...)))))
  (tx-loop))

Receive loop

Receive loops can also be coded with wait or select, as illustrated by the two loops below. These loops also differ in how they are terminated: the first runs until running? is false, the second until an global-timeout event is signaled.

(define running? #T)

(define (rx-loop)
  (let ((message (wait primitive-message-event)))
    (event.clear! primitive-message-event)
    ...)
  (if running? (rx-loop)))

(define (rx-loop)
  (select
   (primitive-message-event
    => (lambda (message)
	 (event.clear! primitive-message-event)
	 ...))
   (global-timeout 'done)))

Synchronized loops

It is sometimes desirable to synchronize loops that are running as separate threads. This can be achieved using select in at least one of the loops and signaling events from another. Note that if one loop reassigns a variable that appears in the guards of the select construct of another, the new value will not be seen until select is next evaluated. The following code resets the transmit timer when any message is received - but note that, due to the interleaving that occurs between the threads, it does not prevent an immediate transmission.

(define reset-timer (make-event))

(define (tx-loop) 
  (let ((transmit-timer (make-timeout-event (random 1000))))
    (select
     (transmit-timer (broadcast ...)
		     (tx-loop))
     (reset-timer (event.clear! reset-timer)
		  (tx-loop))
     (global-timeout 'done))))

(define (rx-loop)
  (let ((message (wait primitive-message-event)))
    (event.clear! primitive-message-event)
    (event.signal! reset-timer #T)
    ...))

(parallel (tx-loop) (rx-loop))

Combined Event Loop

The event-driven transmit and receive loops can be combined into one event loop. This has the advantage that the state variables can be passed as arguments to the loop and shared throughout. It also reflects the single-threaded nature of the communications model. However, committing all possible events to one select statement does not aid modularity, nor does it facilitate the dynamic creation of additional threads with new sets of events.

(define (event-loop ...)
  (select
   (primitive-message-event
    => (lambda (message)
	 (event.clear! primitive-message-event)
	 ...
         (event-loop ...)))
   (transmit-event (broadcast ...)
		   (set! transmit-event (make-timeout-event (random 5000)))
		   (event-loop ...))
   (break 'done)))

This variation on the above event loop assists visualization of communications.

(define (event-loop color ...)
  (color-me color)
  (select
   (primitive-message-event
    => (lambda (message)
	 (event.clear! primitive-message-event)
	 (if (eq? message 'collision) 
	     (color-me "red")
	     (begin (color-me "green") 
		    ...))
	 (event-loop color ...)))
   (transmit-event (color-me "cyan")
		   (broadcast ...)
		   (set! transmit-event (make-timeout-event ...))
		   (event-loop color ...))
   (break (color-me color) 'done)))

The event re-distributor

Usually only one place in the program handles received events, and this is a constraint on organization. This can be overcome by re-distributing the events from that one location to the places they are handled, such as multiple select statements or multiple instances of a loop. NB The handlers should clear the events as their first action, but even then there is no guarantee that an event appearing in two select statements will not trigger both.

(define (rx-loop)
  (let ((message (wait primitive-message-event)))
    (event.clear! primitive-message-event)
    (event.signal! (lookup message table ...) message))
  (rx-loop))

The Dice, or Event Generator (unbounded)

This is a way of generating events to `clock' the program. There are many variations on this.

(define (clock-loop)
  (wait (make-timeout-event 300))
  (case (random 6)
    ((0) (event.signal! slow #T))
    ((1 2) (event.signal! medium #T))
    ((3 4 5) (event.signal! fast #T)))
  (clock-loop))

Receptor-Producer

This is a variation on the event loop, which attempts to broadcast all the time (using a clock as above) but is prevented from doing so by the output guards.

(define (loop ...)
  (select
   (receptor1 => (lambda (m)
		   (event.clear! receptor1)
		   (if ....  (loop ...))))
   (receptor2 => (lambda (m)
		   (event.clear! receptor2)
		   (if ....  (loop ...))))
   
   ((and ... slow-producer) (event.clear! slow-producer) (broadcast ...))
   ((and ... fast-producer) (event.clear! fast-producer) (broadcast ...)))
  (loop ...))

Timers

Timers are useful for comms programming. This timer mechanism permits any thread to reset any timer, triggering re-evaluation in the corresponding select statements. It is possible to build a timer abstraction from this.

(define never (make-event))
(define timer1-reset (make-event))
(define timer1 never)

(define (set-timer1! delay)
  (set! timer1 (if delay (make-timeout-event delay) never))
  (event.signal! timer1-reset #T))

(define (loop ...)
  (select
   (timer1 ... (set-timer1! ...)
	   (loop ...))
   (timer1-reset (event.clear! timer1-reset)
		 (loop ...)))

David DeRoure is an amorphous visiting researcher from University of Southampton (that's Southampton UK, not Southampton MA). Contact him on dder@martigny.ai.mit.edu. This page last updated September 25 1997.