README

About this project:
This project initially set out to be a logic optimizer for 7400 series logic but went under many scope reductions.
Unlike conventional digital logic minimization techiniques such as K-maps or the espresso algorithm, this does not
limit the result to one circuit topology such as sum of products or product of sums. Additionally, this project is 
designed for real logic gates you find on IC's where each gate has a fixed number of inputs. However, because of the 
relaxation of these constraints it is significantly slower. Solving even a four variable system can take many minutes.
Originally, it hoped to solve for a minimum number of IC's used instead of gates, and originally I thought the
algorithm I designed would do so by simply ajdusting the cost function. However I realized at a late stage in the
project that this was not the case and to avoid rewriting the project reduced the scope to just optimizing for the 
fewest number of gates. 

How it works:
1) Representation : A boolean function is represented by its truth table (incorrectly called minterm in the source),
    the operation that was used to create it, and the inputs to that operation. For example, the inputs are each
    functions where (for a 3 variable function) A is 11110000, B is 11001100 and C is 10101010. A and B would be
    represented by an AND gate with the inputs A and B as its inputs and the truth table 11000000. These truth tables
    are both used for fast equality checking and as keys for the hashtable (more on this later) as they are always
    unique.
2) The algorithm : The algorithm basically preforms djikstra's algorithm on a lazily generated graph. Each node is a
    function (see #1) and its neighbors generated by combining itself with all combinations of nodes in the closed set.
    The cost of the path to that node is sum of the costs of the unique inputs + 1. 
3) Storage: All nodes are stored in a hashtable. If a node is generated with the same truth table but higher cost than 
    an existing node, it is discarded. The closed set is also stored in a dynamic array (for fast generation of 
    combinations based on indices) and the open set is stored as a binary heap for (reasonably) fast remove_min and
    insert. 

Speed:
The optimizer will reach some solutions very quickly and some very slowly based on how many gates are needed to
construct it. Additionally, the more gates supplied the more combinations it will need to process and the longer it
will take. Since there are fastly more combinations for gates with more than 2 inputs, 3+ input gates slow it down a
lot.

Bottlenecks:
I'm reasonably sure the project is memory bandwidth bound. I analyzed it using gprof and most (~50%) of the time is
spent doing hashtable lookup (and yes, I mean the actual lookup, not hashing). This isn't really something I can thread
my way out of, which is why, while the project slams one CPU to max, I am not looking into threading it. Additionally,
gprof revealed that not much time is spent in binary heap operations, which is why I haven't switched from the simple
binary heap to a faster but more complex heap such as fibonacci heap. 

Dependencies:
-Octothorpe (included as git submodule, you'll want to clone with --recursive)