Patent Description:
Cache memory is a memory area used to store copies of data from a main memory area. Cache memory is typically smaller and faster than the main memory and in some computerized systems is used to reduce the average time it takes a hardware processor to access data from the main memory area. It is common practice to store in cache memory copies of data from frequently accessed locations in the main memory. A cache memory may store copies of computer instructions executed by the hardware processor. A cache memory may store copies of program data of one or more programs executed by the hardware processor.

When a copy of data from a memory location of the main memory is stored in the cache memory it is said that the memory location is cached. Access time to a cached memory location is significantly faster than access time to a memory location that is not cached, thus to reduce average access time to memory there is a need to increase the likelihood that when the hardware processor accesses a memory location the memory location is already cached. Access to a cached memory location is also called a cache hit. To reduce average access time to memory there is a need to increase the likelihood of a cache hit.

There exists an assumption that the likelihood of referencing a memory location is higher when some other memory location near the memory location was referenced shortly beforehand. For example, the sequential nature of computer instructions increases the likelihood that consecutive computer instructions reside consecutively in main memory, and thus after referencing a memory location storing one computer instruction the hardware processor will reference a consecutive memory location storing a consecutive computer instruction. Similarly, when processing a data object stored consecutively in a main memory, after accessing one element of the data object there is an increased likelihood the hardware processor will access another element of the data object. This assumption is sometimes referred to as "spatial locality".

In some systems the cache memory is divided into a plurality of cache lines, each for storing a copy of a physically consecutive part of the main memory. Each cache line may be associated with a different part of the main memory; two consecutive cache lines may store copies of two separate (non-consecutive) areas of the main memory. Under the assumption of spatial locality, when the hardware processor accesses a memory location that is not cached (also called a cache miss), when copying data from the memory location into a cache line additional data from nearby locations immediately preceding, and additionally or alternatively immediately following the memory location, are copied into the cache line as there is a high likelihood that the hardware processor will access at least one of the nearby locations shortly after accessing the memory location. Under the assumption of spatial locality, copying data from the memory location and its vicinity increases the likelihood of a cache hit in a future access to memory. According to some cache management methods, when a hardware processor accesses a new memory location that is not cached and the cache memory is full, one or more of the cache memory's cache lines is released and data is copied from the new memory location and its vicinity into one or more of the released cache lines.

In computer programming, a process is an active computer program, i.e. a computer program under execution and comprises, in addition to program code, also a memory stack of the process, a program instruction counter etc. In computer programming, an execution thread is a set of instructions of a computer program that can be scheduled and executed by one or more hardware processors independently of other parts of the computer program. A thread may be seen as a lightweight process that can be managed independently by a scheduler. When a plurality of execution threads, possibly of more than one computer program, access a common main memory, each execution thread may access a different location of the main memory. When the plurality of execution threads execute concurrently, spatial locality may be reduced as there may be consecutive accesses to the main memory from more than one execution thread, each accessing a different location of the main memory. <CIT> discloses storing data from different threads in separate locations of a cache line.

It is an object of some embodiments disclosed herein to describe a system and a method for caching memory.

According to a first aspect, a method for caching memory comprises: caching, in a cache line of a cache memory for accessing a physical memory area connected to at least one hardware processor, the cache memory comprising a plurality of cache lines each having a cache line amount of bits, at least two data values, where each data value is of one of at least two ranges of application memory addresses, wherein each range of application memory addresses is associated with one of a set of execution threads having an identified order of threads and executed by the at least one hardware processor, by: organizing a plurality of sequences of consecutive address sub-ranges, each sequence associated with one of the set of execution threads and consisting of a consecutive sequence of application memory address sub-ranges of the respective range of application memory addresses associated with the execution thread, each application memory address sub-range having an identified amount of memory bits less than the amount of cache line bits, in an interleaved sequence of address sub-ranges by alternately selecting, for each execution thread in the identified order of threads, a next address sub-range in the respective sequence of address sub-ranges associated therewith; generating a mapping of the interleaved sequence of address sub-ranges to a range of physical memory addresses in order of the interleaved sequence of address sub-ranges; and when an execution thread of the set of execution threads accesses an application memory address of the respective range of application memory addresses associated thereof: computing a target memory address according to the mapping using the application memory address; and storing the at least two data values in one cache line of the plurality of cache lines by accessing the physical memory area using the target memory address. Interleaving the plurality of sequences of consecutive sequences of application memory address sub-ranges when mapping the plurality of sequences to a range of physical memory addresses allows sharing at least one physical page of memory between the set of execution threads and thus storing the at least two data values, that are each associated with one of the set of execution threads, in one cache line. Storing the at least two data values that are each associated with one of a set of execution threads in a one cache line increases the likelihood of a cache hit when executing the set of execution threads, thus reducing the average access time to memory.

According to a second aspect, a system for caching memory comprises at least one hardware processor adapted for: caching, in a cache line of a cache memory for accessing a physical memory area connected to at least one other hardware processor, the cache memory comprising a plurality of cache lines each having a cache line amount of bits, at least two data values, where each data value is of one of at least two ranges of application memory addresses, wherein each range of application memory addresses is associated with one of a set of execution threads having an identified order of threads and executed by the at least one other hardware processor, by: organizing a plurality of sequences of consecutive address sub-ranges, each sequence associated with one of the set of execution threads and consisting of a consecutive sequence of application memory address sub-ranges of the respective range of application memory addresses associated with the execution thread, each application memory address sub-range having an identified amount of memory bits less than the amount of cache line bits, in an interleaved sequence of address sub-ranges by alternately selecting, for each execution thread in the identified order of threads, a next address sub-range in the respective sequence of address sub-ranges associated therewith; generating a mapping of the interleaved sequence of address sub-ranges to a range of physical memory addresses in order of the interleaved sequence of address sub-ranges; and when an execution thread of the set of execution threads accesses an application memory address of the respective range of application memory addresses associated thereof: computing a target memory address according to the mapping using the application memory address; and storing the at least two data values in one cache line of the plurality of cache lines by accessing the physical memory area using the target memory address.

With reference to the first and second aspects, in a first possible implementation of the first and second aspects for at least one of the set of execution threads the respective range of application memory addresses associated thereof is one of: the range of physical memory addresses, and a range of virtual memory address. Optionally, the target memory address is a target physical memory address. Optionally, the target memory address is a linear virtual memory address. Optionally, the method further comprises: computing another target physical memory address using the linear virtual memory address; and accessing the physical memory area using the other target physical memory address instead of using the target memory address.

With reference to the first and second aspects, in a second possible implementation of the first and second aspects accessing the physical memory area using the target memory address comprises retrieving a cache line amount of bits from the physical memory area. Optionally, the execution thread accesses the application memory address of the respective range of application memory addresses to retrieve the identified amount of memory bits from the physical memory area. Retrieving a cache line amount of bits from the physical memory area stores the at least two data values that are each associated with one of a set of execution threads in a one cache line, increasing the likelihood of a cache hit when executing the set of execution threads, thus reducing the average access time to memory.

