Start-Gap: Low-Overhead Near-Perfect Wear Leveling for Main Memories

Start-Gap: Low-Overhead Near-Perfect Wear Leveling for Main Memories

Start-Gap: Low-Overhead Near-Perfect Wear Leveling for Main Memories Moinuddin Qureshi John Karidis, Michele Franceschini Viji Srinivasan, Luis Lastras, Bulent Abali IBM T. J. Watson Research Center, Yorktown Heights, NY MICRO-2009 2007 IBM Corporation Introduction: Lifetime Limited Memories Emerging Memory Technologies (PCM) candidate for main memory. Reasons: Scalability, Leakage Power Savings, Density, etc. Challenge : Each cell can endure 10-100 Million writes Limited lifetime 16 yrs workloads 4 yrs With uniform write traffic, system lifetime ranges from 4-20 years 2

2007 IBM Corporation Problem: Non-Uniformity in Writes Database workload (writes occur on eviction from a 256MB DRAM cache) Average Heavy non-uniformity in writes: <10% lines incur 90%+ of write traffic 3 2007 IBM Corporation Expected Lifetime with Non-Uniform Writes Normalized Endurance (%) Norm. Endurance = Num. writes before system failure Num. writes before failure with uniform writes x 100%

20x lower 100 95 90 85 80 75 70 65 60 55 50 45 40 35 30 25 20 15 10 5

0 Baseline w/o spares Baseline (64K spare lines) oltp db1 db2 fft stride stress Gmean Even with 64K spare lines, baseline gets 5% lifetime of ideal 4

2007 IBM Corporation Outline 5 Problem Background on Wear Leveling Start Gap Wear Leveling Randomized Start-Gap Security Considerations Summary 2007 IBM Corporation Existing Proposals: Table-Based Wear Leveling

Wear Leveling: Make writes uniform by remapping frequently written lines. Studied extensively for Flash Memories. Almost all proposals Table based. Line Addr. A B C Lifetime Count 99K (Low) 100K (Med) 101K (High) Period Count 1K (Low) 3K (High) 2K (Med) Line Remap Addr A C

B A C B Indirection Table Physical Address 6 PCM Address 2007 IBM Corporation Disadvantages of Table Based Methods Overheads: 1. Area of several (tens of) megabytes 2. Indirection latency (table in EDRAM/DRAM) Area overhead can be reduced with more lines per region: Reduced effectiveness (e.g. Line0 always written) Support for swapping large memory regions (complex)

Our Goal: A wear leveling algorithm that avoids the storage, latency, and complexity of table based methods and still achieves lifetime close to ideal. 7 2007 IBM Corporation Outline 8 Problem Background on Wear Leveling Start Gap Wear Leveling Randomized Start-Gap Security Considerations

Summary 2007 IBM Corporation Start-Gap Wear Leveling Two registers (Start & Gap) + 1 line (GapLine) to support movement. Move GapLine every 100 writes to memory. 0 1 2 3 GAP A B C D START 4

PCMAddr = (Start+Addr); (PCMAddr >= Gap) PCMAddr++) Storage overhead: less than 8 bytes (GapLine taken from spares) Latency: Two additions (no table lookup) Write overhead: One extra write every 100 writes 1% 9 2007 IBM Corporation Normalized Endurance (%) Results for Start-Gap 100 90 80 70 60 50 40 30 20

10 0 Baseline Start Gap Perfect oltp db1 db2 fft stride stress Gmean On average, Start-Gap gets 53% normalized endurance

10X better than baseline, but still 2x lower than Ideal. Why? 10 2007 IBM Corporation Spatial Correlation in Heavily Written Regions Start-Gap moves a line to its neighbor If heavily written regions are spatially close, Start-Gap may move hot lines to other hot lines db1 Peaks FFT Writes Localized If address space is randomized, hot regions will be spread uniformly 11 2007 IBM Corporation Outline

