System and method for cache organization in row-based memories

The present disclosure relates to a method and system for mapping cache lines to a row-based cache. In particular, a method includes, in response to a plurality of memory access requests each including an address associated with a cache line of a main memory, mapping sequentially addressed cache lines of the main memory to a row of the row-based cache. A disclosed system includes row index computation logic operative to map sequentially addressed cache lines of a main memory to a row of a row-based cache in response to a plurality of memory access requests each including an address associated with a cache line of the main memory.

FIELD OF THE DISCLOSURE

The present disclosure is generally related to the field of cache organization, and more particularly to methods and systems for mapping cache lines to a row-based cache.

BACKGROUND

Computing systems include one or more memories for storing data and other information in the form of bits. Many computing systems include both a main or primary memory and a cache memory. The main memory, which may include one or more memory structures or storage mediums, stores data and instructions that are executed by a processor (e.g., CPU) or other control unit of the computing system. Some main memories include volatile random access memories (RAM), although other suitable memory types may be provided. The cache memory, which also may include one or more memory structures or storage mediums, is often used by a processor of the computing system to temporarily store copies of data from the main memory to reduce the time or latency required for the processor to access and manipulate requested data. A memory controller, internal or external to the processor, typically controls the indexing of and access to data stored in the cache and in the main memory.

Based on memory requests from the processor, the memory controller populates the cache with data from the main memory after startup of the computing system and on-demand throughout the operation of the computing system. Data is transferred between the main memory and the cache in the form of cache lines. In particular, a “cache line” (or “cache block”) as used herein refers to the unit or block of data from the main memory that is transferred between the main memory and the cache. The cache line is typically fixed in size as set by the processor or memory controller of the computing system. Cache lines may include any suitable size, typically based on the power of two (i.e., cache line size=2n). A common cache line size is 64 bytes. Other suitable cache line sizes may be provided, such as, for example, 16, 32, 64, 128, and 256 bytes. As such, cache lines are used to transfer data from the main memory for temporary storage in the cache. A “data block” as used herein refers to a portion or a data subset of the cache line. For example, a 128-byte cache line may include two 64-byte data blocks.

Row-based memories may be used as the cache for a computing system. A row-based memory includes multiple memory locations organized into rows or “sets,” and each row is operative to store multiple cache lines from the main memory. The number of cache lines storable in each row of the cache is the set associativity of the cache. For example, a 2 kilobyte row of a cache with 64-byte cache lines has a 32-way set associativity (2048/64=32).

In particular, row-based memories typically store data in a bit cell array that includes multiple rows of bit cells. Each bit cell is operative to store a data bit in some physical format. For example, a dynamic random access memory (DRAM) stores charge to encode a bit value (i.e., logical 0 or 1), and resistive memories (e.g., phase-change memory, memristors, etc.) encode the bit value using the resistance of the material in the bit cell. Reading the bit cells typically involves sensing the physical properties (e.g., the presence or absence of charge in DRAM, whether the resistance is high or low in resistive memories, etc.) of an entire row of bit cells in the bit cell array, and then recording or loading all detected values in the row into a row buffer of the memory. To access data in the row-based memory, the memory controller loads a row of the array into the row buffer and then accesses the loaded row buffer such that data in the row buffer can be read from and/or written to. As such, read and write operations performed on the cache are performed at the row buffer. On the other hand, in a memory that is not row-based, such as a static random access memory (SRAM), for example, data is read directly from and written directly to the bit cell array of the memory. As such, data is not required to be first loaded into a row buffer before the read/write operation is performed.

In row-based memories, copying the data from the requested row of the bit cell array into the row buffer is referred to as “activating” or “opening” the row. In some row-based memories, such as DRAM, for example, the data in the row buffer is written back to the bit cell array after the read/write operation or access is complete because the original activation operation often destroys the charges (i.e., data) stored in the activated row. Restoring or writing back the data from the row buffer to a row of the bit cell array is referred to as “precharging” or “closing” the row. Each activation and precharge of the bit cell array consumes energy, increases observed memory access latencies, and reduces memory bank availability. In non-row-based memories, because data is not required to be first loaded into a row buffer before the read/write operation, separate activate and precharge operations are not required for each row access.

