Abstract:
The performance of a multi-microprocessor implemented data processing system that emulates a mainframe system is enhanced and optimized in view of space and power constraints for purposes of address translation by providing RAM-based storage means of predetermined depth and width to function as a page address table. The storage means depth is set to at least provide bit space to represent the total number of fixed size pages possible in a given virtual memory space. The width of the storage means is set to at least provide bit space to represent the largest page number that might be encountered in the available real memory and to accommodate a predetermined number of bits that flag information pertinent to translation and system performance. Circuit means, including microcode, is provided for initializing and updating the contents of the storage means as required. Further, when the translation capability is off, a real out-of-bounds flag bit in the storage means can be used to dynamically insure that a real out-of-bounds condition is not produced. The storage means is coupled to the microprocessor address bus from when it receives the page portion of a virtual address for which a real address is desired.

Description:
This is a continuation of application Ser. No. 542,933, filed Oct. 18, 1983, now abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention is concerned with apparatus for and a method of effecting address translation in a multi-microprocessor implemented data processing system that emulates a mainframe system. More particularly, this invention is directed to optimizing dynamic address translation in such a system through the replacement of the translation look-aside buffer with a random access memory array. 
     2. Description of the Prior Art 
     The emulation of &#34;mainframe&#34; data processing systems through the use of microprocessors has become a reality. A typical mainframe data processing system would be any one of the System/370 (S/370) models available from International Business Machines Corporation. The Personal Computer XT/370, a &#34;desktop&#34; System/370, also available from International Business Machines Corporation, is one example of such a microprocessor implemented mainframe. This particular desktop system is a hardware/software package that allows one to run System/370 application programs in a single user environment, to run as a terminal attached to a mainframe host or to run in a stand-alone mode as a personal computer, as required by the particular application. There are, of course, similar systems available from other manufacturers, all of which systems incorporate many of the same functions as the Personal Computer XT/370 although the manner and means of implementation does differ, in varying degrees, from system to system. 
     Due to revolutionary advances in chip densities and packaging, which have been accompanied by significant reductions in costs, many main frame features can now be implemented directly in a desktop system, while other features require some hardware and/or software assistance in order to make them available. The introduction and use of more powerful microprocessors such as, for example, the 8086 and 8088 from Intel Corporation and the 68000 from Motorola Corporation, add further to the list of functions it would be possible to implement in a desktop mainframe. This new breed of microprocessors is fully capable of running a large, enriched instruction set, such as that of System/370, although several of these microprocessors, working in concert with the aid of additional hardware and/or software support, would be required to effect instruction execution in an acceptable time period. It will also be appreciated that presently available microprocessors, while remarkable for the functions they do offer, are not capable of providing all mainframe capability without system compromise. 
     Thus, as in all data processing system designs, various trade-offs are made in order to optimize the price and performance of these microprocessor implemented desktop mainframes. One particular trade-off problem is posed by the need or desire to utilize certain mainframe functions and features that would be particularly difficult to provide in a microprocessor implemented desktop mainframe. Another type of trade-off problem is posed by the requirement that all architectural constraints of the emulated mainframe be adhered to so that user programs can be run without conflict. One specific implementation problem of concern, due in part to such trade-offs being made, is that of effecting address translation, from a virtual to a real address, without adversely impacting space and power constraints in a microprocessor implemented mainframe data processing system. In the System/370 world, for example, dynamic address translation (DAT) is implemented with performance as a paramount consideration, with space and power constraints being given secondary weight. In a microprocessor implemented system such design priorities are often reversed and sometimes dramatically so. 
     Dynamic address translation, by way of background explanation, is a capability which enables the user of a data processing system to have access to a greater working memory size than that which is actually available in terms of physically realized memory. The extra memory size is obtained through the use of a fast mass storage device, such as a hard disk. The memory space perceived to be available by the user is referred to as the virtual memory space. If the data processing system is a multi-user facility or if the size of the application program warrants the use of DAT, part of the user&#39;s program will reside in real memory and the rest will reside on the hard disk. 
     For address translation purposes, the real and virtual memory spaces are partitioned into blocks of equal size called pages. All addresses are divided into two parts; a high order portion that identifies the page number and a low order portion that identifies the address of an element within the page. Given a virtual address, translation to the real address is accomplished by means of a &#34;page table&#34;. The page number portion of a virtual address is used to locate the memory residence of a desired page by reference to the page table. If the page table reveals that the desired page is presently in real memory, the virtual page number gets translated to the real page number. The element address within the page remains unchanged. If the desired page is not in real memory, a &#34;page fault&#34; is indicated that causes the desired page to be fetched from the hard disk and loaded into real memory. The page table is then updated to reflect the changes made to real memory. 
     When a new page is to be loaded into real memory, the position it will occupy is decided by an algorithm that determines which old page can first be removed to make room in real memory for the desired page, with the least impact on system performance. This page selection algorithm is based, in part, on a flag called the reference bit, one of which is associated with each page table entry. The previous contents on the page location being loaded are either written to the hard disk, if the page had been changed since it was first loaded, or simply overwritten, if no page changes have been made. This fact is also determined by software and is indicated by a flag called a change bit, one of which is associated with each page table entry. The reference and change bits are kept in real memory, in a System/370 environment, separate from the page table and pages with which they are associated. 
     In System/370 architecture, the page table is located in real memory. As a result, due to the relatively slow access times of the real memory chips or modules, translations directly accessing it are extremely slow from a performance standpoint. Therefore, a small subset of the page table is kept in a fast piece of hardware called a translation look-aside buffer (TLB). Address translations are referenced to both the TLB and the page table. If the desired page resides in the TLB, then translation is performed via the TLB and access to the page table is terminated. Otherwise, translation is performed through the page table and the contents of the TLB must be updated. When updating the TLB, reference bits provide a means for determining which address is the least recently used. This address is replaced with the new address obtained via the page table translation. To clear the TLB, a &#34;purge&#34; instruction is given. Performance suffers anytime a translation is performed via the page table because of a &#34;miss&#34; in the TLB. 
     The above techniques were designed for use in mainframe systems where, as noted above, space and power considerations are secondary to performance. In small, microprocessor-based systems, performance is still important, but space and power considerations becomes significant limiting factors. The address translation problem for the system designer now becomes one of balancing the trade-offs among performance, space and power restrictions while still providing efficient DAT in a single user, microprocessor-based environment. 
     As was previously mentioned, performing DAT using a page table in a real memory, without a TLB, would result in excessive and relatively slow memory accesses and, thus, degrade system performance. While performance enhancement is made possible in such a situation via implementation of a TLB, this alternative and its associated circuitry utilizes a large amount of high speed logic which requires, in turn, a relatively large quantity as noted, of board space and power. In addition, there is a considerable amount of microcode needed to manage and control operation of the TLB which, if provided, further taxes the limited resources of a microprocessor implemented mainframe. Thus, while it would be possible to enhance address translation to benefit that aspect of system performance, the space, power and coding penalties associated with a TLB-aided solution to translation performance improvement are too great to accept. 
     OBJECTS AND SUMMARY OF THE INVENTION 
     Accordingly, it is a principal object of the present invention to provide means for and a method of address translation that will permit a multi-microprocessor implemented mainframe data processing system to satisfactorily utilize virtual memory space without need of a translation look-aside buffer. 
     It is also a principal object of the present invention to provide such means and methodology in such a system wherein address translation is implemented in a manner that does not unduly sacrifice translation speed while conserving space and power. 
     It is a further object of the present invention to provide means and a method for enabling address translation in a microprocessor implemented mainframe data processing system that includes parity, page content change and page usage indicia. 
     It is another object of the present invention to provide means and a method for enabling address translation in a microprocessor implemented mainframe data processing system that includes out-of-bounds detection. 
     It is another object of the present invention to provide means and a method for enabling address translation in a microprocessor implemented mainframe data processing system that includes out-of-bounds detection which permits real memory space to be configured, as desired, in a programmable segmented or continuous manner. 
     These and other objects of the present invention are achieved in a multi-microprocessor implemented mainframe emulated data processing system by selectable apparatus for effecting address translation which employs storage means of appropriate and predetermined dimensions for the translation task. The storage means is coupled to the microprocessor address bus from whence it receives the page portion of a virtual address for which a real address is desired. The storage means depth is set to at least provide bit space to represent the total number of fixed size pages possible in a given virtual memory space. The width of the storage means is set to at least provide bit space to represent the largest page number that might be encountered in the available real memory and to accommodate a predetermined number of bits that flag information pertinent to translation and system performance. Circuit means, including microcode, is provided for initializing and updating the contents of the storage means as required. Further, when the translation capability is off, a real out-of-bounds flag bit in the storage means can be used to dynamically insure that a real out-of-bounds condition is not produced. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The invention will be described further, by way of a preferred example thereof, with reference to the accompanying drawings wherein like reference numerals have been used in the several views to depict like elements, in which: 
     FIG. 1 schematically illustrates a simplified block diagram of a multi-microprocessor implemented mainframe data processing system which includes control and main memory storage; 
     FIG. 2 schematically depicts, in accordance with the present invention, a block diagram of address translation apparatus for the FIG. 1 processing system; and 
     FIGS. 3A and 3B schematically show, in greater detail, the address translation apparatus for the FIG. 2 processing system. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The present invention is to be explained in the context of a mainframe desktop system that has been implemented with at least two microprocessors. More particularly, this resultant system has been adapted to emulate a System/370 mainframe. For those requiring further information on the instruction set of this mainframe and details of System/370 functions, reference should be made to the IBM System/370 Principles Of Operation (Manual No. GA22-7000), which is available from the IBM Corporation and which is, to the extent necessary, incorporated herein by reference. In addition, those requiring further information on the details of the desktop mainframe referred to herein should refer to Technical Reference Manual For The IBM Personal Computer XT/370 Manual No. 6936732). 
     It will be understood by those having skill in this art that mainframe implementation can be achieved by use of only a single microprocessor. Alternatively, a plurality of microprocessors, equal to or different than the number used herein, could be employed to emulate a mainframe system. Further divergence in system configuration is possible as a result of variations in instruction set partitioning schemes and the manner in which the subsets are then emulated. Examples of this multiple microprocessor implementation approach are more completely described in commonly assigned U.S. patent application Ser. No. 371,634, filed in the names of Agnew et al on Apr. 26, 1982. In Agnew et al, a System/370 instruction set is partitioned in accordance with several criteria and the subsets thereof are each implemented on one or more of a plurality of microprocessors, but not all necessarily in the same manner. 
     An illustrative desktop mainframe data processing system 10 is shown in FIG. 1. As depicted in the simplified system block diagram thereof, a primary processing unit 12, and its associated secondary microprocessors 14 and 16 are connected to a local processor bus 18. Local bus 18 is connected, in turn, by bus-to-bus adapter 20 to the system bus 22. Main storage 24 and the secondary control storage 26 are both connected to the system bus 22. The primary processor 12 and secondary processors 14 and 16 are also responsively connected to processor control logic means 28 which incorporates processor control and interface logic and some private storage therefor. Certain aspects of the control logic means 28 shall be discussed hereinafter in greater detail. 
     In the particular embodiment described herein, primary processor 12 is assigned the responsibility for performing all instruction fetches and operand address calculations for all of the processors used in the system. It also performs execution of all fixed point instructions, contains and maintains the general purpose registers, instruction length codes, condition codes and instruction addresses, recognizes system interrupts and provides indications to the system that a main storage instruction fetch or operand access is required. In addition, primary processor 12 is also able to provide an indication to the system that a change in processor control is needed. 
     Secondary processor 14 performs execution of all system control instructions and maintains all of the control registers. When necessary, it performs the service processor function and provides indications to the system of main storage operand access and private storage microcode access. In addition, secondary microprocessor 14 is adapted to provide the system with an indication that a change in processor control is needed. 
     Secondary microprocessor 16 performs execution of all floating point instructions, containing and maintaining all of the floating point registers. It also provides the system with an indication of main storage operand access and of a need to alter microprocessor control. Alternatively, these floating point functions can be provided by a peripheral unit rather than by a microprocessor. 
     The mainframe instruction set is thus allocated for execution among the several processors. Primary processor 12 is provided with limited on-chip control store that can be utilized to store mainframe instruction responsive microcode and/or microprocessor interface and control microcode. It will be recognized, given the fixed quantity of on-chip control store available, that the instruction responsive microcode and the interface microcode reside in control store at the cost of the other. A greater amount of one type of microcode in on-chip control store residence means that a lesser amount of the other type can be accommodated therein. If a more functional microprocessor interface is desired, with an attendant cost in supporting microcode, there will be less room in control store for instruction responsive microcode. From a performance standpoint, it is best to keep the interface simple and leave as much control store as possible for instruction code. In this embodiment, for example, it has been decided to place microcode for the most frequently used mainframe instructions in the control store of microprocessor 12 and to use a relatively simple intermicroprocessor interface that requires minimal microcode. 
     A main storage module 24 is attached to system bus 22 and used as needed by the processors 12, 14 and 16. It is assumed that the processor local bus 18 and the microprocessors 12, 14 and 16 all include 24 bits of addressing to accommodate the addressing structure of the mainframe to be implemented. It may be necessary to slightly modify currently available microprocessors to achieve this addressing capability. The secondary processor 14 uses off-chip control storage module 26, as may be necessary, for its own microcode and scratchpad functions. While secondary processor 16 has no need to use off-chip control store 26 in this embodiment, it could access that module, as might be necessary, to satisfy its microcode and scratchpad needs. Processors 12, 14 and 16 and processor control logic means 28 are interconnected together by and pass information to each other on the processor local bus 18. The microcode required by secondary microprocessor 14 is shown in source form in Appendix A hereof. It includes the code for interfacing the processors and for controlling certain aspects of dynamic address translation, such as initialization and updating, as shall be hereinafter explained. 
     Because all of the available address bits or lines in a microprocessor implemented mainframe will be needed to define and emulate the mainframe&#39;s virtual storage, it would not be effective to divide all possible storage defined by the available address bits between virtual main storage and control storage. Since all of the available address lines are needed to define virtual storage, prior to determination of the real address involved, there is no direct manner of using those same address lines to also identify unique control storage addresses. An additional line is required and implemented to distinguish main storage from control storage accesses. 
     Although shown as two separate modules, and they are from a logical standpoint, main storage and control storage are a physically contiguous block of random access memory (RAM), with an exception to be discussed below. The dividing line between storage modules, as described herein, is the dividing line between real main storage and control storage. In this illustrative embodiment, the main storage module 24 runs from address 00000 to address 77FFF (hexidecimal--hereinafter hex). The control storage module 26 runs from address 78000 to address 7FFFF (hex). The addresses used herein have been selected to simplify and facilitate this description. Those having skill in this art will recognize that the address limits for each memory module are a design choice and that the manipulation of more than than one address bit, to steer between main and control storage, may be necessary. 
     Private store 30, referred to previously, is logically a portion of off-chip control storage 26, but is physically located in the processor control logic means 28 and mapped into a reserved segment of control store 26. The reserved segment of control store 26 is typically about 256 bytes long, although it can be greater. The processor control logic means 28 is connected to bus-to-bus interface 20 via bus feeder 18a. Also physically located in the processor control logic means 28 are a pair of override latches, see commonly assigned U.S. patent application Ser. No. 527,053 filed in the name of Buonomo et al for additional details, that serve to steer memory accesses from processors 12 and 14 to either the main memory storage module 24 or to the off-chip control storage module 26. 
     The invention described herein enables an optimal and efficient realization of dynamic address translation in a single user, microprocessor-based System/370. By taking advantage of advances in random access memory (RAM) technology, the traditional high speed, hardware implemented TLB-slow real memory page table combination can be replaced by a page table implemented in fast static RAMs. Given a fixed page size, the overall RAM depth is set equal to or greater than the total number of pages of that size which will fit in the virtual memory space. The RAM width is set, in part, to accommodate the number of bits needed to represent the highest page number possible in the available real memory space. In addition, the RAM width is chosen to include, for each page entry therein, a page fault bit that is used to signify whether the desired virtual page is in real memory, reference and change bits to assist in the transfer of pages from disk to memory and vice versa, a real out-of-bounds bit that signifies if an address is outside the defined real memory space, and a parity bit for checking proper operation of all functions associated with the RAM. 
     A generalized view of a mainframe desktop system which incorporates dynamic address translation in accordance with the subject invention is shown in FIG. 2. The RAM organization of the above-mentioned functions will henceforth be referred to as the page address table or PAT 40. Input bus information for use by the PAT 40 or for system use when PAT 40 is not operational is derived from the microprocessor bus 18. In total, three address sub-buses are derived utilizing specific bits of the microprocessor address bus 18, as follows. The twelve low order address bits A11-A00, which define the element address within a page, are extracted from microprocessor address bus 18 and placed on element bus 42. The next seven bits A18-A12, which are sufficient to define all real memory page numbers, are similarly extracted from microprocessor address bus 18 and placed on real address bus 44. The ten high order bits A21-A12, which define all possible virtual memory page addresses, are also removed from microprocessor address bus 18 and placed on PAT input bus 46. The Pat 40 output bus 48 is actually a composite bus that includes three sub-busses 48a, 48b  and 48c. PAT output sub-bus 48a carries the real or translated address, bits A18-A12, to data multiplexer 50. PAT output sub-bus 48b bi-directionally transfers information between microcode interface 52 and PAT 40 as shall hereinafter be explained. PAT output bus 48c performs a similar function in transferring information between DAT control circuit 54 and PAT 40. The nature and use of the information transferred by these PAT output buses shall also be explained hereinafter. 
     There are three modes of operation for PAT 40. Mode A is &#34;DAT on&#34;, in which address translation and any functions associated therewith are automatically controlled by hardware and the microcode provided for that purpose. In this first or &#34;DAT on&#34; mode, the input PAT address bus 46, which consists of the 10 high order address bits A21-A12 from microprocessor address bus 18, define the virtual page number being sought. All data bus functions are automatically controlled by hardware in the &#34;DAT on&#34; mode. The second mode, &#34;DAT off&#34;, basically bypasses the PAT with the exception of use of the real out-of-bounds bit. Translation is not needed in this operating mode. The third mode, &#34;PAT modification&#34; allows access to the PAT by the processor microcode for initializing and updating purposes. In this mode, the address space of PAT 40 becomes a subspace of memory accessible only to the microcode. This prevents any direct interaction between software and PAT 40. Initialization and updating of PAT 40 by the microcode is aided by a microcode interface circuit 52, see FIG. 3, composed of the tri-state buffer 70, transceivers 72, 74 and 76, as well as the necessary address, data and control signal information therefor. 
     Mode selection is accomplished by processor microcode manipulation of a mode selection control register 59. When the contents of mode selection register 59 are set to a predetermined value, it causes the data multiplexer control line 56 to be set. This results in the address information on bus 48a being passed through data multiplexer 50 to its output bus 58. If the &#34;PAT off&#34; or &#34;PAT manipulation&#34; modes are required, the mode register is loaded with an appropriate value that resets data multiplexer control line 56. This switches the data on bus 44 to the multiplexer output bus 58 since address translation is not required for these modes of operation. 
     The translation and page fault mechanism are required for DAT use. When a translation is attempted, the virtual page number is input to PAT 40. If no page fault is detected by the microcode, the translation bus 48a, excluding the page fault bit, represents the real page number. This address portion is concatenated with the element address on bus 42 to form the entire real address placed on the real address bus 60. If a page fault is detected, the translation content of the PAT has no meaning. The microcode then responsively initiates a page fault exception which begins the paging process and ultimately updates PAT 40. 
     Reference and change bits are supplied to assist the secondary processor 14 microcode in determining where a new page will be placed in real memory and whether or not the old page it replaces need be written to the hard disk. Every time a virtual page is accessed, its corresponding reference bit is correspondingly set. It can only be reset or de-asserted by the microcode. The change bit is asserted or set whenever a write operation is performed during a virtual page access. It also can only be reset by the microcode. 
     Real out-of-bounds detection is normally implemented in random logic as an address threshold. Any address above the threshold causes the processor in control to be notified of the addressing error. This function is implemented, in accordance with the present invention, by using PAT 40 when in the &#34;DAT off&#34; mode. The real address is obtained directly from processor address bus 18 by multiplexing certain of the address bits around PAT 40, as previously explained. The input PAT 46 bus of the microprocessor address bus remains connected as the PAT input address bus. Since this bus contains part of the real address being accessed, a threshold may be defined in PAT 40 by asserting all locations of the real out-of-bounds bit above the threshold address. That information is placed into PAT 40 by the microcode and the microcode interface logic, see FIG. 3, for subsequent real address verification. This task is primarily handled by the tri-state buffer. In addition, programmable, multiple thresholds may be implemented, allowing the real memory space to be segmented in any desired configuration. When DAT is on, the real out-of-bounds bit has no meaning. In this case, microcode operation during PAT modification must prevent the user from establishing an address translation which would produce a real out-of-bounds condition. Use of the real out-of-bounds bit when translation is off is under microcode control. 
     Parity is automatically checked and generated across the entire width of the PAT for every access when DAT is on or any microcode access. If a parity error is detected, the microcode sends a machine check to notify the user of the error. As shown in FIG. 3, parity is checked for DAT RAMs 40a, 40b and 40c by the combination of buffer 62 and Exclusive OR gates 64, 66 and 68. 
     As an example of PAT 40 use, it will be assumed that a 4 megabyte (MB) virtual memory space having fixed 4 kilobyte (KB) size pages is to be implemented in accordance with the arrangement shown in FIG. 2. The lower twelve address lines, bus 42, of the microprocessor address bus 18 determine the location of an element within a 4KB page. Ten upper address lines from the microprocessor address bus 18 are needed to identify and access 1,024 virtual pages, which is the maximum number of 4KB pages that fit in the defined virtual memory space. In this example, the real memory space is limited to 512KB. This requires that the width of translation bus 48a of PAT 40 be seven bits. These seven address lines will carry the translated real page number and are concatenated with the lower twelve address lines to form the real address on bus 60. 
     Although the present invention has been described in the context of a preferred embodiment thereof, it will be readily apparent to those skilled in the appertaining art, that modifications and variations can be made therein without departing from its spirit and scope. Accordingly, it is not intended that the present invention be limited to the specifics of the foregoing description of the preferred embodiment. Instead, the present invention should be considered as being limited solely by the appended claims, which alone are intended to define its scope. ##SPC1##