Project 3 - Distributed Artificial Life

See the assignment turn-in page (last modified on 9 February 2004) for instructions on turning in your assignment.

A germ program is stored, conceptually, as as a contiguous sequence of bytes in soup storage. The size of a germ can vary, depending on whether or not the germ contains bud and spawn instructions.

• The error register contains the number of errors committed by the associated germ. This register cannot be read or written by the associated germ.

• The program counter P contains the index of the next instruction to be executed. The value in the P is an index relative to the first byte in the germ; it is not an index into a soup's storage.

  The value stored in P must always at least zero and less than the size of the associated germ. If the value in P is less than zero or at least the size of the associated germ, the germ has effectively ceased execution and should be removed from the soup.

• A sixteen-word stack. An instruction that tries to push a word into a full stack (a stack containing sixteen words) is in error and should be aborted. An instruction that tries to pop a word from an empty stack is in error and should be aborted.

  Byte values pushed on the stack are sign-extended to the full sixteen bits; byte values popped from the stack lose their most-significant byte.

A context is not part of a germ's allocated soup storage, and should not be included when determining the size of a germ.

• an instance of the instruction under discussion is found at a valid relative offset ro in a germ; that is, assume the program counter contains the value ro.

• an instruction that causes a stack overflow or underflow is aborted and execution proceedes to the instruction following the aborted instruction.

The number following the instruction name is the op-code value for the instruction; all instructions are byte values.

zero (0)

A no-op.

one (1)

A no-op.

add (2)

Pop the top two elements of the stack, add them, and push the result back on the stack.

sub (3)

Pop the top two elements of the stack, subtract the second element from the first, and push the result back on the stack.

mul (4)

Pop the top two elements of the stack, multiply them, and push the result back on the stack.

div (5)

Pop the top two elements of the stack, divide the first by second, and push the quotient back on the stack.

rem (6)

Pop the top two elements of the stack, divide the first by second, and push the remainder back on the stack.

ifzero (7)

Pop the top of the stack; if the value popped is zero, do nothing. If the value popped is non-zero, add one to the program counter (this skips the instruction following the ifzero instruction).

findb (8)

Pop the top of the stack to get n; if n is not positive, the findb instruction is in error and should be aborted.

The n statements following the findb should be either zero or one statements. If there are not n statements following the findb, or if any of the n statements following the findb are neither zero nor one, then the findb is in error and should be aborted.

Search backwards from the findb instructions for the first sequence of n statements matching the n statements following the findb. If such a instruction sequence is found, then push the relative offset of the first instruction (that is, the instruction with the lowest relative offset) matched. If no such instruction sequence is found, then push zero.

In either case, execution continues n statements beyond the findb instruction; that is, the program counter advances to skip the n zero and one instructions following the findb instruction.

findf (9)

The same behavior as findb, but the search goes forward from from the instruction P + n; that is, the search begins at the first instruction after the findf.

bud (10)

Pop the top of the stack to get n, which should be in the range 10 to 512 (inclusive). If n is not in the range [10..512], the bud is in error and should be aborted.

Increase the size of the germ by n; the extra space is added to the end of the germ. The extra space is called the bud germ. The initial contents of the storage-array elements occupied by the bud germ is undefined. If the bud germ could be allocated, push a non-zero value on the stack; if the bud germ could not be allocated, push a zero on the stack.

Attempting to allocate a bud germ when one has already been allocated but not spawned is an error and should abort the bud instruction with no storage allocated.

spawn (11)

Turn the bud germ into a separate germ to begin independent execution. If there is no bud germ, the spawnis in error and should be aborted.

push.b (12)

Push the contents of the byte immediately following the push.b instruction on the stack. Execution continues with the instruction at P + 1; that is, at the instruction two bytes after the push.b.

push.w (13)

Take the contents of the two byte immediately following the push.w instruction as a word value and push it on the stack. Execution continues with the instruction at P + 2; that is, at the instruction three bytes after the push.w.

pop.bi (14)

Pop the stack and take the value as the relative offset ro'; pop the stack again and store the low byte of the value in the byte referenced by ro'.

pop.wi (15)

Pop the stack and take the value as the relative offset ro'; pop the stack again and store the value in the byte pair starting at ro'.

push.bi (16)

Pop the stack and take the value as the relative offset ro'; push the value in the byte referenced by ro'.

push.wi (17)

Pop the stack and take the value as the relative offset ro'; push the value in the byte-pair starting at ro'.

pop.pc (18)

Pop the contents of the stack into the program counter.

push.pc (19)

Push the contents of the program counter on the stack.

A soup's free space is the number of unoccupied bytes in its storage array as a percent of the total number of bytes in the storage array. Free space is an integer between 0 (every byte in the storage array is being used by a germ) and 100 (the storage array contains no gerns). An underpopulated soup is a soup with free space of at least 75; an overpopulated soup is a soup with free space of at most 25.

When a soup, call it O, becomes overpopulated, but before free space becomes 0, it should stop executing germs and query the other soups in its network looking for soups willing to accept some of O's germs. When it finds a willing soup (call it W), O should ship one of its germs to W.

Off-loading germs from O should continue until either O's free space rises above 25 or every other soup on the list has refused to accept a germ. In the latter case, O should just go back to executing germs until the grim reaper comes along to do its work.

When a soup, call it U, becomes underpopulated, it should stop executing germs (if any) and query the other soups in its network looking for soups wanting to off-load some of their germs. A soup willing to off-load will send a germ to U.

Off-loading germs to U should continue until either U's free space drops below 75 or every other soup on the list has indicated it doesn't have germs so spare. In the latter case, U should just go back to executing germs; if U doesn't have any germs, it should suspend for a brief period of time and they poll for off-loaders again. Note that, while suspended, U could get a request to accept a germ from an overpopulated soup.