다단계 상호 연결망에 기초된 ATM 스위치에서 효율적인 두단계 멀티캐스트 알고리즘

맹승렬(Seung Ryoul Maeng),박재형(Jaehyung Park),유동호(Dongho Yoo),윤현수(Hyunsoo Yoon),은성배(Sungbae Eun) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.12

본 논문에서 비동기적 전송 모드(asynchronous transfer mode) 스위치 구조를 구성하기 위한 자체 라우팅(self-routing) 특성을 갖는 다단계 상호 연결망에서 멀티캐스트 통신에 대해서 연구한다. ATM 스위치의 많은 응용 분야에서 기존의 점대점 통신 뿐만 아니라 멀티캐스트 통신도 요구한다. 이러한 멀티캐스트 통신은 하나 출발점에서 임의의 도착점으로 같은 메시지를 보내는 방법으로 케이블 TV, 원격회의, 요구형 비디오 서비스를 포함하는 공동적인 작업을 요구하는 통신을 제공하는데 기반이 된다. 본 논문은 멀티캐스트 라우팅 헤더를 적고 고정되게 구성하는 제한적 주소 인코팅 방식과 원하는 목적지로 멀티캐스트 패킷을 보내기 위해서 연결망을 순회하는 재귀적인 기법을 기반으로 하여 멀티캐스트 통신을 지원하는 접근방법을 제시한다. 또한 다단계 상호 연결망에 기초된 ATM 스위치에서 교착상태가 없는 두단계 멀티캐스트 알고리즘을 제안한다. 제안한 알고리즘의 성능은 연결망을 순회하는 횟수와 멀티캐스트 통신을 위해서 사용되는 링크의 수로 평가하였다. 본 멀티캐스트 알고리즘은 버퍼가 있는 다단계 상호 연결망에 기초된 ATM 스위치에도 적용할 수 있다. In this paper, we study the multicast communication in the self-routing multistage interconnection network(MIN) for constructing asynchronous transfer mode(ATM) switch architectures. Many of these applications require multicast communications in addition to conventional point-to-point communications. Multicast communication which the same message is delivered from a source to an arbitrary number of destinations, is fundamental in supporting collective communication primitives including cable TV, teleconferencing, and video-on-demand(VOD) services. This paper presents a novel approach to supporting multicast communication, on the basis of the restricted address encoding scheme which constructs a short fixed-size multicast header and the recursive scheme that recycles a multicast packet one or more times through the network to reach at desired destinations. We also propose two-pass multicast algorithms providing deadlock-freedom in MIN-based ATM switches. The emphasis is on evaluating the performance of these algorithms in terms of the number of recycling passes and the number of links used. The proposed algorithms can easily be applied to buffered MIN-based ATM switches.

무효화 힌트를 이용하여 읽기 접근시간을 줄이는 캐쉬 일관성 유지 프로토콜

오승택(Seung-Taek Oh),이윤석(Yun-Seok Rhee),맹승렬(Seung-Ryoul Maeng),이준원(Joon-Won Lee) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.1A

대규모 분산 공유메모리 다중처리기는 공유메모리 접근 지연시간이 크다는 약점을 지니고 있다. 이러한 다중처리기에서 모든 메모리 요청이 홈노드를 이루어지는 디렉토리 기반의 캐쉬 일관성 유지 기법의 사용은 메모리 접근 지연시간을 더욱 크게하는 요인으로 작용한다. 뿐만 아니라 메모리 접근 지연시간은 시스템의 규모가 커질수록 전체 성능에 중요한 요소로 작용하므로, 대규모 시스템에서 이를 줄이기 위해서 많은 연구들이 있었다. 본 논문에서는 메모리 읽기 지연시간을 줄이는 새로운 캐쉬 일관성 유지 기법을 제안한다. 제안된 기법은 무효화힌트를 이용하여 구현되었다. 무효화힌트는 어떤 노드가 전에 캐쉬블록을 무효화시켰는가에 관한 정보이며, 메모리블록이 필요한 노드는 이 정보를 이용하여 홈노드의 도움없이 직접 메모리 요청을 할 수 있다. 제안된 프로토콜이 성능을 측정하기 위하여 모의실험을 하였다. 모의실험 결과는 제안된 프로토콜에서 읽기 지연시간이 감소하는 것을 나타낸다.