12 Problem Background on Wear Leveling Start Gap Wear Leveling Randomized Start-Gap Security Considerations Summary 2007 IBM Corporation Randomized Start Gap Physical Address Line Addr Randomized Address

Static Randomizer Start-Gap Mapping PCM Address PCM Hot lines One-to-one mapping Invertible function. Configured at design/boot. Minor change can support Pagemode memory. Randomizer is OS unaware. 13 2007 IBM Corporation Efficient Address Space Randomization Two proposals (very little hardware) Random Invertible Binary (RIB) Matrix

Feistel Network (crypto) RIB Matrix b00 b01 b02 b03 b10 b11 b12 b13 b20 b21 b22 b23 x b30 b31 b32 b33 a0 a1 a2 a3 = c0 c1 c2 c3 5 byte storage (3 cycle latency) 85 byte storage (1 cycle latency) 14

2007 IBM Corporation Normalized Endurance (%) Results for Randomized Start-Gap 100 90 80 70 60 50 Baseline StartGap StartGap+RIB StartGap+Feistel Nw 40 30 20 10

0 oltp db1 db2 fft stride stress Gmean Randomized Start-Gap achieves 97% of ideal lifetime while incurring a total storage overhead of 13 bytes. 15 2007 IBM Corporation

Analytical Model for Randomized Start Gap We developed a simple analytical model that uses variance in write traffic across lines to compute norm. endurance (details in paper) Lifetime from analytical model matches very well (97% vs. 96.8%) 16 2007 IBM Corporation Normalized N o rm a lizEndurance e d E n d u ra(%) n c e (% ) Comparison with Table Based Methods 100 95 90 85 80 75

70 65 60 55 50 45 40 35 30 25 20 15 10 5 0 1 Baseline 2

3 TBWL-640MB TBWL-1.25MB (1 line per region) (region=128KB) 4 RandSGap 13 bytes Randomized Start-Gap achieves lifetime similar to hardware-intensive version of table based & avoids several tens of cycle of latency overhead 17 2007 IBM Corporation Outline

18 Problem Background on Wear Leveling Start Gap Wear Leveling Randomized Start-Gap Security Considerations Summary 2007 IBM Corporation Security Challenge in Lifetime Limited Memories What if an adversary knows about write endurance limit? Repeat Address Attack (RAA): repeat writes to same line. RAA can cause line failure in less than 1 minute Time to 1 line failure = Endurance * (CyclesPerWrite/CyclesPerSec) (seconds) = 225 x 212 4GHz

= 32 seconds Both baseline and randomized Start-Gap suffers from this attack. Even table based wear leveling (practical version) suffers. 19 2007 IBM Corporation Security Aware Wear Leveling Solution: Divide memory into regions. One Start-Gap per region. Region size is made such that each line in region guaranteed to move once every endurance number of writes to region NumLinesInRegion < Endurance WritesPerGapMovement We use 256K lines per region (256 regions). Area Overhead < 1.5KB RAA now takes about 3-4 months to cause failure. With delayed writes (in paper), time to failure ranges in year(s) 20

2007 IBM Corporation Outline 21 Problem Background on Wear Leveling Start Gap Wear Leveling Randomized Start-Gap Security Considerations Summary 2007 IBM Corporation Summary

Limited endurance poses lifetime and security challenge Table based wear leveling: area and latency overhead Start-Gap: Cost-effective wear leveling with two registers Randomized Start-Gap: 97% of ideal endurance with 13 bytes We took a first step towards making PCM systems secure against malicious attacks (RAA). Motivation for more research 22 2007 IBM Corporation Advertisement HPCA 2010 Tutorial Phase Change Memory: A Systems Perspective Organizers Dr. Moinuddin K Qureshi (IBM Research) Prof. Sudhanva Gurumurthi (University Of Virginia) Dr. Bipin Rajendran (IBM Research) Date: Jan 9, 2010 (Half Day) http://www.cs.virginia.edu/~gurumurthi/PCM_tutorial/ 23

