초기호출시간이 지정된 실시간 주기적 태스크의 비선점적 스케쥴링

길아라(Ara Khil),맹승렬(Seungryoul Maeng) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.4

단일 프로세서 시스템에서 초기호출시간이 지정된 주기적 태스크를 비선점적 스케쥴링하는 문제는 NP-hard 문제로 알려져 있다. 본 논문에서는 초기호출시간이 지정된 주기적 태스크의 스케쥴링 성공율을 향상시키기 위하여 주기적 태스크의 반복성과 예측가능성을 이용하는 새로운 스케쥴링 전략과 새로운 비선점적 스케쥴링 알고리즘을 제안한다. 본 논문에서 제안하는 스케쥴링 전략은 주어진 문제를 각각 주어진 스케쥴링 시간구간내에서 순방향 또는 역방향으로 스케쥴링하는 두 개의 부-스케쥴링 문제로 나눈 후, 이들 두 개의 실행가능한 부-스케쥴들을 적용하는 시간구간에 따라 결합하여 하나의 완전한 실행가능한 스케쥴을 구하는 정적 스케쥴링 전략이다. 이 때, 보다 효율적으로 주어진 문제를 분할하기 위하여 초기호출 시간과 주기와의 관계식을 제시한다. 제안된 스케쥴링 알고리즘은 선택한 태스크 호출을 비선점적 최소 마감시간 우선 (earliest- deadline-first, EDF) 알고리즘으로 스케쥴링할 경우 발생할 수 있는 다른 태스크 호출의 마감시간 초과를 미리 계산한다. 계산 결과, 다른 태스크의 마감시간 초과가 예상되면, 선택한 태스크의 스케쥴링을 연기하므로써 예상된 마감시간 초과를 회피한다. 그렇지 않은 경우, 선택한 태스크 호출은 비선점적 최소 마감시간 우선 알고리즘의 경우와 통일한 방법으로 스케쥴링한다. 제안된 스케쥴링 알고리즘은 최소 마감시간 우선 알고리즘으로 실행가능한 스케쥴을 찾을 수 있는 태스크 집합에 대해서는 항상 실행가능한 스케쥴을 찾을 수 있다. 본 논문에서 제안된 스케쥴링 전략 및 스케쥴링 알고리즘의 향상된 성능은 모의실험 결과로써 나타내 보인다. The problem of non-preemptive scheduling of real-time periodic tasks with specified release times on a uniprocessor system is known as NP-hard problem In this paper, we propose the new scheduling strategy and the new scheduling algorithm which use the reperitiveness and the predictability of periodic tasks for improvements of schedulabilities of real-time periodic tasks with specified release times. The proposed scheduling strategy is the static scheduling strategy that suggests dividing the given problem into two subproblems which find feasible schedules in the forward scheduling or in the backward scheduling within specific time intervals and combining the two feasible schedules into a complete feasible schedule for the original problem. We present the release times as a function of periods for the efficient problem division. The proposed scheduling algorithm schedules periodic tasks by using the heuristic that precalculates if the scheduling of the selected task leads that a task misses a deadline when tasks are scheduled by the non-preemptive EDF algorithm. It defers the scheduling of the selected task to avoid the precalculated deadline-missing. Otherwise, it schedules the selected task in the same as the non-preemptive EDF algorithm. Our scheduling algorithm can always find a feasible schedule for the set of periodic tasks with specified release times which is schedulable by the non-preemptive EDF algorithm. We show the improvements on the performance of the proposed scheduling strategy and scheduling algorithm by simulation results.

마이크로프로세서 전력소모 절감을 위한 명령어 큐 구조

최민(Min Choi),맹승렬(Seungryoul Maeng) 대한전자공학회 2008 電子工學會論文誌-SD (Semiconductor and devices) Vol.45 No.11

