Virtual memory compression: Difference between revisions

Revision as of 16:16, 30 December 2023

Latest revision as of 07:46, 15 July 2025

(21 intermediate revisions by 7 users not shown)

Line 1:

{{Short description|DivakarrajAlgorithms for compressing in-memory data}}

{{Use dmy dates|date=May 2019|cs1-dates=y}}

{{Use list-defined references|date=December 2021}}

Line 10:

==Types==

There are two general types of virtual memory compression : (1) sending compressed pages to a swap file in main memory, possibly with a backing store in auxiliary storage,<ref name ="CaseForCompressedCaching"/><ref name="zram_kernel_org">{{cite web |url="https://www.kernel.org/doc/html/next/admin-guide/blockdev/zram.html" |title="zram: Compressed RAM-based block devices" |last="Gupta" |first="Nitin" |website="docs.kernel.org" |publisher="The kernel development community" |access-date=2023-12-29 }}</ref><ref name="zswap_kernel_org">{{cite web |url="https://www.kernel.org/doc/html/v4.18/vm/zswap.html" |title="zswap" |website="https://www.kernel.org/doc/html/v4.18/vm/zswap.html" |publisher="The kernel development community" |access-date=2023-12-29 }}</ref>, and (2) storing compressed pages side-by-side with uncompressed pages.<ref name="CaseForCompressedCaching"/>

The first type (1) usually uses some sort of [[LZ77_and_LZ78|LZ]] class dictionary compression algorithm combined with [[Entropy_coding|entropy coding]], such as [[Lempel–Ziv–Oberhumer|LZO]] or [[LZ4_(compression_algorithm)|LZ4]] ,<ref name="zswap_kernel_org" /><ref name="zram_kernel_org" />, to compress the pages being swapped out. Once compressed, they are either stored in a swap file in main memory, or written to auxiliary storage, such as a hard disk.<ref name="zswap_kernel_org" /><ref name="zram_kernel_org" /> A two stage process can be used instead wherein there exists both a backing store in auxiliary storage and a swap file in main memory and pages that are evicted from the in-memory swap file are written to the backing store with a greatlymuch decreasedincreased write bandwidth need(eg. duepages/sec) so that writing to the compressionbacking store takes less time. This last scheme leverages the benefits of both previous methods : fast in-memory data access with a greatlarge increase in the total amount of data that can be swapped out and aan decreasedincreased bandwidth requirementin forwriting datapages written(pages/sec) to auxiliary storage.<ref name="zswap_kernel_org" /><ref name="zram_kernel_org" /><ref name ="CaseForCompressedCaching"/>

One example of the most useda class of algorithms for the second type (2), virtual memory compression is the WK (Wilson-Kaplan et. al) class of compression algorithms,. These takestake advantage of in-memory data regularities present in pointers and integers.<ref name ="CaseForCompressedCaching"/><ref name="SIMPSON" /> Specifically, in (the data segment -- the WK algorithms are not suitable for instruction compression<ref name ="CaseForCompressedCaching"/>) target code generated by most high-level programming languages, both integers and pointers are often present in records whose elements are word-aligned. Furthermore, the values stored in integers are usually small. Also pointers close to each other in memory tend to point to locations that are themselves nearby locationsin memory. Additionally, common data patterns such as a word of all zeroes can be encoded in the compressed output by a very small code (two bits in the case of WKdm). Using these data regularities, the WK class of algorithms use a very small dictionary ( 16 entries in the case of [[WKdm]] ) to achieve up to a 50%2:1 compression ratio while achieving much greater speeds and having less overhead than LZ class dictionary compression schemes.<ref name ="CaseForCompressedCaching"/><ref name="SIMPSON" />

==Benefits==

Line 44:

===Prioritization===

In a typical virtual memory implementation, paging happens on a [[least recently used]] basis, potentially causing the compression algorithm to use up CPU cycles dealing with the lowest priority data. Furthermore, program code is usually read-only, and is therefore never paged-out. Instead code is simply discarded, and re-loaded from the program’s auxiliary storage file if needed. In this case the bar for compression is higher, since the I/O cycle it is attempting to eliminate is much shorter, particularly on flash memory devices.

==Compression using quantization==

Accelerator designers exploit quantization to reduce the bitwidth of values and reduce the cost of data movement. However, any value that does not fit in the reduced bitwidth results in an overflow (we refer to these values as outliers). Therefore accelerators use quantization for applications that are tolerant to overflows. In most applications the rate of outliers is low and values are often within a narrow range <ref name="Quant"/> providing the opportunity to exploit quantization in generalpurpose processors. However, a software implementation of quantization in general-purpose processors has three problems. First, the programmer has to manually implement conversions and the additional instructions that quantize and dequantize values, imposing a programmer's effort and performance overhead. Second, to cover outliers, the bitwidth of the quantized values often become greater than or equal to the original values. Third, the programmer has to use standard bitwidth; otherwise, extracting non-standard bitwidth (i.e., 1–7, 9–15, and 17–31) for representing narrow integers exacerbates the overhead of software-based quantization. A hardware support in the memory hierarchy of general-purpose processors for quantization can solve these problems. The hardware support allows representing values by few and flexible numbers of bits and storing outliers in their original format in a separate space, preventing any overflow. It minimizes metadata and the overhead of locating quantized values using a software-hardware interaction that transfers quantization parameters and data layout to hardware. As a result, transparent hardware-based quantization has three advantages over cache compression techniques: (i) less metadata, (ii) higher compression ratio for floating-point values and cache blocks with multiple data types, and (iii) lower overhead for locating the compressed blocks.<ref name="Quant"/>

