Patent Publication Number: US-5630045-A

Title: Device and method for fault tolerant dual fetch and store

Description:
FIELD OF THE INVENTION 
     This invention relates to a method for allowing parallel stores in a fault tolerant multiprocessing system, without a need for software maintenance of redundant copies of all data in storage. 
     BACKGROUND OF THE INVENTION 
     A fault tolerant system is designed to allow continuous service by the system during the occurrence of a hardware failure. In such cases, to restore data and maintain its integrity, a master copy of the data generated by the computer is kept in storage somewhere in the main memory at all time. Therefore everytime data is compiled, it is usually preserved in some hard copy device such as a hard disc or a tape for future use. It is also common practice to keep dual copies of data, in case of hardware failures affecting the original copy. To keep the necessary storage at a minimum data is packed and the procedure of backing up data is time consuming, and causes overall performance degradation of the system. Storage is a critical element of a fault tolerant system. Tasks are terminated and have to be restarted when critical storage data is damaged, affecting the overall turn-around time for the completion of the program. It has been an on-going challenge to provide a data storing method that can selectively copy multiple copies of data into storage without affecting the performance of the system as a whole and to address the problem of data restoration after a hardware failure. 
     OTHER PATENTS RELATING TO THE FIELD OF INVENTION 
     U.S. Pat. No. 4,356,550 teaches a dual multiprocessor system with a plurality of power supplies and a method of recovery and an error detection and correction system in the memory of each processor. Although U.S. Pat. No. 4,356,550 uses a separate memory for each CP, but there is no teachings of a correction mechanism used for recovery of multiple memory bit errors. Similarly there is no teachings of a redundant storage which corrects as in the present invention. 
     U.S. Pat. No. 4,819,154 apparently discloses a multiprocessing system with a fault-tolerant computing and stored information sequentially written in two separate memory units. There are no teachings or suggestions of a method that allows parallel stores and fetches by using a multiprocessor system. 
     U.S. Pat. No. 4,933,823 apparently teaches a dual system of microprocessors with an active and a backup state, providing simultaneous processing of data or stores by continuously comparing signals. There are no teachings or suggestions of a method using asynchronous configuration of hardware and assignment of storage addresses in both system controllers, allowing selective assignment to either the primary or a secondary system controllers or choice or selective duplication. 
     U.S. Pat. No. 4,654,819 discloses a multiprocessing system and fault-tolerant computing and memory back-up system which allows back-up status information to be written from storage area for updating and backup status. There are no teachings or suggestions of a processor allowing parallel fetch and stores. 
     U.S. Pat. No. 4,933,835 appears to teach a dual microprocessor system capable of independently storing digital information on separate or parallel buses with a first and a second data processing elements. There are no teachings or suggestion of non-exclusive lines which are only to be stored in one SC concurrently with dual store to both SCs. 
     U.S. Pat. No. 4,317,169 apparently teaches a method for performing memory refresh operation where the memory refresh operation signal can be given to the memory unit in parallel with or without detracting from CPU operation. There are no teachings or suggestion of a fault tolerant system capable of handling parallel fetch and store operations. 
     U.S. Pat. No. 5,101,492 seems to disclose a method and apparatus for maintaining data redundancy and restoring data to a failed disk within a disk array in a manner transparent to the host system and user. However, this invention uses software to rewrite data to accomplish write restores to disk. There are no teachings or suggestions of a device and method for performing parallel stores. 
     U.S. Pat. No. 4,996,687 teaches a method and apparatus allowing fault recovery in a system whereby the system upset can be induced by external transient noise conditions. There is no teachings or suggestion or a method involving hard error recovery as discussed in the present invention. 
     U.S. Pat. 4,387,423 discloses a multiprocessing system with a rechargeable memory which is used for storage of software instructions and a memory refresh operation. There are no teachings or suggestions of a multiprocessing system capable of handling simultaneous stores and fetches. 
     SUMMARY OF THE INVENTION 
     Accordingly, an object of the present invention is to provide a device and method for allowing parallel stores in a fault tolerant multiprocessing system. 
     Another object of the present invention is to improve the performance and integrity of a fault tolerant system by providing a device and method that allows parallel stores without a need for software program maintenance of redundant copies of all data in storage. 
     Yet another object of the present invention is to provide a data storing method that can selectively copy multiple copies of data into storage without affecting the performance of the system as a whole. 
     Still another object of the present invention is to allow continuous service by the system during the occurrence of a hardware failure while improving performance and integrity of the system. 
     To achieve the above-mentioned objects, in one embodiment of the invention a method for the same is described, utilizing a multiprocessor system having at least two memory controllers. The invention can also be used in an environment where there is a plurality of central processors (CPs) which can be partitioned to provide a plurality of system sides for the multiprocessor system. This multiprocessor system also includes a plurality of input-output (I/O) processors; each of these CP and I/O processors being further defined as a requestor. 
     The present invention allows information to be accessed and stored by either memory controller in different areas of the memory. During the initialization process, each memory controller is designated a specific area in the memory for its usage. The physical address of the memory location is stored in separate logic arrays either indicating the actual physical address or a virtual address that can be translated at any time to reflect the physical address when the specified area designated to each memory controller needs to be accessed. The present invention provides access to either memory controller preventing continuous engagement of one of the memory controllers at all times. 
     Each requestor selects one of the memory controllers for each data space as a primary memory controller and the remaining memory controller as a secondary memory controller. The selection of these memory controllers as primary and secondary is stored by a unit of data in the logic array associated with each of these requestors. In addition, the logic array defines single or dual copy of data which may be selectively assigned to either primary or secondary memory controllers. 
     To protect data integrity, the present invention uses an interlocking data protection mechanism providing data access to only one of the requestors at any one time. The memory controllers determining an exclusivity ownership access status for these requestors and also removing this exclusivity ownership access when the requestor is no longer in need of accessing the data. 
     When a fetch or store command is issued by any of the requestors, each system controllers processes the command and provides the requestor with a response upon processing completion. The requestor, while waiting for this response, can perform any required data updating. A response must be received from both memory controllers. The primary memory controller in addition to the above-mentioned response also provides the requestor with data in pursuant to the earlier issued store or fetch command. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The subject matter which is regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of practice, together with the further objects and advantages thereof, may best be understood by reference to the following description taken in connection with the accompanying drawings in which: 
     FIG. 1 is a schematic diagram showing one embodiment of the present invention where a multiprocessor system configured into two sides, each side having a memory or system controller (SC), multiple central processor (CPs), an I/O processors and an extended storage; 
     FIG. 2 shows the steps of a CP update, in one embodiment of the present invention; 
     FIG. 3 is a schematic diagram of a store stack in a system controller; 
     FIG. 4 shows the configuration array within each memory controller, identifying each memory controller as a primary or secondary memory controller; 
     FIG. 5 compares the prior art approach to an I/O store instruction (5A) versus the steps occurring pursuant to an I/O store instruction in one embodiment of the present invention (5B); 
     FIG. 6 is a schematic diagram showing the steps of a dual page-in, according to one embodiment of the present invention; and 
     FIG. 7 is a schematic diagram showing the steps of a dual page-out, according to one embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     This invention is capable of providing a means to concurrently store multiple copies of data to storage reducing the performance overhead of serial waiting for multiple responses to the stores. FIG. 1 shows one embodiment of the present invention where a multiprocessor system 100, configured into multiple symmetric or asymmetric sides 105 and 110, with each side having a memory or system controller 120 and multiple processors 130 and or I/O processors 140 on each of the sides, as shown in FIG. 1. The sides of a multiprocessor can be reconfigured into independent systems or configured back to a multiprocessor system. FIG. 1 also shows each side having an extended storage 150. 
     The multiple processors 130 and I/O processors known as requestors 140, a data protection design is provided so that only one processor is changing a given line of data at one time in order that the latest or master copy of the data is used. An exclusivity bit is assigned to a line of data, when fetched, by a requestor. A requestor sets an exclusive fetch when data is to be changed. Each memory controller maintains a copy of the exclusivity bits. Before assigning a line of data to a processor, the memory controller verifies that no other requestor has assignment to that line of data. The memory controller removes previous ownership (a line of data, which has been stored exclusively) from all copies of the data when the new exclusive fetch request is honored. Likewise, when a requestor stores the data in a multiple copy storage system, both or all copies must be stored, before any other requestor can have access to any of the copies. If it is not a dual copy request only one store takes place. 
     Generally the method used in prior art has been for the requestor to wait for a successful response for all the stores before proceeding to the next instruction, passing a synchronization point). In the prior art, a processor will fetch exclusive data from one memory controller, wait for data and response. Data is updated by the processor and then stored to the one system controller, containing one copy of the data, wait for response and then store the same data to another memory controller, containing another copy of the same data, wait for response. However, in this store a fetch is required to access the data to be changed and then store the data. Exclusivity being allowed to be removed after the last memory controller response. This response mechanism does not require system controllers to process requests in lock step, allowing asymmetric systems to exist. 
     In the present invention as shown in FIG. 2, the requestor issues an exclusive fetch 410 to the primary memory controller and simultaneously to the secondary memory controller 415 and waits for responses from both memory controllers 420. The secondary memory controller noted by a modifier in the fetch command. The primary memory controller executes the cross interrogation with all other requestors to see that data is not being held exclusive. If held exclusive by another CP requestor, exclusivity is removed by signalling the original owner. The original owner signals release of the memory controller when related. Changed data arrives at SC store stacks. When the memory controller removes the data from the store stack to storage old ownership is removed. If data was not held exclusively previously, then the memory controller directory 430 is updated to reflect ownership removal. The secondary memory controller waits for a synchronization command from the primary memory controller. The primary memory controller then synchronizes with the secondary memory controller by sending status of the requestor to the secondary memory controller when outstanding exclusivity is removed. Both memory controllers update their directories to reflect new ownership status. Storage is accessed by both memory controllers, data is delivered to the memory controller caches (if not already there). Data and response from primary memory controller is sent to the requestor, response only, no data, is sent from the secondary memory controller. The requestor receives both responses. The fetch access of the secondary memory controller overlaps any primary SC access and possibly the requestor update of data. 
     The requestor, after data update, stores the data simultaneously to both the primary 440 and secondary memory controllers 445, waits for response from both memory controllers 450 and 455 respectively. At this point the requester can respond to the primary that memory controller and that exclusivity can be removed for a new update from another requestor. In this manner update order is maintained. Requestor coordinates store responses as a means of maintaining ownership and data integrity. 
     FIG. 3 shows the data stored in the storage of each of the system controllers 600. Requestors, processors for instance, have ports 131, 132, 141, 142 to each system controller respectively and requestors in a dual storage system fetch/store data to both system controllers. The requestors configuration array identifies which system controller is a primary memory controller for this data and which is a secondary. Designation of primary and secondary is based upon a unit of data, such as a megabyte range of data in the configuration array. (Primary and secondary may be on either SC side.) This allows either memory controller to be accessed for a fetch or store request without loading one side all the time. 
     The configuration array of the system controller 120, is shown in greater detail in FIG. 4. Each system controller&#39;s embedded configuration array 700 can hold information about the physical address 710, installed or uninstalled elements 720, and about the system area 740 of the storage elements attached. 
     There are some differences in a processor fetch store request and an I/O processor fetch/store request. Typical I/O data store request for data entering from an I/O device brings data directly to storage in blocks of data without a prefetch to alter partial data within a block, as shown in FIG. 5A. The sequence in a dual storage design would be to store to the primary 800, wait for completion 805 and then store to the secondary 810 and wait for completion 815. In the present invention, as shown in FIG. 5B, the I/O requester sends command and data concurrently to both SC&#39;s 850. The primary removes outstanding exclusivity 860, puts a temporary lock on the data 865, sends synchronization signal to secondary to process store without further need to remove exclusivity 870. In parallel, primary and secondary test local stack 880. Both memory controller&#39;s store data, return responses to requester 890. Primary memory controller waits for synchronization from secondary and removes temporary address lock 895. These lock registers allow concurrency of multiple I/O stores while providing serialization of stores. These locks also maintain data integrity for recovery purposes in case one side fails. During recovery of rewriting the data, only requester with valid requester ID and address ID are permitted to retry. Secondary to primary synchronization mechanism allows for recovery in either primary or secondary. An error response or lack of response as seen by the requestor will cause the requestor to initiate a recovery action. If primary memory controller data cannot be retrieved through normal and retry techniques, the secondary memory controller is made a primary memory controller for that data segment and it becomes the data source. 
     This invention is applicable to an extended storage (ES) which is not directly attached to the system controller. Implementation can have the extended storage as a separate entity, larger in size and slower response rate than central storage. Data is usually transferred in large blocks such as 4K byte pages. Data is transferred from main storage to extended storage for page out commands and from extended storage to main storage for page in commands. 
     On page in requests, shown in FIG. 6, requesters issue separate commands, simultaneously to both the primary 905 and secondary 906 memory controller to which the extended stores are attached. A command identifier identifies which memory controller is the primary. A page holdoff register 910 in the primary memory controller maintains integrity of the page in main storage until data is in the storage of both memory controller&#39;s. Primary memory controller executes cross interrogation on behalf of all lines in the page of data 915. Primary memory controller sends synchronizing signal to secondary memory controller 920, both memory controllers concurrently send data from expanded to main storage. Primary memory controller awaits synchronizing signal from secondary memory controller before resetting the page holdoff register 940. Both memory controller&#39;s give response to the requesting CP 950. 
     Page out command sending data from main storage to expanded storage is very similar to the page in command, and is shown in FIG. 7. However, in this situation, primary SC must remove all outstanding exclusivity from all main storage source lines before sending synchronizing command to secondary memory controller 1000. 
     While the invention has been described in detail herein in accordance with certain preferred embodiments thereof, many modifications and changes therein may be effected by those skilled in the art. Accordingly, it is intended by the appended claims to cover all such modifications and changes as fall within the true spirit and scope of the invention.