In future computing systems (or infrastructures), which are based not only on regular direct networks such as mesh or ring but also on switch-based irregular networks and mobile ad hoc networks,$\emph{collective communication}$ is a crucial issue because the collective communication among multiple nodes in a cooperating group usually constitutes the sequential or bottleneck park of parallel and mobile computing applications. In this research, we investigate two of the most important collective communication primitives, $\emph{barrier synchronization}$ and $\emph{multicast}$, which are easily applied to other collective communication functions such as total exchange or reduction.
First, we propose a $\emph{Barrier Tree for Meshes (BTM)$}$ to minimize the barrier synchronization latency for two-dimensional (2D) mesh systems. The proposed BTM scheme has two distinguishing features. One is that the synchronization tree is 4-ary. The synchronization latency of the BTM scheme is asymptotically $\theta$($log_4n$) while that of the fastest scheme reported in the literature is bounded between $\Omega$($log_3n$) and O($n^{1/2}$)where n is the number of member nodes. The other is that nonmember nodes are neither involved in the construction of a BTM nor actively participate in the synchronization operations, which avoids interference among different process groups during synchronization. Extensive simulation study shows that, for up to $64\times64$ meshes, the BTM scheme results in about 40~70% shorter synchronization latency, and is more scalable thatn conventional schemes.
Second, we propose a $\emph{Barrier Tree for Irregular Networks (BTIN)}$ and a barrier synchronization scheme using BTIN for switch-based cluster systems. The synchronization latency of the proposed BTIN scheme is asymptotically O(log n) while that of the fastest scheme reported in the literature is bounded by O(n), where n is the number of member nodes. According to our simulation results, for the group size of 256, the BTIN scheme improves the synchronization latency by a factor of 3.3~3.8. It is alsp shown to be more scalable than conventional schemes with less network traffic.
Third, we reevaluate the multicast protocols for mobile ad hoc networks in terms of energy efficiency and propose a new multicast protocol, called $\emph{Two-Tree Multicast (TTM)}$. According to our quantitative analysis, $\emph{mesh-based multicast}$ provides good general performance but consumes around $\frac{f+1}{2}$ times more energy than $\emph{tree-based multicast}$ because of broadcast-based flooding within the mesh, where f is $\emph{node connectivity ($f$\gg2$)}$. The proposed TTM consumes less energy than the mesh-based multicast by employing multi-destined unicast-based trees and alleviates the energy balance problem found in conventional single shared tree-based multicast (STM) with two trees, called $\emph{primary}$ and $\emph{alternative trees}$. Performance evaluation study shows that the proposed TTM saves energy consumption by a factor of 1.9~4.0 compared to the mesh-based multicast without having an adverse impact on the general performance. In terms of a combined performance metric ,$\emph{energy per delivered packed}$, TTM shows up to 80% and 40% better performance than the mesh-based multicast and STM, respectively.
메쉬나 링과 같은 정형 네트워크 뿐만 아니라 스위치 기반 비정형 네트워크 및 이동 애드혹 (ad hoc)네트워크에 기반을 둔 미래 컴퓨팅 시스템에서는, 그룹 내 다중 노드 사이의 집합 통신(그룹 통신)이 병렬 및 이동 컴퓨팅 응용 프로그램의 순차 수행 또는 병목 지점이 되기 때문에 집합 통신이 중대한 이슈이다. 본 연구에서는 두 가지의 가장 중요한 집합 통신 프리므티브인 배리어 동기화와 멀티캐스트를 다룬다. 이들은 전체 교환이나 리덕션과 같은 다른 집합 통신 함수에 쉽게 응용될 수 있다.
첫째, 2차원 메쉬 시스템에서 동기화 지연시간을 최소화하는 메쉬용 배리어 트리(BTM)를 제안한다 제안한 BTM 기법은 두 가지의 독특한 특성을 갖는다. 그 중 하나는 동기화 트리인 BTM이 4진 트리라는 것이다. 기존의 가장 빠른 기법의 동기화 지연시간이 $\Omega$($log_3n$)와 O($n^{1/2$)사이에 한정되는 반면에 BTM 기법의 동기화 지연시간은 $\theta$($log_4n$)이다. 여기서 n은 멤버 노드의 수이다. 다른 특성은 비 멤버 노드가 BTM의 생성에 관여하지 않고 동기화 동작에도 적극적으로 참여하지 않는다는 것이다. 이 특성은 동기화가 수행되는 동안 서로 다른 프로세스 그룹 사이의 간섭을 막아준다. 시뮬레이션 결과에 따르면, $64\times64$메쉬에 이르기까지 BTM기법이 기존의 기법에 비해 약 40~70% 짧은 동기화 지연시간을 나타내고 확장성 또한 우수하다.
둘째, 스위치 기반 클러스터 시스템을 위한 비정형 네트워크용 배리어트리(BTIN)와 BTIN을 이용한 배리어 동기화 기법을 제안한다. 기존의 가장 빠른 기법의 동기화 지연시간이 O(n)으로 제한되는 반면에 BTIN기법의 동기화 지연시간은 O(log n)으로 표현된다. 여기서 n은 멤버 노드의 수이다. 광범위한 시뮬레이션 수행 결과에 의하면, 그룹 크기 256에 대하여 BTIN기법이 기존의 기법에 비하여 동기화 지연시간을 3.3~3.8배 향상시킨다. 또한, BTIN기법은 보다 적은 네트워크 트래픽으로 기존 기법보다 우수한 확장성을 제공한다.
셋째, 이동 애드혹(ad hoc)네트워크를 위한 멀티캐스트 프로토콜올 에너지 효율성 측면에서 재평가하고 새로운 멀티캐스트 프로토콜인 이중 트리 멀티캐스트(TTM)기법을 제안하다. 정량적 해석에 의하면, 메쉬 기반 멀티캐스트는 일반 성능이 우수한 반면 메쉬 내 브로드캐스트 기반 플러딩 때문에 트리 기반 멀티캐스트에 비하여 $frac{f+1}{2}$배 많은 에너지를 소모한다. 여기서 f는 노드 연결성을 나타낸다.($f\gg2$). 제안한 TTM은 다중 수신 유니캐스트 기반 트리를 사용함으로써 메쉬 기반 멀티캐스트보다 적은 에너지를 소모하고, 사용 트리와 대기트리로 불리는 두 개의 트리를 이용하여 기존의 단일 공유 트리 멀티캐스트(STM)에서의 에너지 균형 문제를 완화시킨다. 성능 평가에 의하면, 제안한 TTM은 일반 성능에 미치는 역효과없이 메쉬 기반 멀티캐스트에 비하여 에너지 소모를 1.9~4.0배 절약한다. 복합 성능 척도인 전달 패킷당 에너지 측면에서는 TTM이 메쉬 기반 멀티캐스트 및 STM보다 각각 최대 80% 및 40% 우수한 성능을 나타낸다.
