[논문]이산적 DVFS 멀티코어 프로세서 상에서 실시간 병렬 작업을 위한 확률적 저전력 스케쥴링

이완연

doi:10.9708/jksci.2013.18.2.031

이산적 DVFS 멀티코어 프로세서 상에서 실시간 병렬 작업을 위한 확률적 저전력 스케쥴링
Probabilistic Power-saving Scheduling of a Real-time Parallel Task on Discrete DVFS-enabled Multi-core Processors 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.18 no.2, 2013년, pp.31 - 39

초록
AI-Helper

본 논문에서는 멀티코어 프로세서에서 단일 실시간 병렬 작업의 데드라인을 만족하면서 전력 소모량의 확률적 기대 값을 최소화하는 스케쥴링 기법을 제안하였다. 제안된 기법에서는 단일 작업을 여러 개의 코어들 상에서 동시에 수행하는 병렬 처리 기법을 적용하였고, 전체 코어들 중에서 일부의 코어들만을 사용하고 나머지 코어들의 전원을 소등하여 전력 소모량을 줄였다. 또한 한정된 개수의 이산적 클락 주파수 값들을 가지는 DVFS 기반 멀티코어 프로세서에 대해서, 확률적 계산량 모델을 가진 실시간 병렬 작업의 데드라인을 만족하면서 전력 소모량의 확률적 기대 값을 최소화함을 수학적으로 증명하였다. 성능평가 실험에서, 제안된 기법이 기존 방법의 전력소모량을 최대 81%까지 감소시킴을 확인하였다.

Abstract ▼ AI-Helper

In this paper, we propose a power-efficient scheduling scheme that stochastically minimizes the power consumption of a real-time parallel task while meeting the deadline on multicore processors. The proposed scheme applies the parallel processing that executes a task on multiple cores concurrently, and activates a part of all available cores with unused cores powered off, in order to save power consumption. It is proved that the proposed scheme minimizes the mean power consumption of a real-time parallel task with probabilistic computation amount on DVFS-enabled multicore processors with a finite set of discrete clock frequencies. Evaluation shows that the proposed scheme saves up to 81% power consumption of the previous method.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 DVFS 기법을 제공하는 멀티코어 프로세서 상에서 주어진 단일 실시간 작업의 데드라인을 만족하면서 전력 소모량을 최소화는 스케쥴링 기법을 제안하였다. 제안된 스케쥴링 기법은 한정된 개수의 이산적 클락 주파수 값들만을 제공하는 DVFS 기반 멀티코어 프로세서 상에서 동작 가능하도록 설계되었다.
본 논문에서는 멀티코어 프로세서에 적합한 실시간 작업용 저전력 스케쥴링 기법을 제안하였다. 제안된 기법은 단일 작업을 여러 개의 코어들상에서 병렬로 수행하는 방법을 적용하였다.

가설 설정

(증명): 최적 스케쥴이 전력 비효율적 클락 주파수 F_y를 사용하여 C_y=(C_x+C_z)개의 연산 사이클들을 수행한다고 가정한다. .

제안 방법

