Patent Description:
However, typical scrambling schemes often default to a row-based scrambling. That is, a given row is associated with a given scrambler state, such that I/O operations are scrambled (or descrambled) according to that state. This presents a challenge for memory architectures adapting column-based I/O operations because each location in the column is associated with a different scrambler state from one another.

<CIT> describes techniques for programming and reading data with reduced read errors in a memory device. Data to be written to the memory device is scrambled using a first pseudo random number which is generated based on a page of the memory device to which the data is to be written, to provide first scrambled data, which is scrambled using a second pseudo random number which is generated based on a block of the memory device.

<CIT> describes random sequence data that is sequentially generated based on a seed assigned to a selected memory space and one or access-requested segments of the selected memory space is logically combined with the sequentially generated random sequence data to transfer the access-requested segment.

<CIT> describes a method for operating a controller including storing a pseudo noise sequence provided from a pseudo noise sequence generator in an i-th area of a seed table and cyclically shifting the pseudo noise sequence from the i-th area to an (i+<NUM>)-th area in the table to form the table.

<CIT> describes a controller of a non-volatile memory system that is configured to identify bits of data to be stored in the memory elements of the memory system that are identified as unreliable. The controller is configured to bias at least some of these bits to a predetermined logic value at which the bits are likely to be read from the unreliable memory elements.

<CIT> a randomizer that includes a first and second pseudorandom number generator, and a first logic circuit configured to output a pseudorandom sequence by carrying out an operation on pseudorandom sequences generated by the first and second pseudorandom number generators, and a second logic circuit configured to randomize a data string input to the randomizer.

<CIT> describes technologies for performing hyper-dimensional operations in memory including a device with a memory media and a memory controller. The memory controller is configured to receive a query from a requestor and determined a reference hyper-dimensional vector associated with the query. The memory controller performs a nearest neighbor search by search columns of a stochastic associative arrays to determined a number of matching bit values for each row relative to the reference hyper-dimensional vector.

<CIT> describes data scrambling techniques implemented externally to a flash memory device which can be used in concert with flash memory on-chip copy functionality operating internally to the flash device. All data stored in the flash may be scrambled including headers and control structures. <CIT> and <CIT> describe background information.

The dependent claims recite selected optional features.

The disclosed embodiments may be implemented, in some cases, in hardware, firmware, software, or any combination thereof. The disclosed embodiments may also be implemented as instructions carried by or stored on a transitory or non-transitory machine-readable (e.g., computer-readable) storage medium, which may be read and executed by one or more processors. A machine-readable storage medium may be embodied as any storage device, mechanism, or other physical structure for storing or transmitting information in a form readable by a machine (e.g., a volatile or non-volatile memory, a media disc, or other media device).

Referring now to <FIG>, a compute device <NUM> for performing column architecture-aware scrambling on data includes a processor <NUM>, a memory <NUM>, an input/output (I/O) subsystem <NUM>, a data storage device <NUM>, communication circuitry <NUM>, and one or more accelerator devices <NUM>. Of course, in other embodiments, the compute device <NUM> may include other or additional components, such as those commonly found in a computer (e.g., a display, peripheral devices, etc.). Additionally, in some embodiments, one or more of the illustrative components may be incorporated in, or otherwise form a portion of, another component. The term "memory," as used herein, may refer to the memory <NUM> and/or the data storage device <NUM>, unless otherwise specified. As explained in more detail herein, media access circuitry <NUM>, <NUM> (e.g., any circuitry or device configured to access and operate on data in the corresponding memory media <NUM>, <NUM>) connected a corresponding memory media <NUM>, <NUM> (e.g., any device or material that data is written to and read from) may access (e.g., read) individual columns (e.g., bits) of rows of data (e.g., vectors), such as for use in performing similarity searches, also referred to as "stochastic associative searches" (SAS). As such, the memory may operate as a "stochastic associative memory" (e.g., is designed to enable the efficient performance of stochastic associative searches).

