Apparatus and method for a skip-list based cache

BACKGROUND OF THE PRESENT INVENTION

[0001] 1. Technical Field of the Present Invention

[0002] The present invention relates generally to the field of cache memory and more specifically to large size cache memories having a varying block size.

[0003] 2. Description of the Related Art

[0004] There will now be provided a discussion of various topics to provide a proper foundation for understanding the present invention.

[0005] Cache memories are commonly used in the industry as a type of memory that holds readily available data to be fed into a processing node. It is usually thought of as the fastest, and hence most expensive, memory in a computer system. The main purpose of the cache memory is to provide data to the processing node such that the processing node does not have to wait to receive the data. The result is a system having a higher overall performance, mostly at the expense of additional costs, including additional power consumption. In some implementations, there are multiple cache levels that allow for a balance between cost and performance Therefore, a processing node may have a first level fast cache memory that is expensive but is kept relatively small and is supported by a slower but significantly larger second level cache memory.

[0006] Since the cache memory provides data at high rates to the processing node, it is imperative that it performs its task efficiently. In “read” operations, when a piece of data requested by the processing node is found in the cache, it is considered to be a “hit” and the data is immediately provided to the processing node. If the data is not located in the cache memory, it will have to locate the requested data from a slower memory. This will result in a delay in the supply of data to the processing node, which is referred to as a “miss.” The cache memory will generate a request for data, which is larger, in most cases, than the actual request received from the processing node. This is done due to a phenomenon called “spatial locality,” or in other words, the higher likelihood to use the data that is in the immediate vicinity of the requested data. In fact, advanced compilers take advantage of this capability and attempt to ensure a high as possible locality, which results in a higher system performance. In most cases the locality found in code is higher then the locality found in general data and therefore the “hit ratio”, i.e., the ratio between the number of hits and the total number of requests from the cache memory, is usually larger for code than for data.

[0007] Three commonly used types of cache memories are direct mapped caches, N-way set associative caches, and fully associative caches. In each of these caches, there is a basic unit known as the “cache line” which is filled up with data each time data that should be placed there is requested, but not found. The size of the cache line affects the performance of the system. The smaller the cache line, the more likely a miss will occur; however, using very large cache lines may result in a long latency, i.e., the time until data is returned in a case of miss, and inefficiency of the cache. Therefore, it is desirable to balance between these two opposite extremes. In all cases, the cache line, once determined, is fixed and does not change.

[0008] In a direct mapped cache memory, each memory location is mapped to a single cache line that it shares with many other addresses, but not all addresses. The hit ratio is relatively low and more suitable for storage of code that generally presents a high degree of locality and sequentially. An N-way set associative cache memory overcomes some of the deficiencies of the direct mapped cache memory by offering the possibility of mapping a memory location into N cache lines. Therefore, if one cache line is already in use, another one of the available cache lines may be used. Usually N is a power of 2 and therefore the association degree found may be 2, 4, 8 and so forth. In a full associative cache memory, each location in memory can be mapped into any one of the available lines of the cache. Theoretically, this implementation provides the highest hit rate but this comes at the expense of complexity and power consumption.

[0009] The fixed size cache line, as well as the single way of accessing the data, results in a relatively inflexible cache system. It would be advantageous to develop a system that allows for a variable size cache line as well as multiple ways of accessing data. It would also be advantageous to utilize the cache in distributed cache implementations.

SUMMARY OF THE PRESENT INVENTION

[0010] The present invention has been made in view of the above circumstances and to overcome the above problems and limitations of the prior art.

[0011] Additional aspects and advantages of the present invention will be set forth in part in the description that follows and in part will be obvious from the description, or may be learned by practice of the present invention. The aspects and advantages of the present invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.

[0012] A first aspect of the invention provides a cache that stores a plurality of data blocks. The cache comprises a memory, and a skip-list based key handler that provides a cache address to the memory.

[0013] A second aspect of the present invention provides a skip-list based key handler. The skip-based key handler comprises data organized in a form of a skip list. The skip-based key handler further comprises means for searching the organized data and determining if an input address to the key handler matches an address contained within the key handler If it is determined that a match is found to the input address, the skip-based key handler further comprises means for outputting a cache address based on the matched input address.