컴파일시 생성된 여러개의 선형 순서를 가지는 AND / OR 프로세스 모델에 관한 연구

박승운(Seung Woon Park),김승범(Seung Beom Kim),맹승렬(Seung Ryoul Maeng) 한국정보과학회 1987 정보과학회논문지 Vol.14 No.2

본 논문에서는 AND/OR 프로세스 모델의 수행시 부담을 줄이기 위해 컴파일시에 수행 순서를 생성하도록 하였다. 가능한 입력 바인딩 패턴에 따라 heuristic한 규칙에 의해 여러개의 가능한 선형 순서가 만들어지며, 수행시에는 바디리터럴을 풀기위해 그중 하나가 선택된다. 각각의 선형 순서는 적합한 데이터 종속 관계를 만들어내기 때문에 거의 최적의 AND 병렬성을 추구할 수 있으며, 이것은 기존의 다른 컴파일 방식들보다 우수하다. 때로는 AND 병렬성이 제한되는 경우가 있으나, 수행시 부담을 줄임으로써 보상될 수 있다. 전방향 및 후방향 수행을 위한 수행시 제어도 간단한 자료 구조에 의해서 효과적으로 제어된다. The AND/OR process model is modified to reduce the runtime overhead in this thesis. In the proposed model, the run time overhead for literal ordering is reduced by generating the execution orders ill compile time. Several possible ordered lists are generated in compile time with several heuristic rules according to the possible input binding patterns and one of them is selected in run time to solve the body literals. Because each ordered list can generate the proper data dependencies, the heady optimal AND parallelism can be exploited, which is better than the other compile approaches. Though this approach may restrict AND parallelism in some cases, it can be compensated by reducing the run time overhead. The run time control for the forward and backward executions is managed simply and efficiently by a simple data structure.

개인휴대 통신망에서 공간적 국부성을 이용한 위치추적 방법

이종민,권보섭,맹승렬,Lee, Jong-Min,Kwon, Bo-Seob,Maeng, Seung-Ryoul 한국정보처리학회 2003 정보처리학회논문지 C : 정보통신,정보보안 Vol.10 No.2

무선단말기 사이의 호 연결을 위하여 유휴상태에 있는 무선단말기의 위치정보를 관리하는 위치추적방법이 사용된다. 본 논문에서는 움직임에 기반한 위치추적방법의 성능을 더욱 향상시키기 위하여 공간적 국부성을 이용한 위치추적방법을 제안한다. 제안한 방법은 무선단말기의 실제 이동경로에서 공간적 국부성을 제거하여 가상 이동경로를 생성한 후 이를 이용하여 위치 갱신함으로써 불필요한 위치갱신을 줄일 수 있게 한다. 컴퓨터 모의실험을 통하여 본 논문에서 제안한 방법이 위치추적경비를 많이 줄일 수 있음을 보여준다. Location tracking is used to keep track of the location information of a mobile terminal in an idle state for a call setup between mobile terminals. In this paper, we introduce a new location tracking strategy that utilizes spatial locality to have better performance than a movement based location tracking strategy. We reduce a lot of unnecessary location updates by updating the location information of a mobile terminal using the virtual movement path, which is generated after removing spatial localities in the actual movement path. Simulation results show that the proposed strategy greatly reduces the overall location tracking cost.

호도착기록에 기반한 위치갱신 알고리즘의 성능 분석

이종민,권보섭,맹승렬,Lee, Jong-Min,Kwon, Bo-seob,Maeng, Seung-Ryoul 한국정보처리학회 2003 정보처리학회논문지 A Vol.10 No.4

