컴파일시 생성된 여러개의 선형 순서를 가지는 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.

다단계 상호 연결망에 기초된 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

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

원격 로깅 기법을 이용하는 고장 허용 소프트웨어 분산공유메모리 시스템의 구현

박소연(Soyeon Park),김영재(Youngjae Kim),맹승렬(Seung Ryoul Maeng) 한국정보과학회 2004 정보과학회논문지 : 시스템 및 이론 Vol.31 No.5·6

최근에 소프트웨어 분산공유메모리 시스템은 그 성능이 높아짐에 따라 큰 규모의 클러스터 상에서 사용되는 경우가 많아졌다. 그러나 시스템 규모가 커지면서 고장이 발생하는 가능성도 높아졌다. 시스템의 가용성을 높이기 위하여 고장 허용 기능을 제공하는 분산공유메모리 시스템이 요구되었으며 메시지 로깅에 대한 많은 연구가 이루어져 왔다. 본 논문에서는 고속의 네트웍을 이용하여 복구에 필요한 메시지들을 원격 노드의 메모리에 로깅하는 방법을 제안한다. 원격 로깅은 정상 수행 동안 빈번한 디스크 접근을 요구하지 않으므로 오버헤드가 적다. 또한 로그를 유지하는 백업 노드들이 고장나지 않은 경우 다중 노드의 고장을 허용하여, 분산공유메모리 시스템의 신뢰성을 높인다. 본 논문에서는 FT-KDSM (Fault Tolerant KAIST DSM) 시스템을 설계하고 구현하여 원격 로깅의 성능을 보이고 고장으로부터의 복구시간을 보인다. Recently, Software DSMs continue to improve its performance and scalability. As Software DSMs become attractive on larger clusters, the focus of attention is likely to move toward improving the reliability of a system. A popular approach to tolerate failures is message logging with checkpointing, and so many log-based rollback recovery schemes have been proposed. In this work, we propose a remote logging scheme which uses the volatile memory of a remote node assigned to each node. As our remote logging does not incur frequent disk accesses during failure-free execution, its logging overhead is not significant especially over high-speed communication network. The remote logging tolerates multiple failures if the backup nodes of failed nodes are alive. It makes the reliability of DSMs grow much higher. We have designed and implemented the FT-KDSM(Fault Tolerant KAIST DSM) with the remote logging and showed the logging overhead and the recovery time.

시간 제약과 신뢰성을 최적화하는 새로운 스케쥴링 문제

은성배(Seongbae Eun),송효정(Hyojung Song),맹승렬(Seung Ryoul Maeng),조정완(Jung Wan Cho) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2B

최근들어, 실시간 시스템과 오류 허용 시스템 각각에 대해서 독립적으로 많은 연구가 진행되고 있다. 그러나, 시간 제약과 신뢰성을 동시에 고려한 응답 시스템에 대해서는 충분한 연구가이루어지고 있지 않은 실정이다. 본 논문에서는 시간 제약과 신뢰성을 모두 고려하는 새로운 스케쥴링(응답 스케쥴링) 문제에 대한 고찰을 통해 응답성이라는 새로운 평가 척도를 정의하며, 단일처리기 상에서 비주기 태스크들을 대상으로 응답성을 최대화하는 REDF(Responsive Earliest Deadline First) 스케쥴링 알고리즘을 제안한다. 그리고, REDF 알고리즘이 최대 응답성을 갖는 최적의 알고리즘임을 증명한다.

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

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

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

소프트웨어 분산공유메모리의 고장 허용을 위한 원격 로깅 기법

박소연(Soyeon Park),김영재(Youngjae Kim),맹승렬(Seung Ryoul Maeng) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.1A

소프트웨어 분산공유메모리 시스템의 성능이 높아짐에 따라 최근에는 큰 규모의 클러스터 상에서 사용되는 경우가 많아졌다. 그러나 시스템 규모가 커지면서 고장이 발생하는 가능성도 높아졌다. 시스템의 가용성을 높이기 위하여 고장 허용 기능을 제공하는 분산공유메모리 시스템이 요구되었으며 체크포인팅과 더불어 메시지 로깅에 대한 많은 연구가 이루어져 왔다. 본 논문에서는 고속의 네트웍을 이용하여 원격 노드의 메모리에 로깅하는 방법과 복구 방법을 제안하고 구현을 통하여 성능을 보인다. 원격 로깅은 디스크 접근을 요구하지 않으므로 오버헤드가 적으며 제한적으로 다중 노드의 고장을 허용한다.

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

김시관(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.

Generalized Rearrangeable Networks with Recursive Decomposition Structure

Myung-Kyun Kim,Hyunsoo Yoon,Seung-Ryoul Maeng 대한전기학회 1997 Journal of Electical Engineering and information S Vol.2 No.5

고장을 허용하는 분산공유메모리 시스템의 성능 향상 기법

김영재(Youngjae Kim),박소연(Soyeon Park),맹승렬(Seung Ryoul Maeng) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.1A

클러스터 시스템의 규모가 커짐에 따라 소프트웨어 분산공유메모리 시스템의 고장 발생 확률은 점차 증가하고 있다. 그래서 최근에는 소프트웨어 분산공유메모리 시스템에 고장 허용 기능을 추가하는 연구가 활발히 이루어지고 있다. 연구의 초점은 소프트웨어 분산공유메모리 시스템이 정상 실행을 하는 동안 고장 허용 기능을 추가로 지원하면서 발생하는 오버헤드를 줄이는데 있다. 본 논문은 고장 허용 기능을 위해 원격 로깅 기법을 사용하는 소프트웨어 분산공유메모리 시스템에서 로그를 이용함으로써 전체적인 성능 향상을 기대한다.