FIG. 1illustrates an exemplary known memory control system10including a control unit12operatively coupled to a cache memory14and to a main memory18. Control unit12, such as a processor, includes a memory controller16that controls access to memories14,18for read/write operations. Memory controller16, while illustrated as a single block, includes logic for controlling main memory18and logic for controlling cache memory14. Memory14is illustratively a row-based memory14serving as a cache memory for control unit12. Exemplary memories14include a dynamic random access memory (DRAM), phase-change memory (PCM), spin-torque transfer magnetoresistive random-access memory (STT-MRAM), or other suitable volatile and non-volatile row-based memories.

Row-based memory14includes a bit cell array20comprised of a plurality of rows, and each row is comprised of a plurality of bit cells (i.e., storage cells or memory cells) operative to store data, as described herein. Each bit cell of bit cell array20represents a “bit” of stored data and has two stable states—an off state (e.g., logical “0”) and an on state (e.g., logical “1”). Some row-based memories, such as some flash memories and phase-change memories (PCMs), for example, allow for non-binary encodings and encode multiple bits of information per bit cell. For example, PCMs may use different levels of resistance to encode multiple bits, e.g., logical “00” is very low resistance, logical “01” is medium-low resistance, logical “10” is medium-high resistance, and logical “11” is very high resistance. An activated row of bit cell array20is loaded into the row buffer22during the read and/or write access, as described above. Memory14may further include a buffer cache24that provides additional caching, for example, to improve memory speed (such as in a flash memory, for example).

In the illustrated embodiment, memory14is in communication with control unit12and memory controller16via communication paths26,28. Communication path26includes one or more electrical lines or conductors for communicating various commands and controls from memory controller16to memory14. Such commands include activate and precharge commands (described herein), read command, write command, and other suitable memory commands, such as power mode control, wake up and sleep mode control, etc. Communication path28includes a data bus for communicating data during the read and write operations.

Memory controller16includes logic that communicates with main memory18via one or more communication links30. Communication link30includes a data bus or data paths for communicating read/write data as well as one or more control paths for communicating controls, commands, and feedback between memory controller16and memory18.

To initiate a memory access and thus a read/write operation, control unit12provides a memory access request to memory controller16that requests a read or write operation. For example, an application, operating system, or other program or logic executed by control unit12provides the memory access requests to memory controller16. Upon receipt of the memory access request, the memory controller16accesses the requested location in cache14(loads the corresponding row of array20into the row buffer22) and returns the data to control unit12for a read operation or modifies the data in the row buffer22for a write operation. If the requested data is not stored in cache14, memory controller16retrieves the data from main memory18and stores it in the cache14.

The access latencies depend on whether the cache access requires closing (i.e., precharging) an already opened (i.e., activated) row of the cache before opening the requested row. If a requested row has already been opened by an earlier memory access request, a read or write can be completed in less time than if the activate and precharge commands also need to be issued.

Conventional memory control systems10map requested cache lines to the row-based memory14such that sequentially (i.e., consecutively) addressed cache lines of the main memory18are mapped to consecutive rows in the cache14. For example, referring toFIG. 2, three consecutive physical rows (i, i+1, i+2) of bit cell array20are illustrated. Addresses A0, A1, and A2represent consecutive main memory addresses of three cache lines that are stored in bit cell array20. In other words, address A0is the main memory address of a first cache line, address A1is the main memory address of a second cache line that is stored adjacent the first cache line in main memory18, and address A2is the main memory address of a third cache line that is stored adjacent the second cache line in main memory18. Consecutively addressed cache lines of main memory18having addresses A0, A1, and A2are stored in consecutive rows (i, i+1, i+2) of bit cell array20. As illustrated, the cache line with main memory address A0is stored in row i, the cache line with address A1is stored in row i+1, and the cache line with address A2is stored in row i+2. For a cache line size of 64 bytes, for example, the actual bit values of addresses A0, A1, and A2are separated by 64 bytes. Bit cell array20illustratively stores another cache line having main memory address B0. In the illustrated embodiment, main memory address B0is at a separate location of main memory18that is nonconsecutive with addresses A0, A1, A2. While only four cache lines are illustratively stored in bit cell array20ofFIG. 2, additional cache lines may be stored in array20.

