WikiPatents - Community Patent Review
Create Free Account  |  License or Sell Your Patent  |  WikiPatents Marketplace  |  WikiPatents Blog
Username:  Password:  
    
Advanced Search
Method and apparatus for exception handling in pipeline processors having mismatched instruction pipeline depths    
United States Patent5193158   
Link to this pagehttp://www.wikipatents.com/5193158.html
Inventor(s)Kinney; Daryl F. (Hopkinton, MA); Drogaris; Anthony N. (Wellesley, MA); Mills; Christopher H. (Chelmsford, MA); Kahaiyan; Michael (East Bridgewater, MA); Manton; John (Marlboro, MA)
AbstractMethod and apparatus for sequentially executing a plurality of pipelined instruction words of a program in which each instruction has independently selectable execution cycle count latencies. After the occurrence of an exception, instructions are identified which began after the instruction that caused the exception, and which have completed execution before execution of the exception provoking instruction was inhibited. Detection of an exception causes the processor to inhibit further execution of the exception provoking instruction. Pending instructions, which have yet to complete their execution prior to the inhibition of the exception provoking instruction, are similarly inhibited from further execution. Subsequently, the exception is serviced and the exception inducing instruction is restarted for re-execution in the processor. Pending instructions are subsequently re-executed in the sequence of their occurrence at the time the exception provoking instruction caused the processor to inhibit further instruction execution. Completed instructions are not re-executed. Applicable to computing systems having a plurality of processors, of either the same or different type such as floating point and integer processors, the method and apparatus inhibits all such further execution of plural processors upon the detection of an exception in one of the processors. In processors other than the processors serving the exception, no-op instructions are executed until the processor servicing the exception causes pending instructions to be re-executed, at which time the other processors also re-execute instructions which were pending at the time further execution of the instructions was inhibited.



 Title Information Submit all comments and votes
 
Patent Text Patent PDF Print Page Summary File History
Plain text PDF images Print Summary File History
Drawing from US Patent 5193158
Method and apparatus for exception handling in pipeline processors

     having mismatched instruction pipeline depths - US Patent 5193158 Drawing
Method and apparatus for exception handling in pipeline processors having mismatched instruction pipeline depths
Inventor     Kinney; Daryl F. (Hopkinton, MA); Drogaris; Anthony N. (Wellesley, MA); Mills; Christopher H. (Chelmsford, MA); Kahaiyan; Michael (East Bridgewater, MA); Manton; John (Marlboro, MA)
Owner/Assignee     Hewlett-Packard Company (Palo Alto, CA)
Patent assignment
All assignments
Publication Date     March 9, 1993
Application Number     07/780,527
PAIR File History     Application Data   Transaction History
Image File Wrapper   Patent Term   Fees
Litigation
Filing Date     October 18, 1991
US Classification    
Int'l Classification    
Examiner     Clark; David L.
Assistant Examiner     Fagan; Matthew C.
Attorney/Law Firm    
Address
Parent Case     This application is a continuation of application Ser. No. 07/259,793, filed Oct. 19, 1988, now abandoned.
Priority Data    
USPTO Field of Search    
Patent Tags     exception handling pipeline processors mismatched instruction pipeline depths
   
Enter a comma (,) or semicolon (;) between multiple tag words/phrases.
Describe this patent:
 Amusing   
 Clever   
 Complex   
 Efficient   
 Historic   
 Important   
 Innovative   
 Interesting   
 Practical   
 Simple   
[no votes]
Patent WIKI

Share information and news about this patent, including information and news about the technology, inventors, company, ligation and licensing.

 References Submit all comments and votes
 
*references marked with an asterisk below are user-added references
 U.S. References
 
Add a new US reference:  
ReferenceRelevancyCommentsReferenceRelevancyComments
5119483
Madden
714/15
Jun,1992

[0 after 0 votes]
5109514
Garner
710/260
Apr,1992

[0 after 0 votes]
5063497
Cutler

Nov,1991

[0 after 0 votes]
5051885
Yates, Jr.
712/215
Sep,1991

