Method for dynamically adjusting memory system paging policy

[0002] This invention relates to memory technologies generally and particularly to a paging policy in a memory system.

[0003] As computer applications become increasingly complex, they also rely heavily on the efficient utilization of fast memory subsystems. Dynamic Random Access Memory (hereinafter DRAM) is one such memory commonly used in computer systems. DRAM is logically organized into “pages”, where a typical page covers between 1 kbytes and 64 kbytes of memory. A page is either in an “open” or “closed” state. When a page is “open”, a system memory controller has instructed a memory device to make its memory information contained in that page immediately available to future commands. On the other hand, when a page is “closed”, the information is only available after the memory controller has instructed the DRAM to open the page.

[0004] In addition, the memory subsystem is often divided into regions, or banks, accessible through a single “page window”. Each of these banks may contain many times the number of bytes that are available through the single page window. For example, a DRAM device with a 1 kbyte page window might have banks that are 512 kbytes each. Thus, applying the aforementioned “open” rules to this DRAM device, the device only has 1/512 of its individual bank available for immediate access at any given time. In order to further improve data access to and from the device, a DRAM memory controller's “paging policy” attempts to effectively manage which pages to keep open and which pages to proactively close.

[0005] Traditionally, paging polices are simple. Often pages are left open until either a “bank conflict” occurs or the DRAM memory controller becomes unable to track a large number of open pages. In other cases, pages are closed immediately after their data are accessed. This type of paging policy results in no immediate accesses to data but a high probability of avoiding time-consuming bank conflicts. Such a paging policy also allows for faster access within the same page.

[0006] However, due to the dynamic nature of user behavior and computer applications, determining in advance the best paging policy for a given system is often impractical. In such situations, in order to improve system performance, a method and apparatus is needed to create more than one paging policy and to dynamically switch between them.

[0007] A method and apparatus of dynamically adjusting a memory system's existing paging policy is disclosed. In one embodiment, the method for dynamically adjusting the paging policy generates a select signal according to at least one input signal and the existing paging policy to the memory system and proceeds to modify the existing paging policy basing on the generated select signal.

[0008] The present invention is illustrated by way of example and is not limited by the figures of the accompanying drawings, in which like references indicate similar elements, and in which:

[0009] FIG. 1 illustrates a general block diagram of one embodiment of a paging policy selector.

[0010] FIG. 2 illustrates a general purpose computer system architecture.

[0011] FIG. 3 illustrates an example of a memory entry table.

[0012] FIG. 4 illustrates a detailed block diagram of one embodiment of a select-signal generator and a paging policy modifier.

[0013] FIG. 5 illustrates a detailed block diagram of another embodiment of a select-signal generator and a paging policy modifier.

[0014] FIG. 6 is a flow chart of one embodiment of a process for asserting input signals.

[0015] FIG. 7 is a flow chart of one embodiment of a process for incrementing and decrementing different counters.

[0016] FIG. 8 illustrates a state diagram of one embodiment for transitioning between an aggressive paging policy and a non-aggressive paging policy.

[0017] A method and apparatus of dynamically adjusting a memory system's existing paging policy is described. In the following description, numerous specific details are set forth such as counters, memory controllers, non-aggressive and aggressive paging policies, etc. in order to provide a thorough understanding of the disclosed method and apparatus. However, it will be apparent to one of ordinary skill in the art that the disclosure may be practiced without these particular details. In other instances, well-known elements and theories, such as memory systems, paging policies, page hit, page miss, page empty, selector, FOR loops, etc., have not been discussed in special details in order to avoid obscuring the disclosure.

[0018] An “existing paging policy” is used throughout the written description to refer to the adopted paging policy of a memory system. On the other hand, “distinctive paging policies” refer to various paging policy schemes, which are accessible by the memory system. Therefore, the memory system is capable of replacing the existing paging policy with another paging policy chosen from the distinctive paging policies.

[0019] FIG. 1 is a general block diagram of one embodiment of a paging policy selector, which dynamically adjusts its associated memory system's existing paging policy. Referring to FIG. 1, paging policy selector 108 comprises select-signal generator 100 and paging policy modifier 102. Specifically, select-signal generator 100 receives various input signals indicative of status information of existing paging policy 106. Some examples of these input signals are, but not limited to, occurrences of re-opening pages or occurrences of closing-before-opening pages. Detailed discussions of these signals will follow in subsequent sections. According to the input signals and the existing paging policy 106, select-signal generator 100 generates and transmits select signal 104 to paging policy modifier 102. Then paging policy modifier 102 either maintains or modifies existing paging policy 106 based on select signal 104.

