Algorithms and data structures for compressed-memory machines

An overview of a set of algorithms and data structures developed for compre ssed-memory machines is given. These include 1) very fast compression and d ecompression algorithms, for relatively small fixed-size lines, that are su itable for hardware implementation; 2) methods for storing variable-size co mpressed lines in main memory that minimize overheads due to directory size and storage fragmentation, but that are simple enough for implementation a s part of a system memory controller; 3) a number of operating system modif ications required to ensure that a compressed-memory machine never runs out of memory as the compression ratio changes dynamically. This research was done to explore the feasibility of computer architectures in which data are decompressed/compressed on cache misses/writebacks, The results led to and were implemented in IBM Memory Expansion Technology (MXT), which for typic al systems yields a factor of 2 expansion in effective memory size with gen erally minimal effect on performance.