As such, to populate bit cell array20as illustrated inFIG. 2, memory controller16(FIG. 1) maps the cache lines to the row-based memory14such that sequentially addressed cache lines of the main memory18are mapped to consecutive rows in the cache14. If the last row of the bit cell array20is reached during the mapping of consecutively addressed cache lines, the next consecutively addressed cache line of main memory18is mapped to the next available memory location of the first row i, thereby providing a “round-robin” mapping sequence. Various replacement strategies or policies may be implemented to manage the replacement of cache entries in an accessed row of bit cell array20with other cache lines from the array20.

With the cache line organization ofFIG. 2, long sequences of sequential cache line accesses cause repeated activations and precharges, thereby increasing the total access latencies. For example, timeline40ofFIG. 2illustrates the sequence for accessing the sequential cache lines with main memory addresses A0and A1. First, accessing the cache line with main memory address A0requires an activation (ACT) of row i followed by the read (or write) of the cache line. To then access the cache line with main memory address A1, a precharge is required to close row i before another activation (ACT) is implemented to open row i+1 where the cache line with address A1is stored. Further, memory14(FIG. 1) often has a built-in electrical delay between the activation and precharge of a row based on the specifications of the memory chip. This built-in delay (e.g., the Row Active Time (tRAS) for RAM, etc.) is often longer than the time required to perform the read on the row buffer, as illustrated with the DELAY ofFIG. 2, thereby further increasing the overall access latencies of the row-based memory14.

Some conventional memory control systems utilize larger cache lines while attempting to capture spatial locality benefits of main memory data. With larger cache lines and thus a larger block of data transferred from main memory18to cache14, it may be possible to execute memory requests for spatially local data, i.e., data in physically nearby memory locations of the main memory18, with fewer row accesses. For example, referring toFIG. 3, the cache lines of bit cell array20are doubled in size compared with the cache lines ofFIG. 2. In particular, address A0ofFIG. 3references a cache line that spans two cache lines ofFIG. 2(spans both data blocks at addresses A0and A1). With cache line addresses A0and A1ofFIG. 2referencing two separate but consecutive cache lines each with a size of 64 bytes, for example, cache line address A0ofFIG. 3points to a single cache line having a size of 128 bytes. As such, whileFIG. 3illustrates two separate data blocks associated with main memory addresses A0and A1, the two data blocks cooperate to form a single larger cache line having main memory address A0.

Three additional, nonconsecutive cache lines are illustrated in row i with main memory addresses B0, C0, and D0, with each cache line spanning two 64-byte data blocks (e.g., B0and B1; C0and C1; and D0and D1) for a total size of 128 bytes. As such, the four cache lines at addresses A0, B0, C0, D0are at nonconsecutive addresses. Similar to the cache organization ofFIG. 2, the cache line at address A2, which is the next consecutive cache line address after address A0, is stored in the next consecutive row (row i+1).

With the larger cache line size ofFIG. 3, the set associativity of each cache row is reduced. For example, with 64-byte cache lines and 2-kilobyte rows, bit cell array20ofFIG. 2has 32-way set associativity. However, with 128-byte cache lines and 2-kilobyte rows, bit cell array20ofFIG. 3has only 16-way set associativity. Further, larger cache line sizes may lead to an increase in false sharing for cache coherent systems. For example, in a multi-core processor system, it is possible that two different processor cores (e.g., core X and core Y) each have a copy of a 128-byte cache line spanning main memory addresses A0and A1in their respective caches. If core X writes to the data block with address A0, then core Y must discard the entire cache line, including both data blocks at A0and A1, because the stored data is no longer valid or up-to-date. If core Y is only accessing data at A1rather than at A0, then invalidation of the entire cache line wastes power and increases latency because core Y only needed to invalidate the data block at address A0, i.e., because the data at A1was still up-to-date. As such, because the cache only handles data on cache line granularity (illustratively 128 bytes inFIG. 3), then even if a single byte within an entire cache line is modified, all other copies of the cache line in other cores are invalidated. Accordingly, rather than sharing data at A0and A1, cores X and Y are actually using disjoint data. Further, memory bandwidth consumption is increased, as the data at both A0and A1is transferred even if only one of A0and A1is used.