With reference to the first and second aspects, in a third possible implementation of the first and second aspects each of the set of execution threads has an identification value according to the identified order of threads. Optionally, computing the target memory address comprises: inserting into a binary representation of the target memory address an identified amount of lower bits of the application memory address, and inserting into the binary representation of the target memory address a lane value indicative of the respective identification value of the execution thread. Inserting into the binary representation of the target memory address an identified amount of lower bits of the application memory address and a lane value indicative of the respective identification value of the execution thread facilitates identifying an offset in the cache line that is associated with the execution thread, and not associated with another execution thread in the same cache line. Optionally, the physical memory area is organized in a plurality of physical memory pages, each having an amount of physical page bytes. Optionally, the identified amount of lower bits is a base <NUM> log of the amount of physical page bytes. Optionally, the identified amount of lower bits of the application memory address are inserted into a low part of the binary representation of the target memory address. Optionally, the lane value is inserted into the binary representation of the target memory address immediately following the identified amount of lower bits of the application memory address. Optionally, computing the target memory address further comprises rotating the identified amount of lower bits of the application memory address and the lane value. Optionally, rotating the identified amount of lower bits and the lane value is rotating to the right by a base-<NUM> log of the identified amount of memory bits. Inserting the identified amount of lower bits of the application memory address into the low part of the binary representation of the target memory address, inserting the lane value immediately following the identified amount of lower bits of the application memory address, and rotating the identified amount of lower bits and the lane value allow identifying the offset in the cache line that is associated with the execution thread using existing caching circuitry, reducing cost of implementation of a cache according to the present disclosure compared to using bespoke caching circuitry.

With reference to the first and second aspects, in a fourth possible implementation of the first and second aspects the set of execution threads are selected from a plurality of execution threads executed by the at least one hardware processor. Optionally, the set of execution threads is selected from the plurality of execution threads according to a plurality of statistical values collected while executing the plurality of execution threads. Optionally, the plurality of statistical values comprises at least one of: an amount of accesses to an application memory address, an order of accesses to a plurality of application memory addresses, an association between an application memory address and a thread identification value, and an amount of application memory in an application memory area. Selecting the set of execution threads according to the plurality of statistical values collected while executing the plurality of execution threads increases the likelihood of a cache hit when executing the set of execution threads, thus reducing the average access time to memory.

With reference to the first and second aspects, in a fifth possible implementation of the first and second aspects the method further comprises: selecting from the plurality of execution threads another set of execution threads having another order of threads, each associated with one of at least two other ranges of application memory addresses; organizing another plurality of sequences of consecutive address sub-ranges, each sequence associated with one other of the other set of execution threads and consisting of another consecutive sequence of application memory address sub-ranges of the respective range of application memory addresses associated with the other execution thread, each other application memory address sub-range having another identified amount of memory bits less than the amount of cache line bits, in another interleaved sequence of address sub-ranges by alternately selecting, for each other execution thread in the identified other order of threads, another next address sub-range in the respective other sequence of address sub-ranges associated therewith; and generating another mapping of the other interleaved sequence of address sub-ranges to the range of physical memory addresses in the other order of the interleaved sequence of address sub-ranges. Optionally, the cache memory comprises a plurality of cache bins and the range of physical memory addresses is associated with one of the plurality of cache bins. Optionally, the range of physical memory addresses comprises a first subrange of the range of physical memory addresses, associated with a first cache bin of the plurality of cache bins, and a second subrange of the range of physical memory addresses, associated with a second cache bin of the plurality of cache bins. Optionally the mapping of the interleaved sequence of address sub-ranges is to the first subrange of the range of physical memory addresses, and the other mapping of the other interleaved sequence of address sub-ranges is to the second subrange of the range of physical memory addresses. Optionally, the first cache bin comprises a first plurality of cache lines each having a first amount of cache bits and the second cache bin comprises a second plurality of cache lines each having a second amount of cache bits. Associating each of two or more sets of execution threads with one of a plurality of cache bins increases the likelihood of a cache hit when executing the plurality of execution threads. Using a plurality of cache bins having different amounts of cache bits in their respective cache lines further increases the likelihood of cache hit when executing the plurality of execution threads, as memory of each set of execution threads is interleaved according to an amount of cache bits the increases a likelihood of a cache hit when executing the set of execution threads.

With reference to the first and second aspects, in a sixth possible implementation of the first and second aspects the at least one other hardware processor is a configurable computation grid.

Unless otherwise defined, all technical and/or scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which embodiments. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of embodiments, exemplary methods and/or materials are described below.

Some embodiments are herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of embodiments. In this regard, the description taken with the drawings makes apparent to those skilled in the art how embodiments may be practiced.

As used herewithin, the term "temporal locality" refers to a concept that a memory area that is referenced at one point in time will be referenced again sometime in the near future after the one point in time. As described above, a cache line holds a copy of a physically consecutive memory area of the main memory. Thus, when a sequence of memory accesses is temporally local, i.e. the sequence of memory accesses includes more than one access to a physically consecutive memory area within a relatively short period of time, the likelihood of a cache hit increases as after the first access to the memory area the memory area is cached, at least for some time.

According to some common methods for caching memory, a cache memory area has a plurality of equally sized cache lines each having a cache line amount of bits. When data is copied from the main memory to the cache memory, a cache line amount of physically consecutive bits are retrieved from the main memory and stored in a cache line of the cache memory area. A typical execution thread is associated with one or more ranges of application memory addresses. In some systems an application memory address is a physical memory address, however in many modern systems an application memory address is a virtual memory address and there exists a mapping between each application memory range of the execution thread and one or more ranges of physical memory addresses. When an execution thread accesses an application memory address, a physical memory address is computed according to the mapping and the main memory is accessed using the physical memory address.

According to common practice, a memory area is divided into pages, each having one of an identified set of amounts of bytes (known as page size). Also according to common practice, a cache line does not cross a page boundary, i.e. one cache line stores a copy of data values that have consecutive physical memory addresses in one page of memory.

When consecutive accesses to the main memory are not spatially local, the amount of cache hits is reduced, increasing an average time for accessing memory. When a set of execution threads use a shared physical memory area and are executed concurrently, a likelihood of a cache hit increases as more than one of the set of execution threads may access a cached part of the shared physical memory area. However, in some systems memory usage patterns are such that one physical memory page is not shared by more than one execution thread, for example when the execution threads do not use shared memory. As a result, when a plurality of execution threads is executed concurrently and do not use a shared memory area, spatial locality may be reduced as there may be consecutive accesses to the main memory from more than one execution thread, each accessing a different physical page of the main memory. There is a need to increase the amount of cache hits when concurrently executing a plurality of execution threads.

For brevity, henceforth the term "thread" is used to mean an execution thread, and the terms are used interchangeably.

