Patent Description:
In a shared memory multi-core processor with a separate cache memory for each processor, it is possible to have many copies of shared data: one copy in the main memory and one in the local cache of each processor that requested a copy of the data. When one of the data copies is changed, the other copies must reflect that change.

Cache coherence is the uniformity of shared resource data that requires multiple local caches. When clients (e.g., processor cores) in a system maintain local caches of a common memory resource, problems may arise with incoherent data, e.g., the local caches have different values of a single address location.

An example conventional architecture <NUM> for implementing cache coherence is shown in <FIG>. Each processor core <NUM>-<NUM> through <NUM>-M (hereinafter referred to individually as a processor core <NUM> and collectively as processor cores <NUM> for simplicity purposes) is associated with a corresponding local cache <NUM>-<NUM> through <NUM>-M (hereinafter referred to individually as a local cache <NUM> and collectively as local caches <NUM> for simplicity purposes). All core processors <NUM> and their corresponding local caches <NUM> access a shared memory <NUM>.

As the memory <NUM> is shared by the multiple processor cores <NUM> (and their respective local caches <NUM>), when accessing the shared memory <NUM>, a processor core (e.g., the core <NUM>-<NUM>) generally needs to copy a data block from the shared memory <NUM> to its own cache (e.g., the cache <NUM>-<NUM>) in order to accelerate data access. When multiple processor cores <NUM> access the shared memory <NUM>, a copy of the data block in the shared memory <NUM> exists in the local caches <NUM> of all such processor cores <NUM>. To maintain coherence of the copies, a cache coherence mechanism (CCM) <NUM> is required to manage data sharing.

Specifically, when performing a write (or store) operation on a shared data block or a copy of the shared data block, a write invalidate operation is sent to a processor core <NUM> that stores a copy of the shared data block, to avoid a data incoherence problem. To maintain cache coherence, the mechanism <NUM> records a cache status of a data block (or a data block interval). The cache status of the data block (or the data block interval) may include an access type and a sharer of the data block (or the data block interval).

The cache coherence mechanism <NUM> utilized in conventional architectures operates in a pipeline fashion. As such, a large portion of the processing time is spent on moving data from one area of the memory <NUM> to the local cache(s) <NUM>, and from one local cache <NUM> to another. In addition, the conventional architecture of caching as shown <FIG> is static by nature and therefore, certain inefficiencies occur as the static pipeline operation does not absolutely fit every use-case.

The limitation of a shared memory resource can also be solved using a reconfigurable cache architecture. Typically, such architectures support dynamic cache partitioning at the hardware level. A reconfigurable cache architecture is typically designed to allow core processors to dynamically allocate cache resource while guaranteeing strict cache isolation among the real-time tasks.

Reconfigurable cache architectures mainly target for power reduction by using direct addressing mapping. However, such architectures do not improve the latency of memory access.

There exist methods for cache management and conflict detection, for example as described in <CIT>, hereinafter referred to as Horn. However, where Horn describes determining a target cache segment based on one or more parameters of a target of a memory access command, determined from the memory access command, for example a volume identifier of a disk and an address range that is local to the target volume of the disk, Horn does not describe computing a deterministic function based on one or more access parameters that are related to an originator of the memory access command, for example a process ID.

Thus, it would be advantageous to provide a processing architecture that overcomes the deficiencies noted above.

A summary of several example embodiments of the disclosure follows. This summary is provided for the convenience of the reader to provide a basic understanding of such embodiments and does not wholly define the breadth of the disclosure. This summary is not an extensive overview of all contemplated embodiments, and is intended to neither identify key or critical elements of all embodiments nor to delineate the scope of any or all aspects. Its sole purpose is to present some concepts of one or more embodiments in a simplified form as a prelude to the more detailed description that is presented later. For convenience, the term "some embodiments" may be used herein to refer to a single embodiment or multiple embodiments of the disclosure.

Some embodiments disclosed herein include a method for cache coherency in a reconfigurable cache architecture. The method comprises receiving a memory access command, wherein the memory access command includes at least an address of a memory to access; determining at least one access parameter based on the memory access command, wherein the at least one access parameter includes at least one of: a process ID, a processing core ID, a thread ID, and a cache bit; computing a deterministic function over the at least one access parameter and the address to achieve cache coherency; and determining a target cache bin for serving the memory access command based in part on an outcome of computing the deterministic function. The reconfigurable cache architecture is distributed over a plurality of separate physical cache nodes, coupled to the memory.