Further still, some portions of the cache line in the accessed row may not be needed but still take up memory space, leading to fragmentation in which unused data blocks occupy cache memory. In particular, memory bandwidth may be wasted when, for example, only a single 64-byte block of data is requested during the row access but the cache line is larger, such as 128 bytes or 256 bytes. InFIG. 3, the data blocks with addresses C1and D1are illustratively not utilized in a memory access of row i but are still stored in the row due to the large cache line size described above. As such, a request for the data blocks at address E0or F0will result in a “cache miss” because these data blocks are not stored in the cache14. For example, upon a request for address E0, one of the cache lines at addresses A0, B0, C0, or D0must be evicted from row i based on the replacement policy of memory controller16, and then the cache line at address E0is retrieved from main memory18and is installed in row i in the newly vacant location. Accordingly, accessing the data block with address E0or F0results in increased access latencies and power consumption. Larger cache lines may thus increase “cache miss” rates due to the fragmentation.

Sub-sectoring may be used by the memory controller18to reduce the bandwidth consumption and false sharing impacts of larger cache lines. Sub-sectoring reads from or writes to only needed data blocks or “sectors” (i.e., a portion or data subset of the cache line) of the row buffer during the access. For example, rather than reading the entire cache line spanning addresses C0and C1, sub-sectoring allows only the needed data block at address C0to be read. However, sub-sectoring does not solve the problem of reduced cache efficiency and underutilization of the cache due to fragmentation, as the unrequested data blocks with addresses C1and D1still occupy row space. Further, sub-sectoring does not solve the problem of reduced set associativity of the cache.

Referring toFIG. 4, a “pool of subsectors” approach is utilized in conjunction with the larger cache lines ofFIG. 3.FIG. 4illustrates row i of bit cell array20ofFIG. 3, which includes cache lines that are double the size of the cache lines ofFIG. 2, along with a tag array62comprised of multiple tag entries. Each tag or address entry of tag array62identifies the location of a single cache line in array20. In particular, each tag entry includes a main memory address of a cache line and two pointers that identify the location of data blocks of the cache line in bit cell array20. Each pointer points to a data block or “subsector” located in a different pool of the row. In particular, bit cell array20is divided into two pools such that half of each cache line is allocated to the first pool (pool ‘0’) and the other half of the cache line is allocated to the second pool (pool ‘1’). For example, tag entry A01stores a main memory address A0of a cache line, a pointer that identifies the location in pool ‘0’ of the data block of the cache line having address A0, and a pointer that identifies the location in pool ‘1’ of the data block of the cache line having main memory address A1. Tag entry B01similarly stores a cache line address B0and two pointers each pointing to the data block or subsector of the cache line in each pool of array20. Tag entries C01and D01each include a single pointer pointing to the respective data block of the corresponding cache line that is stored in pool ‘0’. Since the data blocks having main memory addresses C1and D1are not requested inFIG. 4, as inFIG. 3, tag entries C01and D01do not include pointers that identify the data blocks at respective addresses C1and D1. However, due to the larger cache lines, the memory space allocated for the data blocks with addresses C1and D1are still occupied and are unavailable for other data, despite the data at addresses C1and D1not being requested. As such, similar to the cache organization ofFIG. 3, other cache lines requested during the row access, such as data blocks with addresses E0and F0, will result in a “cache miss” and an increase in access latencies and power consumption. As a result, the cache organization ofFIG. 4may also increase “cache miss” rates due to fragmentation issues.