The present disclosure, according to the invention proposes increasing a likelihood of a cache hit by storing in one cache line copies of data values accessed by more than one concurrently executed threads. Increasing a likelihood of a cache hit reduces an average access time to memory. To store in one cache line copies of data values accessed by more than one concurrently executed threads when the more than one concurrently executed threads do not use a shared memory area, the present disclosure proposes in some embodiments sharing at least one physical page of memory between a set of concurrently executed threads. Optionally, the at least one physical page of memory is one of a group of physically contiguous physical pages of memory having a common page size.

In such embodiments, the present disclosure proposes interleaving on the at least one physical page of memory data associated with one of the set of concurrently executed threads with other data associated with another of the set of concurrently executed threads, such that copies of at least two data values comprising at least one data value associated with the one thread and at least another data value associated with the other thread, may be copied into one cache line. By interleaving the data and the other data on the at least one physical page, in such embodiments the at least two data values are stored in the at least one physical page of memory and each is accessed by one of the set of concurrently executed threads using a common cache line.

To interleave data associated with the one thread and other data associated the other thread, in some embodiments the present disclosure proposes organizing a plurality of sequences of consecutive address sub-ranges in an interleaved sequence of address sub-ranges, where each sequence of consecutive address sub-ranges is associated with one of a set of threads having an identified order of threads, and consists of a consecutive sequence of application memory address sub-ranges of a range of application memory addresses associated with the thread. Optionally, the plurality of sequences of consecutive address sub-ranges is organized in the interleaved sequence of address sub-ranges by alternately selecting, for each of the set of threads, in the identified order of threads, a next address sub-range in the respective sequence of consecutive address sub-ranges associated with the thread.

Reference is now made to <FIG>, showing a block diagram schematically representing an exemplary interleaving 100A of address sub ranges, according to some embodiments. It should be noted that example 100A is a non-limiting example, representing an exemplary interleaving of four sequences of application memory address sub-ranges. It should be emphasized that the methods and systems described in the present disclosure are not limited to embodiments having four threads and may be applied to any other amount of threads and ranges of application memory address sub-ranges.

In some embodiments, a set of four threads is optionally identified in a plurality of threads executing on one or more hardware processors. Optionally, the set of four threads has an identified order of threads. Optionally, each of the set of four threads is associated with a range of application memory addresses, for example application address range <NUM>, application address range <NUM>, application address range <NUM> and application address range <NUM>, in the identified order of threads. Optionally, each range of application memory addresses comprises a sequence of consecutive address sub-ranges, where each sequence of consecutive address sub-ranges consists of a sequence of application memory address sub-ranges of the respective range of application memory addresses. In this example, application address range <NUM> comprises the sequence of sub-range 110A, sub-range 110B, sub-range 110C and sub-range 110D. Similarly, in this example application address range <NUM> comprises the sequence of sub-range 111A, sub-range 111B, sub-range 111C and sub-range 111D, application address range <NUM> comprises the sequence of sub-range 112A, sub-range 112B, sub-range 112C and sub-range 112D, and application address range <NUM> comprises the sequence of sub-range 113A, sub-range 113B, sub-range 113C and sub-range 113D.

According to some embodiments, the present disclosure proposes organizing application address range <NUM>, application address range <NUM>, application address range <NUM> and application address range (henceforth referred to collectively as the plurality of application address ranges) in interleaved sequence of address sub-ranges <NUM>. The plurality of application address ranges is organized in interleaved sequence <NUM> by alternately selecting from each of the plurality of application address ranges, in the identified order of threads, a next address sub-range. Thus, in this example, sub-range 110A of application address range <NUM> is added first to interleaved sequence <NUM>, followed by sub-range 111A of application address range <NUM>, then sub-range 112A of application address range <NUM>, and then sub-range 113A of application address range <NUM>. The sequence of sub-range 110A, sub-range 111A, sub-range 112A and sub-range 113A may be considered one group of interleaved sub-ranges. Next, sub-range 110B of application address range <NUM> is added, followed by sub-range 111B of application address range <NUM>, then sub-range 112B of application address range <NUM>, and then sub-range 113B of application address range <NUM>, and so forth. Similarly, the sequence of sub-range 110B, sub-range 111B, sub-range 112B and sub-range 113B may be considered one other group of interleaved sub-ranges.

In such embodiments, interleaved sequence of address sub-ranges <NUM> is mapped to a range of physical memory addresses, in order of interleaved sequence of address sub-ranges <NUM>. For example, interleaved sequence <NUM> is mapped to mapped physical range <NUM> of physical memory addresses. In this example, mapped physical range <NUM> consists of a sequence of consecutive sub-ranges of physical memory addresses, for example including mapped physical sub-range <NUM>-<NUM>, mapped physical sub-range <NUM>-<NUM>, mapped physical sub-range <NUM>-<NUM>, and mapped physical sub-range <NUM>-N. In this example, sub-range 110A is mapped to mapped physical sub-range <NUM>-<NUM>; sub-range 111A which is consecutive to sub-range 110A in interleaved sequence <NUM> is mapped to mapped physical sub-range <NUM>-<NUM> which is consecutive to mapped physical sub-range <NUM>-<NUM> in mapped physical range <NUM>. Similarly, in this example sub-range 112A is mapped to mapped physical sub-range <NUM>-<NUM>, sub-range 113A is mapped to mapped physical sub-range <NUM>-<NUM>, and so forth in order of interleaved sequence <NUM> until sub-range <NUM>-D is mapped to mapped physical sub-range <NUM>-N.

For brevity, henceforth the term "memory" is used to mean "physical memory area" unless otherwise stated, and the terms are used interchangeably.

Optionally, data values are stored in physical memory according to the mapping between interleaved sequence <NUM> and mapped physical range <NUM>. Reference is now made also to <FIG>, showing a block diagram schematically representing an extension 100B of interleaving 100A, according to some embodiments. In this example, data of sub-range 110A is stored in physical memory area <NUM> at a location addressed by mapped sub-range physical <NUM>-<NUM>, to which sub-range 110A is mapped. Similarly, data of sub-range 111A is stored in memory <NUM> at another location addressed by mapped physical sub-range <NUM>-<NUM>, to which sub-range 111A is mapped. As mapped sub-range physical <NUM>-<NUM> is consecutive to mapped sub-range physical <NUM>-<NUM>, data of sub-range 111A is consecutive to data of sub-range 110A in memory <NUM>. Similarly, data of sub-range 112A is consecutive to data of sub-range 111A in memory <NUM>, followed by data of sub-range 113A, with data of sub-range 110B consecutive to data of sub-range 113A, data of sub-range 111B consecutive to data of sub-range 110B and so forth. Thus, in this example, memory associated with four threads is interleaved when stored in a common page of physical memory. Further in this example, to store four pages of memory, each associated with one of the four threads, four common pages of physical memory are needed, each storing some of the respective memory associated with one of the four threads, interleaved therebetween.

