Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân bổ điện áp tối thiểu cho các tác vụ có cấu trúc cây
Tóm tắt
Chúng tôi nghiên cứu việc lập lịch công việc trên các bộ xử lý có khả năng hoạt động với điện áp/tốc độ biến đổi nhằm giảm thiểu mức tiêu thụ năng lượng. Mỗi công việc trong một trường hợp vấn đề được xác định bởi thời gian đến và thời hạn, cùng với số chu kỳ CPU cần thiết. Được biết rằng lịch trình năng lượng tối thiểu cho n công việc có thể được tính toán trong thời gian O(n3), giả sử hàm năng lượng là lồi. Chúng tôi khảo sát các thuật toán hiệu quả hơn để tính toán lịch trình tối ưu khi các tập công việc có các cấu trúc đặc biệt nhất định. Khi các khoảng thời gian được cấu trúc thành cây, lịch trình năng lượng tối thiểu được chứng minh có một đặc trưng ngắn gọn và có thể được tính toán trong thời gian O(P) với P là tổng chiều dài đường đi của cây. Chúng tôi cũng nghiên cứu một phương pháp heuristics trung bình theo tỷ lệ AVR và chứng minh rằng mức tiêu thụ năng lượng của nó đạt được tỷ lệ cạnh tranh hằng số nhỏ đối với các tập công việc lồng trong và đối với các tập công việc có sự chồng chéo hạn chế. Một số kết quả mô phỏng cũng được đưa ra.
Từ khóa
#lập lịch công việc #tiết kiệm năng lượng #công việc có cấu trúc cây #thuật toán hiệu quả #heuristics trung bìnhTài liệu tham khảo
Augustine J, Irani S, Swamy C (2004) Optimal power-down strategies. In: Proc. of the 45th Annual Symposium on Foundations of Computer Science, pp. 530–539
Bansal N, Kimbrel T, Pruhs K (2004) Dynamic Speed Scaling to Manage Energy and Temperature. In: Proc. of the 45th Annual Symposium on Foundations of Computer Science, pp. 520–529 .
Blum M, Floyd R, Pratt V, Rivest R, Tarjan R (1973) Time Bounds for Selection. J Comp and Sys Sci 7:488–461
Intel Corporation, Wireless Intel SpeedStep Power Manager—Optimizing Power Consumption for the Intel PXA27x processor family. Wireless Intel SpeedStep(R) Power Manager White Paper, 2004
Jejurikar R, Gupta RK (2004) Dynamic Voltage Scaling for Systemwide Energy Minimization in Real-Time Embedded Systems. International Symposium on Low Power Electronics and Design
Kwon W, Kim T (2003) Optimal Voltage Allocation Techniques for Dynamically Variable Voltage Processors. 40th Design Automation Conference
Mochocki B, Hu XS, Quan G (2002) A Realistic Variable Voltage Scheduling Model for Real-Time Applications. IEEE/ACM International Conference on Computer-Aided Design
Yao F, Demers A, Shenker S (1995) A Scheduling Model for Reduced CPU Energy. In: Proc. of the 36th Annual Symposium on Foundations of Computer Science, 374–382
Yun HS, Kim J (2003) On Energy-Optimal Voltage Scheduling for Fixed-Priority Hard Real-Time Systems. ACM Transactions on Embedded Computing Systems 2(3):393–430