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

논문 상세정보

Torus Ring : 계층 링 구조의 변형을 통한 상호 연결망의 성능 개선
Torus Ring : Improving Performance of Interconnection Networks by Modifying Hierarchical Ring

곽종욱   (서울대학교 전기컴퓨터공학부UU0000691  ); 반형진   (삼성전자CC0101996  ); 전주식   (서울대학교 전기컴퓨터공학부UU0000691  );
  • 초록

    다중 프로세서 시스템에서 노드 간의 연결을 제공하는 상호 연결망이 전체 시스템의 성능에서 차지하는 비중은 매우 크다 상호 연결망의 형태는 여러 종류가 있을 수 있으나 Mesh, 링, 계층 링 등의 형태가 많이 사용된다. 이 논문에서는 기존의 계층 링을 수정,한 Torus Ring을 제안한다. Torus Ring은 계층 링과 완전히 동일한 복잡도를 가지면서도 지역 링 간의 연결 방법만을 변경한 형태의 상호 연결망이다. 이 연결망은 역방향 인접 링에 대한 요청에서 홉 수의 이득을 봄으로써 평균 흡수를 감소시킨다. 또한 접근의 지역성을 고려하지 않은 균등분포의 가정 하에서도 평균 홉수의 기대값에서 계층링과 동일한 값을 가지며, 실제 병렬 프로그램이 수행되는 환경에서는 인접링에 대한 통신 비율이 증가할 가능성이 크기 때문에 더 큰 흡수의 이익을 기대할 수 있다. 이에 따라 상호 연결망의 요청과 웅답의 지연 시간이 최대 19 $\%$ 까지 감소하였으며, 이러한 웅답 지연 시간의 단축이 수행 시간을 최대 10 $\%$ 정도까지 감소시키는 결과를 가져왔다.


    In multiprocessor systems, interconnection network design is critical for overall system performance. Popular interconnection networks, which are generally considered, are meshes, rings, and hierarchical rings. In this paper, we propose (')Torus Ring('), which is a modified version of hierarchical ring. Torus Ring has the same complexity as the hierarchical rings, but the only difference is the way it connects the local rings. It has an advantage over the hierarchical rings when the destination of a packet is the neighbor local ring in the reverse direction. Though the average number of hops in Torus Ring is equal to that of the hierarchical rings when assuming the uniform distribution of each transaction, the benefits of the number of hops are expected to be larger because of the spatial locality in the real environment of parallel programming. In the simulation results, latencies in the interconnection network are reduced by up to 19 $\%$ , and the execution times are reduced by up to 10 $\%$ .


  • 주제어

    다중 프로세서 시스템 .   상호 연결망 .   링 연결망 .   계충 링 연결망 .   망 토폴로지.  

  • 참고문헌 (17)

    1. David E. Culler and Jaswinder Pal Singh with Anoop Gupta, 'Parallel Computer Architecture : A Hardware/Software Approach,' Morgan Kaufmann Publishers, Inc, 1998 
    2. Sung Woo Chung, Seong Tae Jhang and Chu Shik Jhon, 'PANDA : Ring-Based Multiprocessor System using New Snooping Protocol,' In The Proceeding of ICPADS'98, pp 10-17, Dec. 1998 
    3. Byoung Soon Jang, Sung Woo Chung, Seong Tae Jhang and Chu Shik Jhon, 'Efficient Schemes to Scale the Interconnection Network Bandwidth in a Ring-based Multiprocessor System,' SAC-2001(16th ACM Symposium on Applied Computing), Las Vegas, United States, pp.510-516, March 2001 
    4. G. Ravindran and M. Stumm, 'A performance comparison of hierarchical ring- and meshconnected multiprocessor networks,' Third International Symposium on High-Performance Computer Architecture, pp. 58-69, Feb 1997 
    5. G. Ravindran and M. Stumm, 'On topology and bisection bandwidth of hierarchical-ring networks for shared-memory multiprocessors,' 5th International Conference On High Performance Computing, pp. 262-269, Dec 1998 
    6. Z.G. Vranesic, M. Stumm, D.M. Lewis and R. White, 'Hector: a hierarchically structured shared-memory multiprocessor,' Computer, Vol.24, Iss.1, pp. 72-79, Jan. 1991 
    7. R. Grindley, T. Abdelrahman, S. Brown, S. Caranci, D. DeVries, B. Gamsa, A. Grbic, M. Gusat, R. Ho, O. Krieger, G. Lemieux, K. Loveless, N. Manjikian, P. McHardy, S. Srbljic, M. Stumm, Z. Vranesic and Z. Zilic, 'The NUMAchine multiprocessor,' Proceedings of International Conference on Parallel Processing, pp. 487-496, 2000 
    8. Dongho Yoo, Inbum Jung, Seung Ryoul Maeng and Hyunglae Roh, 'Multistage ring network: a new multiple ring network for large scale multiprocessors,' Proceedings of International Workshops on Parallel Processing, pp. 290-294, 1999 
    9. Guihai Chen and F.C.M. Lau, 'Shuffle-Ring: overcoming the increasing degree of hypercube,' Proceedings of Second International Symposium on High-Performance Computer Architecture, pp. 130-138, Feb 1996 
    10. 'Recursive cube of rings: a new topology for interconnection networks,' Y. Sun, P.Y.S. Cheung, X. Lin, IEEE Transactions on Parallel and Distributed Systems, Vol.11, Iss.3, pp, 275-286, Mar 2000 
    11. 성현중, 김형호, 장성태, 전주식, '스누핑 프로토콜을 사용하는 NUMA 시스템의 계층적 링 구조로의 확장', 정보과학회 논문지(A), pp. 1305-1317, Vol. 26, No. 11, Nov. 1999 
    12. 경진미, 김인석, 김봉준, 장성태 '리피터 노드를 장착한 이중 링 CC-NUMA 시스템', 한국정보과학회:학술대회지, 2002, 10 v.2002, n.한국정보과학회 02 가을 학술발표논문집(1), pp.697-699 
    13. W.J, Dally, 'Virtual-Channel Flow Control,' IEEE Trans. Parallel and Dist. Sys., vol. 3, no. 2, pp. 194-205, Mar. 1992 
    14. G. Ravindran, 'Performance Issues in the Design of Hierarchical-ring and Direct Networks for Sharedmemory Multiprocessors,' Ph.D. Dissertation, Department of Electrical and Computer Engineering, University of Toronto, Jan 1998 
    15. Vijai S. Pai, Parthasarathy Ranganathan and Sarita V. Adve, 'RSIM Reference Manual,' Dept. of Electrical and Computer Engineering, Rice University, Technical Report 9705, 1997 
    16. J. P. Singh, W. D. Weber, and A. Gupta, 'Splash: Stanford parallel applications for shared memory,' Tech. Rep. CSL-TR-91-469, Stanford University, 1991 
    17. Steven Cameron Woo, Moriyoshi Ohara, Evan Torrie, Jaswinder Pal Singh, and Anoop Gupta, 'The SPLASH-2 Programs: Characterization and Methodological Considerations,' Proceedings of the 22nd International Symposium on Computer Architecture, 1995 

 저자의 다른 논문

  • 전주식 (24)

    1. 1999 "새로운 스누핑 프로토콜을 사용한 링 구조의 다중 프로세서 시스템" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (3): 313~323    
    2. 1999 "스누핑 프로토콜을 사용하는 NUMA 시스템의 계층적 링 구조로의 확장" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (11): 1305~1317    
    3. 2000 "음성 인식을 이용한 증권 정보 검색 시스템의 개발" 정보과학회논문지. Journal of KISS : Computing practices. 컴퓨팅의 실제 6 (4): 403~410    
    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. 2003 "공유메모리 다중프로세서 시스템의 다중 프로그래밍 모의실험 기법" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (3): 194~204    
    9. 2003 "링 구조 NUMA 시스템에서 적응형 다중 그레인 원격 캐쉬 설계" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (9): 461~476    
    10. 2004 "NUMA 시스템에서 소유권에 근거한 원격 캐시 교체 정책" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 31 (8): 473~486    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

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