Patent Description:
Many data processing systems include random access memory (RAM) and non-volatile storage (NVS), with the RAM having less capacity but faster accessibility than the NVS. When software on such a data processing system needs data, the data processing system may copy that data from the NVS to the RAM. And if the RAM is already full, the data processing system may swap one or more pages of old data out of the RAM to the NVS, to make room for the new data.

Or, instead of swapping an old page to NVS, the data processing system may use a software tool to compress the old page and to copy that compressed data to another part of the RAM. For instance, an operating system that is known by the name or trademark of "Linux" (i.e., a "Linux OS") may include a tool known as "zswap" which may be used for that purpose.

However, it takes time to compress data. In addition, some data is not very compressible. Consequently, in at least some cases, a system that uses zswap may perform more poorly than a system that uses the more conventional approach of swapping old pages of data from RAM to NVS.

<CIT> discloses data compression and decompression operations that are performed during or in conjunction with processes for moving data between memory elements of the memory system. A set of operations can be configured to use parameters and perform the operations of an API. The API can support moves between memory having a first access latency, such as memory integrated on the same chip as a processor core, and memory having a second access latency that is longer than the first access latency, such as memory on a different integrated circuit than the processor core.

The invention is defined by an apparatus and a method according to the independent claims.

Features and advantages of the present invention will become apparent from the appended claims, the following detailed description of one or more example embodiments, and the corresponding figures, in which:.

As indicated above, to make room in RAM for a new page data, a data processing system may use a tool such zswap to compress an old page and move that compressed data to another part of the RAM instead of moving the old page to NVS. For purposes of this disclosure, the area or areas of RAM which contain the data that has been "swapped in" so that it can quickly be accessed by software running on the system may be referred to as the "working area" of the RAM or as the "work pool," while the area or areas of RAM for holding data that has been "swapped out" may be referred to as the "swap area" of the RAM or as the "swap pool. " And when the old page is needed again, the system decompresses the compressed data and moves that decompressed data to the work pool. Thus, a data processing system may provide for a memory hierarchy or memory tiers by using a tool like zswap to provide for a work pool and a swap pool in RAM, and to use compression and decompression at the page level when moving data between the work pool and the swap pool. For purposes of this disclosure, since that kind of process involves deciding between at least two different types of destinations for the old page, that kind of process may be referred to in general as "variable-destination swapping.

Also, for purposes of this disclosure, the input data that is to be compressed by a compression accelerator may be referred to as the "source data" or the "source file," and the compressed data that is produced may be referred to as the "output file.

In general, the goal of variable-destination swapping is to increase the effective memory capacity but with much better performance than swapping to a slower tier such as storage media. Consequently, it is important to minimize the latency for compression and decompression while maximizing the compression ratio achieved (and thereby RAM savings). The ideal performance goal is to maximize the memory savings (via page compression) with nearly zero performance impact to applications, relative to a system with a much larger RAM capacity and no compression.

In some systems, the compression and decompression tasks may be performed by software that uses relatively lightweight compression algorithms such as the algorithm known as "Lempel-Ziv-Oberhumer" (LZO). Such an algorithm has the advantage of relatively high speed, but at the cost of relatively low compression. Alternatively, a system may use a compression algorithm such as the one known as "Deflate" to achieve better compression, but at the cost of increased latency for compression and decompression. Deflate is a lossless data compression and decompression process which involves an output file format that uses a combination of Huffman coding and coding based on the data compression algorithm known as LZ77 (or coding based on a derivative or variation of LZ77, such as Lempel-Ziv-Storer-Szymanski (LZSS) coding). However, one way to reduce the latency impact of using such a heavyweight compression algorithm is to use a hardware compression accelerator, instead of a software compression tool, to implement the compression and decompression algorithm. For purposes of this disclosure, the term "accelerator" denotes a hardware compression accelerator. A compression accelerator may also be referred to as a "compression engine" or a "coprocessor.

As part of the variable-destination swapping process, software such as an operating system (OS) or a virtual machine monitor (VMM) may use an accelerator to generate compressed data, based on uncompressed source data. In particular, the software may use the accelerator in that manner as part of the compression phase of a swap-out operation to swap a page of data out of the RAM work pool.

As described in greater detail below, one way to enhance the performance of that compression phase is to implement an early-abort feature based on the characteristics of the data being compressed and based on various predetermined parameters, including software defined parameters. In particular, this disclosure describes a hardware compression accelerator with early-abort circuitry which enables the accelerator to abort the compression process after analyzing only a subset of the source data, based on parameters that are programmed into the hardware accelerator by the software. In other words, the accelerator may decide not to produce compressed data as output, after analyzing only a portion of the source data.

<FIG> is a block diagram depicting an example embodiment of a data processing system <NUM> with technology for early abort of compression acceleration. In particular, data processing system <NUM> includes a compression accelerator <NUM> which includes early-abort circuitry <NUM> with various components that cooperate to provide early-abort functionality. In particular, early-abort circuitry <NUM> causes compression accelerator <NUM> to abort compression operations based on characteristics of the data being compressed and based on various predetermined parameters. In the embodiment of <FIG>, early-abort circuitry <NUM> resides in an integrated circuit along with one or more processing cores <NUM> in a processor package <NUM>. However, in other embodiments, a compression accelerator may reside in a separate integrated circuit in the processor package with one or more processing cores, or a compression accelerator may reside in a separate processor package.

