주기 및 비주기 태스크의 효율적인 관리를 위한 실시간 센서 노드 플랫폼의 설계

김병훈,정경훈,탁성우,Kim, Byoung-Hoon,Jung, Kyung-Hoon,Tak, Sung-Woo 한국정보처리학회 2007 정보처리학회논문지 C : 정보통신,정보보안 Vol.14 No.4

본 논문에서는 주기 및 비주기 태스크의 효율적인 관리를 제공하는 실시간 센서 노드 플랫폼을 설계하고 구현하였다. 기존 센서 노드의 소프트웨어 플랫폼은 제한된 센서 노드의 자원을 효율적으로 사용하기 위하여 메모리 및 전력 소비량의 최소화에만 초점을 두었기 때문에 태스크의 실시간성과 빠른 평균 응답시간을 보장하는 실시간 센서 노드의 소프트웨어 플랫폼에는 적합하지 않다. 이에 본 논문에서는 센서 노드의 소프트웨어 플랫폼으로 많이 사용되고 있는 TinyOS 기반에서 태스크의 실시간성과 빠른 평균 응답시간을 보장할 수 있는 기법과 한계를 분석하였으며, 모든 주기 태스크가 마감시한 내에 실행이 완료되는 것을 보장하고 비주기 태스크의 응답시간을 최소화하는 실시간 센서 노드 플랫폼을 제안하였다. 본 논문에서 제안한 플랫폼은 Atmel사의 초경량 8비트 마이크로프로세서인 Atmega128L이 탑재된 센서 보드에서 구현되었다. 구현된 실시간 센서 플랫폼의 성능을 분석한 결과, 모든 주기 태스크의 마감시한 보장을 제공함과 동시에 향상된 비주기 태스크의 평균 응답시간과 낮은 시스템의 평균 처리기 이용률을 확인할 수 있었다. In this paper, we propose a real-time sensor node platform that efficiently manages periodic and aperiodic tasks. Since existing sensor node platforms available in literature focus on minimizing the usage of memory and power consumptions, they are not capable of supporting the management of tasks that need their real-time execution and fast average response time. We first analyze how to structure periodic or aperiodic task decomposition in the TinyOS-based sensor node platform as regard to guaranteeing the deadlines of ail the periodic tasks and aiming to providing aperiodic tasks with average good response time. Then we present the application and efficiency of the proposed real-time sensor node platform in the sensor node equipped with a low-power 8-bit microcontroller, an IEEE802.15.4 compliant 2.4GHz RF transceiver, and several sensors. Extensive experiments show that our sensor node platform yields efficient performance in terms of three significant, objective goals: deadline miss ratio of periodic tasks, average response time of aperiodic tasks, and processor utilization of periodic and aperiodic tasks.

실시간 제약조건을 갖는 다중태스크 다중코어 SoC의 하드웨어-소프트웨어 통합합성

이춘승(Choonseung Lee),하순회(Soonhoi Ha) 한국정보과학회 2006 정보과학회논문지 : 시스템 및 이론 Vol.33 No.9

