Two-Level Adaptive Training Branch Prediction

Có sự suy giảm nghiêm trọng về hiệu năng trong các máy có đường ống sâu và/hoặc siêu vô hướng do các lỗi dự đoán gây ra bởi lượng lớn công việc suy đoán phải bị loại bỏ [1, 8]. Đây là động lực để đề xuất một sơ đồ dự đoán nhánh động mới có độ chính xác cao hơn. Sơ đồ mới sử dụng hai mức thông tin lịch sử nhánh để đưa ra dự đoán. Mức thứ nhất là lịch sử của $n$ nhánh gần nhất. Mức thứ hai là hành vi nhánh đối với $s$ lần xuất hiện gần nhất của mẫu duy nhất đó trong lịch sử của $n$ nhánh gần nhất. Thông tin lịch sử được thu thập trực tiếp trong quá trình thực thi mà không cần thực thi chương trình trước đó, loại bỏ nhược điểm chính của Static Training Prediction. Sơ đồ được đề xuất ở đây được gọi là Two-Level Adaptive Training Branch Prediction, vì các dự đoán không chỉ dựa trên bản ghi của $n$ nhánh gần nhất, mà còn dựa trên bản ghi của $s$ lần xuất hiện gần nhất của bản ghi cụ thể của $n$ nhánh gần nhất.

Các mô phỏng dựa trên trace đã được sử dụng trong nghiên cứu này. Sơ đồ dự đoán nhánh Two-Level Adaptive Training cũng như các sơ đồ dự đoán nhánh động và tĩnh khác đã được mô phỏng trên bộ phép đo chuẩn SPEC. Bằng cách sử dụng Two-Level Adaptive Training Branch Prediction, độ chính xác dự đoán trung bình đối với các phép đo chuẩn đạt 97 phần trăm, trong khi hầu hết các sơ đồ khác đạt dưới 93 phần trăm. Điều này biểu thị sự giảm hơn 100 phần trăm số lần dự đoán sai khi sử dụng sơ đồ Two-Level Adaptive Training. Sự giảm này có thể trực tiếp dẫn đến mức tăng hiệu năng lớn trên một bộ xử lý hiệu năng cao.

Abstract

High-performance microarchitectures use, among other structures, deep pipelines to help speed up execution. The importance of a good branch predictor to the effectiveness of a deep pipeline in the presence of conditional branches is well-known. In fact, the literature contains proposals for a number of branch prediction schemes. Some are static in that they use opcode information and profiling statistics to make predictions. Others are dynamic in that they use run-time execution history to make predictions.

This paper proposes a new dynamic branch predictor, the Two-Level Adaptive Training scheme, which alters the branch prediction algorithm on the basis of information collected at run-time.

Several configurations of the Two-Level Adaptive Training Branch Predictor are introduced, simulated, and compared to simulations of other known static and dynamic branch prediction schemes. Two-Level Adaptive Training Branch Prediction achieves 97 percent accuracy on nine of the ten SPEC benchmarks, compared to less than 93 percent for other schemes. Since a prediction miss requires flushing of the speculative execution already in progress, the relevant metric is the miss rate. The miss rate is 3 percent for the Two-Level Adaptive Training scheme vs. 7 percent (best case) for the other schemes. This represents more than a 100 percent improvement in reducing the number of pipeline flushes required.

Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.

© 1991 ACM 0-89791-460-0/91/0011/0051 \$1.50

This section is missing here.

1 Introduction

This section is missing here.

2 Two-Level Adaptive Training Branch Prediction

This section is missing here.

3 Implementation Methods