The very first instruction in most heads-based organisms is "h-alloc", which will allocate space for an offspring to be placed into. If you look at the file source/cpu/hardware_util.cc, you will see that this instruction is associated with the method cHardwareCPU::Inst_MaxAlloc(). What this means is that the organism will automatically allocate as much space as it possibly can, without having to first calculate its needs. When the organism is finished copying itself and divides off its child, any excess allocated memory will automatically be discarded. It appears in the code as follows:
void cHardwareCPU::Inst_MaxAlloc() // Allocate maximum additional memory
{
const int cur_size = GetMemory().GetSize();
const int alloc_size = Min((int) (cConfig::GetChildSizeRange() * cur_size),
MAX_CREATURE_SIZE - cur_size);
if( Allocate_Main(alloc_size) ) Register(REG_AX) = cur_size;
}
This method will determine the maximum amount of extra space that an organism is allowed to allocate, and then run the Allocate_Main() function passing in that amount. Allocate_Main is a very long method which is mostly just check to make sure that everything going on is legal, and then initializes the new memory that was allocated as per the genesis file: random, default instruction, or leave as it was in the previous organism that used it (for "necrophelia").
Most of the initial self-analysis done on avida organisms is with the search instruction or one of its variants. In the heads based instruction set, we call this "h-search" and associate it with the method cHardwareCPU::Inst_HeadSearch().
The search type instructions read in the template (series of nops) that follows it, determine the complement template, and find that complement elsewhere in the genome. It then sets the registers BX and CX to be the distance to the found template and the size of that template respectively. Finally, we place the flow control head at the end of the template found in order to reference it later on. Obviously this last step only occurs in the heads-based search.
The first search instruction executed by a heads organism is typically used to locate the end of its genome. The search will place the flow-head at the end of the genome, which the organism will use to move the write head to this point as well. This is done with the "mov-head" instruction, implemented as follows:
void cHardwareCPU::Inst_MoveHead()
{
const int head_used = FindModifiedHead(HEAD_IP);
GetHead(head_used).Set(GetHead(HEAD_FLOW));
if (head_used == HEAD_IP) advance_ip = false;
}
If the mov-head instruction is followed by a nop-C it will
move the write head to the flow head, and ideally be ready to start copying
itself into the newly allocated space for the offspring.
The copy loop is the heart of any organism. It consists of a setup, a copy segment to copy one or more instructions, a test segment to determine if the loop has finished, and a "jump" type instruction to move back to copy the next line.
In a hand written organism, the setup is an h-search command with no template to direct its behavior. The default when this instruction does not have a template is to just drop the flow-head at the very next instruction, which is what it is used for here -- it places the flow head at the beginning of the portion of code that will actually be looped through copying each line.
The copy segment is typically just a single h-copy instruction, which will read in an instruction from the location of the read-head, and write it out to the location of the write-head. It will then advance both heads to the next positions in the genomes. Take a look at the source code for the method cHardwareCPU::Inst_HeadCopy(), which you will find in your handout for the file hardware_cpu.cc.
The first thing that happens in this method is the variables read_head, write_head, and cpu_stats are setup as references to the appropriate objects in the hardware and organism (that is, any modifications to these references change the actual objects, not just a local copy of them). This is so that we have easy to use variables locally for those objects that we are working with. The read_head and write_head are then adjusted to make sure they are in a legal position on the genome (if, for example, the last instruction changed the organism's size, the heads might no longer be pointing to memory that still exists).
Next, the instruction at the read head is recorded in the variable read_inst, and we test to see if this should be mutated to some other value. If a mutation does occur, we change the read_inst variable to a random value, increment the mutation count, and mark flags at the instruction position of the write head to denote the mutation. After we determine what instruction was read (be it a correct reading or not), we call the ReadHead() method, which is simply used to keep track of the most recent template copied. This template is used to help detect the end of the organism, which we shall discuss in a moment.
Finally, we collect the statistics that another copy command was executed in this organism, finish the write by placing this instruction at the position of the write head (and setting its flag as being a copied instruction) and then advancing both heads to their next positions.
After an organism executes one of these copies it has to test to see if it is done copying itself. The heads based organisms will typically do this with the aid of the if-label instruction, which tests to see if the most recent label copied is the complement of the one that follows it. If so, it will execute the next instruction (often a divide), otherwise it will skip that next instruction and execute a mov-head that will jump the instruction pointer back to the flow head that was placed at the beginning of the copy loop. It will continue this copy-test-jump cycle until all the lines have been copied.
A common adaptation is "unrolling the loop".
In the hand-written version discussed above, each instruction must have
three instructions executed to copy it: h-copy, if-label,
and mov-head. But what if a second
h-copy command were inserted after the first? Now the program
would be one line longer, so it would have more to copy, but each time
through the loop would now copy two instructions while executing four --
that means that on average only two instructions need be executed to copy
one. A *huge* savings. The main drawback to the organism is that its
length will need to be a multiple of two, or else the test to see if it is
finished won't occur at the proper time. This loop unrolling becomes less
and less beneficial each time the organism does it, so it won't go completely
out of control, but I do think it is a bit too easy in the current version of
the code.
When an organism finishes copying itself, it needs to divide off its child using a divide command. In the heads based instruction set, this is the h-divide command which calls the cHardwareCPU::Inst_HeadDivide() method, found in your hardware_cpu.cc handout.
This method will use the read head to determine the starting location of the offspring, and the write head to determine its end. This is logical because these are the locations that the heads should be in right after the copy loop has finished. Everything after the write head is cut off and discarded as "extra_lines". This information is passed into the Divide_Main method which does the bulk of the work for divide (and is called by all of the various divide instructions in all of the sets).
The cHardwareCPU::Divide_Main() method is therefore what we are most interested in. It begins by calculating the size of that child that would result from the divide point and the extra_line count that were passed into it, and runs Divide_CheckViable() to make sure that all of these values are legal (that is that both parent and child are reasonable sizes for organisms, and reasonable sizes in relationship to each other -- for definitions of reasonable as found in the genesis file). If any of them are not legal, the method returns false.
From this point on, we know the divide is legal, so we just need to process it. We create a variable called child_genome, which we use to construct the child genome. We use a reference to a cGenome object inside of the organism so that this child genome is attached to its parent organism and will be easily accessible from other places where it will be needed later. We're not going to be doing all of the work on it right in this method. We initialize the child genome to the section of the parents genome that was created for it. We then run Resize() on the parent genome to get rid of all of this extra space (both child and extra lines).
The Divide_DoMutations() method will test and (if needed) process any divide mutations that may occur. There are many of them, so this method is quite long. It is followed by Divide_TestFitnessMeasures(), which will run the offspring through a test CPU for special options that may be set in the genesis file (such as mutation reversions). Obviously this is very processor intensive since it would occur with every birth, so tests are only performed if required. Both of these methods are left to the reader to step through themselves.
Next, the method Divide_SetupChild() is executed on the organism to transform the child genome we have constructed into a full-fledged child organism (adding in references to the environment, its interface to the population, its parent's phenotypic characteristics, etc.) Basically, it gets the child organism ready to be inserted into the population, but does not do so yet. This method is located in source/main/organism.cc if you wish to look at it for yourself.
If we are using extra costs associated with the first time instructions are used, those costs a reset now that a divide has occurred, and must be paid for again on the next divide cycle.
After a divide, we mark that we no longer have a mal (Memory ALlocation) active. If the parent is reset (i.e., we have two offspring, not a parent and child) we need to make sure not to advance the IP of the parent. The reset parent has its IP placed at the beginning of its genome, and we want to leave it there to execute the very first instruction.
Finally, we tell the organism to activate the divide and do something with the child. Give the child to the population (or the test CPU as the case may be) to be dealt with, and reset the parent if we're splitting into two offspring.
We will examine the population in a future class, where I'll go into more
detail as to how the child organism is placed. By default, the placing of
an organism in the population can cause the removal of an organism that is
already there, and this is the only way that an organism can be killed off.
In the description of this life-cycle, one issue that I have not discussed is where these organisms would perform their computations. In truth, there isn't a fixed time other than it must be before the divide occurs, since merit is recalculated on a divide. In practice it will typically be place right before the copy loop, but there are plenty of exceptions.
Ideally, in the longer term, an organism's life will be composed of much
more than just replication and computations -- they will have to interact with
each other and have more interactions with the environment. In a
multi-threaded model, organisms will be doing many activities at the same
time.