[0020] In one embodiment, the described paging policy selector is part of a memory controller, which resides in an electronic system. Some examples of the electronic system are, but not limited to, standalone electronic apparatuses and general-purpose computer systems. A general-purpose computer system 200 is illustrated in FIG. 2.

[0021] Referring to FIG. 2, the general-purpose computer system architecture comprises microprocessor 202 and cache memory 204 coupled to each other through processor bus 205. Sample computer system 200 also includes high performance I/O bus 208 and standard I/O bus 218. Processor bus 205 and high performance I/O bus 208 are bridged by host bridge 206, whereas high performance I/O bus 208 and standard I/O bus 218 are bridged by I/O bus bridge 210. Coupled to high performance I/O bus 208 are main memory 212 and video memory 214. Alternatively, main memory 212 can also be coupled to host bridge 206. Coupled to video memory 214 is video display 216. Additionally, a video processing device may also be coupled to host bridge 206. Coupled to standard I/O bus 218 are mass storage 220, network interface 224, and alphanumeric input device or other conventional input device 222. These elements perform their conventional functions well known in the art.

[0022] The paging policy selector dynamically adjusts its associated memory system's existing paging policy. Specifically, the selector modifies the existing paging policy according to a select signal, which is generated basing on various input signals and the existing paging policy. A memory controller may include such a paging policy selector, and thus the following paragraphs use the term “memory controller” instead of “paging policy selector”.

[0023] The memory controller maintains tables of memory addresses and some status information associated with them. FIG. 3 illustrates an example of one such table. Column 300 comprises entries of memory addresses, which the memory controller monitors. Column 302 indicates whether pages pointed to by these addresses are currently open or not. “T” stands for True, or the page is open. “F”, on the other hand, stands for False.

[0024] When the memory controller receives a request for memory access of a memory range, the memory controller checks the table to determine whether the desired memory range is open or is available for immediate access. If the range is open as indicated a “T” in column 302, the memory controller goes through a memory accessing procedure commonly described as “page hit”. Otherwise, when accessing the requested memory range depends on closing a different page, such a memory accessing procedure is known as “page miss”. Lastly, if the requested memory range is neither open nor in a state where closing a different page is necessary, then such a situation is labeled as “page empty”.

[0025] FIG. 4 illustrates a block diagram for one embodiment of select-signal generator 100 and paging policy modifier 102. Starting with select-signal generator 100, the generator 100 has counter 404 and signal generator 408. More particularly, counter 404 receives input signals as shown in FIG. 1. In this embodiment, the input signals are CloseToOpen signal 400 and Re-Opening signal 402. Each time the memory controller closes a page in order to open another, CloseToOpen signal 400 is asserted. In other words, in one embodiment, the memory controller's paging policy leaves a page open until it inhibits another access. As a result, a page may remain open for a number of accesses or cycles. This type of paging policy is referred to as a non-aggressive paging policy.

[0026] In contrast, each time the memory controller opens a page which would already have been opened if not for its preemptive paging policy, Re-Opening signal 402 is asserted. Preemptive paging policy refers to a policy, which may forcefully close a page after each access. Such a policy is also refers to as an aggressive paging policy.

[0027] In one embodiment, assertion of CloseToOpen signal 400 increments counter 404, and assertion of Re-Opening 402 signal decrements counter 404. Counter 404 maintains a cumulative result of these assertions of input signals and presents the result to signal generator 408 through signal path 406. This cumulative result indicates the effectiveness of the existing paging policy. For instance, a high cumulative result suggests many pages are left open and suggests switching to an aggressive paging policy. On the contrary, a low result suggests preemptive closing of many pages when the same pages are still frequently accessed. In that low result scenario, adopting a non-aggressive paging policy may be preferred.

[0028] In addition, one embodiment of signal generator 408 establishes a threshold for switching from one paging policy to another. When the cumulative result from counter 404 reaches or exceeds the established threshold value, signal generator 408 asserts select signal 104. This threshold value can either be a predetermined and fixed value or an adjustable value.

[0029] When paging policy modifier 102 receives select signal 104, its selector 414 has a group of distinctive paging policies, such as 410 and 412, to choose from. In one embodiment, Type-I paging policy 410 is the mentioned aggressive paging policy, and Type-N paging policy 412 is the mentioned non-aggressive paging policy. Depending on the value of select signal 104, either existing paging policy 106 remains unchanged or is replaced by either 410 or 412.

