United States Patent [19J
`Porten et al.
`
`[54] SYSTEM FOR MONITORING AN
`EXECUTION PIPELINE UTILIZING AN
`ADDRESS PIPELINE IN PARALLEL WITH
`THE EXECUTION PIPELINE
`
`[75]
`
`Inventors: Joshua Porten, Palo Alto, Calif.; Amir
`Bar-Niv, Givatayim, Israel
`
`[73] Assignee: National Semiconductor Corporation,
`Santa Clara, Calif.
`
`[ *] Notice:
`
`This patent issued on a continued pros(cid:173)
`ecution application filed under 37 CFR
`1.53( d), and is subject to the twenty year
`patent term provisions of 35 U.S.C.
`154(a)(2).
`
`[21] Appl. No.: 08/886,520
`
`[22] Filed:
`
`Jul. 1, 1997
`
`Int. Cl.6
`........................................................ G06F 9/30
`[51]
`[52] U.S. Cl. ................................ 712/200; 712/42; 714/38
`[58] Field of Search ..................................... 395/376, 377,
`395/800.41, 800.42; 712/200, 201, 41, 42;
`714/38, 45
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US005996059A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,996,059
`*Nov. 30, 1999
`
`5,572,690
`5,600,848
`5,604,878
`5,682,493
`5,704,054
`
`11/1996 Molnar et a!. .......................... 395/376
`2/1997 Sproull et a!. ..................... 395/800.42
`2/1997 Colwell et a!.
`.................... 395/800.42
`10/1997 Yung eta!. ............................. 395/393
`12/1997 Bhattacharya .. ... ... ... .... ... ... ... .. 395/388
`
`Primary Examiner-Richard L. Ellis
`Attorney, Agent, or Firm---Limbach & Limbach, LLP
`
`[57]
`
`ABSTRACT
`
`An address pipeline includes a sequence of registers for
`storing the memory addresses of instructions currently being
`processed within the different stages of an execution pipe(cid:173)
`line. In parallel with the execution pipeline, the address
`pipeline advances the corresponding memory addresses as
`the instructions are advanced through the execution pipeline.
`Address pipelining allows the programmer of a pipelined
`processor to understand the otherwise hidden operation of a
`pipelined processor by giving the programmer means to
`track instructions through the pipeline. In addition, the
`address pipeline includes an instruction status register for
`indicating whether an instruction at any given stage of the
`pipeline has been executed and a program counter address
`breakpoint register for storing the address of the instruction
`that actually triggers a breakpoint.
`
`5,564,028 10/1996 Swoboda et a!. ....................... 395/568
`
`17 Claims, 4 Drawing Sheets
`
`Data Bus
`
`Address Bus
`
`'-10
`
`'-20
`
`I
`I
`I
`I
`
`: l Operand
`
`Stage
`
`'-so
`
`I
`I
`
`'-60
`
`r - - - --- -;_;o
`L
`I
`
`Instruction
`Stage
`
`: l
`
`I
`I
`I
`I
`
`,.1o
`l
`II
`L_ _______ J
`
`i I Execution
`
`Stage
`
`110-...
`
`300
`
`Pipeline
`Control
`
`Advance_Pipe
`
`I f-'
`
`I
`1
`I
`I
`I
`I
`
`r - - - ----,40
`I .J Instruction
`Address
`1 "I Register
`I 80-'
`I
`I
`I
`1.1 Operand
`Add!ess
`1•
`1
`Register
`1
`I
`90.1
`I
`I 100\
`I J Execute
`Address
`1 ·1 Register
`L---!---~
`
`I:
`
`I
`I
`
`I
`
`I:
`
`Address Select
`
`"' 120
`
`.) Y.
`
`190
`
`J60 u?o j80
`j <8
`&.1 <.>
`~
`<ol
`
`1l.
`0
`
`I Instructions
`
`Status
`Register
`
`1-'130
`I
`
`I PCABP
`
`Register
`
`140
`
`16
`
`16
`
`16
`
`----.
`
`~50
`
`Mux
`
`Registers
`Read Bus
`
`~
`
`16
`
`3
`
`LJ
`
`FireEye - Exhibit 1028 Page 1
`
`

