Abstract:
A memory controller includes an incrementer for predicting a next address to be asserted by a processor. The incrementer, structurally a counter, is configurable to wrap at a wrap boundary and to indicate when a predicted address crosses a page boundary if the memory is in page mode. This incrementer provides accurate predictions even where successor addresses are on different pages or, in the case of address loops, even in some cases in which the successor address is not consecutive. Thus, the number of accurate address predictions is increased, enhancing overall performance. The invention has particular applicability to signal processing applications with instructions loops that cross one or more page boundaries.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    The present invention relates to computers and, more particularly, to memory controllers for computers. A major objective of the invention is to provide for more effective speculative addressing by a memory controller.  
           [0002]    Much of modern progress is associated with the increasing prevalence of computers. A typical computer has memory for storing data and instructions and one or more processors (e.g., a “central processing unit” or “CPU”) for executing the instructions and manipulating data accordingly. The instructions executed by computers are relatively simple; complex tasks can be accomplished by executing programs with large numbers of instructions. The prowess of computers is largely due to the speed with which the instructions can be executed.  
           [0003]    Advances in computer technology have provided dramatic increases in computer performance. As dramatic as the advances have been, there is an insatiable demand for more computing power. One speed bottleneck is the time it takes for data and instructions to be transferred between processor and memory. While, in principle, processor would communicate directly with memory, the rapid design cycles for both processor and memory make it difficult for the processors and memories to interface optimally upon introduction to the market.  
           [0004]    For example, some memories provide for a paged mode in which it can be assumed that only low-order address bits need to be examined to determine a next address. Since fewer address lines need to be examined, the memory can respond to addresses more rapidly. When a page change is required, a page-boundary detection signal is to be sent to the memory, in which case the memory responds by looking at all the address bits. In general, processors are not “aware” of memory specifics, such as the presence of a page mode, so there is a problem of optimally interfacing processors and memory.  
           [0005]    Memory controllers can be designed in a relatively short time to interface between a processor and a memory type so that the optimal memory-operating mode could be used. The presence of the memory controller adds a potential latency to memory accesses, since instead of being transmitted directly to the memory, an address asserted by a processor must be forwarded to or translated and then forwarded to the memory. On the other hand, a memory controller can speed up accesses by accessing memory in anticipation of predicted next addresses. Typically, memory addresses are accessed sequentially, so the prediction can simply involve selecting the next address in a series. Some processors indicate whether the next address is sequential or not, so the validity of the prediction is known even before the next address is received.  
           [0006]    The predictive approach improves performance to the extent the predictions are accurate. Typically, the predictions are accurate when the addresses are sequential and do not cross page boundaries. An objective of the present invention is to provide for further performance improvements by enlarging the class of accurate predictions.  
         SUMMARY OF THE INVENTION  
         [0007]    The present invention addresses two important cases of address prediction: wrapping of an address in case of crossing wrap boundaries in a burst transfer at the processor side, and crossing page boundaries at the memory side. The present invention provides a memory controller that provides predictive addresses that wrap at a programmable wrap boundary and/or provides predictive page-boundary detection signals. In one aspect the invention is a memory controller with a incrementer in the form of a programmable counter, while in another the invention is a computer system with such a memory controller. The inventive method can involve the predictive wraps, predictive page boundary detections or both.  
           [0008]    In the case of a wrap boundary of a burst transfer, the invention provides for wrapping without interrupting the performance enhancement achieved by accurate address predictions. Where predictive page boundaries are used, a series of accurate predictions can proceed with little or no interruption across page boundaries. The predictive wraps and page boundary detections can be used together in the case of a loop that extends across page boundaries. These and other features and advantages of the invention are apparent from the description below with reference to the following drawings.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]    [0009]FIG. 1 is a schematic logic diagram of a computer system with memory controller in accordance with the present invention.  
         [0010]    [0010]FIG. 2 is a schematic logic diagram of a one-bit-counter element of the memory controller of FIG. 1.  
         [0011]    [0011]FIG. 3 is a schematic diagram of a portion of an alternative memory controller incorporating a carry-select technique for enhanced performance.  
         [0012]    [0012]FIG. 4 is a flow chart of a method of the invention utilized in the computer system of FIG. 1. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0013]    In accordance with the present invention, a computer system API comprises a processor (CPU)  11 , a system bus  13 , memory  15  and a memory controller  20 , as shown in FIG. 1. Memory controller  20  has a system-bus interface  21 , a page-value register BP, an incrementer  23 , a multiplexer  25 , and a memory interface  27 . Interfaces  21  and  27  are functional elements rather discrete structural elements as they are co-located with processor  11  and bus  13  on a single integrated circuit. Structurally, incrementer  23  is a programmable counter with N bit-counter elements CT 0 -CTN and an OR-gate G 1 .  
         [0014]    Processor  11  transmits via system bus  13  to memory controller  20  the following signals: data DATA 1 , addresses AD, a transfer-size indication TS, and a wrap-boundary value BW. In FIG. 1, TS=001 if the transfer size is byte; TS=010 if the transfer size is two-bytes (half word in a 32-bit system or a word in a 16-bit system); TS=100 if the transfer size is four-bytes (word in a 32-bit system or double word in a 16-bit system). In supervisor mode, processor  11  can provide a page boundary value to register BP.  
         [0015]    The data can include data to be stored in register BP, which is located within the address space of processor  11 . Associated with addresses AD are indications of whether an operation is a read or a write, and whether an address is sequential or not. In the event of a read operation, data is transferred from memory  15 , through memory controller  20 , via system bus  13 , and to processor  11 .  
         [0016]    As shown in detail in FIG. 1, bit-counter element CT 1  includes a one-bit adder AD 1 , a NAND gate G 2 , and two AND gates G 3  and G 4 . Element CT 1  accepts the lowest order bits from each of the page and wrap registers BP and WP, the second least-significant bit of transfer-size signal TS and the second least-significant bit of an address signal AD. The address signal AD and the transfer-size signal TS are provided to respective addend inputs of adder AD 1 . A carry-in is also provided from bit-counter element CT 0 . In effect, the output AQ 1  of adder AD 1  is the second-least significant bit of the successor address for the given word width. The remaining bit-counter elements CT 0  and CT 2 -CTN provide the remaining bits of the successor address. Thus the function of incrementer  23  is to provide the successor address to the address presently asserted by processor  11 .  
         [0017]    Except for obvious simplifications, bit-counter elements CT 0 -CTN are similar. For example, bit-counter element CT 3  is shown in FIG. 2. Instead of a 1-bit adder, it has a 1-bit incrementer including an XOR gate G 5  and an AND gate G 6 . The remaining logic gates, NAND gate G 7 , and AND gates G 8  and G 9  correspond with counterparts in bit-counter element CT 1 . XOR gate G 5  has address bit AD 3  and carry-in C 13  as its inputs to generate predictive address bit AQ 3 ; AND gate G 6  has the same inputs to generate in conjunction with gates G 7 , G 8 , and G 9 , page boundary detection bit DT 3  and carry out CQ 3 .  
         [0018]    Bit-counter element CT 4  is essentially similar to bit-counter element CT 3 . Bit-counter elements CT 5 -CTN also employ 1-bit incrementers, but the ancillary logic is reducible due to the one or more constant inputs. The page boundary inputs to bit-counter elements CT 5 -CTN are held high because memory control  20  does not provide for page sizes greater than 32 bytes. The word-boundary input to bit-counter element CT 5  is controlled by word-boundary signal BW while the corresponding inputs to bit-counter elements are held high to accommodate a maximum 64-byte wrapping burst transfer. Bit-counter element CT 0  can be a one-bit adder with no carry-in signal.  
         [0019]    A method M 1  of the invention practiced in the context of system AP 1  is flow-charted in FIG. 3. At step S 1 , the page boundary value is entered into register BP. Typically, this occurs in supervisor mode and the page-boundary value is not changed during user program execution. In system AP 1 , register BP is a conventional writable register. However, in applications where there is no need to change the page boundary value, it can be hard-wired or encoded in read-only memory.  
         [0020]    At step S 2 , a wrap-boundary is asserted during user program execution. The wrap boundary is a value at which incrementer  23  resets to zero, and thus serves as the count modulo. This count modulo can be changed during program execution so that loops of different sizes can be managed optimally.  
         [0021]    At step S 3 , processor  11  initiates a read or write operation by asserting an address, along with an address-width value, and a sequential/nonsequential indication SQ. Memory controller  20  uses the sequential/nonsequential indication to determine, at step S 4 , whether the operation is sequential or not. When a sequential address is indicated, multiplexer  25  selects AQ; when a non-sequential transfer is indicated, multiplexer  25  selects address AD′. In an alternative embodiment, a memory controller selects the counter output except when a comparator indicates it is not equal to the address asserted by the processor.  
         [0022]    If the address is not sequential, method M 1  proceeds to step S 4 . The data stored at the location indicated by the asserted address is selected for data transfer. If a read operation is requested, the data is transferred at step S 5  from memory  15  via bus DATA 3  to memory interface  27 , via data bus DATA 2  to system-bus interface  21 , to system bus  13 , to processor  11 . If a write operation is requested, the data is transferred from processor  11 , via system bus  13 , to system-bus interface  21 , via bus DATA 2 , through memory interface  27  to memory  15 . If at step S 4 , the address is determined to be sequential, the data transferred at step S 5  is the data already accessed from memory  15  from address location AQ.  
         [0023]    After either step S 5  or S 6 , incrementer  23  generates a predictive address at step S 7 . This is achieved by adding the address width indicated by transfer-size signal TS to the currently or most recently asserted address AD′. The addition is modulo BW so the address wraps at the programmed wrap boundary. Also, if a page boundary is met, a detection indication is generated along line DTQ. At step S 8  the data at the predicted address in memory  15  is accessed and buffered at memory interface  27 . This data is transferred if the prediction is confirmed and overwritten if it is disconfirmed at the next iteration of step S 3 .  
         [0024]    The method iterates generally by returning to step S 3 , in which the processor asserts the next “asserted” address. However, as indicated by a dashed line in FIG. 3, a next iteration can involve setting a new wrap boundary at step S 2 . In general, page boundaries are less likely to be changed during execution of a program.  
         [0025]    The speed with which predictive addresses can be generated in system API is limited by the carry-propagation design of incrementer  23 . Bit-counter element CT 1  cannot determine its carry and address outputs until bit-counter element CTO determines its carry output. Likewise, bit-counter elements CT 2 -CTN require carries from lower-order bit-counter elements to determine their results. Thus, a carry must propagate through N stages for a predictive address to be generated.  
         [0026]    To reduce the latency due to carry propagation, a carry-select counter  40 , shown in FIG. 4, can be used instead of incrementer  23 . Conceptually, counter  40  divides its positions, 0-7, into low and high-order groups. Four least-significant bit counter elements constitute the low order bit-counter group  41 , which thus provides a 4-bit output AQ[3:0]. There are two high-order groups  42  and  43 , each of which includes bit-counter elements for the four most-significant bit positions (4-7). Groups  42  and  43  differ only in that bit-counter group  42  has its carry-in hard wired to 0, while group  43  has its carry-in hard-wired to 1.  
         [0027]    In effect, groups  42  and  43  pre-calculate the high-order results for the two possible results for the carry-out Cq of low-order group  41 . When the low-order carry-out is determined, it is used to select one of the two high order results. If CQ 3  is 0, then a multiplexer  44  selects the results of high-order group  42 ; if CQ 3  is 1, then multiplexer  44  select the results of high-order group  43 . The selected detection signals DT[4-7] are ORed with the detection signals DT[0-3] from low order group  41  to determine the overall page-boundary detection signal DT[0-8]. In this case, the latency required for generating the predictive address is reduced almost by half relative to incrementer  23 , but at the expense of additional integrated-circuit area due to the extra high-order bit-counter elements and multiplexer  44 .  
         [0028]    The present invention has applicability to computers and integrated circuits generally, and especially to signal processing applications. The invention applies using different host systems, different memory controller designs and different counter designs. These and other variations upon and modifications to the described embodiments are provided for by the present invention, the scope of which is defined by the following claims.