請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38576完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 郭大維(Tei-Wei Kuo) | |
| dc.contributor.author | Chin-Fu Kuo | en |
| dc.contributor.author | 郭錦福 | zh_TW |
| dc.date.accessioned | 2021-06-13T16:37:56Z | - |
| dc.date.available | 2007-07-07 | |
| dc.date.copyright | 2005-07-07 | |
| dc.date.issued | 2005 | |
| dc.date.submitted | 2005-07-05 | |
| dc.identifier.citation | [1] L. Abeni and G. Butazzo. QoS guarantee using probabilistic deadlines. In Multiprocessor
EDF and Deadline Monotonic Schedulability Analysisthe IEEE Euromicro Conference on Real-Time Systems, pages 242–249, June 1999. [2] L. Abeni and G. Buttazzo. Integrating multimedia applications in hard real-time systems. In the Proceedings of the 18th IEEE Real Time Systems Symposium, pages 4–13, December 1998. [3] M.D.M. Akbar, E.G. Manning, G.C. Shoja, and S. Khan. Heuristic solutions for the multiple-choice multi-dimension knapsack problem. In International Conference on Computational Science, pages 659–668, 2001. [4] T.P. Baker. Multiprocessor edf and deadline monotonic schedulability analysis. In the Proceedings of the 24th IEEE Real-Time Systems Symposium, pages 120–129, December 2003. [5] A. Barbato and P. Giustiniani. An improved scheduling algorithm for a naval phased array radar. In Radar 92. International Conference, pages 42–45, 1992. [6] S. Baruah, J. Goossens, and G. Lipari. Implementing constant-bandwidth servers upon multiprocessor platforms. In the Proceedings of the 8th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 154–163, September 2002. [7] R.A. Baugh. Computer Control of Modern Radars. RCAM&SR-Moorestown Library, 1973. [8] C. Bergenhem, M. Jonsson, B. Gorden, and A. Ahlander. Heterogeneous real-time services in high-performance system area networks - application demands and case study definitions. Technical Report IDE - 0254, School of Information Science, Computer and Electrical Engineering (IDE), Halmstad University, 2002. [9] R. Bettati. End-To-End Scheduling To Meet Deadlines In Distributed Systems. PhD thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 1994. [10] R. Bettati and J.W.-S. Liu. End-to-end scheduling to meet deadlines in distributed systems. In the Proceedings of the 2th IEEE International Conference on Distributed Computing Systems, pages 452–459, December 1990. [11] W.D. Blair, G.A. Watson, T. Kirubarajan, and Y. Bar-Shalom. Benchmark for radar allocation and tracking in ECM. IEEE Transactions on Aerospace and Electronic Systems, 34(4):1097–1114, October 1998. [12] M. Brahumi and D.J. Worthington. Queueing models for out-patient appointment systems- a case study. Journal of the Operational Research Society, 42:733–746, 1991. [13] C. Chang and T.-C.Wang. Use object-oriented paradigm to design a programmable radar digital signal processor. In the Workshop on Object-Oriented Technology and Applications, 1997. [14] J.P. Chawla, S.I. Marcus, and M.A. Shayman. Stability of wireless networks for mode S radar. In the Proceedings of the 32nd Conference on Information Sciences and Systems, 1998. [15] D. Chen, A.K. Mok, and S.K. Baruah. Scheduling distributed real-time tasks in the DGMF model. In the Proceedings of the IEEE Real Time Technology and Applications Symposium, pages 14–22, March 2000. [16] T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. McGraw-Hill, second edition, 2001. [17] S.K. Dhall. Scheduling Periodic-Time-Critical Jobs on Single Processor and Multiprocessor Computing Systems. PhD thesis, University of Illinois, Urbana, 1977. [18] S.D. Elton and B.J. Slocumb. Robust parameter estimation for periodic point process signals using circular statistics. In the Proceedings of Signal Processing VIII, Theories and Applications (EUSIPCO-96), 1996. [19] W. Fan, E.A. Fox, P. Pathak, and H. Wu. The effects of fitness functions on genetic programming-based ranking discovery for web search. Journal of the American Society for Information Science and Technology, 55(7):628–636, 2004. [20] M.R. Garey and D.S. Johnson. Computers and Intractability: A guide to the Theory of NP-Completeness. W. H. Freeman & Company, San Francisco, 1979. [21] S. Ghosh, J. Hansen, R. Rajkumar, and J. Lehoczky. Integrated resource management and scheduling with multi-resource constraints. In the Proceedings of the 25th IEEE Real- Time Systems Symposium, pages 12–22, December 2004. [22] S. Gopalakrishnan, M. Caccamo, C.-S. Shih, C.-G. Lee, and L. Sha. Finite-horizon scheduling of radar dwells with online template construction. In the Proceedings of the 25th IEEE Real-Time Systems Symposium, pages 23–33, December 2004. [23] C.C. Han and K.J. Lin. Scheduling distance-constrained real-time tasks. In the Proceedings of the 13th IEEE Real-Time Systems Symposium, pages 300–308, December 1992. [24] R.V. Hogg and E.A. Tanis. Probability and Statistical Inference. Prentice Hall, 2001. [25] J.A. Hoogeveen, J.K. Lenstra, and B. Veltman. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. European Journal of Operational Research, 89(1):172– 175, 1996. [26] A.G. Huizing and A.A.F. Bloemen. An efficient scheduling algorithm for a multifunction radar. In IEEE International Radar Conference, pages 359–364, 1996. [27] A. Izquierdo-Fuente and J.R. Casar-Corredera. Approach to multifunction radar scheduling simulation. In IEEE Telesystems Conference, pages 67–70, 1994. [28] K. Jeffay and S. Goddard. A theory of rate-based execution. In the Proceedings of the 20th IEEE Real-Time Systems Symposium, pages 304–314, December 1999. [29] B. Kao and H. Garcia-Molina. Deadline assignment in a distributed soft real-time system. IEEE Transactions on Parallel and Distributed Systems, 8(12):1268–1274, 1997. [30] S. Khan. Quality Adaptation in a Multi-Session Adaptive Multimedia System: Model and Architecture. PhD thesis, Department of Electrical and Computer Engineering, University of Victoria, 1998. [31] L. Kleinrock. Queueing Systems Volume II: Computer Applications. Wiley-Interscience Publication, 1976. [32] J.W. Layland. Real-Time System. Prentice Hall, 2000. [33] C. Lee, J. Lehoczky, D. Siewiorek, R. Rajkumar, and J. Hansen. A scalable solution to the multi-resource QoS problem. In the Proceedings of the 20th IEEE Real-Time Systems Symposium, pages 315–326, December 1999. [34] C.-G. Lee, P.-S. Kang, C.-S. Shih, and L. Sha. Radar dwell scheduling considering physical characteristics of phased array antenna. In the Proceedings of The IEEE 24th Real- Time Systems Symposium, pages 14–24, December 2003. [35] C.G. Lee, C.S. Shih, and L. Sha. Service class-based online QoS management in surveillance radar systems. In the Proceedings of the 22nd IEEE Real-Time Systems Symposium, pages 139–150, December 2001. [36] K.J. Lin, S. Natarajan, and J.W.-S. Liu. Imprecise results: Utilizing partial computations in real-time systems. In the Proceedings of the 8th IEEE Real-Time Systems Symposium, pages 210–217, December 1987. [37] 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. [38] X. Liu and S. Goddard. Resource sharing in an enhanced rate-based execution model. In the Proceedings of the 15th Euromicro Conference on Real-Time Systems, pages 131–140, 2003. [39] S. Martello and P. Toth. Knapsack problems : algorithms and computer implementations. Kluwer Academic Publishers, 1990. [40] A.K. Mok. Fundamental Design Problems for the Hard Real-Time Environment. PhD thesis, MIT, Cambridge, MA, 1983. [41] A.K. Mok and D. Chen. A multiframe model for real-time tasks. IEEE Transactions on Software Engineering, 23(10):635–645, October 1997. [42] R.L. Nevin and F.W. Schatz. AN/APG-67 multimode radar development. In IEEE International Radar Conference, pages 1–8, 1985. [43] A.K. Parekh and R.G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single node case. In the Proceedings of IEEE INFOCOM, pages 915–924, 1992. [44] J.-C. Pomerol and S. Barba-Romero. Multicriterion decision in management : principles and practice. Wiley & Sons, 1990. [45] Rapid prototyping of Application Specific Signal Processors (RASSP). http://eto.sysplan.com/eto/rassp. 2000. [46] R. Rajkumar, C. Lee, J. Lehoczky, and D. Siewiorek. A resource allocation model for QoS management. In the Proceedings of the 18th IEEE Real-Time Systems Symposium, pages 298–307, December 1997. [47] D. Rosu, K. Schwan, and S. Yalamanchili. FARA - a framework for adaptive resource allocation in complex real-time systems. In the Proceedings of the 4th IEEE Real Time Technology and Applications Symposium, pages 79–84, June 1998. [48] L. Sha, R. Rajkumar, and J.P. Lehoczky. Priority inheritance protocols: An approach to real-time synchronization. IEEE Transactions on Computers, 39(9):1175–1185, September 1990. [49] C.-S. Shih, S. Gopalakrishnan, P. Ganti, M. Caccamo, and L. Sha. Template-based realtime dwell scheduling with energy constraint. In the Proceedings of the 9th IEEE Real- Time and Embedded Technology and Applications Symposium, May 2003. [50] C.-S. Shih, S. Gopalakrishnan, P. Ganti, M. Caccamo, and L. Sha. Schedulability and fairness for computation tasks in surveillance radar systems. In the Proceedings of the 10th Real-time and Embedded Computing Systems and Applications Conference, 2004. [51] J.F. Shortle, P.H. Brill, M.J. Fischer, D. Gross, and D.M.B. Masi. An algorithm to compute the waiting time distribution for the M/G/1 queue. INFORMS Journal on Computing, 16(2):152–161, 2004. [52] B. Sprunt, L. Sha, and J. Lehoczky. Aperiodic task scheduling for hard-real-time systems. Real-Time Systems, 1(1):27–60, July 1989. [53] M. Spuri, G. Buttazzo, and F. Sensini. Scheduling aperiodic tasks in dynamic scheduling environment. In the Proceedings of the 16th IEEE Real-Time Systems Symposium, 1995. [54] L.H. Su. A hybrid two-stage flowshop with limited waiting time constraints. Computers and Industrial Engineering, 44(3):409–424, 2003. [55] J. Sun. Fixed-Priority End-to-End Scheduling in Distributed Real-time Systems. PhD thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, year 1997. [56] Y. Toyoda. A simplified algorithm for obtaining approximate solution to zero-one programming problems. Management Science, 21:1417–1427, 1975. [57] E.J. Watson. Laplace Transforms and Applications. Birkhauserk, 1981. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38576 | - |
| dc.description.abstract | 近幾年來，隨著軟硬體的進步，有許多現代化的元件導向分散系統，例如相位雷達，已利用商用元件來建構而成，除此之外，許多硬體元件的功能逐漸可以利用軟體模組來實作。這些系統中的工作可以被當成分散式的即時工作，這些工作有點對點截限時間保證需求，以及有執行先後關係限制。在這論文中，我們提出一個有機率效能保證的兩階段排程演算法，另外當考慮到如果沒有工作的完整優先權關係或是執行工作後所獲得的利益值時，我們提出一個階層資源分配架。
我們以元件導向雷達系統當作一個例子來展示我們所提出方法的可行性，我們所提出的方法與以往和資源使用效率有關的演算法或是沒有可排程保證分析方法不同，因為我們對前後端的工作提出了一個聯合的即時排程演算法，這個方法可以作為離線式的機率分析與執行時的許可控制機制。除此之外，我們也發展了一套階層式的資源分配架構，這個方法包含了兩個階段：在離線階段中，這個演算法利用動態程式規劃方法來計算出一些狀態的次佳資源分配方式；而在執行階段，這個演算法利用貪婪方法來找到一個由離線階段所計算出的次佳資源分配方式。除了元件導向雷達系統可以使用我們所提出的想法外，這些想法也適用於許多元件導向分散式系統的設計上。 | zh_TW |
| dc.description.abstract | In recent years, many modern component-oriented distributed
systems, such as phased array radars, are built with commercial-off-the-shelf components, and the functions of many hardware components are also re-implemented by software modules. In such systems, tasks could be modelled as distributed real-time tasks which require end-to-end deadline guarantees and have precedence constraints. In this thesis, we propose a two stage scheduling algorithm with emph{probabilistic timing guarantees} and a hierarchical emph{resource allocation} framework with no totally ordered importance or numeric utility value for every task. We take component-oriented radar systems as a case study to demonstrate the feasibility of our work. Different from most previous work on either algorithms with restrictions in resource utilization or heuristics without analytical ways for schedulability guarantees, we propose a joint real-time scheduling algorithm for both front-end and back-end processor workloads with an analytical framework for off-line probabilistic analysis and on-line admission control. We also develop a hierarchical resource allocation framework. This approach consists of two phases: In the off-line phase, the algorithm computes the sub-optimal resource configuration assignments for few workload states by a dynamic programming approach; in the on-line phase, the algorithm computes resource reconfiguration assignments by a greedy approach, provided that sub-optimal resource reconfiguration assignments for several selected workload states are computed in the off-line phase. Beside component-oriented radar systems, the ideas presented in this thesis could be applied to the designs of many component-oriented distributed systems. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T16:37:56Z (GMT). No. of bitstreams: 1 ntu-94-D91922012-1.pdf: 567204 bytes, checksum: a47aa54c4e413345abc7189c6f7dff6b (MD5) Previous issue date: 2005 | en |
| dc.description.tableofcontents | 1 Introduction 7
1.1 Resource Management for Distributed Systems . . . . . . . . . . . . . . . . . 7 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 RelatedWork 13 2.1 Probabilistic Timing Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Resource Allocation Framework for Tasks with Partially Ordered Importance . 15 3 Hardware Configuration Diagram and Workload Characteristics 17 3.1 Hardware Configuration Diagram . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Workload Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4 Component-Oriented Radars with Probabilistic Timing Guarantees 21 4.1 Task Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 Probabilistic Schedulability Guarantees under Two-Stage Scheduling . . . . . . 22 4.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.2 Probabilistic Guarantees for Beam-Transmission Scheduling . . . . . . 24 4.2.3 Rate-Based Scheduling for Signal Processing . . . . . . . . . . . . . . 29 4.2.4 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.3.1 Experiment Setup and Performance Metrics . . . . . . . . . . . . . . . 37 4.3.2 Analysis Results and Experimental Results . . . . . . . . . . . . . . . 39 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5 A Resource Allocation Framework for Real-Time Tasks with Partially Ordered Importance 46 5.1 Formal Model and Problem Formulation . . . . . . . . . . . . . . . . . . . . . 46 5.2 A Hierarchical Resource Management Framework . . . . . . . . . . . . . . . . 52 5.2.1 Formulating the Problem as an Integer Linear Programming Problem . 52 5.2.2 Sub-optimal Resource Allocation for Off-line Design . . . . . . . . . . 55 5.2.3 On-line Phase: Approximating Feasible Resource Configuration Assignments for Run-Time Workload States . . . . . . . . . . . . . . . . 60 5.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.3.1 Experiment Setup and Performance Metrics . . . . . . . . . . . . . . . 67 5.3.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6 Conclusion and Future Work 79 Bibliography 81 | |
| dc.language.iso | en | |
| dc.subject | 即時資源分配 | zh_TW |
| dc.subject | 相位雷達 | zh_TW |
| dc.subject | 即時工作排程 | zh_TW |
| dc.subject | 機率效能保證 | zh_TW |
| dc.subject | 分散式系統 | zh_TW |
| dc.subject | Phased-Array Radar | en |
| dc.subject | Real-Time Resource Allocation | en |
| dc.subject | Distributed Systems | en |
| dc.subject | Probabilistic Performance Guarantee | en |
| dc.subject | Real-Time Task Scheduling | en |
| dc.title | 具點對點截限時間之即時資源管理 | zh_TW |
| dc.title | Real-Time Resource Management for End-to-End Deadlines | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 93-2 | |
| dc.description.degree | 博士 | |
| dc.contributor.oralexamcommittee | 何建明(Jan-Ming Ho),薛智文(Chih-Wen Hsueh),逄愛君(Ai-Chun Pang),吳家麟(Ja-Ling Wu),劉邦鋒(Pang-Feng Liu),林風(Phone Lin),施吉昇(Chi-Sheng Shih) | |
| dc.subject.keyword | 相位雷達,即時工作排程,機率效能保證,分散式系統,即時資源分配, | zh_TW |
| dc.subject.keyword | Phased-Array Radar,Real-Time Task Scheduling,Probabilistic Performance Guarantee,Distributed Systems,Real-Time Resource Allocation, | en |
| dc.relation.page | 87 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2005-07-06 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-94-1.pdf 未授權公開取用 | 553.91 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。