[0014] A third aspect of the present invention provides a method for operating a skip-list based cache. The method comprises receiving an input address, and then determining if the input address is contained within a skip-list. Next, if the input address is contained within the skip-list, the method outputs a corresponding cache address. If the input address is not contained within the skip-list, a miss indication is issued. Next, if the cache address is available, the method accesses a memory and reads out the corresponding data.

[0015] A fourth aspect of the present invention provides a computer software product for a skip-list based cache. The computer software product comprises software instructions that enable the skip-list based cache to perform predetermined operations, and a computer readable medium that bears the software instructions. The predetermined operations comprise receiving an input address, and then determining if the input address is contained within a skip-list. Next, if the input address is contained within the skip-list, the predetermined operations output a corresponding cache address. If the input address is not contained within the skip-list, a miss indication is issued. Next, if the cache address is available, the predetermined operations access a memory and reads out the corresponding data.

[0016] The above aspects and advantages of the present invention will become apparent from the following detailed description and with reference to the accompanying drawing figures.

BRIEF DESCRIPTION OF THE DRAWINGS

[0017] The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate the present invention and, together with the written description, serve to explain the aspects, advantages and principles of the present invention. In the drawings,

[0018]FIG. 1 is an exemplary block diagram of a skip-list based cache;

[0019]FIG. 2 is an exemplary flowchart of a skip-list based cache data read and update;

[0020]FIG. 3 is an exemplary mapping of variable size blocks from main memory to a memory of a skip-list based cache;

[0021] FIGS. <b>4</b>A-<b>4</b>D illustrate an exemplary build of a single level skip-list as the result of the loading of data from main memory to a memory of a skip-list based cache; and

[0022]FIG. 5 is an exemplary mapping of a hierarchical skip-list for a skip-list based cache.

DETAILED DESCRIPTION OF THE PRESENT INVENTION

[0023] Prior to describing the aspects of the present invention, some details concerning the prior art will be provided to facilitate the reader's understanding of the present invention and to set forth the meaning of various terms.

[0024] As used herein, the term “computer system” encompasses the widest possible meaning and includes, but is not limited to, standalone processors, networked processors, mainframe processors, and processors in a client/server relationship. The term “computer system” is to be understood to include at least a memory and a processor. In general, the memory will store, at one time or another, at least portions of executable program code, and the processor will execute one or more of the instructions included in that executable program code. The terms “block” or “data block” mean a consecutive area of memory containing data. Different blocks may have different size unless specifically determined otherwise.

[0025] As used herein, the terms “predetermined operations,” the term “computer system software” and the term “executable code” mean substantially the same thing for the purposes of this description. It is not necessary to the practice of this invention that the memory and the processor be physically located in the same place. That is to say, it is foreseen that the processor and the memory might be in different physical pieces of equipment or even in geographically distinct locations.

[0026] As used herein, the terms “media,” “medium” or “computer-readable media” include, but is not limited to, a diskette, a tape, a compact disc, an integrated circuit, a cartridge, a remote transmission via a communications circuit, or any other similar medium useable by computers. For example, to distribute computer system software, the supplier might provide a diskette or might transmit the instructions for performing predetermined operations in some form via satellite transmission, via a direct telephone link, or via the Internet.

[0027] Although computer system software might be “written on” a diskette, “stored in” an integrated circuit, or “carried over” a communications circuit, it will be appreciated that, for the purposes of this discussion, the computer usable medium will be referred to as “bearing” the instructions for performing predetermined operations. Thus, the term “bearing” is intended to encompass the above and all equivalent ways in which instructions for performing predetermined operations are associated with a computer usable medium.

[0028] Therefore, for the sake of simplicity, the term “program product” is hereafter used to refer to a computer-readable medium, as defined above, which bears instructions for performing predetermined operations in any form.

[0029] A detailed description of the aspects of the present invention will now be given referring to the accompanying drawings.

[0030] In traditional cache implementations, a key is used to access the data in the cache line. Specifically, the key is all or part of the address that is associated with the location in which the data resides. When data is requested, the address is compared with the relevant key, and if there is a match, then the data in the cache line may be used. Only the relevant data actually sought is provided from the cache. For example, if two bytes are needed out of a 16 byte cache line, the two bytes requested will appear as valid data from the cache.