Some embodiments disclosed herein include a reconfigurable cache architecture, comprising: a memory; and a plurality of cache nodes coupled to the memory, wherein each cache node is partitionable to a plurality of cache bins, wherein access to any cache bin of the plurality of cache bins is determined based on at least one access parameter, wherein the at least one access parameter includes at least one of: a process ID, a processing core ID, a thread ID, and a cache bit, and comprises computing a deterministic function over the at least one access parameter to achieve cache coherency and an address of a memory to access.

The subject matter disclosed herein is particularly pointed out and distinctly claimed in the claims at the conclusion of the specification. The foregoing and other objects, features and advantages of the invention will be apparent from the following detailed description taken in conjunction with the accompanying drawings.

In general, statements made in the specification of the present application do not necessarily limit any of the various claimed embodiments. Moreover, some statements may apply to some inventive features but not to others. In general, unless otherwise indicated, singular elements may be in plural and vice versa with no loss of generality. In the drawings, like numerals refer to like parts through several views.

<FIG> illustrates an example schematic diagram of a processing architecture <NUM> demonstrating the operation of a reconfigurable cache in accordance with one embodiment.

The processing architecture <NUM> includes a processing circuitry <NUM> coupled to a memory <NUM> via an interface or bus <NUM>. An input/output (IO) and peripherals unit <NUM> is also connected to the interface or bus <NUM> to allow special functions, access to external elements, or both. The I/O and peripherals unit <NUM> may interface with a peripheral component interconnect (PCI) or PCI Express (PCIe) bus, co-processors, network controllers, and the like (not shown). It should be appreciated that PCIe bus enables connectivity to other peripheral devices.

The memory <NUM> is coupled to a plurality of cache nodes <NUM>-<NUM> through <NUM>-n (hereinafter referred to individually as a cache node or collectively as cache nodes for simplicity purposes). Each cache node <NUM> is configured to store data processed by the processing circuitry <NUM> and to load data to the processing circuitry <NUM>. Typically, access to the cache nodes <NUM> is performed through memory access commands, such as store (or write), load (or read). Each cache node <NUM> may be realized using high-speed static RAM (SRAM), dynamic RAM (DRAM), and the like. Each cache node <NUM> can be logically partitioned to a plurality of a cache bins (not shown in <FIG>), as is discussed in detail herein below.

The processing circuitry <NUM> may be any processing device or computational device, such as, but not limited to, a central processing unit (CPU), a field-programmable gate array (FPGA), a graphics processing unit (GPU), a coarse-grained reconfigurable architecture (CGRA), an application-specific integrated circuit (ASIC), a quantum computer, and so on. Typically, the processing circuitry <NUM> is a multi-core processor. It should be noted that the processing architecture <NUM> can further support a plurality of processing devices <NUM>, e.g., multiple CPUs, hybrid CPUs, and the like.

The processing circuitry <NUM> is realized as a reconfigurable processing architecture. Such an architecture may be realized as an array of logical elements and multiplexers (MUXs). The logical elements may include arithmetic logic units (ALUs) and functional units (FUs) configured to execute computing functions.

The processing circuitry <NUM> is configured to perform various processes to provide a configurable cache architecture which maintains cache coherency among the caches <NUM>-<NUM> through <NUM>-n. As such, the configurable cache architecture is enabled without any additional dedicated hardware. The processing circuitry <NUM> providing the configurable cache also executes the main programs designed for the processing architecture <NUM>. For example, the processing circuitry <NUM> may execute a computational machine learning process and run the cache coherency.

It should be appreciated that, by not using a dedicated hardware, low latency cache access and low power utilization by the processing architecture <NUM> is ensured. As such, the reconfigurable cache architecture, as disclosed herein, can be utilized to accelerate the operation of the processing circuitry <NUM> (e.g., a CPU, a FPGA, a GPU, an ASIC, etc.).

According to the disclosed embodiments, the cache coherency is achieved by determining the location of data in any of the nodes and their cache bins using a deterministic function computed over at least one access parameter. The access parameters are determined by the processing circuitry <NUM>. An access parameter includes at least one of a unitary identification (ID) representing, a physical entity, and a logical entity. Examples for such entities include, a process ID, a thread ID, a core ID, a cache bit, a source instruction point, a memory port ID, the memory access address, or a combination thereof. The type of the access parameter may be assigned based on the type of memory being accessed. For example, bins of shared memory may be accessed through, for example, at least one cache bit, while bins of local memory can be accessed through at least one process ID. The type of access parameter may be determined during compilation or at runtime.

