본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

정보과학회논문지. Journal of KIISE. 시스템 및 이론 v.32 no.11/12, 2005년, pp.541 - 556  
본 등재정보는 저널의 등재정보를 참고하여 보여주는 베타서비스로 정확한 논문의 등재여부는 등재기관에 확인하시기 바랍니다.

다중 프로세서 시스템에서 프로세서 지역성을 이용한 원격 캐쉬 교체 정책
Remote Cache Replacement Policy using Processor Locality in Multi-Processor System

한상윤   (서울대학교 전기컴퓨터공학부UU0000691  ); 곽종욱   (서울대학교 전기컴퓨터공학부UU0000691  ); 장성태   (수원대학교 컴퓨터공학부UU0000815  ); 전주식   (서울대학교 전기컴퓨터공학부UU0000691  );
  • 초록

    컴퓨터 시스템에서의 메모리 접근 지연은 전체 시스템 성능에 큰 장애 요인 중 하나이다. 특히 분산 메모리 구조에서 지역 메모리와 원격 메모리의 접근 지연 시간은 큰 차이를 나타낸다. 원격 메모리 접근 지연으로 인한 성능 저하를 줄이고자 원격 메모리 영역만을 캐싱하는 원격 캐쉬가 제안되었으며, 원격 캐쉬는 프로세서 캐쉬와 더불어 다단계 캐쉬 형태로 구성된다. 일반적으로 상위 계층 캐쉬의 모든 내용을 하위 계층 캐쉬가 반드시 포함하는 다단계 캐쉬 내포성(MLI)을 지키는 다중 계층 메모리 구조에서 LRU 교체 정책을 사용할 경우, 하위 계층 캐쉬의 LRU 알고리즘에 따른 라인 교체로 인하여 상위 계층 캐쉬의 라인 교체가 일어날 패, 상위 계층 캐쉬로 요구된 라인 교체가 상위 계층 캐쉬 자체의 LRU 정보와 일치하지 않는 경우가 발생하며, 이로 인해 상위 캐쉬의 적중률이 저하되어 전체 시스템 성능이 저하된다. 본 논문은 원격 캐쉬를 추가시킨 분산 공유 메모리 구조 다중 프로세서 시스템의 성능 향상을 위해 LRU 캐쉬 교체 정책의 단점을 보완한 새로운 원격 캐쉬 교체 정책을 제안한다. 논문에서 제안하는 교체 정책은 LRU 정보에 부가하여 프로세서의 시간적 접근 지역성을 이용하여 교체할 캐쉰 라인을 선택하게 함으로써, 프로세서에서 자주 사용되는 원격 캐쉬 라인의 교체가 일어나지 않도록 하여 시스템의 성능 향상을 꾀한다. 시뮬레이션을 통한 성능비교 결과, 본 논문에서 제시한 원격 캐쉬 교체 정책은 기존의 LRU 교체 정책과 비교하여 평균 $3\%$ , 최대 $10\%$ 의 무효화 및 캐쉬 접근 실패를 감소시켰고, 이 결과 전체 시스템의 성능은 평균 $2.5\%$ , 최대 $3.5\%$ 향상되었다.


    The memory access latency of the system has been a primary factor of performance degradation in single-processor system and multi-processor system. The remote memory access latency takes a lot of overhead over the local memory access latency especially in the distributed shared-memory system. To resolve this problem, the multi-level cache architecture that contains a remote cache in the multi-processor system has been proposed. In this paper, we propose a new cache replacement policy that improves the performance of the multi-processor system with the remote cache. If the multi-level cache keeps the multi-level inclusion(MLI) property and uses the LRU(Least Recently Used) cache replacement policy, the LRU information of the higher-level cache(a processor cache) would be different with that of the lower-level cache(a remote cache). In this situation, the replacement of a remote cache line can induce the exchange of a processor cache line that is used by the processor. It is a main factor of performance degradation in a whole system. To alleviate this disadvantage of the LRU replacement polity, the new policy analyses tht processor's remote memory access pattern of each node and uses this information to reduce the number of invalidations of the useful cache line in the higher-level cache. The new replacement policy of the remote cache can improve the performance by $3.5\%$ in maximum and $2.5\%$ in average on SPLASH-2 benchmarks, compared to the general LRU cache replacement policy.


  • 주제어

    다중 프로세서 시스템 .   원격 캐쉬 .   LRU 캐쉬 교체 정책 .   다중 계층 캐쉬 내포성 .   원격 메모리 접근 패턴ㅂ .   프로세서 지역성.  

  • 참고문헌 (15)

    1. J. L. Hennessy and D.A Patterson, Computer Architecture : A Quantitative Approach, Third Edition, Morgan Kaufmann Publishers, Inc, 2003 
    2. Manuel E. Acacio, Jose Gonzalez, 'A Two-Level Directory Architecture for Highly Scalable ccNUMA Multiprocessors,' IEEE Transactions on Parallel and Distributed System, Vol. 16, No.1, January 2005 
    3. Zhang, Z. and J. Torrelas, 'Reducing Remote Conflict Misses : NUMA with Remote Cacae versus COMA,' In Proc. of the 3rd IEEE Symp. on High performance Computer Architecture (HPCA-3), pp. 272-281, Feb. 1997 
    4. 김형호, '지점간 링크를 이용한 스누핑 버스의 설계 및 성능 분석', 서울대학교 석사학위 논문, 1996 
    5. B. Nelson, J. Archibald, and K. Flanagan, 'Performance Analysis of Inclusion Effects in Multi-Level Multiprocessor Caches,' Proceedings of the Third IEEE Symposium, pp. 513-516, Dec. 1991 
    6. J.-L.. Bear and W.-H. Wang. 'On the inclusion properties for multi-level cache hierarchies,' In proceeding of 15th International Symp. on Computer Architecture, pp. 73-80, IEEE, 1988 
    7. 서효중, 장성태, 전주식, '내포성이 제거된 공유 캐쉬에 기반한 계층 버스 CC-NUMA 다중처리기', Journal of KISS A, vol. 25, no. 3, pp. 306-321, 1998 
    8. E. Cecchet, 'Parallel pull-based LRU : a request distribution algorithm for clustered Web caches using a DSM for memory mapped networks,' in Proceedings of the Cluster Computer and the Grid. IEEE/ACM International Symposium on, 15-18 May 2001 
    9. Wayne A. Wong and Jean-Loup Baer, 'Modified LRU Policies for Improving Second-level Cache Behavior,' In Proceedings of the 6th International Symposium on High-Performance Computer Architecture (HPCA), pp. 49-60, January 2000 
    10. J. Alghazo, A. Akaaboune, N. Botros, 'SF-LRU Cache Replacement Algorithm,' in Proceedings of Memory Technology, Design and Testing, 2004. Records of the 2004 International Workshop on, 9-10 Aug. 2004 
    11. D. Lee, J. Choi, H. Choe, Noh, S. Min, Y. Cho, 'Implementation and Performance Evaluation of the LRFU Replacement Policy,' In Proceedings of 23rd Euromicro Conference: New Frontiers of Information Technology-Short Contributions, September 01-04, 1997 
    12. Jeffrey D. Gee, Alan Jay Smith, 'Analysis of Multiprocessor Memory Reference Behavior,' in Proceedings of the IEEE International conference on, 10-12 Oct. 1994 
    13. P. Foglia, R. Giorgi and C.A. Prete, 'Simulation study of memory performance of SMP multiprocessors running a TPC-W workload,' in Proceedings of the IEE Proc. -Comput. Digit. Tech, Vol. 151, No.2, March 2004 
    14. J. E.Veenstra and R.J.Fowler. 'MINT : A Front End for Efficient Simulation of Shared-Memory Multiprocessors,' Proc., 2nd Int'l Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 201-207, Jan. 1994 
    15. S. Woo et al., 'The SPLASH-2 Programs: Characterization and Methodological Considerations,' In Proceedings of 22nd International Symposium on Computer Architecture, pp. 24-36, June 1995 

 저자의 다른 논문

  • 장성태 (16)

    1. 1995 "MI-MESI 쓰기-무효화 스누핑 캐쉬 일관성 유지 프로토콜" 정보처리논문지 = The transactions of the Korea Information Processing Society 2 (5): 757~767    
    2. 1999 "새로운 스누핑 프로토콜을 사용한 링 구조의 다중 프로세서 시스템" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (3): 313~323    
    3. 1999 "스누핑 프로토콜을 사용하는 NUMA 시스템의 계층적 링 구조로의 확장" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (11): 1305~1317    
    4. 2000 "링 구조 다중프로세서 시스템에서 링 대역폭 확장을 위한 효율적인 방안" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (2): 177~187    
    5. 2000 "CC-NUMA 시스템에서의 동기화 기법에 대한 성능 비교" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (4): 394~400    
    6. 2001 "링 구조 NUMA 시스템에서 디스크 입출력의 성능 향상을 위한 효율적인 방안" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 28 (3): 134~143    
    7. 2002 "이중 링 CC-NUMA 시스템에서 링 구조 변화에 따른 시스템 성능 분석" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (2): 105~115    
    8. 2002 "리피터 노드를 이용한 Scalable CC-NUMA 시스템" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (9): 503~513    
    9. 2003 "링 구조 NUMA 시스템에서 적응형 다중 그레인 원격 캐쉬 설계" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (9): 461~476    
    10. 2004 "NUMA 시스템에서 소유권에 근거한 원격 캐시 교체 정책" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 31 (8): 473~486    
  • 전주식 (24)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기