[0031] Referring to FIG. 1, an implementation of a skip list based cache memory <b>100</b> is shown. A key handler <b>120</b> receives an address <b>110</b> and by means of following through a skip list outputs a cache address <b>130</b>. The cache address <b>130</b> is output if and only if the data requested in address <b>110</b> actually resides in cache <b>100</b>. The cache address <b>130</b> is used to access memory <b>140</b> where the requested data is located, and the data is output on data bus <b>150</b>. Key handler <b>120</b> may be implemented in software, hardware or combination thereof. While the implementation of key handler <b>120</b> would be possible with a single level skip-list implementation, it is beneficial to use a hierarchical skip-list implementation for a higher level of performance. A detailed explanation of skip lists is provided in “The Elegant (and Fast) Skip List” by Thomas Wegner, incorporated herein by reference for all it contains. A skilled artisan could easily modify cache address <b>130</b> implementation, such that the cache address is provided over network connectivity. Moreover, it would be possible to have several units of memory <b>140</b>, and furthermore, such units of memory <b>140</b> could be geographically distributed resulting in a distributed cache implementation.

[0032] Referring to FIG. 2, where an exemplary flowchart <b>200</b> illustrating a search for a data in cache memory <b>100</b>, and an update of cache <b>100</b> if such data is missing. At S<b>210</b>, an address <b>110</b> is provided to key handler <b>120</b>. Address <b>110</b> is the system address in which a processing node expects the data to reside. At S<b>220</b>, key handler <b>220</b> searches the skip list to identify the position of address <b>110</b> and extract the cache address <b>130</b>. If it is determined at S<b>230</b> that the data may be found in memory <b>140</b>, then execution continues at S<b>240</b>. At S<b>240</b>, the cache address is used to access memory <b>140</b> and the data is placed on the data bus <b>150</b> for use by the processing node. An example of the process is described below.

[0033] It is possible, however, that address <b>110</b> is not found by key handler <b>120</b> as the data was either never before placed in memory <b>140</b>, or it is further possible that at a certain point in time the data did reside in the memory but was removed to provide space for other data. Regardless of the specific reason, if it is determined at S<b>230</b> that the data is not in memory <b>140</b>, the execution continues at S<b>250</b> where data is fetched from main memory. A main memory of a processing node may be a larger and slower memory, such as a large dynamic random access memory (DRAM) array, a hard disk, or other types of slower memories. At S<b>260</b>, the data is inserted into memory <b>140</b> and at S<b>270</b> the skip list of key handler <b>120</b> is updated. An example of the process is provided below. Execution continues at S<b>220</b> with the purpose of providing the data to the processing node. A skilled artisan could easily adapt this process by first providing that data to the processing node and only then updating memory <b>140</b> and skip list of key handler <b>120</b>.

[0034] Referring to FIG. 3, a mapping of blocks of data residing in main memory into memory <b>120</b> of a skip-list based cache is shown. While main memory may be a significantly large memory, a cache memory, such as memory <b>120</b>, is usually limited in size, but is mostly a fast memory to deliver high performance. In this case, first a 50 byte block, located at address “250” of main memory, is placed in address “0” of memory <b>120</b>. The last byte of the 50 byte block is placed in address “49” of memory <b>120</b>. Subsequently, a 100 byte block, beginning at address “0” of main memory, is mapped to address “50” of memory <b>120</b>. Thereafter, a 25 byte block from address “3000” in main memory is placed starting at address “150” of memory <b>120</b> Finally, a 1.024 byte block, beginning at address “512” of main memory, is copied into memory <b>120</b> at location “175”. This sequence of events may take place as a processing node identifies these blocks of data to be required for its processing needs for a variety of possible operations such as read, write, modify, and others. Prior art cache architectures could not handle these kinds of significantly different and arbitrary sized blocks. In order to access these blocks efficiently, key handler <b>120</b> uses a skip list implementation.

