Patent Description:
Database management systems (and other storage systems) may use data encoding to compress the stored data into the storage devices. To save storage space, data may be stored in a compressed manner. Compressing the data generally involves storing the data in a format that differs in some way from the original data, while still representing the original data (for lossless compression) or something close to the original data (for lossy compression). While some operations may be run on the encoded data, running different database operations may require the data to be decoded first. Performing this decoding in the host processor may reduce the ability of the host processor to execute other commands.

A need remains to improve host processor performance when data is dictionary encoded.

<CIT> discloses: A data encoding system includes a non-transitory memory, a processor, a digital-to-analog converter (DAC) and a transmitter. The non-transitory memory stores a predetermined file size threshold. The processor is in operable communication with the memory, and is configured to receive data. The processor detects a file size associated with the data. When the file size is below the predetermined file size threshold, the processor compresses the data using a variable length codeword (VLC) encoder. When the file size is not below the predetermined file size threshold, the processor compresses the data, using a hash table algorithm. The DAC is configured to receive a digital representation of the compressed data from the processor and convert the digital representation of the compressed data into an analog representation of the compressed data. The transmitter is coupled to the DAC and configured to transmit the analog representation of the compressed data.

<CIT> discloses: An improved multi-codebook phase-in coding process for coding electronic data wherein for each received electronic input data, the coding process detects whether that input data exceeds a current coding maximum, then selecting a codebook coding method from one or more codebook coding methods in response to detecting whether that input data exceeds the current coding maximum, and then encoding that input data in accordance to the selected codebook coding method to generate a coded output data. A corresponding codebook indicator is inserted into a generated coded output data stream to indicate which codebook method to use to decode the coded output data. During decoding, the decoding process detects for a decode method indicator associated with each encoded input data, and decodes in accordance to a decode method corresponding to the detected decode method indicator to generate a decoded output data.

<CIT> discloses: Blocks of data are losslessly compressed and decompressed using a nested hierarchy of fixed phrase length dictionaries. The dictionaries may be built using information related to the manner in which data is commonly organized in computer systems for convenient retrieval, processing, and storage. This results in low cost designs that give significant compression.

Specific embodiments are defined in the dependent claims. Embodiments of the disclosure include an accelerator associated with a storage device. The accelerator may perform decoding of data that is stored in a dictionary encoded format. After decoding, the decoded data may be written back to the storage device or to Dynamic Random Access Memory (DRAM).

The drawings described below are examples of how embodiments of the disclosure may be implemented, and are not intended to limit embodiments of the disclosure. Individual embodiments of the disclosure may include elements not shown in particular figures and/or may omit elements shown in particular figures. The drawings are intended to provide illustration and may not be to scale.

Reference will now be made in detail to embodiments of the disclosure, examples of which are illustrated in the accompanying drawings. In the following detailed description, numerous specific details are set forth to enable a thorough understanding of the disclosure. It should be understood, however, that persons having ordinary skill in the art may practice the disclosure without these specific details.

For example, a first module could be termed a second module, and, similarly, a second module could be termed a first module, without departing from the scope of the disclosure.

The terminology used in the description of the disclosure herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the disclosure. As used in the description of the disclosure and the appended claims, the singular forms "a", "an", and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will also be understood that the term "and/or" as used herein refers to and encompasses any and all possible combinations of one or more of the associated listed items. The components and features of the drawings are not necessarily drawn to scale.

Database management systems (and other storage systems) may use data encoding to compress the stored data into the storage devices. Dictionary encoding may be a lossless one-to-one compression method that replaces attributes from a large domain with small numbers. To sort the database, if the data is stored in the encoded format, the table should be decoded and then sorted.

But transferring large amounts of data to a host processor to perform dictionary decoding as a preparatory step to other processing may consume resources (such as bus bandwidth and processing time) that might be used for other purposes. A computational storage devices may support general purpose dictionary decoding of data stored in a storage device. With general purpose dictionary decoding, the same accelerator may be used to decode data encoded with two or more different dictionary encodings. The dictionary may encode fixed- or variable-width data. The dictionary may be loaded into the accelerator, after which the data may be read and decoded, then delivered to another processing unit for processing (such as sorting, filtering, etc.) or written back to the storage device (for later processing).

<FIG> shows a system including an accelerator to support dictionary decoding, according to embodiments of the disclosure. In <FIG>, machine <NUM>, which may also be termed a host, may include processor <NUM>, memory <NUM>, and storage device <NUM>. Processor <NUM> may be any variety of processor. (Processor <NUM>, along with the other components discussed below, are shown outside the machine for ease of illustration: embodiments of the disclosure may include these components within the machine. ) While <FIG> shows a single processor <NUM>, machine <NUM> may include any number of processors, each of which may be single core or multi-core processors, each of which may implement a Reduced Instruction Set Computer (RISC) architecture or a Complex Instruction Set Computer (CISC) architecture (among other possibilities), and may be mixed in any desired combination.

Processor <NUM> may be coupled to memory <NUM>. Memory <NUM> may be any variety of memory, such as flash memory, Dynamic Random Access Memory (DRAM), Static Random Access Memory (SRAM), Persistent Random Access Memory, Ferroelectric Random Access Memory (FRAM), or Non-Volatile Random Access Memory (NVRAM), such as Magnetoresistive Random Access Memory (MRAM) etc. Memory <NUM> may also be any desired combination of different memory types, and may be managed by memory controller <NUM>. Memory <NUM> may be used to store data that may be termed "short-term": that is, data not expected to be stored for extended periods of time. Examples of short-term data may include temporary files, data being used locally by applications (which may have been copied from other storage locations), and the like.

Processor <NUM> and memory <NUM> may also support an operating system under which various applications may be running. These applications may issue requests (which may also be termed commands) to read data from or write data to either memory <NUM> or storage device <NUM>. Storage device <NUM> may be used, for example, to store initial parameters (or ranges of values for initial parameters, along with what types of behaviors the ranges of values represent) used to initialize the simulation. Storage device <NUM> may be accessed using device driver <NUM>. While <FIG> uses the generic term "storage device", embodiments of the disclosure may include any storage device formats that may benefit from the use of data quality metrics, examples of which may include hard disk drives and Solid State Drives (SSDs). Any reference to "SSD" below should be understood to include such other embodiments of the disclosure.

Machine <NUM> may also include accelerator <NUM>. Accelerator <NUM> may be an accelerator that may perform dictionary decoding in support of operations performed on data stored in storage device <NUM>. Accelerator <NUM> may be part of storage device <NUM>, accelerator <NUM> may be directly connected to storage device <NUM> (but still a separate element), or accelerator <NUM> may be communicatively coupled to storage device <NUM> across, for example, a bus, such as a Peripheral Component Interconnect Express (PCIe) bus. By keeping accelerator <NUM> closer to storage device <NUM>, the amount of data transferred to processor <NUM> may be reduced, which may increase the available bandwidth for data being sent to or from processor <NUM>. Accelerator <NUM> is discussed further with reference to <FIG> below.

<FIG> shows details of machine <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, typically, machine <NUM> includes one or more processors <NUM>, which may include memory controllers <NUM> and clocks <NUM>, which may be used to coordinate the operations of the components of the machine. Processors <NUM> may also be coupled to memories <NUM>, which may include random access memory (RAM), read-only memory (ROM), or other state preserving media, as examples. Processors <NUM> may also be coupled to storage devices <NUM>, and to network connector <NUM>, which may be, for example, an Ethernet connector or a wireless connector. Processors <NUM> may also be connected to buses <NUM>, to which may be attached user interfaces <NUM> and Input/Output (I/O) interface ports that may be managed using I/O engines <NUM>, among other components.

<FIG> shows an architecture for using the accelerator of <FIG> to support dictionary decoding in the storage device of <FIG>, according to embodiments of the disclosure. In <FIG>, processor <NUM> may be connected to multiple storage devices, each with its own accelerator. Thus, processor <NUM> may be connected to storage devices <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> (which may be referred to collectively as storage device <NUM>). Each storage device <NUM> may include an associated accelerator <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> (which may be referred to collectively as accelerator <NUM>). Accelerator <NUM>-<NUM> is shown coupled between processor <NUM> and storage device <NUM>-<NUM>; storage device <NUM>-<NUM> is shown coupled between processor <NUM> and accelerator <NUM>-<NUM>; and storage device <NUM>-<NUM> is shown as including accelerator <NUM>-<NUM>. While <FIG> shows three storage devices <NUM> and three accelerators <NUM>, embodiments of the disclosure may support any number (one or more) of storage devices <NUM> and accelerators <NUM>.

<FIG> shows processor <NUM>, storage devices <NUM>, and accelerators <NUM> communicating across bus <NUM>. Bus <NUM> may be the bus as bus <NUM> of <FIG>, or bus 305may be a different bus than bus <NUM> of <FIG>. In addition, while <FIG> shows one bus supporting communications between processor <NUM>, storage devices <NUM>, and accelerators <NUM>, embodiments of the disclosure may include any number (one or more) of different buses supporting communication between any of processor <NUM>, storage devices <NUM>, and accelerators <NUM>.

<FIG> shows a Solid State Drive (SSD) supporting dictionary decoding, according to embodiments of the disclosure. In <FIG>, SSD <NUM> may include interface <NUM>. Interface <NUM> may be an interface used to connect SSD <NUM> to machine <NUM> of <FIG> (and/or to connect SSD <NUM> to accelerator <NUM>, when accelerator <NUM> is not part of SSD <NUM>). SSD <NUM> may include more than one interface <NUM>: for example, one interface might be used for block-based read and write requests, and another interface might be used for key-value read and write requests. While <FIG> suggests that interface <NUM> is a physical connection between SSD <NUM> and machine <NUM> of <FIG>, interface <NUM> may also represent protocol differences that may be used across a common physical interface. For example, SSD <NUM> might be connected to machine <NUM> using a U. <NUM> or an M. <NUM> connector, but may support block-based requests and key-value requests: handling the different types of requests may be performed by a different interface <NUM>.