[0 after 0 votes]
5019967
Wheeler
712/219
May,1991

[0 after 0 votes]
5003462
Blaner
711/207
Mar,1991

[0 after 0 votes]
5003458
Yamaguchi
710/260
Mar,1991

[0 after 0 votes]
4970641
Hester
710/260
Nov,1990

[0 after 0 votes]
4956767
Stephenson
703/13
Sep,1990

[0 after 0 votes]
4924466
Gregor
714/2
May,1990

[0 after 0 votes]
4914578
MacGregor
710/260
Apr,1990

[0 after 0 votes]
4903264
Talgam
714/25
Feb,1990

[0 after 0 votes]
4901233
Liptay
712/218
Feb,1990

[0 after 0 votes]
4893233
Denman Marvin A. (Austin, TX)
712/244
Jan,1990

[0 after 0 votes]
4879676
Hansen
708/505
Nov,1989

[0 after 0 votes]
4875160
Brown, III
712/228
Oct,1989

[0 after 0 votes]
4845659
Hrusecky
712/222
Jul,1989

[0 after 0 votes]
4797816
Uchiyama
711/220
Jan,1989

[0 after 0 votes]
4783783
Nagai
714/17
Nov,1988

[0 after 0 votes]
4782441
Inagami
712/9
Nov,1988

[0 after 0 votes]
4777593
Yoshida
712/9
Oct,1988

[0 after 0 votes]
4763294
Fong
708/510
Aug,1988

[0 after 0 votes]
4750112
Jones
712/217
Jun,1988

[0 after 0 votes]
4745547
Buchholz

May,1988

[0 after 0 votes]
4701915
Kitamura
714/6
Oct,1987

[0 after 0 votes]
4639886
Hashimoto
708/521
Jan,1987

[0 after 0 votes]
4597044
Circello
713/100
Jun,1986

[0 after 0 votes]
4594660
Guenthner
712/23
Jun,1986

[0 after 0 votes]
4566103
Sato
714/17
Jan,1986

[0 after 0 votes]
4541047
Wada
712/228
Sep,1985

[0 after 0 votes]
4530052
King
713/100
Jul,1985

[0 after 0 votes]
4521851
Trubisky
712/218
Jun,1985

[0 after 0 votes]
4498136
Sproul, III
710/262
Feb,1985

[0 after 0 votes]
4488228
Crudele
714/21
Dec,1984

[0 after 0 votes]
4399507
Cosgrove, deceased
712/219
Aug,1983

[0 after 0 votes]
4385365
Hashimoto
712/228
May,1983

[0 after 0 votes]
4161026
Wilhite
712/232
Jul,1979

[0 after 0 votes]
3736566
Anderson
714/15
May,1973

[0 after 0 votes]
3654448
Hitt
714/17
Apr,1972

[0 after 0 votes]
5134561
Liptay
711/164
Dec,1969

[0 after 0 votes]
 Foreign References
 Other References
 Market Review Submit all comments and votes
   
Market Size
Estimate the gross annual revenues of the relevant market sector:
> $10B
$5B - $10B
$2B - $5B
$500M - $2B
$100M - $500M
$10M - $100M
$1M - $10M
$500K - $1M
$100K - $500K
< $100K
[No votes]
$0
 
$0   $2.5B   $5B   $7.5B   $10B
Market Share
Estimate the percentage of the relevant market sector this invention will capture:
75% - 100%
50% - 74.99%
25% - 49.99%
10 - 24.99%
5 - 9.99%
2 - 4.99%
1 - 1.99%
< 1%
[No votes]
0.0%
 
0%   25%   50%   75%   100%
Reasonable Royalty
What percentage of gross sales should the inventor or assignee be paid?
75% - 100%
50% - 74.99%
25% - 49.99%
10 - 24.99%
5 - 9.99%
2 - 4.99%
1 - 1.99%
< 1%
[No votes]
0.0%
 
0%   25%   50%   75%   100%
Public's "Guesstimation" of Royalty Value
Market SizeN/A[No votes]
xMarket ShareN/A[No votes]
xReasonable RoyaltyN/A[No votes]

