JPS6337416B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a data processing system, and particularly to a computer using a virtual storage system that manages a storage device by dividing it into a plurality of blocks. More specifically, the present invention relates to a device for transferring control from the last instruction of a block to a subsequent block without using a special instruction when a sequence of machine language instructions is divided into a plurality of blocks.

There are commercially available computers that manage storage devices by dividing them into blocks called pages or segments. The segment method will be described below as an example of division into blocks.

Virtual memory type computers have the advantage that program creators can create programs without being limited by the computer's capacity. On the other hand, this method uses segment associative memory and segment-based memory to prevent deterioration in execution speed, and uses program locality to maintain the locations of segments referenced in the near past on the real storage device. This is common.

The process leading to reference to the real storage device in this virtual storage system will be briefly explained.

Referencing the real storage device from a program is
This is always done by segment name and relative address within the segment. The location of the segment corresponding to the segment name on the real storage device is determined when the program is executed, not when the program is created. For this reason, segment base storage is provided to indicate the address in the real storage device of the segment referenced by the program. The program checks the match between the segment name stored in segment associative memory and the segment name to be referenced, and finds the address of the segment located on the real storage device by segment base storage corresponding to the matching segment name. You can know.

The above case is a case where the segment to be referenced by the program exists in the segment associative memory in advance, and the case where the segment to be referenced does not exist in the segment associative memory will be described. First, a signal indicating that the segment does not exist in the associative memory is sent to the virtual memory controller. In response to this signal, the virtual storage control unit searches for a location where the target segment is stored and places it on the real storage device. At this time, the address where the segment is stored is determined and this address is stored in the segment base storage. At the same time, the segment name in which the segment base is stored is stored in the segment associative memory. Thereafter, when the currently stored segment name is referenced by a program, the address in the segment base storage enables high-speed reference to the real storage device.

Conventionally, in virtual memory computers like the one mentioned above,
An unconditional branch instruction is added to the last instruction in order to transfer control from the last non-branch instruction to the first instruction of the next segment when divided into segments. By executing this branch instruction, control is transferred to the first instruction of the next succeeding segment.

Such an unconditional branch instruction is an instruction that cannot be predicted at the time of program creation, and is unnecessary in a system that stores all instruction sequences in a storage device in the order of physical addresses instead of a virtual storage system. However, in the virtual memory system, adding this originally unnecessary branch instruction to a machine language instruction sequence deteriorates the utilization efficiency of the storage device that stores the machine language instruction sequence and causes deterioration of the performance of the computer. In particular, when a loop is formed in which a sequence of instructions is executed repeatedly across the boundaries of divided segments, the performance deteriorates significantly. To avoid this, a method may be considered that does not divide a segment in the middle of a looping instruction sequence when compiling a source program written by a programmer into machine language instructions. However, in order to implement this method, advanced compilation functions are required, and it is difficult to provide sufficient functions.

Furthermore, inserting an instruction that a programmer cannot predict into a machine language instruction sequence makes it difficult to interpret the machine language instruction sequence.

The present invention solves the above-mentioned problems in the virtual memory system, and aims to prevent unexpected instructions from being inserted into a machine language instruction string divided into a plurality of segments into a machine language instruction string.

Furthermore, the purpose is to make effective use of the storage device by omitting branch instructions added by dividing into segments and shortening the machine language instruction string.

Furthermore, it is an object of the present invention to prevent processing performance from deteriorating even when an instruction sequence for repeated processing is divided into segments in the middle.

Furthermore, the purpose is to eliminate the need for compilers to have advanced functionality to prevent segments from being split in the middle of repeated instructions.

According to the present invention, in a computer in which the address space of a storage device is divided into a plurality of segments, a segment associative memory that stores some or all segment names and can be associated with segment names; a range memory that stores the size of a segment corresponding to a segment; a range detection device that detects execution of an instruction other than a branch instruction beyond the range of the segment;
a subsequent segment memory for storing a segment for an instruction code following the segment, and an address and a range of the segment of the range memory for executing the last instruction in the segment and then executing the next instruction; An electronic computer comprising a virtual memory control unit that determines a subsequent segment based on the contents of the subsequent segment storage, determines the address of the subsequent segment, and starts processing of the subsequent segment storage when the range detection device detects that the segment is outside the range. is obtained.

Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing an embodiment of a virtual memory type computer using the present invention. The block diagram in Figure 1 has a configuration that eliminates the need to provide an unconditional branch instruction as the last instruction of a segment, and a structure that enables high-speed processing when the instruction string to be repeatedly processed is divided into segments in the middle. At the same time, the configuration for We first describe a configuration that eliminates the need for unconditional branch instructions, and then:
The components added to speed up repetitive processing will be explained.

