2차원 메쉬 상에서 최적의 All - to - All 방송 알고리즘 = Optimal All - to - All Broadcasting Algorithms on 2 - Dimensional Meshes

국문 초록 (Abstract)

다중 컴퓨터의 성능을 극대화하기 위해서는 효율적인 통신 자원의 이용이 필수적이다. All-to-all 방송은 다중 컴퓨터 시스템에서 많이 사용되는 통신 형태로서 다중컴퓨터 시스템 내의 모든 노드들이 다른 모든 노드들에게 자신의 정보를 전달하는 통신형태이다. 본 논문에서는 각 노드가 가지고 있는 모든 포트로 동시에 메시지를 주고 받을 수 있는 d-포트 통신 모델의 가정 하에 2차원 메쉬 상에서 최적의 시간 내에 all-to-all 방송을 할 수 있는 알고리즘을 제안한다. 본 논문에서는 메쉬에 특정한 형태의 트리를 embedding 하는 방법을 제안하고 embedding 된 링과 트리가 edge-disjoint 함을 증명한 후 제안된 링과 트리를 이용한 all-to-all 방송 알고리즘이 최적의 시간내에 수행됨을 증명한다.

목차 (Table of Contents)

• 요약
• 1. 서론
• 2. 기본 정의
• 3. 정방형 메쉬 상에서의 All - to - All 방송
• 4. 결론
• 참고문헌