`
`•
`\Jl
`d •
`
`Cache ~
`1
`
`:
`
`I
`
`-----------------------------------~
`
`Instruction Pipe
`
`(PRIOR ART)
`
`FIG.l
`
`Memory
`Cache And
`Flow From
`Instruction
`
`'--3
`
`'-4
`
`--------r--~~---
`I
`I
`I
`I
`I
`I
`
`Register
`14~~---+----1 Holding
`
`A
`
`B
`
`Stage
`
`Stage
`
`1...,
`
`Unit
`
`Execution
`
`\..._
`8
`
`.,~
`
`'1
`
`~
`
`rr
`
`""
`
`Unit
`
`Control
`
`Sequencer
`
`'-
`7
`
`'---
`6
`
`~-----------------
`
`'--5
`
`c
`Stage
`
`FireEye - Exhibit 1028 Page 2
`
`

`
`U.S. Patent
`
`Nov. 30, 1999
`
`Sheet 2 of 4
`
`5,996,059
`
`------~------------------------~~~10--- DruaBus
`Address Bus
`- - - - - - - - - -... --..-'-.2•0-
`
`~ -
`
`-
`
`, lr -
`-
`-
`Instruction
`s
`tage
`
`'-so
`
`, lr -
`- ~0
`r -
`-
`-
`. _____ _J1~ Instruction
`""""'--
`....: 1
`Address
`1 Register
`so.l
`
`I
`1
`I
`I
`I
`I
`I
`I
`, r
`I .---_,..I.r __ ~
`I
`I Operand
`I
`Operand
`_,.
`Stage
`14-;--------4...,_-....,.1 ~ Address
`I
`Register
`I '------1t---r--__.~
`I
`90.)
`I
`\.60
`I
`I
`I
`I
`I
`I
`I
`Execution
`I
`Stage
`I
`L-------...1
`110~
`
`-
`
`-
`
`,
`
`-40
`
`j--1
`I
`1
`
`1
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`1
`
`, 1r
`1 00'\
`Execute
`Address
`Register
`L---.J.---...1
`
`1 ..
`
`1
`
`150
`
`Mux
`
`Registers
`Read Bus
`
`I~
`
`..
`
`..
`
`16
`
`..
`
`16
`
`...
`-...
`
`16
`
`I
`
`0..
`
`Pipeline
`Control
`
`Advance_Pipe
`
`,~r
`
`Address Select
`J
`190
`
`.. 1
`•
`
`,
`
`"'
`
`Mux
`
`/
`
`-----e;o
`T
`
`140
`~
`
`PCABP
`Register
`
`T
`
`~ c - ~ 0.
`
`0
`
`~~-~·lr---L.......,...J130
`Instructions
`Status
`Register
`
`FIG. 2
`
`FireEye - Exhibit 1028 Page 3
`
`

`
`U.S. Patent
`
`Nov. 30, 1999
`
`Sheet 3 of 4
`
`5,996,059
`
`\.:205
`
`'C220
`
`Data Bus
`
`Address Bus
`
`r -
`
`-
`
`- 1 lr -
`
`-
`
`-
`
`-;_}30
`
`Fetch
`Stage
`
`l '"245
`
`Instruction
`Stage
`
`~ '250
`
`oraerand
`Sage
`
`.I
`I
`I
`I
`....1
`... I
`I
`I
`.I
`I
`~260 I
`,...270 I
`I
`
`~·
`Execution
`Stage
`
`I
`L - - - - - - - . .1
`
`r---1.,---'V40
`I
`Fetch
`I Address
`I Register
`I 275./
`-.I
`~
`I
`Instruction
`I
`Address
`I
`Register
`I 280-' •
`+
`I
`I Operand
`I Address
`Register
`I 29QJ
`.I.
`I 300, +
`
`I
`
`Execute
`Address
`Register
`I
`L ___
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`- - - .J
`
`16 .. r--1
`
`..
`
`16 ...
`..
`,
`
`16 ...
`..
`,
`
`16 ..
`..
`
`050
`
`Mux
`
`Registers
`Read Bus
`...
`\410-,.
`
`I
`
`310,
`
`~00
`
`Pipeline
`Control
`
`Advance_ Pipe
`
`Address Select
`
`39c!
`
`35t
`~60 070 J80
`..
`-
`:><:
`~ :><:
`~ ~
`~
`..c
`()
`~
`~
`~ = 0 ~
`c.
`......
`
`t.l.o
`
`()
`
`J30
`
`lr
`Instructions
`Status
`Rep;ister
`
`I.
`
`~·~r~rt
`
`:=Y20
`
`M
`
`342._
`
`1 "
`PCABP
`Register
`
`16
`
`..
`...
`~
`, ~
`
`FIG. 3
`
`FireEye - Exhibit 1028 Page 4
`
`

`
`U.S. Patent
`
`Nov. 30, 1999
`
`Sheet 4 of 4
`
`5,996,059
`
`------~----------------------~~~20•5-- DmaBus
`------------------•--·~·2•2•0- Address Bus
`
`r -
`
`-
`
`-
`
`, 1r -
`
`-
`
`-
`
`'r}30
`
`Fetch
`Stage
`
`--l '"245
`
`.....1..
`..,...._----.
`I
`:
`
`Instruction
`Stage
`
`J..
`r
`
`"" "250
`oraerand
`S age
`
`:
`....L
`1-4~-__.
`
`,
`
`(""500
`
`FIFO
`
`~260 I
`,-270 I
`I
`
`'lr
`
`Execution
`Stage
`____ ___ .J
`
`~00
`
`Pipeline
`Control
`
`Advance_Pipe
`
`Address Select
`
`39cl
`
`3St
`
`,...........:'~'~.....1...__,:![__,, }30
`Instructions
`~
`Status
`Register
`
`l l
`
`j50
`
`16 ..
`
`,.
`
`I
`
`16 ..
`r
`
`1,6 ..
`r
`
`16 ...
`'
`
`Mux
`
`Registers
`Read Bus
`
`I
`
`34t_
`
`' lr
`
`PCABP
`Register
`
`.. ..
`
`16
`
`~
`
`L...-.J
`
`FIG. 4
`
`FireEye - Exhibit 1028 Page 5
`
`

`
`5,996,059
`
`1
`SYSTEM FOR MONITORING AN
`EXECUTION PIPELINE UTILIZING AN
`ADDRESS PIPELINE IN PARALLEL WITH
`THE EXECUTION PIPELINE
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates to computer processors and
`in particular, to pipelined processors and machines. More
`particularly the present invention relates to a method and
`apparatus for observing and understanding the operational
`characteristics of different pipelined machines to aid in
`optimizing their use.
`2. Description of the Related Art
`A pipe lined machine is, for example, a computer proces(cid:173)
`sor in which instruction execution takes place in a series of
`units or stages, arranged so that several units can be simul(cid:173)
`taneously processing the appropriate parts of several instruc(cid:173)
`tions. Two or more of a pipelined machine's stages, such as
`prefetch, fetch, decode, execute, and write-back, can each
`simultaneously operate on a different instruction. In other
`words, pipelining is a method of fetching and decoding
`instructions (preprocessing) in which, at any given time,
`several program instructions are in various stages of being
`fetched, decoded, or executed. Ideally, pipelining speeds
`execution time by ensuring that the machine does not have
`to wait for instructions when execution of one instruction is
`completed, the next is ready and waiting. The DECchip
`21064 (also called the DEC Alpha or the DEC Alpha AXP)
`manufactured by Digital Equipment Corporation of Massa(cid:173)
`chusetts is an example of a pipelined machine.
`More particularly, a typical pipeline, like the one found in
`the DEC Alpha, will have a number of stages that execute
`different phases of an instruction in parallel. For example, a
`pipeline may have four stages. The first stage fetches a new
`instruction, the second decodes the previously fetched
`instruction, the third fetches any operands that may be
`required by the previously decoded instruction and finally,
`the fourth stage executes the instruction after it has been
`fetched, decoded and all its operands have been fetched.
`Thus, the four pipeline stages, in this example, are: fetch,
`decode, operand fetch and execute. This pipeline is called an
`execution pipeline because it is responsible for executing the
`programmer's code. General purpose computer processor 45
`pipelines have been mentioned, but it should be understood
`that any instruction based machine, such as a digital signal
`processor (DSP) or a disk controller, can be pipelined.
`Another example of a prior art processor pipeline is the
`Motorola 68020 Microprocessor manufactured by Motorola, 50
`Inc. of Schaumburg, Ill. This processor includes an instruc(cid:173)
`tion fetch and decode unit as shown in FIG. 1. This unit
`provides the mechanism for simultaneous fetch, decode and
`execution of instructions. The instruction pipeline 2 includes
`several stages 3, 4, 5, that instructions move through as they 55
`are processed. The pipeline 2 is fed by the cache holding
`register 1 which is merely a buffer between memory and the
`pipeline 2. The sequencer 6 and the control unit 7 drive the
`processor including the pipeline 2 in response to the values
`contained in the various pipeline stages 3, 4, 5. The execu- 60
`tion unit 8 is essentially the computational element of the
`processor. At a given time, the processor may be working on
`four words of an instruction or four separate word-size
`instructions.
`For instance, the execution unit 8 might contain the results
`of an instruction that has just been executed, while Stage A
`3 may be providing the next instruction to be processed.
`
`5
`
`2
`may be providing data needed to complete the
`
`Stage B 4
`current instruction, such as an immediate operand. Finally,
`Stage C 5 might contain a fully decoded and validated
`instruction ready for execution. The objective of this part of
`the pipe lined architecture is to eliminate the amount of time
`required in an instruction's execution that represents the
`fetch and decode operations. This can be achieved because
`these operations are done in parallel while the previous
`instruction is still being executed. The desired result of this
`10 instruction prefetch and decoding is faster execution of the
`program.
`Ideally, a set of instructions executing on a pipelined
`machine will function identically to, and run faster than, the
`same series of instructions executing on a non-pipelined
`15 machine. A programmer should be able to expect that if his
`code first specifies that a certain register is to be read and
`then the same register is to be written in the next instruction,
`that is the order that the pipelined machine will execute his
`instructions. Likewise, if he reverses the order of the
`20 instructions, he should be able to expect that the register will
`first be written and then read. The programmer expects the
`pipeline to perform his instructions in the sequence he
`specifies just like a non-pipelined machine would. If this is
`the case, the pipelining is said to be transparent because it
`25 does not introduce any undesirable or unpredictable effects
`into the execution of the instructions. In other words, the
`only difference between a non-pipelined machine and a
`transparently pipelined machine is that the pipelined
`machine completes instruction execution sooner and thus,
`30 gets the job done faster.
`Unfortunately, pipelines are not transparent. The reality is
`that they have side effects and these side effects can cause
`anomalous results. For example, if two different instruction
`sequences, i.e. ABC and ACE, logically do the same thing,
`35 but when executed on a pipelined machine have different
`results, then there is a pipeline side effect. This is a problem
`because it becomes difficult for a programmer to know what
`to expect when computing a value. Programmers must be
`able to consistently determine the results of their calcula-
`40 tions and to know when these results are available for use in
`order to effectively program a machine. If the pipeline
`scrambles the order in which the programmer expects a
`value to be computed, the program is likely not to function
`even if the value would ultimately be computed correctly.
`Side effects can be even more subtle and hard to detect
`than execution order problems. For instance, a pipelined
`DSP machine will typically perform multiple operations per
`instruction. A DSP that uses an address unit, which includes
`registers and an arithmetic logic unit (ALU), to calculate the
`address from where the next operand is to be loaded, is likely
`to have some side effects. The address unit's registers can be
`accessed directly with an instruction or indirectly with an
`increment address pointer instruction. If an instruction such
`as load accumulator (LACC) with a certain memory operand
`is to be performed, the operand is fetched from memory and
`then loaded into the accumulator. But at the same time, on
`the same instruction line, the DSP can also advance an
`address pointer, add an offset to the address pointer, and
`perform various other functions. With all of these different
`functions of the same compound instruction, it is possible
`that as a result of a processor design flaw, at least two of the
`functions will take place at the same stage of the pipeline.
`Thus, such a compound instruction could cause an undefined
`result when two functions access the same register during
`65 the same stage. Unless this particular scenario has been
`documented, the programmer can only observe the final
`effect of the contention and wonder at how it was achieved.
`
`FireEye - Exhibit 1028 Page 6
`
`

`
`5,996,059
`
`3
`Prior art pipelines are black boxes in which the order of
`execution of different parts of an instruction is hidden and
`thus, there are side effects which can only be understood if
`documented or by trial and error experience.
`Another difficult situation that results in side effects
`occurs when two different instructions, for example, "incre(cid:173)
`ment address register one" and "write a new value to address
`register one", follow one another. A programmer unaware of
`side effects, would expect that this would not be a problem
`because even though both instructions access the same
`register, they are written to be performed sequentially.
`However, since "increment address register one" is executed
`in a different stage of the pipeline than "write a new value
`to address register one" it could very well happen that the
`two instructions try to access register one at the same time
`causing a contention with undefined consequences.
`Unfortunately, due to the complexity of pipe lined machines,
`it is very difficult and costly to fully document them. The
`number of different permutations of instruction and data
`sequences that may arise is vast. Thus, it is not surprising
`that many side effects are usually not documented. In fact,
`frequently, the nature and complete impact of a pipelining
`side effect may not be fully understood by the designers of
`the machine, much less by the users who must program the
`machine.
`It can be difficult to detect pipeline side effects because
`they often occur after the fact, as a result of many things
`happening at once. In other words, each stage of the pipeline
`is simultaneously performing a different function and the
`consequence of a conflict between two stages might not
`become apparent until several additional instructions have
`passed through the pipeline. Prior art pipelined machines do
`not provide any means to look into the stages of the pipeline
`to determine how different instructions are handled at the
`different pipeline stages. Even if a prior art pipelined
`machine was equipped with a status register, it would be
`nearly impossible to determine at what point in time, which
`portion, of which instruction, in which stage of the pipeline,
`caused a particular status. What is needed then, is a means
`to simultaneously trace the progress and effect of several
`instructions as they move through the pipeline so that side
`effects can be identified and their impact can be accurately
`determined.
`For the pipeline to operate correctly, only the actual
`instructions that are to be executed (or some form of the
`instructions) need to be stored in each of the different
`pipeline stages. The original memory addresses of the
`instructions are not required for the proper functioning of the
`pipeline. However, it is the instruction's address that can be
`used to provide the information required to identify and 50
`understand a pipeline side effect. If it was known which
`instruction was being executed at each phase of the pipeline,
`a complete picture of the pipeline's operation could be
`deduced. This information could then be used by the pro(cid:173)
`cessor's debugger to provide an accurate picture of how any 55
`instruction sequence is handled as it moves through the
`pipeline. The effects of each stage on each instruction could
`be tracked whether by single stepping through a sequence or
`by setting breakpoints. What is needed therefore, is a means
`to provide the programmer with a view into the pipeline's 60
`operation. More particularly, what is needed is a means to
`ascertain which instruction is in which stage of the pipeline
`at any given time and whether the instructions have
`executed. Further, what is needed is status regarding the
`pipeline after a breakpoint has been reached and an indica- 65
`tion of which instruction caused the processor to reach the
`breakpoint.
`
`4
`Beyond debugging a program to avoid any negative or
`undesired consequences of side effects, programs can be
`optimized so as to exploit any opportunities that side effects
`might provide. This is particularly true for applications that
`5 have time or space critical requirements. In other words, if
`a side effect is fully understood, it can be used to reduce the
`number of instructions required to perform a task, or reduce
`the amount of time required for performing a task.
`Many digital signal processing (DSP) applications are
`10 implemented in software, running on a programmable DSP,
`much like a general purpose processor. However, DSP
`applications must run with real time constraints, as they
`must deal with real life signals, such as speech, vision,
`process control, etc. As the applications become more com-
`15 plex their performance requirements increase. One of the
`main features of programmable DSPs is their pipeline. The
`pipeline enables a DSP to achieve high throughput, execut(cid:173)
`ing complex (multiple) operations at the same rate as the
`processor's clock. For example, a 40 MHz DSP can execute
`20 40 million MAC (multiply and accumulate) instructions per
`second.
`One of the programmer's challenges is to write code that
`optimally uses the unique operational characteristics of the
`pipeline in order to gain the benefits of the DSP' s maximum
`25 possible performance. This task is complicated by the pres(cid:173)
`ence of pipeline side effects. As described above, a pipe(cid:173)
`line's operation is not always transparent to the programmer
`in terms of the code he writes. Further, as with the pipeline
`for a general purpose processor, the DSP pipeline's opera-
`30 tion is not visible to the DSP programmer (i.e. there are no
`registers that provide information on the pipeline's
`operation). Only its effects on the code are observable. In
`addition, as with general purpose pipelined processors, the
`pipeline for a DSP is a very complex engine and is therefore
`35 very difficult to fully document because there are many
`different situations that may arise, depending on a specific
`sequence of instructions and data.
`What is needed is a means for the designer of a program-
`40 mable DSP to help the programmer better understand the
`pipeline operation and enable him to optimize his code for
`a given application. It should be understood that although
`performance is of particular interest to DSP and real time
`programmers, the present invention described below is
`45 applicable to any pipelined machine or processor. In
`addition, providing visibility into the pipeline may also
`assist the processor's architects and designers to debug and
`improve the pipeline's operation.
`
`SUMMARY OF THE INVENTION
`
`The above and other objects of the invention are achieved
`by the present invention of an address pipeline in a pipelined
`machine. The present invention provides a means for the
`programmer to observe a pipeline's operation and obtain
`information useful for optimizing code accordingly by mak(cid:173)
`ing the operation of the pipeline visible. It also enables
`processor designers to debug and improve the pipeline
`design. The present invention provides an address pipeline
`that operates in parallel to the main execution pipeline, a
`register that indicates which instruction from within the
`pipeline triggered a breakpoint, and a status register that
`indicates whether or not each of the execution pipeline
`phases has been executed.
`In accordance with a first embodiment of the present
`invention, an address pipeline in the form of a secondary
`pipeline structure in parallel with the execution pipeline, is
`provided to sequentially store the memory addresses of
`
`FireEye - Exhibit 1028 Page 7
`
`

`
`5,996,059
`
`5
`instructions as they move through the different stages of a
`pipeline. The address pipeline includes one register for each
`corresponding stage of the execution pipeline. The execu(cid:173)
`tion pipeline control signal used to trigger the advance of
`instructions through the execution pipeline is used to also 5
`advance corresponding addresses through the address pipe(cid:173)
`line. Pipeline control logic generates a status signal for each
`pipeline stage which indicates whether the instruction cur(cid:173)
`rently in a particular stage has been executed. The present
`invention includes an instructions status register that stores 10
`the present state of each stage's status signal. Finally, the
`present invention includes a register for storing the memory
`address of the instruction that triggered a breakpoint.
`In accordance with a second embodiment of the present
`invention, an addressable, first-in-first-out (FIFO) shift reg(cid:173)
`ister file is provided to sequentially store the memory
`addresses of instructions as they move through the different
`stages of a pipeline. The pipeline control signal used to
`trigger the advance of instructions through the pipeline is
`also used to clock the corresponding addresses through the
`shift register file. As with the first embodiment, pipeline
`control logic generates and stores a status signal for each
`pipeline stage which indicates whether the instruction cur(cid:173)
`rently in a particular stage has been executed. Finally, this
`second embodiment of the present invention also includes a
`register for storing the memory address of the instruction
`that triggered a breakpoint.
`These and other features and advantages of the present
`invention will be understood upon consideration of the
`following detailed description of the invention and the
`accompanying drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram depicting a prior art pipelined 35
`processor.
`FIG. 2 is a block diagram depicting a three-stage pipe(cid:173)
`lined processor, including a first embodiment of an address
`pipeline, according to the present invention.
`FIG. 3 is a block diagram depicting a four-stage pipelined
`processor, including a second embodiment of an address
`pipeline, according to the present invention.
`FIG. 4 is a block diagram depicting a pipelined processor,
`including a third embodiment of an address pipeline, accord(cid:173)
`ing to the present invention.
`
`6
`execution stage 70. Although the pictured embodiment
`labels the various execution stages with particular functional
`names, it should be understood that the various stages will
`depend upon the particular pipeline processor that is to be
`enhanced by the present invention. Likewise, the particular
`number of stages will vary from pipeline implementation to
`implementation and, as will be seen in FIG. 3 and the
`accompanying text below, the address pipeline of the present
`invention is scaleable to accommodate any number of pipe-
`line stages.
`The address pipeline 40 includes an instruction address
`register 80 which corresponds to the instruction stage 50 of
`the execution pipeline 30, an operand address register 90
`which corresponds to the operand stage 60 of the execution
`pipeline 30, and an execute address register 100 which
`15 corresponds to the execution stage 70 of the execution
`pipeline 30. As instructions advance through the execution
`pipeline 30, their corresponding memory addresses advance
`through the corresponding registers 80, 90, 100 of the
`address pipeline 40. That is to say, an instruction read from
`20 the data bus 10 will move from the instruction stage 50 to the
`operand stage 60 and then from the operand stage 60 to the
`execution stage 70 as it is processed. At the same time, the
`memory address of the instruction will be read from the
`address bus 20 to the instruction address register 80, and
`25 when the instruction moves from the instruction stage 50 to
`the operand stage 60, the memory address will be moved
`from the instruction address register 80 to the operand
`address register 90. Likewise, when the instruction is moved
`from the operand stage 60 to the execution stage 70, the
`30 memory address will be advanced from the operand address
`register 90 to the execute address register 100. The registers
`80, 90, 100 of the address pipeline 40 are wide enough to
`accommodate the size of the system's memory addressing
`requirements. A sixteen bit wide address pipeline 40 is
`shown as an example of a typical width.
`The Advance_Pipe signal200, generated by the pipeline
`controlllO, is the signal used to indicate that the instructions
`are to be moved to the next stage of the execution pipeline
`30. This signal, or its functional equivalent, is a generic
`signal found in all pipeline systems. It is asserted when the
`40 execution pipeline 30 has completed all of its operations in
`the current cycle for all of the stages 50, 60, 70 and the
`instructions can be advanced. In other words, the Advance_
`Pipe signal 200 is asserted when the instruction in the
`execute stage 70 has been executed, the operand required in
`45 the operand stage 60 has been read, and the instruction in the
`instruction stage 50 has been decoded. The present invention
`uses the Advance_Pipe signal 200 to trigger the advance(cid:173)
`ment of the memory addresses through the address pipeline
`40 as well as for triggering the advancement of instructions
`50 through the execution pipeline 30. Thus, the Advance_Pipe
`signal200 is fed to each of the address registers 80, 90, 100,
`as well as each stage 50, 60, 60 of the execution pipeline 30.
`In this way, the memory addresses in each of the address
`registers 80, 90, 100 of the address pipeline 40 are kept in
`55 synchronization with the instructions in each of the corre(cid:173)
`sponding execution pipeline stages 50, 60, 70.
`Another aspect of the invention provides for reading the
`memory addresses being transferred between the various
`address registers. A multiplexor 150 allows addressable
`60 access to the values being transferred between the address
`registers. The user or a debugger system can access the
`desired information via the multiplexor 150 which transfers
`the selected address register value onto the registers read bus
`210. In addition to the memory addresses, the present
`65 invention also makes the status of each stage 50, 60, 70 of
`the execution pipeline 30 available via the instructions status
`register 130.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`The present invention provides a second pipeline, called
`an address pipeline, added in parallel to the execution
`pipeline of the processor. This address pipeline stores the
`addresses of the instructions that are currently in the pipe(cid:173)
`line. The address pipeline has the same number of stages as
`the execution pipeline and is advanced at the same time as
`the execution pipeline. Each stage of the address pipeline
`stores the memory address of the corresponding instruction
`in the execution pipeline. The address pipeline is readable so
`that a programmer (or debugger) may read out its values.
`Turning to FIG. 2, an illustration of a three stage pipeline
`30 system including an address pipeline 40 is depicted. The
`execution pipeline 30 reads instructions from the data bus
`10. At the same time, the address pipeline 40 reads the
`memory addresses of the instructions from the address bus
`20.
`The three stage execution pipeline 30 depicted in FIG. 2
`includes an instruction stage 50, an operand stage 60, and an
`
`FireEye - Exhibit 1028 Page 8
`
`

`
`5,996,059
`
`7
`A debugger enables the programmer to single step
`through his program or to set a breakpoint. The programmer
`may set a breakpoint at a certain instruction or he may
`specify a certain condition that will halt the processor's
`execution (e.g. break if address X has been accessed). In
`either case, the programmer will want to know when exactly
`did the breakpoint occur (i.e. which instruction actually
`triggered the breakpoint).
`If a breakpoint is set on a certain instruction, the processor
`will break when that instruction has reached the execution
`phase. However if a condition was set, the processor will
`break when that condition has been met. This may not be
`during the execution phase. Therefore, an additional register
`is needed that will store the memory address of the instruc(cid:173)
`tion that actually caused the processor to halt. This register 15
`is called a PCABP (program counter address breakpoint)
`register 140.
`Upon reaching a breakpoint, the pipeline control 110
`signals a multiplexor 120 via an Address_select signal190
`to select the stage that caused the breakpoint to be reached. 20
`If the instruction that caused the processor to halt is currently
`in the execution stage 70, then the PCABP register 140 will
`latch the content of the execute address register 100.
`Likewise, if the instruction that caused the processor to halt
`is currently in the operand stage 60, then the PCABP register 25
`140 will latch the content of the operand address register 90.
`If the instruction that caused the processor to halt is currently
`in the instruction stage 50, then the PCABP register 140 will
`latch the content of the instruction address register 80.
`In addition to knowing the memory address and current 30
`stage of the instruction that caused the processor to halt, the
`programmer may want to know whether each of the phases
`of the execution pipeline 30 succeeded in completing before
`the processor was halted. This is facilitated by a set of status
`signals 160, 170, 180, one per pipeline stage, that are 35
`generated by the pipeline controlllO. These signals indicate
`whether the corresponding stage 50, 60, 70 in the execution
`pipeline 30, completed execution. The state of the status
`signals 160, 170, 180 are stored in an instructions status
`register 130.
`In the embodiment of the present invention depicted in
`FIG. 2, the instructions status register 130 stores three bits.
`Each bit corresponds to an instructions status signal 160,
`170, 180 that indicates whether the corresponding phase of
`the execution pipeline 30 has been executed. The ExecEx 45
`signal180 indicates whether the instruction currently in the
`execute stage 70 has executed, the OperEx signal 170
`indicates whether the operand specified in the operand stage
`60 has been fetched, and the InstrEx signal indicates whether
`the instruction in the instruction stage 50 has been decoded. 50
`For example, assume there is a conditional break set on a
`read operation that has been triggered by an instruction
`currently in the operand stage 60. Further assume that within
`the same pipeline cycle (e.g. before the next Advance_Pipe
`signal 200 is asserte