Data processing system <NUM> also include other components in communication with processor package <NUM>, such as RAM <NUM> and NVS <NUM>. RAM <NUM> may be implemented using one or more dynamic RAM (DRAM) modules for example, and NVS may be implemented using one or more hard disk drives or any other suitable non-volatile data storage devices.

NVS <NUM> may also include system software <NUM> that is copied into RAM <NUM> and executed by processing core <NUM> and compression accelerator <NUM>. System software <NUM> includes logic (e.g., executable instructions) to implement variable-destination swapping, including instructions for configuring RAM <NUM> with a work pool <NUM> to hold swapped-in pages and a swap pool <NUM> to hold swapped-out pages - or more specifically, to hold compressed data that has been generated from such pages. The logic to implement variable-destination swapping also includes logic for using compression accelerator <NUM> to perform compression for pages to be swapped out.

For instance, when system software <NUM> determines that an old page of data <NUM> in RAM <NUM> should be swapped out to make room in work pool <NUM> for a new page of data <NUM> to be swapped in to work pool <NUM> from NVS <NUM>, system software <NUM> may use compression accelerator <NUM> to compress the data from old page <NUM> into compressed data <NUM>. And system software <NUM> may then save compressed data <NUM> to swap pool <NUM>. In <FIG>, old page <NUM> is depicted with a dashed outline in NVS <NUM> to focus on a scenario in which old page <NUM> has been swapped in to work pool <NUM>. But system software <NUM> has decided that old page <NUM> should be swapped out to make room for new page <NUM>, as indicated above, and so system software <NUM> has used compression accelerator <NUM> to generate compressed data <NUM>, based on old page <NUM>, and system software <NUM> has saved compressed data <NUM> in swap pool <NUM>. System software <NUM> may then use the space that was occupied by old page <NUM> in work pool <NUM> to swap in new page <NUM>.

Moreover, the logic in system software <NUM> for using compression accelerator <NUM> includes logic for using early abort of compression acceleration, in cooperation with early-abort circuitry <NUM> in compression accelerator <NUM>. As described in greater detail below, if early-abort circuitry <NUM> decides to take an early abort, compression accelerator <NUM> may not return compressed data, but may instead return result data such as a return code to system software <NUM>. For instance, the return code may indicate whether processing is complete, and if so, whether early abort was taken or compressed data was produced. In particular, in one embodiment, system software <NUM> uses an enqueue operation to submit the compression request to compression accelerator <NUM>, the payload of that enqueue operation includes a descriptor with <NUM> bytes to contain various fields, including a field for a completion record (CR), and compression accelerator <NUM> updates the CR with the return code. System software <NUM> may poll that CR to determine whether compression is complete and whether early abort was taken. For instance, a return code of zero may indicate that compression is still in process, a return code of <NUM> may indicate that compression was successfully completed, and any other return code may indicate that early abort was taken.

To prepare for early abort, system software <NUM> may load various early-abort parameters <NUM> into early-abort circuitry <NUM> in compression accelerator <NUM>. As shown in <FIG>, those parameters may include a sample-size parameter and an early-abort threshold parameter. As described in greater detail below, early-abort circuitry <NUM> may also include a table of early-abort sizes <NUM>. System software <NUM> may use any suitable approach to supply early-abort parameters <NUM> to compression accelerator <NUM>. As illustrated, early-abort circuitry <NUM> may store those parameters using various fields in a table of early-abort parameters <NUM>. However, in various embodiments, the "table" of early-abort sizes does not need to be any particular kind of data structure. For instance, the early-abort sizes may be stored in a table, in an array, in a linked list, in a record, in a directory, etc. Accordingly, for purposes of this disclosure, the storage that is used to store the early-abort sizes may be referred to as "early-abort-size storage.

<FIG> presents a table to illustrate an example embodiment of early-abort parameters <NUM> for compression accelerator <NUM>.

The sample size field specifies when compression accelerator <NUM> will perform the check to determine whether or not compression is expected to achieve at least a particular amount of size/space savings. In the embodiment of <FIG>, for instance, system software <NUM> loads a value in the sample size field to select a size from the list consisting of <NUM> bytes, <NUM> bytes, <NUM> bytes, and <NUM> bytes. Thus, early-abort circuitry <NUM> checks as soon as <NUM>, <NUM>, <NUM>, or <NUM> input bytes have been processed. Also, early-abort circuitry <NUM> may only check once, when the specified sample size is reached, as described in greater detail below.

The early-abort threshold field specifies the minimum compression ratio needed to continue with compression. Thus, the early-abort threshold specifies the amount of size/space savings needed to continue with compression. In general, the compression ratio indicates how much smaller the compressed output is, relative to the source data, and it may be computed as input size / output size. For instance, if the compressed output is half the size of the source data, the compression ratio is <NUM>% or <NUM>:<NUM>, and if the compressed output is ¼ the size of the source data, the compression ratio is <NUM>% or <NUM>:<NUM>. Thus, when expressed as percentages, "smaller" compression ratios reflect more effective compression, and "larger" compression ratios reflect less effective compression.