==History==

Line 53 ⟶ 50:

===Origins===

[[Acorn Computers]]' Unix variant, [[RISC iX]], was supplied as the primary operating system for its R140 workstation released in 1989.<ref name="acornuser198912">{{cite magazine | url=https://archive.org/details/AcornUser089-Dec89/page/n67/mode/2up | magazine=Acorn User | title=Power to the People | last1=Cox | first1=James | date=December 1989 | access-date=6 September 2020 | pages=66-67,69,71}}</ref> RISC iX provided support for demand paging of compressed executable files. However, the principal motivation for providing compressed executable files was to accommodate a complete Unix system in a hard disk of relatively modest size. Compressed data was not paged out to disk under this scheme.<ref name="taunton1991">{{cite journalbook | chapter-url=https://archive.org/details/1991-proceedings-tech-conference-nashville/page/385/mode/1up | journaltitle=Proceedings of the Summer 1991 USENIX Conference, Nashville, TN, USA, June 1991 | publisher=USENIX Association | year=1991 | last1=Taunton | first1=Mark | titlechapter=Compressed Executables: An Exercise in Thinking Small | pages=385–404}}</ref><ref name="taunton1991_unix_internals">{{cite newsgroup | title=Compressed executables | date=22 January 1991 | access-date=10 October 2020 | last1=Taunton | first1=Mark | newsgroup=comp.unix.internals | message-id=[e-mail] | url=https://groups.google.com/d/msg/comp.unix.internals/mGP6CTNdfDI/4NKaA4_rIxgJ}}</ref>

Paul R. Wilson proposed compressed caching of virtual memory pages in 1990, in a paper circulated at the ACM OOPSLA/ECOOP '90 Workshop on Garbage Collection ("Some Issues and Strategies in Heap Management and Memory Hierarchies"), and appearing in ACM SIGPLAN Notices in January 1991.<ref name ="WilsonIssuesStrategies"/>

Line 85 ⟶ 82:

<ref name="PAT-5785474">{{cite patent|country=US|number=5875474|pubdate=1999-02-23|title=Method for caching virtual memory paging and disk input/output requests using off screen video memory|assign1=[[Helix_Software_Company|Helix Software Co., Inc.]]|inventor1-last=Fabrizio|inventor1-first=Daniel|inventor2-last=Spilo|inventor2-first=Michael L.}}</ref>

