본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

고정 우선순위 경성 실시간 시스템에 대한 최적의 전압 스케줄링
On Energy-Optimal Voltage Scheduling for Fixed-Priority Hard Real-Time Systems

윤한샘   (서울대학교 컴퓨터공학부UU0000691  ); 김지홍   (서울대학교 전기컴퓨터공학부UU0000691  );
  • 초록

    본 논문에서는 고정 우선순위 경성 실시간 시스템에 대한 에너지 측면에서의 최적의 전압 스케줄링 문제를 고려한다. 먼저, 이 문제가 NP-hard임을 증명한다. 다음으로 이 문제에 대한 fully polynomial time approximation scheme(FPTAS)을 제시한다 제안한 FPTAS는 주어진 임의의 $\varepsilon$ $\varepsilon$ )배 이내에 있는 전압 스케줄을 문제의 입력의 크기와 1/ $\varepsilon$ 의 다항함수 이내의 시간에 계산해준다. 실험 결과, 제안된 FPTAS는 기존의 휴리스틱에 비해 더 효율적인 전압 스케줄을 더 빠른 시간에 찾아주었다.


    We address the problem of energy-optimal voltage scheduling for fixed-priority hard real-time systems. First, we prove that the problem is NP-hard. Then, we present a fully polynomial time approximation scheme (FPTAS) for the problem. for any $\varepsilon$ $\varepsilon$ ) times that of the optimal voltage schedule. Furthermore, the running time of the proposed approximation scheme is bounded by a polynomial function of the number of input jobs and 1/ $\varepsilon$ . Experimental results show that the approximation scheme finds more efficient voltage schedules faster than the best existing heuristic.


  • 주제어

    가변 전압 프로세서 .   동적 전압 조절 .   실시간 시스템.  

  • 참고문헌 (20)

    1. T. Sakurai and A. Newton. Alpha-power Law MOSFET Model and Its Application to CMOS Inverter Delay and Other Formulars. IEEE Journal of Solid State Circuits, vol. 25, no. 2, pp. 584-594, 1990 
    2. Intel Corporation. Intel XScale Technology. http://developer.intel.com/design/intelxscale, 2001 
    3. AMD Corporation. PowerNow! Technology. http://www.amd.com, 2000 
    4. Transmeta Corporation. Crusoe Processor, http://www.transmeta.com, 2000 
    5. H. Aydin, R. Melhem, D. Mosse and P. M. Alvarez. Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems. In Proc. of Real-Time Systems Symposium, 2001 
    6. I. Hong, G. Qu, M. Potkonjak and M. B. Srivastava. Synthesis Techniques for Low-Power Hard Real-Time Systems on Variable Voltage Processors. In Proc, of Real-Time Systems Symposium, pp. 178-187, 1998 
    7. W. Kim, J. Kim and S. L. Min. A Dynamic Voltage Scaling Algorithm for Dynamic-Priority Hard Real-Time Systems Using Slack Time Analysis. In Proc. of Design, Automation and Test in Europe, 2002 
    8. P. Pillai and K. G. Shin. Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems. In Proc. of ACM Symposium on Operating Systems Principles, 2001 
    9. F. Yao, A. Demers and S. Shenker. A Scheduling Model for Reduced CPU Energy. In Proc. of IEEE Annual Foundations of Computer Science, pp. 374-382, 1995 
    10. F. Gruian. Hard Real-Time Scheduling for Low-Energy Using Stochastic Data and DVS Processors. In Proc. of International Symposium on Low Power Electronics and Design, pp. 46-51, 2001 
    11. Y. Shin and K. Choi. Power Conscious Fixed Priority Scheduling for Hard Real-Time Systems. In Proc. of Design Automatioin Conference, pp. 134-139, 1999 
    12. G. Quan and X. Hu. Energy Efficient Fixed-Priority Scheduling for Real-Time Systems on Variable Voltage Processors. In Proc. of Design Automatioin Conference, pp. 828-833, 2001 
    13. G. Quan and X. Hu. An Optimal Voltage Schedule for Real-Time Systems on a Variable Voltage Processor. In Proc. of Design, Automation and Test in Europe, 2002 
    14. Y. Shin, K. Choi and T. Sakurai. Power Optimization of Real-Time Embedded Systems on Variable Speed Processors. In Proc. of International Conference on Computer-Aided Design, pp. 365-368, 2000 
    15. G. J. Woeginger. When Does a Dynamic Programming Formulation Guarantee the Existence of an FPTAS? In Proc. of ACM-SIAM Symposium on Discrete Algorithms, pp. 820-829, 1999 
    16. On Energy-Optimal Off-Line Scheduling for Fixed-Priority Hard Real-Time Systems On a Variable Speed Processor. Technical report, 2003. Available from http://davinci.snu.ac.kr/Download/opt_fp_vs.pdf 
    17. A. Ben-Tal and A. Nemirovski. Lectures on Modem Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM, 2001 
    18. M. Garey and D. Johnson. Computers and Intractability. W.H. Freeman and Company, 1979 
    19. N. Kim, M. Ryu, S. Hong, M. Saksena, C. Choi, H. Shin. Visual Assessment of a Real-Time System Design: A Case Study on a CNC Controller. In Proc. of Real-Time Systems Symposium, pp. 300-310, 1996 
    20. C. Locke, D. Vogel and T. Mesler. Building a Predictable Avionics Platform in Ada: A Case Study. In Proc. of Real-Time Systems Symposium, 1991 

 저자의 다른 논문

  • 김지홍 (27)

    1. 2000 "다중 이슈 프로세서를 위한 최악 실행시간 분석 기법" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (10): 848~860    
    2. 2001 "저전력 VLIW 명령어 추출을 위한 연산재배치 기법" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 28 (10): 530~540    
    3. 2001 "정적 시간 분석을 이용한 저전력 태스크내 전압 스케줄링" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 28 (11): 561~572    
    4. 2001 "디스크 배열-기반 주문형 비디오 서버에서의 탐색 시간 단축을 위한 효율적인 주기적 요청 묶음 기법" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 28 (12): 660~673    
    5. 2002 "가변 전압 프로세서를 위한 저전력 소프트웨어 설계 기법" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 20 (10): 21~28    
    6. 2002 "실행 시간 프로파일을 이용한 저전력 경성 실시간 프로그램용 동적 전압 조절 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (11): 601~610    
    7. 2003 "저전력을 소모하는 난수발생기의 성능 평가" 응용통계연구 = The Korean journal of applied statistics 16 (2): 427~440    
    8. 2003 "효율적인 슬랙 분석 방법에 기반한 경성 실시간 시스템에서의 동적 전압 조절 방안" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (12): 736~748    
    9. 2004 "압축블록의 압축률 분포를 고려해 설계한 내장캐시 및 주 메모리 압축시스템" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 31 (1): 125~134    
    10. 2004 "저전력 소프트웨어 개발을 위한 전력 분석 도구" 정보처리학회지 = Korea information processing society review 11 (6): 100~109    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기