The processing circuitry <NUM> is configured to receive a memory access command, to determine the access parameter, and to determine the target cache bin based on the access parameter and address designated in the memory access command. As a non-limiting example, a deterministic function, e.g., a hash function, a set of ternary content-addressable memory (TCAM) match rules, a combination thereof, and the like, is computed over the address and the access parameter is called to decide which cache bin of the cache nodes <NUM> maintains the data.

For example, a store command may be received at the processing circuitry <NUM> through the I/O and peripherals unit <NUM>. Such a command may include a data block and a memory address in which to save the data block. The processing circuitry <NUM> is configured to determine if the command is associated with, for example, a particular process. If so, the process ID of the process is used as an access parameter. A function computed over the address and process ID (serving as an access parameter) is used to determine the target cache bin for storing the data block. It should be noted that a thread-ID, a core-ID, a cache bit, and so on, can be used as an access parameter. For example, if the received stored command is associated with a particular thread, then a thread-ID will be utilized.

It should be appreciated that the system architecture <NUM> described hereinabove depicts a single computational device for the sake of simplicity, and that the architecture <NUM> can be equally implemented using a plurality of computational devices such as, e.g., CPUs, GPUs, combinations thereof, and so on.

In an embodiment, the processing circuitry <NUM> is configured to determine which of the cache nodes <NUM> should be partitioned, and is further configured to partition each node <NUM>. That is, the processing circuitry <NUM> is configured to determine how many bins to partition the cache node <NUM>, and the size of each partition. In an embodiment, the partitioning may be static, e.g., to a pre-defined number of bins having equal size. In another embodiment, the partitioning may be dynamic, where the allocation is based on the utilization of each cache bin. To this end, after each execution iteration, the utilization of each bin is measured, and based on the measured utilization, it is determined whether the bins' allocation should be modified. It should be noted that the measurement can be made after program termination or during runtime. For example, the size of popular bins may be increased, while the size of less popular bins is reduced. Further, the number of bins may be increased or decreased based on the measured utilization.

In certain embodiments, some cache nodes <NUM> may be statically partitioned, while other may be dynamically partitioned. It should be noted that, initially, the cache may be statistically partitioned, and as the program runs, the allocation of the bins may be dynamically modified.

In an embodiment, the cache address is divided among the cache bins. Each cache partition of the cache nodes <NUM> can be assigned a different logical or physical entity. For example, the cache node <NUM>-<NUM> can be partitioned into two cache bins, with one cache bin dedicated to a first process and the other cache bin dedicated to a second process of a program. Alternatively, the cache bin can be assigned to processor cores of the processing circuitry <NUM>. Other examples of entities that can be allocated cache bins include threads. A partitioning of a cache node to bins is further illustrated in <FIG>.

It should be appreciated that this list is only illustrative and not exhaustive of the many types of logical entities and physical entities that can be assigned to cache bins. It should be further appreciated that a cache bin may be any portion of a cache node.

<FIG> illustrate an example schematic diagram of a reconfigurable cache architecture <NUM>. In the example illustrated in <FIG>, a single cache node <NUM>-n is shown being dynamically partitioned to a number of bins <NUM>.

Specifically, as shown in <FIG>, the cache node <NUM>-n is initially partitioned to <NUM> cache bins <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM> and <NUM>-<NUM> having similar sizes. After a first execution iteration, during runtime or between runs, the partitioning of the node <NUM>-n is changed to include <NUM> bins <NUM>-<NUM> through <NUM>-<NUM> having similar sizes (<FIG>). After another execution iteration, during runtime or between runs, the partitioning of the node <NUM>-n changes to include <NUM> bins <NUM>-<NUM> through <NUM>-<NUM>, but with different sizes. As shown in <FIG>, the memory allocated to bin <NUM>-<NUM> is different than bin <NUM>-<NUM>.

The cache architecture <NUM> is distributed over multiple physical nodes where each node is further divided into one or more logical bins. A processing circuitry of each physical node may access all or part of the cache nodes.

As shown in <FIG>, a deterministic hash function <NUM> is utilized to determine a target cache. The function <NUM> is computed by the processing circuitry <NUM>. It should be appreciated that the reconfigurable cache architecture <NUM> enables a higher granularity of memory usage, therefore enhancing the system operation and improving runtime performance.

It should be further appreciated that the reconfigurable cache architecture <NUM> depicts a single cache node <NUM>-n and a number of <NUM> or <NUM> bins <NUM> merely for the sake of simplicity. The architecture <NUM> would typically include a plurality of cache nodes that can be partitioned into any number of cache bins.

In an embodiment, a memory cache bin <NUM> may perform atomic memory access commands. Such commands may load, conditionally modify, and thereafter store the value of memory at a location, as a single operation. It is to be appreciated that when multiple atomic access commands are executed in parallel from multiple memory ports, and performed sequentially at the cache bin, they provide a coherent view to all memory ports.

