| Sonstiges: |
- Nachgewiesen in: USPTO Patent Grants
- Sprachen: English
- Patent Number: 10997,085
- Publication Date: May 04, 2021
- Appl. No: 16/429880
- Application Filed: June 03, 2019
- Assignees: INTERNATIONAL BUSINESS MACHINES CORPORATION (Armonk, NY, US)
- Claim: 1. A compression device for compressing a mapping table in a flash translation layer of a solid state drive, the mapping table comprising mappings between Logical Page Numbers (LPNs) and Physical Page Numbers (PPNs), the compression device comprising: a base PPN table storing at least one entry which includes a base PPN that is common to a plurality of the LPNs; a PPN offset table, separate from the base PPN table, storing a respective offset for each of the mappings; a set of hash functions duplicated for each of the at least one entry in the base PPN table; a bit extension unit, operatively coupled to the PPN offset table, which adds one or more bits to the respective offset in the PPN offset table to provide an extended offset bit; a hash calculator, operatively coupled to the base PPN table, calculating a hash value by using the base PPN and one of the hash functions corresponding to the base PPN; and an exclusive OR unit, operatively coupled to the bit extension unit and the hash calculator, outputting a new PNN for each of different pluralities, including the plurality, of the LPNs by applying an exclusive OR operation to the hash value and the extended offset bit.
- Claim: 2. The compression device of claim 1 , wherein each of the hash functions in the set removes a random bit from a sum of the base PPN and an integer value, and switches a bit order of the sum.
- Claim: 3. The compression device of claim 1 , wherein the set of hash functions scatters an allocable area of the PPNs for each of the LPNs to avoid mapping conflicts.
- Claim: 4. The compression device of claim 1 , wherein the set of hash functions comprise a common permutation there between.
- Claim: 5. The compression device of claim 1 , wherein the common permutation comprises is arbitrarily selected but consistently applied across the set of hash function.
- Claim: 6. The compression device of claim 1 , wherein the respective offset is between the base PPN and the respective new one of the PNNs.
- Claim: 7. The compression device of claim 1 , wherein a number of LPNs capable of using one of the PPNs is identical between all of the PPNs.
- Claim: 8. The compression device of claim 1 , wherein the set of hash functions comprise adding hardware and fixed bit permutation hardware for implementing the set of hash functions.
- Claim: 9. A computer-implemented method for compressing a mapping table in a flash translation layer of a solid state drive, the mapping table comprising mappings between Logical Page Numbers (LPNs) and Physical Page Numbers (PPNs), the compression method comprising: storing, in a base PPN table, at least one entry which includes a base PPN that is mapped to a plurality of the LPNs; storing, in a PPN offset table separate from the base PPN table, a respective offset for each of the mappings; providing a set of hash functions duplicated for each of the at least one entry in the base PPN table; adding, by a bit extension unit operatively coupled to the PPN offset table, one or more bits to an offset value bit in the PPN offset table to provide an extended offset bit; calculating, by a hash calculator operatively coupled to the base PPN table, a hash value by using the base PPN and one of the hash functions corresponding to the base PPN, and outputting, by an exclusive OR unit operatively coupled to the bit extension unit and the hash calculator, a new PNN for each of different pluralities, including the plurality, of the LPNs by applying an exclusive OR operation to the hash value and the extended offset bit.
- Claim: 10. The computer-implemented method of claim 9 , wherein the method is performed responsive to a data read request for the solid state drive.
- Claim: 11. The computer-implemented method of claim 9 , wherein the method is biased to using all available flash pages over less than all of the available flash pages.
- Claim: 12. The computer-implemented method of claim 9 , wherein each of the hash functions in the set removes a random bit from a sum of the base PPN and an integer value, and switches a bit order of the sum.
- Claim: 13. The computer-implemented method of claim 9 , wherein the set of hash functions scatters an allocable area of the PPNs for each of the LPNs to avoid mapping conflicts.
- Claim: 14. The computer-implemented method of claim 9 , wherein the set of hash functions comprise a common permutation there between.
- Claim: 15. The computer-implemented method of claim 9 , wherein the common permutation is arbitrarily selected but consistently applied across the set of hash functions.
- Claim: 16. The computer-implemented method of claim 9 , wherein the respective offset is between the base PPN and the respective new one of the PNNs.
- Claim: 17. The computer-implemented method of claim 9 , wherein a number of LPNs capable of using one of the PPNs is identical between all of the PPNs.
- Claim: 18. The computer-implemented method of claim 9 , wherein the set of hash functions comprise adding hardware and fixed bit permutation hardware for implementing the set of hash functions.
- Claim: 19. A computer program product for compressing a mapping table in a flash translation layer of a solid state drive, the mapping table comprising mappings between Logical Page Numbers (LPNs) and Physical Page Numbers (PPNs), the computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to perform a method comprising: storing, in a base PPN table, at least one entry which includes a base PPN that is mapped to a plurality of the LPNs; storing, in a PPN offset table separate from the base PPN table, a respective offset for each of the mappings; providing a set of hash functions duplicated for each of the at least one entry in the base PPN table; adding, by a bit extension unit operatively coupled to the PPN offset table, one or more bits to an offset value bit in the PPN offset table to provide an extended offset bit; calculating, by a hash calculator operatively coupled to the base PPN table, a hash value by using the base PPN and one of the hash functions corresponding to the base PPN, and outputting, by an exclusive OR unit operatively coupled to the bit extension unit and the hash calculator, a new PNN for each of different pluralities, including the plurality, of the LPNs by applying an exclusive OR operation to the hash value and the extended offset bit.
- Claim: 20. The computer program product of claim 19 , wherein each of the hash functions in the set removes a random bit from a sum of the base PPN and an integer value, and switches a bit order of the sum.
- Patent References Cited: 5754819 May 1998 Lynch ; 2007/0079106 April 2007 Davis ; 2007/0244951 October 2007 Gressel ; 2016/0041905 February 2016 Turner ; 2017/0315927 November 2017 Loh ; 2017/0364446 December 2017 Pham ; 2019/0227947 July 2019 Keppel ; 2020/0310665 October 2020 Hansen ; 103136109 June 2016 ; WO 2014055445 April 2014
- Other References: Hu et al., “PUD-LRU: An Erase-Efficient Write Buffer Management Algorithm for Flash Memory SSD”, 2010 18th Annual IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, Aug. 2010, pp. 69-78. cited by applicant ; Lee et al., “μ-FTL: A Memory-Efficient Flash Translation Layer Supporting Multiple Mapping Granularities”, EMSOFT'08, Oct. 2008, pp. 21-30. cited by applicant ; Zhou et al., “An Efficient Page-level FTL to Optimize Address Translation in Flash Memory”, EuroSys'15, Apr. 2015, pp. 1-16. cited by applicant
- Primary Examiner: Matin, Tasnima
- Attorney, Agent or Firm: Tutunjian & Bitetto, P.C. ; Bluestone, Randall
|
