Increasing VLSI chip address and data I/O pin bandwidth through compression

Bandwidth is becoming a performance limiting factor in VLSI chips: the number of address and data lines connecting a chip to external circuitry has increased only slightly while the amount and speed of circuitry that can be integrated continues to grow exponentially. This thesis evaluates the feasibility of exploiting redundancy in address and data streams in order to reduce their bandwidth requirements through compression. First, I analyze the information content of several address and data reference streams to determine how much compression may be possible. My results indicate that a new scheme, based on dynamic Huffman coding (Vitt87), can encode a typical 32 bit address in fewer than six bits. This scheme is also able to encode a typical 32 bit data value in fewer than four bits.

Although my coding scheme is too complex and computationally expensive to implement in practice, it provides an upper bound on the bandwidth that can be achieved by practical compression schemes for address and data information. Thus, the remainder of this work comprises analyses of several such schemes. In particular, I investigate the feasability of placing compression hardware between the on-chip cache and the I/O pins. I introduce the fully associative LRU stack as a means of assessing locality, and show that the amount of locality is drastically reduced in the cache miss stream. This implies that the memory requirements of compression hardware could be as high as the memory used in on-chip caches. I then evaluate the Header Stack address compression scheme of Plezskun et al. (P1RD81) in order to validate their results and determine if architectural developments since its introduction have had any affect. Finally, I present the Successor Cache address and data compression scheme. Through trace-driven simulations, I empirically derive the relationship between performance and storage requirements.

My results imply that given 1993 transistor densities, it may not be practical to integrate compression hardware onto VLSI chips. However, as transistor densities continue to increase much faster than the I/O pin count, some form of address and data compression will be vital. These techniques will enable a substantial reduction in the number of bus lines and I/O pins required for off-chip transfers.