현대 마이크로프로세서는 적정수준의 전력소모에 고성능의 애플리케이션성능을 요구한다. 전력소모와 성능향상의 상호보정 측면에서 볼때, 명령어 윈도우(Instruction window)는 특별히 중요한 구성요소이다. 이는 명령어 윈도우의 크기를 확장하면 성능향상을 가능하도록 하지만, 기존의 명령어 구조를 그대로 이용하여 크기만 늘리는 것은 전력소모와 복잡도 측면에서 불리하기 때문이다. 본 연구에서는 전력소모를 감소하기 위해서 직접 검색 테이블(Direct table lookup :DTL)을 사용하여 명령어 윈도우에서 발생하는 연관 검색을 최소화한다. 이를 위해 비트 벡터(bit-vector) 기반의 태그 변환 기법을 제안하여 데이터 종속성 및 자원 충돌 현상을 효과적으로 해결한다. 본 논문에서는 SPEC2000 벤치마크를 활용하여 성능평가를 수행하여 제안된 기법이 기존 방법 대비 24.45%의 전력소모 개선 효과를 나타냄을 확인하였다. Modern microprocessors must deliver high application performance, while the design process should not subordinate power. In terms of performance and power tradeoff, the instructions window is particularly important. This is because a large instruction window leads to achieve high performance. However, naive scaling conventional instruction window can severely affect the complexity and power consumption. This paper explores an architecture level approach to reduce power dissipation. We propose a low power issue logic with an efficient tag translation. The direct lookup table (DTL) issue logic eliminates the associative wake-up of conventional instruction window. The tag translation scheme deals with data dependencies and resource conflicts by using bit-vector based structure. Experimental results show that, for SPEC2000 benchmarks, the proposed design reduces power consumption by 24.45% on average over conventional approach.

MPI를 활용한 PI(π)값 계산 병렬화 알고리즘

최민(Min Choi),맹승렬(SeungRyoul Maeng) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.1A

정확한 π값의 계산은 자연과학의 여러 분야에 도움을 준다. 이와 같이 π값을 계산하는 여러 가지 방법이 제안되어 있으며 널리 사용되고 있으나, 본 논문에서는 MPI 라이브러리를 활용한 π값 계산의 병렬화 알고리즘을 소개한다. tan^(-1)의 정의를 이용하는 π값 계산 방법은 다항식의 계산과정에서 각 항(term)들의 종속성으로 인하여 병렬화 수행이 힘든 단점이 있다. 본 논문에서는 tan^(-1)를 맥클로린 수열(Maclaurin Series)을 통하여 다항함수로 표현하고, 병렬화 수행에 적합한 적분형태로 변형한다. 따라서, MPI 환경에서 수행하기 적합한 π값 계산의 병렬화 알고리즘을 제안하고 8노드 클러스터 환경에서 성능을 비교해본다. 또한, 직렬화된 방법에 대한 성능향상(speedup)을 측정한다.

콘텐츠 복제 웹 서버에서 캐쉬 복제를 통한 성능 향상

김호중(Hojoong Kim),맹승렬(Seungryoul Maeng) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.1C

최근 웹 서비스에서 동적 콘텐츠의 비율이 증가함에 따라 캐쉬 적중률을 높임으로써 서버 CPU의 부하를 줄이는 일의 중요성이 커지고 있다. 서버의 성능을 증가시키기 위한 방법으로 콘텐츠 복제 서버 클러스터가 널리 활용되고 있다. 그러나 콘텐츠 복제 서버의 각 노드는 유사한 작업을 수행함에도 불구하고 서로 독립적으로 동작하므로 캐쉬 적중률이 감소한다. 본 논문에서는 한 서버 노드에서 캐슁하는 웹 콘텐츠를 다른 서버 노드의 캐쉬에 복제함으로써 서버 팜의 각 노드의 캐쉬 내용을 유사하게 관리하여 캐쉬 적중률을 높인다.

IO 집합자의 부하에 따른 MPI-IO 성능 분석