Optionally, mapped physical range <NUM> spans more than one physically contiguous page of memory in memory <NUM>. Optionally, mapped physical range <NUM> spans a group of physically contiguous pages of physical memory in memory <NUM>, having a common page size.

Optionally, a cache is used when accessing memory <NUM>, addressed by mapped physical range <NUM> of physical memory addresses. Reference is now made also to <FIG>, showing a block diagram schematically representing another extension 100C of interleaving 100A and interleaving 100B, according to some embodiments. In this example, cache <NUM> comprises a plurality of cache lines, including cache line <NUM>-<NUM>, cache line <NUM>-i and cache line <NUM>-m, where m denotes an amount of cache lines in the plurality of cache lines of cache <NUM>. In this example, when a thread associated with application address range <NUM> accesses data in sub-range 111A which is mapped to mapped physical sub-range <NUM>-<NUM>, physical memory addressed by mapped physical sub-range <NUM>-<NUM> is copied into cache <NUM> if not already there. As memory is copied into cache <NUM> in full cache lines, an entire cache line comprising data from physical memory at location mapped physical sub-range <NUM>-<NUM> is retrieved from memory <NUM> and stored in one cache line, for example cache line <NUM>-i. In this example, data from mapped physical sub-range <NUM>-<NUM>, mapped physical sub-range <NUM>-<NUM>, mapped physical sub-range <NUM>-<NUM> and mapped physical sub-range <NUM>-<NUM> are copied as one cache line into cache line <NUM>-i. As long as cache line <NUM>-i is not reused to cache another area of memory <NUM>, when another thread associated with application address range <NUM> accesses data in sub-range 112A, the access may be served by cache line <NUM>-i. Thus, according to the invention copying from memory <NUM> into cache line <NUM>-i stores in cache line <NUM>-i at least two data values where each is of one of at least two ranges of application memory addresses, where each range of application memory addresses is associated with one of the set of execution threads and is accessed thereby.

<CIT>, Publication No. <CIT>et al, applicants), henceforth Tian, describes a system where two threads each access one of two data values stored in a single cache line of a cache memory. However, in Tian this condition is described as undesirable and the teachings of Tian are directed towards detecting this condition. Tian does not teach how to deliberately store two data values in a single cache line, where each of the two data values are associated with one of a plurality of executable threads. More specifically, Tian does not refer to an identified order among the plurality of executable threads, nor does Tian describe interleaving memory ranges.

Optionally, to access an application memory address, a target memory address is computed using the application memory address, according to the mapping. Optionally, the target memory address is a target physical memory address. For example, to access an application memory address in application address sub-range 111A, the target memory address may be a target physical memory address in mapped physical sub-range <NUM>-<NUM>. Optionally, the target memory address is a linear virtual address, i.e. an address mapped without segmentation, and to access the physical memory area another target physical memory address is computed using the linear virtual memory address.

Optionally, the set of threads are selected from the plurality of execution threads according to a plurality of statistical values, collected while executing the plurality of execution threads, for example an amount of accesses to an application memory address and an order of accesses to a plurality of application memory addresses. Using a plurality of statistical values to select the set of threads facilitates mapping a plurality of application memory address ranges of the set of threads to one or more common physical pages using interleaving as described above such that a likelihood of a cache hit is increased, thus reducing an average memory access time.

In addition, in some embodiments the above described method may be repeated for one or more other sets of threads, such that memory associated with each set of threads is interleaved in one or more physical memory pages. Optionally, each of the other sets of threads are selected from the plurality of threads according to the plurality of statistical values.

In the field of computing, a page table is a data structure used by an operating system to store a mapping between virtual addresses of memory pages and the respective physical addresses of the memory pages. Each mapping between a virtual address of a page and a physical address of the page is known as a page table entry (PTE). A PTE typically comprises an indication whether the memory page referenced thereby has been modified, also known as being dirty. There exists a practice, in some systems, to organize virtual memory translation in a hierarchy of page tables, where each PTE in a high level page table points to one of a plurality of lower level page tables. In such systems, the virtual address may be segmented, where each segment of the virtual address is used as an index of a page table in one of the hierarchies. Finding a translation of a virtual memory address to a physical memory address in a page table of such systems involves reading one or more memory locations, one for each of the hierarchy of page tables. This process is also known as a page walk.

There exist systems where more than one page size is supported simultaneously, such that one thread executing in a system uses physical memory having a first page size and another thread executing in the system uses physical memory having a second page size which is different than the first page size. In some existing systems the size of a page referenced by a PTE of a page table is implicit, where each PTE in the page table, or in an identified area of the page table, references an identified page size. The page size may be identified according to the level of the page table in its respective hierarchy. In such systems, when a system supports more than one page size there may exist more than one page table or the page table may be divided into distinct areas. In some systems, a system supports more than one page size by having more than one level in the page table hierarchy. In some systems, each process executing in the system has their own page table, or their own page table hierarchy.

A translation lookaside buffer (TLB) is a memory cache that stores recent translations of virtual memory addresses to physical memory addresses and is used in some systems to reduce the time it takes to access a memory location. A TLB typically comprises a plurality of TLB entries, each comprising a translation of a virtual memory address to a physical memory address. In such systems, accessing a virtual memory address comprises searching a TLB for the virtual memory address and retrieving a respective physical memory address which is used to access memory. A TLB hit is when a virtual memory address is found in the TLB and a respective physical memory address is retrieved. When the virtual memory address is not found in the TLB this is known as a TLB miss. In such systems, when a TLB miss occurs when translating a virtual address, translation proceeds by looking for the virtual memory address in a page walk of the page table or hierarchy of page tables. After the physical memory address is determined by the page walk, the virtual address to physical address mapping is entered into the TLB. To reduce access time to memory there is a need to increase an amount of TLB hits. A common method of accessing a TLB involves computing a hash function using the virtual memory address. However, there may be a high amount of hash collisions, where multiple virtual memory addresses map to a common hash result. A hash collision when accessing the TLB causes eviction of the corresponding entry in the TLB, reducing utilization of the TLB. There is a need to reduce an amount of hash collisions in the TLB.

In some systems the TLB is organized in a hierarchy of TLBs. In systems where each supported page size requires a separate page table, there is also a need for a separate TLB for each page size, possible in more than one hierarchy of the TLB.

In some embodiments described herewithin, each of two sets of threads of the plurality of threads may use a different page size. In such embodiments, one or more first physical memory pages of a first set of threads of the plurality of threads has a first page size and one or more second physical memory pages of a second set of threads of the plurality of threads has a second page size where the first page size and the second page size are different.

