US4679141A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pageable branch history table
Assignee: International Business Machines Corp
•
Filing: 1985-04-29
•
Granted: 1987-07-07
•
Expires: 2005-04-29
Abstract
Abstract A branch history table (BHT) is substantially improved by dividing it into two parts: an active area, and a backup area. The active area contains entries for a small number of branches which the processor can encounter in the near future and the backup area contains all other branch entries. Means are provided to bring entries from the backup area into the active area ahead of when the processor will use those entries. When entries are no longer needed they are removed from the active area and put into the backup area if not already there. New entries for the near future are brought in, so that the active area, though small, will almost always contain the branch information needed by the processor. The small size of the active area allows it to be fast and to be optimally located in the processor layout. The backup area can be located outside the critical part of the layout and can therefore be made larger than would be practicable for a standard BHT.
Inventors
- 👤 James H. Pomerene
- 👤 Thomas R. Puzak
- 👤 Rudolph N. Rechtschaffen
- 👤 Philip L. Rosenfeld
- 👤 Frank J. Sparacio
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 15:45
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3806; G06F9/3836; G06F9/3842; G06F9/3844
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
108 words
In a branch history table which is divided into two sections, with groups of instructions being divided into segments and with the branch information for a segment forming a segment entry, the combination comprising: an active high speed section in which n, where n is an integer, segment entries are stored, including means for processing branch information in said segment entries; a slower speed backup section which stores the remaining segment entries of said branch history table; and means for updating the active high speed section from the slower speed section based on analyzing branch information in segment entries to determine entries to be used in the future.
Claim 2
Dependent Claim
108 words
In a branch history table which is divided into two sections, with groups of instructions being divided into segments and with the branch information for a segment forming a segment entry, the combination comprising: an active high speed section in which n, where n is an integer, segment entries are stored, including means for processing branch information in said segment entries; a slower speed backup section which stores the remaining segment entries of said branch history table; and means for updating the active high speed section from the slower speed section based on analyzing branch information in segment entries to determine entries to be used in the future.
Claim 3
Dependent Claim
85 words
The combination claimed in claim 1, wherein said means for updating comprises: analyzing means for determining exit address of each branch instruction in a given segment entry; and staging means responsive to the exit address determination of said analyzing means for examining the exit addresses of each segment in said active high speed section to determine which are target addresses of following segment entries in said slow speed section, including means for readying said following segment entries for fetching to said active high speed section.
Claim 4
Dependent Claim
159 words
In a branch history table which is divided into two sections, with said branch history table viewing memory as being divided into segments, wherein a segment is a continuous portion of memory, the combination comprising: a first active high speed section in which n, where n is an integer, segment entries are stored, including means for processing branch information in said n segment entries; a second slower speed section in which the remaining segment entries in said branch history table are stored; analyzer means coupled to said first active high speed section and said second slower speed section for determining an exit address of each branch instruction in a given segment; and stager means coupled to said first active high speed section and said second slower speed section and responsive to the exit address determination of said analyzer means for assuring the next n-1) segment crossing will be to segment entries stored in said first active high speed section.
Claim 5
Dependent Claim
159 words
In a branch history table which is divided into two sections, with said branch history table viewing memory as being divided into segments, wherein a segment is a continuous portion of memory, the combination comprising: a first active high speed section in which n, where n is an integer, segment entries are stored, including means for processing branch information in said n segment entries; a second slower speed section in which the remaining segment entries in said branch history table are stored; analyzer means coupled to said first active high speed section and said second slower speed section for determining an exit address of each branch instruction in a given segment; and stager means coupled to said first active high speed section and said second slower speed section and responsive to the exit address determination of said analyzer means for assuring the next n-1) segment crossing will be to segment entries stored in said first active high speed section.
Claim 6
Independent Claim
111 words
A method of processing branch instructions in a branch history table, wherein memory is viewed as being divided into segments, wherein a segment is defined as a continuous portion of memory which starts on a segment boundary, said method comprising the steps of: processing n, where n is an integer, segment entries in an active high speed section of said branch history table; storing the remaining segment entries in said branch history table in a slow speed section; and updating the active high speed section from the slow speed section based on analyzing the segment entries to determine if branch information contained in the segment entries are anticipated for future use.
Claim 7
Independent Claim
111 words
A method of processing branch instructions in a branch history table, wherein memory is viewed as being divided into segments, wherein a segment is defined as a continuous portion of memory which starts on a segment boundary, said method comprising the steps of: processing n, where n is an integer, segment entries in an active high speed section of said branch history table; storing the remaining segment entries in said branch history table in a slow speed section; and updating the active high speed section from the slow speed section based on analyzing the segment entries to determine if branch information contained in the segment entries are anticipated for future use.
Claim 8
Dependent Claim
58 words
The method of claim 4, wherein the step of updating includes the steps of: analyzing the segment entries to determine the exit address of each branch instruction contained therein; and staging segment entries presently stored in said slow speed section, for storage in said active high speed section based on the exit address determination during the analyzing step.
Claim 9
Independent Claim
142 words
A method of processing branch instructions in a branch history table, wherein memory is viewed as being divided into segments, wherein a segment is defined as a continuous portion of memory which starts on a segment boundary, said method comprising the steps of: processing n, where n is an integer, segment entries in a first active high speed section of said branch history table; storing the remaining segment entries in said branch history table in a slow speed section of said branch history table; analyzing each branch instruction in a segment entry by an analyzer to determine the exit addresses of the branch instructions; and responding to the determination of the exit addresses of the branch instructions in the respective segment entries by a stager, to assure the next (n-1) segment crossings will be to segment entries stored in said active area.
Claim 10
Independent Claim
142 words
A method of processing branch instructions in a branch history table, wherein memory is viewed as being divided into segments, wherein a segment is defined as a continuous portion of memory which starts on a segment boundary, said method comprising the steps of: processing n, where n is an integer, segment entries in a first active high speed section of said branch history table; storing the remaining segment entries in said branch history table in a slow speed section of said branch history table; analyzing each branch instruction in a segment entry by an analyzer to determine the exit addresses of the branch instructions; and responding to the determination of the exit addresses of the branch instructions in the respective segment entries by a stager, to assure the next (n-1) segment crossings will be to segment entries stored in said active area.
Claim 11
Dependent Claim
99 words
The method of claim 6, wherein said step of responding includes the steps of: maintaining in said stager a first list of segment entries presently stored in said active area and a second list of the next (n-1) segment crossings; comparing said first and second lists to determine if said (n-1) segment crossings are in one of the n segment entries presently stored in said first active high speed section; and fetching any segment entry that includes one of said (n-1) crossings and is not presently stored in said active high speed area, to said active high speed area.
References Cited (Backward Citations)
US4370711A
Cited
US4477872A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1990-07-06 | 1991-01-05 | 1991-07-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1994-07-06 | 1995-01-05 | 1995-07-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1998-07-06 | 1999-01-05 | 1999-07-07 | $7700.00 | Window Closed / Lapsed |