One Word Buffer Memory System

The present invention relates generally to randomly accessible memory systems.

Memory systems operate in a generally serial fashion. That is, the memory system will handle a request for data from one particular address, operate upon that request, supply the requested data, and then turn and start the next request. Generally, the first request must be completed before the second request can be initiated. When the memory system is a large one, and is randomly accessible, the access time for a particular data word may be significant with respect to the overall operating system of which the memory system is a part.

Buffer memories have been developed which attempt to decrease the access time necessary for some data words requested. Generally, these buffer memory systems try to anticipate future requests for data words by providing a separate and faster buffer memory into which are stored selected data words which the memory system feels may be requested in the future. If such data words are requested, they will be available without the necessity of going to the main memory. Generally, the data words which are selected for storage in the buffer memory are tied in some fashion to the address of a normal memory request. For example, when one particular data word is requested from main memory, more than just that data word may be loaded into the buffer memory. Generally, this is accomplished on a page or block basis in which data words are grouped into pages or blocks and when one data word within that page or block is requested, then all of the data words within that page or block are loaded into the buffer memory and then are available for subsequent memory requests. When a subsequent request occurs to one of the other data words within the page or block, that data can be made available much quicker than if that data were not located in the buffer memory.

The basis for loading a page or block of data words into the buffer memory when one of the data words is requested from the memory system is based on the limited assumption that requests to the memory system will tend to be somewhat sequential in nature based on the general flow of a software program. If the flow is generally sequential, then the next data word following that data word which has been requested from the memory system will be the most likely candidate for future accesses. As buffer memories are increased in size and the data words which are loaded into the buffer memory become larger and larger, the benefit, or rather the likelihood that the next request will be a request for one of those data words, increases. But such increase is not in direct proportion to the number of data words being added to the buffer.

Buffer memories of present memory systems are somewhat expensive to construct. The buffer memory requires not only the randomly accessible memory unit in which the data words contained in the buffer memory are stored, but also includes an associative memory which is used to determine which data words are present in the buffer memory and for matching the address of a future request to those addresses of data words present in the buffer memory.

The one word buffer memory system of the present invention provides the advantage of low cost as would result from not having a buffer memory and the performance advantage of having a buffer memory.

Because of existing registers and components in a normal non-buffered memory system, a one word buffer memory can be implemented according to the present invention by adding only a plus one adder, an address register, a comparator and a selector.

The normal memory system normally includes an address register, a randomly accessible memory unit, a data-in register and a data-out register. The plus one adder is added by the present invention for incrementing the address contained in the address register. The result is then stored in a newly added address register, called the address-plus-one register. The randomly accessible memory unit will be sequentially accessed by the address-plus-one register when it has completed the normal access with the address register. When a new request occurs, a comparator compares the new contents of the address register and the address-plus-one register. If they match, the data will already be available from the sequential access following the previous normal access. If they do not match, the randomly accessible memory unit may be accessed in the normal manner. The selector is utilized for sequentially selecting between the address register and the address-plus-one register for the address input to the randomly accessible memory unit.

Features of the present invention will become more readily apparent by having reference to the accompanying drawings in which:

FIG. 1 is a schematic representation of the one word buffer memory system including components already existing in a present memory system;

FIG. 2 is a timing diagram of the one word buffer memory system illustrated in FIG. 1 when sequential requests to the memory system are not for sequential data words therein;

FIG. 3 is a timing diagram of the one word buffer memory system of FIG. 1 when sequential requests to the memory system are to sequential data words contained therein; and

FIG. 4 is a flow chart illustrating the sequencing of events of the one word buffer memory system illustrated in FIG. 1.