이 논문은 실시간 제약 조건을 갖는 다중태스크 응용을 여러 개의 코어를 갖는 SoC 위에서 동작시키고자 할 때, 시스템의 비용은 최소로 하면서 성능을 높일 수 있도록 프로세서 및 하드웨어 IP를 선정하고, 태스크를 매핑 하는 기법을 제안한다. 이와 같은 기법은 하드웨어-소프트웨어 통합합성 기법이라고 한다. 이전 연구에서 우리는 복잡한 통합합성 문제를 세 가지 하부 문제(프로세서 컴포넌트 선택문제, 태스크 매핑문제, 그리고 스케줄-가능성 검사문제)로 세분화 하고, 각 문제를 독립적으로 해결하는 기법을 제안하였다[1]. 하지만 많은 장점에도 불구하고 이전 연구에서는 한 태스크가 스케줄 될 때, 자신의 스케줄-길이를 최소로 줄이기 위해 시스템 전체 자원을 모두 점유하는 것을 가정하는 제약점이 있었다. 그러나 일반적으로 보다 향상된 성능을 얻기 위해서는, 서로 관련이 없는 태스크들은 서로 다른 프로세서에서 동시에 실행될 수 있어야 한다. 이 논문에서는 다중프로세서 환경에서 다양한 운영정책을 가지는 일반적인 시스템을 위하여 태스크 매핑회피 기법과 태스크 매핑전용 기법이라는 두 가지 매핑기법을 제시한다. 멀티미디어 실시간 응용 프로그램인 다채널 디지털 비디오 레코더(Digital Video Recorder)와 관련 논문에서 제공된 임의 생성 다중태스크 예제에 대해서 큰 성능 향상을 얻을 수 있었다. This paper proposes a technique to select processors and hardware IPs and to map the tasks into the selected processing elements, aming to achieve high performance with minimal system cost when multitask applications with real-time constraints are run on a multicore SoC. Such technique is called to ‘Hardware-Software Cosynthesis Technique’. A cosynthesis technique was already presented in our early work [1] where we divide the complex cosynthesis problem into three subproblems and conquer each subproblem separately: selection of appropriate processing components, mapping and scheduling of function blocks to the selected processing component, and schedulability analysis. Despite good features, our previous technique has a serious limitation that a task monopolizes the entire system resource to get the minimum schedule length. But in general we may obtain higher performance in multitask multicore system if independent multiple tasks are running concurrently on different processor cores. In this paper, we present two mapping techniques, task mapping avoidance technique(TMA) and task mapping pinning technique(TMP), which are applicable for general cases with diverse operating policies in a multicore environment. We could obtain significant performance improvement for a multimedia real-time application, multi-channel Digital Video Recorder system and for randomly generated multitask graphs obtained from the related works.

잉여 여유시간을 이용한 연성 비주기 태스크들의 효율적인 스케줄링

김희헌(Heeheon Kim),박학봉(Xuefeng Piao),박문주(Moonju Park),박민규(Moonju Park),조유근(Yookun Cho),조성제(Seongje Cho) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.1

마감시간이 있는 주기 태스크와 마감시간이 없는 비주기 태스크가 공존하는 경성 실시간 시스템에서는 주기 태스크의 마감시간과 비주기 태스크의 빠른 응답시간을 보장하는 것이 중요하다. 본 논문에서는 비주기 태스크 처리에 효율적이면서 잘 알려져 있는 알고리즘인 Total Bandwidth Server(TBS) 보다 향상된 알고리즘인 Enhanced TBS(ETBS)를 제시한다. ETBS는 Earliest Deadline First(EDF) 스케줄링 알고리즘을 사용하는 단일처리기 시스템에서 주기 작업의 단위 수행시간마다 확보할 수 있는 잉여 여유시간을 이용해 온라인으로 비주기 태스크에 마감시간을 부여하는 알고리즘이다. 제시한 알고리즘은 주기 및 비주기 태스크들이 처리기의 이용률을 모두 이용할 수 있게 하며 주어진 주기 태스크들의 마감시간을 보장한다. ETBS 알고리즘은 TBS와 같은 계산 복잡도 O(1)을 가지면서도 TBS보다 좋은 응답시간을 가짐을 이론적으로 보였고, 정량적인 응답시간 차이는 모의실험을 통해 보였다. In a real-time system with both hard real-time periodic tasks and soft real-time aperiodic tasks, it is important to guarantee the deadlines of each periodic task as well as obtain fast response time for each aperiodic task. This paper proposes Enhanced Total Bandwidth Server (ETBS) with possibly shorter response time than Total Bandwidth Server (TBS), which is efficient and widely used for servicing aperiodic tasks. For uniprocessor system using Earliest Deadline First (EDF) scheduling algorithm, ETBS assigns an on-line deadline to each aperiodic task considering a surplus slack time which gained for every unit execution time of periodic job. The proposed method can fully utilize the processor while meeting all the deadlines of periodic tasks. We show that the proposed ETBS provides better response time of aperiodic tasks than TBS theoretically, but has the same computational complexity as TBS, O(1). Simulation results show that the response time of aperiodic tasks with ETBS are shorter than one with TBS.

MPEG-2 디코딩을 위한 멀티미디어 시스템에서 우선순위에 의한 태스크 스케쥴링 기법

김진환,Kim Jinhwan 한국정보처리학회 2005 정보처리학회논문지B Vol.12 No.2

