請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31783完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 郭大維(Tei-Wei Kuo) | |
| dc.contributor.author | Heng-Ruey Hsu | en |
| dc.contributor.author | 許恒瑞 | zh_TW |
| dc.date.accessioned | 2021-06-13T03:20:06Z | - |
| dc.date.available | 2007-08-01 | |
| dc.date.copyright | 2006-08-01 | |
| dc.date.issued | 2006 | |
| dc.date.submitted | 2006-07-28 | |
| dc.identifier.citation | [1] T. A. AlEnawy and H. Aydin. On energy-constrained real-time scheduling. In EuroMicro
Conference on Real-Time Systems (ECRTS'04), pages 165.174, 2004. [2] T. A. AlEnawy and H. Aydin. Energy-aware task allocation for rate monotonic scheduling. In Proceedings of the 11th IEEE Real-time and Embedded Technology and Applications Symposium (RTAS'05), pages 213.223, 2005. [3] T. A. AlEnawy and H. Aydin. Energy-constrained scheduling for weakly-hard real-time systems. In Proceedings of the 26th IEEE Real-time Systems Symposium (RTSS'05), pages 376.385, 2005. [4] H. Aydin, R. Melhem, D. Moss’e, and P. Mej’ a-Alvarez. Determining optimal processor speeds for periodic real-time tasks with different power characteristics. In Proceedings of the IEEE EuroMicro Conference on Real-Time Systems, pages 225.232, 2001. [5] H. Aydin, R. Melhem, D. Moss’e, and P. Mej’ a-Alvarez. Dynamic and aggressive scheduling techniques for power-aware real-time systems. In Proceedings of the 22nd IEEE Real- Time Systems Symposium, pages 95.105, 2001. [6] H. Aydin and Q. Yang. Energy-aware partitioning for multiprocessor real-time systems. In Proceedings of 17th International Parallel and Distributed Processing Symposium (IPDPS), pages 113 . 121, 2003. [7] N. Bansal, T. Kimbrel, and K. Pruhs. Dynamic speed scaling to manage energy and temperature. In Proceedings of the Symposium on Foundations of Computer Science, pages 520.529, 2004. [8] T. Blickle, J. Teich, and L. Thiele. System-level synthesis using evolutionary algorithms. In Design Automation for Embedded Systems, pages 23.58. Boston. Manufactured in The Netherlands, 1998. [9] J. S. Chase, D. C. Anderson, P. N. Thakar, A. Vahdat, and R. P. Doyle. Managing energy and server resources in hosting centres. In Symposium on Operating Systems Principles, pages 103.116. ACM Press, 2001. [10] J.-J. Chen, H.-R. Hsu, K.-H. Chuang, C.-L. Yang, A.-C. Pang, and T.-W. Kuo. Multiprocessor energy-ef cient scheduling with task migration considerations. In EuroMicro Conference on Real-Time Systems (ECRTS'04), pages 101.108, 2004. [11] J.-J. Chen, H.-R. Hsu, and T.-W. Kuo. Leakage-aware energy-ef cient scheduling of realtime tasks in multiprocessor systems. In IEEE Real-time and Embedded Technology and Applications Symposium, pages 408.417, 2006. [12] J.-J. Chen and T.-W. Kuo. Multiprocessor energy-ef cient scheduling for real-time tasks. In International Conference on Parallel Processing (ICPP), pages 13.20, 2005. [13] J.-J. Chen and T.-W. Kuo. Voltage-scaling scheduling for periodic real-time tasks in reward maximization. In the 26th IEEE Real-Time Systems Symposium (RTSS), pages 345.355, 2005. [14] J.-J. Chen, T.-W. Kuo, and C.-S. Shih. 1+ approximation clock rate assignment for periodic real-time tasks on a voltage-scaling processor. In the 2nd ACM Conference on Embedded Software (EMSOFT), pages 247.250, 2005. [15] J.-J. Chen, T.-W. Kuo, and C.-L. Yang. Pro t-driven uniprocessor scheduling with energy and timing constraints. In ACM Symposium on Applied Computing, pages 834.840, 2004. [16] G. B. Dantzig and M. N. Thapa. Linear Programming 1: Introduction. Springer Verlag, 1997. [17] B. Dave, G. Lakshminarayana, and N. K. Jha. Cosyn: Hardware-software co-synthesis of embedded systems. IEEE Transactions VLSI Systems, 7, Mar. 1999. [18] Y. G. Decastelo, M. Potkonjak, and A. Parker. Optimal ILP-based approach for throughtput optimization using simultaneous algorithm/architecture matching and retiming. In Proceedings of Design Automation Conf. (DAC), pages 113.118, 1995. [19] R. P. Dick and N. K. Jha. Cowls: Hardware-software co-synthesis of distributed wireless low-power embedded client-server systems. In Proceedings of International Conference VLSI Design, Jan. 2000. [20] J. G. Dù Ambrosio and X. Hu. Con guration-level hardware/software partition for realtime embedded systems. In Proceedings of CODES/CASHE'94, Third InternationalWorkshop on Hardware/Software Codesign, pages 34.41, Sept. 1994. [21] M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman and Co., 1979. [22] GNU Linear Programming Kit. http://www.gnu.org/software/glpk/glpk.html. [23] F. Gruian. System-level design methods for low-energy architectures containing variable voltage processors. In Power-Aware Computing Systems, pages 1.12, 2000. [24] F. Gruian and K. Kuchcinski. Lenes: Task scheduling for low energy systems using variable supply voltage processors. In Proceedings of Asia South Paci c Design Automation Conference, pages 449.455, 2001. [25] T. Ishihara and H. Yasuura. Voltage scheduling problems for dynamically variable voltage processors. In Proceedings of the International Symposium on Low Power Electronics and Design, pages 197.202, 1998. [26] N. K. Jha. Low power system scheduling and synthesis. In Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, pages 259.263, 2001. [27] D.-I. Kang, S. P. Crago, and J. Suh. A fast resource synthesis technique for energy-ef cient real-time systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium, pages 225.234, 2002. [28] D. Kirovski and M. Potkonjak. System-level synthesis of low-power hard real-time systems. In Proceedings of the 34th ACM/IEEE Conference on Design Automation Conference, pages 697.702, 1997. [29] C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-realtime environment. Journal of the ACM, 20(1):46.61, 1973. [30] J. W. Liu. Real-Time Systems. Prentice Hall, Englewood, Cliffs, NJ., 2000. [31] P. Mej’ a-Alvarez, E. Levner, and D. Moss’e. Adaptive scheduling server for power-aware real-time tasks. ACM Transactions on Embedded Computing Systems, 3(2):284.306, 2004. [32] R. Mishra, N. Rastogi, D. Zhu, D. Moss’e, and R. Melhem. Energy aware scheduling for distributed real-time systems. In International Parallel and Distributed Processing Symposium, page 21, 2003. [33] C. H. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, 1994. [34] P. Pillai and K. G. Shin. Real-time dynamic voltage scaling for low-power embedded operating systems. In Proceedings of the 18th ACM Symposium on Operating Systems Principles, pages 21.24, 2001. [35] K. Pruhs, P. Uthaisombut, and G. J. Woeginger. Getting the best response for your erg. In 9th Scandinavian Workshop on Algorithm Theory (SWAT), pages 14.25, 2004. [36] C. Rusu, R. Melhem, and D. Mosse. Maximizing the system value while satisfying time and energy constraints. In IEEE 23th Real-Time System Symposium, pages 246.255, Dec. 2002. [37] C. Rusu, R. Melhem, and D. Moss’e. Multiversion scheduling in rechargeable energyaware real-time systems. In EuroMicro Conference on Real-Time Systems (ECRTS'03), pages 95.104, 2003. [38] Z. Shao, Q. Zhuge, X. Chun, and E. H.-M. Sha. Ef cient assignment and scheduling for heterogeneous dsp systems. IEEE Transaction on Parallel and Distributed Systems, 16(6):516.525, June 2005. [39] N. Shenoy, P. Banerjee, and A. N. Choudhary. A system-level synthesis algorithm with guaranteed solution quality. In DATE, pages 417., 2000. [40] V. V. Vazirani. Approximation Algorithms. Springer, 2001. [41] C.-Y. Yang, J.-J. Chen, and T.-W. Kuo. An approximation algorithm for energy-ef cient scheduling on a chip multiprocessor. In Proceedings of the 8th Conference of Design, Automation, and Test in Europe (DATE), pages 468.473, 2005. [42] F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced CPU energy. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 374.382. IEEE, 1995. [43] Y. Zhang, X. Hu, and D. Z. Chen. Task scheduling and voltage selection for energy minimization. In Annual ACM IEEE Design Automation Conference, pages 183.188, 2002. [44] D. Zhu, R. Melhem, and B. Childers. Scheduling with dynamic voltage/speed adjustment using slack reclamation in multi-processor real-time systems. In Proceedings of IEEE 22th Real-Time System Symposium, pages 84.94, 2001. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31783 | - |
| dc.description.abstract | 系統省電設計在硬體或軟體的實作上已經是一個很重要的問題，而在嵌入式系統上更顯得重要。這篇論文主要是針對各種異質性的多處理器系統所做的省電研究，該如何在能源限制之下去排程週期性的即時工作。在這個問題上，每個工作都必需在一個處理器上執行，而在不
同處理器上執行會有不同的執行時間和不同的能源消耗，我們的目標要將整個系統的處理器成本降到最低，而且仍要滿足能源和時間上的限制。我們證明這個問題是一個NP-hard的問>題，除非NP等於P，否則沒有常數倍的多項式時間逼近演算法，我們對於這個問題提供了一>個 (m+2) 倍的多項式時間逼近演算法，m 是可使用處理器的種類數目，實驗結果顯示由我>們提供的演算法所得到的答案非常接近最佳解。 | zh_TW |
| dc.description.abstract | The energy-aware design for electronic systems has been an important issue in hardware and software implementations, especially for embedded systems. This paper targets a synthesis problem for heterogeneous multiprocessor systems to schedule a set of periodic real-time tasks under a given energy consumption constraint. Each task is required to execute on a processor without migration, where tasks might have different execution times on different processor types. Our objective is to minimize the processor cost of the entire system under the given timing and energy consumption constraints. The problem is first shown being NP-hard and having no polynomial-time algorithm with a constant approximation ratio unless NP = P. We propose polynomial-time approximation algorithms with (m+2)-approximation ratios for this challenging problem, where m is the number of the available processor types. Experimental results show that the proposed algorithms could always derive solutions with system costs close to those of optimal solutions. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T03:20:06Z (GMT). No. of bitstreams: 1 ntu-95-R93922046-1.pdf: 586979 bytes, checksum: cb3ef9526f9ae1da5dace851749880e9 (MD5) Previous issue date: 2006 | en |
| dc.description.tableofcontents | Chinese Abstract ii
English Abstract iii Acknowledgements iv Contents vi List of Tables viii List of Figures ix 1 Introduction 1 1.1 Related work 3 1.2 Organization 4 2 Problem Denition 5 3 Approximation Algorithms 9 3.1 Integer Programming and Relaxations 9 3.2 Approximation Algorithms Based on Parametric Rounding 14 4 Performance Evaluation 21 4.1 Experimental Setups 21 4.2 Experimental Results 23 5 Conclusion 31 Bibliography 32 Appendix A : GLKP Model 37 Appendix B : GLKP Data 38 | |
| dc.language.iso | en | |
| dc.title | 在省電考量下之週期性硬式即時程序的多處理器系統組態 | zh_TW |
| dc.title | Multiprocessor Synthesis for Periodic Hard Real-Time Tasks under a Given Energy Constraint | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 94-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 逄愛君(Ai-Chun Pang),施吉昇(Chi-Sheng Shih),呂學一(Hsueh-I Lu),薛智文(Chih-Wen Hsueh) | |
| dc.subject.keyword | 省電,週期性,硬式即時程序,多處理器,系統組態, | zh_TW |
| dc.subject.keyword | Multiprocessor,Hard Real-Time Tasks,Synthesis,Periodic,Energy, | en |
| dc.relation.page | 38 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2006-07-30 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-95-1.pdf 目前未授權公開取用 | 573.22 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。