The memory media <NUM>, in the illustrative embodiment, has a three dimensional cross point architecture that has data access characteristics that differ from other memory architectures (e.g., dynamic random access memory (DRAM)), such as enabling access to one bit per tile and incurring time delays between reads or writes to the same partition or other partitions. The media access circuitry <NUM> is configured to make efficient use (e.g., in terms of power usage and speed) of the architecture of the memory media <NUM>, such as by accessing multiple tiles in parallel within a given partition. In some embodiments, the media access circuitry <NUM> may utilize scratch pads (e.g., relatively small, low latency memory) to temporarily retain and operate on data read from the memory media <NUM> and broadcast data read from one partition to other portions of the memory <NUM> to enable calculations (e.g., matrix operations) to be performed in parallel within the memory <NUM>. Additionally, in the illustrative embodiment, instead of sending read or write requests to the memory <NUM> to access matrix data, the processor <NUM> may send a higher-level request (e.g., a request for a macro operation, such as a request to return a set of N search results based on a search key). As such, many compute operations, such as artificial intelligence operations (e.g., stochastic associative searches) can be performed in memory (e.g., in the memory <NUM> or in the data storage device <NUM>), with minimal usage of the bus (e.g., the I/O subsystem <NUM>) to transfer data between components of the compute device <NUM> (e.g., between the memory <NUM> or data storage device <NUM> and the processor <NUM>).

In some embodiments the media access circuitry <NUM> is included in the same die as the memory media <NUM>. In other embodiments, the media access circuitry <NUM> is on a separate die but in the same package as the memory media <NUM>. In yet other embodiments, the media access circuitry <NUM> is in a separate die and separate package but on the same dual in-line memory module (DIMM) or printed circuit board as the memory media <NUM>.

The processor <NUM> may be embodied as any device or circuitry (e.g., a multi-core processor(s), a microcontroller, or other processor or processing/controlling circuit) capable of performing operations described herein, such as executing an application (e.g., an artificial intelligence related application that may utilize stochastic associative searches). In some embodiments, the processor <NUM> may be embodied as, include, or be coupled to a field-programmable gate array (FPGA), an application specific integrated circuit (ASIC), reconfigurable hardware or hardware circuitry, or other specialized hardware to facilitate performance of the functions described herein.

The memory <NUM>, which may include a non-volatile memory (e.g., a far memory in a two-level memory scheme), includes the memory media <NUM> and the media access circuitry <NUM> (e.g., a device or circuitry, such as a processor, application specific integrated circuitry (ASIC), or other integrated circuitry constructed from complementary metal-oxide-semiconductors (CMOS) or other materials) underneath (e.g., at a lower location) and coupled to the memory media <NUM>. The media access circuitry <NUM> is also connected to the memory controller <NUM>, which may be embodied as any device or circuitry (e.g., a processor, a co-processor, dedicated circuitry, etc.) configured to selectively read from and/or write to the memory media <NUM> in response to corresponding requests (e.g., from the processor <NUM> which may be executing an artificial intelligence related application that relies on stochastic associative searches to recognize objects, make inferences, and/or perform related artificial intelligence operations). In some embodiments, the memory controller <NUM> may include a vector function unit (VFU) <NUM> which may be embodied as any device or circuitry (e.g., dedicated circuitry, reconfigurable circuitry, an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), etc.) capable of offloading vector-based tasks from the processor <NUM> (e.g., comparing data read from specific columns of vectors stored in the memory media <NUM>, determining Hamming distances between the vectors stored in the memory media <NUM> and a search key, sorting the vectors according to their Hamming distances, etc.).

Referring briefly to <FIG>, the memory media <NUM>, in the illustrative embodiment, includes a tile architecture, also referred to herein as a cross point architecture (e.g., an architecture in which memory cells sit at the intersection of word lines and bit lines and are individually addressable and in which bit storage is based on a change in bulk resistance), in which each memory cell (e.g., tile) <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> is addressable by an x parameter and a y parameter (e.g., a column and a row). The memory media <NUM> includes multiple partitions, each of which includes the tile architecture. The partitions may be stacked as layers <NUM>, <NUM>, <NUM> to form a three dimensional cross point architecture (e.g., Intel 3D XPoint™ memory). Unlike typical memory devices, in which only fixed-size multiple-bit data structures (e.g., byte, words, etc.) are addressable, the media access circuitry <NUM> is configured to read individual bits, or other units of data, from the memory media <NUM> at the request of the memory controller <NUM>, which may produce the request in response to receiving a corresponding request from the processor <NUM>.

