서지주요정보
2차원 메쉬에서 최적의 All-to-all 방송 알고리즘 = Optimal all-to-all broadcasting algorithms on 2-dimensional mesh
서명 / 저자 2차원 메쉬에서 최적의 All-to-all 방송 알고리즘 = Optimal all-to-all broadcasting algorithms on 2-dimensional mesh / 황효정.
저자명 황효정 ; Hwang, Hyo-Jung
발행사항 [대전 : 한국과학기술원, 1993].
Online Access 제한공개(로그인 후 원문보기 가능)원문

소장정보

등록번호

8004040

소장위치/청구기호

학술문화관(문화관) 보존서고

MCS 93054

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

An effective utilization of communication resources is crucial for good overall performance in multicomputer systems. All-to-all broadcasting problem, distribution of common message from each node to all other nodes, is one of the most popular communication patterns on multicomputer systems. In this thesis, we consider all-to-all broadcasting problems with d-port communication model in 2-dimensional mesch. In d-port communication model, each node on multicomputer systems can receive and send messages with two or more nodes concurrently. We propose two optimal all-to-all broadcasting algorithms for mxn meshconfigured multicomputer systems. One is for model with the buffer size n. We prove this algorithm is optimal in the number of communication steps and has time complexity O(m+n-2). The other is for model with the buffer size 1. We propose the methods of embedding the ring and the tree on mxn meshes and design the algorithm based on these methods. We prove that the ring and the tree embedded on mxn meshes using these methods are edge-disjoint and that the algorithm has the Time complexity O((mm-1)/2). This algorithm is optimal in the number of communication steps.

서지기타정보

서지기타정보
청구기호 {MCS 93054
형태사항 [iii], 55 p. : 삽도 ; 26 cm
언어 한국어
일반주기 부록 수록
저자명의 영문표기 : Hyo-Jung Hwang
지도교수의 한글표기 : 윤현수
지도교수의 영문표기 : Heun-Soo Yoon
학위논문 학위논문(석사) - 한국과학기술원 : 전산학과,
서지주기 참고문헌 : p. 51-53
주제 Multiprocessors.
Broadcasting.
Telecommunication.
Wire netting.
통신 방식. --과학기술용어시소러스
다중 컴퓨터. --과학기술용어시소러스
방송 알고리즘.
QR CODE qr code