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

논문 상세정보

이질적인 분산 시스템에서의 개선된 브로드캐스트 알고리즘
Improved Broadcast Algorithm in Distributed Heterogeneous Systems

박재현   (서강대학교 컴퓨터학과UU0000674  ); 김성천   (서강대학교 컴퓨터학과UU0000674  );
  • 초록

    최근 이질적인 분산 컴퓨팅 환경 상에서의 공동 작업들이 나날이 늘어나고 있다. 고속의 원거리 네트워크의 유용성 (availability)은 화상 회의, 분산된 대화식의 시뮬레이션, 그리고 공동의 시각화(collaborative visualization)와 같은 공동의 멀티미디어 응용들을 가능하게 하였다. 이와 같은 응용들과 분산된 고성능 컴퓨팅에서의, 효율적인 그룹 통신은 매우 중요하다. 일반적인 그룹 통신으로는 브로드캐스트, 멀티캐스트 등이 있다. 기존의 FEF, ECEF, look-ahead 와 같은 휴리스틱 알고리즘들은 이러한 이질적 분산 시스템에서의 브로드캐스트와 멀티캐스트를 위한 메시지 전송 트리를 구성하여 준다. 하지만 이러한 알고리즘들은 각 단계에서의 최적의 해를 선택하기 때문에 지역적 최적해(local optimum)에 빠질 수 있는 단점이 있다. 본 논문에서는 노드와 네트워크 모두가 이질적인 기존의 통신 모델 상에서 보다 효율적인 집합적 연산을 위한 트리를 구성해주는 개선된 브로드캐스트 알고리즘을 제안한다. 기존의 휴리스틱 알고리즘들이 지역적 최적해에 빠질 수 있는 점을 감안하여, 보다 합리적이고, 유용성 있는 edge 선택 기준을 제시하였다. 여러 가지 통신비용에 대한 성능 평가를 통하여, 개선된 휴리스틱 알고리즘은 기존의 알고리즘보다 적은 완료 시간을 가지며, 특히 look-ahead 알고리즘보다 낮은 계산 복잡도를 가지는 장점을 가짐을 알 수 있다.


    Recently, collaborative works are increased more and more over the distributed heterogeneous computing environments. The availability of high-speed wide-area networks has also enabled collaborative multimedia applications such as video conferencing, distributed interactive simulation and collaborative visualization. Distributed high performance computing and collaborative multimedia applications, it is extremely important to efficiently perform group communication over a heterogeneous network. Typical group communication patterns are broadcast and Multicast. Heuristic algorithms such as FEF, ECEF, look-ahead make up the message transmission tree for the broadcast and multicast over the distributed heterogeneous systems. But, there are some shortcomings because these select the optimal solution at each step, it may not be reached to the global optimum In this paper, we propose a new heuristic algerian that constructs tree for efficiently collective communication over the previous heterogeneous communication model which has heterogenity in both node and network. The previous heuristic algorithms my result in a locally optimal solution, so we present more reasonable and available criterion for choosing edge. Through the performance evaluation over the various communication cost, improved heuristic algorithm we proposed have less completion time than previous algorithms have, especially less time complexity than look-ahead approach.


  • 주제어

    RT CORBA .   CORBA .   real time .   scheduling .   hard real time.  

  • 참고문헌 (8)

    1. I.Foster and C.Kesselman, 'Globus: A metacomputing infrastructure toolkit'. Intl. Journal of Supercomputer Applications, 11(2): pp.115-128, 1997 
    2. M.Banikazemi, V.Moorthy, and D.K.Panda, 'Efficient Collective communication on heterogeneous networks of workstations', Technical report OSU-CISRC-03/98-T07, Dept. of Computer and Information Science, The Ohio State University, March 1998 
    3. Mohammad Banikazemi, Jayanthi Sampathkumar, Sandeep Prabhu, Dhabaleswar K. Panda, P. Sadayappan, 'Communication Modeling of Heterogeneous Netwokrs of Workstations for Performance Characterization of Collective Operation', Proceedings of the Heterogeneous Computing(HCW '99), pp.125-133, April 1999 
    4. Nicholas T. Karonis, Bronis R. de Supinski, Ian Foster, William Gropp, Ewing Lusk, John Bresnahan, 'exploiting hierachy in parallel computer networks to optimize collective ooperation performance', Proceddings of the 14th International Parallel & Distributed Processing Symposium, pp.377-384, May 2000 
    5. Prashanth B. Bhat, C. S. Raghavendra, Viktor K.Prasanna, 'Efficient collective communication in distributed heterogeneous systems', Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, pp.15-24, May 1999 
    6. Pangfeng Liu, Da-Wei Wang, 'Reduction Optimization in Heterogeneous Cluster Environments', Proceedings of the 14th International Parallel & Distributed Processing Symposium, pp. 477-482, May 2000 
    7. M.Banikazemi, V.Moorthy, and D.K.Panda, 'Efficient Collective communication on heterogenous networks of workstations', in Proc. Intl.Conf. Parallel Processing, pp. 460-467, 1998 
    8. T.Anderson, D.Guller, and D.Patterson, 'A case for NOW(Networks of Workstations)', IEEE Micro, pp.54-64, february 1995 

 저자의 다른 논문

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

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