RAS 오염 방지를 통한 함수 복귀 예측 정확도 향상

김주환(Ju-Hwan Kim),곽종욱(Jong Wook Kwak),장성태(Seong Tae Jhang),전주식(Chu Shik Jhon) 大韓電子工學會 2011 電子工學會論文誌-CI (Computer and Information) Vol.48 No.3

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

분기 선예측과 개선된 BTB 구조를 사용한 분기 예측 지연시간 은폐 기법

김주환(Ju-Hwan Kim),곽종욱(Jong-Wook Kwak),전주식(Chu-Shik Jhon) 한국컴퓨터정보학회 2009 韓國컴퓨터情報學會論文誌 Vol.14 No.10

현대의 프로세서 아키텍처에서 정확한 분기 예측은 시스템의 성능에 지대한 영향을 끼친다. 최근의 연구들은 예측 정확도뿐만 아니라, 예측 지연시간 또한 성능에 막대한 영향을 끼친다는 것을 보여준다. 하지만, 예측 지연시간은 간과되는 경향이 있다. 본 논문에서는 분기 예측지연시간을 극복하기 위한 분기 선예측 기법을 제안한다. 이 기법은 분기장치를 인출 단계에서 분리함으로써, 분기 예측기가 명령어 인출 장치로부터의 아무런 정보도 없이 스스로 분기 예측을 진행 가능하게 한다. 또한, 제안된 기법을 지원하기 위해, BTB의 구조를 새롭게 개선하였다. 실험 결과는 제안된 기법이 동일한수준의 분기 예측정확도를 유지하면서, 대부분의 예측지연시간을 은폐한다는 것을 보여준다. 더욱이 제안된 기법은 항상 1 싸이클의 예측 지연시간을 가지는 이상적인 분기 예측기를 사용한 경우보다도 더 나은 성능을 보여준다. 본 논문의 실험 결과에 따르면, 기존의 방식과 비교했을 때, 최대 11.92% 평균 5.15%의 IPC 향상을 가져온다. Precise branch predictor has a profound impact on system performance in modern processor architectures. Recent works show that prediction latency as well as prediction accuracy has a critical impact on overall system performance as well. However, prediction latency tends to be overlooked. In this paper, we propose Branch Pre-Prediction policy to tolerate branch prediction latency. The proposed solution allows that branch predictor can proceed its prediction without any information from the fetch engine, separating the prediction engine from fetch stage. In addition, we propose newly modified BTE structure to support our solution. The simulation result shows that proposed solution can hide most prediction latency with still providing the same level of prediction accuracy. Furthermore, the proposed solution shows even better performance than the ideal case, that is the predictor which always takes a single cycle prediction latency. In our experiments, IPC improvement is up to 11.92% and 5.15% in average, compared to conventional predictor system.

신경망의 분석을 통한 방향 정보를 내포하는 분기 예측 기법

곽종욱,김주환,전주식,Kwak Jong Wook,Kim Ju-Hwan,Jhon Chu Shik 대한전자공학회 2005 電子工學會論文誌-CI (Computer and Information) Vol.42 No.1

