ارائه یک مدل زمانبندی ایستای وظایف با استفاده از سوئیچینگ خطی فضای حالت
محورهای موضوعی : مجله فناوری اطلاعات در طراحی مهندسی
کلید واژه: پایداری, heuristic algorithm, زمانبندی وظایف, زمانبندی ایستا, سوئیچینگ خطی فضای حالت, سیستم های کنترل, Task scheduling, static scheduling, dynamic scheduling, linear switching state space,
چکیده مقاله :
چکیده:مسئله زمانبندی وظایف در سیستمهای پردازش توزیعی از جنبه های متفاوتی مانند ناهمگنی پردازشگرها،تحلیل کارایی و پیچیدگی های محاسباتی قابل بحث است. اساساً روشهای کلاسیک در این حوزه، مانندزمانبندی مبتنی بر لیست یا جستجوی تصادفی مبتنی بر الگوریتم های تکاملی، وابسته به ارزیابی کارایی بهشیوة عددی بوده و در تحلیلهای نظری با مشکلات متعدد روبرو هستند. به طور کلی این مقاله، مسئلۀ تحلیلنظری را با استفاده از یک روش مبتنی بر مهندسی سیستم، مورد بحث قرار می دهد، چگونگی نگاشتزمانبندی ایستای وظایف در فضای حالت غیر خطی را به اثبات می رساند و پایداری آن را از طریق تحلیلنظری نشان می دهد. اصولاً هدف از زمانبندی استاندارد وظایف، زمانبندی ایستا در سیستم های چندپردازنده ای است که با استفاده از تبدیل مناسب، به سوئیچینگ خطی فضای حالت با قیود غیر خطی تبدیلمی شود. سپس دو روش ارتفاع مرتب و وظایف آماده برای تعیین بردارهای کنترل ارائه می شود و پایداریبر روی چند HEFT آنها به اثبات می رسد. در نهایت، مقایسۀ نتایج حاصل از روشهای پیشنهادی با روشآزمون تصادفی، کارایی نسبی مدل ارائه شده را نشان می دهد.
AbstractTask Scheduling (TS) poses a challenging problem in distributed systems from multiple perspectivessuch as the uncertainty in resource capacity and topology, heterogeneity of processors, computationalcomplexity as well as theoretical performance analysis. To reach timely solutions, currentapproaches, whether classic approaches, which are based on list scheduling, or intelligentapproaches, which are generally based on evolutionary algorithms, either impose extra constraints orignore some aspects of the reality of this problem. Furthermore, they generally depend on numericalperformance evaluation and lack the ability to reach clear theoretical conclusions. Here, we addressthe problem of theoretical analysis by proposing a new paradigm based on system engineering. Thisnew modeling paradigm is promising due to its extensive theoretical developments. In its generalform, TS is inherently nonlinear because of its many nonlinear constraints. In this paper, wedemonstrate how TS can be mapped via nonlinear state space and, through theoretical analysis, showstability of the resulting system. Then, a suitable transformation is devised to convert this model tolinear switching state space with some nonlinear constraints. It is shown that the resulting model cansuitably represent uncertainty in resource capacity. We then present a systematic method todetermine control vectors based on this model. Finally, the proposed method is compared againstHEFT (heterogeneous earliest finish time) scheme on several random experiments and demonstratecomparative performance.
1. A.J. Page, T.J. Naughton, ”Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing,” in: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium, IEEE Computer Society, Washington, DC, USA, 2005, p. 189.1. 2. Y.K. Kwok and I. Ahmad, “Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 5, 1996, pp. 506-521. 3. H. Topcuoglu, et al., “Performance-effective and low-complexity task scheduling for heterogeneous computing,” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 3, 2002, pp. 260-274. 4. A. Rowhanimanesh, A. Karimpour, N. Pariz, “Optimal Path Planning for Controllability of Switched Linear Systems using Multi-Level Constrained GA”, Applications ofSoft Computing: From Theory to Praxis, Springer, Series: Advances in Intelligent and Soft Computing, Volume 58/2009, Pages: 399-408. 5. Z. Sun, S.S. Ge, “Switched Linear Systems: Control and Design (Communications and Control Engineering“), Springer, 2005. ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 24 6. O. Sinnen, Task scheduling for parallel systems, JohnWiley & Sons-Interscience, 2007. 7. O. Sinnen, et al., “Toward a realistic task scheduling model,” IEEE Trans. Parallel and Distributed Systems, vol. 17, no. 3, 2006, pp. 263-275. 8. M. Yoo and M. Gen, “Scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm in heterogeneous multiprocessors system,” Computers & Operations Research, vol. 34, 2007, pp. 3084 – 3098. 9. S.-C. Cheng, et al., “Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints,” Expert Systems with Applications, vol. 36, no. 1, 2009, pp. 852–860. 10. M. Yoo, “Real-time task scheduling by multiobjective genetic algorithm,” Systems and Software, vol. 82, no. 4, 2009, pp. 619-628. 11. K. Shin, et al., “Task scheduling algorithm using minimized duplications in homogeneous systems,” Parallel and Distributed Computing, vol. 68, 2008, pp. 1146–1156. 12.X. Kong, et al., “Permutation-based Particle Swarm Algorithm for Tasks Scheduling in Heterogeneous systems with Communication Delays,” Computational Intelligence Research, vol. 4, no. 1, 2008, pp. 61–70. 13.I.-H. Kuo, et al., “An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model,” Expert Systems with Applications, 2008. 14.H.-S. Choi and D.-H. Lee, “Scheduling algorithms to minimize the number of tardy jobs in twostage hybrid flow shops,” Computers & Industrial Engineering, 2008. 15.R. Hwang, et al., “A comparison of multiprocessor task scheduling algorithms with communication costs,” Computers & Operations Research, vol. 35, 2008, pp. 976 – 993. 16.K. Ogata, Discrete-Time Control Systems, Prentice Hall, 1995. 17.C.-T. Chen, Linear System Theory and Design, Oxford University Press, USA, 1995. 18.H. Ozbay, Introduction to feedback control theory. CRC Press-Technology & Engineering, 1999. 19.S. Al-Sharaeh and B.E. Wells, “A Comparison of Heuristics for List Schedules using The Boxmethod and P-method for Random Digraph Generation,” Proc. of the 28th Southeastern Symposium on System Theory, 1996, pp. 467–471. 20.L.G. Q., et al., “Iterative list scheduling for heterogeneous computing,” Parallel and Distributed Computing, vol. 65, no. 5, 2005, pp. 654–665.
_||_