To increase utilization of the TLB, in some embodiments the present disclosure additionally proposes using each TLB entry of the plurality of TLB entries to reference more than one contiguous physical page, and thus reference an effective physical page formed by the combination of the more than one contiguous physical page and having an effective physical address range. To do so, in such embodiments the present disclosure proposes encoding each PTE to reference the effective physical page consisting of the more than one contiguous physical page. Encoding in one PTE a reference to more than one physical memory page increases the likelihood of a TLB hit and reduces an amount of hash collisions in the TLB. Using one PTE to reference an effective physical page consisting of a set of memory pages interleaving memory associated with a set of threads further increases the likelihood of a TLB hit as the set of threads may be selected to increase temporal proximity of memory accesses.

To reference a set of memory pages in one TLB entry, the present disclosure proposes, in some embodiments, encoding in the PTE a hint indicative of an amount of contiguous physical memory pages referenced by the PTE. Optionally, the hint is encoded in one or more bits of a binary representation of the virtual address in the PTE. Encoding the hint in one or more bits of the binary representation of the virtual address in the PTE facilitates carrying the hint untranslated into a respective entry in the TLB, corresponding with the PTE, thus allowing one TLB entry to reference an effective physical address range consisting of more than one contiguous physical memory pages and allowing one TLB to support access to more than one effective page size of memory. Optionally, the page table comprises a separate PTE for each of the one or more contiguous physical memory pages. However, when an address in one of the more than one contiguous physical memory pages is accessed, a TLB entry reflecting an address translation for the address in the one page will be hit when accessing another address in another of the one or more contiguous physical memory pages.

In addition, in some embodiments, the present disclosure proposes that in a TLB, a first TLB entry references a first amount of contiguous physical memory pages each having a first page size and a second TLB entry references a second amount of contiguous memory pages each having a second page size. Thus, the first TLB entry references a first effective physical page having a size of the first amount multiplied by the first page size, and the second TLB entry references a second effective physical page having a size of the second amount multiplied by the second page size. Optionally, the first TLB entry references a first set of memory pages interleaving memory associated with one set of threads of the plurality of threads, and the second TLB entry references a second set of memory pages interleaving other memory associated with another set of threads of the plurality of threads.

In addition, in some embodiments the cache comprises a plurality of cache bins. Optionally, the physical memory is addressed by a plurality of distinct ranges of physical memory addresses. Optionally, each respective range of application addresses of each of a plurality of sets of threads, consisting of the set of threads and the one or more other sets of threads, is mapped to one of the plurality of distinct ranges of physical memory addresses. Optionally, each distinct range of physical memory addresses is associated with one of the plurality of cache bins. Thus, in such embodiments, each of the plurality of sets of threads is associated with one of the plurality of cache bins, and one or more memory accesses of a thread is served by the respective cache bin associated with the thread. Optionally, not all of the plurality of cache bins have a common cache line size, i.e. a cache line amount of bits of one of the plurality of cache bins is different from another cache line amount of bits of another of the plurality of cache lines. Using different cache line amount of bits for different cache bins allows using for each set of threads a cache line size according to a pattern of a plurality of memory accesses, thus increasing likelihood of a cache hit.

Before explaining at least one embodiment in detail, it is to be understood that embodiments are not necessarily limited in its application to the details of construction and the arrangement of the components and/or methods set forth in the following description and/or illustrated in the drawings and/or the Examples. Implementations described herein are capable of other embodiments or of being practiced or carried out in various ways.

Embodiments may be a system, a method, and/or a computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the embodiments.

A non-exhaustive list of more specific examples of the computer readable storage medium includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, and any suitable combination of the foregoing. A computer readable storage medium, as used herein, is not to be construed as being transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber- optic cable), or electrical signals transmitted through a wire.

Computer readable program instructions for carrying out operations of embodiments may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++ or the like, and conventional procedural programming languages, such as the "C" programming language or similar programming languages. In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of embodiments.

Aspects of embodiments are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments.

Reference is now made also to <FIG>, showing a schematic block diagram of an exemplary system <NUM>, according to some embodiments. In such embodiments, at least one hardware processor <NUM> is connected to physical memory area <NUM>.

For brevity, henceforth the term "processing unit" is used to mean "at least one hardware processor" and the terms are used interchangeably.

Optionally, processing unit <NUM> is connected to memory <NUM> via memory management unit <NUM>. Optionally, memory management unit <NUM> comprises processing circuitry for handling memory and caching operations associated with processing unit <NUM>. Optionally, processing unit <NUM> is coupled with memory management unit <NUM>, for example via an electrical interface or via a bus.

Memory <NUM> is connected to cache memory area <NUM>. For brevity, henceforth the term "cache" is used to mean "cache memory area" and the terms are used interchangeably. Optionally, memory <NUM> is coupled with cache <NUM>, for example via another electrical interface or another bus. Optionally, memory management <NUM> is connected to cache <NUM>, optionally via yet another electrical interface or yet another bus. Optionally, memory management unit <NUM> is connected to cache <NUM> via the other electrical interface or other bus connecting memory <NUM> to cache <NUM>. Optionally, cache <NUM> is a multi-layered cache, having a plurality of cache levels, optionally organized hierarchically. For example, cache <NUM> may comprise four levels, for example identified as L1, L2, L3 and L4. Any of the methods described herewithin may be applied to any layer, and additionally or alternatively to any combination of layers, of cache <NUM>.

Optionally, the processing circuitry for handling memory and caching operations in memory management unit <NUM> handles caching of one or more values used when accessing a Translation Lookaside Buffer (TLB). Optionally, at least some of the one or more values used when accessing the TLB are values of one or more PTEs. Optionally, the TLB is cached in cache <NUM>. Optionally, at least some of the one or more values used when accessing the TLB are cached in cache <NUM>.

Optionally, processing unit <NUM> is connected to another processing unit <NUM>, optionally via one or more digital communication network interfaces. Optionally, processing unit <NUM> is electrically coupled with other processing unit <NUM>. Optionally, other processing unit <NUM> is a configurable computation grid, comprising a plurality of configurable computation elements. Optionally, processing unit <NUM> communicates with other processing unit <NUM> to configure other processing unit <NUM> to execute one or more execution threads of a software application executed by processing unit <NUM>. Optionally, for example when other processing unit <NUM> is a configurable computation grid, configuring other processing unit <NUM> comprises configuring at least some of the plurality of configurable computation elements.

Other processing unit <NUM> is connected to memory <NUM>, optionally via memory management unit <NUM>. Optionally, other processing unit <NUM> is coupled with memory <NUM>. Optionally, other processing unit <NUM> is coupled with memory management unit <NUM>, optionally via the memory interface or bus that processing unit <NUM> is coupled with memory management unit <NUM>.

Cache <NUM> comprises a plurality of cache lines. Each of the plurality of cache lines has a cache line amount of bits, for example <NUM> bits. Other examples of a cache line amount of bits include, but are not limited to, <NUM> bits and <NUM> bits.

Optionally, cache <NUM> comprises a plurality of cache bins. Reference is now made again to <FIG>. Optionally, cache <NUM> is one of the plurality of cache bins of cache <NUM>.