제시된 기법이 전력 소모량을 줄이기 위해서 병렬 처리 기법을 활용하였다면, 기존 방법에서는 작업을 하나의 코어에서만 실행하였다. 기존 방법에서는 사용되지 않는 코어들의 전원을 소등하는 것을 고려하지 않았지만, 본 실험에서는 최대한 엄격한 조건에서 성능 비교가 되도록 사용되지 않는 코어들의 전원을 소등하도록 기존 방법을 개선하여 적용하였다. 또한 기존 방법은 DVFS 기법이 무한 개으로 연속된 클락 주파수들을 사용하는 비현실적 DVFS 기법을 가정하였지만, 본 실험에서는 유한개의 이산적 클락 주파수 값들을 사용하여 최소 전력 소모량의 가진 스케쥴을 찾도록 기존방법을 개선하여 적용하였다.
천개의 작업들을 우선적으로 생성하여, 생성된 과거의 계산량 정보를 이용하여 II장 2절에서 설명한 확률적 계산량 모델을 도출하였다. 도출된 확률적 계산량 모델을 기반으로 실시간 작업의 데드라인을 만족하면서 전력 소모량을 최소화하는 스케쥴을 찾았고, 평가 신뢰도를 높이기 위하여 작업을 십만번 생성하여 찾아딘 스케쥴들의 전력 소모량 평균 값을 실험 결과 지표로 사용하였다.
기존 방법에서는 사용되지 않는 코어들의 전원을 소등하는 것을 고려하지 않았지만, 본 실험에서는 최대한 엄격한 조건에서 성능 비교가 되도록 사용되지 않는 코어들의 전원을 소등하도록 기존 방법을 개선하여 적용하였다. 또한 기존 방법은 DVFS 기법이 무한 개으로 연속된 클락 주파수들을 사용하는 비현실적 DVFS 기법을 가정하였지만, 본 실험에서는 유한개의 이산적 클락 주파수 값들을 사용하여 최소 전력 소모량의 가진 스케쥴을 찾도록 기존방법을 개선하여 적용하였다. 평가 지표로는 ‘기존 방법이 소모하는 단위 시간당 전력량’ 대비 ‘제시된 방법이 소모하는 단위 시간당 전력량’ 비율을 ‘상대적 전력 소모량(Normalized Power Consumption: NPC)‘이라고 정의하고, 이를 제시된 방법의 성능 지표로 사용하였다.
제안된 기법에서는 단일 작업의 계산량을 여러 개의 코어들에 분배하여 동시에 수행하는 병렬 처리 기법을 적용하였고, 모든 프로세싱 코어들 중에서 일부의 코어들만을 사용하고 나머지 사용하지 않는 코어들의 전원은 소등하였다. 또한 작업의 변동하는 계산량을 과거의 계산량 분포도에 근거하여 확률적 계산량 모델로 표현하고, 도출된 확률적 계산량 모델에 근거하여 주어진 이산적 클락 주파수 값들을 적용하여 전력 소모량 기대 값을 최소화하였다.
멀티코어 프로세서에서 사용 가능한 프로세싱 코어들의 개수 N의 값과 병렬 처리 기법의 효율성 모델에 대한 제시된 방법의 상대적 전력 소모량을 측정하였다. 그림 3은 작업의 계산량 부하가 정규 분포를 이용하여 생성되었을 때의 결과를 보여주고 있다.
최근의 스케쥴링 기법들 [9]와 [10] 은 고정된 계산량을 가지는 작업들에 대해서는 전력 소모량을 효과적으로 줄이지만, 변동하는 계산량을 가지는 작업들에 대해서 비효율적으로 동작하는 방법이다. 반면 본 논문에서 제안된 스케쥴링 기법은 변동하는 계산량을 가지고 일정 간격으로 반복적으로 도착하는 주기적 작업(periodic task)에 대해서 전력 소모량을 효과적으로 줄이는 방법을 다루었다.
본 논문의 선행 연구인 [11]에서도 변동하는 계산량을 가진 단일 실시간 병렬 작업의 전력 소모량 확률적 기대 값을 최소화하는 스케쥴링 기법을 다루었다. 선행 연구에서는 무한개수의 연속된 클락 주파수 값들을 적용한 비현실적 DVFS 기법 환경에서 전력 소모량의 확률적 기대 값을 최소화하는 상대적으로 단순한 문제의 해법을 다루었고, 본 논문의 확장연구에서는 한정된 개수의 이산적 클락 주파수 값들만을 적용하는 현실적 DVFS 기법 환경에서 전력 소모량의 확률적 기대 값을 최소화하는 상대적으로 더 복잡한 문제의 최적 해법을 다루었다. 실제 생활에서 사용하는 DVFS 기반 프로세서는 한정된 개수의 이산적 클락 주파수 값들만을 제공하므로[3], 본 논문에서 제안된 기법이 실생활의 프로세서들에게 적용 가능한 실용적인 방법이다.
성능 평가를 위하여 제시된 기법과 기존 방법[8]의 전력소모량을 비교하였다. 제시된 기법이 전력 소모량을 줄이기 위해서 병렬 처리 기법을 활용하였다면, 기존 방법에서는 작업을 하나의 코어에서만 실행하였다.
성능 평가를 위하여 제시된 기법과 기존 방법[8]의 전력소모량을 비교하였다. 제시된 기법이 전력 소모량을 줄이기 위해서 병렬 처리 기법을 활용하였다면, 기존 방법에서는 작업을 하나의 코어에서만 실행하였다. 기존 방법에서는 사용되지 않는 코어들의 전원을 소등하는 것을 고려하지 않았지만, 본 실험에서는 최대한 엄격한 조건에서 성능 비교가 되도록 사용되지 않는 코어들의 전원을 소등하도록 기존 방법을 개선하여 적용하였다.
본 논문에서는 멀티코어 프로세서에 적합한 실시간 작업용 저전력 스케쥴링 기법을 제안하였다. 제안된 기법은 단일 작업을 여러 개의 코어들상에서 병렬로 수행하는 방법을 적용하였다. 또한 한정된 개수의 이산적 클락 주파수 값들만을 제공하는 환경에서, 제안된 기법이 확률적 계산량을 가진 실시간 병렬 작업의 데드라인을 만족하면서 전력 소모량의 확률적 기대 값을 최소화함을 수학적으로 증명하였다.
본 논문에서는 DVFS 기법을 제공하는 멀티코어 프로세서 상에서 주어진 단일 실시간 작업의 데드라인을 만족하면서 전력 소모량을 최소화는 스케쥴링 기법을 제안하였다. 제안된 스케쥴링 기법은 한정된 개수의 이산적 클락 주파수 값들만을 제공하는 DVFS 기반 멀티코어 프로세서 상에서 동작 가능하도록 설계되었다. 제안된 기법에서는 단일 작업의 계산량을 여러 개의 코어들에 분배하여 동시에 수행하는 병렬 처리 기법을 적용하였고, 모든 프로세싱 코어들 중에서 일부의 코어들만을 사용하고 나머지 사용하지 않는 코어들의 전원은 소등하였다.
모의실험에서는 작업들이 요구하는 연산 사이클 개수는 1K와 1000K 사이에서 정규 분포 또는 지수 분포를 따르도록 인위적으로 생성하였다. 천개의 작업들을 우선적으로 생성하여, 생성된 과거의 계산량 정보를 이용하여 II장 2절에서 설명한 확률적 계산량 모델을 도출하였다. 도출된 확률적 계산량 모델을 기반으로 실시간 작업의 데드라인을 만족하면서 전력 소모량을 최소화하는 스케쥴을 찾았고, 평가 신뢰도를 높이기 위하여 작업을 십만번 생성하여 찾아딘 스케쥴들의 전력 소모량 평균 값을 실험 결과 지표로 사용하였다.
평가 지표로는 ‘기존 방법이 소모하는 단위 시간당 전력량’ 대비 ‘제시된 방법이 소모하는 단위 시간당 전력량’ 비율을 ‘상대적 전력 소모량(Normalized Power Consumption: NPC)‘이라고 정의하고, 이를 제시된 방법의 성능 지표로 사용하였다.