SSD <NUM> may also include host interface layer <NUM>, which may manage interface <NUM>. If SSD <NUM> includes more than one interface <NUM>, a single host interface layer <NUM> may manage all interfaces, SSD <NUM> may include a host interface layer for each interface, or some combination thereof may be used.

SSD <NUM> may also include SSD controller <NUM>, various channels <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM>, along which various flash memory chips <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> may be arrayed. SSD controller <NUM> may manage sending read requests and write requests to flash memory chips <NUM>-<NUM> through <NUM>-<NUM> along channels <NUM>-<NUM> through <NUM>-<NUM>. Although <FIG> shows four channels and eight flash memory chips, embodiments of the disclosure may include any number (one or more, without bound) of channels including any number (one or more, without bound) of flash memory chips.

Within each flash memory chip, the space may be organized into blocks, which may be further subdivided into pages, and which may be grouped into superblocks. The page is typically the smallest unit of data that may be read or written on an SSD. Page sizes may vary as desired: for example, a page may be <NUM> KB of data. If less than a full page is to be written, the excess space is "unused".

While pages may be written and read, SSDs typically do not permit data to be overwritten: that is, existing data may be not be replaced "in place" with new data. Instead, when data is to be updated, the new data is written to a new page on the SSD, and the original page is invalidated (marked ready for erasure). Thus, SSD pages typically have one of three states: free (ready to be written), valid (containing valid data), and invalid (no longer containing valid data, but not usable until erased) (the exact names for these states may vary).