<ref name="CaseForCompressedCaching">{{cite conference |url=https://www.usenix.org/legacy/event/usenix99/full_papers/wilson/wilson.pdf |title=The Case for Compressed Caching in Virtual Memory Systems |author-last1=Wilson |author-first1=Paul R. |author-last2=Kaplan |author-first2=Scott F. |author-last3=Smaragdakis |author-first3=Yannis |date= 1999-06-06 |conference=USENIX Annual Technical Conference |___location=Monterey, California, USA |pages=101–116}}</ref>

<ref name="SIMPSON">{{cite web |author-last=Simpson |author-first=Matthew |title=Analysis of Compression Algorithms for Program Data |date=2014 |url=http://www.ece.umd.edu/~barua/matt-compress-tr.pdf |access-date=2015-01-09 |pages=64-14}}</ref>

<ref name="RIZZO">{{cite journal |author-last=Rizzo |author-first=Luigi |title=A very fast algorithm for RAM compression |journal=ACM SIGOPS Operating Systems Review |date=1996 |volume=31 |issue=2 |url=http://dl.acm.org/citation.cfm?id=250012 |access-date=2015-01-09 |page=8|doi=10.1145/250007.250012 |s2cid=18563587 |url-access=subscription }}</ref>

<ref name="DENNING">{{cite journal |author-last=Denning |author-first=Peter J. |title=Thrashing: Its causes and prevention |journal=Proceedings AFIPS, Fall Joint Computer Conference |date=1968 |url=http://www.cs.uwaterloo.ca/~brecht/courses/702/Possible-Readings/vm-and-gc/thrashing-denning-afips-1968.pdf |access-date=2015-01-05 |page=918 |volume=33}}</ref>

<ref name="FREEDMAN">{{cite web |author-last=Freedman |author-first=Michael J. |title=The Compression Cache: Virtual Memory Compression for Handheld Computers |url=http://www.cs.princeton.edu/~mfreed//docs/6.033/compression.pdf |date=2000-03-16 |access-date=2015-01-09}}</ref>

<ref name="CWORLD-RD2">{{cite journal |url=https://books.google.com/books?id=BUaIcc6lsdwC&pg=PA56 |title=Mac Memory Booster Gets an Upgrade |journal=[[Computerworld]] |publisher=IDG Enterprise |date=9 September 1996 |issn=0010-4841 |volume=30 |number =37 |page=56 |access-date=2015-01-12}}</ref>

<ref name="PCMAG-HURR-2">{{cite journal |url=https://books.google.com/books?id=7WGv1D0tOVYC&pg=PA48 |title=Hurricane 2.0 Squeezes the Most Memory from Your System |journal=[[PC Magazine]] |date=1996-10-08 |access-date=2015-01-01}}</ref>

<ref name="Quant">{{cite journal|author-last=Lenjani |author-first=Marzieh | url=http://www.cs.virginia.edu/~es9bt/papers/iiswc2019_Quantized.pdf |title=An Overflow-free Quantized Memory Hierarchy in General-purpose Processors |journal=In Proceedings of the IEEE International Symposium on Workload Characterization |date=2019-11-03 |access-date=2020-03-16}}</ref>

<ref name="PCMAG-PERF">{{cite journal |url=https://books.google.com/books?id=8RSHdk84u50C&pg=RA1-PA165 |title=Performance Enhancers |journal=[[PC Magazine]] |date=1997-04-08 |access-date=2015-01-01}}</ref>

<ref name="SoftRAM">{{cite journal |url=https://books.google.com/books?id=XcEKP0ml18EC&pg=PA34 |title=SoftRAM Under Scruitny |journal=[[PC Magazine]] |date=1996-01-23 |access-date=2015-01-01}}</ref>

<ref name="IBM-MXT-PERF">{{cite web |url=http://www.kkant.net/papers/caecw.doc |title=An Evaluation of Memory Compression Alternatives |author-first=Krishna |author-last=Kant |publisher=[[Intel Corporation]] |date=2003-02-01 |access-date=2015-01-01}}</ref>

<ref name="IBM-MXT-NEWS">{{cite web |url=http://www-03.ibm.com/press/us/en/pressrelease/1653.wss |archive-url=https://web.archive.org/web/20130622050529/http://www-03.ibm.com/press/us/en/pressrelease/1653.wss |url-status=dead |archive-date=22 June 2013 |title=IBM Research Breakthrough Doubles Computer Memory Capacity |publisher=[[IBM]] |date=2000-06-26 |access-date=2015-01-01}}</ref>

<ref name="IBM-MXT-PAPERS">{{cite web |url=http://researcher.watson.ibm.com/researcher/view_group_pubs.php?grp=2917 |title=Memory eXpansion Technologies |publisher=[[IBM]] |access-date=2015-01-01}}</ref>

<ref name="zswap-bench">{{cite web |url=https://events.linuxfoundation.org/sites/events/files/slides/tmc_sjennings_linuxcon2013.pdf |title=Transparent Memory Compression in Linux |author-first=Seth |author-last=Jennings |website=linuxfoundation.org |access-date=2015-01-01 |archive-date=2015-01-04 |archive-url=https://web.archive.org/web/20150104214723/https://events.linuxfoundation.org/sites/events/files/slides/tmc_sjennings_linuxcon2013.pdf |url-status=dead }}</ref>

Line 105 ⟶ 101:

<ref name="Arstechnica">{{Cite web|url=https://arstechnica.com/apple/2013/10/os-x-10-9/17/#compressed-memory|title=OS X 10.9 Mavericks: The Ars Technica Review|date=22 October 2013}}</ref>

<ref name="Willson_Usenix">{{Cite web|url=https://www.usenix.org/legacy/publications/library/proceedings/usenix01/cfp/wilson/wilson_html/acc.html|title = The Case for Compressed Caching in Virtual Memory Systems}}</ref>

<ref name="Aul_2015">{{cite web |author-last=Aul |author-first=Gabe |url=httphttps://blogs.windows.com/bloggingwindowswindows-insider/2015/08/18/announcing-windows-10-insider-preview-build-10525/ |title=Announcing Windows 10 Insider Preview Build 10525 |work=Blogging Windows Insider Blog |publisher=[[Microsoft]] |date=2015-08-18 |access-date=20152024-08-1903}}</ref>

<ref name="Paul_1997_NWDOSTIP">{{cite book |title=NWDOS-TIPs &mdash; Tips & Tricks rund um Novell DOS 7, mit Blick auf undokumentierte Details, Bugs und Workarounds |chapter=Kapitel II.18. Mit STACKER Hauptspeicher 'virtuell' verdoppeln… |language=de |trans-title=NWDOS-TIPs &mdash; Tips & tricks for Novell DOS 7, with a focus on undocumented details, bugs and workarounds |trans-chapter=Utilizing STACKER to 'virtually' double main memory… |author-first=Matthias R. |author-last=Paul |date=1997-07-30 |orig-year=1996-04-14 |edition=3 |version=Release 157 |url=http://www.antonis.de/dos/dos-tuts/mpdostip/html/nwdostip.htm |access-date=2012-01-11 |url-status=live |archive-url=https://web.archive.org/web/20161105172944/http://www.antonis.de/dos/dos-tuts/mpdostip/html/nwdostip.htm |archive-date=2016-11-05}}</ref>

}}