Memory interleaving

Interleaving is a technique for speeding up access to sequential main memory addresses (e.g. by the CPU as it executes a program), for memories which have a cycle time which is significantly longer than their access time. (The classic example is core memory, which inherently has a much longer cycle time since it has destructive readout; the data has to be written back before a read cycle can complete.)

It consists of assigning sequential addresses to different memory units; so that a reference to word A goes to one bank, and a following reference to word A+1 goes to the other. It was not unknown for interleaving to decrease the access time for a second word by up to 50%, a very significant savings. This is called 'two-way interleaving', but it was possible to extend the technique; e.g. the KL10 could use four-way interleaving.

The implementation was fairly simple, and thus has a large cost/benefit ratio (especially in a oeriod where individual transistors had significant cost). Switches were provided which exchanged two of the bits on the address bus as they were fed into each memory unit; the two bits would be the low bit of the word address (since some memories were byte addressed), and the bit just about the highest bit of the memory's local address. Thus, sequential addresses (on the bus) would alternate between memory units.

This did mean that sequential words in the actual memory would not be sequential in the address space, but keeping the words in order would vitiate the whole point of interleaving (to direct sequential requests to different memory units); it was much simpler to simply accept the unusual order (which the CPU could not see, anyway).

Also, the simple technique of exchanging address bits only works with two (or more) memories of equal size.