IEEE T R A N S A C T I O N S O N
`
`COMPUTERS
`
`January 2010
`
`VOLUME 59
`
`NUMBER 1
`
`A publication of the IEEE Computer Society
`Indexed in ISI
`(ISSN 0018-9340)
`
`ITCOB4
`
`RegulaR PaPeRs
`Distributed Systems
`A Novel Weighted-Graph-Based Grouping Algorithm for Metadata Prefetching
`P. Gu, J. Wang, Y. Zhu, H. Jiang, and P. Shang .................................................................................................................. 1
`Interconnection networks
`Heterogeneous Interconnects for Energy-Efficient Message Management in CMPs
`A. Flores, J.L. Aragón, and M.E. Acacio .............................................................................................................................
`Network-on-Chip Hardware Accelerators for Biological Sequence Alignment
`S. Sarkar, G.R. Kulkarni, P.P. Pande, and A. Kalyanaraman ..............................................................................................
`Load Balancing and Task assignment
`Communication-Aware Load Balancing for Parallel Applications on Clusters
`X. Qin, H. Jiang, A. Manzanares, X. Ruan, and S. Yin .......................................................................................................
`Memory and Storage Management
`Improving Flash Wear-Leveling by Proactively Moving Static Data
`Y.-H. Chang, J.-W. Hsieh, and T.-W. Kuo ............................................................................................................................
`Modeling and Performance Evaluation
`Model-Driven System Capacity Planning under Workload Burstiness
`G. Casale, N. Mi, and E. Smirni .........................................................................................................................................
`Security
`Conversion Algorithms and Implementations for Koblitz Curve Cryptography
`B.B. Brumley and K.U. Järvinen .........................................................................................................................................
`Theory and algorithms
`Independent Spanning Trees on Multidimensional Torus Networks
`S.-M. Tang, J.-S. Yang, Y.-L. Wang, and J.-M. Chang .........................................................................................................
`Scalable Node-Level Computation Kernels for Parallel Exact Inference
`Y. Xia and V.K. Prasanna ....................................................................................................................................................
`Verification
`Integrating Evolutionary Computation with Abstraction Refinement for Model Checking
`F. He, X. Song, W.N.N. Hung, M. Gu, and J. Sun ...............................................................................................................
`BRief ContRiButions
`Predictive Temperature-Aware DVFS
`J.S. Lee, K. Skadron, and S.W. Chung ...............................................................................................................................
`Proofs of Correctness and Properties of Integer Adder Circuits
`G. Chen and F. Liu .............................................................................................................................................................
`(Contents continued on back cover)
`
`16
`
`29
`
`42
`
`53
`
`66
`
`81
`
`93
`
`103
`
`116
`
`127
`
`134
`
`www.computer.org
`tc@computer.org
`
`IEEE TRANSACTIONS ON COMPUTERS
`
`Vol. 59, No. 1, January 2010
`
`(Contents continued from front cover)
`
`Comments
`Comment on “Performability Analysis: A New Algorithm”
`V. Suñé, J.A. Carrasco, H. Nabli, and B. Sericola ..............................................................................................................
`2009 Annual Reviewers List ...............................................................................................................................................
`
`137
`139
`
`applications are Invited for the Position of Editor-in-Chief for IEEE Transactions on Computers
`
`The IEEE Computer Society seeks applicants for the position of Editor-in-Chief (EIC) of IEEE Transactions on
`Computers. The initial two-year term of the new EIC is to begin 1 January 2011.
`
`For more information please visit: http://www.computer.org/tc
`
`PURPOSE: The IEEE Computer Society is the world’s largest association
`of computing professionals and is the leading provider of technical
`information in the field.
`MEMBERSHIP: Members receive the monthly magazine Computer,
`discounts, and opportunities to serve (all activities are led by volunteer
`members). Membership is open to all IEEE members, affiliate society
`members, and others interested in the computer field.
`COMPUTER SOCIETY WEB SITE: www.computer.org
`OMBUDSMAN: Email help@computer.org.
`
`Next Board Meeting: 17 Nov. 2009, New Brunswick, NJ, USA
`EXECUTIVE COMMITTEE
`President: Susan K. (Kathy) Land, CSDP*
`President-Elect: James D. Isaak;* Past President: Rangachar Kasturi;*
`Secretary: David A. Grier;* VP, Chapters Activities: Sattupathu V.
`Sankaran;† VP, Educational Activities: Alan Clements (2nd VP);* VP,
`Professional Activities: James W. Moore;† VP, Publications: Sorel
`Reisman;† VP, Standards Activities: John Harauz;† VP, Technical &
`Conference Activities: John W. Walz (1st VP);* Treasurer: Donald F.
`Shafer;* 2008–2009 IEEE Division V Director: Deborah M. Cooper;†
`2009–2010 IEEE Division VIII Director: Stephen L. Diamond;† 2009
`IEEE Division V Director-Elect: Michael R. Williams;† Computer Editor in
`Chief: Carl K. Chang†
`*voting member of the Board of Governors
`BOARD OF GOVERNORS
`Term Expiring 2009: Van L. Eden; Robert Dupuis; Frank E. Ferrante; Roger
`U. Fujii; Ann Q. Gates, CSDP; Juan E. Gilbert; Don F. Shafer
`Term Expiring 2010: André Ivanov; Phillip A. Laplante; Itaru Mimura; Jon
`G. Rokne; Christina M. Schober; Ann E.K. Sobel; Jeffrey M. Voas
`Term Expiring 2011: Elisa Bertino, George V. Cybenko, Ann DeMarle,
`David S. Ebert, David A. Grier, Hironori Kasahara, Steven L. Tanimoto
`
`†nonvoting member of the Board of Governors
`
`EXECUTIVE STAFF
`Executive Director: Angela R. Burgess; Director, Business & Product
`Development: Ann Vu; Director, Finance & Accounting: John Miller;
`Director, Governance, & Associate Executive Director: Anne Marie
`Kelly; Director, Information Technology & Services: Carl Scott;
`Director, Membership Development: Violet S. Doan; Director,
`Products & Services: Evan Butterfield; Director, Sales & Marketing:
`Dick Price
`COMPUTER SOCIETY OFFICES
`Washington, D.C.: 2001 L St., Ste. 700, Washington, D.C. 20036
`Phone: +1 202 371 0101; Fax: +1 202 728 9614; Email: hq.ofc@computer.org
`Los Alamitos: 10662 Los Vaqueros Circle, Los Alamitos, CA 90720-1314
`Phone: +1 714 821 8380; Email: help@computer.org
`Membership & Publication Orders:
`Phone: +1 800 272 6657; Fax: +1 714 821 4641; Email: help@computer.org
`Asia/Pacific: Watanabe Building, 1-4-2 Minami-Aoyama, Minato-ku, Tokyo
`107-0062, Japan
`Phone: +81 3 3408 3118 • Fax: +81 3 3408 3553
`Email: tokyo.ofc@computer.org
`IEEE OFFICERS
`President: John R. Vig; President-Elect: Pedro A. Ray; Past President:
`Lewis M. Terman; Secretary: Barry L. Shoop; Treasurer: Peter W.
`Staecker; VP, Educational Activities: Teofilo Ramos; VP, Publication
`Services & Products: Jon G. Rokne; VP, Membership & Geographic
`Activities: Joseph V. Lillie; President, Standards Association Board
`of Governors: W. Charlton Adams; VP, Technical Activities: Harold L.
`Flescher; IEEE Division V Director: Deborah M. Cooper; IEEE Division
`VIII Director: Stephen L. Diamond; President,
`IEEE-USA: Gordon W. Day
`
`revised 1 May 2009
`
`Micron Ex. 1065, p. 1
`Micron v. Vervain
`IPR2021-01547
`
`

`

`the ieee Computer society is an association of people with professional interest in the field of computers. All members of the IEEE are eligible for membership
`in the Computer Society, as are members of certain professional societies and other computer professionals. Computer Society members will receive this Transac-
`tions in print and online upon payment of the annual Society membership fee ($50 for IEEE members, $99 for all others) plus an annual subscription fee of $49. For
`additional membership and subscription information, visit our Web site at http://computer.org/subscribe, send email to help@computer.org, or write to IEEE Computer
`Society, 10662 Los Vaqueros Circle, PO Box 3014, Los Alamitos, CA 90720-1314 USA. Individual subscription copies of Transactions are for personal use only.
`
`TC
`
`
`inFormation For authors
`
`www.computer.org/tc
`tc@computer.org
`
`IEEE Transactions on
`
`Computers
`
`editorial Board
`
`Editor-in-ChiEf
`FaBrizio lomBardi
`Department of Electrical and Computer Engineering
`Northeastern University
`Boston, MA 02115
`+1 617.373.4159 • + 1 617.373.8970 (FAX)
`Lombardi@ece.neu.edu
`
`AssoCiAtE Editor-in-ChiEf
`CECilia mEtra
`Department of Electronics, Computer Science and Systems
`Università di Bologna
`Viale Risorgimento, 2
`40136 Bologna (Italy)
`+39 051 2093038 • +39-051-2093073 (FAX)
`cmetra@deis.unibo.it
`
`John laCh
`University of Virginia
`jlach@virginia.edu3
`
`walid naJJar
`University of California, Riverside
`najjar@cs.ucr.edu
`
`sanG hyuK son
`University of Virginia
`son@cs.virginia.edu
`
`viCtor C. m. lEunG
`The University of British Columbia
`vleung@ece.ubc.ca
`
`sotiris niKolEtsEas
`Patras University
`nikole@cti.gr
`
`stEPhan olariu
`Old Dominion University
`olariu@cs.odu.edu
`
`sPyros traGoudas
`Southern Illinois University
`spyros@engr.siu.edu
`
`yi-min wanG
`Microsoft Research
`ymwang@microsoft.com
`
`BEhrooz Parhami
`Univ. of California, Santa Barbara
`parhami@ece.ucsb.edu
`
`Jon wEissman
`University of Minnesota Twin Cities
`jon@cs.umn.edu
`
`naGaraJan ranGanathan
`University of South Florida
`ranganat@cse.usf.edu
`
`ChEnG-wEn wu
`National Tsing Hua University
`cww@ee.nthu.edu.tw
`
`miChaEl raynal
`IRISA-IFSIC, Université de Rennes 1
`raynal@irsa.fr
`
`JiE wu
`Temple University
`jiewu@temple.edu
`
`EriC sChwarz
`IBM
`eschwarz@us.ibm.com
`
`honG shEn
`The University of Adelaide
`hong@cs.adelaide.edu.au
`
`sandEEP K. shuKla
`Virginia Polytechnic & State
`University
`shukla@vt.edu
`
`yuanyuan yanG
`The State University of New York
`at Stony Brook
`yang@ece.sunysb.edu
`
`mazin yousiF
`Intel
`mazin.s.yousif@intel.com
`
`alBErt zomaya
`The University of Sydney
`zomaya@it.usyd.edu.au
`
`Elisardo antElo
`University of Santiago de Com-
`postela
`elisardo@dec.usc.es
`
`John K. antonio
`University of Oklahoma
`antonio@ou.edu
`
`d.r. avrEsKy
`IRIANC
`autonomic@irianc.com
`
`Cristiana BolChini
`Politecnico di Milano
`bolchini@elet.polimi.it
`
`JianEr ChEn
`Texas A&M University
`chen@cs.tamu.edu
`
`GEorGE ConstantinidE
`Imperial College London
`george.constantinides@ieee.org
`
`shlomi dolEv
`Ben-Gurion University of the Negev
`dolev@cs.bgu.ac.il
`
`alan d. GEorGE
`University of Florida
`george@hcs.ufl.edu
`
`Kanad GhosE
`State University of New York
`ghose@cs.binghamton.edu
`
`PhilliP B. GiBBons
`Intel Research
`phillip.b.gibbons@intel.com
`
`PatriCK Girard
`LIRMM
`Patrick.Girard@lirmm.fr
`
`dimitris GizoPoulos
`University of Piraeus
`dgizop@unipi.gr
`
`maya GoKhalE
`Sarnoff Corp.
`maya@lanl.gov
`
`Carl a. GuntEr
`University of Illinois at Urbana-
`Champaign
`cgunter@illinois.edu
`
`John Chi-shinG lui
`The Chinese University of Hong
`Kong
`cslui@cse.cuhk.edu.hk
`
`anna lysyansKaya
`Brown University
`anna@cs.brown.edu
`
`radu marCulEsCu
`Carnegie Mellon University
`radum@ece.cmu.edu
`
`iGor marKov
`University of Michigan
`imarkov@eecs.umich.edu
`
`PatriCK mCdaniEl
`Pennsylvania State University
`mcdaniel@cse.psu.edu
`
`tarEK El-Ghazawi
`George Washington University
`tarek@gwu.edu
`
`raJiv GuPta
`University of California, Riverside
`gupta@cs.ucr.edu
`
`Ethan millEr
`University of California
`elm@cs.ucsc.edu
`
`mohamEd EltowEissy
`Virginia Tech
`toweissy@vt.edu
`
`sonia Fahmy
`Purdue University
`fahmy@cs.purdue.edu
`
`lizy Kurian John
`The University of Texas at Austin
`ljohn@ece.utexas.edu
`
`Paolo montusChi
`DAUIN, Politecnico di Torino
`Paolo.Montuschi@polito.it
`
`ieee ComPuteR soCietY
`
`transactions operations Committee
`Vice President:
`david alan GriEr
`Transactions Operations Chair:
`stEvEn tanimoto
`
`members-at-large
`alain aPril
`FranK FErrantE
`Paolo montusChi
`Jon roKnE
`r. samPath
`stEvE sEidman
`
`Journals
`Affective Computing
`Computational Biology & Bioinformatics:
`Computer Architecture Letters
`Computers:
`Dependable and Secure Computing:
`Haptics:
`Knowledge & Data Engineering:
`Learning Technologies:
`Mobile Computing:
`Multimedia:
`NanoBioscience:
`Networking:
`Parallel & Distributed Systems:
`Pattern Analysis & Machine Intelligence:
`Services Computing:
`Software Engineering:
`Very Large Scale Integration:
`Visualization & Computer Graphics:
`
`editors-in-Chief
`Jonathan GratCh
`mariE-FranCE saGot
`KEvin sKadron
`FaBrizio lomBardi
`ravi sandhu
`J. Edward ColGatE
`BEnG Chin ooi
`wolFGanG nEJdl
`mani srivastava
`s.s. hEmami
`CarmElina ruGGiEro
`roCh GuErin
`ivan stoJmEnoviC
`ramin zaBih
`l.J. zhanG
`Bashar nusEiBEh
`n. ranGanathan
`thomas Ertl
`
`Publishing services staff
`
`Senior Manager, Publishing Services
`Production Editor II
`Digital Production Supervisor
`Digital Production Specialist
`Associate Manager, Peer Review and
`Periodical Administration
`Publications Coordinator
`
`aliCia l. stiCKlEy
`EriCa hardison
`stEvE warEham
`marK BartosiK
`hilda Carman
`
`JoyCE arnold
`
`Caring about the environment
`Because the IEEE Computer Society is dedicated to environmental responsibility, we have
`asked our printer to change from a UV-coated cover stock to an aqueous coating. We have
`also switched to FSC certified paper to futher reduce our impact on the enviroment.
`
`IEEE TRANSACTIONS ON COMPUTERS is published monthly by the IEEE Computer Society. ieee Corporate office: Three Park Avenue, 17th Floor, New York, NY 10016-5997 USA. Responsibility for the content rests upon the authors
`and not upon the IEEE or the IEEE Computer Society. ieee Computer society Publications office: 10662 Los Vaqueros Circle, PO Box 3014, Los Alamitos, CA 90720-1314 USA. ieee Computer society Headquarters: 1730 Massachusetts
`Ave. NW, Washington, DC 20036-1992 USA. Back issues: IEEE members $20.00, nonmembers $130.00 per copy. (Note: Add $4.00 postage and handling charge to any order from $1.00 to $50.00, including prepaid orders). Complete price
`information available on request. Reuse Rights and Reprint Permissions: Educational or personal use of this material is permitted without fee, provided such use: 1) is not made for profit; and 2) includes this notice and a full citation to
`the original work on the first page of the copy; and 3) does not imply IEEE endorsement of any third-party products or services. Authors and their companies are permitted to post their IEEE-copyrighted material on their own web servers
`without permission, provided that the IEEE copyright notice and a full citation to the original work appear on the first screen of the posted copy. Permission to reprint/republish this material for commercial, advertising or promotional
`purposes or for creating new collective works for resale or redistribution must be obtained from IEEE by writing to the IEEE Intellectual Property Rights Office, 445 Hoes Lane, Piscataway, NJ08854-4141 or pubs-permissions@ieee.org.
`Copyright © 2010 IEEE. All rights reserved. Abstracting and Library Use: Abstracting is permitted with credit to the source. Libraries are permitted to photocopy for private use of patrons, provided the per-copy fee indicated in the code
`at the bottom of the first page is paid through the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923. Periodicals postage paid at New York, NY, and at additional mailing offices. Postmaster: Send address changes to
`IEEE TRANSACTIONS ON COMPUTERS, IEEE, Membership Processing Dept., 445 Hoes Lane, PO Box 1331, Piscataway, NJ 08854-4141 USA. GST Registration No. 125634188. Canada Post Publications Mail Agreement Number 40013885.
`Return undeliverable Canadian addresses to: PO Box 122, Niagara Falls, ON L2E 6S8. Printed in the USA on ANSI/NISO standard Z39.48-1992 acid-free paper.
`
`Scope of the Journal
`The IEEE Transactions on Computers (TC) is a monthly publication with
`a wide distribution to researchers, developers, technical managers,
`and educators in the computer field. It publishes papers on research in
`areas of current interest to the readers. These areas include, but are not
`limited to, the following: a) computer organizations and architectures;
`b) operating systems, software systems, and communication protocols;
`c) real-time systems and embedded systems; d) digital devices,
`computer components, and interconnection networks; e) specification,
`design, prototyping, and testing methods and tools; f) performance,
`fault tolerance, reliability, security, and testability; g) case studies and
`experimental and theoretical evaluations; and h) new and important
`applications and trends.
`
`SubmiSSion of manuScriptS for peer review
`The information below is a summary of our guidelines detailed at
`the TC author center, www.computer.org/portal/web/tc/author.
`All authors are responsible for understanding these guidelines before
`submitting their manuscript.
`
`Manuscript Central
`The IEEE Computer Society is now employing a secure, Web-
`based manuscript submission and peer-review tracking system
`called Manuscript Central. To submit a manuscript, please visit
`https://mc.manuscriptcentral.com/tc-cs. The site contains detailed
`instructions on usage and submission requirements.
`
`TC Manuscript Specifications
`
`• Regular papers—14 double-column pages, using the IEEE CS template*
`• Brief contributions—8 double-column pages, using the
`IEEE CS template*
`• Comments—2 double-column pages, using the IEEE CS template*
`
`*These page limits include references and reasonably-sized figures.
` A double-column page is defined as an 7.875" x 10.75" page with 9.5-
`point type and 12-point vertical spacing, Margins should be one inch
`all around (for top, bottom, right, and left).
` Templates for submitting manuscripts can be downloaded from the
`TC author center.
`
`Online First Publication Model
`The IEEE Computer Society uses an online first publication model
`which means that accepted papers will be posted online shortly after
`all publication materials are received. Author PDF will be stamped as
`a “Preprint” and sent to the IEEE for posting in Xplore. After the paper
`has been edited and proofs reviewed, it will then be restamped as a
`“Rapid Post,” indicating that the paper is complete with the exception
`of pagination. Authors that do not wish to participate in this program
`should notify the Transactions Assistant upon acceptance of the
`paper.
`
`Supplemental Material
`Supplemental material can include relevant proofs, code, experimental
`data, short movies, appendices, animations, audio, etc.
` All supplemental material will undergo the peer review process
`along with the paper.
` Supplemental material will be published on our Digital Library with
`the electronic version of the paper, where it can be accessed for free,
`and a pointer to the supplemental material will be included in the
`printed version.
`
`For information on submitting final publication materials, please visit
`www.computer.org/portal/web/peerreviewjournals/author.
`
`SubmiSSion policieS
`Submissions to TC must represent original material. Papers are
`accepted for review with the understanding that the same work has
`been neither submitted to, nor published in, another journal.
` Concurrent submission to these Transactions and other publications
`is viewed as a serious breach of ethics and, if detected, will result in
`immediate rejection of the submission.
` However, papers previously published in conference proceedings,
`digests, preprints, or records are eligible for consideration provided
`that the papers have undergone substantial revision and that the
`author informs the Transactions Assistant and editor-in-chief at the
`time of submission. A version of the previously published work will
`need to be sent to our office, and a brief description of the differences
`will need to be provided.
`
`copyright information
`The author is responsible for obtaining copyright releases and corporate
`and security clearances prior to submitting material for consideration.
` Please refer to the IEEE policies (www.ieee.org/about/whatis/
`policies/p6-4.xml) on authorship (section A), duplication publication,
`and self-plagiarism (section B(f) and (h)) to ensure that your paper
`meets all criteria for submission.
`
`It is the IEEE's policy (Policy 6.16) to assume that all clearances are
`granted when a paper is submitted.
` For more information about our copyright policies, please visit
`www.computer.org/copyright.htm.
`
`mandatory overlength page chargeS
`In its mission to maintain a consistent and high quality publication
`process, the IEEE Computer Society follows a strict policy on the
`lengths of both manuscript submissions and final papers.
` So that manuscripts meet submission requirements, supporting
`but nonessential information should be submitted as supplemental
`material. However, there may occasionally be an accepted (final)
`paper for which an editor-in-chief determines that an exception to the
`standard limit is appropriate and that from one to four additional pages
`are needed. The IEEE Computer Society allows for this possibility
`within its policy on mandatory overlength page charges.
`
`Independent of any voluntary page charges, the IEEE Computer
`Society assesses the authors of accepted papers that exceed the regular
`paper length limit a fee called Mandatory Overlength Page Charge
`(MOPC). The regular paper page length limit is defined at 14 formatted
`pages, including references and author biographies. Any pages or
`fraction thereof exceeding this limit are charged $200 per page. Regular
`papers may not exceed 18 formatted pages.
` Authors will be notified of any assessed charges when galley proofs
`are sent for review. Payment must be sent at the time galley proofs are
`approved by the author.
` The IEEE Computer Society's policy on page limits as described here
`is strictly enforced.
`
`Ordering reprints
`reprints
`Information
`about purchasing
`www.computer.org/author/reprint.htm.
`
`can be
`
`found
`
`at
`
`For additional information or to inquire about the status of a paper
`awaiting production, please visit the IEEE Computer Society Web
`site or contact the TC Transactions Assistant.
`
`
`
`
`
`
`
`
`TC Transactions Assistant
`IEEE Computer Society
`PO Box 3014
`Los Alamitos, CA 90720-1314, USA
`E-MAIL: tc@computer.org
`PHONE: +1.714.821.8380 FAX: +1.714.821.9975
`
`Micron Ex. 1065, p. 2
`Micron v. Vervain
`IPR2021-01547
`
`

`

`IEEE TRANSACTIONS ON COMPUTERS, VOL. 59, NO. 1,
`
`JANUARY 2010
`
`53
`
`Improving Flash Wear-Leveling
`by Proactively Moving Static Data
`
`Yuan-Hao Chang, Member, IEEE, Jen-Wei Hsieh, Member, IEEE, and
`Tei-Wei Kuo, Senior Member, IEEE
`
`Abstract—Motivated by the strong demand for flash memory with enhanced reliability, this work attempts to achieve improved flash-
`memory endurance without substantially increasing overhead and without excessively modifying popular implementation designs such
`as the Flash Translation Layer protocol (FTL), NAND Flash Translation Layer protocol (NFTL), and Block-Level flash translation layer
`protocol (BL). A wear-leveling mechanism for moving data that are not updated is proposed to distribute wear-leveling actions over the
`entire physical address space, so that static or rarely updated data can be proactively moved and memory-space requirements can be
`minimized. The properties of the mechanism are then explored with various implementation considerations. A series of experiments
`based on a realistic trace demonstrates the significantly improved endurance of FTL, NFTL, and BL with limited system overhead.
`
`Index Terms—Flash memory, wear leveling, endurance, reliability.
`
`Ç
`
`1 INTRODUCTION
`
`WHILE flash memory remains one of the most popular
`
`storage-system designs for embedded systems, its
`applications have far surpassed its original design goals. The
`two popular NAND flash-memory designs are Single Level
`Cell (SLC) flash memory and Multiple Level Cell (MLC)
`flash memory. Each SLC flash-memory cell can accommo-
`date one-bit information while each MLCn flash-memory
`cell can contain n-bit information. As n increases, the
`endurance of each block in MLC flash memory decreases
`substantially. In recent years, flash memory has become one
`part or layer in many system designs. Well-known examples
`are the flash-memory cache of hard disks proposed by Intel
`[2], [3], [4] and the Microsoft Windows Vista fast booting
`service [5], [6]. Such developments reveal the limitations of
`flash memory, especially in terms of endurance.
`The reliability of
`flash memory is an even more
`challenging problem now that
`low-cost
`flash-memory
`designs are gaining market momentum [7]. For example,
`the endurance of an MLC2 flash-memory block is only
`10,000 (or 5,000) erase cycles whereas that of its SLC flash-
`memory counterpart is 100,000 erase cycles [8], [9]. As the
`number of bits of
`information per cell would keep
`increasing for MLC in the near future, the endurance of a
`block might also get worse, such as few thousand or even
`hundred erase cycles. This underlines the reliability issue of
`
`. Y.-H. Chang and T.-W. Kuo are with the Department of Computer Science
`and Information Engineering, Graduate Institute of Networking and
`Multimedia, National Taiwan University, CSIE Building, No. 1, Sec. 4,
`Roosevelt Rd., Taipei 106, Taiwan.
`E-mail: {johnson, ktw}@csie.ntu.edu.tw.
`. J.-W. Hsieh is with the Department of Computer Science and
`Information Engineering, National Taiwan University of Science and
`Technology, IB-1032, CSIE, No. 43, Sec. 4, Keelung Rd., Taipei 106,
`Taiwan. E-mail: jenwei@mail.ntust.edu.tw.
`
`Manuscript received 20 Sept. 2007; revised 1 Mar. 2009; accepted 11 Mar.
`2009; published online 10 Sept. 2009.
`Recommended for acceptance by A. Gonzalez.
`For information on obtaining reprints of this article, please send e-mail to:
`tc@computer.org, and reference IEEECS Log Number TC-2007-09-0476.
`Digital Object Identifier no. 10.1109/TC.2009.134.
`
`flash memory. However, improving reliability is proble-
`matic because flash-memory designs allow little compro-
`mise between system performance and cost, especially for
`low-cost devices. These observations motivate the current
`proposal
`for enhancing flash-memory endurance with
`minor modifications of popular implementation designs.
`A NAND flash-memory chip contains many blocks, and
`each block consists of a fixed number of pages. A block is
`the smallest unit involved in erase operations while read
`and write operations are done in pages. Each page of
`small-block(/large-block) SLC flash memory can store
`512 B(/2 KB) data, and each block contains 32(/64) pages.
`The configuration of MLC2 flash memory is the same as
`that of large-block SLC flash memory, except that each
`block is composed of 128 pages [10]. Notably, recent MLC
`designs are intended to reduce costs by employing large-
`capacity pages such as 4 KB pages and 8 KB pages [11].
`Flash memory is usually managed by a block-device-
`emulating layer so that file systems can be built on top (see
`below discussion regarding Flash Translation Layer proto-
`col (FTL), NAND Flash Translation Layer protocol (NFTL),
`and Block-Level flash translation layer protocol (BL)). Such
`a layer implementation can be carried out by either software
`on a host system (as a raw medium) or hardware/firmware
`on the flash device. In the past decade, numerous research
`results and implementation designs have been proposed to
`satisfy the performance needs of flash-memory storage
`systems, e.g., [12], [13], [14], [15], [16], [17], [18], [19], [20].
`Some authors have proposed different system architectures
`and layer designs, e.g., [16], [17], [18], and some have
`exploited large-scaled storage systems and data compres-
`sion, e.g., [19], [20].
`Given the characteristics of flash memory in out-place
`updates, data to be updated must be written to another
`page of flash memory, where the original page of the data is
`marked as invalid. The out-place-update characteristic
`results in the wear-leveling issue over flash memory
`because any recycling of invalid pages introduces block
`
`0018-9340/10/$26.00 ß 2010 IEEE
`Published by the IEEE Computer Society
`Authorized licensed use limited to: Kaytlyn Snyder. Downloaded on September 21,2022 at 21:57:08 UTC from IEEE Xplore. Restrictions apply.
`
`Micron Ex. 1065, p. 3
`Micron v. Vervain
`IPR2021-01547
`
`

`

`54
`
`IEEE TRANSACTIONS ON COMPUTERS, VOL. 59, NO. 1,
`
`JANUARY 2010
`
`erasing. The objective of wear leveling is to evenly
`distribute block erases over flash memory so that flash-
`memory endurance can be improved. Thus, various
`promising approaches based on dynamic wear leveling
`have been proposed, e.g., [16], [21], [22], [23], [24]. Dynamic
`wear leveling achieves wear leveling by recycling blocks of
`hot (i.e., dynamic or frequently updated) data areas. Such
`approaches require efficient identification of hot data, and
`several excellent designs have been proposed, e.g., [16],
`[25],
`[26],
`[27]. Although dynamic wear leveling does
`substantially enhance wear leveling, the endurance im-
`provement is stringently constrained by its nature: that is,
`blocks of cold data (i.e., infrequently updated data) are
`likely to stay intact regardless of whether updates of hot
`data wear out other blocks. In other words, updates and
`recycling of blocks/pages will only happen to blocks that
`are free or occupied by hot data.
`to dynamic wear
`Static wear leveling is orthogonal
`leveling.
`Its objective is to proactively move static or
`infrequently updated data to other locations so as to
`prevent any static or infrequently updated data from
`staying at any block for a long period of time. Thus, wear
`leveling can be evenly applied to all blocks. For example,
`assume that an extremely large quantity of data must be
`written or even repeatedly updated to a 2 GB flash memory.
`If cold data, such as movies, comprise 1.5 GB of the flash
`memory, then updating those data would be constrained in
`the reusing of blocks in the one fourth of the flash memory.
`No dynamic wear leveling can effectively resolve the
`endurance problem because cold data always stay at their
`blocks. Only static wear leveling can ensure that blocks are
`evenly utilized and have even erase counts because it can
`keep cold data from staying at their blocks.
`Although static wear leveling was first defined in early
`2000, e.g., [28], there are still limited results reported in the
`literature [21], [22], [28] due to historic market needs.
`Particularly, Ban and Hasbaron proposed randomly erasing
`blocks after a fixed number of erase or write requests [22].
`Ban and Hasbaron’s algorithm was analyzed both theore-
`tically and experimentally by Ben-Aroya and Toledo and
`later implemented by Spivak and Toledo in a flash-based
`storage system [29], [30]. Although Ban and Hasbaron’s
`algorithm has proven being effective, the algorithm has
`difficulty in identifying hot and cold data. Its inadequate
`tracking of data-access locality limits its effectiveness since
`hot data are frequently updated and are not necessary to be
`moved around by a wear-leveling algorithm. The popularity
`of MLC flash memory and the widespread adoption of flash
`memory in various products with high update frequencies
`have focused much attention on static wear leveling in
`recent years. For example, some recent
`flash-memory
`products have adopted Ban and Hasbaron’s algorithm for
`static wear leveling. The main technical challenge of static
`wear leveling is on the endurance improvement with
`respect to extra overheads that are considered reasonable
`in selected products.
`This study proposes a static wear-leveling mechanism for
`improving flash-memory endurance with limited memory-
`space requirements. Specifically, an adjustable housekeep-
`ing data structure is presented, and a cyclic-queue-based
`
`Fig. 1. The typical system architecture.
`
`scanning procedure is proposed for static wear leveling. The
`objective is to improve the endurance of flash memory with
`limited overhead and without excessively modifying
`popular implementation designs, such as FTL, NFTL, and
`BL. The behavior of the proposed mechanism was analyzed
`with respect to FTL, NFTL, and BL, on extra block erases,
`extra live-data copying, address translation time, space
`utilization, and main-memory requirements. A series of
`experiments was then conducted based on a realistic trace.
`The experiments revealed endurance improvements of
`103.37, 136.32, and 60.74 percent
`in FTL, NFTL, and
`BL-based storage systems, respectively, in terms of the first
`failure time (i.e., the first time that a worn-out block occurs).
`Erase-count distribution over blocks was also substantially
`improved.
`The rest of this paper is organized as follows: Section 2
`presents the system architectures and summarizes popular
`existing implementations of Flash Translation Layer for
`address translation and bloc