[0035] Referring to FIG. 4, the same sequence is shown as it applies to the creation of a single level skip list. In FIG. 4A, a skip list is shown after the first insertion of reference item <b>430</b>A. It is inserted between the initial pointer <b>410</b> and the final skip-list node <b>420</b>, otherwise referred to as the NIL of the skip list. Prior to insertion of reference items <b>430</b>A, pointer <b>410</b> points to NIL <b>420</b>, after the first insertion pointer <b>410</b> points to pointer <b>432</b> of reference item <b>430</b>A and pointer <b>432</b> of reference items <b>430</b>A points to NIL <b>420</b>. Reference item <b>430</b>A, in addition to the pointer <b>432</b> used to reference the next item, or in this example to NIL <b>430</b>, has three more fields. Field <b>434</b>, the memory block address (MBA) field, contains the address of the first item within a data block in main memory. Field <b>436</b>, the cache block address (CBA) field, contains the address of the first item of the same block of data once placed in memory <b>120</b>. Field <b>438</b>, the block size field, contains the length of the block, for example, the length of the block in bytes, as presented in this example. The first block of data transferred to memory <b>120</b> is a 50 byte block, starting at address “250” of main memory. Being the first to be placed in memory <b>120</b>, it is placed in address “0” of memory <b>120</b>. This is indicated in the various fields of reference item <b>430</b>A such that the MBA field <b>434</b> receives the value “250”, the CBA field <b>436</b> receives the value “0”, and the block size field <b>438</b> receives the value “50”.

[0036] In FIG. 4B, the next step of the transfer of data into skip-list based cache <b>100</b> is shown. The next data placed in memory <b>120</b> is a 100 byte block located in address “0” of the main memory. In a skip list implementation, the data item is placed between pointer <b>410</b> and reference item <b>430</b>A, as is reference item <b>430</b>B. The reason for that is that this would maintain the order in which the data blocks appear in main memory. MBA field <b>434</b> of reference item <b>430</b>B receives therefore the value “0”, while CBA field <b>436</b> receives the value “50”, which is the address in memory <b>120</b> where the first byte of the block from the main memory will be place. Block size field <b>438</b> of reference item <b>430</b>B receives the value “100” as 100 bytes are placed in memory <b>120</b>. Similarly, the next reference items inserted are shown in FIGS. 4C and 4D for the 25 byte and 1024 byte blocks, respectively.

[0037] Turning now to locating data in a cache skip list, when a data byte from address “75” of main memory, supplied over address bus <b>110</b>, is sought, key handler <b>120</b> is used to verify that such data exists in memory <b>120</b>. If the data block exists in memory <b>120</b> the key handler <b>120</b> provides the cache address <b>130</b> that corresponds to the requested address <b>10</b>. To perform this task, the skip list is checked and it is noted that reference item <b>430</b>B has such data available as the address provided, i.e. address “75”, is within the address range of a block available in memory <b>120</b>. The address range is determined to be the range spanning from an MBA <b>434</b> to the end of its corresponding data block determined by the block size <b>438</b>. Hence, in this example the address range for the block referenced by reference item <b>430</b>B spans from memory address “0” through memory address “99”, i.e., one hundred bytes, and therefore memory address “75” is within that range.

[0038] The cache address <b>130</b> is calculated based on the value contained in the CBA field <b>436</b> of reference item <b>430</b>B, which is address “50” and adding to it item <b>430</b>B. The reason for that is that this would maintain the order in which the data blocks appear in main memory. MBA field <b>434</b> of reference item <b>430</b>B receives therefore the value “0”, while CBA field <b>436</b> receives the value “50”, which is the address in memory <b>120</b> where the first byte of the block from the main memory will be place. Block size field <b>438</b> of reference item <b>430</b>B receives the value “100” as 100 bytes are placed in memory <b>120</b>. Similarly, the next reference items inserted are shown in FIGS. 4C and 4D for the 25 byte and 1024 byte blocks, respectively.