Referring back to <FIG>, the memory <NUM> may include non-volatile memory and volatile memory. The non-volatile memory may be embodied as any type of data storage capable of storing data in a persistent manner (even if power is interrupted to the non-volatile memory). For example, the non-volatile memory may be embodied as one or more non-volatile memory devices. The non-volatile memory devices may include one or more memory devices configured in a cross point architecture that enables bit-level addressability (e.g., the ability to read from and/or write to individual bits of data, rather than bytes or other larger units of data), and are illustratively embodied as three dimensional (3D) cross point memory. In some embodiments, the non-volatile memory may additionally include other types of memory, including any combination of memory devices that use chalcogenide phase change material (e.g., chalcogenide glass), ferroelectric transistor random-access memory (FeTRAM), nanowire-based non-volatile memory, phase change memory (PCM), memory that incorporates memristor technology, Magnetoresistive random-access memory (MRAM) or Spin Transfer Torque (STT)-MRAM. The volatile memory may be embodied as any type of data storage capable of storing data while power is supplied volatile memory. For example, the volatile memory may be embodied as one or more volatile memory devices, and is periodically referred to hereinafter as volatile memory with the understanding that the volatile memory may be embodied as other types of non-persistent data storage in other embodiments. The volatile memory may have an architecture that enables bit-level addressability, similar to the architecture described above.

The processor <NUM> and the memory <NUM> are communicatively coupled to other components of the compute device <NUM> via the I/O subsystem <NUM>, which may be embodied as circuitry and/or components to facilitate input/output operations with the processor <NUM> and/or the main memory <NUM> and other components of the compute device <NUM>. For example, the I/O subsystem <NUM> may be embodied as, or otherwise include, memory controller hubs, input/output control hubs, integrated sensor hubs, firmware devices, communication links (e.g., point-to-point links, bus links, wires, cables, light guides, printed circuit board traces, etc.), and/or other components and subsystems to facilitate the input/output operations. In some embodiments, the I/O subsystem <NUM> may form a portion of a system-on-a-chip (SoC) and be incorporated, along with one or more of the processor <NUM>, the main memory <NUM>, and other components of the compute device <NUM>, in a single chip.

The data storage device <NUM> may be embodied as any type of device configured for short-term or long-term storage of data such as, for example, memory devices and circuits, memory cards, hard disk drives, solid-state drives, or other data storage device. In the illustrative embodiment, the data storage device <NUM> includes a memory controller <NUM>, similar to the memory controller <NUM>, memory media <NUM> (also referred to as "storage media"), similar to the memory media <NUM>, and media access circuitry <NUM>, similar to the media access circuitry <NUM>. Further, the memory controller <NUM> may also include a vector function unit (VFU) <NUM> similar to the vector function unit (VFU) <NUM>. The data storage device <NUM> may include a system partition that stores data and firmware code for the data storage device <NUM> and one or more operating system partitions that store data files and executables for operating systems.

The communication circuitry <NUM> may be embodied as any communication circuit, device, or collection thereof, capable of enabling communications over a network between the compute device <NUM> and another device. The communication circuitry <NUM> may be configured to use any one or more communication technology (e.g., wired or wireless communications) and associated protocols (e.g., Ethernet, Bluetooth®, Wi-Fi®, WiMAX, etc.) to effect such communication.