Processing unit <NUM> caches in cache <NUM> two or more data values, each of one of two or more ranges of application memory addresses, each associated with one of a set of execution threads. Reference is made again to <FIG>, <FIG> and <FIG>. For example, the set of threads may comprise one thread and associated with application address range <NUM>, and another thread associated with application address range <NUM>. Optionally, processing unit <NUM> caches data of sub-range 110A and of sub-range 111A in cache line <NUM>-i.

Optionally, the set of execution threads are executed by processing unit <NUM>. Optionally, the set of execution threads are executed by other processing unit <NUM>. Optionally, processing unit <NUM> configures other processing unit <NUM> to execute the set of execution threads. The set of execution threads has an identified order of threads.

To cache the two or more data values, in some embodiments, system <NUM> executes the following non-mandatory method.

Reference is now made also to <FIG>, showing a flowchart schematically representing an optional flow of operations <NUM> for caching, according to some embodiments. In such embodiments, in <NUM> processing unit <NUM> organizes a plurality of sequences of consecutive address sub ranges, for example application address range <NUM>, application address range <NUM>, application address range <NUM> and application address range <NUM> in interleaved sequence of address subranges <NUM>. Optionally, each address sub-range of each of the plurality of application address sub ranges has an identified amount of memory bits which is less than the amount of cache line bits. For brevity, henceforth the term "step size" is used to mean the identified amount of memory bits. Optionally, the step size is an amount of memory bits cached consecutively in one cache line and associated with one thread of the set of threads, i.e. a size of an interleaving step in a cache line. Some examples of a step size include, but are not limited to, <NUM> bits and <NUM> bits. Optionally, the identified amount of cache line bits is a multiple of the step size by an integer number. Optionally, the identified amount of cache line bits is a multiple of the step size by an amount of threads in the set of threads. For example, when the amount of cache line bits is <NUM>, in one example the step size may be <NUM> bits, in another example the step size may be <NUM> bits, and in yet another example the step size may be <NUM> bits. To organize the plurality of sequences of consecutive address sub-ranges in interleaved sequence of address sub-ranges <NUM>, processing unit <NUM> optionally selects, alternately for each thread in the identified order of threads, a next address sub-range in the respective sequence of address sub-ranges associated with the thread.

Optionally, at least one of the application memory address ranges is a range of application physical addresses. For example, application address range <NUM> may be a range of application physical addresses in memory <NUM>. Optionally, at least one of the application memory address ranges is a range of application virtual addresses. For example, application address range may be a range of application virtual addresses.

In <NUM>, processing unit <NUM> generates a mapping between interleaved sequence <NUM> and mapped physical range <NUM> of physical memory addresses in memory <NUM>. The mapping is in the order of interleaved sequence of address sub-ranges <NUM>, such that sub-range 111A, which is consecutive to sub-range 110A in interleaved sequence of address sub-ranges <NUM>, is mapped to mapped physical sub-range <NUM>-<NUM> and sub-range 110A is mapped to mapped physical sub-range <NUM>-<NUM>, where mapped physical sub-range <NUM>-<NUM> is consecutive to mapped physical sub-range <NUM>-<NUM> in mapped physical range <NUM>.

The following description pertains to an embodiment where the set of threads are executed by other processing unit <NUM>. The same steps may be executed by processing unit <NUM> when the set of threads are executed by processing unit <NUM>.

When an execution thread of the set of execution threads accesses an application memory address of the respective range of application memory addresses associated with the execution thread, for example when a thread accesses an application memory address in sub-range 111A, other processing unit <NUM> computes in <NUM> a target memory address according to the mapping, using the application memory address, and in <NUM> accesses memory <NUM> using the target memory address. Optionally, the thread accesses memory <NUM> to retrieve a step size amount of memory bits from memory <NUM>. Optionally, other processing unit <NUM> accesses memory <NUM> via memory management unit <NUM>. Optionally, accessing memory <NUM> comprises retrieving a full cache line from memory <NUM>, i.e. retrieving from memory <NUM> the cache line amount of bits from memory <NUM>. In <NUM>, two or more values, for example data of 110A, data of 111A, data of 112A and data of 113A are stored in cache-line <NUM>-i, optionally by memory management unit <NUM>.

Optionally, the target memory address is a target physical memory address and in <NUM> other processing unit <NUM> accesses memory <NUM> using the target physical memory address.

Optionally, the target memory address is a linear virtual address. For example, when each of two or more of the set of threads are associated with a common range of application virtual addresses, a plurality of application virtual addresses of the set of threads may be mapped to a contiguous range of linear virtual addresses, such that each of the set of threads is mapped to a unique sub-range of the contiguous range of linear virtual addresses.

In the field of computing, a page table is a data structure used to store mappings between a plurality of virtual addresses and a plurality of physical addresses. Optionally, other processing unit <NUM> computes the target memory address in <NUM> by providing the application memory address to a TLB and additionally or alternatively to a page table.

In the field of computing, the term "memory paging" (or "paging" for short) refers to a memory management scheme where data is stored and retrieved from a secondary storage for use in a main memory, for example memory <NUM>. A secondary storage may be a non-volatile digital storage, for example a hard disk or a solid-state disk. When system <NUM> uses memory paging, more than one virtual address may be mapped to one physical address. When system <NUM> supports memory paging and the application memory address is a virtual memory address, the physical address may be an outcome of providing the virtual memory address to the TLB and additionally or alternatively to the page table. Optionally, when the target memory address is a linear virtual address, the linear virtual address is the outcome of providing the application memory address to the TLB and additionally or alternatively to the page table.

When the target memory address is a linear virtual address, in <NUM> other processing unit computes in <NUM> another target physical memory address using the linear virtual memory address and in <NUM> accesses memory <NUM> optionally using the other target physical memory address instead of the target memory address computed in <NUM>.

Optionally, each of the set of execution threads has an identification value according to the identified order of threads, henceforth referred to as a lane value. Optionally, the identification value of a thread is an ordinal number of the thread in the identified order of threads.

Reference is now made also to <FIG>, showing a block diagram schematically representing an exemplary address mapping <NUM>, according to some embodiments. In such embodiments, application memory address <NUM> comprises low bits <NUM>, having an identified amount of least significant bits of application memory address <NUM>. Optionally, memory <NUM> is organized in a plurality of physical memory pages. Optionally, each of the plurality of physical memory pages has an amount of physical page bytes, for example <NUM>, <NUM>, <NUM>, and <NUM>. Optionally, an amount of bits of low bits <NUM> is a base <NUM> log of the amount of physical page bytes. For example, when the amount of physical page bytes is <NUM>, the amount of bits in low bits <NUM> may be <NUM>. In another example, when the amount of physical page bytes is <NUM>, the amount of bits in low bits <NUM> may be <NUM>.

