Chips & Circuits

Introduction

Chips (or more precisely: integrated circuits) are found in your PC, MacBook, Android Phone and microwave oven where they perform a diversity of functions, ranging from timekeeping and motor control to arithmetic and logic. Basically a small plate of silicon, chips are usually designed logically and subsequentially transformed to a list of connectable gates. This list, commonly known as a net list is finally transformed into a 2-dimensional design on a silicon base.

This last step however, the physical real-world process of connecting 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 and good wiring between them is of vital essence to the performance of the IC as a whole.

To make things easier, we will consider the wiring problem only. The gates have already been arranged, and all it takes is finding very short wiring patterns.

Example

Netlist #1

Een suboptimale wiring voor netlist #1.

De optimale wiring voor netlist #1.

This is an integrated circuit built up from five gates that need to be connected. The connections ("nets") follow the grid in a Manhattan style. Luckily enough, the wires don't cross. Sometimes they have to and when they do, the base consists of multiple grid layers. Besides going North, South, East and West, nets can also go up and down, and the distance between levels is identical to the distance between grid points.

Assignment

This is an arrangement of gates on a base, and all it takes is to wire the appropriate gates together. There are three net lists for different functionalities. Each net list needs to be implemented.

Print #1

Print #2

30 gates

50 gates

100 gates

Advanced

For each of the three arrangements, try to determine the relation between the number of wires and the required number of layers.

Links

No links.

Terug

Back to the Heuristics main page.