Flip-N-Write: A Simple Deterministic Techniqueto Improve PRAM Write Performance, Energyand EnduranceSangyeun Cho Hyunjin LeePresenter: Brian WongchaowartMarch 17, 2010MotivationSuppose that you had a rewritable storage medium with thefollowing characteristics:•The values of individual bits can be changed independently.•Updating a bit from 0 to 1 or from 1 to 0 is a relativelyexpensive operation (in time, energy, or both), compared tothe cost of leaving a bit unchanged.How can you minimize the cost of updating the information storedin this medium?Practical Justification: PRAM•Phase-change random access memory (PRAM) may soonreplace flash memory and DRAM in many applications.•Each memory cell contains a material that has two phaseswith very different electrical properties.•An “amorphous phase” exhibits high resistivity, while a“crystalline phase” has much lower resistivity.•Reading the bit value stored in a cell consists of sensing itsresistivity (a fast, low-power operation).•In order to change the bit value stored in a PRAM cell, thephase-change material must be brought into a different phaseby heating.•Heating the phase-change material to its crystallizationtemperature for a sufficiently long period of time causes it toassume its crystalline state.•Heating it to a yet higher temperature for a short period oftime makes the material amorphous.•Both of these operations require high-power current pulses.Worst-Case Number of Bit Updates•Suppose that the storage medium is accessed as an array ofn-bit words, where n is even.•Each array element must be able to store one of 2ndifferentlogical word values, but the number of bits used to physicallyrepresent each logical word and the mapping between thelogical word values and their physical representations isunspecified.•We now consider the problem of limiting the worst-casenumber of physical bit update operations required to store anarbitrary logical word value to an array element (making thesimplifying assumption that updating a bit from 0 to 1 andfrom 1 to 0 have the same cost).•If each array element is physically stored as a bit string oflength n, then there must be a one-to-one mapping betweenthe 2nlogical word values that can be stored in the arrayelement and the 2npossible bit strings of length n that canreside on the storage medium.•In the worst-case, the unique physical representation of a newlogical word value to be stored will be the bitwise complementof the bit string currently stored in the medium, meaning thatall n bits must be updated.•Thus limiting the worst-case number of bit update operationsrequires using at least n + 1 bits to store one of 2nlogicalword values.Hamming WEM Codes•The problem of limiting the worst-case number of bit updateoperations in this model was formalized in 1989 by Ahlswedeand Zhang as a problem in coding theory.1•We would like to store M different messages (logical wordvalues) in a storage medium called a WEM (write-efficientmemory).•Each message mi, for 1 ≤ i ≤ M, is associated with a subsetCiof {0, 1}n(the bit strings of length n), such that Ciand Cjare disjoint for i 6= j.•Any member of Ciis a valid physical representation ofmessage miwhen stored on the medium.1R. Ahlswede and Z. Zhang, “Coding for Write-Efficient Memory,”Information and Computation 83, no. 1 (1989): 80–97.Hamming WEM Codes•Suppose that the medium currently holds the bit string a ∈ Ci.•In order to update the message stored on the medium from mito mj, some bit string b ∈ Cjmust be written to the medium.•Because we want to minimize the number of bit updateoperations required, we always choose the bit string b ∈ Cjthat minimizes the Hamming distance between a and b.•Our objective is to design a collection {C1, C2, . . . , CM} ofpairwise-disjoint subsets of {0, 1}nsuch that given a bit stringa ∈ Cifor arbitrary i, it is possible to transform a into somebit string b ∈ Cjusing no more than D bit update operationsfor arbitrary j. This is called an (n, M, D) Hamming WEMcode.Flip-N-Write•We will restrict our attention to the case where M = 2nfor apositive even integer n and each message is stored on themedium as a bit string of length n + 1.•It will be seen that Flip-N-Write is the natural (n + 1, 2n, n/2)Hamming WEM code for this setting.•Flip-N-Write was indirectly described by Ahlswede and Zhangin 1989 (“the collection of cosets of a perfect linear channelcode is a perfect WEM code”) and was later independentlyrediscovered by Sangyeun Cho as a practical technique forPRAM.Derivation of Flip-N-Write•We first show that the best achievable upper bound on theworst-case number of bit update operations is n/2, given theassumption that we want to be able to store 2ndifferentmessages, where n is even, using n + 1 bits.•We then show that the collection of cosets of a binaryrepetition code of length n + 1—that is, the perfect binarylinear channel code consisting of just the two codewords 0n+1and 1n+1—is a (n + 1, 2n, n/2) Hamming WEM code.Lemman/2Xk=0n + 1k= 2n.Proof.Recall thatnk=nn−k. Thenn/2Xk=0n + 1k=n/2Xk=0n + 1n + 1 − k=n+1Xk=n/2+1n + 1k.But sincen/2Xk=0n + 1k+n+1Xk=n/2+1n + 1k=n+1Xk=0n + 1k= 2n+1,it follows thatn/2Xk=0n + 1k=2n+12= 2n.TheoremAny (n + 1, 2n, D) Hamming WEM code satisfies D ≥ n/2.Proof.•Suppose that the medium currently holds the bit string a ∈ Ci.•The number of bit strings of length n + 1 within Hammingdistance D of a is exactlyn + 10+n + 11+ · · · +n + 1D=DXk=0n + 1k.•In order for it to be possible to transform a into some bitstring b ∈ Cjusing no more than D bit update operations for1 ≤ j ≤ 2n, we therefore require thatPDk=0n+1k≥ 2n.•But sincePn/2k=0n+1k= 2nby the preceding lemma,PDk=0n+1k≥ 2nimplies D ≥ n/2.•We now make a critical observation: if every bit stringc ∈ {0, 1}n+1is within Hamming distance D of some bitstring b ∈ Cj, then it immediately follows that some bit stringb ∈ Cjis within Hamming distance D of any bit string a ∈ Cicurrently stored in the medium.•A perfect binary linear channel code of length n + 1 with aminimum Hamming distance of 2D + 1 between codewordsguarantees that every bit string c ∈ {0, 1}n+1is withinHamming distance D of exactly one codeword.•This means that if we can find a collection of 2npairwise-disjoint perfect binary linear codes of length n +