But while pages may be written and read individually, the block is the basic unit of data that may be erased. That is, pages are not erased individually: all the pages in a block are typically erased at the same time. For example, if a block contains <NUM> pages, then all <NUM> pages in a block are erased at the same time. This arrangement may lead to some management issues for the SSD: if a block is selected for erasure that still contains some valid data, that valid data may need to be copied to a free page elsewhere on the SSD before the block may be erased. (In some embodiments of the disclosure, the unit of erasure may differ from the block: for example, it may be a superblock, which may be a set of multiple blocks.

Because the units at which data is written and data is erased differ (page vs. block), if the SSD waited until a block contained only invalid data, the SSD might actually run out of available storage space, even though the amount of valid data might be less than the advertised capacity of the SSD. To avoid such a situation, SSD controller <NUM> may include a garbage collection logic (not shown in <FIG>). The function of the garbage collection may be to identify blocks that contain all or mostly all invalid pages and free up those blocks so that valid data may be written into them again. But if the block selected for garbage collection includes valid data, that valid data will be erased by the garbage collection logic (since the unit of erasure is the block, not the page). So to avoid such data being lost, the garbage collection logic may program the valid data from such blocks into other blocks. Once the data has been programmed into a new block (and the table mapping LBAs to PBAs updated to reflect the new location of the data), the block may then be erased, returning the state of the pages in the block to a free state.

SSDs also have a finite number of times each cell may be written before cells may not be trusted to retain the data correctly. This number is usually measured as a count of the number of program/erase cycles the cells undergo. Typically, the number of program/erase cycles that a cell may support mean that the SSD will remain reliably functional for a reasonable period of time: for personal users, the user may be more likely to replace the SSD due to insufficient storage capacity than because the number of program/erase cycles has been exceeded. But in enterprise environments, where data may be written and erased more frequently, the risk of cells exceeding their program/erase cycle count may be more significant.

To help offset this risk, SSD controller <NUM> may employ a wear leveling logic (not shown in <FIG>). Wear leveling may involve selecting data blocks to write data based on the blocks' program/erase cycle counts. By selecting blocks with a lower program/erase cycle count, the SSD may be able to avoid increasing the program/erase cycle count for some blocks beyond their point of reliable operation. By keeping the wear level of each block as close as possible, the SSD may remain reliable for a longer period of time.

SSD controller <NUM> may include flash translation layer <NUM> (which may be termed more generally a logical-to-physical translation layer, for storage devices that do not use flash storage) and DRAM <NUM>. Flash translation layer <NUM> may handle translation of LBAs or other logical IDs (as used by processor <NUM> of <FIG>) and physical block addresses (PBAs) or other physical addresses where data is stored in flash chips <NUM>-<NUM> through <NUM>-<NUM>. Flash translation layer <NUM>, may also be responsible for relocating data from one PBA to another, as may occur when performing garbage collection and/or wear leveling. DRAM <NUM> may be local memory used by SSD <NUM> for any desired purpose. In some embodiments of the disclosure, DRAM <NUM> may be on the order of <NUM>-<NUM> GB of memory, but may also be larger or smaller than this range of memory.

While <FIG> shows SSD <NUM> as including one accelerator <NUM>, embodiments of the disclosure may include storage device <NUM> including (or connected to) two or more accelerators <NUM>.

<FIG> shows how unencoded/decoded data on storage device <NUM> of <FIG> may be encoded using a dictionary, according to embodiments of the disclosure. In <FIG>, decoded (or original) data <NUM> is shown. While <FIG> shows decoded data <NUM> as a list of integers, embodiments of the disclosure may include any data type: for example, fixed-width data types (that is, data types where the number of bits/bytes used to represent any value in the list is the same). Thus, decoded data <NUM> may include floating point numbers, unsigned numbers, characters, strings, etc..

A dictionary, such as dictionary <NUM>, may be used to store representations of the decoded data, potentially using fewer bits/bytes than the original data. The premise of dictionary <NUM> is that while the number of bits/bytes needed to store each value may be significant, the number of unique values to be represented is relatively small. Thus, by establishing a mapping from a "small" unique key to a "large" value and storing only the "small" unique keys may save space.

As an example, consider a database that contains citizenship information. Countries around the world have names whose lengths vary from <NUM> characters ("Chad") to <NUM> characters ("The United Kingdom of Great Britain and Northern Ireland"). Assuming one byte is needed per character in a country name, the number of bytes needed to store a country of citizenship as a string could therefore vary from <NUM> to <NUM>.

On the other hand, there are only roughly <NUM> countries in the world. The number "<NUM>" may be represented using only two signed bytes (or one unsigned byte). So if a dictionary table maps individual keys to the country names, then the keys could be stored in the database rather than the longer country names.

This mapping may save significant space, depending on the number of entries in the database. Continuing the example, assume that the database includes <NUM>,<NUM> entries. To store <NUM>,<NUM> entries, each including <NUM> bytes (since each entry could, in the worst case, use the longest country name) would require <NUM>,<NUM>,<NUM> bytes. In contrast, storing a dictionary table and using two-byte keys in the database would require storing approximately <NUM> x <NUM> = <NUM>,<NUM> bytes for the dictionary table, and <NUM>,<NUM> bytes in the entries themselves, for a total space requirement of <NUM>,<NUM> bytes: a savings of approximately <NUM>% for that portion of the database. Even if the space required to store the full country names in the entries were approximately ½ of the worst case, the space required would still be <NUM>,<NUM>,<NUM> bytes, and the dictionary encoding would still save approximately <NUM>%.

Thus, <FIG> shows an example of the dictionary encoding, using integer values. Given decoded data <NUM> and dictionary page <NUM>, encoded data <NUM> may be produced. For example, value <NUM>, which is "<NUM>", may be stored in dictionary page <NUM> as key "<NUM>", which may then be stored in encoded data <NUM> as key <NUM>.

Note that the example values shown in decoded data <NUM> would all fit in two-byte integers. If two-byte integers are also used for the keys, then there would be no apparent savings of space by using dictionary page <NUM>. But it could be that while all the example values shown in dictionary page <NUM> would fit in two bytes, there might be other values not shown that could require more than two bytes to store. And even if the width of the keys and values-the number of bits/bytes needed to represent each key and value-are the same, dictionary encoding might still be used.

Dictionary page <NUM> may be constructed in a number of different ways. One way to construct dictionary page <NUM> is to scan decoded data <NUM> one value at a time. If the value is already in dictionary page <NUM>, then the corresponding key may be used in encoded data <NUM>; otherwise, the new value may be added to dictionary page <NUM> and assigned a new key, which may then be used in encoded data <NUM>. Alternatively, decoded data <NUM> may be scanned to identify all the unique values. The unique values may then be sorted and assigned keys. Decoded data may then be mapped to encoded data based on the constructed dictionary page <NUM>. Other embodiments of the disclosure may construct dictionary page <NUM> in other ways.

<FIG> shows the transfer of decoded data to other storage media of <FIG> and <FIG>, according to embodiments of the disclosure. In <FIG>, storage device <NUM> is shown as storing dictionary page <NUM>, along with encoded data pages <NUM>-<NUM> and <NUM>-<NUM> (which may be referred to collectively as encoded data page <NUM>). Accelerator <NUM> may then read dictionary page <NUM> and encoded data page <NUM> from storage device <NUM>, decode encoded data page <NUM>, and write decoded data pages <NUM>-<NUM> and <NUM>-<NUM> (which may be referred to collectively as decoded data page <NUM>) to either DRAM <NUM> (within storage device <NUM>, as shown in <FIG>) and/or memory <NUM> (within host <NUM> of <FIG>, as shown in <FIG>), depending on where the data is to be used next. Accelerator <NUM> may also write decoded data page <NUM> back to storage device <NUM>, in case decoded data page <NUM> may be used at some point in the future.

<FIG> shows details of accelerator <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, accelerator <NUM> is shown as including input buffer <NUM>, address generator <NUM>, memory <NUM>, table read module <NUM>, output filter <NUM>, and output buffer <NUM>. Input buffer <NUM> may receive data from storage device <NUM> of <FIG>, such as encoded data <NUM> of <FIG>. Input buffer <NUM> may receive data from storage device <NUM> of <FIG> via an interface, such as the Advanced Extensible Interface (AXI) over a port on accelerator <NUM> (not shown in <FIG>). Input buffer <NUM> may receive a large block of data to be processed by accelerator <NUM> at one time, or input buffer <NUM> may receive data in streams (that is, sent in multiple small chunks rather than as a single large chunk). Input buffer <NUM> may store the received data temporarily-for example, to fill input buffer <NUM> before further processing by accelerator <NUM>-or may deliver data for further processing by accelerator <NUM> as received.

Once the data is received by input buffer <NUM>, address generator <NUM> may take the key (as stored in encoded data page <NUM> of <FIG>) and use that information to generate the address where the value is stored in dictionary table <NUM>. Address generator <NUM> is discussed further with reference to <FIG> below. Dictionary table <NUM> may store the mapping between key and value (represented by dictionary page <NUM> of <FIG>): table read module <NUM> may then access a data in dictionary table <NUM> from memory <NUM>, using the address generated by address generator <NUM>, to retrieve the entry/entries (which may also be termed row/rows) from dictionary table <NUM> that contains the desired value. Table read module <NUM> may be implemented using, for example, a Central Processing Unit (CPU) or some other processor, a Graphics Processing Unit (GPU), a General Purpose GPU (GPGPU), a Data Processing Unit (DPU), a Tensor Processing Unit (TPU), a Field Programmable Gate Array (FPGA), or an Application-Specific Integrated Circuit (ASIC), among other possibilities. In addition, accelerator <NUM> may include more than one table read module <NUM>, each of which may be separately implemented using any of the above options. (Accelerator <NUM> may also include other such processing elements that may be used for other purposes, such as processing the decoded data. ) Dictionary table <NUM> is discussed further with reference to <FIG> below.

Given the entry/entries from dictionary table <NUM>, output filter <NUM> may then filter out the value to which the key from encoded data page <NUM> of <FIG> is mapped. Output filter is discussed further with reference to <FIG> below. This information may be passed to output buffer <NUM>, which may then output decoded data page <NUM>.

Note that accelerator <NUM> may process the encoded data in encoded data page <NUM> of <FIG>. But in some embodiments of the disclosure encoded data page <NUM> might include more information than just the data encoded using the dictionary <NUM>. For example, consider again a database storing information about the citizenship of some set of people. While the country of citizenship may be data that would benefit from dictionary encoding, the names of the people, or their street addresses might not benefit from dictionary encoding: the number of such unique values is roughly equivalent to the number of entries in the database. Encoded data page <NUM> of <FIG> might include both data that is encoded using dictionary <NUM> and data that is not dictionary encoded. Since accelerator <NUM> may perform dictionary decoding of the encoded data, unencoded data may be returned without modification by accelerator <NUM>. Since accelerator <NUM> may process an entire data page that might include some unencoded data, data from input buffer <NUM>-specifically, data that is not subject to dictionary encoding by accelerator <NUM>-may be provided to output buffer <NUM>, as shown by dashed line <NUM>. Of course, if accelerator <NUM> only receives the actual data that is subject to dictionary encoding. For example, if a filter external to accelerator <NUM> identifies what data is subject to dictionary encoding and what data is not subject to dictionary encoding, that external filter might provide just the dictionary-encoded data to accelerator <NUM>, in which case accelerator <NUM> may simply perform dictionary decoding without concern for data that might be dictionary-encoded.

Memory <NUM> may be DRAM <NUM> of <FIG> or some equivalent type of memory. But memory <NUM> may also be an on-chip memory, which may operate faster than DRAM. For example, memory <NUM> may be block RAM (BRAM) or Ultra RAM (URAM) or some other form of memory. In some embodiments of the disclosure, memory <NUM> may be on the order of <NUM>-<NUM> MB of memory, but may also be larger or smaller than this range of memory.

While <FIG> shows memory <NUM> as including one dictionary table <NUM>, embodiments of the disclosure may support more than one dictionary table <NUM> in memory <NUM>. In such embodiments of the disclosure, accelerator <NUM> may support performing dictionary decoding on data encoded using two or more different dictionaries.

<FIG> shows details of address generator <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, address generator <NUM> may receive as input the input address (which may be the key) as well as the output width (that is, the number of bits/bytes used to store a single value in the dictionary table). As discussed below with reference to <FIG>, a single entry in dictionary table <NUM> of <FIG> may store one or more different values (or parts of one or more different values). If the output width is fixed for all values in dictionary table <NUM> of <FIG>, then given the width of dictionary table <NUM> of <FIG> and the width of a value in dictionary table <NUM> of <FIG>, the number of values in each entry in dictionary table <NUM> may be determined. The least significant bits in the key may then be used to distinguish among the possible values in the entry in dictionary table <NUM> of <FIG>: to identify the entry itself, the input value may be shifted to the right by the number of bits needed to distinguish among the values in an entry. Shift module <NUM> may perform this shift of the input value.

Some examples may help make this clear. Consider the possibility where a single entry in dictionary table <NUM> of <FIG> stores exactly two entries: for example, dictionary table <NUM> of <FIG> might be might be eight bytes wide and each value might require four bytes. Since there are two values in each row in dictionary table <NUM> of <FIG>, one bit may be used to distinguish between the two values. So shift module <NUM> may shift the input key to the right by one bit to identify the row in dictionary table <NUM> of <FIG> where the value is desired stored. So, for example, if the input address is the key "<NUM>" ("<NUM><NUM>" in binary) (actually the seventh value in the table, since addresses may start at zero rather than one), the input address may be shifted by one bit to the right, resulting in the row address "<NUM>" ("<NUM><NUM>" in binary), as the sixth value may be found in row three of dictionary table <NUM>.

On the other hand, consider the situation where a single entry in dictionary table <NUM> of <FIG> stores exactly four entries: for example, dictionary table <NUM> of <FIG> might be eight bytes wide and each value might require two bytes. Since there are four values in each row in dictionary table <NUM> of <FIG>, two bits may be used to distinguish among the four values. So shift module <NUM> may shift the input key to the right by two bits to identify the row in dictionary table <NUM> where the desired value is stored. So, for example, if the input address is the key "<NUM>" ("<NUM><NUM>; in binary), the input address may be shifted by two bits to the right, resulting in the address "<NUM>" ("<NUM><NUM>" in binary), as the sixth value may be found in row one of dictionary table <NUM>.

<FIG> shows details of output filter <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, given as input a row (or rows) from dictionary table <NUM> of <FIG> and the least significant bits of the input address (labeled "entry filter" in <FIG>), output filter <NUM> may use the entry filter to distinguish among values in the row to filter out the desired value. This filtering may be accomplished by masking and shifting the value to eliminate any bits/bytes that are not part of the desired value. For example, bits/bytes that are to the left of the desired value may be masked, and bits/bytes to the right of the desired value may be removed by shifting the desired value to the right.

Consider again the example where a row in dictionary table <NUM> of <FIG> includes eight bytes, and each value is four bytes wide. Since there are two values in each row in dictionary table <NUM> of <FIG>, one bit may be used to distinguish between the two values. If the entry filter is zero, then the first four bytes in the row in the entry may be masked to zero; otherwise, the entry may be shifted to the right by four bytes.

On the other hand, consider again the example where a row in dictionary table <NUM> of FIG. <NUM> includes eight bytes, and each value is two bytes wide. Since there are our values in each row in dictionary table <NUM> of <FIG>, two bits may be used to distinguish between the four values. Based on the entry filter, two of the eight bytes in the row may be left after masking/shifting is complete.

In the above examples, the value may be found entirely within a single row of dictionary table <NUM> of <FIG>, as the width of dictionary table <NUM> of <FIG> is a multiple of the width of the decoded data. In some embodiments of the disclosure, this relationship may not be true, and a single decoded value may be split across two rows in dictionary table <NUM> of <FIG>. <FIG> below discuss how this situation may be handled.

Given the above discussion, it should be apparent that accelerator <NUM> of <FIG> may support dictionary decoding. But more than just supporting dictionary decoding, accelerator <NUM> of <FIG> may support dictionary decoding with any size dictionary table <NUM> of <FIG>, and encoded data width, and any decoded data width. Rather than being customized specific for a dictionary, accelerator <NUM> of <FIG> may be used with any dictionary with a fixed decoded data width. Thus, accelerator <NUM> may be used at one time using a dictionary with one encoded data width, and at another time with a dictionary with another encoded data width, without requiring any reconfiguring (beyond storing the new dictionary in dictionary table <NUM> and specifying the encoded and decoded data widths to be used).

In the above discussion, accelerator <NUM> of <FIG> has been described as though using byte-aligned data types. Since this is true for many data types, byte alignment is convenient to use. But embodiments of the disclosure may use data widths that are measured in bits rather than bytes: for example, if data is packed. Data may be packed if the normal width of the data is greater than needed. For example, two bytes may be used to store (signed) integers up to <NUM>. But if the values are limited to between <NUM> and <NUM>, then only four bits are needed to represent the possible values. By packing four four-bit numbers into two bytes, the data may be stored more compactly, albeit by no longer being byte-aligned. Accelerator <NUM> of <FIG> may handle such packed data simply by measuring widths in terms of bits rather than bytes. For example, in an eight-byte wide row of dictionary table <NUM> of <FIG>, <NUM> different four-bit values may be stored. If the provided key is the value <NUM> (that is, the second entry), then the output filter may filter out all but the second quartet of bits from the row. (Of course, dictionary encoding may not be of much value in the described example, as the encoded width might be larger than the decoded width, but the principle stands).

<FIG> show different ways data may be stored in and retrieved from dictionary table <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, dictionary table <NUM> is shown as eight bytes wide, and storing eight byte data. The first row of dictionary table <NUM> may store value <NUM>-<NUM>, the second row of dictionary table <NUM> may store value <NUM>-<NUM>, the third row of dictionary table <NUM> may store value <NUM>-<NUM>, and so on (values <NUM>-<NUM> through <NUM>-<NUM> may be referred to collectively as values <NUM>). Thus, the input key may be used as the row identifier in dictionary table <NUM> without modification (or, more accurately, by having shift module <NUM> of <FIG> shift the input key to the right by zero bits). For example, if the input key is "<NUM>", then the first row of dictionary table <NUM> may store the value, including bytes zero through sever, as shown by dashed area <NUM>.

In <FIG>, dictionary table <NUM> is shown as eight bytes wide, and storing four byte data. The first row of dictionary table <NUM> may store values <NUM>-<NUM> and <NUM>-<NUM>, the second row of dictionary table <NUM> may store values <NUM>-<NUM> and <NUM>-<NUM>, the third row of dictionary table <NUM> may store values <NUM>-<NUM> and <NUM>-<NUM>, and so on (values <NUM>-<NUM> through <NUM>-<NUM> may be referred to collectively as values <NUM>). Thus, the input key may be used as the row identifier in dictionary table <NUM> by shifting the input key by one bit to the right (since one bit is enough to distinguish between two different values in the row). For example, if the input key is "<NUM>", then the first row of dictionary table <NUM> may store the value (as "<NUM>" in binary is "<NUM><NUM>", and after shifting "<NUM>" to the right one bit, the result is "<NUM><NUM>", indicating the first row in dictionary table <NUM>), including bytes four through seven, as shown by dashed area <NUM>.

In <FIG>, dictionary table <NUM> is shown as eight bytes wide, and storing six byte data. The first row of dictionary table <NUM> may store values <NUM>-<NUM> and the start <NUM>-<NUM>, the second row of dictionary table <NUM> may store the conclusion of value <NUM>-<NUM> and the start of value <NUM>-<NUM>, the third row of dictionary table <NUM> may store the conclusion of value <NUM>-<NUM> and value <NUM>-<NUM>, and so on (values <NUM>-<NUM> through <NUM>-<NUM> may be referred to collectively as values <NUM>). Thus, the input key might be used as the row identifier in dictionary table <NUM> by shifting the input key by one bit to the right (since one bit is enough to distinguish between two different values in the row), subject to the caveat discussed below. For example, if the input key is "<NUM>", then the first row of dictionary table <NUM> may store the value (as "<NUM>" in binary is "<NUM><NUM>", and after shifting "<NUM>" to the right one bit, the result is "<NUM><NUM>", indicating the first row in dictionary table <NUM>), including bytes six through seven, as shown by dashed area <NUM>-<NUM>; since the first row only includes two bytes of the value, the remaining four bytes may be found in the second row, as shown by dashed area <NUM>-<NUM>.

When a single row will hold some number of values precisely, the above description works as described. But when a single entry may span multiple rows due to the width of dictionary table <NUM> not being an exact multiple of the width of the decoded data, then some modifications may be needed. First, because a value may span multiple rows, accelerator <NUM> of <FIG> may retrieve two rows from dictionary table <NUM> to locate the value. Accelerator <NUM> of <FIG> may modified to retrieve the identified row and the following row in each case: at worst, the data in the second row may be discarded by output filter <NUM> of <FIG>.

Second, and more importantly, eventually just shifting the key by some number of bits may return an incorrect row identifier. For example, key "<NUM>" (the fifth value) would be represented in binary as "<NUM><NUM>". With two values in each row, one bit may be used to distinguish between the values: shifting "<NUM><NUM>" by one bit to the right would return "<NUM><NUM>", suggesting that the value may be found in row <NUM> (the third row in dictionary table <NUM>). But in fact the fifth value would be found in bytes zero through five of the fourth row of dictionary table <NUM>. This error occurs because eventually some value will end in the last byte of a row in dictionary table <NUM> (which may occur when the number of bytes needed to store a multiple of the values also is a multiple of the width of dictionary table <NUM>).

There are a few different ways in which this problem may be addressed. One solution is to use a more complicated formula to calculate the row in which the desired value may be located than just a shift operation. If the dictionary width is represented as wdict, the decoded data width is represented as wdata, and the key is represented as k, then the row in which the desired value starts may be calculated as <MAT>. Continuing the earlier example, using k = <NUM>, wdata = <NUM>, and wdict = <NUM>, the row including the fifth value is <MAT>, which is the correct row number (again remembering that rows in dictionary table <NUM> may start at zero). This calculation works because, if the bytes in dictionary table <NUM> are numbered consecutively starting at zero, then k x wdata is the byte in dictionary table <NUM> where the desired value starts; dividing by the width of dictionary table <NUM> and taking the floor of that result (or alternatively, discarding any remainder) identifies the row in which that byte is located.

Another solution to the problem may be used as shown in <FIG>. In <FIG>, rather than calculating the row in which a desired value is stored using the key, the decoded data width, and the width of dictionary table <NUM>, accelerator <NUM> of <FIG> may store (for example, in memory <NUM> of <FIG>) table <NUM>, which may map a particular key to a particular row and offset where the data is stored. Thus, for example, entry <NUM>-<NUM> shows that key "<NUM>" is stored in dictionary table <NUM> starting at row zero, offset zero, entry <NUM>-<NUM> shows that key "<NUM>" is stored in dictionary table <NUM> starting at row zero, offset six, entry <NUM>-<NUM> shows that key "<NUM>" is stored in dictionary table <NUM> starting at row one, offset four, and so on. Then, given a particular key, a lookup in table <NUM> may identify the row and offset in dictionary table <NUM> where that value is stored: the identified row (and perhaps the next row, if a value is split across two rows) may be retrieved, and the output filter may then reduce that information to just the desired value as described above.

In addition to or alternatively to storing the row and offset of each key, table <NUM> may store the byte address and/or the width of the data (shown as optional information by dashed boxes in <FIG>). The byte address may be used to determine the row and offset where the desired value starts in dictionary table <NUM>, similar to the discussion above regarding determining the row and offset from a key. Where the data is of fixed width (that is, all values in dictionary table are the same width) and this value is known by accelerator <NUM> of <FIG>, the width of each individual data element does not need to be stored in table <NUM>. Even for variable width data, the width of any individual value may be determined by determining the number of bits/bytes between adjacent keys in table <NUM> (that is, by counting the number of bits/bytes between where one value starts in dictionary table <NUM> and where the next value starts in dictionary table <NUM>). But by storing the width of values in table <NUM>, accelerator <NUM> may be extract the width of a value along with its location, avoiding the need to calculate the width of the value in decoding the key.

Note that storing the individual lengths for each data value also provides an alternative way to locate a value in dictionary table <NUM>: accelerator <NUM> of <FIG> may calculate a running sum of the widths of the individual values: that sum, divided by the width of dictionary table <NUM>, identifies the row where the value starts, with the remainder identifying the offset within the row. In such an embodiment of the disclosure, table <NUM> may store only the widths of the individual values, rather than their rows/offsets.

Table <NUM> may also offer other benefits. First, by supporting the possibility that the data width of entries in dictionary table <NUM> might not be fixed, table <NUM> enables storing variable-width data in dictionary table <NUM>. In addition, table <NUM> may support storing values that may exceed the width of dictionary table <NUM>. By using table <NUM> to identify where individual values are located in dictionary table <NUM>, there does not need to be a relationship between the key and where the value is stored in dictionary table <NUM>. Thus, while using address generator <NUM> permits a simple calculation of the row in which a value is located, using table <NUM> may provide for a more general solution.

Table <NUM> may be constructed in advance (for example, when dictionary table <NUM> is loaded into accelerator <NUM> of <FIG>), since all that is needed is to know the number of values (that is, the different keys that may be used), the width of the decoded data, and the width of dictionary table <NUM>: the rest is simple arithmetic. In fact, the number of different values does not even need to be known, since the worst case may be assumed (which would be equal to the number of rows in dictionary table <NUM>, multiplied by the width of dictionary table <NUM>, divided by the width of the decoded data (or the width of the narrowest decoded data, if variable-width data is stored in dictionary table <NUM>). And if the key used is identical to the row number in table <NUM>, then table <NUM> does not need to store the key either.

In addition, by storing the starting bit/byte of each value in dictionary table <NUM>, table <NUM> may permit accelerator <NUM> of <FIG> to store variable width data types. For example, as discussed above, country names, when used as strings, may vary in width from four bytes to <NUM> bytes. All the string names may be made the same width by padding the individual values appropriately (with either spaces or null characters, for example) to be as long as the longest string, in which case accelerator <NUM> of <FIG> may be used as described above. But by storing the row and offset where each value starts, accelerator <NUM> of <FIG> may determine not only the starting location of the value in dictionary table <NUM>, but also its width by comparing the row and offset for adjacent keys in table <NUM>. When variable width data types are used, table <NUM> may require scanning dictionary page <NUM> of <FIG> to determine the width of each value (which may affect the row and offset of other values in table <NUM>).

<FIG> shows a flowchart of an example procedure for using the accelerator of <FIG> to perform dictionary decoding in support of data stored on the storage device of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, accelerator <NUM> of <FIG> may read dictionary page <NUM> of <FIG> from storage device <NUM> of <FIG>. Accelerator <NUM> of <FIG> may also configure itself to access data appropriately from dictionary table <NUM> of <FIG> after reading dictionary page <NUM> of <FIG> into dictionary table <NUM> of <FIG>. At block <NUM>, accelerator <NUM> of <FIG> may read encoded data page <NUM> of <FIG> (or alternatively, data from encoded data page <NUM> of <FIG> may be fed to accelerator <NUM> of <FIG>).

At block <NUM>, accelerator <NUM> of <FIG> may access an encoded value in encoded data page <NUM> of <FIG>. At block <NUM>, accelerator <NUM> of <FIG> may map the encoded value from encoded data page <NUM> of <FIG> to a desired value in dictionary table <NUM> of <FIG>. Finally, at block <NUM>, accelerator <NUM> of <FIG> may replace the encoded value in encoded data page <NUM> of <FIG> with the desired value from dictionary table <NUM> of <FIG>, producing decoded data page <NUM> of <FIG>. Blocks <NUM> through <NUM> may be repeated as often as necessary, depending on the number of encoded values in encoded data page <NUM> of <FIG>.

<FIG> show a flowchart of another example procedure for using accelerator <NUM> of <FIG> to perform dictionary decoding in support of data stored on storage device <NUM> of <FIG>, according to embodiments of the disclosure. <FIG> are similar to <FIG>, but more general and with some additional blocks. In <FIG>, at block <NUM>, accelerator <NUM> of <FIG> may read dictionary page <NUM> of <FIG> from storage device <NUM> of <FIG>. Accelerator <NUM> of <FIG> may also configure itself to access data appropriately from dictionary table <NUM> of <FIG> after reading dictionary page <NUM> of <FIG> into dictionary table <NUM> of <FIG>. At block <NUM>, accelerator <NUM> of <FIG> may read encoded data page <NUM> of <FIG> (or alternatively, data from encoded data page <NUM> of <FIG> may be fed to accelerator <NUM> of <FIG>). At block <NUM>, accelerator <NUM> of <FIG> may access an encoded value in encoded data page <NUM> of <FIG>.

At block <NUM> (<FIG>), accelerator <NUM> of <FIG> may map the encoded value from encoded data page <NUM> of <FIG> to a desired value in dictionary table <NUM> of <FIG>. At block <NUM>, accelerator <NUM> of <FIG> may replace the encoded value in encoded data page <NUM> of <FIG> with the desired value from dictionary table <NUM> of <FIG>, producing decoded data page <NUM> of <FIG>. Blocks <NUM> through <NUM> may be repeated as often as necessary, depending on the number of encoded values in encoded data page <NUM> of <FIG>. Finally, there are two possible steps: accelerator <NUM> of <FIG> may store decoded data page <NUM> of <FIG> back to storage device <NUM> of <FIG> (as shown in block <NUM>), or accelerator <NUM> of <FIG> may send decoded data page <NUM> of <FIG> to DRAM <NUM> of <FIG> or memory <NUM> of <FIG> (as shown in block <NUM>).

<FIG> shows a flowchart of an example procedure to load dictionary page <NUM> of <FIG> into accelerator <NUM> of <FIG> and to configure accelerator <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, accelerator <NUM> of <FIG> may store dictionary page <NUM> of <FIG> into dictionary table <NUM> of <FIG>. At block <NUM>, accelerator <NUM> of <FIG> may determine the width of the encoded values as used in dictionary page <NUM> of <FIG> (which may be determined, for example, by the number of bits/bytes used to store the largest key in dictionary page <NUM> of <FIG>). At block <NUM>, accelerator <NUM> of <FIG> may determine the width of the decoded values used in dictionary page <NUM> of <FIG> (which may be determined, for example, by the number of bits/bytes used to store values in dictionary page <NUM> of <FIG>. ) Finally, at block <NUM>, accelerator <NUM> of <FIG> may configure itself using the width of the encoded data and the width of the decoded data.

<FIG> shows a flowchart of an example procedure for accelerator <NUM> of <FIG> to map an encoded value to a decoded value using dictionary table <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, accelerator <NUM> of <FIG> may determine the number of bits used to distinguish among values in a single row of dictionary table <NUM> of <FIG>. At block <NUM>, address generator <NUM> of <FIG> shifts the encoded value (the key) by the number of bits used to distinguish among values in a single row of dictionary table <NUM> of <FIG>, to produce a row identifier. At block <NUM>, accelerator <NUM> of <FIG> may read the identified row from dictionary table <NUM> of <FIG>. At block <NUM>, accelerator <NUM> of <FIG> may also read the adjacent row in dictionary table <NUM>, which may be used if a decoded value is split across two rows in dictionary table <NUM>. Block <NUM> may be omitted, As shown by dashed line <NUM>, if the desired value may be found within a single row in dictionary table <NUM> of <FIG>. Finally, at block <NUM>, output filter <NUM> of <FIG> may filter the desired value from the row(s) of dictionary table <NUM> of <FIG>, based on the bits used to distinguish among values in a row of dictionary table <NUM> of <FIG>.

In <FIG>, some embodiments of the disclosure are shown. But a person skilled in the art will recognize that other embodiments of the disclosure are also possible, by changing the order of the blocks, by omitting blocks, or by including links not shown in the drawings. All such variations of the flowcharts are considered to be embodiments of the disclosure, whether expressly described or not.

As the size of data generated every day increases, there may be a computational bottleneck in the storage devices. The interface between the storage device and the computational platform may be a limitation due to limited bandwidth that might not scale as the number of storage devices increases. Interconnect networks may not provide simultaneous accesses to all storage devices and thus may limit the performance of the system when independent operations occur on different storage devices.

Offloading computations to the storage devices may reduce or eliminate the burden of data transfer from the interconnects. Near storage computing may offload a portion of computation to the storage devices to accelerate the big data applications. A near storage accelerator for database sort (or other database operations) may utilize a computational storage device, such as a Non-Volatile Memory Express (NVMe) flash drive with an on-board Field Programmable Gate Array (FPGA) chip (or other processor) that processes data in-situ. The near storage accelerator may support dictionary decoding, sort, and shuffle operations. The near storage accelerator may support sorting columns with any arbitrary data type, while considering the specifications of the storage devices to increase the scalability of computer systems as the number of storage devices increases. The system may improve both performance and energy efficiency as the number of storage devices increases.

With the growth of data, processing large amounts of data has become a cornerstone of many big data use-cases, such as database applications. As the size of the stored data increases, the cost of loading and storing the data may outweigh the computation cost, which may reduce performance. In some applications, such as database, graph processing, machine learning, and statistical analysis, more than half of the execution time may be spent on data transfer, which shows the impact of data communication on overall performance. The rapid development of Solid-State Drives (SSDs) has shifted the bottleneck associated with data transfer time from magnetic disks (i.e., seek and rotational latency) to interconnect bandwidth and operating system overhead.

The Peripheral Component Interconnect Express (PCIe) interface provides limited simultaneous accesses to the storage devices, which may limit the scalability of the system when independent operations are called on in different storage devices in parallel. This issue, along with low performance of the interconnect bus, may increase the gap between the performance capacity of storage devices and the interconnection buses.

Near-storage computing may enable offloading a portion of computation to the storage drive to accelerate big data applications. Accordingly, new devices have been developed to bring the computation power into the flash storage devices. A computational storage device may be, for example, an NVMe flash drive with an on-board FPGA chip that processes data in-situ. The FPGA, as the computation node of the computational storage device, may provide a high degree of parallelism with affordable power consumption and reconfigurability to implement versatile applications. FPGAs may run parallelizable applications faster with less power as compared to general-processing cores (i.e., a host processor). The benefits achieved by using a computational storage device over a conventional storage device may include both increasing the overall performance by offloading tasks to near-storage nodes to bridge the interconnection gap reduced power consumption through the use of the FPGA. Since the performance of data-intensive applications, such as database management, may be limited by the system bandwidth, such applications may be accelerated by offloading the computations to the storage drive. Therefore, recent processing systems aim to offload the query processing to storage drive to minimize data transfer between the host and storage. In addition, unlike compute-intensive applications, input/output (I/O) bound applications may not benefit from high-performance host processors as their performance may be limited by the host-to-storage bandwidth. Therefore, offloading I/O bound applications to computational storage devices release the host resources to execute more compute-intensive tasks.

As the size of the real-world databases grows, storing databases may involve multiple storage devices. Database-management systems may partition databases into multiple partitions and breakdown operations into multiple independent operations on the partitioned database. Although the independent operations may be executed in parallel, due to storage-to-host bandwidth limitation in I/O bound applications, host processors may not fully utilize the partitioning opportunity. But as computational storage devices have their own computation resources, a computational storage device may perform the independent operations in-situ without using the storage-to-host bandwidth. In particular, a sort operation may be commonly used in database-query processing as a standalone operation or as a backbone of more complex database operations, such as merge-join, distinct, order-by, group-by, etc. When sorting a database, all the table columns may be sorted based on a single column, dubbed a key column. FPGA-based accelerators may focus on accelerating numeric arrays, due to the high complexity of sorting string arrays. However, sorting a table based on a non-numeric column may be widely used in database systems. Due to the number of columns, real-world databases may be complicated to sort because after sorting the key column, the rest of the table should be shuffled accordingly.

Database management systems may use data encoding to compress the stored data into the storage devices. Dictionary encoding may be a lossless one-to-one compression method that replaces attributes from a large domain with small numbers. To sort the database, if the data is stored in the encoded format, the table should be decoded and then sorted.

Computational storage devices may offer independent operations on data stored in each storage device. To sort database tables, a near-storage sort may use computational storage devices that comprise FPGA-based accelerators with specific kernels to accelerate dictionary decoding, sort, and the subsequent shuffle operations. The system may support sorting columns with any arbitrary data types. If the table is stored in the encoded format, the dictionary-decoding kernel may decode the key column. Then, the sort kernel may sort the key column, and the shuffle kernel may reorder the table according to the sorted key column. Such a system not only inherently addresses the data transfer issue by carrying out computations near the storage system, but also embraces an FPGA-friendly implementation of dictionary decoding, sort, and shuffle operations. Additionally, if data is stored in dictionary-encoded format, the system may utilize dictionary encoded data to sort other data types than integer and long data types. Dictionary-encoding may map different data types to integer key values, and the system may first sort the encoded data and then-by using a novel dictionary-decoder kernel that supports any arbitrary data types-decode the sorted column to the original data type.

Embodiments of the disclosure may include accelerator <NUM> of <FIG> as a near-storage accelerator that brings computations closer to the storage devices by leveraging a computational storage device.

Embodiments of the disclosure may include accelerator <NUM> of <FIG> with an FPGA-friendly architecture (or some other substitutable architecture) for a bitonic sort that benefits from FPGA parallelism. The architecture may be scalable to sort various data size, outputs the sorted indices, and may be scaled based on available resources of the FPGA.

Database-management systems may encode data using dictionary encoding to compress the data. The system may include a generic dictionary-decoding kernel to decode data to any data type. The system may use dictionary decoding as a first stage of a database sort to provide an input to a sort kernel. Additionally, dictionary decoding may be utilized to support sorting columns with non-numeric data types. The dictionary-decoding kernel of the system may be optimized to maximize the SSD-to-FPGA bandwidth utilization.

Shuffling may be a step of a database sort and may be I/O bounded. The system may accomplish table sort using a shuffle kernel that fully utilizes bandwidth of an SSD to maximize performance of sorting database tables. The storage pattern of the table may be modified to benefit from regular memory patterns in both shuffle and sort kernels.

Embodiments of the disclosure may include accelerator <NUM> of <FIG>, which may be faster and more energy efficient than the same accelerator on conventional architectures that include a stand-alone FPGA and storage devices in which the FPGA may be connected to the system through a PCIe bus. The system may also be faster and more energy efficient when compared to a CPU baseline.

Database systems may be constrained by disk performance because operations on a database may involve large amounts of data. A database may include one or more tables, each with rows and columns in which each entry holds a specific attribute. Data encoding may be used to compress the table stored in the storage system. Dictionary encoding may be a common encoding method widely used in database-management systems. Unlike byte-oriented compression methods (e.g., gzip, snappy, run-length encoding) that may involve decompression as a blocking step before query execution, dictionary encoding may support parallel decoding and in-situ query processing. Sorting a database table based on a key column may involve the following three steps: decompressing the key column, if the database table is stored in a dictionary-encoded format; sorting the key column; and reordering the rest of the table correspondingly. The system may include three types of kernels: dictionary decoding, sort, and shuffle to execute each step. The system may perform all the computations on a computational storage device to eliminate host-storage communication.

The general architecture of a computational storage device, which may include storage device <NUM> of <FIG> and accelerator <NUM> of <FIG> as separate components or combined into a single device, may include the components of a general SSD, an SSD controller, and a NAND array, as well as an additional FPGA accelerator, a FPGA Dynamic Random Access Memory (DRAM), and a PCIe switch to set up the communication between the NAND array and the FPGA. The link between the FPGA and the SSD may provide direct communication between the computational storage device and a host. The SSD used by the computational storage device may be, for example, about a <NUM> TB SSD connected to, for example, a FPGA through a PCIe Gen3 x4 bus interface.

In such a computational storage device, the processor may issue common SSD commands, such as SSD read/write requests to the SSD controller through the SSD driver. Furthermore, the processor may also be able to issue an FPGA computation request and FPGA DRAM read/write requests via a FPGA driver. In addition to host-driven commands, a computational storage device may support data movement over an internal data path between the NVMe SSD and the FPGA by using the FPGA DRAM and the on-board PCIe switch, which may be referred to herein as peer-to-peer (P2P) communication. The FPGA DRAM may be exposed to a host PCIe address space so that NVMe commands may securely stream data to the FPGA via the P2P communication. The P2P may bring the computations close to where the data may be residing, thereby reducing or eliminating the host-to-storage and the host-to-accelerator PCIe traffic, as well as related round-trip latencies and performance degradations. The computational storage device may provide a development environment and run-time stack, such as runtime library, API, compiler, and drivers to implement the FPGA-based designs.

Current databases may involve multiple devices to store the data. Such databases may be larger than what current commodity-hardware platforms may be able to cope with. Thus, database-management systems may partition the data into smaller chunks so that the computation nodes may execute the computations on each partition in a temporally-affordable manner. Thereafter, the management systems combine the result of each partition to generate a final result. Assuming that the data may be stored in SSDs, the tables of each SSD may be divided into a certain number of partitions. To sort the entire database, all the partitions of each SSD may be sorted and merged through the merge tree. Locally sorting each partition may be independent of the other partitions; therefore, locally different partitions may be sorted in parallel.

In sorting a database table, the system may utilize the storage bandwidth. Therefore, parallelizing multiple partitions on a single SSD may not be beneficial as it may not increase the performance: the FPGA may switch between partitions because it may not simultaneously access different partitions. Thus, the system may parallelize computations at the SSD-level. The system may deploy computational storage devices, each of which may be directly connected to an FPGA. Each computational storage device may sort an SSD-level partition independently of the computational storage device, which may significantly accelerate overall system performance as the number of storage devices grows.

Since accelerator <NUM> of <FIG> may include sort, shuffle, and dictionary-decoder kernels, the system may deal with a trade-off between allocating resources to the kernels. The dictionary-decoder kernel may be able to saturate the storage to FPGA bandwidth; thus, instantiating a single dictionary-decoder kernel may be sufficient to deliver maximum performance. A single-shuffle kernel may not fully utilize the SSD-to-FPGA bandwidth due to the fact that, although in the system a new table storage format enables reading a row in a sequential pattern, reading the next row still may involve a random memory access that has a high latency. Therefore, an aim may be to set the total input consumption rate for all the shuffle kernels to the maximum provided bandwidth of the SSD-to-FPGA to fully utilize bandwidth. Due to the fact that the shuffle operation may be I/O intensive and the size of the table may be significantly larger than the size of the key column, the performance of the shuffle operation may be determinative of the overall performance. Thus, multiple instances of the shuffle kernel may be instantiated to fully leverage the storage-to-FPGA bandwidth and a single instance of the dictionary-decoder kernel and to use the rest of the resources for the sort kernel. The storage-to-FPGA bandwidth may be fully utilized in the shuffle and dictionary-decoder kernel while still having sufficient resources to have a high-throughput sort. The sort kernel may use a great portion of the FPGA block RAM (BRAM) to store the arrays and may provide parallelism. Additionally, the dictionary-decoder kernel may involve on-chip memory to store the dictionary table locally to provide high throughput. Therefore, the dictionary decoder of the system may mostly use FPGA Ultra RAMs (URAMs) to balance the overall resource utilization of the system.

A bitonic sort may be a sorting network that may be run in parallel. In a sorting network, the number of comparisons and the order of comparisons may be predetermined and data-independent. Given a number and order of comparisons, a bitonic sort may be efficiently parallelized on FPGAs by utilizing a fixed network of comparators. A bitonic sort may first convert an arbitrary sequence of numbers into multiple bitonic sequences. By merging two bitonic sequences, a bitonic sort may create a longer bitonic sequence and may proceed until the entire input sequence is sorted. A sequence of length n may be a bitonic sequence if there is an i (<NUM> ≤ i ≤ n) such that all the elements before the ith element are sorted ascending and all the elements after that are sorted descending: that is, x<NUM> ≤ x<NUM> ≤. ≤ xi ≥ xi+<NUM> ≥ xi+<NUM> ≥.

For example, to sort an example input sequence of length n = <NUM> that includes n/<NUM> = <NUM> bitonic sequences of length <NUM>, the initial unsorted sequence may pass through a series of comparators that swap two elements to be in either increasing or decreasing order. The output of the first step may be n/<NUM> bitonic sequences each of length <NUM>. Applying a bitonic merge on the n/<NUM> sequences creates n/<NUM> bitonic sequences. The output sequence after applying log<NUM> n bitonic merge may produce the sorted sequence.

Generally, in the bitonic merge at the ith step (starting from i = <NUM>), n/<NUM>i bitonic sequences of length <NUM>i may be merged to create n/<NUM>(i+<NUM>) bitonic sequences of length <NUM>(i+<NUM>). The ith bitonic merge step itself may include i sequential sub-steps of element-wise comparison. In the first sub-step of the ith step, an element k may be compared with an element k + <NUM>i-<NUM>, while the first <NUM>i elements may be sorted in ascending order and the next <NUM>i elements may be sorted in descending order (the sorting direction may change after every <NUM>i elements). In the aforementioned example, in the first sub-step of the last/third step, the first element may be compared with the <NUM> + <NUM><NUM>-<NUM> = <NUM>th element (with a value of <NUM>). Generally, in the jth sub-step (<NUM> ≤ j ≤ i) of the ith main step, element k may be compared with the element k + <NUM>i-j. Thus, in the second sub-step of the third step, the first element may be compared to the <NUM> + <NUM><NUM>-<NUM> = <NUM>nd element.

To sort a database table, the system may begin with sorting the key column. As mentioned earlier, the sequence of operations in a bitonic sort may be predefined, data-independent, and parallelizable. Therefore, the system may take advantage of FPGA characteristics to accelerate a bitonic sort. The input sequence may be stored in the FPGA DRAM, also referred as "off-chip memory. " Then, the system may stream the input sequence into the FPGA through a port, such as an Advanced Extensible Interface (AXI) port, which has an interface data width of <NUM> bits (<NUM><NUM>-bit integers). The AXI port may write the data to the input buffer, which may have a capacity of P = <NUM>m integer numbers. To have a regular sort network, without lack of generality, P, the size of bitonic-sort kernel, may be a power-of-two number (padding may be used if the total data elements is not a multiple of P). If P may be greater than <NUM>, it may take multiple cycles to fill the input buffer. Whenever the input buffer fills, the input buffer passes the buffered inputs to the P-sorter module.

The P-sorter may be implemented in parallel and may include log<NUM> P steps. The P-sorter module may be pipelined to meet a timing requirement of the FPGA and may be able to provide a throughput of one sorted sequence (of size P) per cycle. The first step in the P-sorter may compare elements of even indices (<NUM>k-indexed elements) with a successor element. Thus, the first step may involve P/<NUM> Compare-and-Swap (CS) modules. During a second step, the P-sorter may first compare and swap elements with indices <NUM>k with <NUM>k + <NUM>, and <NUM>k + <NUM> with <NUM>k + <NUM>. Afterwards, the P-sorter may compare and swap <NUM>k elements with <NUM>k + <NUM> elements of the updated array. Therefore, the second step in the P-sorter may involve P/<NUM> + P/<NUM> = P instances of the CS module. Analogously, the ith step in the P-sorter in which <NUM> ≤ i ≤ log<NUM> P should involve i x P/<NUM> CS modules. The total number of CS modules that should be involved for the -sorter may be estimated as nCS = P/<NUM> + (<NUM> x P/<NUM>) +. + (log<NUM> P x P/<NUM>) ≃ P/<NUM> x log<NUM> P.

The system may orchestrate a sort operation on the entire data by leveraging the P -sorter modules and the fast on-chip memory of the FPGA. First, when sorting every P elements, the P-sorter may toggle between ascending and descending orders. The sorted output of P-sorter modules may be written into a sequence memory, which may include two sub-memory blocks, M<NUM> and M<NUM>, that are made up of FPGA BRAMs. Initially, the ascending and descending sorts may be respectively written in M<NUM> and M<NUM>. Each row of M<NUM> and M<NUM> may include P elements that together form a bitonic row (as the first half is ascending and the second half is descending) in the sequence memory with a length of <NUM>P. Note that, by row refers to adjacent placements of items in a sequence, not necessarily a physical row of a block RAM that may just fit one or two integers. Since the <NUM>P sequence may be just a single bitonic array, using a merging procedure the 2P bitonic array may be sorted using P x log<NUM> <NUM>P) compare-and-swap (CS) units.

Merging the results of P-sorters is itself a bitonic-like procedure, but on sorted arrays rather than scalar elements. That is, step <NUM> may be similar to step <NUM> in a bitonic sort, merging the adjacent arrays. Step <NUM> may be similar to the second step of a simple bitonic sort that compares and swaps every item i with item i + <NUM> using Parallel Compare-and-Swap (PCS) units, followed by comparing item i with item i + <NUM> in the modified array. Thus, the entire sort may be considered to be as an intra-array followed by an inter-array bitonic sort. When the system accomplishes sorting an entire sequence memory, the system may write the sequence back into the off-chip DRAM (or back to the storage device) and uses the same flow to fetch and sort another chunk of the input sequence repetitively and then merges the chunks to build larger sorted chunks.

To provide a desired bandwidth for the parallelization, each of the M<NUM> and M<NUM> memory blocks may use P columns of BRAMs in parallel, so P integers may be fetched at once (the data width of FPGA BRAMs may be <NUM> bit or one integer). Also, in each memory block, L rows of BRAMs may be placed vertically so the results of L sorters may be compared simultaneously. The number of BRAMs and their capacity in terms of <NUM>-bit integers number may be formulated as nBRAM = <NUM> x P x L and CBRAM = <NUM> x <NUM> xP x L.

Note that BRAMs may have a <NUM> bit (depth) by <NUM> bit (width) configuration. At each iteration, CBRAM = <NUM>PL integers may be sorted and written back to the off-chip DRAM.

To sort a database table, the rest of the table rows may be reordered based on the indices of the sorted key column, referred to herein as sorted indices. Thus, the sorted indices may be generated that later may be used by the shuffle kernel to sort the entire table. To this end, when reading an input sequence from DRAM, an index may be assigned to each element and the indices may be stored in an index memory that has the same capacity as the sequence memory. When reading from the sequence memory and feeding inputs to the P-sorter, the system may read the corresponding index and concatenates to the value. The compare-and-swap units of P-sorters may perform the comparison merely based on the value part of the concatenated elements, but the entire concatenated element may be swapped. The system, therefore, may store the sorted indices in the DRAM as well.

The P-sorter module may sort chunks of elements and may store in the following sequence memory. The M<NUM> memory group may store the ascending sorts while M<NUM> may store the descending sorted elements. There are P BRAMs at every row of the M<NUM> (and M<NUM>) memory, so the sorted P elements may be partitioned element-wise for subsequent parallel operations. In the PCS sub-steps, two P-element arrays from the same memory (either M<NUM> or M<NUM>) may be fetched while in the last sub-step (i.e., merge), a P-element array from M<NUM> and another from M<NUM> may be fetched and sorted/merged. L-to-<NUM> multiplexers that are connected to all L BRAM groups may be used to manage these operations, and up to two arrays may be selected from each of M<NUM> and M<NUM>. The PCS and merge modules' outputs may be written back in the sequence memory to accomplish the next steps.

After sorting the key column, the system may use a shuffle kernel to reorder the table rows. To implement this operation, the system may read the value of the first element of the sorted key column as well as its index in the original table (which may be concatenated to the value of elements). Then, the system may read all the entries of the original row that the index points to and may write it as the first row of the new sorted table. Analogously, to generate the ith row of the sorted table, the system may read the ith element of the sorted indices sequence. The index represents the index of the row in the original table. Thus, the mapping between the original table and the sorted one may be formulated as<MAT>.

The shuffle kernel does not necessarily perform any computation; hence, the performance of the kernel may be bounded by the memory access time. Storing the tables in the storage, therefore, may directly affect the performance of the kernel. Typically, tables may be stored in either column-wise or row-wise format. In the column-wise format, elements of every column may be stored in consecutive memory elements. In the row-wise format, all the elements of a row may be placed in successive memory elements. Consecutive memory elements may be transferred to the FPGA from DRAM in a burst mode significantly faster than scattered (random) accesses.

Storing the table in a column-wise format may result in a sequential/burst memory access pattern in the sort kernel (because it involves access to the consecutive elements of the key column, which may be denoted as Ck). However, the shuffle kernel may have random access patterns (as the shuffle kernel uses access to the consecutive elements of the same row, which may be placed distantly in the column-wise arrangement). Analogously, storing the table in row-wise format may enable sequential access patterns to read a single row (suitable for the shuffle kernel), but reading the next row (as part of a sort kernel) may involve random memory access. To optimize the access patterns of both kernels, the system may use a hybrid technique for storing the table in the storage. The key column (Ck ) may be stored column-wise while the rest of the table may be stored in row-based format. Therefore, both kernels may benefit from sequential memory accesses.

In database-management systems, data may be stored compressed in the storage system to reduce the number of storage devices used to store the database. Dictionary encoding may be used as a stand-alone compression technique or as a step combined with other compression techniques. Dictionary encoding may be a lossless compression technique that maps each "value" to a "key". Using dictionary encoding may be beneficial when the range of the numbers may be significantly greater than the number of unique values (U). Each unique value may be represented by a k-bit key in which k = log<NUM> U. Dictionary encoding may be beneficial when the size of the encoded data is considerably smaller than the total size of the elements. Dictionary encoding may be more effective for data types with greater sizes. A dictionary-decoding accelerator may only support decoding values having fixed-length data types. However, dictionary encoding may be more effective in encoding variable-length data types, such as strings. The system may include an accelerator for dictionary decoding that supports all data types (both fixed- and variable-length data types).

If the data is stored in the storage devices in the encoded format, even though some database operations (e.g., filter or shuffle) may be run on the dictionary encoded data to perform sort operation on the table, the data should be decoded first. The dictionary decoder of the system, which may be implemented using accelerator <NUM> of <FIG>, may first read the "dictionary page," which is stored along with the encoded data, from the storage device. It may store the dictionary page in the FPGA local BRAM to provide fast access to decode the inputs. Since the length of values may be different, in variable-length data types, such as string; the system may not store a single value in every row of the on-chip dictionary table to fully utilize the capacity of limited FPGA BRAMs. A dictionary table of the system may include R rows in which each row may be Lmax bytes. Lmax may be the number of bytes of the longest value in the dictionary. The dictionary decoder of the system may concatenate the dictionary values and may write them in the dictionary table consecutively. As a result, bytes of a dictionary value may split in two consecutive rows of the dictionary table. Since the length of each row may be equal or greater than the length of every dictionary value, each value may either be stored in a single row, or split into two consecutive rows. To find the location and length of the value corresponding to a key, the dictionary decoder of the system constructs the index memory, which may store the byte address and the length of every dictionary value in the dictionary table. The dictionary decoder of the system may use the input key to look up the index and the length of the corresponding value. Then, the system may use the index and the length to read the value from the byte addressable dictionary table. As there may be multiple accesses to both index memory and dictionary table in every clock cycle, the system may use on-chip memory to store the two tables.

The dictionary decoder of the system, which may be implemented using accelerator <NUM> of <FIG>, after constructing the index memory and the dictionary table, may stream in the data page, decode the data page, and write the decoded data to the FPGA DRAM. As the decoded data may be used in the sort kernel, the system may keep the decoded data into the FPGA DRAM to avoid unnecessary storage accesses. The width of the input elements (k) may depend on the number of unique elements in the dictionary (U), and the width of the decoded elements may depend on the original data type. The system may provide a generic dictionary decoder that supports various input and output bit widths that may be configured during the runtime. The dictionary decoder of the system, after loading the dictionary, may stream in the data page using the AXI interface. For the sake of design simplicity and AXI compatibility, the dictionary decoder of the system may limit the input bit widths k to power-of-two numbers that are greater than eight. The AXI interface may read the encoded data page elements and may store the encoded data page elements in the input buffer. Input keys may be associated with values with different bit widths. Thus, to support decoding to different data types, the dictionary table may support the reading and writing element with different bit widths.

Embodiments of the disclosure may include accelerator <NUM> of <FIG>, which may stream in the input keys and may store the input keys in the input buffer. The system may look up the location and length of the corresponding value in the dictionary table from the index memory. The index memory may output the byte address of the first byte of the value in the dictionary table as well as the length of the value. The byte address may be used to find the row address of the dictionary memory that contains the value. A dictionary value may either be entirely store in a dictionary table row or it may be split into two consecutive rows. Therefore, for each key, the address generator may output the row address that contains the first byte of the value and the next row. The system may read two rows of the dictionary table and may write them into an output filtering module. The output filtering may use the byte address and the length of the value to find and filter the value corresponds to the input key. The output filtering module may output the dictionary value and may write it into the parallel buffers in the output buffer module. The output buffer module may aggregate multiple values and may transfer them to the FPGA off-chip DRAM.

As an example, a dictionary page might include values that are a maximum of <NUM> bytes wide. Therefore, each row of the dictionary table may include <NUM> bytes. The content of the index memory may be constructed during the runtime. The first byte of the first value may start at address <NUM>, and the value may be, for example, <NUM> bytes long. The next value may start at address <NUM> in the dictionary table and may be <NUM> bytes long. For each value, the pointer may be the accumulation of all the previous lengths, and the length represents the size of the value in bytes. The address generator module may use the byte address to find the row addresses that contain the value. To get the row address, the address generator may shift the byte address to right for log<NUM> MS, where MS may be the maximum string length. Then the shifted value its next rows will be the row addresses that contain the value. The [MS-<NUM>:<NUM>] bits of the byte address may be used in the output filtering module to extract the value from the two rows read from the dictionary table. For instance, for some value the byte address and the length parameters might be <NUM> and <NUM>, respectively. The first byte of the value may starts at address <NUM>. The address generator may shift the byte address to right for three bits (log<NUM> <NUM>), which returns the row address of <NUM> >> <NUM> = <NUM>: in other words, the desired value is in rows <NUM> and <NUM>. The system may read rows <NUM> and <NUM> from the dictionary table and may write them into the output filtering module. Bits [<NUM>:<NUM>] of the byte address may be used as an offset from the first byte of the read rows. The value may starts at the byte offset and ends after length bytes. In this example, the offset may be equal to <NUM> and the length may be equal to <NUM>, which means the value is between bytes <NUM> to <NUM>. The output filtering module may extract the value from the read rows, and may write it into parallel output buffers. The system may use multiple parallel buffers to increase the output bandwidth utilization and, consequently, increase the performance by writing multiple bytes in each cycle. However, because the length of values varies, the output buffer module may concatenate the consecutive values and may write them into P parallel buffers and whenever, all the P buffers have an element in them, it may transfer the P bytes into the FPGA DRAM.

Database-management systems may frequently use dictionary encoding to store the data. The system not only ay sort columns of integer and long data types, it also may support sorting columns with any data types if the column is stored in a dictionary encoded format. Dictionary encoding may represent values with any data types with integer keys. The system may use a method to sort the dictionary encoded column by leveraging the sort and dictionary-decoding kernels. The table may be stored in the storage system and the column based on which table that is going to be sorted is dictionary may be encoded. Note that the rest of the columns may be stored in either dictionary encoded or in plain format. First, the system may read the dictionary page of the column on the host server: the size of the dictionary table may be significantly less than the size of the original column. Database-management systems may use dictionary encoding when the number of unique elements (size of the dictionary) may be significantly less than the number of elements in the column. Thus, sorting the dictionary page may take significantly less time than sorting the column considering the size of the arrays and non-linear complexity of the sort operation. Therefore, the system may take advantage of the host server to sort the dictionary table due to the efficiency of sorting small arrays on general-purpose processors. The host machine may sort the dictionary table based on the values and assigns new keys, referred to herein as mapped keys, to the sorted values. The host server may also generate a key mapping table that may map the keys of the original dictionary encoding to the keys of the sorted dictionary table. The system may use the sorted dictionary table and key mapping table in a generic sort flow. The system may use the key mapping table to map the input data to the mapped key array. In this mapping, the order of the keys may be the same as the order of the sorted values. For instance, if a column is sorted in ascending order, the greater key, corresponds to a value that is greater in the sorted order.

The host program may read the dictionary page from the storage system, sorts the dictionary table, generates the key mapping table and transfers both sorted dictionary table and key mapping table to the FPGA DRAM. The FPGA may read the data page directly from the storage device to eliminate the overhead of transferring the data page through the host server. A generic-sort method of the system may be a flow of data that utilizes the sort kernel and the dictionary-decoder kernel to sort a column with any data types and may use the shuffle kernel to sort the entire table based on the sorted column. First, the system may load the key mapping table, and then may stream in the data page. Then, the system may map the input keys to mapped keys using the key mapping table. The system may initiate the sort kernel of the system to sort the mapped key. Sorting the mapped key may be equivalent to sorting the original data because the order of the mapped keys may be the same as the order of the values in the sorted array. The system sort kernel may sort the mapped key array and may write it into the sorted mapped key array. The system may use the dictionary-decoder kernel to decode the sorted mapped key array to the sorted array in the original data type.

As an example, consider a column of strings. The string column may be dictionary encoded, and stored in the storage as {<NUM>, <NUM>, <NUM>, <NUM>, <NUM>}, and the dictionary page may be stored along with the data page. Note that, in this example for simplicity a small column is used; however, in real-world applications, the data page size may be significantly larger than the dictionary page. The system may offload sorting the dictionary page and may generate the key mapping table to the host server. The host may transfer the two tables and may send them to the FPGA DRAM. In this example, the system may sort the data page in an ascending order. For example, the original dictionary-encoded data may map the string "USA" to the key <NUM>, but after sorting the dictionary table, the string "USA" may be the last element of all the values. The key mapping table may map key <NUM> to mapped key <NUM>, which means the value corresponding to any key less than <NUM> may come earlier in the sorted data in the original data type. The system may read the data and may mapped the data into the mapped-key array. The system may then sort the mapped key array and may store the data into the sorted mapped-key array. The system may use the sorted dictionary table to decode the sorted mapped-key array to the original data type. For example, as discussed above, the key <NUM> in the original dictionary page may correspond to the dictionary value "USA". Since "USA" may come last when the data is sorted, the system may map keys <NUM> to mapped keys <NUM>. Then, in the sorted mapped key array the element <NUM> becomes the last element. The system may decode the sorted mapped key array and the last element may be decoded to the string "USA".

Embodiments of the disclosure offer technical advantages over the prior art. By using an accelerator, dictionary decoding may be performed closer to the data, which may reduce the load on the host processor, as well has reducing the amount of data to be sent between the storage device and the host processor. Further, by making the accelerator configurable to use with any dictionary, the accelerator may be reused simply by loading a new dictionary page and adjusting the widths of the encoded and decoded values.

The following discussion is intended to provide a brief, general description of a suitable machine or machines in which certain aspects of the disclosure may be implemented. The machine or machines may be controlled, at least in part, by input from conventional input devices, such as keyboards, mice, etc., as well as by directives received from another machine, interaction with a virtual reality (VR) environment, biometric feedback, or other input signal. As used herein, the term "machine" is intended to broadly encompass a single machine, a virtual machine, or a system of communicatively coupled machines, virtual machines, or devices operating together. Exemplary machines include computing devices such as personal computers, workstations, servers, portable computers, handheld devices, telephones, tablets, etc., as well as transportation devices, such as private or public transportation, e.g., automobiles, trains, cabs, etc..

The machine or machines may include embedded controllers, such as programmable or non-programmable logic devices or arrays, Application Specific Integrated Circuits (ASICs), embedded computers, smart cards, and the like. The machine or machines may utilize one or more connections to one or more remote machines, such as through a network interface, modem, or other communicative coupling. Machines may be interconnected by way of a physical and/or logical network, such as an intranet, the Internet, local area networks, wide area networks, etc. One skilled in the art will appreciate that network communication may utilize various wired and/or wireless short range or long range carriers and protocols, including radio frequency (RF), satellite, microwave, Institute of Electrical and Electronics Engineers (IEEE) <NUM>, Bluetooth®, optical, infrared, cable, laser, etc..

Embodiments of the present disclosure may be described by reference to or in conjunction with associated data including functions, procedures, data structures, application programs, etc. which when accessed by a machine results in the machine performing tasks or defining abstract data types or low-level hardware contexts. Associated data may be stored in, for example, the volatile and/or non-volatile memory, e.g., RAM, ROM, etc., or in other storage devices and their associated storage media, including hard-drives, floppy-disks, optical storage, tapes, flash memory, memory sticks, digital video disks, biological storage, etc. Associated data may be delivered over transmission environments, including the physical and/or logical network, in the form of packets, serial data, parallel data, propagated signals, etc., and may be used in a compressed or encrypted format. Associated data may be used in a distributed environment, and stored locally and/or remotely for machine access.

Embodiments of the disclosure may include a tangible, non-transitory machine-readable medium comprising instructions executable by one or more processors, the instructions comprising instructions to perform the elements of the disclosures as described herein.

The various operations of methods described above may be performed by any suitable means capable of performing the operations, such as various hardware and/or software component(s), circuits, and/or module(s). The software may comprise an ordered listing of executable instructions for implementing logical functions, and may be embodied in any "processor-readable medium" for use by or in connection with an instruction execution system, apparatus, or device, such as a single or multiple-core processor or processor-containing system.

The blocks or steps of a method or algorithm and functions described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. If implemented in software, the functions may be stored on or transmitted over as one or more instructions or code on a tangible, non-transitory computer-readable medium. A software module may reside in Random Access Memory (RAM), flash memory, Read Only Memory (ROM), Electrically Programmable ROM (EPROM), Electrically Erasable Programmable ROM (EEPROM), registers, hard disk, a removable disk, a CD ROM, or any other form of storage medium known in the art.

Claim 1:
An accelerator (<NUM>) for dictionary decoding of data stored on a storage device (<NUM>), the accelerator (<NUM>) comprising:
a memory (<NUM>, <NUM>, <NUM>) configured to store a dictionary table (<NUM>, <NUM>), wherein the accelerator (<NUM>) is configured to read a dictionary page (<NUM>) from the storage device (<NUM>) and store the dictionary page (<NUM>) in the dictionary table (<NUM>, <NUM>) in the memory (<NUM>, <NUM>, <NUM>), and wherein the dictionary page (<NUM>) maps an encoded value with an encoded width to a decoded value with a decoded width;
an address generator (<NUM>) configured to generate an address in the dictionary table (<NUM>, <NUM>) in the memory (<NUM>, <NUM>, <NUM>) based at least in part on the encoded value with the encoded width; and
an output filter (<NUM>) configured to filter the decoded value with the decoded width from the dictionary table (<NUM>, <NUM>) based at least in part on the address,
wherein the accelerator (<NUM>) is configured to support at least two different encoded widths,
wherein:
the address generator (<NUM>) includes a shift module (<NUM>) configured to shift the encoded value based at least in part on a number of bits to produce a row number, wherein one bit is used to distinguish between the two values in each row in the dictionary table (<NUM>, <NUM>);
the accelerator (<NUM>) further comprises a table read module configured to read an entry (<NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>) from the dictionary table (<NUM>, <NUM>) based at least in part on the row number; and
the output filter (<NUM>) is configured to filter the entry (<NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>) to produce the decoded value.