Introduction
Chips (or more precisely: integrated circuits) are found in your PC, MacBook, Android Phone and microwave oven where they perform a diversity of frunctions, ranging from timekeeping and motor control to arithmetical calculations. Basically a small plate of silicon supporting a considerable number of connected logical gates, chips are usually designed by a logical design, subsequentially transformed to a list of connectable logical gates (commonly known as a net list) and in the final step transformed to 2-dimension design on a silicon base.
The final step however, the physical real-world process connecting of the gates, is highly volatile. Good arrangements on the base lead to short connections, leading to faster circuits, whereas poor arrangements lead to slower circuits. It leads to no doubt that a good arrangement of logical gates is of vital essence to the value of the IC as a whole.
Example
Assignment
1) Design a chip from netlist#1.
| Netlist: A->B,D;C->E;D->B;E->C,D | thumb Game #2 | 
|
|---|
2) Design a chip from netlist#2.
3) Design a chip from netlist#3.
Advanced
The suspicion is, that the minimal number of layers required for a chip to be designed from a netlist depends on the connectivity of the netlist. Generate 10 random netlists with the exact same number of gates and connections as in netlist#3 and run them through your algorithm. Carefully document the number of layers needed and the optimality of the found solution. Next, double the number of connections for each netlist and run them through your algorithm again. Document carefully again, and compare the results with the previous experiment.
Links
Nothing here for now.
Go Back
Go back to the Heuristics Main Page.