Location tracking is used to keep track of the location information of a mobile terminal in an idle state for a cail setup between mobile terminals. In this paper, we introduce a location update algorithm based on the call arrival history, which is appropriate for a variable call arrival rate over time. The location tracking strategy which uses the proposed algorithm can find changes in the call arrival rate by maintaining a call arrival history of a mobile terminal, from which a mobile terminal can calculate an appropriate timeout interval for a variable call arrival rate. We show that the proposed scheme is appropriate for a variable call arrival rate by presenting a simple analytical model and analytical results to investigate its performance for both a fixed and a variable call arrival rate. 무선단말기에 도착하는 호의 연결을 위해서 유휴상태에 있는 무선단말기의 위치정보를 관리하는 위치추적 방법이 사용된다. 본 논문에서는 시간이 지남에 따라서 호도착율이 변화할 때에 적합한 호도착기록에 기반한 위치갱신 알고리즘을 제안한다. 이 알고리즘을 사용한 위치추적방법은 무선단말기의 호도착기록을 사용하여 호도착율의 변화를 파악하고, 이를 사용하여 현재의 호도착율에 적합한 타임아웃 주기를 계산한다. 그리고 이 방법에 대한 성능을 평가하기 위하여 고정/가변 호도착율에 대한 분석 모델과 그에 따른 분석 결과를 제시함으로써 호도착율의 변화에 적합함을 보인다.

HIMIPv6: 광대역 무선 통신 네트워크를 위한 효율적인 IP 이동성 관리 프로토콜

정현구,김영탁,맹승렬,채영수,Jeong Hyeon-Gu,Kim Young-Tak,Maeng Seung-Ryoul,Chae Young-Su 한국통신학회 2006 韓國通信學會論文誌 Vol.31 No.4B

최근 들어 휴대형 무선 기기들의 보급이 확대되고 WiBro/WiMAX/HSDPA 등의 고속 무선 데이터 통신 시스템의 등장에 따라 무선 환경에서 인터넷을 효과적으로 사용할 수 있는 이동성 관리 프로토콜에 대한 관심이 증가하고 있다. MIPv6(mobile IPv6)는 IPv6 환경에서 이동성을 지원하기 위한 프로토콜로 제안되었고, 이동이 빈번한 셀룰라 환경에서 효율적인 이동성 지원을 위해서 MIPv6의 핸드오버 성능을 개선한 HMIPv6(hierarchical MIPv6)와 FMIPv6(fast handovers for MIPv6) 등의 새로운 프로토콜에 대한 연구가 활발히 이루어지고 있다. 본 논문에서는 HMIPv6의 계층구조를 이용한 효율적 이동성 관리의 장점과 FMIPv6의 선행적 (proactive) 핸드오버 지원에 의한 끊임없는 서비스 지원의 장점을 효과적으로 결합하여 이동이 빈번한 셀룰러 환경에 적합한 새로운 이동성 관리 프로토콜인 HIMIPv6(highly integrated MIPv6)를 제안한다. HIMIPv6는 선행적 이동성 관리를 하위 도메인내의 핸드오버뿐만 아니라 하위 도메인간의 핸드오버에도 적용함으로써 시스템 전체적인 이동성 관리성능을 개선하였다. NS-2 시뮬레이션에 의한 성능 분석은 HIMIPv6가 빈번한 핸드오버 환경에서도 MIPv6, FMIPv6, 그리고 HMIPv6보다 이동성 지원에 필요한 신호 부하를 작게 발생시키고 핸드오버 상황에서의 서비스 끊김 현상이나 패킷 손실률도 작음을 보여준다. With the increasing deployment of mobile devices and the advent of broadband wireless access systems such as WiBro, WiMAX, and HSDPA, an efficient IP mobility management protocol becomes one of the most important technical issues for the successful deployment of the broadband wireless data networking service. IETF has proposed the Mobile IPv6(MIPv6) as the basic mobilitymanagement protocol for IPv6 networks. To enhance the performance of the basic MIPv6, researchers have been actively working on HMIPv6 and FMIPv6 protocols. In this paper, we propose a new mobility management protocol, HIMIPv6 (Highly Integrated MIPv6), which tightly integrates the hierarchical mobility management mechanism of the HMIPv6 and the proactive handover support of the FMIPv6 to enhance the handover performance especially for the cellular networking environment with high frequent handover activities. We have performed extensive simulation study using ns-2 and the results show that the proposed HIMIPv6 outperforms MIPv6, FMIPv6 and HMIPv6 in terms of signaling overhead, service interruption and packet lost during handovers.