2007 IBM Corporation Backup Slides 24 2007 IBM Corporation Supporting DRAM PageMode with Start-Gap Randomization must be done at a DRAM-Page granularity instead of line 25 2007 IBM Corporation Lifetime Under RAA attack Time to Failure (in seconds) 100000000 4 months

10000000 1000000 1 week 100000 10000 1000 1 minute 100 10 1024 2048 4096 8192

16384 32768 65536 131072 262144 524288 1048576 2097152 Number of Lines in Region RAA will now take about 3-4 months to cause failure. With delayed writes (in paper), time required would range in year(s). 26 2007 IBM Corporation Outline

27 Problem Background on Wear Leveling Start Gap Wear Leveling Randomized Start-Gap Security Considerations Summary 2007 IBM Corporation Spare Lines 28 2007 IBM Corporation

Recently Viewed Presentations

  • Entropy, Free Energy, and Equilibrium

    Entropy, Free Energy, and Equilibrium

    DG = 0 The reaction is at equilibrium. 18.5 18.5 aA + bB cC + dD DG0 rxn dDG0 (D) f cDG0 (C) f = [ + ] - bDG0 (B) f aDG0 (A) f [ + ] DG0 rxn...
  • So Ya Wanna Go to Grad School  UW

    So Ya Wanna Go to Grad School UW

    Introduction of UW Econ Grad. Program. Co-op Option (5 terms / 20 months)5 core courses (*), 3 electives, eight month (2 term) co-op placement and capstone research project YEAR 1 - Fall Term. Academic integrity workshop. Math-camp (*) ECON 601...
  • Ieee 802.11

    Ieee 802.11

    Wireless Medium Access Control (MAC)(Refer Section 7.3.1 and 7.3.2 in textbook)Slides Adopted from:Romit Roy Choudhury Wireless Networking Lectures University of Illinois at Urbana Champaign
  • RSS Feeds - Colorado State University

    RSS Feeds - Colorado State University

    CSU news and events. RSS feed link on catalog search results in Discovery. RSS link on most CSU Libraries Web pages. New books lists e.g. Alabama. Databases saved searches e.g. Web of Science. Journal contents e.g. Chicago. 12/9/2008. RSS Feeds...
  • Canada - MR. PETRILLO&#x27;S SOCIAL STUDIES CLASS

    Canada - MR. PETRILLO'S SOCIAL STUDIES CLASS

    Good soil in Canada allows farmers to grow crops for the people of Canada with enough left over to trade with other countries. About 5% of Canada's land is arable (farmable) While this may seem like only a small amount...
  • Chapter 4 - Force System Resultants

    Chapter 4 - Force System Resultants

    * Moment of a Couple Resultant Force is zero. Effect of couple is a moment * Moment of a Couple A Couple consists of two parallel forces, equal magnitude, opposite directions, and separated a distant "d" apart. A Couple Moment...
  • Program Sponsor Ohio Department of Transportation Program Administrator

    Program Sponsor Ohio Department of Transportation Program Administrator

    Determine Support Structure and Organizational Infrastructure OGRIP reviews the County organizational infrastructure to ensure the LBRS' success at both the county and state level. This structure must support the process for policy and decision-making as well as maintenance and updates...
  • ABECEDA RAUNALA PRIKAZ BROJEVA I ZNAKOVA U RAUNALU

    ABECEDA RAUNALA PRIKAZ BROJEVA I ZNAKOVA U RAUNALU

    (2) zapis sa stalnom točkom (ili fiksnim zarezom) Koliko je? 0,00000000000000000000000011 1100000000000000000000000 2,3E+14 2,3E-14 Tehnika kliznog ili pomičnog zareza 230000000000000(10)=2,3·1014 0,000000000000023 (10)=2,3·10-14 PRAKTIČNIJE 2,3 10 -14 mantisa baza eksponent Binarni brojevi i množenje s 2n i 2-n Binarni broj se...