Therefore a need exists for methods and systems to reduce the access latencies involved with a row-based memory. Further, a need exists for such methods and systems to avoid fragmentation and bandwidth consumption issues associated with large cache lines and sub-sectoring and to improve set associativity and cache utilization.

SUMMARY OF EMBODIMENTS OF THE DISCLOSURE

In an exemplary embodiment of the present disclosure, a method for mapping cache lines to a row based cache is provided. The method includes, in response to a plurality of memory access requests each including an address associated with a cache line of a main memory, mapping a plurality of sequentially addressed cache lines of the main memory to a row of the row-based cache.

Among other advantages, some embodiments of the method and system of the present disclosure provide a cache organization strategy that reduces the power consumption and improves performance of the cache by reducing the number of activations and precharges required to access the data stored in the cache. By organizing data in the cache such that a number of sequentially addressed cache lines are stored in the same cache row, data from spatially local cache lines is retrieved from the cache more efficiently, for example. Another exemplary advantage is that set associativity is improved while avoiding fragmentation issues. Other advantages will be recognized by those of ordinary skill in the art.

In one example, an exemplary embodiment of the method further comprises writing the sequentially addressed cache lines of the main memory to the row of the row-based cache. In another example, the method further comprises accessing the row of the row-based memory and at least one of reading data from the sequentially addressed cache lines and writing data to the sequentially addressed cache lines. In yet another example, the mapping includes populating a tag array that associates the sequentially addressed cache lines of the main memory with the row of the row-based memory. In still another example, the tag array stores at least one pointer indicating at least one memory location in the row of the row-based cache containing the sequentially addressed cache lines.

In another exemplary embodiment of the present disclosure, a cache control system is provided including memory control logic having row index computation logic operative to map sequentially addressed cache lines of a main memory to a row of a row-based cache in response to a plurality of memory access requests each including an address associated with a cache line of the main memory.

In still another exemplary embodiment of the present disclosure, a computer readable medium is provided including executable instructions for execution by an integrated circuit production system such that when executed cause the integrated circuit production system to produce an integrated circuit. The integrated circuit includes memory control logic having row index computation logic operative to map sequentially addressed cache lines of a main memory to a row of a row-based cache in response to a plurality of memory access requests each including an address associated with a cache line of the main memory. In one example, the executable instructions are in a hardware description language (HDL) or register-transfer level (RTL) format.

DETAILED DESCRIPTION

The term “logic” or “control logic” as used herein may include software and/or firmware executing on one or more programmable processors, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), digital signal processors (DSPs), hardwired logic, or combinations thereof. Therefore, in accordance with the embodiments, various logic may be implemented in any appropriate fashion and would remain in accordance with the embodiments herein disclosed.

The terminology “circuit” and “circuitry” refers generally to hardwired logic that may be implemented using various discrete components such as, but not limited to, diodes, bipolar junction transistors (BJTs), field effect transistors (FETs), etc., which may be implemented on an integrated circuit using any of various technologies as appropriate, such as, but not limited to CMOS, NMOS, etc.

It is to be understood that the terms “high” and “low” (also “on” and “off”) are relative to logical values such as respective logical values “1” or “0,” which may also be represented as binary “1” or binary “0.” The values 1 and 0 are binary values (or logical values) that are normally associated with a logical high (or on) and logical low (or off) as understood by those of ordinary skill.

In addition to the components shown in the figures which for the purpose of explaining the principles of the various embodiments herein disclosed, other elements such as additional logic gates, and/or discrete components, etc., may be present in the various specific implementations as may be understood by those of ordinary skill, and such other implementations still remain in accordance with the embodiments herein disclosed.

The various logic circuitry disclosed herein may be described in a form useable by an integrated circuit fabrication or production system. For example, the various logic circuitry disclosed herein may be described in Hardware Description Language (HDL) and may be stored on a computer readable medium/memory. The computer readable medium/memory may be any suitable non-volatile memory such as, but not limited to, programmable chips such as EEPROMS, flash ROM (thumb drives), compact discs (CDs) digital video disks (DVDs), etc., (that may be used to load HDL and/or RTL (register-transfer level), and/or executable instructions or program code), or any other suitable medium so that the HDL, or other suitable data, may be used by various integrated circuit fabrication systems. Therefore, the embodiments herein disclosed include a computer readable medium/memory comprising executable instructions for execution by an integrated circuit production system, that when executed cause the system to produce an integrated circuit comprising at least one integrated circuit logic cell in accordance with the embodiments herein described. The executable instructions may be HDL and/or RTL or any other suitable code and may include code to produce all of the features of the embodiments described above, and also described in further detail herein below.