[0039] Turning now to locating data in a cache skip list, when a data byte from address “75” of main memory, supplied over address bus <b>110</b>, is sought, key handler <b>120</b> is used to verify that such data exists in memory <b>120</b>. If the data block exists in memory <b>120</b> the key handler <b>120</b> provides the cache address <b>130</b> that corresponds to the requested address <b>110</b>. To perform this task, the skip list is checked and it is noted that reference item <b>430</b>B has such data available as the address provided, ie address “75”, is within the address range of a block available in memory <b>120</b>. The address range is determined to be the range spanning from an MBA <b>434</b> to the end of its corresponding data block determined by the block size <b>438</b>. Hence, in this example the address range for the block referenced by reference item <b>430</b>B spans from memory address “0” through memory address “99”, i.e., one hundred bytes, and therefore memory address “75” is within that range.

[0040] The cache address <b>130</b> is calculated based on the value contained in the CBA field <b>436</b> of reference item <b>430</b>B, which is address “50” and adding to it the offset of the memory address. The offset is calculated by subtracting from the memory address provided the corresponding MBA value. In this example the offset is calculated by subtracting the address “0” from the address “75” and hence the offset is “75”. The offset value is now added to the corresponding CBA value thereby adding “50” to the address. Therefore, the memory <b>120</b> is accessed using address “125”. The memory <b>120</b> will respond by providing the respective data on data bus <b>150</b>. While this took only a single step of search in the skip list of key handler <b>120</b>, it should be noted that the case would be different had address “3012” been used, i.e., the 13^thbyte of the 25 byte block is to be provided. In this case, according to a single level implementation of a skip list, reference items <b>430</b>B, <b>430</b>A, <b>430</b>D would have to be checked before finally arriving at reference item <b>430</b>C where a “hit” would be found. This can become an even more demanding task when a significant number of blocks is present in memory <b>120</b>.

[0041] Referring to FIG. 5, a hierarchical implementation <b>500</b> of a skip-list for a skip-list based cache is shown. For this purpose, an additional level of pointers is added. In this case, a pointer <b>510</b> is attached to the pointer <b>410</b>. An additional pointer is added to a reference item that is several reference items ahead of the immediately next reference item. Hence, the pointer <b>410</b> points to the first level pointer of reference item <b>430</b>B while the pointer <b>510</b> points to, in this example, to reference item <b>430</b>D. Checking if an address is present in the skip-list based cache <b>100</b> is now done by first checking the higher level pointer of the skip list, i.e., the pointer <b>510</b>. If the address in the pointed reference item is larger than the requested address, the lower level pointer is used and the search continues until a “hit” or “miss” are identified. If data in address “255” is sought, then initially the address in reference item <b>430</b>D will be checked, as it is pointed to by pointer <b>510</b>. As it contains the start memory address “512” it would mean that it is too high, as compared to the address being searched for and thus, the lower level pointer <b>410</b> should be used. The pointer <b>430</b> points to reference item <b>430</b>B which does not contain the requested address and then the next reference item is used, namely reference item <b>430</b>A, which does contain the requested data. The cache address is calculated and the data is then provided. However, if address “375” was sought, it would go through similar steps but the data is not found using reference item <b>430</b>A and the next available reference item <b>430</b>D has an address which is too large. This will result in a “miss” indication and a fetch procedure in order to insert the missing data block in memory <b>120</b>. When address “3012” is searched, the pointer <b>510</b> is used first to access data item <b>430</b>D which is still too small; however, the next position pointed to by pointer <b>510</b> is NIL. Therefore, it is necessary to use a lower level pointer of <b>430</b>D, which points to reference item <b>430</b>C, where the data is referenced. The advantage of the hierarchical approach is clear when a large number of blocks is used, as a faster search can be implemented. While a two level hierarchy was shown, a person skilled in the art could easily add additional levels as may be needed to implement an efficient search.

[0042] The foregoing description of the aspects of the present invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the present invention to the precise form disclosed, and modifications and variations are possible in light of the above teachings or may be acquired from practice of the present invention. The principles of the present invention and its practical application were described in order to enable one skilled in the art to utilize the present invention in various embodiments and with various modifications as are suited to the particular use contemplated.

[0043] Thus, while only certain aspects of the present invention have been specifically described herein, it will be apparent that numerous modifications may be made thereto without departing from the spirit and scope of the present invention. Further, acronyms are used merely to enhance the readability of the specification and claims. It should be noted that these acronyms are not intended to lessen the generality of the terms used and they should not be construed to restrict the scope of the claims to the embodiments described therein.