FIG. 1 illustrates a schematic of the one word buffer memory of the present invention. Since the operation and construction of the one word buffer memory depends and relies upon existing components contained in an existing memory system, these components are also illustrated in the schematic diagram in FIG. 1. An address register 10 is provided for holding the address of the data word requested from the memory system by an external requestor. An example of a component, a common register circuit, which could be used for the address register 10 is a Motorola MC10175. This address is latched into the address register 10 by the load address register signal 12 coming from the timing and control circuitry 14 which is initiated by the memory request signal 16 which is transmitted by the external requestor. The address from the address register 10 is then available on address signals 18 and 20 and will be directly or indirectly presented to the address input of the randomly accessible memory unit 22. An example of a cmponent, a RAM memory circuit, which could be used for the randomly accessible memory unit 22 is a Motorola MCM10146. Note that in the existing memory systems, the selector 24 is not present and address signals 18 are connected directly to address signals 20 which are in turn connected to the randomly accessible memory unit 22. The timing and control logic 14 sends an initiate memory signal 26 to the randomly accessible memory unit 22. The randomly accessible memory unit 22 then obtains the requested data word and transmits it along data lines 28 to a memory data register 30. An example of a component, a common register circuit, which could be used for the memory data register 30 is a Motorola MC10175. Memory data register 30 is latched by a load memory data register signal 32 supplied from the timing and control circuitry 14. At this point, the data contained in the memory data register 30 may be made available to the requestor directly or in the preferred embodiment of the memory system it may further be operated on by an error correction code apparatus which will detect and correct limited amounts of bit errors in the data obtained from the randomly accessible memory unit 22. This error correction circuitry is a standard part of some existing memory systems. An example of a component, an error correction circuit which could be used as the error correction circuitry is the Motorola MC10163 error detection-correction circuits. A discussion of such prior error correction circuitry may additionally be had by referencing Motorola MECL Integrated Circuits published by Motorola, Inc., in 1978 at pages 3-62 to 3-67. Thus, the data contained in memory address register 30 is supplied to the error correction circuitry 34 and after error correction is supplied to an interface register 36. An example of a component, a common register circuit, which could be used for the interface register 36 is a Motorola MC10175. The interface register 36 is latched by a load interface register signal 38. The output of the interface register 36 then represents the data 40 which is supplied to the external requestor along with a request acknowledge signal 42 supplied from timing and control circuitry 14. The existing memory system may also include a data in register 44 to which is supplied the data input from the external requestor and which supplies such data to the randomly accessible memory unit 22 for write operations. An example of a component, a common register circuit, which could be used for the data in register is a Motorola MC10175.

It can be seen from the operation of the memory system described in FIG. 1 that addresses from serial memory requests are loaded into address register 10 and the randomly accessible memory unit 22 is initiated. A delay occurs while the randomly accessible memory unit 22 obtains the particular data word and until it can be loaded into the memory data register 30. Another delay occurs while the error correction through the error correction circuitry 34 occurs and until the corrected data is available at the interface register 36. It is only at this point that a request acknowledge signal 42 may be sent to the external requestor and the data be made available along data lines 40. When a subsequent request occurs the same process is completed anew. The very same delays that occurred during the first operation are again present in the second operation.

The addition of a few components to the existing memory system thus far described can increase the performance of the memory system dramatically.

Again with reference to FIG. 1, the address from the address register 10 is made available on address signals 18 which is now supplied to one of the inputs of a two input selector 24 instead of directly to the address inputs of the randomly accessible memory unit 22. An example of a cmponent, a common selector circuit, which could be used for the selector 24 is a Motorola MC10158. The selector is controlled by select signal 46 supplied from timing and control circuitry 14. The output of the selector 24 is then supplied to address lines 20 which are connected to the address inputs of the randomly accessible memory unit 22. During the normal request operation, the select signal 46 wll select the address lines 18 to pass through and be present on address lines 20. This is the normal access mode of the memory system.

