Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
~21~
71260-6
APPARATUS AND METHO~ FOR
EXECUTION OF BRANCH INSTRUCTIONS
BACKGROUND OF THE INVENTION
Field of the Invention
This invention relates generally to data processing
systems and, more particularly, to data processing systems in
which the implementation of instructions is divided into a
plurality of suboperations permitting an overlap in the execution
oE consecutive instructions, and typically referred to as
pipelining the execution of the instructions. This technique is
frequently used in the data processing unit subsystems to increase
the rate of instruction execution. The present invention reduces
the delays encountered in the execution of conditional branch
instructions.
~RIEF DESCRIPTION OF THE DRAWINGS
Figure 1 is a block diagram of the components of a data
processing system capable of utilizing the present invention.
Figure 2a is an illustration of the execution of an
instruction sequence according to the related art; Figure 2b is an
illustration showing how an instruction can be divided i~to a
plurality of instructions segments; and Figure 2c illustrates how
a pipellned instruction execution can provide or increased
perEormance by a central processing unit.
Figure 3 is a block diagram of a data processing system
implementing the pipelined execution oE an instruction sequence.
Figure 4 illustrates the execution of an unconditional
branch instruction.
; ~$~
gL2~3~
71260-6
Figure 5 illustrates the execution of a ~onditional
branch instruction in which the processing of further instructions
is halted until the determination of the condition has been
completed.
Figure 6 illustrates the execution of a conditional
branch instruction according to the present invention.
Figure 7 illustrates the execution of a conditional
branch instruction, for which the branch to the new instruction
sequence is highly probable, according to the present invention.
Figure 8a is a block diagram of the central processing
unit along with associated signals illustrating the operation of a
portion of the implementation of a conditional branch
macroinstruction.
Figure 8b is a block diagram of the central processing
unit along with associated signals illustrating the operation of
the remainder of the conditional branch macroinstruction.
Description of the Related Art
Referring to Fiyure 1, a typical data processing system is
shown. The data processing system includes at least one central
processing unit 10 (or 11), at least one input/output device 13
(or 14), a memory unit 15 and a system bus 19 coupling the
plurality of subsystems or units of the data processing system.
The central processiny unit processes groups oE logic signals
according to software and/or firmware
. ~
-2-
.~.,
128S657
~ ~ DE~6~4
instru--tions. Thé lo~i~~ si~nal ~roups t~ be pr~ essed are
typically stored in the memory unit 15. A console unit 1~ can
be 4upled t,~ the .-entral processin~ unitCs~ and in--ludes the
apparatus and st~red instructi~ns to initiali2e the system and
can fun.ti-~n as a terminal durin~ the operation ~f the data
processing system~ The input/output units provide the
interfa,:e of the data processin~ system to terminal units, ma~;s
storage units, communication units, and any oth~r units to be
:cupled to the data proeessing system that exchan~e l~ic
signal groups with the system~ The present inventi~n relates
t-~ the oper~tion ,-~f the central pr~ essin~ unit, and pr.~vid~
an apparatus and meth--d for more efficient executi4n of cer~ain
portions of the pr.~yr~ms contr~llin~ the proeessin~ ~f data
si~nal ~r4ups.
In a data processing system, such ~s i5 illustrated in
Fi~ure 1, the a-tual manipulation of data siynal gr-~ups takes
place under the ._ontrol o~ ~ ~roup of related instructions that
is ~enerally .alled a pr4~ram~ These instructions are executed
in a sequen--e. ~eferring next to-Fi~ure ~a, the execution .~f a
series of instru~-ti~ns accordiny to the related art is
illustrated. Durin~ a first tlme interval, T~, the instruction
~1 is exe-:-lted by a central prc,:essing unit ~ubsystem. A~ter
blle flrst instruction i5 executed, a next instructi~n #~ in the
sequen~e is exe~:uted by the ,:entral pro~essing unit subsystem
during the second time interv~l,TO. Upon completion o~
instru,tion #7, the data pr-~cessing unit executes instrueti~n
~3 durin~ the third time interval To~ In order to maintain an
orderly exe--uti~n oS instructi4ns, the interval for the
.
~85657
~J DE1~64
execution of ~ny instruction by ttle data pro-:essin~ unlt
requires a predetermined period of time. lf the executi~n time
for an instru~~tion can have a variable length, complex
~pparatus must then be included in the central proces~ing unit
to co~rdinate the exctlan~e of data sir~nal ~roups between the
~ntral processinr~ unit and the ottler ~ubsystems of the data
processin~ system. T~lus~ the period for executlon of the three
instru,-tions will ~enerally be three times the basic time
period. It will be clear ttlat the basic time interval must be
of suffi,-ient dur~tion t4 permit the execution o~ thr?
len~thiest instruction in the instruction set unless the
execution of instructions i5 implemented using a m~re
sophisti,-ated te--hnique such as des-~ribed below.
In ~rder to provide f,~r faster c,perati.~n of thra data
pr~cessin~ system, a technique for ~ividin~ the execution l~f an
instruction into the e~ec~tion of a plurality c,f instruction
se~ments tlas been (ievised. Ttle instru~-tion se~ents ~re
components of a micrc,instruction and a related group of
mi,-roinstructi~ns implements a ma,roinstruction. When ttle
apparatu~ implementiny the ser~ments is or~ani~d appr.:~priately,
the executi~n of the instructions can be performed in an
overlappin~ m~nner. This technique is referred to as
"pipelinin~" the exe,:util~n of an instruction set. While the
execution of eactl pipelined instruction can ~ake a lon~er
period of time than ls required for the execution of a
nonpipelined instruction, becau~e cf tt-e ~dditional appar~tus
required for the divisic,n of the instruction into the
instruction seymQnts, ~n instruction stream ,-an be executed
S~
: .
: :
~L~85~5~7
DE~6
fagter tllan i5 p,3ssible for the nonsegmQnted instructi~ns. ~n
Fi~ure ~b, the divisi~on of an inst;ruetion into a plurality ~f
segments is sllown. It will be understood that ea-h segment
relates to a separate and independently operatin~ clr~up of
components in the central processin~ unit. Registers and
~ates, aecordin~ to prin~:iples well-known in the art cf data
processing system desi~n, can implement the operation ~f a
clr~up of ,-omponents executin~ a part$,:ular segment. Tl7e
subinterval, t~, f.,r each segment must be sufficiently l~ng to
permit the execution of all possible segments in each apparatus
clroup,
~ eferring ne~t to Fi~ure ~c, the resulting increase in the
rate o f exe,:ut i on of a sequence of in~tructions pos~ible
thr,~ugll the use "f pipelinin~ techniques i5 illustrated.
Instru~ti,~n #1 i5 n,-,w ~:ompleted in the new ~and possibly
longer~ time period of T90 equals n times t~, wllere to is the
subinterval required f,3r the exe,:uti~3n ,3f ea.:l~ instruction
segment and where n is the number of instruction se~ments
required for the e~;e.:ution .~f ea,:h instru,:ti~n. The next
instrul-ti.~n i~ the sequen.-e, instructi~n #~, begins an interval
t~ after the bel~innin~ ~f instruction #1~ The thircl
instru,-tion in tlle sequen,~.Q, lnstruction #3, then beclins an
interv~l to thereafter. Ea~h instructlon can take the
increased amount of time for the execution. However, once the
initial interval for the ~ompletion of the first instructi~n
has passed, an instruction i5 completed after each interval to.
Thus, for a sequen,:e of instru-:tions, the execution of tile
secluence can be a~.-elerated even thou~ll the indiv~dual
~;~135657
DEC664
instru,-ti,-,n can take an increased len~th of time to exe,:ute.
Althougll the pipelining technique can provide for more
rapid execution of an instructi~n sequence, this te.hnique
lc.ses efficiency with the occurrence of conditional "bran--h"
instru.tions in an instrurtion ~equence. The bran-:h
instru--tic.n involves the swit~hing fr~m one in~truction
sequen-:e t-~ a se-:ond instru-:tion sequen~e. ThR conditional
bran-:h instru.-tiol- involves the testin~ of a quantity ay~inst a
predetermined .:.~ndition. Dependiny on the result of the test,
the instru,-tion sequen,~e can ,-ontinue in the present sequence
c,r the instruction sequen--e can Jump or branch bo a new
instruction sequen~-e. Fcr the instruction seqLtence bein~
e~e-:uted a~ shown in Fi~ure ~a, instru--tion #1 :an be the
instru,-tion testin~ the condition, and the particular next
sequential instruction, illustrated by instrultion #~, can be
determined by the result of instru-_tion #1. In the c~se of the
pipelined exe.:ution of the instru~:tion set as illustrated in
Fi~ure ~.-, the result of the conditi~n testing ~rocedure may
nct be available until instru-:ti4n se~ment ~ of instruction #1.
However, instructi--,n #~ will, in normal operati.~n, already have
beyun execution and instruction segments A and 8 of instruction
~`~ ean h~ve been completed.
In order to address the problem ~f branchin~ in pipelined
executi,~n.of ~n~truction sequences, the typical approa.:h has
been to suspend the execution of the lnstructic,n sequence until
the branch ~:ondition has been tested. Once the branch
~lj
condition has been tested, then the ~xecution of the correct
instruction sequence, i.e. the ori~inal instru-tion sequen-:e or
; , ~
,~:
,
~, :
, ,
~Z~ ;7
~ ~ DE~.6~
.
the new instru,:tion sequence, i5 initi~tedl This strateyy
provides an ineffioient use of the central processlng unit ~nd
results in delays in the instru,-tion execution sequence. Not
only is a delay in,-urred in waitin~ for the testin~ o~ the
:ondition, but a further del~y is en-:ountered as the pluYality
of instructi4n segments i5 executed prior tc, the completion of
the instru,:tion, sometimes referred to as filliny the pipeline.
A need has therefore been felt for apparatus and method c,f
operation for pipelined exe,:ution of an instru,:tion sequen.e
that would minimize the effect of a branch instructi,~n on the
system performance without requiring extensive additional
apparatu~; and minimizin~ the compromi~;e in improved instru~tion
~xe,utic,n resultin~ from the use of the pipelined instru,:tion
sequence e~ecution.
SLJMMARY OF THE INVENTION
It is an obje~:t of the present invention to provide an
improved data processin~ system.
It is a further obje--t of the present inventi.-.n to pr,~vide
an improved data pr.~ces~..in~ unit for the execution of an
lnstru-:ti4n sequence~
It is a furt~ler ob~ect of the present invention to prc,vide
an improved data processin~ unit f-3r thQ pipelined executi~n of
an instruction sequence.
It is a more particular ob~ect of the present inven~ion to
provide a data pro~-essin~ unit having a pipeline~ instruc~i~3n
sequence exec~tîon in whl~h either the c~rlg$nal instruction
~2~57
~ ~ DE~6~4
sequen~e ~r the bran~:h instrueti~n sequen-:e :an be initiated
bef,~re the determinati~n of the ,~ccurrence of the condition has
been c,~mpleted.
Ttle afcrementic!ned and ~ther objects ar~ ac~omplished,
acc,~rding t,~ the present invention, by pYcvidin~ a data
pro,-Qssinc3 unit Wittl apparatus for reco~ni2ing the ~c~urren-:e
,~f a ,-,-,nditi,~nal bran,h instructi-~n. Upon rec4gniti-~n of tl~e
c,3nditional branch instru.:ti~n, the data prccessing unit
initiateC the retrieval clf the first instru-:ti,~n in ~e~u~n-:e t,~
be e~ecuted when t~e branch conditi.~n is determined t;o be trueO
The ne~;t instru.-ti.~n exe.:uted by tlle data pr-~ ssin~ system~is
the instru,-ti.~n that wc.uld be executed if the branch c-~ndition
is determined to be false~ i.e. tlle ~ri~inal instru,tic~n
sequence is cc,ntinued. While this in~tructi~n ~and any
subsequent instructions in the ,~riyinal instructien sequen,:e)
i5 being exe,-uteci, the data prccessinc3 system is preparing t~
exe,-ute the instru~ti~n sequence determined by the branch
cc,nditic,n ~:if true). When the determination is made with
respect t,-, the bran,:h ,."nditi,~n, the data pr~~essin~ unit can
c,~ntinue execution of the ori~inal instructi~n sequence already
in exe,uti,-,n if the conditi4n i5 false~ When tl)e bran,-h
c.~nditibn is true, then the a,:ti.vity ~f the data pr~cessinc~
unit in preparing for the exe-uti-~n of the new instru,:tion
sequen,-e is utili~ed and the executi~n of the new instruction
sequence repla,-es tlle execution of the ~ri~inal instruetion
sequen.:e that is in pr~ress. For selected :onditional branch
instru-:tions, f~r whi--h there i5 a hic~h pr~bability that the
bran-:h ..~ndition will ~ccur, the ~:entral processinc~ unit
, :
.j, , .
~a~Gs~
71260-6
executes an unconditional branch instruction to the new sequence.
After the preparati.on for the new instruction se~uence ls
completed, the condition is tested. If the condition (as
originally interpreted) is true, the central processing unit
contlnues to execute the new instruction sequence. Otherwise, the
instruction sequence execution reverts to the original instruction
secluence .
In summary, the inventlon provides, according to a first
broad aspect a method for implementlng a conditional branch
sequence of overlapped microinstructions, comprising the steps of
initiating execution of a conditional branch microinstruction fcr
determining which of first and second sequences of
microinstructions are ~o be executed in dependence on the presence
of a predetermin~d condition as a predetermined time; and
executing a portion of said first sequence o~ microinstructions
after initiation and before completion of said conditional branch
microinstruction.
According ko a second broad aspect, the invention
provides a circuit arrangement for implementing a conditional
branch microinstruction in a microprogrammed central processing
unit haviny an instruction subunit and an execution subunit
connectecl to receive lnstruction signals and data siynals
respectively from a cache memory unit, comprising: control logic
means for sending a first control signal to said execution subunit
for initiating output of a condition signal by said execution
subunit, a second control signal to said cache memory subunit for
~ 285657
71260-6
of the state of said condi~:Lon siynal, said control signals being
output in response to a conditional branch microinstruction;
branch logic means for determining the state of said condition
signal in response -to receipt of said third control signal, said
branch logic means outputting a first decision signal if said
condition signal is in a first predetermined state; and trap logic
means for cancelling results obtained by executing a
microinstruction rece:lved by said control logic means subsequent
to said aondition branch mlcroinstruetion, in response to said
first decision signal from said branch logic means.
These and other features of the present invention will
be understood upon reading of the following description along with
; the drawings.
DETAILED DESCRlPTION OF THE PREFERRED EMBODIMENT
Detailed Description of the Figures
Figure 1 and Figure 2 have been described in relation to
the related art.
Referring next to Figure 3, an organization for a
central processing uni.t 10 implementing the pipelined execution of
2Q an instruction sequence is shown. The central proaessing unit is
divided into an instruction subunit 31 and associated control unit
32, an exec:ution unit 33 and a cache ~or local) memory unit 34.
The cache memory unit 34 ls aoupled to the system bus 19 and
exallallges cJroups of locJia signals with the other
9a
'~" ''' ' ' ' " ' ' ' ';
. '
'
`' ~' ' .' '
~2~3565i7
~ ~ DEu6~4
subsystems of the data processing system by means of the system
bus under control of the -~ntr41 unit ~2~ The execution unit
33, again under .:ontrol of the control unit 3-~, performs the
manipulation of the data si~nal ~roups that i5 defined by the
instructi,:,ns being executed. The instruction unit receives the
instru,-tions to be executed ~nd ref.~rmats the instru,:tions in a
manner that ,:an be used to control the operation of the central
pr4cessing unit. The reformatted i~structions, or portions
therel3f, are applied to the ,:ontrol unit 32 to provide the
c~nfi~uration of the logic element~ of the data processin~ unit
to implement the ,~peration defined by the instruction.
Tlle structur~ defined above suppor~s the use of
mi,roinstru~ti.~ns to implement ma,-roinstru-_tions. A
macr~instruction ~an be implemented by a ~in~le
micr,~instruction or by a plurality ~f mi,-roinstru,:tions
depending on the cc,mplexity, the nature ,~f the appar~tus of the
central pro,-essin~ unit, and similar parameters. It is the
micr,~instructions that ~re divided into microinstruction
se~ments, ~5 shown in Fig. 2b. Each mi-:roinstru,-ti,~n in,-ludes
"mi,-r~ rders" that ~ ntrol the ~roups ~f components.
P~eferriny to the cimplified divisi~n of the data
pr,~ces~ing unit shl..,wn in Fi~ure ~ and fc,r purposeC~ clf
illustratin~ the inventiont the lengbh of time f-~r ea~h unit ~f
the central pr~cessing unit to cc,mplete it~ p,~rtion of an
~ exe,:ution ,:,f an instructlon will be taken to be equal. Thus,
i for an instructic,n to be exel:uted by the data pr4cessin~ unit,
the execution of a set of instructions is illustrated in Fi~ure
c. The first instruction will be processed by the instructi,-,n
'
-
/
., .
,..
~LZ~i7
~ DEI_~64
unit during a first interval t~. Durin~ the third interval t~,
the ~ache men~ry unit can be processing instructi~n #1, theexecuti~n unit ,-an be pro,:essing instruction #2, and the
instruction unit can be processin~ instruction #~ This three
level pipeline ,an continue as lon~ as instructions are entered
intcl thr~ instru,-tion unit.
It will be ,lear that the division of the data processing
unit into the ir-dicated functional units is, in ~enera}, not
suffi,-ient t,~ provide an operable pipellne con~i~uration~ Each
of the fun:tional units des,ribed above can require a plurality
of suboperations to c,~mplete the execution of each instructien.
For purposes ~f illustration7 a pipeline that in ludes f4ur
set~ments, instead of the three seyments described with
reference to fi~ure 3, will be used to des,:ribe the invention.
Referrin~ ne~;t to Figure 4, the e~;e,:uti4n of an
unl:onditi~rlal br~n,-h instru,:tion is illustrated. The
uncrJnditi,~nal branch instru~-tion f,-,r,es the ,_entr~l pr,~cessin
unit to e~e~:ute a new instruction sequen:e bet~innint~ at the
instruction specified by the un onditi-/nal t)ran~h instr~tion.
As indi,:ated in Fi~ure 4, the un,onditional branl:h
macroinstruction 4~10 is initiated, and the first of its
,:rresp,:,ndin~ mi,-r,~instru,:ti~ns ~auses the apparatus ,~f the
,:entral pr,-":essirlt~ unit to retrieve the first macr~instru~:tion
,~f the tàr~et sequen:e of instru:ti,~ns. The next three
instru:tions in the sequenc~ instr~ctiotls 4011, 401_, 401~, are
"no operatic~n" instructions in whi:h the si~nals fr~m the
contrc,l unit ~,~ n,-,t result in a~tivity th~t ~ontributes to the
exe,:ution ,~f the instruction. Mi,:roillstruction 4014 in~ludes
~1
' , . ' ~ .
. . . .
,
:, ,
~8S~;7
~ DEC:6~,4
the end instru~:ti~n micr.~ rder :ompl~tin~ the implementation
cf the un--~nditi.--n~l branch ~a.-roinstruction and causir)g the
:entral pro.essing unit t4 begin execution of tl~e tar~et
sequence .~f macr.~instructicns.
~ eferring next t.~ Figure 5~ the exe,:ution of a :~nditi~3nal
bran-:h ~acroinstruction instructi-~n, in which the present
inventi-~n is n-~t used, is illustrated. In this pr~cess, the
first mi,:roinstruction implementin~ the ma-:roinstru.tion can be
,:,~ndition testiny !nicr-3instru.:ti-~n 5010. This instru-:tion
tests the cc.nditi4n c.f the c~nditional branch instructior~.
~ecause the result .~f the c-~nditi-~n i~ not kn~wn until the end
of the instructi.:~n, exe.:uticn .~f further processing is
suspended until t~l~ results .~f the test have been determined.
Thus, micr~instructi.-.ns 50ll, 5012 and 5~13 are no c~peration
instru-:ti-:.ns. The c-:~nditi.~nal branch instru-:ti.-n determines a
.:-...nditic.r1 that .:an be true cr false. If the c.~nditicn is true,
then the branch is made ar.d the new instructicn 6equen-:e is
exe.-uted. In the example of Fi~ure 5, the un...onditic,nal branch
instructi-:.n 50l6 is exe-~uted and the instruction sequence .-.f
Figure 4 is implemented. If the c~ndition is fa}se, then
exe-:uti-3n .:-f the :riclinal instructi-3n sequence is ~ntinued. As
illustrated in Figur~q 5, in~tructi,~ns 5015, etc. in the
ori~inal instru--ti,:,n sequen,-e are n,3w executed.
~ eferrin~ next t~ Fi~ure 6, the executi,:,n ,3f a cc,nditional
branch instructlol ac,:~rdin~ t,3 the present inventi,~n i5` gh~wn-
Alth~u~h this instru~-tion ~eq~lence 4f tlle present invention
implements a --~nditi-~nal bran-:h maer.3instructic3n, t~e
individual mi-:roinstru.tion~ are nct identical with the `
'
~Z~5657
~ ~ ~E~ 4
,:~nditional bran,h instru,-tion of Fi~ure 4~ The first
micr,~instruction ~Ctl(~ ~f the sequence in~ des the c4nditional
bran,h micro-crder. The inr,tru~-tion 601l~, in addition to
testing t~le condition~ provides an address t-~ the ca,:he memory
unit ~f the first instru--tion in the new sequen.-e of
instru.:tions, in a manner that the unconditi-~nal bran-_h
instru,tion w,~uld be implemented. Hcwever, in distin,~tion to
the un,-onditil-~nal branch in~tructicn in whirh three no
,~perati4n instru.-ti,-,ns are found after the bran.:h instructi-:.n,
in the present invention, three microinstructicn~ irnplementin~
~ri~inal sequence r~re executed. ~y the end ~ the first
seQment of the third criQinal sequen.:e instruction, the
detrrmination of the truth .~r falsity of the .-~ndition has been
determined, i.e. as indicated by the arrow in instrL~,-tion 61)1b
in Figure 6. If the ~onditi-.~n is false, the ~ri~inal
~ n~i~roinstructi4n r~equenct? contir7ues ~s illustrated by
;~ instru-ti-~n 6014. If the conditi-~n is true, then a .:,ne
mi,roinr~truction bran~h trap rcutine 6015 i5 executed th~t
~~hantles the instru~tion sequen,e in executi-~n to the new
sequence ~ illustrated by instructicn ~016. In adrlition, the
resultri of tt7e inr;tructions 6011, 601~ and 6~13 are irrelevant
and ~re discarded when the new s~ouence is sele-:tr.~d by the
,:~ndition.
~eferrinr~ next to Figure 7, the ex~cuti,~n of the
-onditional bran.:h instru.-tior7, of the type havin~ a hi~h
probability that the branch to the new sequence will be
implemented, is illur,trated. This type ~f macroiristruetion
typi--ally involves c-.,ntrol of an instru~ti-_.n loop, where a
,:
~ 13
,.;~ ~ .
. , ~ , .
.~ :
:
i6S~7
~J DEI_.6~4
multipli,:ity of ma,:roinstru-:tions will typi-~lly be exe-uted
repeatedly before the ~acroinstruction sequen.:e c-~ntinues in a
conse,:utive instructi~n sequen--e. Instru,tions 7010 anJ 7011
are parameter determinin~ microinstru--tic,ns. Instructic,n 701
determines the destinaticln address if the ~-~ndition is
determined to be true. 5imultaneously with the determination
of the destination address, instruction 701~ is als~ an
unc~.,nditicnal branch instruction causin~ the execution of the
new ,~r tar~et instru,tion sequence. However, this c~nditional
bran,-h instruction provides for the saving of the next address
,~f the old sequen,:e. As illustrated in Fi~ure 4, the f,~urth
instructi,~n after the unconditional bran~h instructic~n 7~13,
instructi,~n 7016, ,:ontains the end instru,tion micrl~-order.
Then the next ~llowin~ instrL~ction 7017 i5 the ~irst
instru,:ti,~n of the new sequence. ~ather than three, nl~
c,peration instructions in the unc~nditi.:,nal instruction bran,h
sequence, ,~ne of the instructions~ 71~15, i5 a ,:onditil~nal
bran,h instru,_tic,rl of the type ill~strated in Fir~ure 6. In
additiorl, instru,-tions 7013 and 7014 can be part ~f a
microinstru.:tion sequence implementing ~ macroinstructi~n. It
will be .-lear that the situation with respe.:t to the ,..,:,nditi,:,n
will n~JW be reversed~ the un,:c,ndlti,:,nal branch instru,:tic~rl
,au~inl~ the p,~tential new instrul:tic~n sequen,:e to be the a,:tive
instru,tiw~ sequenc:e. H,~wever~ should the relatively rare
situati,~n~ where the ori~inal sequenl:e was to be l:l~ntinued, be
identified by the cc)rlditic~n~l branch instructic,n~ the address
,~f that instru,:tion was ~aved in instruction 701~. Also when
the ~ri~inal instr~ ti,~n sequence is to be continued, the
1~
'
.: ~ , ~, . : .
`
~28~
~J ~_J 7~Er~J4
results ,3f the exe.:uted new sequen~-e instruction~, 7017, 7018
and 701g, will not be used.
Referrin~ ne~t t-, FiSure 8a, a blo7k diac~ram ~f the
apparatus exec~uting a ,onditional bran-h ma-rc~instructi-,n i6
sh4wn. The macr"instruction~s) are applied t4 instructi-~n
subunit ~1~ Ea,-h ma,-r,3instruction is decclded and the re5ultincl
address sic~nals, implementing the macroinstru--til~n, are applied
t,3 ,_ontrol unit 3~. ~ased ,~n the applied adr~ress signals,
mi,:ro--ode :~ntrol si~nals from control unit 3~ are applied to
~; the e~:e,-uti~,n subunit 33, the ~:ache m~3m.:.ry subunit ~4 and the
conditi-3nal bran.:h logi.: 81. C~ndlti,3nal bran.:h lo~i, 81 is
implemented to re.-eive ccndition signals from the executi,-,r.
subunit ~--, and, In resp-,nse t-~ the .-c~ndition si~nals and the
1~ applied mi,~r~:ode .:.:.ntr.~l signals, provide ,3r~e 4f two output
sic~nals. The mi.-r.:c.,de cc~ntrol sic~nals cause the e~ecution
subunit 33 tc, process data sir~nals and t.~ produ,e c,:.ndition
signal~ that are applieci to t~le .:nditi-,nal branch logic 81. As
a result 3f the applied c~-,ndition si~nals ~nd the mierc":~de
,-ontrol si~nals, a resultin3 c,utput si~nal (.,:,r sic3nals~ is
c~enerateci from the conditional bran,:h loc3ic unit 81. In the
¦ present inventi,:ln, when the c,3nditi~n is true ~i.e. the bran,:h
I su~:ceecis), a esic3nal ie~ applied to a selectec~ pc~rtion of a
J, mi,:r,:,trap lclc~il: unit 8;~ When the condition is false ~:i.e~ the
bran,h fai.ls), sic~nals are applied tc. the ,-a,:he memory subunit
34 that ,:ause the fetlh ~peration~ initiated by the ,~,~ntrol
unit ~ in response to signals from the instructic,n sub unit
31, t,~ be ab~rted.
Referrin~ to Fic~ure 8b, the result ,~f the applicati,3n of a
~5
' ' ' ' ' '
~_J DEI_6~4
si~nal to the mi~:rotrap logi~:, i.e. the bran,:h succeeds, is
shown. The mi~:ro'rap logie unit 82 senris a ~lob~l trap signal
to the instruction subunit 31, the execution subunit 33, the
~ache cubunit ~ and the cc,ntrol unit ~ The result ~,f the
global trap si~nal on the instru,:tion subunit 31, the execution
subunit 3:~1 and the ,-actle memory subunit :~ is to ~bort the
results of the mi,-r,~instru~:tions for whi~:h exeeuti~n was
initiated after the ~-onditi,~nal br~ncll mi~roinstructi~n. The
ef fel-t ,~f t~le ~lobal trap si~nal on the control unit 3~ i5 to
,ause an address3 ~trap ve.-t~r?, resultin~ fr,~m the "ccndition
is true" si~nal bein~ appl ied t,~ the mierotrap loyi,- unit 8~,
fr.~m the mi~~r~trap l.-.~i.- to be used by the c~,ntr~l unit 3::~. The
result ,~f the trap ve.-tor is~ inter alia, t.~ provide a trap
rele~se signal t~ the mi.-r~tr~ap lo~ie unit 8~ that terminates
the routine bein~ exe- uted by the mi~:rotrap l-~il unit 8~ as
resul t of the appl i eat i .~n of the "condi t i on i s true" si ~nal ,.
. Operati,:,n of the Preferred Embodiment
The delays inv,-,lved in the c~r\diti,-,nal bran~h instrul_ti~n
are two-fold. First, the exe,-uti,~n of the appropriate
instru,-ti.3n sequen~e ~!annot b~ ur)dertal:en with certainty untll
a determinati,~n ha been made ai t,~ the wtlether the eonditi~n
is true -~r false. E3econd~ even on-:e the determination ha5 be~en
made with respe,:t tl~ the ful fillment of the e ondition~ ttle
various segme3nts .f the instru~ti~n must be proces~;ed, before
the advantages ,~f the rapid exe~ution by a pro,:ess-~r plpeline
.-an be realiz~d. T~ av~id ttle delays that are involved with a
,:onditional instru-:tion in a pipeline type data pro-:es~in~
'' '
':.
~285~r;7
/ I~Ek~G~
envir,~ment, tlle present invention :ate~ori~es the c.~nditi-~nal
branch instru.-ti~n into two ~roups.
In t~e first gr..up of conditi.~nal bran-h instru.-ti.~ns, the
mcst prc,bable result ~f the testin~ of the condition i5
unkn~wn. The inventicn pro-:esses this type of ,:onditi.~nal
bran.:h instructi4n by fcrcing the next instructic~n to be a
retrieval ,~f t~1e data at the address th~t wculd be the result
of an a-:tual bran.~l in the prcyram a5 a result .3~ the
instru.:ti.~n. ~ecause this retrieval takes a plurality l~f
micr.-instru~tion .-y,:les to execute, the instructi-~n~ that are
executed in this time period are in~tru.-ti.~ns fr~m the ~ri~ginal
sequen-_e that would be pr-~.-essed if a program bran.-h did not
tak:e pla-:e as a result ~f the c-~nditicn testin~. Thus, when
the result .~f testing the c.~ndition is established, if the
condition is false, i.e. the ~ri~inal pr-~ram sequen-e is to be
cc.ntinued, then the data in the prccess .~f bein~ retrieved is
.-an--elled and the original instru--tion sequence, already in
exe--u~icn, is c.~ntirlL~ed. Indeed, acc---rdin~ t.~ ttle
implementati~n in Fi~ure 4, only one micr.~instru-tion l-ycle is
used. If, on the ~ther lland, the conditiorl is true and the new
sequen.:e cf instru:ti-:ns is to be executed, tilen the pr-~cess ~f
retrievin~ tlle flrst si~nal gr.~up .-f the new instruction
sequen.:e ha~ been in pr-~l~ress f-~r three mi-:r-~instru-:til~n
cyclesr and the executiorl of this instru-tion sequence ha~
improved with respe-:t t.~ waitin~ ~or result cf the :.~nditi-~n
test prior to furt~ler processor activity~ It will be clear
that, if the :-~dition is true, the results ~f the instru-ti~n
executi.~n sequen-~e o~ the cri~inal prc~r~m sequence tak.in~
17
~28S~
~ J DE~ 4
pla,:e during the testing .3f the :onditi,~n h~5 be,:ome irrelevant
and must be dis~-arded. Thus, it will be clear that the speed
3f the -onditional branch instruction ~3f the present inventi,3n
uses only one system llock: cycle when the -ondition is false,
and yet e~ecutes the instruction as fast a5 an un.~onditi,~nal
bran-:h instructi4n whèn the conditi-3n is true~
Wit~l respe-:t t,3 t~le sec4nd ~r~up ~f instruCti~3ns
illustrated in FigL~re 7, upon identifi-:ati~n of a conditi-3nal
branch instructi-~n ass-3--iated with t~lis se-:-~nd ~roup, the
assumption i5 made that the branch to the new instru-~tion
sequen.e is the most probabl~ result 3f the testing :f the
c.~nditi,3n~ A~ a result l~f this assumpti,~n, the cc,ndition~l
bran._h is interpreted as an unl-,~nditional bran~h instructi,~n
and the activity ne,-essary for the perf,-.rmin~ the br~nchin~
operati-3n is exe,-uted even thou~h the condition has not been
tested. After the new instructic,n sequence has been prepared
f,3r exe,-uti.3n, then the instru--ti-~n testin~ the .-onditi.~n is
exec~lted. However, the ,-ndition te~tin~ pr,~,:edure is now
reversed, the ~~~,nditil:~n f,~r ,,~ntinuati,~n has now be,-,~me the
c,:,ndition fnr e~;e,-uti,3n l~f a new instru,-ti,~n sequence even
t~ u~h that instructi"n sequenle i~ in fact the ,3ri~inal
instruction sequen~e. Tlle executi,~n clf the c,~nditic~nal branch
lnstru,-ti,3n tah:es pla,:e in the same manner a~; the exe,:util3n c~f
the conditi,-,nal bran,.h instru,tion illue.trated in Fi~ure 6. It
will be lear that the assumpti-3n that the bran-:h is the m,3st
probable res~lt of the tee.tinr~ of the condition must in fa~t be
true in a maj~rity ~f cases. This result arises be,-ause, as
will be apparent fr,~m Fi~ure 7, two alterations in the
lB
~, : .... ~ . . .
'
, ~ . .
~2~35~7
~_J DEI_6~4
instru.:ti-~n sequen,:e must take pla,:e when the ~ri~inal
c..nditicn i5 false. The ,-onditi~nal bran.-h instru~ti--.n
impr-~ves the executi-~n of the instru~:ti~n by forcin~ an
un.:,3nditic,nal branch micro-order to be e~e,:uted as s-~on as the
se-ond ~bran-:h) address i5 known and by usin~ the previou~ly
de~cribed -onditi~nal branch instructi~n to minimi2e the imp~ct
of the ~relatively unlikely~ return to the ori~inal instru~-tion
sequence.
The fore~ing descripti!3n i5 incl~lded to illustrate the
,~perati.~n ~f the preferred emb~diment and is n-~t meant to limit
the sc.-.pe .3f the invention. The sc.~pe of the invention is to
be limited ~nly by the followin~ ,-laims. From the f~re~,~in~
des,ripti~n, many variations will be apparent tcl th,~,se sk:illed
in the art that wlluld yet be en,:ompassed by the ~pirit and
sc~pe ,~f the inventi~n.
:'
~ : -
'