Turning now to the drawings,FIG. 5illustrates an exemplary memory control system100according to various embodiments that is configured to reduce the access latencies involved with accessing sequentially addressed cache lines. Memory control system100may be viewed as modifying the known memory control system10described inFIG. 1. For example, control unit112ofFIG. 5may be viewed as a modification of the control unit12ofFIG. 1, memory controller116ofFIG. 5may be viewed as a modification of the memory controller16ofFIG. 1, and row-based memory114ofFIG. 5may be viewed as a modification of the row-based memory14ofFIG. 1. Like components of memory control system10ofFIG. 1and memory control system100ofFIG. 5are provided with like reference numbers. Various other arrangements of internal and external components and corresponding connectivity of memory control system100, that are alternatives to what is illustrated in the figures, may be utilized and such arrangements of internal and external components and corresponding connectivity would remain in accordance with the embodiments herein disclosed.

Referring toFIG. 5, memory control system100includes control unit112operatively coupled to cache memory114and to main memory18. Control unit112, such as a processor, includes memory controller116having memory control logic operative to control access to and manages memories18,114for read/write operations. In the illustrated embodiment, memory controller116is integrated with control unit112in a single chip device (e.g. a processor device). However, memory controller116alternatively may be external to control unit112and in communication with control unit112via a communication link. Memory114is illustratively a row-based memory114serving as a cache memory for control unit112. Exemplary memories114includes a DRAM, PCM, STT-MRAM, or other suitable volatile and non-volatile row-based memories.

Memory114includes one or more bit cell arrays120each comprised of a plurality of rows, as described herein with respect to memory14ofFIG. 1. An activated row of bit cell array120is loaded into the row buffer122during the read and/or write access, as described above with respect toFIG. 1. Memory114may further include the optional buffer cache124.

Row-based memory114is physically and logically separate from main memory18. In the illustrated embodiment, memory114is in communication with control unit112and memory controller116via communication paths26,28for communicating commands and read/write data, respectively, as described above with respect to memory control system10. In one embodiment, memory114is integrated with control unit112in a single chip device (e.g. processor device, three-dimensional integrated circuit, etc.). In another embodiment, memory114is positioned adjacent or nearby control unit112, such as with interposer-based integration or with multi-chip modules (MCMs), for example. Other suitable configurations of memory114and control unit112may be provided. Memory controller116and control unit112communicate with main memory18via one or more communication links30, as described herein inFIG. 1.

Control unit112includes control logic with software and/or firmware code containing instructions that are executed by the control unit112. Control unit112illustratively includes a processor (e.g. a central processor unit (CPU)), although control unit112may include multiple programmable processors, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), digital signal processors (DSPs), hardwired logic, or combinations thereof. Memory114is illustratively a row-based memory114serving as a cache memory for control unit112. Exemplary memories114includes a dynamic random access memory (DRAM), phase-change memory (PCM), spin-transfer torque magnetoresistive random-access memory (STT-MRAM), or other suitable volatile and non-volatile row-based memories.

To initiate a memory access and thus a read/write operation, control unit112initiates a memory access request to memory controller116that requests a read or write operation, and, upon receipt, memory controller116accesses the requested location in cache114by loading the corresponding bit cell row into the row buffer122, as described above inFIG. 1.