차광호(Kwnagho Cha),맹승렬(Seungryoul Maeng),김성호(Sungho Kim) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.2B

집합 IO (Collective IO)는 MPI-IO의 중요 기능 중 하나로서 병렬 시스템의 IO를 처리하는데 사용된다. 본 연구에서는 이러한 집합 IO를 실행할 때 중간 과정을 담당하는 IO 집합자(IO Aggregator)의 중요성을 파악하기 위하여 IO 집합자 노드에서 다른 작업으로 인하여 나타날 수 있는 예상 부하를 생성하여 성능 저하 정도를 확인하였다. 집합자의 구성과 부하 생성 조건을 조합하여 테스트한 결과 IO 성능에 영향을 미치는 경우를 확인하고 분석할 수 있었다.

베어 메탈 인-메모리 환경에서의 전체 시스템 체크포인트-회복 기법

임재성(Jaeseong Im),김종율(Jongyul Kim),맹승렬(Seungryoul Maeng) 한국정보과학회 2017 한국정보과학회 학술발표논문집 Vol.2017 No.06

멀티코어 플랫폼에서 SCA 규격 웨이브폼의 성능 향상 기법

김한준(Hanjoon Kim),김선희(Sunhee Kim),맹승렬(SeungRyoul Maeng) 한국정보과학회 2008 한국정보과학회 학술발표논문집 Vol.35 No.2

하나의 플랫폼으로 여러 무선 통신 규격들을 동적으로 재구성할 수 있어 차세대 무선통신 기술로 주목받고 있는 Software Defined Radio(SDR)은, 신호 처리 블록을 하드웨어가 아닌 소프트웨어로 처리함에 따라 높은 성능의 프로세서를 요구한다. 단가, 전력 등의 문제로 고성능의 프로세서를 사용할 수 없는 무선 이동 통신 단말에서 SDR 어플리케이션인 웨이브폼(waveform)을 실행하려면, 기존의 프로세서에 비해 저전력으로 높은 성능을 보이는 멀티코어의 활용이 필요하지만, 멀티코어를 고려하지 않고 개발된 기존의 웨이브폼들은 멀티코어의 자원을 충분히 활용하지 못한다. 본 논문에서는 Software Communication Architecture(SCA) 규격 맞게 개발된 웨이브폼을 수쟁하지 않고도 멀티고어의 자원을 최대로 활용할 수 있도록, 병목이되는 웨이브폼의 컴포넌트를 병렬화하여 실행함으로써 SCA 규격 웨이브폼의 성능을 향상시키는 방법을 제안한다.

실시간 단일처리에서 비주기 태스크의 시간 제약과 결함허용을 최적화하는 스케쥴링

은성배(SungBae Eun),송효정(HyoJung Song),맹승렬(Seungryoul Maeng),조정완(Jung-Wan Cho) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.6

최근들어, 실시간 시스템과 고장 허용 시스템 각각에 대해서 독립적으로 많은 연구가 진행되고 있다. 그러나, 시간 제약과 고장 허용성을 동시에 고려한 응답 시스템에 대해서는 충분한 연구가 이루어지고 있지 않은 실정이다. 본 논문에서는 시간 제약과 고장 허용성을 모두 고려하는 새로운 스케쥴링(응답 스케쥴링) 문제에 대한 고찰을 통해 응답성이라는 새로운 평가 척도를 정의하며, 단일처리기 상에서 비주기 태스크들을 대상으로 응답성을 최대화하는 REDF(Responsive Earliest Deadline First) 스케쥴링 알고리즘을 제안한다. 그리고, REDF 알고리즘이 최대 응답성을 갖는 최적의 알고리즘임을 증명한다. The integration of both real-time systems and fault-tolerant systems has been emerged as one of the greatest challenges of this decade. It is called a responsive system, which has the objective to optimize both the timeliness and reliability. The performance measure in responsive systems is responsiveness that appoints how probable a system executes correctly on time with faults occurred. While there have been some achievements in communication protocol and specification, we insist that scheduling problems in responsive systems are not understood deeply and sufficiently, yet. In this paper, we discuss on the scheduling problem in responsive systems. At first, we investigate the issues of the scheduling and propose the definition of responsiveness in the view of responsive systems. We also suggest a scheduling algorithm called Responsive Earliest Deadline First(REDF) for aperiodic preemptive tasks in uniprocessor systems. Finally, we show that REDF is optimal for the responsiveness.