As described in greater detail below, early-abort circuitry <NUM> analyzes a portion of the source data, according to the sample size, and early-abort circuitry <NUM> computes an estimate of the compression ratio that would be achieved by compression accelerator <NUM> for that portion of the source data if compression were not to be aborted. In particular, compression accelerator <NUM> computes various early-abort values <NUM> to determine whether or not to take early abort. As illustrated in <FIG> and described in greater detail below with regard to <FIG>, those values may include (a) a portion size to indicate how many bytes from the source data are being used to estimate the compression ratio and (b) an estimated compressed size to indicate how big (i.e., how many bytes) the corresponding compressed data would be if compression were not to be aborted. And early-abort circuitry <NUM> may use that portion size and that estimated compressed size to compute the estimated compression ratio. In addition, early-abort circuitry <NUM> may perform that analysis of the source data in parallel with the actual compression operations on that source data by compression accelerator <NUM>.

If the estimated compression ratio is greater than the early-abort threshold, compression accelerator <NUM> will take an early abort. In the embodiment of <FIG>, for instance, system software <NUM> loads a value into the early-abort threshold field to select a minimum compression ratio from the list consisting of <NUM>/<NUM>, <NUM>/<NUM>, <NUM>/<NUM>, <NUM>/<NUM>, <NUM>/<NUM>, <NUM>/<NUM>, and <NUM>/<NUM>. Thus, the early-abort threshold can be set to require a compression ratio of at least <NUM>%, at least <NUM>%, at least <NUM>%, at least <NUM>%, at least <NUM>%, at least <NUM>%, or at least <NUM>%, respectively, as described in greater detail below with regard to <FIG>.

In addition, the early-abort threshold also serves as a flag to enable or disable early-abort functionality. In particular, system software <NUM> can set the early-abort threshold field to zero to disable early aborts.

As illustrated, in the embodiment of <FIG>, early-abort parameters <NUM> also include fields for additional parameters affecting compression, such as one or more parameters pertaining to an analytics engine control and state (EACS) structure. The EACS structure may also be referred to simply as "AECS.

The inputs to compression accelerator <NUM> from system software <NUM> include (a) the data to be compressed (i.e., the source data) and (b) parameters for controlling the compression process, such as the sample size and early-abort threshold parameters. System software <NUM> may also supply other input parameters, such as a parameter to select a compress version, a parameter pertaining to statistics, etc..

The outputs from compression accelerator <NUM> to system software <NUM> include control and state information. The AECS may serve different roles at different times, including a state role and a control role. In the "control" role, system software <NUM> uses the AECS to input parameters that do not fit in the descriptor, such as the Huffman tables to be used in the compression. In the state role, the AECS is used to pass information from job to job in the case where a large job is broken into a series of smaller jobs (e.g., to compress a <NUM>-megabyte (MB) file by processing it <NUM> kilobytes (KB) at a time). In the embodiment of <FIG>, system software <NUM> may use the control-size flag to indicate whether the maximum size of the AECS is <NUM> bytes or <NUM> bytes.

<FIG> presents a flowchart of an example embodiment of a process to provide for early abort of compression acceleration. That process is described in the context of data processing system <NUM> from <FIG>. As shown at block <NUM>, that process may begin with compression accelerator <NUM> receiving a request for compression acceleration from system software <NUM>. For instance, in an example scenario, system software <NUM> is using compression accelerator <NUM> to compress old page <NUM> in connection with swapping out old page <NUM>.

In response to the request for compression, compression accelerator <NUM> checks the parameters from that request to determine whether the request has enabled or disabled early abort. If system software <NUM> has requested for early abort to be disabled, compression accelerator <NUM> may generate compressed data (e.g., compressed data <NUM>) based on the complete source data (e.g., old page <NUM>), as shown at block <NUM>. As shown at block <NUM>, compression accelerator <NUM> may then return results to system software <NUM>. For instance, compression accelerator <NUM> may set a return code to indicate that compression has been completed without abort. The process may then end.

However, referring again to block <NUM>, if early abort is enabled, compression accelerator <NUM> may use early-abort circuitry <NUM> to determine whether to compress the entire source data or to abort the compression process without compressing the entire source data. To make that determination, early-abort circuitry <NUM> starts generating output tokens, based on the source data, as shown at block <NUM>. Each output token is either a literal or a back reference, as described in greater detail below. As shown at block <NUM>, after generating each output token, early-abort circuitry <NUM> determines whether the sample size has been reached. If the number of input bytes processed is not greater than or equal to the sample size, the process returns to block <NUM> and early-abort circuitry <NUM> continues to generate output tokens until the sample size has been reached.

As indicated above, the number of bytes to be processed from the source data and the early-abort threshold are controlled by two fields in early-abort parameters <NUM>: the sample-size field and the early-abort threshold field.

When the sample size has been reached, the process passes to block <NUM>, with early-abort circuitry <NUM> computing an estimate of the compressed size for the portion of the source data for which tokens were generated. In particular, early-abort circuitry <NUM> computes that estimate by (a) summing or counting the number of literals among the output tokens, (b) multiplying the number of back references by <NUM>, and (c) adding those two results together. In other words, the estimate of the compressed size is the number of literals plus twice the number of references. Thus, early-abort circuitry <NUM> approximates the size of the output by assuming that each literal will take one byte, assuming that each reference will take two bytes, and disregarding the block header. One result or attribute of this technique or heuristic for estimating the output size is that the estimated size can never be greater than the input size, and it can only be equal if no matches were found, since the minimum match length for Deflate is three, and early-abort circuitry <NUM> uses an estimate of two compressed bytes.