The illustrative communication circuitry <NUM> includes a network interface controller (NIC) <NUM>, which may also be referred to as a host fabric interface (HFI). The NIC <NUM> may be embodied as one or more add-in-boards, daughter cards, network interface cards, controller chips, chipsets, or other devices that may be used by the compute device <NUM> to connect with another compute device. In some embodiments, the NIC <NUM> may be embodied as part of a system-on-a-chip (SoC) that includes one or more processors, or included on a multichip package that also contains one or more processors. In some embodiments, the NIC <NUM> may include a local processor (not shown) and/or a local memory (not shown) that are both local to the NIC <NUM>. In such embodiments, the local processor of the NIC <NUM> may be capable of performing one or more of the functions of the processor <NUM>. Additionally or alternatively, in such embodiments, the local memory of the NIC <NUM> may be integrated into one or more components of the compute device <NUM> at the board level, socket level, chip level, and/or other levels. The one or more accelerator devices <NUM> may be embodied as any device(s) or circuitry capable of performing a set of operations faster than the general purpose processor <NUM>. For example, the accelerator device(s) <NUM> may include a graphics processing unit <NUM>, which may be embodied as any device or circuitry (e.g., a co-processor, an ASIC, reconfigurable circuitry, etc.) capable of performing graphics operations (e.g., matrix operations) faster than the processor <NUM>.

Referring now to <FIG>, the compute device <NUM>, in some embodiments, may utilize a dual in-line memory module (DIMM) architecture <NUM>. In the architecture <NUM>, multiple dies of the memory media <NUM> are connected with a shared command address bus <NUM>. As such, in operation, data is read out in parallel across all of the memory media <NUM> connected to the shared command address bus <NUM>. Data may be laid out across the memory media <NUM> in a configuration to allow reading the same column across all of the connected dies of the memory media <NUM>.

Further, generally, prior to being written to the memory media <NUM>, the data may be scrambled using a scrambling logic (e.g., residing in the memory controller <NUM>, media access circuitry <NUM>, inside memory of an accelerator device attached to a CXL bus, etc.) of the device <NUM>. Doing so ensures that the number of <NUM>'s and number of <NUM>'s written to the memory media <NUM> are relatively even for level power consumption and reduction of wear in the memory <NUM>. When the data is read out from the memory media <NUM>, such as part of a stochastic associative search, the data is descrambled via a descrambling logic.

Referring now to <FIG>, the compute device <NUM> may perform a stochastic associative search <NUM>, which is a highly efficient and fast way of searching through a large database of records and finding similar records to a given query record (key). For simplicity and clarity, stochastic associative searches <NUM>, scrambling and descrambling functions, and other processes are described herein as being performed with the memory <NUM>. However, it should be understood that the processes could alternatively or additionally be performed with the storage device <NUM>, depending on the particular embodiment. Given that the memory media <NUM> allows both row and column-wise reads with similar read latency, the memory media <NUM> is particularly suited to enabling efficient stochastic associative searches. In performing a search, values within the search key <NUM> are compared to the corresponding values in the database elements (e.g., vectors) <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> stored in the blocks of the memory media <NUM>. The compute device <NUM> determines the number of matching values between the search key <NUM> and each database element (e.g., vector), which is representative of a Hamming distance between the search key <NUM> and each database element (e.g., vector). The database elements (e.g., vectors) having the greatest number of matches (e.g., lowest Hamming distance) are the most similar results (e.g., the result set) for the stochastic associative search <NUM>.

As stated, the data is generally scrambled prior to being written to the memory media <NUM>. Each individual bit location in the memory media <NUM> may be associated with a scrambling state, which is indicative of a pattern used to scramble a bit value at that location. Typically, data is scrambled according to a row-based algorithm, and as such, a default way to read from a column would be to use a row-based descrambling algorithm on each bit in the column. However, with each execution of the algorithm, only one individual bit may be output at a time. Because this is time-consuming and generally inefficient, a column-aware scrambling and descrambling approach is desired.

Embodiments presented herein disclose a column-aware scrambling logic that works in row and column direction in the memory media <NUM>. As further described herein, a scrambling pattern of each bit in the memory media <NUM> is selected as a linear function (e.g., a linear-feedback shift register (LFSR) function) of the row and column indices. Further, a specialized circuit in the memory controller <NUM> or the media access circuitry <NUM> may directly advance the state of the scrambler to any row and column. Any scrambler that implements a linear function may be used to compute the scrambling pattern for the column. Advantageously, the techniques described herein allow scrambling and descrambling data in columns to occur without executing row-based scrambling algorithms per entry in a given column, e.g., any requested column may be read or written to more relatively quickly.