SDIO에서 RAID 레벨 5의 효율적인 구현

김호진(Hojin Ghim),황인철(In-Chul Hwang),맹승렬(Seungryoul Maeng),윤현수(Hyunsoo Yoon) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.1A

단일 입출력 디스크(SDIO)는 클러스터 환경에서 빠르고 신뢰성있는 분산 저장장치를 제공한다. 단일 입출력 디스크는 주로 RAID 레벨 0이나 레벨 1을 사용하는데, RAID 레벨 5를 사용함으로써 좋은 성능과 좋은 신뢰도, 그리고 높은 디스크 용량 사용률을 얻을 수 있다. 그러나 RAID 레벨 5를 사용함으로써 네트웍 오버헤드 문제, 작은 데이터의 기록 성능 문제, 동시 기록 문제가 발생한다. 위의 세 가지 문제를 해결하거나 최소화하기 위하여 본 논문에서는 Parity Cumulating이라는 접근방법을 제시한다. Parity Cumulating은 패리티의 계산을 두 개의 노드로 분산시킴으로써 네트웍 오버헤드를 줄이고, 패리티를 버퍼에 저장하고 디스크에 작업이 없을 때 처리함으로써 작은 데이터의 기록 성능을 높이며 동시 기록시 일관성을 지킨다.

초기호출시간이 지정된 실시간 주기적 태스크의 단일 프로세서 시스템 상에서의 비선점적 스케쥴링

길아라(Ara Khil),정의훈(Euihoon Jeong),맹승렬(Seungryoul Maeng) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A

단일 프로세서 시스템에서 초기호출시간이 지정된 주기적 태스크를 비선점적 스케쥴링하는 문제는 NP-hard문제로 알려져 있다. 본 논문에서는 초기호출시간이 지정된 주기적 태스크의 스케쥴링 성공율을 향상시키기 위하여 새로운 스케쥴링 전략과 새로운 스케쥴링 알고리즘을 제안하고 이들의 성능 분석을 위한 모의실험 결과를 보인다. 본 논문에서 제안하는 스케쥴링 전략은 우선, 태스크들의 주기와 초기호출시간을 이용하여 두 개의 스케쥴링 경계시간을 계산하고, 이들을 이용하여 주어진 문제를 각각 다른 시간구간 내에서 실행가능한 스케쥴을 찾는 두 개의 부-문제로 나눈다. 또한, 스케쥴링 경계시간점들의 효율적인 계산을 위한 각 태스크의 초기호출시간과 주기간의 합수를 찾는다. 본 논문에서 제안하는 스케쥴링 알고리즘은 최소 마감시간 우선 (earliest-deadline-first) 정책에 기반한 휴리스틱을 사용하여 주어진 시간구간 내에서 초기호출시간이 지정된 주기적 태스크 집합의 스케쥴링 성공율을 향상시킨다. 즉, 선택한 태스크의 스케쥴링 전에 다른 태스크들의 마감시간 초과 발생을 예상하여 스케쥴링 순서를 변경하므로써 마감시간 초과 발생을 회피한다. 결국, 제안된 알고리즘은 주어진 시간구간 내에서 최소 마감시간 우선 알고리즘으로 스케쥴링 가능한 태스크 집합에 대해서는 항상 실행가능한 시케쥴을 찾을 수 있다. 끝으로, 모의실험 결과로써 제안된 스케쥴링 전략 및 스케쥴링 알고리즘의 향상된 성능을 나타내 보인다.