The present invention also includes the following components that have been used in conventional virtual memory type computers. The storage device 1 stores machine language instruction sequences and data. The instruction address counter 2 stores the address of the instruction being processed or the next instruction to be processed. This instruction address is a logical address.

FIG. 2 is a conceptual diagram illustrating an instruction address counter, and as shown in the figure, it is indicated by a segment name and a relative address within the segment. The segment associative memory 3 stores segment names of some or all of the segments arranged in the storage device 1. This segment associative memory 3 has an associative function that inputs a segment name and compares it with a plurality of segment names in the segment associative memory 3 to check for a match. The segment name of the instruction address counter 2 is associated via the signal line 20. In the segment base memory 7, corresponding to the segment name in the segment associative memory 3, the segment base address at which the segment was placed in the storage device 1 is stored. This segment base address is set by the virtual memory controller 14 via the signal line 22. An adder 13 is provided for adding the value of the segment base memory 7 and the relative address of the instruction address counter 2 to obtain the address of the memory device 1.

These storage device 1, instruction address counter 2, segment content addressable memory 3, segment base memory 7, and adder 13 have the same functions as in a conventional virtual memory type computer. The storage device 1 is composed of a commercially available random access memory (RAM), and the instruction address counter 2 is realized by a commercially available register and arithmetic unit or a register with a counting function. The segment associative memory 3 is composed of a commercially available associative memory that can check for matches between multiple words.
Segment-based memory 7 is composed of commercially available high-speed RAM. Further, the adder 13 is constructed from a commercially available Arithmetics Logic Unit (ALU).

In the present invention, it is not necessary to provide an unconditional branch instruction as the last instruction of a segment; instead, the size of the segment and information about subsequent segments are given at the time of compiling the program. A subsequent segment storage 5 is provided to store this subsequent segment information. When the segment indicated by the segment name in the segment associative memory 3 is an instruction string, the subsequent segment name is stored in the subsequent segment memory 5. A range store 4 is provided to store information regarding the size of the segments. In order to detect that the content of the relative address of the instruction address counter 2 exceeds the size of the segment, a range detecting device 9 is provided which receives the relative address and the value of the range memory 4 as input.

The virtual memory control unit 14 performs segment allocation in the storage device 1, segment associative memory 3, and segment base, which is necessary even in the conventional example when the segment referenced in the instruction sequence does not exist in the segment associative memory 3. In addition to the registration in the memory 7, the following processing is performed.

When it is detected by the mismatch signal on the signal line 24 that the segment to be processed does not exist in the segment associative memory 3, the segment information is registered in the segment associative memory 3 via the signal line 21, as shown in the conventional method. . At the same time, registration in the range memory 4 and subsequent segment memory 5 is performed. When the range detection device 9 detects that the instruction address counter 2 is pointing outside the segment range, the output of the subsequent segment memory 5 is set to the segment name of the instruction address counter 2 via the signal line 26. . At the same time, set the relative address to 0. By this operation, if the instruction address counter 2 indicates an area outside the segment range by an unconditional instruction, control is transferred to the first instruction of the subsequent segment. These processes in the virtual memory control unit 14 allow control to be transferred from a non-branch instruction to a subsequent segment without providing an unconditional branch instruction at the end of the segment.

The virtual memory control unit 14 is realized by firmware or system software as in a conventional computer. Further, the range storage 4 and the subsequent segment storage 5 are realized by high-speed RAM, and the range detection device 9 is realized by a commercially available comparator element.

In the above description regarding FIG. 1, a configuration was shown for eliminating the need to provide an unconditional branch instruction as the last instruction of a segment. Further, referring to FIG. 1, a description will be given of the components added to speed up the repetitive processing.

The subsequent address memory 6 stores the address at which the subsequent segment is placed in the storage device 1. This value therefore corresponds to the value in the segment base store 7 corresponding to the following segment. The above-mentioned configuration and the configuration in which the subsequent address storage 6 is added will be compared in terms of processing methods for moving control to subsequent segments using non-branch instructions. In the above configuration, when the segment range is exceeded, the subsequent segment name is first obtained from the subsequent segment storage 5. Thereafter, a match between the succeeding segment name and the segment associative memory 3 is checked, and the execution address of the succeeding segment is determined from the relative address of the corresponding segment base memory 7 and instruction address counter 2.
On the other hand, in the configuration provided with the subsequent address memory 6, when the range of the segment is exceeded, execution continues using the contents of the subsequent address memory 6 as the address of the next instruction without referring to the subsequent segment name. This allows control to be transferred to subsequent segments at high speed.