확장 가능한 두 단계 프로토콜을 이용한 상호 협력 캐쉬의 쓰기 성능 향상

황인철(In-Chul Hwang),맹승렬(Seung-Ryoul Maeng),조정완(Jung-Wan Cho) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.1

요즘 네트웍과 PC의 성능이 향상됨에 따라 값싼 PC를 빠른 네트웍으로 묶어 높은 성능을 얻고자 하는 클러스터 시스템에 대하여 많이 연구 되어 왔다. 이러한 연구의 한 분야로서 클러스터 I/O 하위 시스템의 성능을 향상시키고자 하는 상호 협력 캐쉬가 제시되었다. 기존 상호 협력 캐쉬에 대한 연구는 주로 효율적인 캐쉬 공유 기법에만 집중되어있고 쓰기 성능에 대한 고려는 하지 않고 있다. 또한 대부분의 읽기 데이터는 상호 협력 캐쉬를 통하여 처리되지만 쓰기 데이터는 디스크에 접근하기 때문에 쓰기가 병목현상이 될 수 있다. 따라서 상호 협력 캐쉬에서 읽기 뿐 아니라 쓰기 성능 향상 기법에 대한 연구가 필요하다. 본 논문에서는 상호 협력 캐쉬에서 쓰기 성능 향상 기법으로 확장 가능한 두 단계 프로토콜을 제시한다. 확장 가능한 두 단계 프로토콜은 기존 두 단계 프로토콜과 같이 파일에 읽기 쓰기 접근을 연속된 읽기/쓰기 단계로 나누고 쓰기 단계에서 연속된 쓰기사이의 불필요한 동작을 제거할 뿐 아니라 쓴 데이터에 대한 일시적 버퍼링을 수행함으로서 쓰기 성능을 향상시킨다 그리고 확장 가능한 두 단계 프로토콜을 상호 협력 클러스터 파일 시스템의 홈 기반 상호 협력 캐쉬에 적용하여 성능을 비교 분석한다.

KDSM(KAIST Distributed Shared Memory) 시스템의 설계 및 구현

이상권,윤희철,이준원,맹승렬,Lee, Sang-Kwon,Yun, Hee-Chul,Lee, Joon-Won,Maeng, Seung-Ryoul 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.5

본 논문에서는 KDSM(KAIST Distributed Shared Memory) 시스템의 설계 및 구현에 관해서 설명한다. KDSM은 Linux 2.2.13 상에서 실행되는 사용자 수준 라이브러리로 구현되었고, TCP/IP를 기반 통신 구조로 사용한다. KDSM은 페이지 기반 무효화 프로토콜(page-based invalidation protocol)과 다중 쓰기 프로토콜(multiple writer protocol)을 기반으로 하고, HLRC(Home-barred Lazy Release Consistency) 메모리 일관성 모델을 사용한다. KDSM의 성능을 측정하기 위해서 4개의 과학계산용 응용 프로그램을 실행하여 JIAJIA와 성능 비교를 하였다. 그 결과, 2개의 응용은 같은 결과를 냈고, 나머지 2개는 KDSM의 성능이 우수하였다. In this paper, we give a detailed description of KDSM(KAIST Distributed Shared Memory) system. KDSM is implemented as a user-level library running on Linux 2.2.13, and TCP/IP is used for communication. KDSM uses page-based invalidation protocol, multiple-writer protocol, and supports HLRC(Home-based Lazy Release Consistency) memory consistency model. To evaluate performance of KDSM, we executed 4 scientific applications and compared the result to JLAJLA. The results showed that performance of KDSM almost equal to JIAJIA for 2 applications and performance of KDSM is better than JIAJIA for 2 applications.

Myrinet 상에서 VMMC를 기반으로 하는 효율적인 MPI 구현 (pp.539-547)

