The Compression Cache: Virtual Memory Compression for Handheld Computers

Michael J. Freedman Recitation: Rivest TR1 March 16, 2000

Abstract Power consumption and speed are the largest costs for a virtual memory system in handheld computers. This paper describes a method of trading o computation and useable physical memory to reduce disk I/O. The design uses a compression cache, keeping some virtual memory pages in compressed form rather than sending them to the backing store. Eciency is managed by a log-structured circular buer, supporting dynamic memory partitioning, diskless operation, and disk spin-down.

Contents 1 Introduction 2 Design Criteria and Considerations 2.1 2.2 2.3 2.4

Compression to Segmented Memory . . . . . . . . Reversed Compression in Fixed-Size Pages . . . . Non-Reversed Compression in Fixed-Sized Pages . Compression to Log-Structured Buers . . . . . .

3 Design

3.1 Virtual Memory . . . . . . . . . . . . 3.1.1 Basic Hierarchical Paging . . 3.1.2 Modi ed Page Tables . . . . . 3.1.3 Cache Descriptor Table . . . . 3.1.4 Circular Compression Cache . 3.2 Paging the Compressed Store . . . . 3.2.1 Storing Compressed Pages . . 3.2.2 Recovering Compressed Pages 3.3 Variable Memory Allocation . . . . . 3.4 Optimized Disk Accesses . . . . . . . 3.5 Diskless Operation . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

4.1 Energy Eciency . . . . . . . . . . . . . . . . . . . 4.1.1 Constant Clock Speed . . . . . . . . . . . . 4.1.2 Disk Stores versus In-Memory Compression 4.2 Memory Eciency . . . . . . . . . . . . . . . . . . 4.2.1 Initial RAM Partitioning . . . . . . . . . . . 4.2.2 Hierarchical Page Table Size . . . . . . . . . 4.3 Prefetching Pages . . . . . . . . . . . . . . . . . . . 4.4 Disk Spin Policy . . . . . . . . . . . . . . . . . . . 4.5 Technology Trends . . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

5 Conclusion

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

4 Results and Discussion

. . . . . . . . . . .

. . . .

2 3 3 3 3 4

4 4 4 5 5 6 6 6 8 8 9 9

10 10 10 11 12 12 12 13 13 14

14

1 Introduction The handheld computer industry has witnessed signi cant growth in the past few years. Users have begun to use personal data assistants (PDAs) and other mobile computers in great numbers. The applications and features provided by these systems have expanded to match this interest. Newer models of the Palm or Windows CE PDAs provide increased storage capacity, applications such as spreadsheets, databases, and document viewers, and wireless communication to