파이프라인과 슈퍼스칼라 방식 그리고 동적 스케줄링 기법이 일반화된 시스템 구조 하에서, 분기 명령어에 대한 분기 예측 정확도는 프로세서 입장에서 뿐만 아니라 시스템 전체적인 성능에 있어서 큰 영향을 미친다. 이는 분기 예측이 실패했을 경우 잘못된 분기 예측으로 인한 페널티가 발생하기 때문이며, 이러한 페널티는 파이프라인의 길이가 깊어지고 더욱 많은 수의 명령어가 동시에 실행되는 환경일수록 더 큰 값을 가진다. 본 논문에서는 분기 예측의 정확도를 높이기 위해서, 분기 예측과 관련된 신경망을 구축하여 이론 통해 분기 예측에 필요한 각 요소별 가중치의 경향을 분석한다. 그 결과, 높은 가중치를 가지는 구성 요소를 기존의 분기 예측 기법에 추가시킨 새로운 형태의 분기 예측 기법을 제안한다. 제안된 새로운 기법은 실행 구동방식의 시뮬레이터인 Simple Scalar를 통하여 모의실험 되었으며, 실험 결과 본 논문에서 제시한 "분기 명령어의 방향 정보를 내포하는 새로운 기법(direction-gshare)"이 기존의 gshare 기법과 비교하여 동일한 하드웨어 복잡도를 가지면서도 일반적인 Bimodal 기법이나 이단계 적응형 분기 예측 기법 혹은 그의 변형인 gshare 기법에 비하여 분기 예측의 정확도가 최대 4.1%, 평균 1.5% 더 우수한 결과를 보였으며, 최적의 방향 정보 내포량에 대해서는 최대 11.8%, 평균 3.7%의 성능 향상을 보였다. In the pursuit of ever higher levels of performance, recent computer systems have made use of deep pipeline, dynamic scheduling and multi-issue superscalar processor technologies. In this situations, branch prediction schemes are an essential part of modem microarchitectures because the penalty for a branch misprediction increases as pipelines deepen and the number of instructions issued per cycle increases. In this paper, we propose a novel branch prediction scheme, direction-gshare(d-gshare), to improve the prediction accuracy. At first, we model a neural network with the components that possibly affect the branch prediction accuracy, and analyze the variation of their weights based on the neural network information. Then, we newly add the component that has a high weight value to an original gshare scheme. We simulate our branch prediction scheme using Simple Scalar, a powerful event-driven simulator, and analyze the simulation results. Our results show that, compared to bimodal, two-level adaptive and gshare predictor, direction-gshare predictor(d-gshare. 3) outperforms, without additional hardware costs, by up to 4.1% and 1.5% in average for the default mont of embedded direction, and 11.8% in maximum and 3.7% in average for the optimal one.

신경망을 이용한 분기 예측의 개선

곽종욱 ( Jong Wook Kwak ),김주환 ( Ju-hwan Kim ),전주식 ( Chu Shik Jhon ) 한국정보처리학회 2004 한국정보처리학회 학술대회논문집 Vol.11 No.1

파이프라인과 슈퍼스칼라 방식이 일반화된 시스템 구조 하에서, 분기 명령어는 시스템 전체적인 성능에 중요한 영향을 미친다. 특히 분기 예측이 실패했을 경우, 잘못된 분기 예측으로 인한 페널티가 발생한다는 점에서 분기 예측의 정확도에 대한 중요성은 크다고 할 수 있다. 본 논문에서는 분기 예측의 정확도를 높이기 위해서, 분기 예측과 관련된 신경망을 구축하여 이를 통해 분기 예측에 필요한 각 요소별 가중치의 변화를 분석하고, 이를 분기 예측에 새롭게 반영하고자 한다. 본 논문에서는 이를 위해 실행 구동 방식의 시뮬레이터인 SimpleScalar 를 통하여 모의 실험을 수행하였으며, 실험 결과 본 논문에서 제시한 새로운 기법이 기존의 일반적인 이단계 적응형 분기 예측 기법이나 gshare 기법에 비하여 더 우수한 결과를 보였다.

칩 멀티 프로세서의 공유 버스를 이용한 유휴 캐시 활용 기법

강석빈 ( Seok-bin Kang ),김주환 ( Ju-hwan Kim ),곽종욱 ( Jong Wook Kwak ),장성태 ( Seong Tae Jhang ),전주식 ( Chu-shik Jhon ) 한국정보처리학회 2009 한국정보처리학회 학술대회논문집 Vol.16 No.1

반도체 집적도의 향상과 제한된 프로세서 설계 능력으로 인한 칩 멀티 프로세서의 도입은 최근 수 년 동안 급속히 이루어졌으나, 다수의 프로세싱 코어를 효율적으로 사용하기 위한 기법은 부족한 실정이다. 칩 멀티 프로세서 상에서 실제 작업을 수행하지 않는 유휴 코어의 발생은 불가피하며, 이 때 코어가 소유한 자원들은 낭비될 수 밖에 없다. 기존의 연구들은 이렇게 낭비되는 자원 중에서 캐시의 효율적 관리를 위해 공유 캐시 형태로 캐시를 구성하였으나, 전체 캐시 관리에 따른 많은 오버헤드를 수반하였다. 본 논문에서는 이러한 유휴 캐시의 발생이 불가피함을 인지하고 그것을 칩 내 메모리 공간으로써 활용하여 칩 멀티 프로세서 전체의 성능을 향상시키는 기법을 제안한다. 이를 위해 ARM 코어 기반의 칩 멀티프로세서 시뮬레이터 환경을 구성하여 제안된 기법을 검증한다. 실험 결과 본 논문에서 소개된 기법은 4-코어 및 16 코어 기반 칩 멀티 프로세서 환경에서 각각 17%와 8%의 IPC 향상을 가져왔다.