However, in other embodiments, the early-abort circuitry may use a different formula to estimate the compressed size for the portion of the source data for which tokens were generated. For instance, if the mode of operation is compression using fixed or canned Huffman codes, which are known at the start of the operation, then the early-abort circuitry can use a more precise bit-level estimate using the symbol bit lengths for each literal or reference. Also, the early-abort circuitry may use a bit-level estimate based on suitable canned code tables that are loaded into the state of the compressor.

As shown at block <NUM>, early-abort circuitry <NUM> then looks up the requested threshold size in table of early-abort sizes <NUM>, based on the specified sample size and the specified early-abort threshold. For instance, if the sample size is <NUM> bytes and the early-abort threshold is <NUM>/<NUM>, early-abort circuitry <NUM> retrieves a threshold size of <NUM> bytes from table <NUM>.

As shown at block <NUM>, early-abort circuitry <NUM> then determines whether (a) the estimated output size (i.e., the estimated size for the portion of the source data for which tokens were generated) is greater than the threshold size. For instance, in the scenario above with a sample size of <NUM> and an early-abort threshold of <NUM>/<NUM>, early-abort circuitry <NUM> determines whether the estimated output size is greater than <NUM> bytes. If the estimated output size is greater than the threshold size (or, in another embodiment, greater than or equal to the threshold size), early-abort circuitry <NUM> aborts compression operations without processing the rest of the source data, as shown at block <NUM>. And as shown at block <NUM>, compression accelerator <NUM> reports that decision to system software <NUM>. For instance, compression accelerator <NUM> may set a return code to indicate that compression has been aborted.

However, if the estimated output size is less than or equal to the threshold size (or, in another embodiment, less than the threshold size), early-abort circuitry <NUM> proceeds to compress the entire source data and generate compressed data <NUM>, as shown at block <NUM>. And compression accelerator <NUM> then reports the results to system software <NUM>, as shown at block <NUM>. For instance, compression accelerator <NUM> may set a return code to indicate that compression has been completed without abort. The process of <FIG> may then end. Thus, early-abort circuitry <NUM> causes compression accelerator <NUM> to abort a compression request if the estimated size for the output file (or a portion of the output file) reflects an unacceptably small amount of compression.

In one embodiment, early-abort circuitry <NUM> compares the threshold against the input bytes coming to the Deflate compressor, i.e., after the optional zero-compress precompression step has occurred.

Also, in other embodiments, early-abort circuitry may use other types of schedules to perform operations such as determining the estimate of compressed size and determining whether that estimated size is greater than the threshold size. For instance, early-abort circuitry may be configured to check after every "N" bytes (i.e., after N bytes, after 2N bytes, after 3N bytes, etc.) or to check after every token after crossing the N input-byte threshold. The early-abort circuitry may thus check multiple times to determine whether the estimated sizes for different portions of the output file reflect an acceptable amount of compression, and the compression accelerator may complete a compression request only if the early-abort circuitry does not detect an unacceptably small amount of compression in any of those checks.

By using the process described above, compression accelerator <NUM> is able to abort the compression process after analyzing only a subset of the source data. Compression accelerator <NUM> is thereby able to produce results more quickly than an accelerator that does not support early abort. In other words, an advantage of taking an early abort is that, if the compression is not expected to achieve a desired level of compression, the accelerator can notify the software sooner, relative to an accelerator without early-abort circuitry, and thus the latency of the process can be reduced, relative to a process that completes compression before determining whether the compression ratio is acceptable.

As indicated above in connection with block <NUM> of <FIG>, each output token is either a literal or a back reference. In one embodiment, those tokens are the output of the matching portion of a Deflate compression process. That output can be considered a stream of things, and those things may be referred to as in general as token. A token can represent either a literal or a back reference. A back reference may also be referred to simply as a "reference" or a "match. " A match consists of a length and distance. In the decompression process, a literal token means to output that literal byte to the output stream. A match token means to copy the specified number of bytes from the specified distance back to the output stream.

In particular, the literals and lengths may be encoded to form one Huffman alphabet (which may be referred to as the "literal and length codes" or "LL codes"), and the distances may be encoded to form another (which may be referred to as the "distance codes" or "D codes"). The decompressor first decodes an LL symbol. If it is a literal, it outputs the specified byte and looks for another LL symbol. If it is a length, it decodes the next input bits as a D symbol, processes the length/distance, and then processes the next bits as an LL symbol. Thus, the body of the Deflate block consists of mixed LL and D codes. The body can be thought of as being a mixture of either (a) a literal code (i.e., an LL code representing a literal) or (b) a length/distance pair (i.e., an LL code representing a length followed by a D code). Each literal may be considered to be one token, and each length/distance pair may be considered to be one token.

Thus, compression accelerator <NUM> provides for early abortion of the compression process, thereby reducing the latency experienced by system software <NUM> when processing source data.

In addition, early-abort may be used to increase the performance of other types of processes or application, in addition to the page swapping application. For instance, when the source data is encrypted, compressing that encrypted data may not save much space. Such source data may be referred to as relatively incompressible. A compression accelerator with early-abort circuitry may be used to quickly determine whether a file or block of source data is relatively incompressible. Accordingly, storage applications and communication applications are other types of application that can use early abort to decrease latency and increase system efficiency. The technology described herein may be used by any application that is sensitive to compression latency where there is an expectation that a non-trivial number of compression jobs may be for data that is incompressible or minimally compressible.

By contrast, a data processing system without early-abort capabilities might compress the complete source data, check the size of the compressed output, and discard the compressed output when it is too large. That approach involves increased latency and decreased system efficiency, relative to an approach that uses early abort.