The address from the address register 10 along address lines 18 is also made available to an adder 48. This is one input to adder 48 since the sole function of the adder 48 is to add one to the address present on address lines 18. The other input of a two input adder, such as adder 48, is hardwired to a plus one. An example of a component, a common ader, which could be used for the adder 48 is a Motorola MC10180. Present on lines 50 after a short delay through adder 48 is the result of the contents of the address register 10 plus one. This incremented address present on lines 50 is then loaded into an address plus one register 52. An example of a component, a common register, which could be used for address plus one register 52 is a Motorola MC10175. Address plus one register 52 is latched by a load address plus one register signal 54 supplied by a timing and control circuitry 14. The output of address plus one register 52 is supplied to the second input of selector 24. As soon as the randomly accessible memory unit 22 is done with the address from address register 10 on a normal memory request, the timing and control circuitry 14 will change select line 46 and present the address from address plus one register 52 through selector 24 and address lines 20 to the address input of the randomly accessible memory unit 22. While the data word previously obtained from the address supplied by address register 10 is being moved through the error correction circuitry 34 to the interface register 36, the timing and control circuitry 14 will initiate the randomly accessible memory unit 22 by sending the randomly accessible memory unit 22 an initiate memory signal 26 which will cause a data word at the address contained in the address plus one register to be supplied memory data register 30. The contents of the address plus one register 52 are also supplied to a comparator 56. An example of a component, a comparator, which could be used for the comparator 56 is a Motorola MC10166. The comparator's other input is supplied from address lines 18. When a next or second request is received by the memory system and the associated new address is loaded into address register 10, the comparator 56 will compare the new, second, address as supplied by address lines 18 with the previous address plus one register 52 first address which was previously supplied to the comparator 56. If the comparator 56 finds that a match has occurred, it means that the second requested address is exactly one more than the first requested address. In that case, the randomly accessible memory unit 22 has already been accessed and that data is presently located in memory data register 30. Thus, the comparator 56 sends a match signal 58 to timing and control circuitry 14 which then does not initiate the randomly accessible memory 22 with a new initiate memory signal 26, but instead sends the data from memory data register 30 through the error correction circuitry 34 into the interface register 36 which supplies that data to the external requestor along data lines 40.

If the comparator 56 determines that the addresses contained in address register 10 and address plus one register 52 do not match, it sends the appropriate signal to timing and control circuitry 14 which then selects address lines 18 to pass through selector 24 to address lines 20 and sends an initiate memory signal 26 to the randomly accessible memory unit 22. The word at the new address is then obtained and presented to memory data register 30 where again it is supplied through the error correction circuitry 34 to the interface register 36 and made available to the external requestor along data lines 40.

FIG. 1 has illustrated the connection of the major components of both the existing memory system and the interconnection of the components added to the existing memory system to form the one word buffer memory system of the present invention. The discussion of FIG. 1 has also included illustrative comments relative to the sequencing of events occurring within the schematic of FIG. 1. Reference to FIG. 2 and FIG. 3 will illustrate in detail the exact sequencing and occurrence of events during the operation of the one word buffer memory system in both the case in which consecutive memory requests are to consecutive sequential addresses (FIG. 3) and the case in which consecutive memory requests are not to consecutive sequential addresses (FIG. 2).