N/A

License Availablity
If you are NOT the owner or assignee, answer here:
Yes, license is available for purchase

No, license is not currently available



[No votes]
License Availablity
If you ARE the owner or assignee, answer here:
Yes, license is available for purchase

No, license is not currently available



[No votes]
Competitive Advantage
Does this invention have a significant competitive advantage over similar technologies?
Yes

No



[No votes]
Most helpful competitive advantage comment
[No comments]

Commercial Alternatives
Are there viable commercial alternatives for this invention?
Yes

No



[No votes]
Most helpful commercial alternative comment
[No comments]

 Technical Review Submit all comments and votes
 Claims Submit all comments and votes
 


What is claimed is:

1. Apparatus for executing a plurality of pipelined instructions, comprising:

an instruction source for providing pipelined instructions having variable length execution cycle times and including at least one short instruction and at least one long instruction;

a first pipelined processor, coupled to said instruction source, for executing a first sequence of said pipelined instructions, said first pipelined processor beginning execution of said at least one short instruction after beginning execution of said at least one long instruction, said first pipelined processor including

detection means for detecting an exception caused by an excepted instruction of said first sequence of pipelined instructions being executed, said detection means detecting said exception after said at least one short instruction has completed execution;

first inhibit means, coupled to said detection means and responsive to said detected exception, for inhibiting further execution of said excepted instruction;

identification means, coupled to said detection means and responsive to said detected exception, for identifying at least one pending instruction of said first sequence of pipelined instructions being executed, said at least one pending instruction including said at least one long instruction;

second inhibit means, responsive to the identification means, for inhibiting further execution of said at least one pending instruction;

exception handler means , coupled to said detection means and responsive to said detected exception, for saving states of said first pipelined processor, for serving said exception and for restoring the saved states of said first pipelined processor; and

re-execution means, coupled to said first and second inhibit means, and responsive to said exception handler means and said identification means, for causing said first pipelined processor to re-execute said excepted instruction and said at least one pending instruction in an order corresponding to said first sequence of pipelined instructions, said re-execution means precluding re-execution of said completed at least one short instruction, wherein said first pipelined processor re-executes only said excepted instruction and said at least one pending instruction.

2. The apparatus of claim 1, wherein said at least one pending instruction and said excepted instruction includes said at least one long instruction.

3. The apparatus of claim 1, further comprising

a second pipelined processor, coupled to said instruction source, for executing a second sequence of said pipelined instructions, said second pipelined processor including

third inhibit means, coupled to said detection means and responsive to said detected exception, for inhibiting further execution of said second sequence of pipelined instructions and for identifying a second at least one pending instruction of said second sequence of pipelined instructions being executed;

delay means, responsive to said third inhibit means, for inhibiting execution of said second sequence of pipelined instructions at least until said re-execution means causes said first pipelined processor to re-execute said excepted instruction; and

second re-execution means, coupled to said delay means and responsive to said re-execution means, for causing said second pipelined processor to re-execute said second at least one pending instruction.

4. The apparatus of claim 3, wherein said delay means comprises means for stalling said second pipelined processor.

5. The apparatus of claim 3, wherein said delay means comprises means for causing said second pipelined processor to execute successive no-op instructions.

6. The apparatus of claim 3, wherein said first pipelined processor is a floating point processor and said second pipelined processor is an integer processor.

7. A method of executing a plurality of instructions in a pipelined computer apparatus, comprising the steps of:

providing a plurality of instructions having variable length execution cycle times and including at least one short instruction and at least one long instruction;

executing a first sequence of said instructions in a first pipelined processor;

executing a second sequence of said instructions in a second pipelined processor concurrently with the step of executing said first sequence of instructions;

wherein the steps of executing said first and second sequences of instructions include beginning execution of said at least one short instruction after beginning execution of said at least one long instruction;

detecting an exception caused by an excepted instruction of one of said first and second sequences of instructions during the steps of executing said first and second sequences of instructions and after said at least one short instruction has completed execution;

