| United States Patent | 6,502,188 |
| Zuraski, Jr. , et al. | December 31, 2002 |
Dynamic classification of
conditional branches in global history branch prediction
Abstract
A branch prediction unit includes a local branch prediction and a global branch prediction. A global branch prediction utilizes a global history shift register to record the behavior of conditional branches. In some cases, a conditional branch may behave in a static manner, either always being taken or not taken, while resident in an instruction cache. Such static behaving conditional branches do not need a global history for prediction and contend with other conditional branches for global branch history training. By utilizing a dynamic branch classification scheme, branches requiring global history prediction can be identified and static behaving conditional branches may be prevented from polluting the global history. All conditional branches are initially classified as local and do not participate in global history training. Only after two mispredictions are branches recognized as exhibiting dynamic behavior and classified as global. These branches classified as global may then participate in global history training and utilize a global history based branch prediction.
| Inventors: | Zuraski, Jr.; Gerald D. (Austin, TX); Roberts; James S. (Austin, TX); Tupuri; Raghuram S. (Austin, TX) |
| Assignee: | Advanced Micro Devices, Inc. (Sunnyvale, CA) |
| Appl. No.: | 441630 |
| Filed: | November 16, 1999 |
| Current U.S. Class: | 712/234; 711/125; 712/207; 712/239; 712/240 |
| Intern'l Class: | G06F 009/40; G06F 009/42; G06F 009/305 |
| Field of Search: | 712/239,230,240,233,234,235,236,237,238,241,243,245,207 711/125 |
References Cited [Referenced By]
U.S. Patent Documents
| 4179737 | Dec., 1979 | Kim | 712/241. |
| 4860197 | Aug., 1989 | Langendorf et al. | 712/238. |
| 5142634 | Aug., 1992 | Fite et al. | 712/240. |
| 5265213 | Nov., 1993 | Weiser et al. | 712/240. |
| 5367703 | Nov., 1994 | Levitan | 712/23. |
| 5381533 | Jan., 1995 | Peleg et al. | 712/215. |
| 5454117 | Sep., 1995 | Puziol et al. | 712/23. |
| 5553253 | Sep., 1996 | Pan et al. | 712/240. |
| 5553254 | Sep., 1996 | Berstis et al. | 712/207. |
| 5592634 | Jan., 1997 | Circello et al. | 712/239. |
| 5608886 | Mar., 1997 | Blomgren et al. | 712/239. |
| 5642500 | Jun., 1997 | Inoue | 712/233. |
| 5649137 | Jul., 1997 | Favor et al. | 712/207. |
| 5649178 | Jul., 1997 | Blaner et al. | 712/240. |
| 5692168 | Nov., 1997 | McMahan | 712/237. |
| 5708803 | Jan., 1998 | Ishimi et al. | 712/233. |
| 5732253 | Mar., 1998 | McMahan | 712/239. |
| 5737590 | Apr., 1998 | Hara | 712/238. |
| 5758142 | May., 1998 | McFaring et al. | 712/239. |
| 5764946 | Jun., 1998 | Tran et al. | 712/239. |
| 5794028 | Aug., 1998 | Tran | 712/240. |
| 5822574 | Oct., 1998 | Tran | 712/233. |
| 5822575 | Oct., 1998 | Tran | 712/239. |
| 5864707 | Jan., 1999 | Tran et al. | 712/23. |
| 5881278 | Mar., 1999 | Tran et al. | 712/238. |
| 5954816 | Sep., 1999 | Tran et al. | 712/239. |
| 5961638 | Oct., 1999 | Tran | 712/239. |
| 5978906 | Nov., 1999 | Tran | 712/239. |
| 5995749 | Nov., 1999 | Tran | 712/239. |
| 6055630 | Apr., 2000 | D'Sa et al. | 712/240. |
| 6253316 | Jun., 2001 | Tran et al. | 712/239. |
| Foreign Patent Documents | |||
| 0 199 947 | Nov., 1986 | EP. | |
| 0 394 711 | Oct., 1990 | EP. | |
| 0 586 057 | Mar., 1994 | EP. | |
| 0 605 876 | Jul., 1994 | EP. | |
| 2 285 526 | Jul., 1995 | GB. | |
| 93/17385 | Sep., 1993 | WO. | |
| 98/22873 | May., 1998 | WO. | |
Other References |
Calder et al., "Next Cache Line and Set Prediction," Computer Architecture News, vol. 23, No. 2, May 1995, pp. 287-296. McFarling, "Combining Branch Predictors," WRL Technical Note TN-36, Jun. 1993, pp. 1-20. Kaiser, "K7 Branch Prediction," .COPYRGT. 1999 by Andrea Kaiser, 4 pgs. Diefendorff, "Athlon Outruns Pentium III," Microprocessor Report, vol. 13, No. 11, Aug. 1999, 7 pgs. |
Primary Examiner: Pan; Daniel H.
Attorney, Agent or Firm: Rankin; Rory D., Merkel; Lawrence
J.
Last Updated : Sun Mar 9 22:46:03 EST 2008
Back to Jerry Z's Home Page