Registration in the subsequent address memory 6 is performed when the last segment instruction is first executed and control is transferred to the next segment. At this time, if the subsequent segment exists in the segment associative memory 3,
Sometimes it doesn't exist.

If the segment does not exist in the segment content addressable memory 3, the subsequent segment is placed in the storage device 1 by the virtual storage control unit 14, as in the conventional method, and the segment base address is determined. It is registered in the segment base memory 7 via this address signal line 22 and simultaneously registered in the subsequent address memory 6.

If the segment exists in the segment associative memory 3, the value of the corresponding segment base memory 7 is sent to the signal line 25.
The address is registered in the subsequent address storage 6 via the .

In either case of registration in the subsequent address memory 6, it is necessary to register the subsequent segment at a position corresponding to the preceding segment before being looked up in the segment associative memory 3. A preceding segment address register 12 is provided to hold the position of this preceding segment in the segment associative memory 3 and to register a subsequent segment base address in the position of the succeeding address memory 6 corresponding to the preceding segment.

Furthermore, control is transferred to the first subsequent segment by an unconditional branch instruction at the end of the segment, and 2.
A subsequent address flag 8 is provided to distinguish the control movement from the second time onward and to indicate that the subsequent address storage 6 can be used from the second time onward. These flags are provided corresponding to each segment name in the segment associative memory 3, and when it is "0", it indicates that the corresponding content in the subsequent address memory 6 is not available, and when it is "1", it indicates that it is available. .

The subsequent address storage 6 is realized by a commercially available high-speed RAM, and the preceding segment address register is realized by a commercially available register element. Further, the subsequent address flag 8 is realized by a commercially available flip-flop.

When using the subsequent address flag 8, clearing the flag becomes a problem. When the flag of the subsequent address flag 8 is “1”, the virtual memory control unit 1
When the location of the subsequent segment in the storage device 1 is changed by 4, the segment base address changes and the corresponding value in the subsequent address storage 6 becomes invalid, so the flag needs to be set to "0".

In this embodiment, when the virtual memory control unit 14 changes the arrangement of any segment registered in the segment content addressable memory 3 in the storage device 1, all subsequent address flags 8 are cleared.

Next, an example of a process in which control is transferred from a non-conditional branch instruction at the end of a segment to the first instruction of a subsequent segment will be described. In this example, a case will be described including a case where a sequence of instructions to be repeatedly processed is processed at high speed.

FIG. 3 is a conceptual diagram showing the result of arranging segments in the storage device 1. Segment X is A
The segment size is 4000.
It's a part-time job. Addresses are counted in bytes. Segment Y is stored starting from address B, and its segment size is 3000 bytes. Segment X,
Instruction sequences are stored in Y and Z, with segment X followed by segment Y, and segment Y followed by segment Z. That is, unless the last instruction of segment X is a branch instruction, the next instruction is the first instruction of segment Y.

4 and 5 show the following address flag 8, segment associative memory 3, range memory 4, succeeding segment memory 5, succeeding address memory 6 and segment base memory 7 when executing an instruction in segment X. It is a schematic diagram showing a state. In FIG. 4, a segment name X is stored at address 1 of the segment associative memory 3. At address 1 of range memory 4, 4000, which is the segment size of segment X, is stored. Next, a segment Y following segment X is placed at address 1 in the subsequent segment memory 5. Furthermore, address A, which is the starting address of segment X, is stored at address 1 of the segment base memory 7. It is assumed that the contents of address 1 of the subsequent address memory 6 are indefinite and not valid. Therefore, address 1 of the subsequent address flag 8 is set to 0. The case where the execution target is the last instruction of segment X, and this last instruction is not a branch instruction, will be described below. When the execution of this last instruction is completed, the instruction address counter 2 is incremented. This step result is stored in the range storage 4 by the range detection device 9.
When compared with the output of , it is detected that the instruction address counter 2 is outside the range of segment X. In other words, the relative address of the instruction address counter 2 becomes 4000 by adding 1 to the relative address 3999 of the last byte of segment X as a result of incrementing. On the other hand, the segment name of the instruction address counter 2 stores the name of the segment currently being executed, so it is segment X. When this segment X is associated with the contents of the segment associative memory 3 via the signal line 20, they match by X at address 1. This one
By referring to the contents of range storage 4 using address X, segment size 4000 of segment X is obtained.
The range detection device 9 detects that the relative address of the output instruction address counter 2 of the range storage 4 is outside the segment range. Therefore, when the instruction address next to the last instruction of the segment is stored in the instruction address counter 2 by incrementing, the range detection device 9 detects that it is outside the range because it becomes 40004000.
This signal is output to the virtual memory control unit 14 via a signal line. At this time, the preceding segment address register 12 stores the value "1" of the address in the current segment content addressable memory 3 where a match is recognized. The virtual memory control unit 14 sets the succeeding address flag 8 to 1.
Look up the address. Since the content of address 1 is currently "0", the subsequent address memory 6 does not store a valid subsequent segment address. In this case, the contents of the subsequent segment memory 5 indicate the name of the segment to which control is transferred next.

