JPS629931B2 - - Google Patents

Description

Claim 1: In a data processing system comprising a memory and an address translation program, an improved apparatus for generating logical addresses for use by the translation program to access the memory, comprising: means for storing data indicating an address, the data including index selection data and displacement data; a plurality of index registers each containing index data; and a plurality of index registers each containing index data; means for selecting one of the displacement data, an expanded address register, and means for adding index data in the selected index register to the displacement data and adding the sum to the expanded address register. means including an adder for storing a predetermined number of least significant digits of the sum in the extended address register; a logical address register comprising first and second portions; means for storing within the first portion of the system; and a plurality of tables each containing a plurality of address location entries for a corresponding one of a plurality of programs that can be executed by the system. table store means for storing, responsive to a program identification number provided by said system and a predetermined number of most significant digits of a sum in said extended address register;
selecting means for accessing a corresponding one of the address arrangement entries in a selected one of the tables and storing the accessed entry in the second portion of the logical address register; and means for adding the contents of first and second portions of an address register to said address translation program. 2. the predetermined number of most significant digits concatenated with the predetermined number of least significant digits constitute a sum in the expanded address register;
An apparatus according to claim 1. 3. The displacement data comprises a value that is not large enough by itself to cause a carry within the predetermined number of predetermined numbers in the expanded address register. equipment. 4. Said means for storing data indicative of a logical address is an instruction register additionally containing operation data indicative of the type of operation to be performed on the data at said logical address. Apparatus described in section. 5. The memory includes a plurality of segments, and each data location entry in the table indicates a reference address for a particular segment.
The device according to any one of paragraphs 1, 2, 3, and 4. 6. The table corresponding to the program contains address location entries corresponding to the base address of the segment specified for the program, and the table also includes at least one address corresponding to the base address of the segment shared by other programs. Claim 5, including a placement entry
Apparatus described in section. 7. The apparatus of claim 6, wherein each address configuration entry includes check data indicating their status. 8. The least significant digits of the predetermined number in the expanded address register determine the resulting location accessed within the segment indicated by the selected address location entry. The device described. 9. In a data processing system comprising a memory and an address translation program, an improved method for generating a logical address for use by the translation program to access the memory, the method comprising: indicating the logical address; providing index selection data and displacement data; providing a plurality of tables each including a plurality of address location entries for a corresponding one of a plurality of programs that can be executed by the system; selecting one of a plurality of index values in response to said index selection data and adding said displacement data to the selected index value to form a sum; and a program provided by said system. selecting an address configuration entry from a selected table in response to an identification number and a predetermined number of most significant digits of said sum; and selecting the selected address configuration entry along with the remaining digits of said sum. applying the address translation program to the address translation program. 10. The method of claim 9, wherein the displacement data comprises a value that is not itself large enough to cause a carry within a predetermined digit of the predetermined number. 11. Claim 9, wherein the memory includes a plurality of segments, and each data location entry in the table indicates a reference address for a particular segment.
The method according to paragraph 1 or paragraph 10. 12 The table corresponding to the program includes an address location entry corresponding to the base address of the segment specified for the program, and the table also includes at least one address corresponding to the base address of the segment shared by other programs. Claim 1, including a placement entry
The method described in Section 1. 13. the remaining digits of the sum determine the resulting location to be accessed within the segment indicated by the selected address location entry;
The method according to claim 12. REFERENCE TO RELATED PATENT APPLICATIONS This invention relates to an address generation apparatus and method by inventor B. Gaither et al. Our commonly assigned patent application filed in SN Contains the main matters related to. BACKGROUND OF THE INVENTION This invention relates generally to an improved method and apparatus for generating memory addresses within a data processing system, and more particularly to a comparison within a data processing system using virtual or mapped data storage. The present invention relates to an improved method and apparatus for generating virtually large virtual or logical addresses. The most straightforward way to create large addresses is to provide a data processor with a data path wide enough to accommodate all bits of the address. However, the hardware obtained by this method is
It is extremely uneconomical. Another known method is to provide relatively narrow data paths within the data processor and then form multiple passes of these narrow data paths to process addresses that are wider than the data paths.
The difficulty with this multi-pass method is that these multiple passes result in a significant reduction in operating speed. One method for overcoming the drawbacks of the multi-pass method described above is described in US Pat. No. 4,251,860 issued February 17, 1981 to GRMitchell et al.
In this patent, an embodiment is described that allows the use of relatively narrow data widths without requiring multiple passes to manipulate large virtual addresses. This is accomplished by separating the reference address register, which contains the data used to form the virtual address, into segment and offset registers. The operation then requires that only the offset portion of the selected reference address be involved in the computational operation to form the virtual address, such that the generated virtual address is narrower even if it is wider. A data path is provided to enable it to be used. Other background information on possible addressing techniques is provided in U.S. Patent No. 4,240,139, issued December 16, 1980.
Issue, August 1980, Ian LeMair's article "Indexed Mapping", Computer Design, p. 111-118.
Extends Microprocessor Addressing Range”,
IBM Technical Disclosure Bulletin , Vol.23,
No. 5 PL Martinez’s article “Storage Relocation
Translator”, IBM Technical Disciosure
Bulletin, Vol. 23, No. 6, November 1980, p. 2199 and 2200, PL Martinez's article “Relocation
Translator Address Bit Scheme" and references cited in the above patents and articles. SUMMARY OF THE INVENTION In a preferred embodiment of the present invention, the method described in the above-mentioned patent no. Generally similar methods are used. However, the present invention further provides even more flexible and responsive address generation capabilities in a relatively simple and economical manner. Briefly, in the preferred embodiment of the invention, these added capabilities allow a program to generate addresses that can access very large data structures outside the program's normally available addressing range. This is achieved by using indexing in a unique dual purpose manner to provide dimension override addressing options. Particular characteristics of the invention, as well as other features, advantages, objects and uses of the invention, will become apparent from the following detailed description, taken in conjunction with the accompanying drawings. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a schematic block diagram illustrating a preferred embodiment of the invention. FIG. 2 shows an example of the operation of FIG. 1 without indexing or dimension override. Figure 3 shows
3 is a graphical representation showing the results of the example of FIG. 2; Fourth
The figure shows an example of the operation of FIG. 1 with no dimension override and indexing. FIG. 5 is a graphical representation of the results of FIG. Figure 6 shows the first example with both indexing and dimension override.
An example of the operation of the figure is shown. Figure 7 shows the 6th
Figure 2 is a graphical representation of the results of the example shown. DETAILED DESCRIPTION OF THE INVENTION Like numbers and letters indicate like elements throughout the drawings. In prior art virtual or logical addressing systems, such as those described in the aforementioned patent no. 4,251,860, memory storage is typically considered to be divided into distinguishable regions commonly referred to as blocks or segments. . These segments are typically referenced by a two-part logical address, with the first part identifying the particular segment and the second part identifying the offset within the segment. In the embodiment described in the aforementioned patent no. 4,251,860, the generation of a virtual address from an instruction is divided into separate segment and offset registers, the segment and offset values of which together constitute the selected reference address. It includes the use of a reference register field provided by the instruction to select a reference address with a segment and offset value. The displacement field provided by the instruction also specifies the selected offset value to provide a resulting offset value that is combined with the segment portion of the reference address contained in the selected segment register to form the desired virtual address. is added to the value contained in the set register. Because only the offset portion of the selected reference address needs to be added with the displacement field to form the virtual address, a narrower data path is required than would otherwise be possible. Although the virtual address generation method described in the aforementioned patent No. 4,251,860 allows large virtual addresses to be generated using a relatively narrow data path, this virtual address, which can be generated by an instruction, It will be clear that we are limited to adding the instruction's displacement field to the particular reference address selected by the instruction's reference register field. If an overflow is detected, indicating that the resulting address invades the next segment, the operation is aborted. Each instruction has a patent number
It is thus understood that the address range that can be accessed using the method described in No. 4,251,860 is limited to one segment. The preferred embodiment of the invention shown in FIG.
Although it has the effect of the narrow data path of No. 4251860, as will become clear from the discussion below, the same instruction can generate addresses that can access data in several different segments. We are trying to make it possible for everyone. Thus, with reference to FIG. 1, it will be appreciated that the instruction to be processed is fetched and placed into instruction register 10, as typically occurs during a data processing operation. A typical instruction, as shown, is an OP code specifying the operation to be performed, and an index selector IS, which together cooperate in generating a virtual or logical address, as will be described later.
and an address portion with a displacement D. Typically, this OP code OP performs the operation specified by the OP code on the data in memory corresponding to the generated address.
The data is sent to the data processor's execution unit (not shown). The specific manner in which such implementation may be accomplished is not part of this invention. Referring to Figure 1, select the index selector.
IS is used for an index decoder 14 whose output selects a particular one of a plurality of index registers 16, but the displacement D of an instruction within an instruction register 10 is used by an arithmetic and logic unit (ALU) 12.
You can see that it is used for the input on the right side of . The selected index 16a is added to the ALU for addition with the displacement D from the instruction register 10.
Added to the left side of 12. The resulting sum at the output of ALU 12 is stored in an extended address register 15 having an offset portion 15a and a dimension override portion 15b. Due to the address range by which it is desired to allow instructions to access, the extended address register 15 is preferably wide enough to accommodate even the largest sum occurrence at the output of the ALU 12 without overflowing. It will be understood that it is formed. As shown in FIG. 1, offset portion 15a in expanded address register 15 is the offset value of the desired virtual or logical address and is loaded into offset portion 20a of logical address register 20. Dimension override portion 15b is used to derive the segment to be loaded into the segment portion of logical address register 20. More specifically, as understood from FIG. 1, the dimension override portion 15b of the extended address register 15 is a program indicating a particular one of a plurality of programs being executed by the processor. It is used in the dimension override decoder 23 which also receives the number signal. The program number allows the dimension override decoder 23 to select a specific one (for each program to be executed) from a plurality of segment tables, and the dimension override portion 15b allows the dimension override decoder 23 to select a specific one (for each program to be executed) from among the plurality of segment tables. Causes decoder 23 to select a particular segment entry 48 in the selected segment table. These segment tables 25 are
It will be appreciated that it may be provided as part of the main memory or as separate hardware or firmware. Each segment table 25 of FIG. 1 includes a plurality of segment entries 48 specifying particular storage segments that each program will be permitted to access. These segment entries 4
8 need not correspond to adjacent portions in real memory. Since one or more of these segments may be privileged and/or shared by other programs, each segment entry 48 will respond to the event when the selected segment is invalid or unavailable. Contains a segment check bit 48a that is sent to the CPU to permit proper operation to be migrated. Such operations may include, for example, blocking the program until the selected segment is available. If the segment check bit 48a indicates that the selected segment entry 48 in the selected segment table 25 is valid or usable, the dimension override decoder 23 then Entry 48 is logical address register 2
0 segment portion 20b. The concatenated offsets and segments within each offset and segment portions 20a and 20b of the logical address register 20 are thus combined into an address translator for translation or mapping into a physical address that is then used in CPU main memory 40. Configure all logical addresses used by program 30 (which may be of conventional type). The correspondence and adaptability of the address generation means of the invention will now be demonstrated with reference to the examples depicted in FIGS. 2 to 7 in accordance with FIG. The selected segment entry loaded into segment portion 20b of the logical address register corresponds to the base address of the segment and offset portion 20b.
The offset loaded in 0a is the offset within this segment, and the address translation program 30 reads these portions 20a and 2 to obtain the actual address in CPU main memory 40.
It can be inferred from these examples that it is bound to 0b. However, this invention also includes portion 20a.
It should be understood that different types of address translation techniques for deriving the actual address responsive to the contents of and 20b are also applicable. FIGS. 2 and 3 show that the index is set as indicated by the selected index register 16 (selected by the index selector IS in the instruction register 10 of FIG. 1) which is all zeros. An example is shown in which neither Dimension Override nor Dimension Override is called by the instruction. Typically each index register 16 may contain eight binary coded decimal digits. If selected as shown in FIG. 2 and index register 16 is all zeros, the resulting sum loaded into expanded address register 15 is simply the displacement in instruction register 10 of FIG. It's just D. Normally, the maximum value of the displacement D is not large enough to be carried into the dimension override section 15b of the extended address register 15, so the dimension override section 15b is filled with all zeros as shown in FIG. The value will remain the same. Typically, the offset portion 15a of the extended address register may contain six binary coded decimal digits, and the dimension override portion 15b may comprise two binary coded decimal digits. The value of all 0s in the dimension override portion 15b in the selected address register 15 is:
The first of the entries 48 in the segment table 25 corresponding to the current program number is selected (through the dimension override decoder 23). This first entry loaded into segment portion 20b of logical address register 20 is simply the base address of segment B that is considered to be designated for the current program. The resulting address within segment B is shown diagrammatically in FIG. Considering now the example shown in FIGS. 4 and 5, this example shows a situation where indexing is invoked except for dimension override. As shown in FIG. 4, the selected index register 16 may be, for example, 00012163, and the displacement D may be, for example, 900054. The sum provided by ALU 12 is therefore 912217. This sum 912217 is not carried into the dimension override part 15b, so the extended address register 1
The dimension override portion 15b within 5 therefore remains entirely 0. The first entry of the segment table 25 is therefore again selected so that the segment B reference register address is again loaded into the segment portion 20b of the logical address register 20 so as to point to the segment B reference address; Sum in offset portion 15a of extended address register 15
912217 is loaded into the offset portion 20a of the logical address register 20. A typical resulting address is shown in FIG. The final example to be considered is shown in FIGS. 6 and 7, and shows a situation where indexing and dimension override are both called. This means that the index in the selected index will now have a large value of 1142131
It is shown in FIG. 5 that the displacement D is again assumed to be 900054. Next time
Since the sum formed by the output of ALU 12 is 02042185, there is a carry of 02 into dimension override portion 15b of extended address register 15. Therefore, dimension override portion 15b is now, for example, segment Q.
Segment table 2 corresponding to the reference address of
5 into segment portion 20b of logical address register 20.
This segment Q may contain portions of a very large table or other large data structure, such as divided by program number and included in any of the program's designated segments. A typical resulting logical address within segment Q is shown in FIG. Of course, if the check bit 48a of the selected entry 48 indicates that it is invalid or unusable, then the CPU aborts the operation, which could be accomplished in a conventional manner. The value loaded into the dimension override portion 15b of the extended address register 15 is the displacement D and the selected index register 16.
Since it is a carry from the sum of It will be seen from the examples of FIGS. 6 and 7 that a very extended range of addresses is possible for use. Although this invention has been described in connection with specific illustrated embodiments, it will be understood that many variations in construction, arrangement and application are possible within the scope of this invention. For example, the invention is applicable to use with mapped memory and virtual memory, and to various types of memory schemes. It is therefore believed that the invention includes all possible modifications and variations falling within the scope of the appended claims.