김호중(Ho-joong Kim),맹승렬(Seung Ryoul Maeng) 한국정보과학회 2001 정보과학회 컴퓨팅의 실제 논문지 Vol.7 No.5

클러스터 시스템의 성능을 향상시키기 위해서는 Myrinet과 같은 고성능 통신망 인터페이스가 필수적이다. 그러나 Myrinet에서 동작하는 저수준 통신 계층들은 각기 고유한 통신 방식을 사용하므로 호환성이 떨어진다. 따라서 MPI와 같은 통신 프로그래밍 표준을 효율적으로 구현하여 응용프로그램 수준에서 고성능과 호환성을 동시에 제공하여야 한다. 본 논문에서는 VMMC 통신 계층을 기반으로 MPI를 구현하였다. VMMC의 직접 저장 방식은 MPI의 Send/Recv 방식을 지원하기에 적합하지 않지만 본 논문에서는 두 가지 통신 방식을 변환하기 위한 송수신 큐 구조를 설계하고 늦은 위치 갱신, 선택적 무복사 전송 등의 최적화 기법을 적용함으로써 높은 전송 성능을 얻는다. MPI-VMMC의 최대 전송 대역폭은 90.7Mbytes/sec이며 이는 VMMC 통신 계층의 최대 전송 성능의 95%에 달한다. Cluster systems employ high speed interconnection networks and use efficient communication layers to gain high performance and scalability. But the diversity in implementation mechanism among these communication layers causes lack of portability. A solution is to provide communication standard APIs such as MPI. This paper introduces MPI-VMMC: an MPI implementation on VMMC. Though the direct deposit transfer mechanism used in VMMC is not suitable for Send/Recv mechanism used in MPI, the proposed sub-layer laid between MPI and VMMC efficiently translates from one mechanism to the other. We also use the lazy pointer and selective zero-copy transfer technique to gain high performance. The peak performance of MPI-VMMC is 90.7Mbytes/sec, which is about 95% of the base communication layer's.

웜홀 방식 망에서의 효율적인 완전교환 통신 알고리즘

김시관(Si Gwan Kim),맹승렬(Seung ryoul Maeng),조정완(Jung Wan Cho) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.5

완전교환 통신은 행렬전이, 푸리에변환 혹은 분산 테이블 검색과 같은 여러 가지 응용에서 아주 많이 활용되는 통신 방법이다. 본 논문은 웜홀 방식을 채용한 2차원 토러스에서의 개시 지연 시간을줄이기 위하여 분할 및 합병(divide-and-conquer) 방식을 사용한 효율적인 완전교환 통신 알고리즘을 제안한다. 전체망을 2x2 형태의 기본셀로 분할한 뒤 각 기본셀에서는 마스터노드라고 불리는 특정 노드를 지정하여 기본셀내의 여타 노드들의 메시지를 이 마스터노드가 수집한다. 이 마스터노드들이 다른 모든 노드로 보내질 메시지를 수집한 뒤 각 기본셀내의 모든 마스터 노드들만이 가상 망을 형성하여 망의 크기가 N/2 x N/2으로 줄어든 상태로 완전 교환 알고리즘을 수행한다. 마스터노드들간의 완전교환 연산을 수행한 뒤 이 마스터노드들은 자기가 전담했던 여타 노드들의 메시지를 재분배해 줌으로써 주어진 완전교환 연산을 완료한다. 기존의 여러 가지 알고리즘과의 비교 분석을 제시하였으며 제시한 알고리즘이 약 2배 정도의 개시 지연시간 면에서 우수함을 보인다. All-to-all personalized communication, or complete exchange, 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. First, we divide the whole network into 2x2 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, N/2 x N/2. When finished with this complete exchange in master nodes, these nodes distribute messages to the rest of the master node, which results in the desired complete exchange communication. After we present our algorithms, we analyze time complexities and compare our algorithms with several previous algorithms. And we show that our algorithm is efficient by a factor of 2 in the required start-up time which means that our algorithm is suitable for wormhole-routed networks.