Memory controller116includes row computation index logic134that is operative to map cache lines of main memory18to the bit cell array120of cache114. Based on memory access requests from control unit112, logic134maps requested cache lines to the cache114such that a number of sequentially addressed cache lines of the main memory18are mapped to the same physical row in the cache114. For example, referring toFIG. 6, three physical rows (i, i+1, i+2) of bit cell array120are illustrated. Similar toFIG. 2, addresses A0, A1, and A2ofFIG. 6represent consecutive (sequential) main memory addresses of three cache lines that are stored in bit cell array120. The consecutively addressed cache lines of main memory18having addresses A0, A1, and A2are stored in the same row (row i) of bit cell array120. Fewer or additional consecutively addressed cache lines may be mapped to row i of the array120. Bit cell array120also illustratively stores the nonconsecutive cache line having main memory address B0in row i. Additional cache lines may be stored in array120.

With the cache organization of bit cell array120ofFIG. 6, memory access requests from control unit112(FIG. 5) that request data from the consecutive cache lines with main memory addresses A0, A1, and A2is carried out with a single row activation. For example, timeline140ofFIG. 6illustrates a sequence for accessing the sequential cache lines having main memory addresses A0and A1. First, accessing the cache line with main memory address A0requires an activation (ACT) of row i followed by the read (or write) of the cache line. The cache line with address A1is then read from the row buffer without performing another precharge or activation. Further, a built-in electrical delay (e.g., tRAS ofFIG. 2) of memory114between activation and precharge is avoided by reading the A1-addressed cache line from the same row as the A0-addressed cache line.

As illustrated inFIG. 6, a tag array142is also populated by logic134with the population of the bit cell array120. Tag array142provides a “lookup table” for controller116by associating the main memory address (or “tag”) of each cache line in cache114to the location of bit cell array120in which the cache line is mapped. Although only a single row of tag array142is illustrated inFIG. 6, the number of rows and columns in tag array142correspond to the number of rows and columns of bit cell array120. A main memory address stored in a row and column of tag array142will have a corresponding cache line located in the same row and column of the bit cell array120. As such, upon receiving memory access requests from control unit112, memory controller116looks up the requested cache line address in tag array142to determine if the cache line is already stored in cache114or if the cache line must be retrieved from main memory18. In one embodiment, tag array142is stored in cache114with the cache lines. For example, the tag entries of tag array142may be stored by combining the tag entries with the cache lines in the same physical rows or storing the tag entries in a specific layer of the cache114(e.g., DRAM stack). In another embodiment, tag array142is stored in a separate memory of memory control system100, such as in a static random access memory (SRAM) or other suitable memory accessible by memory controller116.

Referring toFIG. 7, row index computation logic134populates bit cell array120ofFIG. 3based on memory access requests from control unit112and according to the cache mapping pattern described herein. Rather than setting a larger cache line comprised of multiple data blocks, as in the conventional system ofFIG. 3, the cache lines of bit cell array120are the same size (e.g., 64 bytes, etc.) as the cache lines ofFIG. 6. By mapping the consecutively addressed cache lines to the same row (row i) while utilizing smaller cache lines, additional memory space is available in row i to accommodate the cache lines at addresses E0and F0, as illustrated inFIG. 7. Rather than storing the unrequested data at addresses C1and D1in row i as in the conventional system ofFIG. 3, the requested cache lines at addresses E0and F0are stored in row i. As such, an access to any of the cache lines at addresses A0, A1, B0, B1, C0, D0, E0, and F0will result in a cache hit and will not require an access to main memory18. Further, memory requests for the cache lines at addresses A0, A1, B0, B1, C0, D0, E0, and F0may illustratively be carried out with a single row access.

Referring toFIG. 8, the bit cell array120ofFIG. 7is illustrated along with a tag array162. Tag array162utilizes a level of indirection, illustratively with pointers, to identify the physical location of the stored cache lines in cache114. Each tag or address entry of tag array162corresponds to multiple cache lines of array120. In other words, the number of cache lines stored in cache114exceeds the number of cache line addresses stored in tag array162. For example, tag entry A01stores the main memory address A0of a first cache line and one or more pointers that identify or “point” to the row (row i) and location in the row of cache lines that are consecutively addressed with address A0. Tag entry A01illustratively includes two pointers164that identify the locations of the two consecutively addressed cache lines at addresses A0and A1. Tag entry A01may include additional pointers that point to additional consecutively addressed cache lines. Tag entry B01stores address data and pointers in a similar fashion for cache lines that are consecutive with address B0. Tag entries C01, D01, E01, and F01each illustratively include a single pointer that points to the respective cache line location. In one embodiment, the main memory addresses (e.g., A0, B0, etc.) stored in the tag entries take up more memory space than the pointers. For example, the main memory addresses (e.g., A0, B0, etc.) may be about 30 bits in size while the pointers may be about 3 bits in size. As such, in one embodiment, the use of pointers in tag entries for sequentially addressed cache lines serves to save memory space.