identifying a first at least one pending instruction in at least one of said first and second sequence of instructions concurrently with said step of detecting said exception, said first at least one pending instruction including said at least one long instruction;

inhibiting further execution of said excepted instruction and said first at least one pending instruction;

servicing said exception by at least saving a state of one of said first and second pipelined processors executing said excepted instruction, handling said exception and restoring the saved state of said one of said first and second pipelined processors executing said excepted instruction; and

re-executing said excepted instruction and said first at least one pending instruction in an order corresponding to said first and second sequence of instructions, wherein said re-executing step includes the step of precluding re-execution of said completed at least one short instruction.

8. The method of claim 7, wherein said first at least one pending instruction and said excepted instruction includes said at least one long instruction.

9. The method of claim 7 further including the step of:

halting execution of with instructions on one of said first processor and said second processor not serving said exception and not re-executing said excepted instruction during the steps of servicing said exception and re-executing said excepted instruction by the other of said first and second processors.

10. The method of claim 9 wherein said step of halting involves stalling said one of said first processor and said second processor not servicing said exception and not re-executing said excepted instruction.

11. The method of claim 9 wherein said step of halting includes executing no-op instructions on said one of said first processor and said second processor not servicing said exception and not re-executing said excepted instruction.
 Description Submit all comments and votes
 


FIELD OF THE INVENTION

The present invention relates to computer pipeline processors, and in particular to pipeline processor methods and apparatus for handling exceptions and instructions of differing execution cycle count latencies.

BACKGROUND OF THE INVENTION

The execution of program instructions typically requires a sequential execution of various operations directly related to the instruction, such as instruction fetch, decode, execute and result read/store. Pipelined processors allocate specific hardware elements to each of these operations, and sequentially process succeeding instructions so that each of the hardware elements associated with the various instruction operations function constantly albeit for two or more separate instructions. For an instruction having four separate operation stages which may be sequentially performed in time, a pipeline processor would incorporate four separate hardware elements, each to specifically provide the operation corresponding to the four operation stages of the instruction. A first instruction would be received by the first element to provide a first operation during the first time cycle. A second element would perform the second operation of the first instruction while the first element would acquire the next instruction to provide the first operation of the second instruction. Two cycles subsequently, a fourth element is processing the fourth operation on the first instruction, the third element is providing the third operation on the second instruction, the second element is providing the second operation on the third instruction and the first element is providing the first operation on the fourth instruction. The pipeline processing continues as long as instructions are sequentially received by the processor pipeline or until an exception is generated by one of the four elements of the pipeline processor. The exceptions relate to an unacceptable condition resulting from the processing of a particular instruction, such as page fault, a register overflow, or other condition of invalid data or instructions. While exceptions may occur at any point in the execution of an instruction, the most severe exception recovery requirement occurs when the exception is indicated in the later cycles of the instruction execution.

The number of cycles necessary to execute an instruction is dependent on the particular instruction. The instruction set may comprise instructions which require the same number of execution cycles, or may include instructions requiring varying numbers of execution cycles resulting in a corresponding variability in the number of processor execution elements. When an exception occurs, the processor inhibits the subsequent execution of the instruction which provoked the exception, services the exception and restarts that instruction and any subsequent instructions. However, processors having variable length instruction execution times face a condition where an exception may be generated by a long execution cycle instruction (long instruction) which began before a subsequent, shorter execution cycle instruction (shorter instruction). When the exception occurs, the subsequent, shorter instruction may have completed its execution and modified the corresponding registers with the proper information. However, in the condition that the exception occurs after the completed execution of the shorter instruction, the known exception handling techniques would require that the instruction that provokes the exception, as well as the completed shorter instruction and any subsequent instruction be re-executed. The result would be multiple execution shorter instructions producing erroneous computation. Consequently, the implementation of pipeline processors to service variable execution length instructions has been held in disfavor, or the variability of the instruction execution cycles is strictly controlled to avoid the above-mentioned condition of completed execution of a subsequently begun, shorter instr