Optionally, computing the target memory address comprises inserting low bits <NUM> into a binary representation of the target memory address <NUM>, optionally into a low part of binary representation of the target memory address <NUM>. Optionally, computing the target memory address comprises inserting lane value <NUM> of the respective thread associated with application memory address <NUM> into binary representation of the target memory address <NUM>, optionally immediately following low bits <NUM>.

Optionally, low bits <NUM> comprise a cache line identifier <NUM>, indicative of a cache line of the plurality of cache lines of cache <NUM> intended to store a copy of a data value of memory <NUM> at location application memory address <NUM>. Optionally, low bits <NUM> further comprise an offset value <NUM> indicative of an offset in a step size amount of data retrieved from memory <NUM> according to application memory address <NUM>. Optionally, low bits <NUM> further comprises other low bits <NUM>.

Optionally, computing the target memory address further comprises rotating low bits <NUM> and lane value <NUM>. For example, to produce target memory address <NUM>, the sequence of cache line identifier <NUM>, other low bits <NUM> and lane value <NUM> have been rotated to the right by an amount of bits in cache line identifier <NUM> and other low bits <NUM>. Optionally, rotating low bits <NUM> and lane value <NUM> is rotating to the right by a base-<NUM> log of the step size.

For example, when accessing sub-range 111A lane value <NUM> is indicative of a second thread of the set of threads. In this example, lane value <NUM> is in lower bits of target address <NUM> than cache identifier <NUM>, serving to identify an offset in a cache line associated with sub-range 111A, and not with sub-range 110A or 112A.

Reference is now made again to <FIG>. Optionally, in <NUM> processing unit <NUM> selects the set of threads from a plurality of threads. Optionally, the plurality of threads is executed by one or more of processing unit <NUM> and other processing unit <NUM>. Optionally, processing unit <NUM> selects the set of threads from the plurality of threads according to a plurality of statistical values. Some examples of a statistical value are: an amount of accesses to an application memory address, an order of accesses to a plurality of application memory addresses, an association between an application memory address and a thread identification value, and an amount of application memory in an application memory area. Optionally, the plurality of statistical values is used to identify the set of threads such that when the set of threads are executed concurrently and when respective application memory ranges associated with the set of threads is interleaved in physical memory a likelihood of a cache hit is increased. When more than one thread shares a similar access pattern, using one or more shared cache lines for the more than one thread increases a likelihood of a cache hit. When the more than one thread use a common memory access size, there is a greater likelihood that when the more than one thread share a cache line there will be a cache hit.

When system <NUM> supports memory paging, the plurality of statistical values is optionally used to identify the set of threads such that a likelihood of a cache hit is increased when more than one virtual address is mapped to one physical address.

In some embodiments, sharing a cache line may be done for more than one set of threads, where each set of threads shares a cache line. In such embodiments, processing unit <NUM> repeats step <NUM> and selects from the plurality of execution threads another set of execution threads having another order of threads, where each of the other set of threads is associated with one of two or more other ranges of application memory addresses. Optionally, processing unit <NUM> repeats <NUM> to organize another plurality of sequences of consecutive address sub-ranges in another interleaved sequence of address sub-ranges. Optionally, each of the plurality of sequences of consecutive address sub-ranges is associated with one other of the other set of execution threads. Optionally, each of the plurality of sequences of consecutive address sub-ranges consists of another consecutive sequence of application memory address sub-ranges of the respective range of application memory addresses associated with the respective one other execution thread associated therewith. Optionally, each other application memory address sub-range has another identified amount of memory bits, i.e. another step size. Optionally, the other step size is less than the amount of cache line bits. Optionally, the other step size is different from the step size.

Optionally, processing unit <NUM> alternately selects, for each other thread in the identified other order of threads, another next address sub Orange in the respective other sequence of address sub-ranges associated with the other thread.

Optionally, processing unit <NUM> repeats <NUM> and generates another mapping of the other interleaves sequence of address sub-ranges to the range of physical memory addresses in the other order of the interleaved sequence of address sub-ranges.

Optionally, cache <NUM> comprises a plurality of cache bins.

Reference is now made also to <FIG>, showing a block diagram schematically representing an exemplary caching <NUM>, according to some embodiments. In such embodiments, cache <NUM> comprises a plurality of cache bins, including cache bin <NUM> and cache bin <NUM>. Optionally, cache <NUM> is one of the plurality of cache bins of cache <NUM>, for example cache bin <NUM>. Optionally, cache bin <NUM> comprises a first plurality of cache lines, each having a first amount of cache bits. Optionally, cache bin <NUM> comprises a second plurality of cache lines, each having a second amount of cache bits. Optionally, the first amount of cache bits is different from the second amount of cache bits. For example, the first amount of cache bits may be <NUM> bits and the second amount of cache bits may be <NUM> bits.

Optionally, memory <NUM> is associated with one of the plurality of cache bins of cache <NUM>.

Optionally, mapped physical range <NUM> comprises more than one sub-range of the range of physical memory addresses, for example mapped sub-range <NUM>, addressing memory area <NUM>, and other mapped sub-range <NUM>, addressing memory area <NUM>. Optionally, memory area <NUM> is associated with cache bin <NUM> and therefore mapped sub-range <NUM> is associated with cache bin <NUM>. Optionally, memory area <NUM> is associated with cache bin <NUM> and therefore other mapped sub-range <NUM> is associated with cache bin <NUM>.

Optionally, interleaved sequence of address sub-ranges <NUM> is mapped to mapped sub-range <NUM>, such that a memory access to an address in a sub-range of interleaved sequence <NUM> is an access to memory area <NUM>. Optionally, other interleaved sequence of address sub-ranges <NUM> is mapped to mapped sub-range <NUM>, such that another memory access to another address in another sub-range of interleaved sequence <NUM> is another access to memory area <NUM>.

When system <NUM> comprises a TLB, for example a TLB stored in cache <NUM>, to increase TLB utilization processing unit <NUM> optionally encodes in a PTE in a hierarchy of page tables that are accessed when referencing a virtual memory address allocated to a thread of the plurality of threads a hint indicative of an amount of contiguous physical memory pages that may be referenced by a plurality of consecutive PTEs comprising the PTE. For example, processing unit <NUM> may encode the hint when organizing the plurality of sequences of consecutive address sub ranges in the interleaved sequence of address subranges.

Optionally, processing unit <NUM> encodes the hint in part of a binary representation of the virtual address in the PTE. Reference is now made also to <FIG>, showing a block diagram schematically representing exemplary page table entries <NUM>, according to some embodiments. In such embodiments, leaf page entry <NUM> comprises Physical Page Number (PPN) <NUM>. Optionally, PPN <NUM> is at least part of a page number of an effective physical memory page consisting of one or more contiguous physical memory pages.