본 논문에서는 MPEG-2 비디오 스트림의 프레임을 디코딩하는 멀티미디어 태스크에 대한 효율적인 실시간 스케줄링 기법이 제시된다. 태스크 모델에서 각 프레임은 각각의 멀티미디어 태스크에 의하여 디코딩되며 각 태스크는 비디오 스트림내 프레임의 순서와 중요도에 따라 우선 순위가 설정된다. MPEG-2 비디오 스트림의 디코딩 기능을 수행하는 멀티미디어 태스크마다 CPU 대역폭을 효과적으로 할당하고자 우선순위에 기반한 스케줄링 기법을 사용하는 것이다. 본 논문에서 멀티미디어 태스크에 할당된 CPU 대역폭을 우선순위에 따라 동적으로 제어하는 방법이 기술된다. 우선순위에 의한 스케줄링 기법의 주요 목적은 멀티미디어 태스크들의 디코딩 시간을 감소시키는 한편 종료시한 이후에 실행이 완료되는 디코딩 태스크의 수를 최소화함으로써 멀티미디어 시스템의 실시간적 성능을 향상시키는 것이다. 제시된 스케줄링 기법의 성능은 시뮬레이션 실험을 통하여 다른 기법과 비교 분석된다. In this paper, we propose an efficient real-time scheduling method of multimedia tasks for decoding frames of MPEG-2 video streams. In our task model, each frame is decoded by a separate multimedia task. The decoding task for each frame is assigned to the priority according to the precedence and importance of frames in a video stream. We use a priority-based scheduling policy in order to effectively allocate the CPU bandwidth to multimedia tasks for MPEG-2 decoding. We show how to dynamically control the fraction of the CPU bandwidth allocated to each multimedia task according to the priority. The primary purpose of our scheduling method is to enhance the real-time performance of the multimedia system by minimizing the number of decoding tasks that have missed their deadlines while reducing the decoding times of these multimedia tasks. The performance of this scheduling method is compared with that of similar mechanisms through simulation experiments.

멀티코어 프로세서상의 실시간 태스크들을 위한 중복 실행에 기반한 저전력 결함포용 스케줄링

이관우(Kwan-Woo Lee) 한국컴퓨터정보학회 2014 韓國컴퓨터情報學會論文誌 Vol.19 No.5

제시된 기법은 실시간 태스크들의 데드라인들을 만족하고 또한 기본-백업 태스크 모델을 사용하여 영구 결함을 포용하면서 멀티코어 프로세서의 에너지 소모량을 최소화하도록 태스크들을 스케줄링한다. 기존의 방법들이 기본 태스크와 백업 태스크의 중복 수행 시간을 최소화하도록 태스크들을 스케줄링했지만, 제시된 기법에서는 코어 속도를 최대한 줄이기 위해서 기본 태스크와 백업 태스크의 중복 수행 시간을 최대화하여 에너지 소모량을 감소시켰다. 제시된 기법이 에너지 소모량을 최소화시킴을 수학적으로 분석하였고, 또한 성능평가 실험을 통해서 제시된 기법이 기존 방법의 에너지 소모량을 최대 77%까지 감소시킴을 보였다. The proposed scheme schedules given real-time tasks so that energy consumption of multicore processors would be minimized while meeting tasks' deadline and tolerating a permanent fault based on the primary-backup task model. Whereas the previous methods minimize the overlapped time of a primary task and its backup task, the proposed scheme maximizes the overlapped time so as to decrease the core speed as much as possible. It is analytically verified that the proposed scheme minimizes the energy consumption. Also, the proposed scheme saves up to 77% energy consumption of the previous method through experimental performance evaluation.

태스크 동기화가 필요한 임베디드 실시간 시스템에 대한 효율적인 전압 스케쥴링

이재동(Jae-Dong Lee),허정연(Jung Youn Hur) 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.5·6

