Assignment 2: It's Only Logical

As described in class, in this project you will write and run a perhaps GP to create a minimum-cost combinatorial logic circuit implementing a specified logic function that computes up to 16 different outputs from up to 16 input variables.

Input To Your Program

Although there are many ways to specify a logic function, perhaps the most universal is to simply list the truth table. Except when making a Karnaugh map, the truth table is generally listed in unsigned binary counting order for the input variables; assuming that order allows us to avoid having to specify the input values. Since few of the logic design problems given to your code will be of the maximum allowed complexity, it also is convenient to restrict the number of inputs (Y) and outputs (X) to user-specified values given on the first line of input. For example, to compute the AND and XOR functions from three inputs the specification would be:

3 2
0 0
0 1
0 1
0 0
0 1
0 0
0 0
1 1

Thus, there are three inputs Y2, Y1, Y0 and two outputs X0 and X1 such that X0 = (Y2 AND Y1 AND Y0) and X1 = (Y2 XOR Y1 XOR Y0). The order of the rows is treating {Y2,Y1,Y0} as a 3-bit number starting at zero and incrementing for each new line, with Y0 as the least significant bit. Optionally, you may also allow a value of 2 to be used to indicate a "don't care" entry in the truth table, but only handling of 0 and 1 is required.

But the above isn't all the input your program needs: you also need some guidelines as to what to consider a better implementation. What is your metric?

For example, it is rather trivial to translate the above input specification into a straightforward, not-intentionally-minimized, sum of products (SoP) implementation. Only 1 outputs appear in the SoP; thus, we would have something like:

X0 = ((Y2) AND (Y1) AND (Y0))

X1 = (((((NOT Y2) AND (NOT Y1) AND (Y0)) OR
        ((NOT Y2) AND (Y1) AND (NOT Y0))) OR
       ((Y2) AND (NOT Y1) AND (NOT Y0))) OR
      ((Y2) AND (Y1) AND (Y0)))

Before you go off grabbing a sheet of scrap paper to draw some circles around 1s in a Karnaugh map, let's recognize something rather stupid here: remember we started out knowing that:

X1 = ((Y2) XOR (Y1) XOR (Y0))

In fact, you will not get anything so elegant no matter how you circle the 1s -- XOR functions are notoriously inefficient to implement using the AND/OR logic of SoP forms. Then again, the costs associated with an XOR gate may be quite different from those for an AND or OR gate... so maybe the XOR solution is not really better? Confusing, eh? That's why you going to build a GP....

Thus, the rest of the input to your program is a "technology cost matrix" that allows it to optimize the implementation for different cost functions. For this project, each type of gate has three parameters: purchase cost, power consumption, and propagation delay. Purchase cost obviously is additive, but keep in mind that a subcircuit could be shared by the computations of multiple outputs -- i.e., ADFs without arguments are potentially very useful constructs. The same is roughly true for power consumption. Propogation delay is more complex to compute for a complete circuit; it requires walking the circuit tree to compute the maximum delay on all subbranches. The delay at a gate output is the sum of that gate's delay plus the maximum of the delays of any of its inputs.

The "technology cost matrix" will simply list three non-negative floating-point numbers, the purchase cost, power consumption, and propagation delay, for each part type. This will be listed as 3 numbers per line, suitable as scanf() input, in the fixed order of the following gate types:

NOT
AND
OR
XOR
NAND

NOT is strictly unary; all the other gates are strictly binary. Each performs the expected one-bit function.

Note that the Y variables and the constants 0 and 1 are viable components of any circuit, but have no costs.

On the command line for your program, you will be given a set of three floating-point weights to allow you to compute a combined metric. The combined metric is (first weight * purchase cost) + (second weight * power consumption) + (third weight * proagation delay). Note that the weights can be negative, which would mean that they can start with a - character. In any case, you can get their values from the argument strings using atof().

Output From Your Program

Your program should run for no longer than approximately 5 minutes of real time. You can use time(0) to check the time -- it returns the total number of second elapsed since the start of 1970. You should check the time at least once per generation or 100 new individuals, whichever is larger.

Your program's output to stdout should consist only of a sequence of C assignment statements written using a function notation to express the logic formulation. This should be the one best design found by your program. For the example above, you might output:

X0=AND(Y2, AND(Y0, Y1));
X1=XOR(XOR(Y0, Y2), Y1);

Implicitly, your program should not generate an output function unless it is fully correct -- even the most inefficient design that gives correct answers is better than the most efficient one that gets some values wrong.

It is highly desirable for your program to also output things like the combined metric, costs, etc. However, any such additional output must be sent to stderr -- not to stdout. This allows your program's output to be used much more directly.

Hints

As we have discussed, there are many ways to approach this GP problem. Here are two:

1. One approach would be to create a GP system that does exactly what one would expect....
2. Another approach is to create a GP system that really only does correctness-preserving transformations on an initial population of known correct (but probably quite inefficient) designs.