یک الگوریتم زمان‌بندی وظیفه چندهدفه بر اساس الگوریتم ژنتیک برای طراحی سیستم‌های نهفته
محورهای موضوعی :محدثه نیک سرشت 1 , محسن راجی 2
1 - دانشجو
2 - دانشگاه شیراز
کلید واژه: سیستم‌های نهفته, زمان‌بندی وظیفه, بهینه‌سازی چندهدفه, الگوریتم ژنتیک.,
چکیده مقاله :
طراحان سیستم‌های نهفته با الزامات و اهداف متعددی در طراحی (مانند زمان اجرا، انرژی مصرفی و قابلیت اطمینان) مواجه هستند. ازآنجاکه در بیشتر مواقع، تلاش برای برآوردن یکی از این الزامات در تناقض با دستیابی به دیگر الزامات طراحی است، استفاده از رویکردهای چندهدفه در مراحل مختلف طراحی دستگاه‌های نهفته ازجمله زمان‌بندی وظایف امری اجتنابناپذیر به نظر میرسد. در اين مقاله، یک روش زمان‌بندی وظیفه ایستای چندهدفه برای طراحی دستگاه‌های نهفته ارائه‌شده است. در این روش، وظایف به‌صورت یک گراف مدل شده و با در نظر گرفتن یک زیرساخت سخت‌افزاری برای سیستم نهفته، روشی برای نگاشت و زمان‌بندی وظایف بر روی معماری سخت‌افزاری پیشنهاد می‌شود. به‌منظور مدیریت وابستگی بین وظیفهها در گراف وظایف، از یک روش بخشبندی استفاده‌شده است که در هر بخش، وظایفی که می‌توانند به‌طور هم‌زمان اجرا شوند مشخص‌شده و در فرآیند زمان‌بندی در نظر گرفته میشوند. در این روش زمان‌بندی، پارامترهای زمان اجرای وظایف، انرژی مصرفی و قابلیت اطمینان به‌عنوان اهداف بهینه‌سازی طی یک الگوریتم بهینه‌سازی ژنتیک بهینه می‌گردند. نتایج شبیهسازیها نشان می‌دهد که روش پیشنهادی با در نظر گرفتن اهداف مختلف طراحی در مقایسه با روشهای مشابه پیشین مانند EAG-TA، در زمان اجرای وظایف، انرژی مصرفی و قابلیت اطمینان به ترتیب 21.4، 19.2 و 20 درصد بهبود داشته است. استفاده از یک راهبرد بهینه‌سازی چندهدفه این امکان را فراهم می‌کند که طی مرحله نگاشت و زمان‌بندی، گزینه‌های متعدد طراحی پیش روی طراح قرار گیرد تا بتواند بین پارامترهای مختلف طراحی سیستم (سخت‌افزاری/نرم‌افزاری) موازنه مدنظر خود را انجام دهد.
Embedded system designers face numerous design requirements and objectives (such as runtime, power consumption and reliability). Since meeting one of these requirements mostly contradicts other design requirements, it seem to be inevitable to apply multi-objective approaches in various stages of designing embedded systems, including task scheduling step. In this paper, a multi-objective task mapping and scheduling in the design stage of the embedded system is presented. In this method, tasks are represented by task graphs assuming that the hardware architecture platform is given and determined. In order to manage the dependencies between tasks in the task graph, a segmentation method is used, in which the tasks that can be executed simultaneously are specified in a segment and is considered in the scheduling process. In the proposed method, the task mapping and scheduling problem is modeled as a genetic algorithm-based multi-objective optimization problem considering execution time, energy consumption, and reliability. In comparison to similar previous works, the proposed scheduling method respectively provides 21.4%, 19.2%, and 20% improvement in execution time, energy consumption, and reliability. Applying a multi-objective helps the designer to pick out the best outcome according to different considerations.
Salimi, Maghsood, et al. "Multi-objective Optimization of Real-Time Task Scheduling Problem for Distributed Environments." Proceedings of the 6th Conference on the Engineering of Computer Based Systems. ACM, 2019.
J. Balcarek, P. Fiser, and J. Schmidt, “Test patterns compression technique based on a dedicated SAT-based ATPG,” In Digital System Design: Architectures, Methods and Tools (DSD) 13th Euromicro Conference, pp. 805-808, 2009
Majd, Amin, et al. "NOMeS: Near-optimal metaheuristic scheduling for MPSoCs." 2017 19th International Symposium on Computer Architecture and Digital Systems (CADS). IEEE, 2017.
A. Czutro, I. Polian, M. Lewis, P. Engelke, S. Reddy and B. Becker, “Thread parallel integrated test pattern generator utilizing satisfiability analysis,” Int J Parallel Progr, pp. 185-202, 2012.
H. Marijn , M. Järvisalo and A. Biere, “Efficient CNF simplification based on binary implication graphs,” International Conference on Theory and Applications of Satisfiability Testing, pp. 201-215, 2011.
P. Jackson and D. Sheridan, “Clause form conversions for boolean circuits,” International Conference on Theory and Applications of Satisfiability Testing, Berlin Heidelberg, 2004.
Salimi, Maghsood, et al. "Multi-objective Optimization of Real-Time Task Scheduling Problem for Distributed Environments." Proceedings of the 6th Conference on the Engineering of Computer Based Systems. ACM, 2019.
Majd, Amin, et al. "NOMeS: Near-optimal metaheuristic scheduling for MPSoCs." 2017 19th International Symposium on Computer Architecture and Digital Systems (CADS). IEEE, 2017.
Topcuoglu, S. Hariri and Min-You Wu, "Performance-effective and low-complexity task scheduling for heterogeneous computing", IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 3, pp. 260-274, 2002.
G. Tseitin, On the complexity of derivation in propositional calculus, Berlin Heidelberg: Springer , 1983.
L. T, “Test pattern generation using boolean satisfiability,” IEEE Transactions on Computer-Aided Design, pp. 4-15, 1992.
Z. Wang and T. Fang, "Task Scheduling Model Based on Multi-Agent and Multi-Objective Static Scheduling Algorithm", Journal of Networks, vol. 9, no. 6, 2014. Available: 10.4304/jnw.9.6.1588-1595
L. Zhou, "Integrated Multi-objective Scheduling for Multi-task on Perishable Products", Journal of Information and Computational Science, vol. 12, no. 18, pp. 6653-6664, 2015.
M. Davis and H. Putnam, “A computing procedure for quantification theory,” Journal of the ACM (JACM), Vol. 7, No. 3, pp. 201-215, 1960.
S. Eggersglüß and R. Drechsler, High Quality Test Pattern Generation and Boolean Satisfiability, Berlin: Springer Science & Business Media, 2012.
Akbari, M., Rashidi, H. and Alizadeh, S. (2017). An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems. Engineering Applications of Artificial Intelligence, 61, pp.35-46.
P. Beame, H. Kautz and A. Sabharwal, “Towards understanding and harnessing the potential of clause learning,” Journal of Artificial Intelligence Research, Vol. 22, N0. 1, pp. 319-351, 2004.
W. Lin and X. Jin, "Toward The Flexible Operation Of Integrated Community Energy System: A Two-Stage Multi-Objective Scheduling Method", Science Trends, 2018.
J. Sanders and E. Kandrot, CUDA by example: an introduction to general-purpose GPU programming, Addison-Wesley Professional, 2010.
S. AlEbrahim and I. Ahmad, "Task scheduling for heterogeneous computing systems", The Journal of Supercomputing, vol. 73, no. 6, pp. 2313-2338, 2016. Available: 10.1007/s11227-016-1917-2.
S. Parikh, S. Shah, N. M Patel, "Multi-objective Prediction based Task Scheduling Method in Cloud Computing", International Journal of Recent Technology and Engineering, vol. 8, no. 4, pp. 9388-9394, 2019. Available: 10.35940/ijrte.d9702.118419.
M. Bushnell, V. Agrawal, Essentials of electronic testing for digital,memory and mixed-signal VLSI circuits, Boston, USA: Kluwer, 2000.
K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, “A fast and elitist multiojective genetic algorithm: NSGA-II,”IEEE Trans. On Evolutionary Computation, 2002.
M. C. Hansen, H. Yalcin and J. P. Hayes,“Unveiling the ISCAS-85 benchmarks: A case study in reverse engineering,” IEEE Design & Test , Vol. 16, No. 3, pp. 72-80, 1999.
G. E. Moore, “Cramming more components onto integrated circuits," IEEE Solid-State Circuits Newsletter, 1996.
I. Meedeniya, A. Aleti, and L. Grunske, “Architecture-driven reliability optimization with uncertain model parameters”, J.of Systems and Software, 2012.
