Modeling the performance of algorithms on flash memory devices

ABSTRACT

NAND flash memory is fast becoming popular as a component of large scale storage devices. For workloads requiring many random I/Os, flash devices can provide two orders of magnitude increased performance relative to magnetic disks. Flash memory has some unusual characteristics. In particular, general updates require a page write, while updates of 1 bits to 0 bits can be done in-place. In order to measure how well algorithms perform on such a device, we propose the "EWOM" model for analyzing algorithms on flash memory devices. We introduce flash-aware algorithms for counting, listmanagement, and B-trees, and analyze them using the EWOM model. This analysis shows that one can use the incremental 1-to-0 update properties of flash memory in interesting ways to reduce the required number of page-write operations.

REFERENCES

• 1: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 2: Paul England and Marcus Peinado. System and method for implementing a counter, 2006. US Patent Number 7,065,607.
• 3: T. Gleixner, F. Haverkamp, and A. Bityutskiy. UBI - Unsorted Block Images, 2006.
• 4: Toshiba Inc. NAND vs. NOR flash memory, 2006. Downloaded May 2008 from http://www.toshiba.com/taec/components/Generic/Memory_Resources/NANDvsNOR.pdf.
• 5: Intel Corp. Understanding the Flash Translation Layer (FTL) Specification, 1998.
• 6: T. H. Kuo et al. Design of 90nm 1Gb ORNAND flash memory with MirrorBit technology. In Symposium on VLSI Circuits, Digest of Technical Papers, pages 114--115, 2006.
• 7: Sang-Won Lee , Bongki Moon, Design of flash-based DBMS: an in-page logging approach, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247488]
• 8: David Maier, Using write-once memory for database storage, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588151]
• 9: Suman Nath , Aman Kansal, FlashDB: dynamic self-tuning database for NAND flash, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236412]
• 10: Ronald L. Rivest , Adi Shamir, How to reuse a "write - once " memory (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.105-113, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802182]
• 11: Chin-Hsien Wu , Tei-Wei Kuo , Li Ping Chang, An efficient B-tree layer implementation for flash-memory storage systems, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.3, p.19-es, July 2007 [doi>10.1145/1275986.1275991]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories

General Terms:
Algorithms, Performance