기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
웜홀 방식의 네트워크에서 효율적인 다대다 개별적 통신 알고리즘
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 웜홀 방식의 네트워크에서 효율적인 다대다 개별적 통신 알고리즘
저자명
김시관,강오한,정종인
간행물명
정보과학회논문지. Journal of KIISE. 시스템 및 이론
권/호정보
2003년|30권 7호|pp.359-369 (11 pages)
발행정보
한국정보과학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

본 논문에서는 웜홀 라우팅 방식을 사용한 2차원 토러스에서 다대다 개별적 통신에 대한 효율적인 알고리즘을 제시한다. 다대다 개별적 통신은 집합체 통신(Collective Communication)의 일종으로 행렬 전이, FFT, 흑은 분산 테이블 검색과 같은 많은 응용 분야에 적용이 되고 있다. 이에 대한 연구는 망의 크기가 2의 멱승 혹은 4의 배수인 경우에 대한 알고리즘이 제시가 되었지만 그 크기가 일반적인 경우에 대해서는 아직은 제안되고 있지 않고 있다. 본 논문에서는 먼저 망의 크기가 2의 배수인 경우에 대한 다대다 개별적 통신에 대한 Double-Hop-2D 알고리즘을 제안한 다음 이 알고리즘을 확장하여 임의의 노드 수에 적합한 2개의 알고리즘을 제안한다. Split-and-Merge 알고리즘은 전체망을 4개의 지역으로 분할하여 각 분할된 영역이 독립적으로 영역별로 다대다 개별적 통신을 수행한 후 그 결과를 다시 결합하는 단계로 구성되어 있다. Modified Double-Hop-2D 알고리즘은 기본이 되는 Double-Hop-2D 알고리즘에서 추가적인 작업을 수행함으로써 다대다 개별적 통신을 수행한다. 마지막으로 망의 크기가 일반적인 경우에 Modified Double-Hop-2D 알고리즘이 Split-and-Merge 알고리즘보다 성능이 우수함을 보인다.

기타언어초록

We present efficient generalized algorithms for all-to-all personalized communication operations in a 2D torus. All-to-all personalized communication, or complete exchange, is at the heart of numerous applications, such as matrix transposition, Fast Fourier Transform(FFT), and distributed table lookup. Some algorithms have been Presented when the number of nodes is power-of-2 or multiple-of-four form, but there has been no result for general cases yet. We first present complete exchange algorithm called multiple-Hop-2D when the number of nodes is in the form of multiple-of-two. Then by extending this algorithm, we present two algorithms for an arbitrary number of nodes. Split-and-Merge algorithm first splits the whole network into zones. After each zone performs complete exchange, merge is applied to finish the desired complete exchange. By handling extra steps in Double-Hop-2D algorithm, Modified Double-Hop-2D algorithm performs complete exchange operation for general cases. Finally, we compare the required start-up time for these algorithms.