Next, the segment Y stored at address 1 in the subsequent segment memory 5 is stored as a segment name in the instruction address counter 2 via the signal line 26. At the same time, "0" is stored in the relative address field of the instruction address counter 2. By this operation, the instruction address counter 2 stores the start address of segment Y in which the next instruction to be executed is stored. Thereafter, it is checked via the signal line 20 whether the subsequent segment Y exists in the segment associative memory 3 or not.

If segment Y has never been referenced in the near past, segment Y is not stored in the segment associative memory 3. The results are reported to the virtual storage control unit 14 via the signal line 24. The temporary phase control unit 14 refers to the segment information regarding the segment Y stored in the storage device 1 and controls the signal line 2.
1 to the segment associative memory 3, range memory 4 and subsequent segment memory 5. This result is
As shown in FIG. 5, the segment name of segment Y is stored in the segment associative memory 3 at address 2,
Segment size 3000 of segment Y is stored at address 2 of range memory 4, and subsequent segment memory 5
The segment name of segment Z following segment Y is stored at address 2. Furthermore, segment Y
is placed in storage device 1, the start address of segment Y is determined. In this example, segment Y is stored starting from address "B". The value of the start address "B" is stored in the segment base memory 7 via the signal line 22 as a segment base address. At the same time, the segment base address of segment Y is stored via the signal line 22 at address 1 of the subsequent address storage 6, which is indicated by the content "1" in the preceding segment address register 12. moreover,
The content of address 1 of the subsequent address flag 8, which is indicated by the content "1" of the preceding segment address register 12, is set to "1". This indicates that the address at address 1 in the subsequent address memory 6 is valid. In other words, as shown in Figure 5, segment
The starting address B of segment Y following segment

Execution of segment Y is started from the instruction indicated by instruction address counter 2. When control is transferred from segment X to segment Y in the above state, the segment name of the instruction address counter 2 is Y and the relative address is "0". When we look up this segment name using segment associative memory 3, we find that
As shown in the figure, a match is found at address 2. The corresponding segment base memory 7 shows "B". This "B" and instruction address counter 2
As a result of adding the relative address "0" of "0" in the adder 13, the "B" address is obtained, and execution is performed from the first instruction of the segment Y at the "B" address.

When segment Y following segment X is read out from subsequent segment memory 5 and checked to see if it matches the contents of segment associative memory 3 via signal line 26, a match may be found. That is, this is a case where segment Y has been referenced more than once in the near past. At this time, the segment base address of the segment base memory 7 corresponding to the position of the segment associative memory 3 where a match has been found is the signal line 2.
5 and is stored at address 1 of the subsequent address memory 6, and at the same time, address 1 of the subsequent address flag 8 is set to "1". The states of each memory and flag at this time are the same as those shown in FIG. Also, the signal line 26
Segment Y is stored as the segment name of the instruction address counter 2 via , and "0" is stored in the relative address.

Execution control is transferred to segment Y through the above process. A case will be described in which, after moving to segment Y, control is returned to segment X by a branch instruction and execution of the last instruction of segment X is terminated. As a result of finishing the execution of the last instruction and incrementing the instruction address counter 2, the range detection device 9 finds that it is outside the range of the segment. At this time, the subsequent address flag 8 corresponding to segment
The content of address 1 is "1" as shown in FIG. When this flag is “1”, the content of address 1 of the subsequent address memory 6 is “B”
is the address of the next instruction to be executed.

That is, when control is first transferred from the last instruction of segment X to the first instruction of segment Y, it is necessary to perform a match check using the segment associative memory 3 twice. First, a match check is performed using segment X in the instruction address counter 2 to detect a match at address 1. Next, the content "segment Y" at address 1 of the succeeding segment memory 5 is stored in the instruction address counter 2, and a match check is performed using this segment Y.

When control is transferred from the last instruction of segment X to the first instruction of segment Y for the second time or later,
A match check using the segment associative memory 3 only needs to be performed once. That is, when a match check is performed on segment X, the subsequent address memory 6 is valid, so the processing continues using the output of the subsequent address memory 6 as the address of the next instruction to be executed.

