Quicksort에 근거한, 연결망의 구성에 따른 Multicluster 시스템의 성능 분석 = A Study on the Impact of Network Topology on the Performance of Multicluster Systems Based on Quicksort

국문 초록 (Abstract)

본 논문에서는 주어진 응용 앨고리즘을 수행하는데 소요되는 총 시간을 시스템의 성능으로 정의하여 다중처리 시스템에 있어서 프로세서간의 상호연결망이 시스템의 성능에 미치는 영향을 비교 분석하고 있다.
우선 疎결합형 다중처리시스템의 모형을 제시하고 그 시스템의 연결망으로 고려될 수 있는 ring, tree, mesh의 세가지 네트워크 형태를 선정하여 각각에 대해 데이터 전송에 소요되는 시간(communication time)에 관한 모델을 구한다. 데이터전송에 소요되는 시간을 모델링 하는데 있어서 quicksort 앨고리즘을 성능 비교용(benchmark) 앨고리즘으로 택하였다.
그리고 각 연결망별로 데이터 전송에 소요되는 시간을 포함한 benchmark 앨고리즘의 총수행시간에 관한 모델을 구하여 시뮬레이션에 사용하였다. 시뮬레이션 결과 비교의 대상이 된 세가지 연결망 형태들 중 통신 overhead를 포함한 총수행시간과 프로세서 수의 증가에 따른 속도향상 효과의 측면에서 모두 mesh 연결망으로 구성되는 시스템이 가장 우수한 성능을 보여 주었으며 상대적으로 ring 연결망으로 구성되는 시스템의 성능이 가장 저조한 것으로 나타났다.

다국어 초록 (Multilingual Abstract)

This paper studies the effect of communication overhead on the performance of multiprocessor systems.
A general organization of loosely coupled multiprocessor systems, called Multicluster, is used as the model architecture for this study. Three types of network topology, ring, tree, and mesh, are chosen as the candidates for the interconnection network of the model architecture, and their relative superiority is examined.
With the quicksort algorithm as benchmark, a mathematical model for the communication overhead is derived for each of the three network types. Then, the performance model, which represents the total execution time for the benchmark algorithm including communication overhead, is obtained for each network type. A series of simulation is carried out based on the performance model. The results of simulation show that a mesh connected system would give the best performance for the given task.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. 서론
• 2. Multicluster의 구성
• 3. 병렬 quicksort 앨고리즘 및 그 수행시간 해석
• 4. 시뮬레이션 결과 및 고찰
• 5. 결론
• 참고문헌
• 저자소개