In addition, the early-abort circuitry allows the system software the adjust aspects of the early-abort process such as how big a portion of the source data is to be used to estimate the compression ratio and the minimum compression ratio desired to continue with compression. Thus, the system software can adjust the parameters for different types of data sets.

<FIG> is a block diagram of a system <NUM> according to one or more embodiments. The system <NUM> may include one or more processors <NUM>, <NUM>, which are coupled to a controller hub <NUM>. In one embodiment, the controller hub <NUM> includes a graphics memory controller hub (GMCH) <NUM> and an Input/Output Hub (IOH) <NUM> (which may be on separate chips); the GMCH <NUM> includes a memory controller to control operations within a coupled memory and a graphics controller to which are coupled memory <NUM> and a coprocessor <NUM>; the IOH <NUM> couples input/output (I/O) devices <NUM> to the GMCH <NUM>. Alternatively, one or both of the memory and graphics controllers are integrated within the processor, the memory <NUM> and the coprocessor <NUM> are coupled directly to the processor <NUM>, and the controller hub <NUM> is in a single chip with the IOH <NUM>.

The optional nature of additional processors <NUM> is denoted in <FIG> with broken lines. Each processor <NUM>, <NUM> may include one or more processing cores and may be some version of processor <NUM>.

The memory <NUM> may be, for example, dynamic random-access memory (DRAM), phase change memory (PCM), or a combination of the two. For at least one embodiment, the controller hub <NUM> communicates with the processor(s) <NUM>, <NUM> via a multi-drop bus, such as a frontside bus (FSB), point-to-point interface such as QuickPath Interconnect (QPI), or similar connection <NUM>.

In one embodiment, the coprocessor <NUM> is a special-purpose processor, such as, for example, a high-throughput MIC processor, a network or communication processor, a compression engine, graphics processing unit (GPU), a general purpose GPU (GPGPU), an embedded processor, a BW accelerator, or the like. In one embodiment, controller hub <NUM> may include an integrated graphics accelerator.

In one embodiment, the processor <NUM> executes instructions that control data processing operations of a general type. Embedded within the instructions may be coprocessor instructions. The processor <NUM> recognizes these coprocessor instructions as being of a type that should be executed by the attached coprocessor <NUM>. Accordingly, the processor <NUM> issues these coprocessor instructions (or control signals representing coprocessor instructions) on a coprocessor bus or other interconnect, to coprocessor <NUM>. Coprocessor(s) <NUM> accept and execute the received coprocessor instructions.

<FIG> is a block diagram of a first more specific exemplary system <NUM> according to one or more embodiments. As shown in <FIG>, multiprocessor system <NUM> is a point-to-point interconnect system, and includes a first processor <NUM> and a second processor <NUM> coupled via a point-to-point interconnect <NUM>. Each of processors <NUM> and <NUM> may be some version of processor <NUM>. In one embodiment, processors <NUM> and <NUM> are respectively processors <NUM> and <NUM>, while coprocessor <NUM> is coprocessor <NUM>. In another embodiment, processors <NUM> and <NUM> are respectively processor <NUM> and coprocessor <NUM>. Alternatively, processor <NUM> may be a BW accelerator.

Processors <NUM> and <NUM> are shown including integrated memory controller (IMC) units <NUM> and <NUM>, respectively. Processor <NUM> also includes as part of its bus controller unit's point-to-point (P-P) interfaces <NUM> and <NUM>; similarly, second processor <NUM> includes P-P interfaces <NUM> and <NUM>. Processors <NUM>, <NUM> may exchange information via a P-P interface <NUM> using P-P interface circuits <NUM>, <NUM>. As shown in <FIG>, IMCs <NUM> and <NUM> couple the processors to respective memories, namely a memory <NUM> and a memory <NUM>, which may be portions of main memory locally attached to the respective processors.

Processors <NUM>, <NUM> may each exchange information with a chipset <NUM> via individual P-P interfaces <NUM>, <NUM> using point to point interface circuits <NUM>, <NUM>, <NUM>, <NUM>. Chipset <NUM> may optionally exchange information with the coprocessor <NUM> via a high-performance interface <NUM>. In one embodiment, the coprocessor <NUM> is a special-purpose processor, such as, for example, a high-throughput MIC processor, a network or communication processor, compression engine, graphics processor, GPGPU, embedded processor, or the like.

As shown in <FIG>, various I/O devices <NUM> may be coupled to first bus <NUM>, along with a bus bridge <NUM> which couples first bus <NUM> to a second bus <NUM>. In one embodiment, one or more additional processors <NUM>, such as coprocessors, high-throughput MIC processors, GPGPUs, accelerators (such as, e.g., graphics accelerators or digital signal processing (DSP) units), field programmable gate arrays (FPGAs), or any other processor, are coupled to first bus <NUM>. In one embodiment, second bus <NUM> may be a low pin count (LPC) bus. Various devices may be coupled to a second bus <NUM> including, for example, a keyboard and/or mouse <NUM>, communication devices <NUM> and a storage unit <NUM> such as a disk drive or other mass storage device which may include instructions/code and data <NUM>, in one embodiment. Further, an audio I/O <NUM> may be coupled to the second bus <NUM>. Note that other architectures are possible. For example, instead of the point-to-point architecture of <FIG>, a system may implement a multi-drop bus or other such architecture.

