# 22C:122/55:132 Notes, Lecture 41, Spring 2001

Douglas W. Jones
University of Iowa Department of Computer Science

1. All mention of O(log N) has been incorrect

Up to this point, we have ignored geometric constraints on the construction of computer systems. If we pay attention to gemometry, constraining our systems to be built in a 3-dimensional physical universe instead of the unconstrained universe of the logician, we face a problem!

We can't fabricate 3-dimensional chips. Our silicon technology is inherently 2-dimensional. We can stack chips to a very shallow depth to make thin 3-dimensional structures, but thermal considerations limit this.

If you think of large-scale systems, where each system consists of motherboard with daughterboards and so on, the geometry is 3-dimensional on a local scale, but on a larger scale, a 2-dimensional constraint emerges again. Consider trying to fill a room with computers. If you pack them in 3-dimensions, the ones near the middle will overheat. You must stack them in a single wall, with cooling air flowing in from one side and out the other side.

On a huge scale, you can imagine building a sphere of computers around a star. The inner surface would be lined with solar cells, the outer surface with thermal radiators. The thickness of the shell would be limited by the thermal properties of the system, and again, the astronomically large supercomputer is a 2-dimensional structure.

Therefore, on a large scale, all computer systems are ultimately constrained to O(sqrt(N)) communications delays, unless we can build faster-than-light data communications systems.

2. Geometry is a big problem

We assumed that we could clock all the registers in a system simultaneously. In fact, this is difficult! The simple clock distribution schemes send clock pulses out that ripple away from the origin at speeds ranging from 1/3 the speed of light to 1/10 the speed of light -- not the speed of light! Practical signal speeds are from about 1 inch per nanosecond to 4 inches per nanosecond.

Why not the speed of light? Because signals are slowed by the transmission line characteristics of the conductor they travel down. Free low-energy photons in a vacuum travel at the speed of light. An electric signal on an infinitely long straight conductor with all other conductors infinitely far away will also travel at the speed of light. Nearby conductors slow electrical signals, matter slows light.

Specifically, signals in metal traces on the surface of an integrated circuit travel at about 1/3 the speed of light, and signals in silicon traces inside the body of the circuit travel much slower. If we run half the signals on the surface in one direction and half the signals inside the body in a perpendicular direction, we would be tempted to design long narrow circuits so that the edge to edge speeds would be matched in the two directions. This would be awkward, so we typically arrange signals to alternate from surface to body of chip.

At 1 GHz, the net result is that each clock cycle on a 1 inch is delayed almost half a cycle by the time it reaches the opposite edge from the transmitter. There is a geometric trick that can minimize this problem, a clock distribution tree:

```                 -o-   -o-
|     |
o--o--o
|  |  |
-o- | -o-
In ----------o
-o- | -o-
|  |  |
o--o--o
|     |
-o-   -o-
```
Many modern chips use this geometry to minimize the difference in path length to various parts of the chip.