<FIG> shows an example schematic diagram of a reconfigurable cache architecture <NUM> coupled to I/O peripherals (I/O P) <NUM> according to an embodiment. In this configuration, input/output (IO) and peripheral units <NUM>-<NUM> through <NUM>-k (k is integer greater or equal to <NUM>) may include a PCI bus, a PCI Express (PCIe), one or more co-processors, one or more network controllers, and the like.

As shown herein, the memory access commands are issued by the I/O peripherals <NUM>. The processing circuitry <NUM> determines the target cache bin based in part on the received commands using a deterministic hash function <NUM>.

In this configuration, any data or control signal (e.g., ack signal) received from the target cache bin is mapped to the I/O peripheral <NUM> that issued the received command. The mapping is performed by a mapping function <NUM> that can be implemented as a deterministic hash function, as a set of ternary content- addressable memory (TCAM) match rules, a combination thereof, and the like. It should be noted that the memory access is directed to the local caches <NUM> in order to perform the memory operation.

<FIG> shows an example flowchart <NUM> of a method for cache coherency in a reconfigurable cache architecture. The reconfigurable cache architecture includes a plurality of cache nodes coupled to the memory, wherein each cache node is partitioned into a plurality of cache bins.

At S510, a memory access command is received. As mentioned above, the command may be to store (write) or load (read) data from the memory of a processing architecture. The command may be received via an interface such as, for example, the I/O peripherals unit <NUM>. A received command includes at least a target address to which data is to be stored or from which data is to be loaded. In a store command, the data to be stored is also included in the received command. The memory address should be within the address boundaries determined during compilation of the code of the main program.

At S520, at least one access parameter is determined. As noted above, an access parameter may include a process ID, a thread ID, a cache bit, a storage pointer, a process core ID, and so on. In an embodiment, the determination includes determining a logical or physical entity that the received command is associated with. Examples for physical entities are discussed in detail above.

In an embodiment, if the received command is executed as part of a dedicated process or thread (both are considered logical entities), then the process-ID or thread-ID will be considered as the access parameter. In another embodiment, if the received command is executed on a dedicated processing core (considered a physical entity), then the core-ID will be considered as the access parameter. In yet another embodiment, if the received command is to access a shared memory (considered as a physical entity), then a cache bit will be considered as the access parameter.

In some embodiments, load/store attributes are determined. Such attributes include, for example, never cache certain values, always cache certain values, always check certain values, and so on. Furthermore, ordering of allocation, along with the access synchronization in the grid allows larger pipelines and higher throughput while simplifying mechanisms. Such attributes are advantageous for volatile memory as well as for locking mechanisms.

At S530, a target cache bin to access is determined. The determination is performed using a deterministic function computed over the access parameter and the address designated in the received request. According to another embodiment, the deterministic function is connected to the grid so that the determination is made using the same interfaces.

It should be noted that data is stored to, or loaded from, the target cache bin as determined by the deterministic function.

In an embodiment, S530 includes gathering the statistics about the target cache bin being accessed. For example, the number of the bin, the frequency of accessing the same bin, and the size of the data being written or read are determined. These gathered statistics can be utilized to dynamically change the partitions of the bins.

In S540, it is checked whether additional system calls have been received and if so, execution continues with S510; otherwise, execution terminates.

The embodiments disclosed herein can be implemented as hardware, firmware, software, or any combination thereof. The application program may be uploaded to, and executed by, a machine comprising any suitable architecture. Preferably, the machine is implemented on a computer platform having hardware such as one or more central processing units ("CPUs"), a memory, and input/output interfaces.

The computer platform may also include an operating system and microinstruction code. The various processes and functions described herein may be either part of the microinstruction code or part of the application program, or any combination thereof, which may be executed by a CPU, whether or not such computer or processor is explicitly shown.

Claim 1:
A method for cache coherency in a reconfigurable cache architecture (<NUM>), comprising:
receiving (S510) a memory access command, wherein the memory access command includes at least an address of a memory to access;
determining (S520) at least one access parameter based on the memory access command, wherein the at least one access parameter includes at least one of: a process ID, a processing core ID, a thread ID, and a cache bit;
computing a deterministic function (<NUM>) over the at least one access parameter and the address to achieve cache coherency; and
determining (S530) a target cache bin for serving the memory access command based in part on an outcome of computing the deterministic function;
wherein the reconfigurable cache architecture is distributed over a plurality of separate physical cache nodes (<NUM>-<NUM> - <NUM>-n), coupled to the memory.