<FIG> is a block diagram of a second more specific exemplary system <NUM> in accordance with on one or more embodiments. Certain aspects of <FIG> have been omitted from <FIG> in order to avoid obscuring other aspects of <FIG>.

<FIG> is a block diagram of a system on a chip (SoC) <NUM> according to one or more embodiments. Dashed lined boxes are optional features on more advanced SoCs. In <FIG>, an interconnect unit(s) <NUM> is coupled to: an application processor <NUM> which includes a set of one or more cores 1102A-N (including constituent cache units 1104A-N) and shared cache unit(s) <NUM>; a system agent unit <NUM>; a bus controller unit(s) <NUM>; an integrated memory controller unit(s) <NUM>; a set or one or more coprocessors <NUM> which may include integrated graphics logic, an image processor, an audio processor, a video processor, and/or a BW accelerator; a static random-access memory (SRAM) unit <NUM>; a direct memory access (DMA) unit <NUM>; and a display unit <NUM> for coupling to one or more external displays. In one embodiment, the coprocessor(s) <NUM> include a special-purpose processor, such as, for example, a network or communication processor, compression engine, GPGPU, a high-throughput MIC processor, embedded processor, security processor, or the like.

Example A1 is a processor package comprising an integrated circuit and a compression accelerator in the integrated circuit. The compression accelerator is to process a request to compress source data into an output file. The processor package also comprises early-abort circuitry in the compression accelerator to provide for early abort of compression operations. In particular, to provide for early abort of compression operations comprises (a) using a predetermined sample size to compute an estimated size for a portion of the output file, wherein the sample size specifies how much of the source data is to be analyzed before computing the estimated size for the portion of the output file; (b) determining whether the estimated size for the portion of the output file reflects an acceptable amount of compression, based on a predetermined early-abort threshold; and (c) causing the compression accelerator to abort the request if the estimated size for the portion of the output file does not reflect the acceptable amount of compression.

Example A2 is a processor package according to Example A1, wherein to process a request to compress source data into an output file comprises completing the request if the early-abort circuitry does not predict an unacceptably small amount of compression.

Example A3 is a processor package according to Example A1, wherein the compression accelerator is to allow software to specify the sample size and the early-abort threshold. Example A3 may also include the features of Example A2.

Example A4 is a processor package according to Example A1, wherein the operation of using the predetermined sample size to compute the estimated size for the portion of the output file comprises (a) analyzing a portion of the source data to determine a number of literals and a number of back references that could be used to compress the portion of the source data; and (b) determining the estimated size for the portion of the output file based on the determined number of literals and the determined number of back references. Example A4 may also include the features of any one or more of Examples A2-A3.

Example A5 is a processor package according to Example A4, wherein the operation of determining the estimated size for the portion of the output file based on the determined number of literals and the determined number of back references comprises computing the estimated size for the portion of the output file as one byte for each literal and two bytes for each back reference.

Example A6 is a processor package according to Example A4, wherein the operation of analyzing the portion of the source data to determine the number of literals and the number of back references that could be used to compress the portion of the source data comprises determining the number of literals and the number of back references that would be used to compress the portion of the source data according to a Deflate compression algorithm. Example A6 may also include the features of Example A5.

Example B1 is a data processing system comprising a processing core to execute software and a compression accelerator in communication with the processing core, the compression accelerator to process a request from the software to compress source data into an output file. In particular, to process a request to compress source data into an output file comprises (a) using a predetermined sample size to compute an estimated size for a portion of the output file, wherein the sample size specifies how much of the source data is to be analyzed before computing the estimated size for the portion of the output file; (b) determining whether the estimated size for the portion of the output file reflects an acceptable amount of compression, based on a predetermined early-abort threshold; and (c) aborting the request if the estimated size for the portion of the output file does not reflect the acceptable amount of compression.

Example B2 is a data processing system according to Example B1, wherein the compression accelerator comprises early-abort circuitry, and to process a request to compress source data into an output file further comprises completing the request if the early-abort circuitry does not predict an unacceptably small amount of compression.

Example B3 is a data processing system according to Example B1, wherein the data processing system comprises an integrated circuit that comprises the processing core and the compression accelerator. Example B3 may also include the features of Example B2.

Example B4 is a data processing system according to Example B1, wherein the compression accelerator is to allow the software to specify the sample size and the early-abort threshold. Example B4 may also include the features of any one or more of Examples B2-B3.

Example B5 is a data processing system according to Example B1, wherein the operation of using the predetermined sample size to compute the estimated size for the portion of the output file comprises (a) analyzing a portion of the source data to determine a number of literals and a number of back references that could be used to compress the portion of the source data, and (b) determining the estimated size for the portion of the output file based on the determined number of literals and the determined number of back references. Example B5 may also include the features of any one or more of Examples B2-B4.

Example B6 is a data processing system according to Example B5, wherein the operation of determining the estimated size for the portion of the output file based on the determined number of literals and the determined number of back references comprises computing the estimated size for the portion of the output file as one byte for each literal and two bytes for each back reference.

Example B7 is a data processing system according to Example B5, wherein the operation of analyzing the portion of the source data to determine the number of literals and the number of back references that could be used to compress the portion of the source data comprises determining the number of literals and the number of back references that would be used to compress the portion of the source data according to a Deflate compression algorithm. Example B7 may also include the features of Example B6.