대상 데이터

실용적인 DVFS 프로세서 실험을 위해서, 실제로 널리 사용되는 인텔 XScale 프로세서[3]의 DVFS 기법 데이터를 사용하였다. 표 1은 인텔 XScale 프로세서에서 제공하는 5개의 클락 주파수 값들과 단위 시간당 전력소모량 값을 보여주고 있다.

이론/모형

위의 변경된 수식들을 이용하여 Lagrange Multiplier Method[12]를 적용한다. L(π₂, .

성능/효과

또한 병렬 처리 기법의 효율성면에서 ‘선형 속도증가’모델이 전력 소모량 감소 효과가 가장 좋음을 보여주고 있다.
본 논문에서는 제안된 기법이 확률적 계산량을 가진 실시간 병렬 작업의 데드라인을 만족하면서 전력 소모량의 확률적 기대 값을 최소화함을 수학적으로 증명하였다. 또한 성능 평가 실험을 통하여, 제안된 기법이 기존 스케쥴링 기법의 전력소모량을 최대 81%까지 줄임을 보였다.
제안된 기법은 단일 작업을 여러 개의 코어들상에서 병렬로 수행하는 방법을 적용하였다. 또한 한정된 개수의 이산적 클락 주파수 값들만을 제공하는 환경에서, 제안된 기법이 확률적 계산량을 가진 실시간 병렬 작업의 데드라인을 만족하면서 전력 소모량의 확률적 기대 값을 최소화함을 수학적으로 증명하였다. 성능 평가 실험에서, 제안된 기법과 기존 스케쥴링 기법의 전력 소모량을 최대 81%까지 감소시킴을 확인하였다.
본 논문에서는 제안된 기법이 확률적 계산량을 가진 실시간 병렬 작업의 데드라인을 만족하면서 전력 소모량의 확률적 기대 값을 최소화함을 수학적으로 증명하였다. 또한 성능 평가 실험을 통하여, 제안된 기법이 기존 스케쥴링 기법의 전력소모량을 최대 81%까지 줄임을 보였다.
또한 한정된 개수의 이산적 클락 주파수 값들만을 제공하는 환경에서, 제안된 기법이 확률적 계산량을 가진 실시간 병렬 작업의 데드라인을 만족하면서 전력 소모량의 확률적 기대 값을 최소화함을 수학적으로 증명하였다. 성능 평가 실험에서, 제안된 기법과 기존 스케쥴링 기법의 전력 소모량을 최대 81%까지 감소시킴을 확인하였다.
선행 연구에서는 무한개수의 연속된 클락 주파수 값들을 적용한 비현실적 DVFS 기법 환경에서 전력 소모량의 확률적 기대 값을 최소화하는 상대적으로 단순한 문제의 해법을 다루었고, 본 논문의 확장연구에서는 한정된 개수의 이산적 클락 주파수 값들만을 적용하는 현실적 DVFS 기법 환경에서 전력 소모량의 확률적 기대 값을 최소화하는 상대적으로 더 복잡한 문제의 최적 해법을 다루었다. 실제 생활에서 사용하는 DVFS 기반 프로세서는 한정된 개수의 이산적 클락 주파수 값들만을 제공하므로[3], 본 논문에서 제안된 기법이 실생활의 프로세서들에게 적용 가능한 실용적인 방법이다.
제안된 스케쥴링 기법은 한정된 개수의 이산적 클락 주파수 값들만을 제공하는 DVFS 기반 멀티코어 프로세서 상에서 동작 가능하도록 설계되었다. 제안된 기법에서는 단일 작업의 계산량을 여러 개의 코어들에 분배하여 동시에 수행하는 병렬 처리 기법을 적용하였고, 모든 프로세싱 코어들 중에서 일부의 코어들만을 사용하고 나머지 사용하지 않는 코어들의 전원은 소등하였다. 또한 작업의 변동하는 계산량을 과거의 계산량 분포도에 근거하여 확률적 계산량 모델로 표현하고, 도출된 확률적 계산량 모델에 근거하여 주어진 이산적 클락 주파수 값들을 적용하여 전력 소모량 기대 값을 최소화하였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	프로세서의 전력 소모량을 효율적으로 관리하기 위한 고전적인 방법으로 무엇이 있는가?	배터리의 전원에 의지하여 동작하는 무선 컴퓨터 시스템에서는 프로세서가 소모하는 전력량을 줄이는 것은 매우 중요한 문제이다. 프로세서의 전력 소모량을 효율적으로 관리하기 위한 고전적인 방법으로, 작업을 수행하지 않는 유휴 시간(idle time) 동안 프로세서의 전원을 소등하는 power-down-when-idle 기법[2]이 있다. 프로세서의 전력 소모량을 더 효율적으로 관리하기 위해서 최근 들어 DVFS(dynamic voltage and frequency scaling) 기법[3]이 많이 사용되고 있다.
	병렬 처리 기법은 무엇인가?	병렬 처리 기법은 작업이 요구하는 전체 계산량을 여러 개의 부분들로 분리하여 다수의 코어들에게 분배하고, 분배된 계산량을 다수의 코어들이 동시에 실행하는 방법이다. 일반적으로 병렬 처리 기법을 적용한 작업의 실행 완료 시간은, 병렬 처리에 투입된 코어들의 개수로 비례하여 실행 시간이 단축된다.
	프로세서의 전력 소모량을 더 효율적으로 관리하기 위한 기법 중 하나인 DVFS 기법의 문제점은 무엇인가?	DVFS 기법은 프로세서의 부하에 따라 프로세서에 입력되는 전압을 변화시켜서 프로세서의 클락 주파수(clock frequency)와 전력 소모량을 동적으로 조절하는 기법이다. 입력 전압을 증가시키면 프로세서의 연산 속도를 결정하는 클락 주파수 값도 증가하지만 더불어 전력 소모량도 같이 증가한다. 유휴 시간 동안 프로세서의 전원을 소등하는 power-down-when-idle 기법보다 클락 주파수 값을 감소시키는 DVFS 기법이 실시간 작업의 전력 소모량을 줄이는데 더 효과적이다[3,4].

참고문헌 (12)

Semiconductor Industry Association (SIA), International Technology Roadmap for Semiconductors: 2005 Edition, http://www.itrs.net.
L. Benini, A. Bogliolo, and G. Micheli, "A survey of design techniques for system-level dynamic power management,'' IEEE Trans. VLSI Syst., vol. 8, no. 3, pp. 299-316, 2000.

상세보기
R. Xu, C. Xi, R. Melhem, and D. Moss, ''Practical PACE for embedded systems,'' ACM Int'l Conf. Embedded Software, 2005, pp. 54-63.
C. Yang, J. Chen, and T. Kuo, ''An approximation algorithm for energy-efficient scheduling on a chip multiprocessor,'' Design, Automation and Test in Europe Conf., 2005, pp. 468-473.
H. Aydin and Q. Yang, ''Energy-aware partitioning for multiprocessor real-time systems,'' Int'l Parallel Distributed Processing Symp., 2003, p. 113.2.
A. Andrei, P. Eles, Z. Peng, M. T. Schmitz, and B. Hashimi, ''Energy optimization of multiprocessor systems on chip by voltage selection,'' IEEE Trans. VLSI Syst., vol. 15, no. 3, pp. 262-275, 2007.

상세보기
E. Seo, J. Jeong, S. Park, and J. Lee, ''Energy efficient scheduling of real-time tasks on multicore processors,'' IEEE Trans. Parallel Distrib. Syst., vol. 19, no. 11, pp. 1540-1552, 2008.

상세보기
C. Xian, Y. Lu, and Z. Li, ''Energy-aware scheduling for real-time multiprocessor systems with uncertain task execution time," Design Automation Conf., pp. 664-669, 2007.
H. Pack, J. Yeo and W. Lee, ''Energy-efficient multi-core scheduling for real-time video processing,'' Journal of the Korea Society of Computer and Information, vol. 16, no. 6, pp. 11-20, 2011.

원문보기 상세보기
W. Lee, ''Power-efficient scheduling of periodic real-time tasks on lightly loaded multcore processors,'' Journal of the Korea Society of Computer and Information, vol. 17, no. 8, pp. 11-19, 2012.
W. Lee and K. Kim, ''Energy-saving stochastic scheduling of a real-time parallel task with varying computation amount on multi-core processors,'' IEICE Trans. Fundamentals, vol. E94-A, no. 2, pp. 842-845, 2011.

상세보기
D. Luenberger, Linear and Nonlinear Programming, Addison-Wesley, 1984.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증