Massively parallel computers (MPC) are characterized by the distribution of memory among an ensemble of nodes. Since memory is physically distributed, MPC nodes communicate by sending data through a network. In order to program an MPC, the user may directly invoke low-level message passing primitives, may use a higher-level communications library, or may write the program in a data parallel language and rely on the compiler to translate language constructs into communication operations. Whichever method is used, the performance of communication operations directl affects the total comutation time of the parallel application. Communication operations may be either point-to-point, which involves a single source and a single destination, or collective, in which more than two processes participate.
This thesis discusses the disign of collective communication operations for current systems that use the wormhole routing switching strategy, in which messages are divided into small pieces and pipelined through the network. Compared to the store-and-forward switching method that was used in early multicomputers, wormhole routing often reduces the effect of path length on communication latency. Over the past several years, this propert in the design of new collective communication algorithms, which differ fundamentally from their store-and-forward predecessors, has been widely exploited. This thesis discusses the significant issues involved in wormhole-routed collective communication and presents the major classes of solutions that have been proposed to address the problem.
First, multicast algorithms that minimize node contention are presented so that multiple multicast messages can be implemented with reduced latency. By exploiting available channels evenly as much as possible, these new algorithms show better performance than the existing multicast algorithms for wormhole 2D systems when multiple multicasts are involved.
All multicast algorithms presented are proven to be deadlock-free. A simulation study has been conducted that compared the performance of these multicast algorithms under various situations in a 2D mesh. We show that the overall performance of ours are up to 2~30% better than the previous studies. In addition, we observe that minimizing the number of the generated multidestination messages not always lead to shorter message latency. These proposed algorithms can be easily extended to 3D mesh systems.
All-to-all personalized communication, or complete exchang, is at the heart of numerous applications, such as matrix transposition, fast Fourier Transform(FFT), and distributed table lookup. We present an efficient all-to-all personalized communication algorithm for a 2D torus in wormhole-routed networks. Our complete exchange algorithm adopts divide-and-conquer approach to reduce the number of start-up latency significantly, which is a good metric for network performance in wormhole networks. We divide the whole network into 2×2 basic cells. After specially designated nodes called master nodes have collected messages to transmit to the rest of the basic cell, only master nodes perform complete exchange with reduced network size, $\frac{N}{2}×\frac{N}{2}$. When finished with this complete exchange in master nodes, these nodes distrubute messages to the rest of the master node, which results in the desired complete exchange communication.
After we present our complete exchange algorithms, we analyze time complexities and compare our algorithms with several previous algorithms. Our results show that proposed algorithms are efficient by a foctor of 2 in the required start-up time which means that our algorithm is suitable for wormhole-routed networks.
대규모 병렬 컴퓨터(Massively Parallel Computers)는 여러개의 노드에 기억장치를 분배시켜 두는 특징을 가지고 있다. 기억장치가 물리적으로 분산되어 있기 때문에 병렬 컴퓨터는 망을 통해서 자료를 전달할 수 있다. 병렬 컴퓨터 상에서 프로그램을 하기 위해서는 프로그래머는 저수준의 메시지 전달 명령어를 사용하거나 고수준의 통신 라이브러리를 사용하거나 병렬 데이타 언어를 사용하여 컴파일러가 해당 언어를 적절한 통신 명령어로 변환하도록 할 수 있다. 어떤 방법을 사용하든지 통신 명령의 성능은 응용 프로그램의 총 수행시간에 아주 큰 영향을 미치게 된다. 통신 명령의 형태는 한 개의 원천지와 한 개의 목적지가 관여된 점대점 통신과 두개 이상의 프로세스가 관여된 집합체 통신이 있다.
본 논문에서는 메시지를 플릿 단위로 잘라서 파이프라인 방식으로 망에 전달하는 웜홀방식을 사용한 컴퓨터에서 집합체 통신을 설계하는 방법에 대하여 설명한다. 저장 후 전달 방식을 사용하는 기존의 컴퓨터 시스템과 비교해 볼 때 웜홀 방식은 통신 지연시간을 줄일 수가 있다. 지난 수년간 저장 후 전달 방식을 사용하는 기존의 컴퓨터 시스템과 근본적으로 다른 새로운 집합체 통신의 설계에 대한 연구가 진행되어 왔으며 웜흘 방식의 특징을 최대한 활용하는 기법을 제시한다.
웜홀망의 성능에 영향을 미치는 가장 중요한 요소는 개시지연 시간인데 다중 멀티캐스트 메시지의 개시지연 시간을 단축하기 위하여 노드간의 메시지 충돌을 최소화하는 효율적인 멀티캐스트 전송 알고리즘을 제안한다. 제안되는 3가지의 알고리즘은 사용 가능한 채널들을 되도록 균등하게 사용함으로써 기존 제안된 알고리즘보다 우수한 성능을 보인다. 제안된 알고리즘들이 교착상태가 없음을 증명하고 2차원 메쉬망에서의 여러가지 조건하에서 제안된 알고리즘의 우수함을 시뮬레이션을 통하여 증명한다. 제안 알고리즘의 전반적인 성능은 기존 알고리즘보다 20%정도 우수함을 알수있다. 제안된 2차원 메쉬 다중 멀티캐스트 알고리즘은 3차원 메쉬망으로 확장이 용이하다.
완전교환 통신은 행렬전이, 푸리에변환 혹은 분산 테이블 검색과 같은 여러가지 응용에서 아주 많이 활용되는 통신 방법이다. 본 논문은 웜홀 방식을 채용한 2차원 토러스에서의 개시 지연 시간을 줄이기 위하여 분할 및 합병(divide-and-conquer)방식을 사용한 효율적인 완전교환 통신 알고리즘을 제안한다. 전체망은 2×2 형태의 기본셀로 분할한 뒤 각 기본셀에서는 마스터노드라고 불리는 특정 노드를 지정하여 기본셀내의 여타 노드들의 메시지를 이 마스터노드가 수집한다. 이 마스터노드들이 다른 모든 노드로 보내질 메시지를 수집한 뒤 각 기본셀내의 모든 마스터 노드들만이 가상 망을 형성하여 망의 크기가 $\frac{N}{2}×\frac{N}{2}$으로 줄어든 상태로 완전 교환 알고리즘을 수행한다. 마스터노드들간의 완전교환 연산을 수행한 뒤 이 마스터노드들은 자기가 전담했던 여타 노드들의 메시지를 재분배해 줌으로써 주어진 완전교환 연산을 완료한다. 기존의 여러가지 알고리즘과의 비교 분석을 제시하였으며 제시한 알고리즘이 약 2배 정도의 개시 지연시간면에서 우수함을 보인다.
