Goodard v. Google, Inc.

Filing 158

Goodard v. Google, Inc.

Doc. 158 Att. 4

Dockets.Justia.com

r 11 1
Onishi
INSTRUCTION PROCESSING DEVICE USING ADVANCED CONTROL SYSTEM Inventor. Y d f r p Onishi, Kokubunji, -Ja
Assignee: Hitnchl,
3,629,853 3,408,630 3 3 5 1.895 3,573.853 3,577,189 12/1971 1011968 12l1970 4/1971 5/197 1

3,~64,98$
Oct. 9, 1973
3401172.5 340/172.5 340/172.5 340/172.5 340/172.5

[451

Newton ............................ Packard ...........................

Driscoll ............................ Watson ............................ CQtke..............................

La., Tokyo, Japan

Filed:

Mor. 1, 1972

Appl. No.: 230,913
Foreign ~ p Prbrortty p Data Mar. 1, 1971 Japan..................................

Primary Examiner-Paul J. Henon Assistant Examiner-Sydney R. Chirlin Attorney-Paul M.Craig, Jr. et al.

~
46/996 I

~ instruction processing device employs an advanced ~ An control system which has a first decoder for decoding,
in sequence, ordinary instructions except branch instructions and a second decoder, additional to the first decoder, for discriminating branch instructions. When the second decoder discriminates a branch instruction, the contents of the discriminated branch instruction are preferentially address-modified and thus the instruction to which the branch is made is read out. 22 Clsims, 5 Drawing Figures

[571

ABSTRACT

U.S. C1, ............................................. lot. Ci............................................... FkM of Search ..................................
References Cited UNITED STATES PATENTS 1011971 lshihara ...........................

340/172.5 G06f 9/20

34011 72.5

3,614,747

3401172.5

9

PATENTED OCI 3 1973
SHEET l i f F ,

3

e.
0

w

7

a
Q

0 m

ca

U

e..
0
0

W

T

i=.,
U

QD

n

m
SIC
Q
+

0 0

m

a
Q

r
). -.

mm
c . (

c( -

1-

-*

T

a

Q,
i

I n
L

SHEET 2 ilF 3

3,764,988

INSTRUCTION

PRlOR ART
I I

ri

1-

3,764,988
SHEET 3 flF 3

DETAILED DESCRIPTION OF THE INVENTION Referring to FIG. 1, there i s shown a prior art examBACKGROUND OF THE INVENTION ple of an instruction processing cycle. In FIG. 1, each alphabeticaf code indicates one cycte, 5 I . Field of the Invention with functions as follows. This invention relates to a central processing device P : preparation for a read-out instruction, for example, of an electronic computer, electronic exchanger and renewal of a program counter; the like, and more particularly to an instruction proBI : collation whether instructions are in the buffer cessing device using an advanced control system. 10 memory; 2 . Description of the Prior Art I : reading out instruction from the buffer memory; An aim of an advanced control system employed in TI : transferring the read-out instruction to an instruca computer for reading out and processing the instruction buffer register; D : instruction decoding; 15 A : arithmetic operation on the address of the instruction; memory and, if the instruction read-out requires that BO : collation whether there is an operand in the buffer information is to be read out from the memory, such memory; information is additionally read out therefrom to pre0 : reading out operand from the buffer memory; pare for processing a subsequent instruction, thus mak- 20 TO : transferring the read-out operand to the operand ing the computer operable at a higher efficiency. buffer register; and In a conventional instruction processing method, the E : arithmetic operation. instructions read out from the memory are decoded in this time chart, it is assumed that only the instrucand address-modified in sequence and no special contion 4 is the branch instruction, and the other instrucsideration is given to branch instructions to be pro- 25 tions 1 , 2 , 3 , 5 and 6 are ordinary instructions (such as cessed preferentially. Namely, a branch instruction an addition instruction) for read-out of an operand and cannot be decoded and address-modified unless its turn execution of arithmetic operations. comes around. Therefore, a considerable length of time It is also assumed that all the instructions and operis required before decoding the instruction to which the ands are in the buffer memory, and two instructions are branch is made. As a result branch instruction process- 30 read out from the buffer memory at the same time. ing has been slow in the prior art. it is to be noted that the time chart in FIG. I i only s Even up-to-date electronic computers operable at a an example; the contents of the processing cycle and the cycle time differ by the kind of device and the kind high speed in processing general operation instructions of instructions used. The aim of this time chart is to are slow in dealing with branch instructions, in spite of the fact that a computer is supposed to process branch 35 show several basic processing cycles. FIG. 2 shows in block form a part of a conventional instructions at a rate of 2 5 to 35 percent of its total ininstruction processing device which executes the prostruction processing. This problem has made it difficult cessing cycles shown in the time chart in FIG, 1. In this to improve the overall efficiency of a computer system. device, the cycles TI, D and A are processed. 40 SUMMARY OF THE INVENTION Referring to FIG. 2, the instructions supplied from the memory such as a buffer memory (not shown diaA principal object of this invention is to provide an gramatically ) are stored temporarily in the instruction instruction processing device capable of processing i n buffer register 1. These instructions are transferred in structions at a high speed. Another object of this invention is to provide a de- 45 sequence to the instruction register 2, decoded in the decoder 3, and sent to the address arithmetic unit 4, in vice capable of high speed instruction processing in an which the instructions are address-modified, advanced control system. From the time chart (FIG. 1) and the block diagram Another object of this invention is to provide a de(FIG. 2) it is apparent that the cycle D for transferring vice operable at an incomparably high speed in prothe instruction to the instruction register 2 and decodcessing branch instructions. 50 ing it in the decoder 3 is executed, instruction by inBriefly, the invention has for its objects the provision struction, in a time sequence. of a unit operated for discriminating branch instrucSimilar to the preceding instructions, the instruction tions and supplying the discriminated results to the sub4 (a branch instruction) is decoded in the decoder 3 acsequent processing unit. cording to the sequence. In other words, the instruction 55 4 cannot be discriminated to be a branch instruction B R E F DESCRlPTION OF THE DRAWING until its turn comes around. This branch instruction is FIG. 1 is a time chart showing an example of an inthen address-modified, and the instructions 5 and 6 to struction processing cycle employed in the prior art; which the branch is made are read out, As a conseFIG. 2 is a block diagram showing a conventiot~alinquence, a considerable length of time is required be60 struction processing device; fore decoding the instructions 5 and 6 , thus slowing FIG.3 is a block diagram showing an instruction prodown the branch instruction processing. cessing device embodying this invention; Referring to FIG.3, there is shown in biock form an FIG.4 is a time chart showing an example of an ininstruction processing device of this invention wherein struction processing cycle according to this invention; 65 the numeral reference 5 denotes an instruction buffer register, and 6 and 7 a tint and a second instruction and register respectively. The reference numeral 8 indiFIG.5 is a circuit diagram showing in concrete form cates a first decoder for decoding oridinary instructions a portion of the device shown in FIG.3.

INSTRUCTION PROCESSING DEVICE USING ADVANCED CONTROL SYSTEM

1

3,764,988

2

3

3,764,988

4

excepting branch instructions, 9 a second decoder for discriminating the branch instruction, and 10 an address arithmetic unit. The instruction buffer register 5, the first instruction register 6, the first decoder 8, and the address arithmetic unit 10 in FIG. 3 correspond to the prior art instruction buffer register 1, instruction register 2, decoder 3, and address arithmetic unit 4 in FIG. 2. The second instruction register 7 and decoder 9 are the additional elements provided according to this invention. This novel instruction processing device is operated in the following manner. The instructions read-out from the buffer memory are stored in the instruction buffer register S until the individual decoding sequences appear. An instruction appearing in turn is inserted into the first instruction register 6 and then transferred to the first decoder 8. In the decoder 8, the instructions other than the branch instruction are decoded, and their contents are supplied to the address arithmetic unit 10. At the same time an instruction in turn is inserted into the second instruction register 7, independent of the insertion and processing of the instruction inserted into the first instruction register 6 and decoded by the decoder 8. The second decoder 9 discriminates whether the instruction inserted in the second instruction register 7 is a branch insrruction. Immediately when the instruction is discriminated to not be a branch instruction, the next instruction is inserted into the instruction register 7 from the buffer register 5 . In this manner only branch instructions are examined from among other instructions one after another. When a branch instruction is detected, necessary processing is executed, and the contents of the branch instruction are sent to the address arithmetic unit 10, in which the instruction is address-modified. The instruction to which the branch is made is read out according to the modified result. The time required for the decoder 9 to discriminate a branch instruction from others is sufficiently short so that all the instructions stored in the instruction buffer register 5 can be evaluated within one cycle. In other words, according to this invention, a branch instruction can be accurately evaluated and decoded within the period of one cycle, or the branch instruction can be picked up and decoded in far shorter time than by the conventional processing wherein the instructions are sequentially read out and decoded cycle by cycle. FIG. 4 is a time chart showing how instructions are processed according to this invention. The cycles indicated by the identical codes as in FIG. 1 are functionally the same as those in FIG. 1, In FIG. 4, the cycle DB is for discriminating the branch instruction from the instructions stored in the instruction buffer register 5 , Within this cycle DB, all the instructions stored therein are evaluated if the branch instruction is present. As illustrated in FIG. 4, a branch instruction 4, if present, is discriminated in the cycle DB,and addressmodified in the next cycle A. Following this operation, the processing device starts reading out the instructions 5 and 6 to which the branch is made. The cycle A of the branch instruction 4 is preferentially executed. During this execution, the cycle A of the instruction 2 is maintained in a hold condition.

From the time chart in FIG.4 in comparison with that in FIG. 1, it is apparent that the execution of branch instruction decoding is faster by 2 cycle periods. This means that the instructions to which the 5 branch is made can be processed at a greater efficiency than in the prior art. FIG. S is a circuit diagram showing in concrete form a portion of the instruction processing device shown in FIG. 3, 10 In FIG. 5, the references SA,SB, SC and SD denote instruction buffer registers (corresponding to 5 in FIG. 3 1 for temporarily storing the instructions transferred from memory such as a buffer memory (not shown diagrammatically). The numeral l l denotes a counter for 15 indicating one of the instruction buffer registers SA, SB, 5 0 and 5 0 from which the next instruction is read out, and 12 is selecting circuit for decoding the contents of the counter 11 and selecting one of the instruction buffer registers SA, 5B,SC and SD. The numeral 20 13 indicates an instruction register (corresponding to the second instruction register 7 in FIG.3) to which the instruction is transferred from the instruction buffer register SA, SB, SC or 5D.13A is the field for the instruction operation code, 138 for the number of the 25 index register, and 13C for the address of an operand. The numeral 14 represents a decoding circuit for decoding the operation code 13A of the instruction register 13 and thus discriminating the branch instruction. (This decoder corresponds to the second decoder 9 in j0 FIG. 3). The numeral IS denotes a register for registering the operand address, 16 a register for registering the address of an index register, 17 a flip-flop indicating that a branch instruction is being processed, 18 through 21 and 43 AND circuits, and 22 through 25 OR cir35 cuits. The references 26A, 268,26C and 26D denote transfer lines for transferring instructions from the memory unit to the instruction buffer registers SA, SEI, SC and 5D respectively, 27A, 27B, 27C and 27D transfer lines for transferring instructions to the instruction register I 3 from the instruction buffer registers SA, 5B,5C and 5D respectively, 28A, 288, 2SC and 28D selection lines for selecting the transfer line 27A,27B, 27C or 27D according to the indication from the selection cir4 5 cuit 12,29 a transfer line for transferring the operation code 13A of the instruction register 13 to the decoder circuit 14, 31 an output line carrying an output when the decoder 14 determines that the presented instruction is not a branch instruction, 32 an output line carry50 ing an output when the decoder determines that the presented instruction is a branch instruction, 33 a transfer line for transferring the operand address field 13C of the instruction register 13 to the register 15, 34 5 5 a transfer line for transferring the index register number 13B of the instruction register to the index register group (not shown diagrammatically), 35 a transfer line for transferring the operand address of the first instruction register 6 (FIG. 3), 36 a transfer line for transfer6o ring the address of the index register designated by the index register number 138, 37 a signal line indicating that the condition of the branch instruction has been established, 38 an output line for setting the flip-flop 17,39 an output line of the counter 11,40 and 41 out65 put lines of the registers I5 and 16 respectively, and 42 a transfer line for transferring the address of the index register selected according to the index register number of the first instruction register 6 (FIG, 3).

'*

This instruction processing device is operated in the following manner. The instructions read out from the memory are transferred through the transfer lines 26A, 26B,26C and 26D and stored in the instruction buffer 5 registers %a, SB,5C and SD respectively. The number corresponding to the instruction to be read out from the instruction buffer register §A,§B,SC or SD is stored in the counter 11. The contents of this counter are supplied to the selecting circuit 12 by way of the output fine 39. In the selecting circuit 12,one of 10 the selection lines 28A,288,28C and 28D,which corresponds to the instruction buffer register number, is selected, and a "1" signal is transmitted over the selected h e . This "1" signal is applied to the AND circuit 18A, l8B, 18C or 18D,which corresponds to the selected line. The instruction transferred from the instruction buffer register SA, 5B,SC or SD is sent out over the transfer line 27A,278 , 27C or 27D , which corresponds to the A N D circuit to which the "1" signal was applied. This instruction is received by the instruc- 20 tion register 13 via the A N D circuit lSA, 18B, 18C or 18D and via the OR circuit 22,The instruction register 13 consists of memory fields 13A, 138 and 13C. The operation code of the instruction stored in the field 25 13A is sent to the decoding circuit 1 through the 4 transfer line 29.The decoding circuit 14 determines or judges whether the given instruction is a branch instruction or not. The result is sent out over the output line 30. The decoding circuit 14 can be constituted of 3o a simple, known logic circuit. A "1" signal is sent out over the output line 30 when the instruction is a branch instruction. A "0" signal is sent out over the output line 30 when the determination does not result in a branch instruction. The signal on the output line 30 is supplied 35 to the OR circuit 23. When the determination does not result in a branch instruction, the OR circuit 23 delivers an inverted output, Le., a "1" signal to the output line 31. When it is a branch instruction, a "1" signal is sent out over the output line 32. 40 If the operation code 13A of the instruction register 13 is discriminated to be a branch instruction in the decoding circuit 14,the output line 32 carries a "1" signal. This `$1"signal is appiied to the A N D circuit 19, and the operand address in the field 13C of the register 45 13 is transferred to the register 15 through the transfer line 33, A N D circuit 19 and OR circuit 24. The index register number in the field 138 of the instruction register 13 is sent to the index register group (not shown diagrammatically, through the transfer line 50 34, One of the index registers corresponding to the given register number is selected, and the address of this index register is returned over the transfer line 36. A t the same time. a " I " signal is applied to the A N D circuit 21 by way of the output line 32, and the index 5 5 register address o n the transfer line 36 is stored in the register 16 via the A N D circuit 21 and OR circuit 25. The operand address and the index address stored in the registers 15 and 16 are supplied to the address arithmetic unit by way of the output lines 40 and 41, respectively. Then the two addresses undergo address modification. When the decoding circuit 14 determines that the operation code 13A of the instruction register 13 is not a 65 branch instruction, a "l"signa1 is sent out over the output line 31, thereby advancing the contents of the counter 1 1 by one, and the next instruction is selected

5

3,764,988

6

`'

in the foregoing manner. These operations continue until a branch instruction is discriminated. Via the output line 31, a "1" signal is applied to the AND circuits 20 and 43, and the operand address and the index address of the instruction stored in the first instruction register are transferred to the registers 15 and 16,respectively, by way of the transfer lines 35 and 42,A N D gate 20- OR gate 24 and AND gate 43 OR gate 25, Thus, when the decoder evaluation results in a branch instruction, address modification is executed on the branch instruction; when the decoder evaluation does not result in a branch instruction, address modication is executed on other instructions. Via a " I " signal on the output line 32, flip-flop 17 is set, the set output is applied to the selection circuit 12 via the output line 38, and all the outputs of the selection circuit 12 become "0"signals. After the condition of branch instruction is established, the flip-flop 17 is reset. In other words, processing of the subsequent branch instruction is inhibited until a branch condition is established after the first branch instruction has been discriminated. By a "1"signd on the output line 32,the contents of the counter 12 are set to the necessary initial value. After establishment of a branch condition, the selection circuit 12 starts the aforementioned selection operation from the number corresponding to the initial value. The AND circuits 18A,188.18C and 18D described above are only one bit gates for explanatory simplicity. Practically, however, these AND circuits must be provided to correspond to the number of bits of the instruction register 13. Similarly, the A N D circuits 19 through 21 and 43 must correspond to the number o f bits of the registers IS and 16. According to this invention, as has been described above, a unit operated only for discriminating and processing a branch instruction is used in addition to the conventional unit and, thus, the invention enables an electronic computer to expedite its branch instruction processing and increase overall system efficiency. What I claim is: 1, An instruction processing device employing an advanced control system, comprising: instruction buffer means for storing instructions read out from a memory; decoding means for decoding in sequence said instructions except a branch instruction; judging means for judging whether any one of said instructions is a branch instruction; address arithmetic means for address-modifying the contents of said instructions; and transfer means for preferentially transferring the contents of an instruction judged as a branch insttuction to said address arithmetic means. 2,An instruction processing device employing an advanced control system, comprising: an instruction buffer register for storing instructions read out from a memory; first and second instruction registers for taking out said instructions stored in said instruction buffer register and for storing said taken out instructions; an address arithmetic unit for address-modifying the contents of said instructions;

-

7

3,764.988
circuit and said second instruction register, for transferring the contents of the instruction temporarily stored in said second instruction register and detected to be a branch instruction to said fourth means, 5 8. An instruction processing device according to claim 6,wherein said third means further comprises means, responsive to the output of said decoding circuit and being coupled to said buffer register, for effecting the transfer of a new instruction from said 10 buffer register into said second instruction register, when the output signal of said decoding circuit indicates that the instruction temporarily stored in said second instruction register is an instruction other than a branch instruction. l5 9. An instruction processing device according to claim 6, wherein said third means further comprises means, responsive to the output of said decoding circuit and being coupled to said buffer register, for preventing the transfer of a new instruction from said 2o buffer register into said second instruction register, when the output signal of said decoding circuit indicates that the instruction temporarily stored in said second instruction register is a branch instruction. 10. An instruction processing device according to 2 5 claim 8, wherein said third means further comprises means, responsive to the output of said decoding circuit and being to said buffer register, for preventing the transfer of a new instruction from said buffer register 3o into said second instruction register, when the output signal of said decoding circuit indicates that the instruction temporarily stored in said second instruction register is a branch instruction. 11. An instruction processing device according to 35 claim 7. wherein said fifrh means further comprises a second gating circuit, responsive to the outputs of said decoding circuit and said first instruction register, for transferring the contents of the instruction temporarily stored in said first instruction register to said address 40 arithmetic unit, when the output of said decoding circuit indicates that the instruction temporarily stored in said second instruction register is an instruction other than a branch instruction. 12. An instruction processing device according to 45 claim I I, wherein said fourth means comprises an address arithmetic unit in which the contents of instructions delivered thereto are address-modified. 13. An instruction processing device according to claim 11, wherein said fifth means further includes an operand address register and an index register, each of which is respectively coupled to the operand and index portions of each of said first and second instruction registers via said first and second gating circuits, for storing the operand and index addresses of instructions 5 5 transferred to said address arithmetic unit. 14. An instruction processing device according to claim 10, further including an input gating circuit connected between the output of said at least one buffer register and the input to said second instruction register 60 for gating the contents of said buffer register into said instruction register. 15. An instruction processing device according to claim 14, wherein said means for effecting the transfer of a new instruction into said second register comprises means, coupled to the input of said input gating circuit, for effecting the passage therethrough, of the contents of said buffer register.

a first decoder for decoding the instructions stored in said first instruction register, except a branch instruction; a second decoder for judging whether the instruction in said second instruction register is a branch instruction; and gate means for preferentially transferring the contents of an instruction to said address arithmetic unit when the instruction is judged to be a branch instruction by said second decoder. 3. An instruction processing device employing an advanced control system as defined in claim 2, in which said second decoder and said gate means comprise: a decoder for judging from the operation code field of said instruction in said second instruction register whether such instruction is a branch instruction; a gate for preferentially selecting both the operand address field of an instruction and the contents of the index register designated by this instruction when the instruction is judged to be a branch instruction by said decoder; and a register for holding and transferring the output of said gate to said address arithmetic unit. 4. An instruction processing device for a central processing portion of a computet having a memory unit which a plurality of instructions to be carried out are stored, said processing device comprising: first means. coupled to the memory unit, for storing instructions read-out therefrom; second means, coupled to said first means, for sequentially decoding all instructions except branch instructions supplied thereto from said first means; third means, coupled to said first means, for detecting the existence of a branch instruction among instructions supplied thereto from said first means; fourth means, coupled to said second and third means, for address-modifying the contents of instructions supplied therefrom; and fifth means, responsive to the detection of the existence of a branch instruction by said third means, for preferentially transferring the contents of said branch instruction to said fourth means, to be address-modified thereby, whereby processing of the contents of branch instructions included among a pluraijty of instructions in memory will be expedited. 5. A n instruction processing device according to claim 4, wherein said first means comprises at least one instruction buffer register coupled to said memory unit for storing instructions from said memory unit, and further including first and second instruction registers coupling the instructions from said first means to said second and third means, respectively, by temporarily storing instructions from said at least one instruction buffer register prior to effecting a transfer of the contents of the instructions to said second and third means. 6 . An instruction processing device according to claim 5 , wherein said third means comprises a decoding circuit, responsive to the contents of an instruction stored in said second instruction register, for providing an output signal representative of whether the contents of the instruction temporarily stored in said second instruction register correspond to a branch instruction. 7. An instruction processing device according to claim 6, wherein said fifth means comprises a first gating circuit, responsive to the outputs of said decoding

9

3,764,988

10

16. An instruction processing device according to claim 15, wherein said transfer preventing means camprises means, coupled to the input of said input gating circuit, for inhibiting the passage therethrough, of the contents of said buffer register. 17. An instruction processing device according to claim 16, wherein said passage effecting and inhibiting means comprises a flip-flop coupled to the output of said decoding circuit and to said input gating means for providing a first bistable output when the output of said decoder circuit indicates that the contents of said secand instruction register correspond to a branch insttuclion and for providing a second bistable condition when the output of said decoder circuit indicates that the contents of said second instruction register correspond to an instruction other than a branch instruction, said bistable outputs being coupled to said input gating means. 18. An instruction processing device according to claim 17, wherein said at least one buffer register includes a plurality of buffer registers, and wherein said passage effecting and inhibiring means further includes a counrer circuit coupled to the output of said decoder circuit. and a selecting circuit responsive to the outputs of said Rip-flop and said counter circuit for controlling the gating of the contents of a selected one of said plurality of buffer registers into said second instruction register. 19, A n instruction processing device according to

5

1 0

15

20

25

claim 18, wherein said fifth means comprises a first gating circuit, responsive to the outputs of said decoding circuit and said second instruction register, for transferring the contents of the instruction temporarily stored in said second instruction register and detected to be a branch instruction to said fourth means. 20. An instruction processing device according to claim 19, wherein said fifth means further comprises a second gating circuit, responsive to the outputs of said decoding circuit and said first instruction register, for transferring the contents of the instruction temporarily stored in said first instruction register to said address arithmetic unit, when the output of said decoding circuit indicates that the instruction temporarily stored in said second instruction register is an instruction other than a branch instruction. 21. An instruction processing device according to claim 20, wherein said fourth means comprises an address arithmetic unit in which the contents of instructions delivered thereto are address-modified. 22. An instruction processing device according to claim 21, wherein said fifth means further includes an operand address register and an index register, each of which is respectively coupled to the operand and index portions of each of said first and second instruction registers via said first and second gating circuits, for storing the operand and index addresses af instructions transferred to said address arithmetic unit.

+*+**

30

35

40

45

50

55

60

65