When a page table is organized in a hierarchy of page tables, a leaf page table is a page table in a lowest level of the hierarchy of page tables. Optionally, an entry in a leaf page table comprises an indication as being an entry in a leaf page table, for example readable-indicator <NUM> in leaf PTE <NUM>. Optionally, combination of readable-indicator <NUM> set to <NUM> and valid-indicator <NUM> set to <NUM> is indicative of a leaf PTE. On the other hand, readable-indicator <NUM> of mid-level PTE <NUM> may be set to <NUM> when valid-indicator <NUM> is set to <NUM>, to indicate that mid-level PTE <NUM> is not a leaf PTE. In some other embodiments, other parts of the PTE may be used to indicate whether the PTE is a leaf PTE or a mid-level PTE. Optionally, a leaf PTE is indicated by a property of the page table the PTE is part of.

Optionally, each PTE of a page table used by memory management unit <NUM> comprises a hint indicative of an effective physical memory page size referenced thereof. Optionally, the hint is a page bump indicator indicative of an amount of contiguous physical memory pages the effective physical memory page consists of, for example PBI <NUM> of leaf PTE <NUM>, where each of the contiguous physical memory pages has an identified page size. Optionally, PBI <NUM> is a binary representation of an exponent such the amount of contiguous physical memory pages that may be referenced by leaf PTE <NUM> is equal to <NUM> raised to the power of the value of PBI <NUM>. Thus, effectively, leaf PTE <NUM> references a physical page having an effective size equal to the product of the identified page size and a multiplier equal to <NUM> raised to the power of the value of PBI <NUM>. For example, when PBI <NUM> is equal <NUM> (binary value and decimal value <NUM>), and therefore the multiplier is equal to <NUM>, leaf PTE <NUM> references an effective physical page that consists of one physical page. When the identified page size is <NUM> kilobytes (KB), leaf PTE <NUM> references an effective physical page of <NUM> KB.

Optionally, PBI 611A of leaf PTE 610A has a binary value of <NUM> (decimal value of <NUM>), indicating that leaf PTE 610A references another effective physical page consisting of <NUM> contiguous physical memory pages (as the multiplier is equal <NUM> to the power of <NUM>). Optionally, PPN 612A of leaf PTE 610A is at least part of another physical page number of the other effective physical page. In this example, when the identified page size is <NUM> kilobytes (KB), leaf PTE 610A references an effective physical page of <NUM> KB (<NUM> x 64KB).

Similarly, PBI 611B of leaf PTE 610B may have a binary value of <NUM> (decimal value of <NUM>), indicating that leaf PTE 610B references yet another effective physical page consisting of <NUM> contiguous physical memory pages (as the multiplier is equal <NUM> to the power of <NUM>). Optionally, PPN 612B of leaf PTE 610B is at least part of yet another page number of the yet other effective physical page. In this example, when the identified page size is <NUM> kilobytes (KB), leaf PTE 610B references an effective physical page of <NUM> megabytes (MB) (<NUM> x 64KB).

When a minimum page size in a page table is smaller than a minimum native page size of an operating system executed by system <NUM>, and when the minimum page size of the page table is a divider of the minimum native page size, each page of the operating system is optionally expressed as an integral amount of pages of virtual memory having the minimum page size of the page table, and represented by a plurality of PTEs, one for each of the integral amount of pages.

Optionally, when processing unit <NUM> supports an identified native minimum page size, using a PBI in a PTE allows processing unit <NUM> to use a minimum page size in a page table that is different from the identified native minimum page size used by processing unit <NUM>.

In a page table, each entry typically references one minimum sized page. In some embodiments, when using a page bump indicator, a plurality of PTEs, each referencing one physical memory page of the one or more contiguous physical memory pages an effective physical page consists of, each have a common physical page number and a common page bump indicator. Optionally, the common physical page number is a page number of the effective physical page that consists of the one or more contiguous physical memory pages.

Optionally, PBI <NUM> is not an exponent of a multiplier and the multiplier is encoded in PBI <NUM> using another encoding, for example a mapping between a value of PBI <NUM> and a multiplier value.

When the page table is organized in a hierarchy of page tables, PBI <NUM> of mid-level PTE <NUM> optionally indicates a minimal page size of a next page table in the hierarchy such that the minimal page size of the next page table is a multiple of a page size referenced by mid-level PTE <NUM>. Optionally, PBI <NUM> is encoded in a similar manner as PBI <NUM>, and thus a value of binary <NUM> in PBI <NUM> indicates that the minimal page size of the next page table is <NUM> times the minimal page size of the table to which mid-level PTE <NUM> belongs. Encoding a minimum page size of a next level page table in a mid-level PTE allows reducing a size of one or more page tables in a hierarchy of page tables. Optionally, the size of the one or more page tables in the hierarchy of page tables is reduced by a factor equal to the value of the PBI in the PTE.

Optionally, an amount of bits in PBI <NUM> is a divider of an amount of bits used to represent a minimum page size in the leaf page table that leaf PTE <NUM> belongs to.

Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

It is expected that during the life of a patent maturing from this application many relevant caches will be developed and the scope of the terms "cache", "cache bin", "cache line" and "cache line amount of bits" are intended to include all such new technologies a priori.

Any particular embodiment may include a plurality of "optional" features unless such features conflict.

Throughout this application, various embodiments may be presented in a range format. It should be understood that the description in range format is merely for convenience and brevity and should not be construed as an inflexible limitation on the scope of embodiments.

Claim 1:
A method for caching memory, comprising:
caching, in a cache line of a cache memory (<NUM>, <NUM>) for accessing a physical memory area (<NUM>) connected to at least one hardware processor (<NUM>), the cache memory comprising a plurality of cache lines (<NUM>-<NUM>, <NUM>-i and <NUM>-m) each having a cache line amount of bits, at least two data values, where each data value is of one of at least two ranges of application memory addresses, wherein each range of application memory addresses is associated with one of a set of execution threads having an identified order of threads and executed by the at least one hardware processor, by:
organizing (<NUM>) a plurality of sequences of consecutive address sub-ranges (<NUM>, <NUM>, <NUM> and <NUM>), each sequence associated with one of the set of execution threads and consisting of a consecutive sequence of application memory address sub-ranges (110A, 110B, 110C and 110D) of the respective range of application memory addresses associated with the execution thread, each application memory address sub-range having an identified amount of memory bits less than the amount of cache line bits, in an interleaved sequence of address sub-ranges (<NUM>) by alternately selecting, for each execution thread in the identified order of threads, a next address sub-range in the respective sequence of address sub-ranges associated therewith;
generating (<NUM>) a mapping of the interleaved sequence of address sub-ranges to a range of physical memory addresses (<NUM>) in order of the interleaved sequence of address sub-ranges; and
when an execution thread of the set of execution threads accesses an application memory address of the respective range of application memory addresses associated thereof:
computing (<NUM>) a target memory address according to the mapping using the application memory address; and
storing (<NUM>) the at least two data values in one cache line of the plurality of cache lines by accessing (<NUM>) the physical memory area using the target memory address.