Illustrated in FIG. 2 is a detailed timing diagram showing all of the signals which enter and leave the timing and control circuitry 14 located in FIG. 1. The exact signals and timing of the signals illustrated in FIG. 2 provide both a basic understanding of the sequence of events occurring within the one word buffer memory system and enable one of ordinary skill in the art to construct an appropriate timing and control mechanism 14 for implementing the one word buffer memory system. Memory request signals 16 supplied by the external requester initiates the timing and control cycle. The load address register signal 12 is supplied immediately upon receipt of the memory request signal 16. The select signal 46 is initially set to select the address register and will later in the cycle switch to select the address plus one register as soon as the randomly accessible memory unit 22 is done with the access requiring the address register 10. Soon after the address is latched into the address register 10 by the load address register signal 12, the initiate memory signal 26 is activated by sending it low and it remains activated until the randomly accessible memory unit supplies stable data indicated by data signals 28. The load memory data register signal 32 is then activated following the stabilization of data signals 28. As soon as the memory data register 30 is loaded by load memory data register signal 32, the initiate memory signal 26 is deactivated, the select signal 46 is switched to select the address plus one register and the initiate memory signal 26 is again activated to obtain the data located at address plus one. In the meantime, the data from the address contained in memory data register 30 is sent through error correction circuitry 34 and when that is complete, the interface register 36 is loaded by activation of load interface register signal 38. As soon as the load interface register signal 38 is activated, or in this case slightly before, due to known transmission delays, a request acknowledge signal 42 may be sent to the external requestor. At that point, the external requestor then deactivates memory request signal 16. While the data from the location address contained in the interface register 36 is being sent to the external requestor, as soon as the data lines 28 become the memory data register 30 is available. As soon as data lines 28 become stable, at time T.sub.25, from the second initiate memory signal 26 activation, then data from address plus one is loaded into the memory data register 30 by another activation of load memory data register signal 32. The external requestor may at some time subsequent then send a second memory request 16 signal. Again the load address register signal 12 is activated and the select signal 46 again selects address register. As soon as the address register is selected, initiate memory signal 26 is again activated to obtain the data word from the randomly accessible memory 22. If this subsequent, second, memory request is not for the next consecutive address then the match signal 58 indicates that there is no match between this new, second, address contained in address register 10 and the previous, first, address now incremented and contained in address plus one register 52. This indicates that the data previously obtained and stored in the memory data register 30 is not the requested data and new data must be obtained from the randomly accessible memory. The remainder of the signals then in the second portion of FIG. 2 are then repeats of the first cycle. Again, the address plus one register 52 is loaded with the incremented address from address register 10 and data at this incremented address is then made available for the next cycle by being temporarily stored in memory data register 30.

FIG. 3 represents the same signals discussed in FIG. 2, but illustrates the exact timing and sequencing when the second address loaded into address register 10 is the consecutive sequential address to the first address loaded into address register 10. In FIG. 3 the first set of timing signals from T.sub.0 through T.sub.25 are exact duplicates of the cycle described in FIG. 2. After T.sub.25, however, the sequence and timing of the signals changes to take advantage of the prefetched word contained in the memory data register which is effectively now a one word buffer. Here in FIG. 3 memory request signal 16 goes low and will not again be reactivated until after activated time T.sub.25 following the completion of the first memory cycle. During a second, subsequent, memory cycle load address register signal 12 is activated to latch the new address into the address register 10. Select signal 46 is set to select address register 10 and the initiate memory signal 26 is again activated to request that address from the randomly accessible memory unit 22. Operations to this point are identical to the operation contained in FIG. 2. However, now the new, second, address latched in address register 10 and the previous first address now incremented and contained in address plus one register 52 are identical since the second request is for the next consecutive sequential address. Match signal 58 goes low indicating that a match has occurred. The timing and control circuitry 14 then immediately cancels the initiate memory signal 26 which has the effect of canceling any memory operation occurring within the randomly accessible memory unit 22. Since match signal 58 indicates that a match has occurred, we know that the proper data is already loaded into the memory data register 30 and that data is immediately sent through the error correction circuitry 34 and is loaded into the interface register 36 by load interface register signal 38 and a prompt request acknowledge signal 42 is sent to the external requestor. Note that this has all occurred and the request acknowledge signal 42 has been sent, in this instant, before T.sub.10 whereas in a normal non-match cycle, as in FIG. 2, the request acknowledge signal 42 is not sent until T.sub.20. This represents a sizable and significant increase in speed of the overall memory system. Also in the second cycle described in FIG. 3, note that once the match has occurred and the data previously obtained is loaded into the interface register 36 with load interface register signal 38, then the entire fetch of the data at still the next consecutive address transpires. The address loaded into address register 10 is again incremented and loaded into address plus one register 52 by load address plus one register signal 54. The memory is again initiated by initiate memory signal 26 not to obtain the data word from the current request, but again to prefetch the next sequential data word in case the next request and the next address loaded into address register 10 is also sequential. This data once obtained and stable at approximately time T.sub.15 on the second cycle, is loaded into the memory data register 30 by load memory data register signal 32 and again a new cycle or sequence of events can occur upon a request to memory through memory request signal 16.