Referring now to <FIG>, a method <NUM> for performing a write operation using the scrambling techniques further described herein is shown. Although the steps shown are described relative to the memory <NUM> (e.g., via the memory controller <NUM> or the media access circuitry <NUM>), these steps are generally applicable to any crosspoint architecture and therefore may also be carried out, for example, in the data storage device <NUM>. As shown, the method <NUM> begins in block <NUM>, in which the compute device <NUM>, e.g., via the memory <NUM>, receives a request to perform a write operation of one or more bit values to the memory media <NUM>. The request may specify a column address in the memory media <NUM>.

In block <NUM>, the compute device <NUM> determines a scrambler state at each location associated with the destination column. Particularly, a location corresponds to a specific row and column index associated with the destination column. Further, a scrambler state is indicative of a pattern state (e.g., an <NUM>-bit pattern, <NUM>-bit pattern, etc.) used to determine a pattern bit used in calculating a scramble value for that location (e.g., by a bitwise exclusive-OR operation of the pattern bit with the data bit to be written to that location). The compute device <NUM> may determine the scrambler state using a linear function of the respective location in the column. An example of such a linear function is a Galois LFSR function using some non-zero initial state.

For example, in block <NUM>, the compute device <NUM> may compute a pattern bit using a consistent function. For example, the compute device <NUM> may use a lookup table having arbitrary entries using the state as input and the pattern bit as output.

For instance, consider a logical arrangement of rows and columns of bits in the memory media <NUM>, in which each bit is labeled as (row index, column index):.

Each bit may be scrambled above by performing a bitwise exclusive-OR (XOR) operation with a scrambler pattern bit. During a read operation, the data can be recovered by performing a XOR operation with the same scrambler pattern bit.

A given scrambler state may be determined for each bit as a value of a given bit-size, such as <NUM>- or <NUM>-bits, as S(r,c). From S(r,c), a bit <NUM> of the state is taken as f(r,c) and used a scrambler pattern mask for a bit value, in which f(r,c) is equal to F(S(r,c)) where F(x) is a linear or non-linear function. A scrambler state for each bit location is depicted in abstract below:.

The scrambler pattern bit may be determined based on a function of the row and column, notated as f(r, c), depicted in the table below:.

In block <NUM>, the compute device <NUM> may advance to the next scrambler state using the linear function by one step (or by j steps). When moving across a row, the state S(r,c) can be updated to S(r, c+<NUM>) by advancing the LFSR by one step. The LFSR may also shift by j steps if needed. To do so, the compute device <NUM> may rotate the state bits to the right and perform an XOR operation with the state bits and a state bit <NUM>, based on a LFSR polynomial. Such approach may be applicable for all row and column indices. For example, a S(r, c+j) may be determined by rotating S(r, c) and performing an XOR operation on the state bit <NUM> based on the LFSR polynomial for j. A row may have data bits that are scrambled in sequence. The next row may start with the k-th state of the scrambler logic and continue (e.g., S(r + <NUM>, c) equals S(r, c+k). Consequently, when advancing down the column from one row to the next row, the state may be advanced by k steps. A step may be regarded as a multiplication of a square matrix by a column vector. Assume that A represents a Matrix, s = S(r, c) is a current LFSR state, and n=S(r, c+<NUM>) is the next LFSR state). The compute device <NUM> may jump N steps by multiplying by A raised to the power N (AN). In practice, A is a relatively sparse matrix, but because both A and AN are square matrices with the same dimensions, the hardware requirements for AN saturates quickly for arbitrarily large values of N.

Assume that AD is identical to an identity matrix I. The compute device <NUM> may calculate an A2j by multiplying Aj and Aj for any j. Further, the compute device <NUM> may jump an arbitrary N steps by multiplying the current state s by A<NUM>, A<NUM>, A<NUM>, A<NUM>,. A<NUM> while selecting whether to multiply each term based on the bits in the binary representation of N.

