RAS 오염 방지를 통한 함수 복귀 예측 정확도 향상 = Prediction Accuracy Enhancement of Function Return Address via RAS Pollution Prevention

국문 초록 (Abstract)

조건 분기 명령어의 예측 정확도가 매우 높아짐에 따라 상대적으로 무조건 분기 명령어의 예측이 중요해지고 있다. 그 중 RAS(Return Address Stack)를 사용하는 함수 복귀 예측은 이론적으로 오버플로가 발생하지 않는 한도 내에서 100%의 정확도를 보여야 한다. 하지만 투기적 실행을 지원하는 현대 마이크로프로세서 환경 하에서는 잘못된 실행 경로로의 수행 결과를 무효화 할 때 RAS의 오염이 발생하며, 이는 함수 복귀 주소의 예측 실패로 이어진다. 본 논문에서는 이러한 RAS의 오염을 방지하기 위하여 RAS 재명명 기법을 제안한다. RAS 재명명 기법은 RAS의 스택을 소프트 스택과 하드 스택으로 나누어 투기적 실행에 의한 데이터의 변경을 복구할 수 있는 소프트 스택에서 투기적 실행에 의한 데이터를 관리하고, 소프트 스택의 크기 제한으로 겹쳐쓰기가 일어나는 데이터 중 이후에 사용될 데이터를 하드 스택으로 옮기는 구조로 구성된다. 또한 이러한 구조의 문제점을 파악하여, 본 논문에서는 RAS 재명명 기법의 추가적 개선법을 소개한다. 제안된 기법을 모의실험 한 결과, RAS 오염 방지 기법이 적용되지 않은 시스템과 비교하여 함수 복귀 예측 실패를 약 1/90로 감소시켰으며, 최대 6.95%의 IPC 향상을 가져왔다. 또한 기존의 RAS 오염 방지 기법이 적용된 시스템과 비교하여 함수 복귀 예측 실패를 약 1/9로 감소 시켰다.

다국어 초록 (Multilingual Abstract)

As the prediction accuracy of conditional branch instruction is increased highly, the importance of prediction accuracy for unconditional branch instruction is also increased accordingly. Except the case of RAS(Return Address Stack) overflow, the prediction accuracy of function return address should be 100% theoretically. However, there exist some possibilities of miss-predictions for RAS return addresses, when miss-speculative execution paths are invalidated, in case of modern speculative microprocessor environments. In this paper, we propose the RAS rename technique to prevent RAS pollution, results in the reduction of RAS miss-prediction. We divide a RAS stack into a soft-stack and a hard-stack and we handle the instructions for speculative execution in the soft-stack. When some overwrites happen in the soft-stack, we move the soft-stack data into the hard-stack. In addition, we propose an enhanced version of RAS rename scheme. In simulation results, our solution provide 1/90 reduction of miss-prediction of function return address, results in up to 6.85% IPC improvement, compared to normal RAS method. Furthermore, it reduce miss-prediction ratio as 1/9, compared to previous technique.

목차 (Table of Contents)

• 요약
• Abstract
• Ⅰ. 서론
• Ⅱ. 관련 연구
• Ⅲ. RAS 오염 방지 기법
• Ⅳ. 모의실험 및 성능 분석
• Ⅴ. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

• 1 H. Kim, "VPC prediction: reducing the cost of indirect branches via hardware-based dynamic devirtualization" 424-435, 2007
• 2 A. Seznec, "The L-TAGE Branch Predictor" 9 : 2007
• 3 S. Jourdan, "The Effects of Mispredicted-Path Execution on Branch Prediction Structures" 58-, 1996
• 4 H. Vandierendonck, "Speculative return address stack management revisited" 5 (5): 2008
• 5 "SPEC CPU Benchmarks"
• 6 G. H. Loh, "Revisiting the Performance Impact of Branch Predictor Latencies" 59-69, 2006
• 7 T.-Y. Yeh, "Return address predictor that uses branch instructions to track a last valid return address" 6 : 253-315, 2001
• 8 D. Jimenez, "Piecewise liner branch prediction" 2003
• 9 H. Gao, "PMPM: Prediction by Combining Multiple Partial Matches" 9 : 2007
• 10 G.-Y. Chiu, "Mechanism for return stack and branch history corrections under misprediction in deep pipeline design" 1-8, 2008
• 11 이경호, "Indirect Branch Validation Unit" ELSEVIER SCIENCE BV 33 (33): 461-468, 200910
• 12 E. Sprangle, "Increasing processor performance by implementing deeper pipelines" 25-34, 2002
• 13 K. Skadron, "Improving prediction for procedure returns with return-address-stack repair mechanisms" 259-271, 1998
• 14 Y. Ishii, "Fused Two-Level Branch Prediction with Ahead Calculation" 9 : 2007
• 15 D. Burger, "Evaluating future micro-processors: the SimpleScalar tool set" Univ. of Wisconin-madison Computer Science Dept. 1997
• 16 V. Desmet, "Correct alignment of a return-address-stack after call and return mispredictions" 25-33, 2005
• 17 D. A. Patterson, "Computer architecture: a quantitative approach" Morgan Kaufman 2007
• 18 K. Aasaraai, "Computational and storage power optimizations for the O-GEHL branch predictor" 105-112, 2007
• 19 S. McFarling, "Combining branch predictors. Tech. Rep. TN-36m" Digital Western Research Lab 1993
• 20 J. H. Kim, "Branch Pre-Prediction: A Method for Hiding Branch Prediction Latency" 13 (13): 2010