Many embedded real-time systems have adopted processors supported with dynamic voltage scaling(DVS) recently. Power is one of the important metrics for optimization in the design and operation of embedded real-time systems. We can save considerable energy by using slowdown of processor supported with DVS. In this paper, we propose heuristic algorithms to calculate task slowdown factors for an efficient energy consumption in embedded real-time systems with task synchronization. The previous algorithm has a following constraint : given the tasks are ordered in a nondecreasing order of their relative deadline, the task slowdown factors computed are in a nonincreasing order. In this paper, we relax the constraint and propose heuristic algorithms which have the same time complexity that previous algorithm has and can save more energy. Experimental results show that the proposed algorithms are energy efficient. 최근 많은 임베디드 실시간 시스템에 동적 전압 조절(Dynamic Voltage Scaling: DVS)을 지원하는 프로세서를 사용하고 있다. 이런 시스템의 설계 및 동작의 최적화를 위한 중요한 요소 중 하나가 전력(power)이다. 동적 전압 조절을 지원하는 프로세서의 슬로우다운을 이용하므로서 많은 소비 전력을 절약할 수 있다. 본 논문에서는 태스크의 동기화가 필요한 임베디드 실시간 시스템에서 효율적인 전력 소비를 위해 태스크들의 슬로우다운 값을 구하는 휴리스틱 알고리즘들을 제안한다. 기존 알고리즘에서는 상대 마감시간이 작은 태스크의 슬로우다운 값은 상대 마감시간이 크거나 같은 태스크의 슬로우다운 값보다 크거나 같아야 한다는 제약조건을 가지고 있다. 본 논문에서는 이 제약조건을 완화하여 기존 알고리즘과 같은 시간복잡도를 가지면서 전력을 더 작게 소비하는 휴리스틱 알고리즘들을 제시한다. 실험을 통해 소비전력 면에서 효율적임을 보였다.

태스크 동기화가 필요한 임베디드 실시간 시스템에 대한 효율적인 전압 스케쥴링

이재동,허정연 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.6

Many embedded real-time systems have adopted processors supported with dynamic voltage scaling(DVS) recently. Power is one of the important metrics for optimization in the design and operation of embedded real-time systems. We can save considerable energy by using slowdown of processor supported with DVS. In this paper, we propose heuristic algorithms to calculate task slowdown factors for an efficient energy consumption in embedded real-time systems with task synchronization. The previous algorithm has a following constraint : given the tasks are ordered in a nondecreasing order of their relative deadline, the task slowdown factors computed are in a nonincreasing order. In this paper, we relax the constraint and propose heuristic algorithms which have the same time complexity that previous algorithm has and can save more energy. Experimental results show that the proposed algorithms are energy efficient. 최근 많은 임베디드 실시간 시스템에 동적 전압 조절(Dynamic Voltage Scaling: DVS)을 지원하는 프로세서를 사용하고 있다. 이런 시스템의 설계 및 동작의 최적화를 위한 중요한 요소 중 하나가 전력(power)이다. 동적 전압 조절을 지원하는 프로세서의 슬로우다운을 이용하므로서 많은 소비 전력을 절약할 수 있다. 본 논문에서는 태스크의 동기화가 필요한 임베디드 실시간 시스템에서 효율적인 전력 소비를 위해 태스크들의 슬로우다운 값을 구하는 휴리스틱 알고리즘들을 제안한다. 기존 알고리즘에서는 상대 마감시간이 작은 태스크의 슬로우다운 값은 상대 마감시간이 크거나 같은 태스크의 슬로우다운 값보다 크거나 같아야 한다는 제약조건을 가지고 있다. 본 논문에서는 이 제약조건을 완화하여 기존 알고리즘과 같은 시간복잡도를 가지면서 전력을 더 작게 소비하는 휴리스틱 알고리즘들을 제시한다. 실험을 통해 소비 전력 면에서 효율적임을 보였다.

Energy-Efficient Multi- Core Scheduling for Real-Time Video Processing

백형구(Hyung-Goo Paek),여정모(Jeong-Mo Yeo),이완연(Wan-Yeon Lee) 한국컴퓨터정보학회 2011 韓國컴퓨터情報學會論文誌 Vol.16 No.6

본 논문에서는 DVFS 기능을 제공하는 멀티코어 프로세서 상에서 실시간 비디오 태스크의 에너지 소모량을 최소화하는 최적 스케쥴링 기법을 제안한다. 제안된 스케쥴링 기법은 멀티코어의 병렬처리 기법을 활용하도록 적절한 수의 멀티코어들을 태스크의 수행에 할당하고, 사용되지 않는 코어들의 전원을 끄며, 실시간 태스크의 데드라인을 만족하는 최저 클락 주파수를 배정한다. 단일 코어에서 태스크를 실행하는 기존 방법과 그리고 모든 코어들에서 태스크를 실행하는 기존 방법을 제안된 스케쥴링 기법과 비교하는 실험 결과에서, 제안된 스케쥴링 기법이 기존 방법들의 에너지 소모량을 각각 최대 67%, 89% 감소시킴을 확인하였다. In this paper, we propose an optimal scheduling scheme that minimizes the energy consumption of a real-time video task on the multi-core platform supporting dynamic voltage and frequency scaling. Exploiting parallel execution on multiple cores for less energy consumption, the propose scheme allocates an appropriate number of cores to the task execution, turns off the power of unused cores, and assigns the lowest clock frequency meeting the deadline. Our experiments show that the proposed scheme saves a significant amount of energy, up to 67% and 89% of energy consumed by two previous methods that execute the task on a single core and on all cores respectively.