Doing so can be accomplished by performing a series of multiplications or doing so using a tree of multiplications. Turning briefly to <FIG>, a diagram <NUM> of performing a series of multiplications to calculate a new state by multiplying the current state by an arbitrary power of A is shown. And turning briefly to <FIG>, a diagram <NUM> of calculating the arbitrary power of A using a tree of multiplications is shown. Using a series approach (as illustrated in <FIG>) may allow the compute device <NUM> to perform multiplications over multiple clock cycles to reduce overall gate count compared to the tree of multiplications approach (as illustrated in <FIG>). However, each embodiment may be used to achieve the effect of column-aware scrambling. The circuits depicted in either diagram <NUM> or <NUM> may be used to calculate AC for an arbitrary column c.

Returning to <FIG>, in block <NUM>, the compute device <NUM>, for each of the one or more values, scrambles the value as a function of the determined scrambler state for the respective column location. For instance, to do so, in block <NUM>, the compute device <NUM> performs a bitwise operation, such as an XOR operation, on the bit value and the scrambler pattern bit to achieve the scrambled result. In block <NUM>, the compute device <NUM> writes the scrambled values to the respective column locations.

Referring now to <FIG>, a method <NUM> for performing a read operation on data written to a column in the memory media <NUM>. For example, method <NUM> may occur in instances in which the compute device <NUM> receives a stochastic associative search request on a portion of data in the memory media <NUM>. As shown, the method <NUM> begins in block <NUM>, in which the compute device <NUM> receives a request to perform a read operation to read values from a specified column in the memory media <NUM>.

In block <NUM>, the compute device <NUM> determines a scrambler state at each location in the specified column. For instance, in block <NUM>, the compute device <NUM> computes a pattern bit of the respective location in the column. And in block <NUM>, the compute device <NUM> advances to the next scrambler state using the linear function. These steps may be carried out similar to that of blocks <NUM>, <NUM>, and <NUM> method <NUM>. For example, to descramble a given column c, the compute device <NUM> jumps to an arbitrary state that is c steps from the starting LFSR state. More particularly, the compute device <NUM> calculates a S(<NUM>, c) by multiplying AC and S(<NUM>, <NUM>). Thereafter, the compute device <NUM> traverses down the column by advancing the row offset, e.g., Ak, where k is some arbitrary positive integer. Where XOR gates can implement matrix A, similar logic may implement a multiplication by matrix B = Ak for each bit in the column on successive rows. Such logic may be used to advance by k steps at a time to get a scrambler pattern for the column, where k is a positive integer.

In block <NUM>, the compute device <NUM> descrambles, at each location, the value at the location as a function of the determined scrambler state for the respective location. Particularly, in block <NUM>, the compute device <NUM> performs a bitwise operation using the scrambler pattern bit and the value in the respective location. The scrambler pattern bits are used in an XOR operation with the scrambled column data bits to recover the original data bits. In block <NUM>, the compute device <NUM> outputs the descrambled values from each location of the column.

Claim 1:
A device (<NUM>) comprising:
a memory (<NUM>) comprising a matrix storing individually addressable bit data, the matrix formed by a plurality of rows and a plurality of columns;
circuitry (<NUM>) connected to the memory, wherein the circuitry is configured to
receive a request to perform a write operation of one or more bit values to one of the plurality of columns;
determine a plurality of scrambler states, one respective scrambler state of the plurality of scrambler states being a scrambler state that is determined at each location in the one of the plurality of columns, the location corresponding to a respective row and column index of the one of the plurality of columns and the scrambler state being indicative of a pattern used to determine a value at the respective column location, wherein to determine the scrambler state at each location comprises to compute a pattern bit of the respective location of the row and column index using a linear function of the row and column index;
scramble each of the bit values as a function of the respective scrambler state for the respective column location; and
write the scrambled values to each respective column location in the one of the plurality of columns in one mode of operation.