From reference to the circuit diagram in FIG. 1 and the two extensive and complete timing charts in FIGS. 2 and 3, it should now be readily apparent how the operation of the one word buffer memory system operates and the time advantage obtained therefrom. Note that the only components added to the existing memory system include the adder 48, the address plus one register 52, the comparator 56 and the selector 24. All other components already existed in the initial memory system which did not contain the one word buffer.

The overall sequence of events may now be described by having reference to the flowchart contained in FIG. 4. In the flowchart, the first memory cycle is initiated by the external requestor and the address register 10 is loaded with the requestor's first address as step 100. The selector 24 is changed to select the address register 10 to be applied to the randomly accessible memory 22 as step 102. The randomly accessible memory 22 is initiated to obtain the data at that address as step 104. Since there may have been a previous cycle in which the next sequential address from a previous request has been prefetched, a comparison in comparator 56 is now made between the present address loaded in the address register 10 and the incremented address from the previous request as located in address plus one register 52 and a determination is made as to whether those addresses match in step or do not match 106. If the addresses match, this indicates that that data has already been prefetched and is presently loaded into the memory data register 30. This is indicated on the flowchart by following the path 110 from the compare step 106. Since the data desired is already in the memory data register 30, the randomly accessible memory unit 22 is now stopped by canceling the initiate memory signal 26 in step 112. If the compare step 106 indicates that there is no match, this indicates that the data contained in the memory data register 30 is not the proper data and hence, the memory cycle initiated at step 104 for the present data must be completed. This is indicated by following the path 108 on the flow diagram and loading the memory data register 30 with the proper data in step 116. Since the proper data is now contained in the memory data register 30 at this point for both cases whether there was a match or whether there was a non-match, the two paths now merge and the address plus one register 52 is loaded in step 114 and the selector 24 is moved to select the address plus one register 52 in step 118. The randomly accessible memory unit 22 is initiated in step 120 to prefetch the next sequential data word should it be requested. Error correction in the error correction circuitry 34 is accomplished on the previously obtained data which has been resident in the memory data register in step 122. As soon as the error correction has taken place, the data for the present cycle is loaded into the interface register 36 as step 124. Once the data of the present cycle has been loaded into the interface register 36, the prefetched data for the next cycle may be loaded into the memory data register 30 in step 126. At this point, the external requestor may then begin a new cycle by supplying a new address and the flowchart moves back to step 100 where the address register 10 is again loaded and the entire cycle is again repeated. Note that the cycles are very similar whether or not a match occurs during the compare at step 106. If the compare does indicate a match, notice that the only action taken which is different is to stop the memory initiate from the initiate step 104 since the desired data has already been loaded into the memory data register 30 during step 126 on the previous cycle. If a match is not indicated at step 106, then, of course, the randomly accessible memory 22 must be allowed to complete its fetch and when that data is available, it is loaded into the memory data register 30 at step 116. At this point the sequence again becomes common. While there is not a lot of difference in the flowchart, it must be emphasized that there is a great deal of difference in terms of the time required to perform both paths. In terms of the match following path 110, the memory cycle is simply stopped and this takes only a very short period of time. If there is no match and path 108 must be followed, then the randomly accessible memory unit 22 must be allowed to complete its normal access cycle. This can and does take a substantial portion of time and it is exactly this time that the one word buffer memory of the present invention is saving.

Thus, it can be seen that there has been shown and described a novel one word buffer memory. It is to be understood, however, that various changes, modifications, and substitutions in the form of details of the described memory system can be made by those skilled in the art without departing from the scope of the invention as defined by the following claims.