태스크 선택정책에 기반을 둔 IRIS 태스크 스케줄링 알고리즘

심재홍,최경희,정기현,Shim, Jae-Hong,Choi, Kyung-Hee,Jung, Gi-Hyun 한국정보처리학회 2003 정보처리학회논문지 A Vol.10 No.3

본 논문에서는 IRIS(Increasing Reward with Increasing Service) 태스크들을 위한 기존 온-라인 최적 알고리즘에 근접한 총가치(total reward)를 생성하면서 보다 낮은 스케줄링 복잡도를 가진 휴리스틱(heuristic) 온-라인 스케줄링 알고리즘을 제안한다. 기존 알고리즘들은 총가치를 최대화하기 위해 시스템 내의 모든 태스크들을 스케줄링 대상으로 고려한다. 따라서 이들 알고리즘들은 많은 태스크들을 가진 실제 시스템에 적용하기에는 매우 놀은 시간 복잡도를 가진다. 제안 알고리즘은 시스템 내의 모든 태스크들을 대상으로 스케줄링하는 것이 아니라, 상수 W개의 태스크들을 선택하여 이들을 대상으로 스케줄링 한다. 제안 알고리즘은 W개의 태스크를 어떤 기준에 의해 선택할 것인가를 규정하는 테스크 선택정책에 기반을 두고 있으며, 간단하면서도 직관적인 두 가지 선택정책과 이 둘을 통합한 보다 일반화된 선택정책을 제안한다. 스케줄링 대상을 축소함으로써 제안 알고리즘의 복잡도를 O(Wn)로 줄일 수 있었다. 다양한 성능실험 결과 알고리즘 평균 계산 빈도는 O(W)에 더 가깝다는 것을 확인할 수 있었다. We propose a heuristic on-line scheduling algorithm for the IRIS (Increasing Reward with Increasing Service) tasks, which has low computation complexity and produces total reward approximated to that of previous on-line optimal algorithms. The previous on-line optimal algorithms for IRIS tasks perform scheduling on all tasks in a system to maximize total reward. Therefore, the complexities of these algorithms are too high to apply them to practical systems handling many tasks. The proposed algorithm doesn´t perform scheduling on all tasks in a system, but on (constant) W´s tasks selected by a predefined task selection policy. The proposed algorithm is based on task selection policies that define how to select tasks to be scheduled. We suggest two simple and intuitive selection policies and a generalized selection policy that integrates previous two selection policies. By narrowing down scheduling scope to only W´s selected tasks, the computation complexity of proposed algorithm can be reduced to O(Wn). However, simulation results for various cases show that it is closed to O(W) on the average.

소프트 데드라인을 가지는 실시간 태스크에서의 체크포인터 삽입 방법

곽성우(Seong-Woo Kwak),양정민(Jung-Min Yang) 한국지능시스템학회 2011 한국지능시스템학회 학술발표 논문집 Vol.21 No.1

본 논문에서는 주기보다 긴 데드라인을 가지는 실시간 태스크에 대한 체크포인트 배치 기법을 제안한다. 과도고장의 영향을 받는 실시간 시스템에서 멀티 태스크들은 Rate Monotonic 알고리듬으로 스케줄링된다. 제안하는 기법은 고장 환경 하에서 멀티 태스크가 성공적으로 수행 완료될 확률을 최대화하는 체크포인트 구간 길이를 결정하는 것이다. 데드라인이 주기보다 긴 경우 RM 알고리듬의 스케줄링 가능성을 테스트하는 방법과 멀티 태스크의 수행 성공 확률 식은 데드라인이 주기와 동일한 경우보다 더 복잡하게 유도된다. 사례 연구를 통해서 제안된 기법의 적용가능성을 입증한다.