FIG. 6 shows the case where control is transferred between segments by a branch instruction, the first inter-segment control transfer in the present invention, and the second and subsequent inter-segment control transfer in a, b, and c, respectively. in flow
It is shown together with the timing of t ₁ , t ₂ , t ₃ , and t ₄ . In the figure, a is a flowchart showing a branch instruction, b is a first inter-segment control transfer, and c is a flowchart showing a second and subsequent inter-segment control transfer. 6th
The figure shows a case where a subsequent segment has been previously registered in the segment associative memory 3. What is the transfer of control between the branch instruction and the first segment? t ₁ to _{t 4}
The processing speed is the same. However, in the present invention, the control transfer after the second time is
This is achieved with a processing time of t ₁ and t ₂ and can be executed at high speed.

The subsequent address memory 6 and the subsequent address flag 8 indicating the validity of the subsequent address memory 6 are added to speed up the second and subsequent processing. Subsequent address memory 6 and subsequent address flag 8
If not added, the same processing as the first time is performed for the second and subsequent times.

As described above, according to the present invention, the branch instruction added to the machine language instruction string is no longer necessary by dividing the storage device into a plurality of blocks. This improves the usage efficiency of the storage device in which the machine language instruction sequence is stored. Furthermore, since the storage device is divided into blocks, the source program and the machine language instruction sequence can be made symmetrical without the program creator having to consider branch instructions generated by the computer system during compilation.

By adding subsequent address storage, when a looping instruction sequence is divided into blocks in the middle, control can be moved between blocks at high speed from the second time onwards. Furthermore, when the compiler divides a program into blocks, it can do so without considering performance degradation due to division in the middle of a loop.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing one embodiment of the present invention;
Figure 2 is a conceptual diagram explaining an instruction address counter, Figure 3 is a conceptual diagram of a storage device in which an instruction sequence is divided into multiple blocks, and Figures 4 and 5 are when control moves between blocks. FIG. 6 is a conceptual diagram explaining the contents of each memory and flag, and FIG. 6 is a timing flowchart showing the flow of processing. 1...Storage device, 2...Instruction address counter, 3...Segment associative memory, 4...Range memory, 5...Subsequent segment storage, 6...Subsequent address storage, 7...Segment base storage, 8...
Subsequent address flag, 14...Virtual memory control unit.

Claims (1)

[Scope of Claims] 1. In a computer in which the address space of a storage device is divided into a plurality of segments, whether or not a part or all of the segment names are stored and a segment name that matches the input segment name is stored. segment associative memory means for detecting the size of the segment corresponding to the segment stored in the segment associative memory means; and range storage means for storing the size of the segment corresponding to the segment stored in the segment associative memory means; range detection means for detecting the execution of an instruction; subsequent segment storage means for storing the name of the instruction code segment following the segment; and execution of the last instruction in the segment and the subsequent instruction. If the range detecting means detects that the storage location of the next instruction is outside the range of the segment, the address of the subsequent instruction is compared with the range of the segment of the range detecting means. 1. A computer using a virtual memory system, comprising virtual memory control means that determines a segment, obtains the address of the subsequent segment, and starts processing of the subsequent segment storage means. 2. In computers where the address space of the storage device is divided into multiple segments, segment associative memory stores part or all of the segment names and detects whether or not a segment name that matches the input segment name is stored. means, range storage means for storing the size of the segment corresponding to the segment stored in the segment associative storage means, and a range storage means for storing the size of the segment corresponding to the segment stored in the segment associative storage means; A range detection means for detecting, a subsequent segment storage means for storing a segment name for an instruction code following the segment, and an address and the range detection when executing the last instruction in the segment and further executing the following instruction. When the range detecting means for comparing the ranges of the segments of the means detects that the storage location of the next succeeding instruction is outside the range of that segment, the succeeding segment is determined based on the contents of the succeeding segment storage means, and the succeeding segment is virtual memory control means for determining the address of and starting processing in the subsequent segment storage means; subsequent address storage means for storing the address of the subsequent segment corresponding to the subsequent segment storage means; and the subsequent address storage is effective. and means for setting a subsequent address in the subsequent address storage means and validating the subsequent address flag when control is first transferred from the last instruction of a segment to a subsequent segment, The virtual storage system is characterized in that when the subsequent address flag indicates that the subsequent address is valid, the transfer of control from the last instruction of the segment to the subsequent segment is controlled by the subsequent address storage means. calculator.