Example B8 is a data processing system according to Example B1, further comprising NVS in communication with the processor, wherein the NVS comprises the software, and wherein the software is to specify the sample size and the early-abort threshold. Example B8 may also include the features of any one or more of Examples B2-B7.

Example B9 is a data processing system according to Example B8, further comprising RAM in communication with the processing core. Also, the software is further to (a) establish a work pool and a swap pool in the RAM; (b) store an old page in the work pool, wherein the old page comprises the source data; and (c) in connection with swapping out the old page from the work pool, (i) determine whether or not the compression accelerator aborted the request, and (ii) in response to determining that the compression accelerator did not abort the request, save the output file to the swap pool.

Example C1 is an apparatus comprising a machine-accessible medium, and instructions in the machine-accessible medium which, when executed by a data processing system with a compression accelerator with early-abort circuitry, cause the data processing system to use the compression accelerator to process a request from the software to compress source data into an output file. In particular, to process a request to compress source data into an output file comprises (a) using a predetermined sample size to compute an estimated size for a portion of the output file, wherein the sample size specifies how much of the source data is to be analyzed before computing the estimated size for the portion of the output file; (b) determining whether the estimated size for the portion of the output file reflects an acceptable amount of compression, based on a predetermined early-abort threshold; and (c) aborting the request if the estimated size for the portion of the output file does not reflect the acceptable amount of compression.

Example C2 is an apparatus according to Example C1, wherein the instruction are to specify the sample size and the early-abort threshold.

Example C3 is an apparatus according to Example C1, wherein the operation of using the predetermined sample size to compute the estimated size for the portion of the output file comprises (a) analyzing a portion of the source data to determine a number of literals and a number of back references that could be used to compress the portion of the source data; and (b) determining the estimated size for the portion of the output file based on the determined number of literals and the determined number of back references. Example C3 may also include the features of Example C2.

Example C4 is an apparatus according to Example C3, wherein the operation of determining the estimated size for the portion of the output file based on the determined number of literals and the determined number of back references comprises computing the estimated size for the portion of the output file as one byte for each literal and two bytes for each back reference.

Example C5 is an apparatus according to Example C3, wherein the operation of analyzing the portion of the source data to determine the number of literals and the number of back references that could be used to compress the portion of the source data comprises determining the number of literals and the number of back references that would be used to compress the portion of the source data according to a Deflate compression algorithm. Example C5 may also include the features of Example C4.

Example C6 is an apparatus according to Example C1, wherein to process a request to compress source data into an output file comprises completing the request if the early-abort circuitry does not predict an unacceptably small amount of compression. Also, the instructions, when executed, are further to, after completion of the request, save the output file to a swap pool in the RAM in the data processing system, in connection with swapping out the old page from a work pool in the RAM.

In light of the principles and example embodiments described in the present disclosure by text and/or illustration, one with skill in the art will recognize that the described embodiments can be modified in arrangement and detail without departing from the principles described herein. Furthermore, this disclosure uses expressions such as "one embodiment" and "another embodiment" to describe embodiment possibilities. However, those expressions are not intended to limit the scope of this disclosure to particular embodiment configurations. For instance, those expressions may reference the same embodiment or different embodiments, and those different embodiments are combinable into other embodiments.

Additionally, the present teachings may be used to advantage in many different kinds of data processing systems. Such data processing systems may include, without limitation, mainframe computers, mini-computers, supercomputers, high-performance computing systems, computing clusters, distributed computing systems, personal computers (PCs), workstations, servers, client-server systems, portable computers, laptop computers, tablet computers, entertainment devices, audio devices, video devices, audio/video devices (e.g., televisions and set-top boxes), handheld devices, smartphones, telephones, personal digital assistants (PDAs), wearable devices, vehicular processing systems, accelerators, systems on a chip (SoCs), and other devices for processing and/or transmitting information. Accordingly, unless explicitly specified otherwise or required by the context, references to any particular type of data processing system (e.g., a PC) should be understood as encompassing other types of data processing systems, as well. A data processing system may also be referred to as an "apparatus. " The components of a data processing system may also be referred to as "apparatus.

Also, according to the present disclosure, a device may include instructions and other data which, when accessed by a processor, cause the device to perform particular operations. For purposes of this disclosure, instructions or other data which cause a device to perform operations may be referred to in general as "software" or "control logic". Software that is used during a boot process may be referred to as "firmware. " Software that is stored in non-volatile memory may also be referred to as "firmware. " Software may be organized using any suitable structure or combination of structures. Accordingly, terms like program and module may be used in general to cover a broad range of software constructs, including, without limitation, application programs, subprograms, routines, functions, procedures, drivers, libraries, data structures, processes, microcode, and other types of software components. Also, it should be understood that a software module may include more than one component, and those components may cooperate to complete the operations of the module. Also, the operations which the software causes a device to perform may include creating an operating context, instantiating a particular data structure, etc. Also, embodiments may include software that is implemented using any suitable operating environment and programming language (or combination of operating environments and programming languages). For example, program code may be implemented in a compiled language, in an interpreted language, in a procedural language, in an object-oriented language, in assembly language, in machine language, or in any other suitable language.