As illustrated inFIG. 8and similar to the cache organization ofFIG. 7, by mapping the consecutively addressed cache lines to the same row (row i) while utilizing smaller cache lines, additional memory space is available in row i to accommodate the cache lines at addresses E0and F0. By not storing the unrequested data at addresses C1and D1in row i as in the conventional system ofFIG. 4, the requested cache lines at addresses E0and F0are able to be stored in row i. As such, tag entries E01and F01each include a pointer that identifies the location in row i of the respective cache line at addresses E0and F0, and an access to any of the cache lines at addresses A0, A1, B0, B1, C0, D0, E0, and F0will result in a cache hit and will not require an access to main memory18.

FIGS. 9 and 10illustrate respective flow diagrams200,250of exemplary operations performed by row index computation logic134ofFIG. 5for mapping cache lines of a main memory (e.g., main memory18ofFIG. 5) to a row-based memory (e.g., cache114ofFIG. 5). Reference is made toFIG. 5throughout the following descriptions ofFIGS. 9 and 10.

Referring to flow diagram200ofFIG. 9, row index computation logic134receives a plurality of memory access requests, such as from a program or application of control unit112, each request including an address associated with a cache line of main memory18, as illustrated at block202. At block204, logic134maps sequentially addressed cache lines of the main memory18to a row of the row-based cache114, as described herein. As a result, two or more sequentially addressed cache lines are stored in the same physical row such that a single row access can access the sequentially addressed cache lines. As described herein, any suitable number of sequentially addressed cache lines may be mapped to a common row.

Referring to the flow diagram250ofFIG. 10, another exemplary operation of row index computation logic134is illustrated. At block252, logic134receives a read or a write memory request from control unit112. The request includes an identifier, illustratively the main memory address, of a cache line of main memory18. At block254, logic134maps the requested cache line address to a row of the cache114(i.e., bit cell array120) such that a number of sequential cache lines map to the same cache row, as described herein. In one embodiment, logic134populates a tag array (e.g., tag array142ofFIG. 6) at block254with the cache line address and the mapped row location of the cache114and populates the cache114with data from the requested cache line of main memory18. At block256, logic134accesses the row of cache114that was mapped with the requested cache line address at block254. If the requested cache line is found in the cache114at block258, logic134returns the requested value of the cache line to control unit112if a read was requested and updates the identified value of the cache line if a write was requested. If the requested cache line is not found in cache114at block258, logic134sends a request to main memory to retrieve the requested cache line.

While the illustrated embodiments described herein inFIGS. 5-10relate to a cache organization strategy during the population or initialization of the cache114, any suitable replacement policy may be provided for replacing cache entries after the initial population of the cache114.

In another embodiment, cache114ofFIG. 5is comprised of multiple cache banks, each bank with one or more bit cell arrays120. In this embodiment, sequentially addressed cache lines of main memory18each may be mapped to a different bank of the cache114such that accesses to the sequentially addressed cache lines may proceed in parallel.

Among other advantages, the method and system of the present disclosure provides a cache organization strategy that reduces the power consumption and improves performance of the cache by reducing the number of activations and precharges required to access the data stored in the cache. By organizing data in the cache such that sequentially addressed cache lines are stored in the same cache row, data from spatially local cache lines may be retrieved from the cache more efficiently, for example. Another exemplary advantage is that set associativity is improved while avoiding fragmentation issues. Other advantages will be recognized by those of ordinary skill in the art.