분기 정보의 투기적 사용에 대한 효율적인 복구 기법

곽종욱(Jong Wook Kwak),김주환(Ju-Hwan Kim),장성태(Seong Tae Jhang),전주식(Chu Shik Jhon) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.2

분기 명령어의 예측 정확도는 시스템 전체 성능에 중대한 영향을 미친다. 여러 분기 예측 방식 가운데 하나인 “분기 정보의 투기적 사용”은 분기 명령어의 가장 최근 기록을 일관되게 사용할 수 있도록 도와 줌으로 해서 분기 예측의 정확도 향상에 크게 기여한다. 하지만 이와 같은 기법은 미완료 분기에 대한 히스토리를 투기적으로 사용하는 방식이다. 따라서 사용되는 정보가 올바르지 못할 수 있으며, 이런 경우 적절한 복구 기법을 필요로 한다. 본 논문에서는 분기 정보의 투기적 사용에 대한 필요성과 효율적인 복구 기법을 제안한다. 제안된 기법은 이전 연구와 비교하여 상당한 하드웨어 요구량의 감소를 가져왔으며, 또한 프로그램 수행의 정확성을 해치지 않으면서 최대 3.3%의 성능향상을 보였다.

모드 선택 비트를 활용한 필터 캐시 예측 모델

곽종욱 ( Jong Wook Kwak ),최주희 ( Ju Hee Choi ),장성태 ( Seong Tae Jhang ),전주식 ( Chu Shik Jhon ) 한국정보처리학회 2008 한국정보처리학회 학술대회논문집 Vol.15 No.1

캐시 에너지의 소비 전력을 줄이기 위해 필터 캐시가 제안되었다. 필터 캐시의 사용으로 인해 많은 전력 사용 감소 효과를 가져왔으나, 상대적으로 시스템 성능도 더불어 감소하게 되었다. 필터 캐시의 사용으로 인한 성능 감소를 최소화하기 위해서, 본 논문에서는 기존에 제안된 주요 필터 캐시 예측 모델들을 소개하며, 각각의 방식에 있어서의 핵심 특징 및 해당 방식의 문제점을 분석한다. 이를 바탕으로 본 논문에서는 모드 선택 비트를 활용하는 개선된 형태의 새로운 필터 캐시 예측기 모델을 제안한다. 제안된 방식은 MSB라 불리는 참조 비트를 고안하여, 이를 기존의 필터캐시와 BTB에 새롭게 활용한다. 실험 결과, 제안된 방식은 기존 방식 대비, 전력 소모량·시간 지연면에서 평균 5%의 성능 향상을 가져 왔다.

공유메모리 다중처리기 시스템에서의 혼합형 캐쉬 프로토콜에 관한 연구

장우석(Woo seok Chang),서효중(Hyo jung Seo),장성태(Seong Tae Jhang),전주식(Ju Shik Jhon) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.1

공유버스를 기반으로한 다중처리기 시스템에서 공유데이타의 처리효율은 성능향상의 중요한 요소가 된다. 본 논문에서는 캐쉬의 처리단위를 라인과 서브라인으로 이원화하고, 공유라인 쓰기시에 무효화와 갱신 방식을 혼용함으로써, 융통성이 부가된 혼합형 캐쉬 일관성 프로토콜을 제시한다. 본 X 캐쉬 프로토콜의 효용은 응용프로그램의 실행궤적에 의한 모의실험을 통하여 검증된다. 모의실험의 결과는, 본 프로토콜이 최악의 상황에서도 Firefly 프로토콜에 근접한 캐쉬 성공률을 유지하면서, 버스 사용량은 Illinois 및 Firefly 프로토콜보다 적다는 사실을 보이고 있다.