A medium which contains data and which allows another component to obtain that data may be referred to as a "machine-accessible medium" or a "machine-readable medium. " Accordingly, embodiments may include machine-readable media containing instructions for performing some or all of the operations described herein. Such media may be referred to in general as "apparatus" and in particular as "program products. " In one embodiment, software for multiple components may be stored in one machine-readable medium. In other embodiments, two or more machine-readable media may be used to store the software for one or more components. For instance, instructions for one component may be stored in one medium, and instructions another component may be stored in another medium. Or a portion of the instructions for one component may be stored in one medium, and the rest of the instructions for that component (as well instructions for other components), may be stored in one or more other media. Similarly, software that is described above as residing on a particular device in one embodiment may, in other embodiments, reside on one or more other devices. For instance, in a distributed environment, some software may be stored locally, and some may be stored remotely. The machine-readable media for some embodiments may include, without limitation, tangible non-transitory storage components such as magnetic disks, optical disks, magneto-optical disks, dynamic RAM, static RAM, non-volatile RAM (NVRAM), read-only memory (ROM), solid state drives (SSDs), phase change memory (PCM), etc., as well as processors, controllers, and other components that include data storage facilities. For purposes of this disclosure, the term "ROM" may be used in general to refer to non-volatile memory devices such as erasable programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), flash ROM, flash memory, etc..

Also, operations that are described as being performed on one particular device in one embodiment may, in other embodiments, be performed by one or more other devices. Also, although one or more example processes have been described with regard to particular operations performed in a particular sequence, numerous modifications could be applied to those processes to derive numerous alternative embodiments of the present invention. For example, alternative embodiments may include processes that use fewer than all of the disclosed operations, processes that use additional operations, and processes in which the individual operations disclosed herein are combined, subdivided, rearranged, or otherwise altered.

It should also be understood that the hardware and software components depicted herein represent functional elements that are reasonably self-contained so that each can be designed, constructed, or updated substantially independently of the others. In alternative embodiments, components may be implemented as hardware, software, or combinations of hardware and software for providing the functionality described and illustrated herein. For instance, in some embodiments, some or all of the control logic for implementing the described functionality may be implemented in hardware logic circuitry, such as with an application-specific integrated circuit (ASIC) or with a programmable gate array (PGA). Similarly, some or all of the control logic may be implemented as microcode in an integrated circuit chip. Also, terms such as "circuit" and "circuitry" may be used interchangeably herein. Those terms and terms like "logic" may be used to refer to analog circuitry, digital circuitry, processor circuitry, microcontroller circuitry, hardware logic circuitry, hard-wired circuitry, programmable circuitry, state machine circuitry, any other type of hardware component, or any suitable combination of hardware components.

Also, unless expressly specified otherwise, components that are described as being coupled to each other, in communication with each other, responsive to each other, or the like need not be in continuous communication with each other and need not be directly coupled to each other. Likewise, when one component is described as receiving data from or sending data to another component, that data may be sent or received through one or more intermediate components, unless expressly specified otherwise. In addition, some components of the data processing system may be implemented as adapter cards with interfaces (e.g., a connector) for communicating with a bus. Alternatively, devices or components may be implemented as embedded controllers, using components such as programmable or non-programmable logic devices or arrays, ASICs, embedded computers, smart cards, and the like. For purposes of this disclosure, the term "bus" includes pathways that may be shared by more than two devices, as well as point-to-point pathways. Similarly, terms such as "line," "pin," etc. should be understood as referring to a wire, a set of wires, or any other suitable conductor or set of conductors. For instance, a bus may include one or more serial links, a serial link may include one or more lanes, a lane may be composed of one or more differential signaling pairs, and the changing characteristics of the electricity that those conductors are carrying may be referred to as "signals. " Also, for purpose of this disclosure, the term "processor" denotes a hardware component that is capable of executing software. For instance, a processor may be implemented as a central processing unit (CPU) or as any other suitable type of processing element. A CPU may include one or more processing cores. A processor package may also be referred to as a "processor. " And a device may include one or more processors.

Other embodiments may be implemented in data and may be stored on a non-transitory storage medium, which if used by at least one machine, causes the at least one machine to fabricate at least one integrated circuit to perform one or more operations according to the present disclosure. Still further embodiments may be implemented in a computer-readable storage medium including information that, when manufactured into an SoC or other processor, is to configure the SoC or other processor to perform one or more operations according to the present disclosure. One or more aspects of at least one embodiment may be implemented by representative instructions, stored on a machine-readable medium, which represent various logic units within the processor, and which, when read by a machine, cause the machine to fabricate logic units to perform the techniques described herein. The instructions representing various logic units may be referred to as "IP cores," and they may be stored on a tangible, machine-readable medium and supplied to various customers or manufacturing facilities to load into the fabrication machines that make the logic units or the processor. One or more aspects of at least one embodiment may include machine-readable media containing instructions or design data which defines structures, circuits, apparatuses, processors and/or system features described herein. For instance, design data may be formatted in a hardware description language (HDL).

In view of the wide variety of useful permutations that may be readily derived from the example embodiments described herein, this detailed description is intended to be illustrative only, and should not be construed as limiting the scope of coverage.

Claim 1:
An apparatus comprising:
a processor core (<NUM>); and
a compression accelerator (<NUM>) coupled to the processor core, characterized in that the compression accelerator (<NUM>) is to include early abort circuitry (<NUM>) to allow for the compression accelerator (<NUM>) to perform an early abort of a compression operation before the compression has completed, wherein the early abort is to be configured at least based on one or more parameters (<NUM>) and an estimate of a compressed size of an output from the compression accelerator (<NUM>), wherein at least one of the one or more parameters (<NUM>) is programmed into the hardware accelerator (<NUM>) by a software.