[0030] FIG. 5 demonstrates a block diagram of another embodiment of select-signal generator 100 and paging policy modifier 102. Unlike the embodiment shown in FIG. 4, this embodiment utilizes two counters and has four input signals. Moreover, the two counters, counter A 500 and counter B 502, are enabled separately depending on existing paging policy 106. Specifically, when existing paging policy 106 is an aggressive paging policy, counter A 500 is enabled. When it is a non-aggressive paging policy, counter B 502 is enabled. Counter A 500 and B 502 also receive input signals, such as Pempty signal 504, Re-Open signal 506, CloseToOpen signal 508 and PHit signal 510.

[0031] In conjunction with the previously discussed memory entry table 304, FIG. 6 illustrates a flow chart of a process to assert these aforementioned input signals. In particular, the FOR loop (block 600) compares every entry of memory entry table 304 with the requested memory address, Ain. When there is a match, the corresponding PageOpen field shown in column 302 is checked (block 602). If the field in column 302 indicates true, the page corresponding to the requested memory address is open and PHit signal 510 is asserted (block 604). Asserting PHit signal 510 suggests an occurrence of the previously described “page hit” situation. However, if the field in column 302 indicates false, Re-Open signal 506 is asserted. In other words, the previously described “page miss” situation has occurred.

[0032] On the other hand, if the FOR loop (block 600) does not identity any matching entries in memory entry table 304 for the requested memory address and all entries in the table are indicated to be open (block 608), CloseToOpen signal 508 is then asserted (block 610). Thus, before opening another page, closing of a different page is required. Similarly, even if not all the pages are open, as long as opening a page depends on closing another page (block 612), CloseToOpen signal 508 is still asserted. When no page dependency exists and the requested memory address is not in memory entry table 304, PEmpty 504 signal is asserted (block 616).

[0033] FIG. 7 shows a flow chart for incrementing and decrementing counter A 500 and counter B 502 with these discussed input signals. If existing paging policy 106 is shown to be the aggressive paging policy (block 700) and PEmpty signal 504 is shown to have been asserted (block 702), counter A 500 is enabled and decremented (block 706). Nevertheless, with the aggressive paging policy, if PEmpty signal 504 has not been asserted but Re-Open signal 506 has, counter A 500 is incremented (block 708). Since the aggressive paging policy preemptively closes pages, too many assertions of Re-Open signal 506 suggest changing to a non-aggressive paging policy. On the other hand, assertions of PEmpty signal 504 suggest a lack of page dependencies and maintain the aggressive paging policy as existing paging policy 106.

[0034] When existing paging policy 106 is a non-aggressive paging policy and PHit signal 510 is shown to have been asserted (block 710), counter B 502 is decremented (block 712). If PHit signal 510 is not asserted but CloseToOpen signal 508 is, counter B 502 is incremented (block 714). As has been mentioned previously, a non-aggressive paging policy often leaves pages open for some number of accesses or cycles before closing them. Assertions of PHit signal 510 signify occurrences of page hits and maintain the non-aggressive paging policy as existing paging policy 106. On the contrary, assertions of CloseToOpen signal 508 suggest page dependencies and also suggest switching to the aggressive paging policy.

[0035] One embodiment of the disclosed select-signal generator 100 and paging policy modifier 102 as shown in FIG. 5 may adopt a state machine implementation. Specifically, FIG. 8 illustrates transitions between state 800, where an aggressive paging policy is adopted, and state 802, where a non-aggressive paging policy is enforced. When counter A 500 reaches a predetermined threshold, or Max as denoted in FIG. 8, state 800 transitions to state 802. Similarly, when counter B 502 reaches Max, state 802 transitions to state 800.

[0036] It should be emphasized that although two paging policies, aggressive and non-aggressive, are discussed specifically, the disclosed paging policy modifier 102 may select from more than two distinct types of paging policies to generate existing paging policy 106. Moreover, although up to four input signals are illustrated in the figures, the disclosed select-signal generator may handle many more input signals than the described four. Finally, although assertions of particular input signals increment or decrement counter A 500 and counter B 502, it should have been apparent to one ordinarily skilled in the art to assert other input signals and manage counters differently without exceeding the scope of this disclosure. For example, the select-signal generator may look for particular trigger patterns formed by the input signals rather than tracking the number of assertions of the input signals.

[0037] Thus, a method and apparatus of dynamically adjusting a memory system's existing paging policy have been disclosed. Although the method and apparatus have been described particularly with reference to the figures, the method and apparatus may appear in any number of systems and still perform all the discussed functionality. It is further contemplated that many changes and modifications may be made by one of ordinary skill in the art without departing from the spirit and scope of the disclosure.