Manuscript ID : A-10-2431-2 Visit : 6669 Page: 186 - 197

Article Type: Original Research

A Task Mapping and Scheduling Algorithm based on Genetic Algorithm for Embedded System Design

Subject Areas :

1 - University student
2 - Shiraz University

Received: 2020-11-18 Accepted : 2021-03-10 Published : 2021-09-04

Keywords: Embedded Systems, Task Scheduling, Multi-Objective optimization, Genetic Algorithm,

Abstract :

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.

References:

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, “Efﬁcient CNF simpliﬁcation 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.

Full-Text:

الگوي تهيه مقالات

دو فصلنامه علمي

فناوري اطلاعات و ارتباطات ایران

سال سیزدهم، شماره‌هاي 47 و 48، بهار و تابستان 1400

صص: 186_197

$E:\E Drive\logo\iicta Logo0.JPG$

یک الگوریتم زمان‌بندی وظیفه چندهدفه بر اساس الگوریتم ژنتیک برای طراحی سیستم‌های نهفته

محدثه نیک سرشت* محسن راجی**

* کارشناسی ارشد، دانشکده مهندسی برق و کامپیوتر، دانشگاه شیراز

**عضو هیئت علمی، دانشکده برق و کامپیوتر، دانشگاه شیراز

تاریخ دریافت: 23/08/1399 تاریخ پذیرش: 20/12/1399

نوع مقاله: پژوهشی

چکیده

طراحان سیستم‏های نهفته با الزامات و اهداف متعددی در طراحی (مانند زمان اجرا، انرژی مصرفی و قابلیت اطمینان) مواجه هستند. ازآنجاکه در بیشتر مواقع، تلاش برای برآوردن یکی از این الزامات در تناقض با دستیابی به دیگر الزامات طراحی است، استفاده از رویکردهای چندهدفه در مراحل مختلف طراحی دستگاه‌های نهفته ازجمله زمان‌بندی وظایف امری اجتناب‏ناپذیر به نظر می‏رسد. در اين مقاله، یک روش زمان‌بندی وظیفه ایستای چندهدفه برای طراحی دستگاه‌های نهفته ارائه‌شده است. در این روش، وظایف به‌صورت یک گراف مدل شده و با در نظر گرفتن یک زیرساخت سخت‌افزاری برای سیستم نهفته، روشی برای نگاشت و زمان‌بندی وظایف بر روی معماری سخت‏افزاری پیشنهاد می‌شود. در این روش زمان‌بندی، پارامترهای زمان اجرای وظایف، انرژی مصرفی و قابلیت اطمینان به‌عنوان اهداف بهینه‏سازی طی یک الگوریتم بهینه‌سازی ژنتیک بهینه می‌گردند. نتایج شبیه‏سازی‏ها نشان می‌دهد که روش پیشنهادی با در نظر گرفتن اهداف مختلف طراحی در مقایسه با روش‏های مشابه پیشین مانند EAG-TA، در زمان اجرای وظایف، انرژی مصرفی و قابلیت اطمینان به ترتیب 21.4، 19.2 و 20 درصد بهبود داشته است. استفاده از یک راهبرد بهینه‌سازی چندهدفه این امکان را فراهم می‌کند که طی مرحله نگاشت و زمان‌بندی، گزینه‌های متعدد طراحی پیش روی طراح قرار گیرد تا بتواند بین پارامترهای مختلف طراحی سیستم (سخت‌افزاری/نرم‌افزاری) موازنه مدنظر خود را انجام دهد.

واژه‌های کلیدی: سیستم‌های نهفته، زمان‌بندی وظیفه، بهینه‌سازی چندهدفه، الگوریتم ژنتیک.

1 مقدمه

سیستم‌های نهفته یا سیستم‌های تعبیه‌شده به‌طور گسترده‌ای در خدمات و محصولات صنعتی ، نظامی و تجاری استفاده می‌شود [1]. این زمینه‌های مختلف کاربرد، منجر به ناهمگنی بیشتر و پیچیدگی روزافزون در سیستم‌های نهفته امروزی شده است و طراحی این سیستم‌ها را به یک چالش مهم مهندسی تبدیل کرده است [2].

نویسنده مسئول: محسن راجی، mraji@shirazu.ac.ir

یکی از بخش‌های اصلی این چالش شامل مسئله نگاشت و زمان‌بندی کارها در طراحی سیستم‌های نهفته می‌باشد [2]. در یک مسئله نگاشت و زمان‌بندی، فرآیند کاری که بر عهده سیستم نهفته است به‌صورت یکسری وظایف نرم‌افزاری مدل شده و بایستی با توجه به زیرساخت سخت‌افزاری موجود، ترتیب اجرای هرکدام از وظایف روی اجزای زیرساخت سخت‌افزاری تعیین گردد. با توجه به محدودیت‌های متعددی که سیستم‌های نهفته با آن روبه‌رو هستند، از قبیل زمان اجرای وظایف، توان مصرفی و صحت عملکرد آن‌ها (قابلیت اطمینان)، مسئله زمان‌بندی بایستی با در نظر گرفتن هم‌زمان این پارامترها در قالب یک مسئله بهینه‌سازی چندهدفه حل شود‎ [3]-[6]. به ‌این ‌ترتیب، این امکان برای طراح سیستمی فراهم می‌شود که طی مرحله نگاشت و زمان‌بندی، بتواند از بین گزینه‌های متعدد طراحی و بین پارامترهای مختلف طراحی سیستم (سخت‌افزاری/نرم‌افزاری) موازنه مدنظر خود را انجام دهد.

مسئله زمان‌بندی وظایف یک مسئله NP-سخت است که در [7] بررسی‌شده است، به این معنی که با افزایش ابعاد مسئله، رسیدن به بهترین جواب مسئله در یک‌زمان معقول امکان‌پذیر نیست. به همین دلیل، از الگوریتم‌های اکتشافی و فرا اکتشافی برای رسیدن به جواب‌هایی که تا حد ممکن به بهترین جواب‌ها نزدیک باشند، استفاده می‌شود. یکی از روش‌های محبوب فرا اکتشافی که قابلیت حل مسائل بهینه‏سازی چندهدفه را نیز دارد، الگوریتم ژنتیک است. این الگوریتم، به دلیل کارآمد بودن و درعین‌حال، سادگی پیاده‌سازی به‌طور گسترده‌ای برای حل مسائل بهینه‌سازی مختلف مورداستفاده قرارگرفته است که در ‎[8] بررسی‌شده است. الگوریتم ژنتیک با الهام از سیر تکامل انسان‏ها، قادر است پس از مدل شدن مسئله به‌صورت کروموزم¹ ها، با اعمال عملگرهای ژنتیکی بر روی آن‌ها، به حل مسئله بهینه‌سازی نائل گردد که در [9] بررسی‌شده است. نیاز به تأکید است که ابزار ما در مرحله طراحی سیستم‌های نهفته کار می‌کند. در این سطح هیچ سیستم‌عاملی وجود ندارد، فقط مجموعه‌ای از وظایف مورد انتظار و بستر سخت‌افزاری موجود است. این امر به طراح کمک می‌کند تا بفهمد مجموعه‌ای از کارها را می‌توان بر روی سخت‌افزار موردتقاضا در شاخص‌های موردنظر زمان‌بندی کرد یا خیر و در صورت لزوم تغییراتی را در بستر سخت‌افزاری یا مجموعه وظایف ایجاد کند. ابزارهای ارزیابی در مرحله اول طراحی با تجزیه‌وتحلیل دقیق سیستم، طراحان را قادر می‌سازد گزینه‌های مختلف طراحی را بررسی و بر اساس شاخص‌های طراحی انتخاب کنند. تصمیمات طراحی که در مراحل اولیه فرآیند طراحی گرفته می‌شوند برای جلوگیری از تغییرات بالقوه پرهزینه در مراحل پیشرفته‌تر فرآیند بسیار مهم هستند. درنتیجه، طراح باید در مراحل اولیه طراحی، تجزیه‌وتحلیل و ارزیابی لازم را انجام دهد تا اطمینان حاصل کند که سیستم تعبیه‌شده حاصل عملکرد مطلوبی را در مورد پارامترهای طراحی موردنظر برآورده می‌کند.

2 کارهای پیشین

کارهای متعددی از الگوریتم ژنتیک به‌منظور حل مسئله نگاشت و زمان‌بندی وظایف در حین طراحی سخت‌افزاری/نرم‌افزاری سیستم‌های نهفته بهره برده‌اند. می‌توان این روش‌های متعدد را بر اساس نوع گراف ورودی سیستم به دو دسته ایستا و پویا تقسیم کرد. در نوع استاتیک گراف ورودی در لحظه ورود دریافت می‌شود و زمان‌بندی بر روی آن انجام می‌شود. درحالی‌که در حالت پویا گراف ورودی در زمان اجرا امکان دارد تغییر کند یا در هرلحظه وظیفه‌ای جدید به سیستم داده شود. کارهای ارائه‌شده در [10] و [11] بر روی گراف‌های ورودی پویا تمرکز کرده است. اما تمرکز این مقاله بر روی گراف‌های ورودی ایستا می‌باشد.

زمان‌بندی وظایف از نوع استاتیک خود به دو زیرشاخه اکتشافی و فراکتشافی تقسیم می‌شوند. از طرفی الگوریتم‌های اکتشافی شامل سه زیرشاخه‌ لیست محور، خوشه‌ای و تکثیری هستند [12].

در الگوریتم‌های لیست محور، به هر یک از وظایف لیست اولویتی داده می‌شود و وظایف بر اساس تقدم اولویت شروع به اجرا می‌کنند. به‌طورکلی وظیفه‌ای با اولویت بالاتر سریع‌تر به یک پردازنده منصوب می‌شود. برای مثال در سیستم‌های ناهمگن وظیفه‌ای با اولویت بالاتر به پردازشگر قدرتمندتر تخصیص داده می‌شود تا زمان اجرا آن به حداقل برسد. الگوریتم‌های HEFT و CPOP [12]از مهم‌ترین نمونه‌های الگوریتم‌های لیست محور می‌باشند. در روش‌های تکثیری و خوشه‌ای با سپردن متعدد و مکرر وظایف به پردازنده‌های متفاوت زمان اجرا به حداقل رسانده می‌شود. در این روش‌ها با اجرای وظایف تکراری بر روی بیش از یک پردازنده و جلوگیری از انتقال نتیجه از یک پردازنده به پردازنده دیگر سربار زمانی ارتباط بین پردازنده‌ها را کاهش می‌دهیم. در سیستم‌های موازی و مجزا این روش راه‌حل مناسبی است تا تأخیر ارتباطی گراف را به حداقل برسانیم، زیرا وظایفی که با یکدیگر ارتباط زیادی دارند در یک دسته قرار می‌گیرند و به یک پردازنده محول می‌شوند. به‌طورکلی الگوریتم‌های اکتشافی قادر نیستند برای طیف وسیعی از مسائل به جواب پایدار دست یابند به‌خصوص زمانی که پیچیدگی‌های مربوط به زمان‌بندی وظایف افزایش پیدا می‌کند. از طرف دیگر، الگوریتم‌های اکتشافی هزینه بالای محاسباتی دارند و نسبت به الگوریتم‌های فرا اکتشافی دارای کارایی کمتری می‌باشند.

الگوریتم‌های فرا اکتشافی معمولاً به یک‌راه حل کلی برای حل مسائل بهینه‌سازی دست پیدا می‌کنند. زمانی که یک الگوریتم اکتشافی می‌باشد یعنی کاملاً بر اساس آزمون‌ و خطا پیاده‌سازی شده است اما الگوریتم‌های فراشناختی می‌توانند بر اساس استراتژی‌های پایدار پیاده شوند که الگوریتم‌های اکتشافی را به سمت اکتشافات هدایت‌شده تغییر می‌دهند. به‌این‌ترتیب می‌توانند به نوآوری‌هایی تازه دست یابند. در حل مسائل ما به دنبال جواب می‌باشیم که برای تمام زیرمجموعه‌های مسئله بهینه باشد و نه‌تنها برای یک زیرمجموعه خاص از کل فضای جست‌وجو، از طرفی پیدا کردن پاسخ بهینه سراسری در اکثر مسائل حقیقی بسیار سخت می‌باشد و درنتیجه رسیدن به پاسخ‌های به‌اندازه مناسب رضایت‌بخش قابل‌قبول است. از الگوریتم‌های فراشناختی برای دست‌یابی به این دسته از پاسخ‌ها استفاده می‌شود. الگوریتم‌های فرا اکتشافی بر اساس سه معیار سادگی، قابلیت انعطاف و گستردگی جستجو در فضای حل مسئله استوار می‌باشند. اکثر الگوریتم‌های فرا اکتشافی ساده و به‌راحتی قابل پیاده‌سازی می‌باشند و پیچیدگی کمی دارند، این الگوریتم‌ها انعطاف‌پذیر بوده و به‌راحتی می‌تواند طیف وسیعی از مسائل بهینه‌سازی را حل کنند حتی مسائلی که با استفاده از الگوریتم‌های سنتی قابل پوشش دادن نیست.

درزمینه گراف‌های ورودی ایستا اولین بار در [13]، یک الگوریتم ژنتیک چندهدفه برای ترکیب سخت‌افزاری/نرم‏افزاری سیستم‌های نهفته توزیع‌شده ارائه‌شده است. در این کار، تنها پارامترهای توان مصرفی و زمان اجرای وظایف در نظر گرفته شده است. همچنین وابستگی وظایف در گراف وظایف در نظر گرفته نشده است. در ‎[14]، [15] و [16] رویکردی برای نگاشت و زمان‌بندی سیستم نهفته مبتنی بر الگوریتم ژنتیک ارائه‌شده است. در این کار نیز پارامتر قابلیت اطمینان لحاظ نشده است. در ‎[17]، چارچوبی یکپارچه برای ترکیب سیستم‌های نهفته در سطح سیستمی ارائه‌شده است. در این چارچوب، ضمن استفاده از الگوریتم ژنتیک به بهینه‌سازی چندهدفه پارامترهای نگاشت پذیری و ویژگی‌های مختلف معماری می‌پردازد. هدف این کار مشخصاً ارائه یک بن سازه یکپارچه برای ترکیب سطح سیستمی بوده و به جستجوی فضای طراحی با توجه به پارامترهایی مانند توان مصرفی و قابلیت اطمینان نپرداخته است. همچنین در ‎[18]، [19] و [20] که نسخه‌ای تکمیل‌شده از کار [17] می‌باشد، از الگوریتم ژنتیک برای بهینه‌سازی زمان اجرای وظایف در حین زمان‌بندی برای سیستم‌های نهفته استفاده ‌شده است. از نقطه‌ضعف‌های کارهای فوق می‌توان به نادیده گرفتن دیگر پارامترهای مهم سیستم‌های نهفته ازجمله توان مصرفی و قابلیت اطمینان اشاره کرد. در [21] ، برای اولین بار با رویکرد جست جو در فضای طراحی و ارائه مجموعه جواب‌ها برای طرح با الهام گرفتن از کارهای پیشین قابلیت اطمینان در نظر گرفته‌شده است. اما از نکات منفی این روش می‌توان به نادیده گرفته شدن انرژی مصرفی و زمان اجرا اشاره کرد. همچنین شبیه‌سازی قابلیت اطمینان با فرمول‌های بسیار پیچیده انجام‌شده است که قدرت محاسبات را به‌شدت کاهش می‌دهد و علاوه بر این تنها به مسئله قابلیت اطمینان مختص به پارامتر سالخوردگی در ترانزیستورها پرداخته‌شده است. در کارهای اخیر صورت گرفته در این حوزه در سطح طراحی مقاله‌هایی مانند [22] ، [23] و [24] وجود دارند که یک محیط مدل‌سازی و شبیه‌سازی را برای کاوش فضای طراحی سیستم‌های نهفته ناهمگن ایجاد کرده‌اند. بااین‌حال، این کارها بر روی مسئله نگاشت متمرکز بوده و از پرداختن به مشکل زمان‌بندی چشم‌پوشی کرده‌اند جمع‌بندی موارد گفته‌شده را می‌توانید در جدول 1 مشاهده کنید.

به‌طور خلاصه کارهای پیشین دارای محدودیت‌های جدی‏ای هستند؛ ازجمله این‌که پارامترهای زمان اجرای وظایف، توان/انرژی مصرفی و قابلیت اطمینان به‌صورت هم‌زمان در حین حل مسئله نگاشت و زمان‌بندی وظایف در سیستم‌های نهفته در نظر گرفته نشده‌اند و یا این‌که تنها به مسئله نگاشت وظایف پرداخته‌شده است.

جدول 1 . جمع‌بندی از کارهای پیشین

نقاط ضعف	نقاط مثبت	مرجع مربوط به الگوریتم
فرمول‌های شبیه‌سازی بسیار ساده، عدم پشتیبانی از گراف های ورودی پیچیده و دارای وابستگی، عدم در نظر گرفتن قابلیت اطمینان	در نظر گرفتن انرژی مصرفی و زمان اجرا	[13], [14], [15], [16]
عدم در نظر گرفتن دو پارامتر مهم قابلیت اطمینان و انرژی مصرفی	ترکیب نگاشت سخت‌افزاری با گراف وظایف ورودی سیستم، جست‌وجوی فضای طراحی برای اولین بار و قرار دادن نتایج مختلف شبیه‌سازی در اختیار طراح	[17], [18], [19], [20]
غفلت از سایر پارامترهای مهم طراحی مانند انرژی مصرفی و زمان اجرا، محدود بودن مدلسازی قابلیت اطمینان به سالخوردگی ترانزیستورها	مدلسازی قابلیت اطمینان در مسئله زمانبندی سیستم های نهفته برای اولین بار	[21]
محدود بودن به مسئله نگاشت وظایف و عدم پرداختن به مسئله زمان‌بندی وظایف	در نظر گرفتن هر سه پارامتر مهم انرژی مصرفی، قابلیت اطمینان و زمان اجرا در سطح طراحی و حل مسئله نگاشت وظایف بر روی سخت افزار	[22], [23], [24]

در اين مقاله، یک روش زمان‌بندی وظیفه ایستای چندهدفه مبتنی بر الگوریتم ژنتیک برای طراحی سیستم‏های نهفته ارائه‌شده است. در این روش، وظایف به‌صورت یک گراف وظیفه مدل شده و با توجه به معماری سخت‌افزاری موجود، روشی برای نگاشت و زمان‌بندی وظایف بر روی معماری سخت‌افزاری پیشنهاد می‌شود. به این منظور، فرآیند نگاشت و زمان‌بندی به‌صورت کروموزوم‌هایی مدل شده و هر کروموزوم با استفاده از تابع ارزیابی‌های مختلف برای پارامترهای زمان اجرای وظایف، توان مصرفی و قابلیت اطمینان ارزیابی می‌شوند. برای یک بهینه‌سازی چندهدفه، از انتخاب راه‌حل‌های پارتو استفاده‌شده و هر بار با توجه به نتایج ارزیابی پارامترهای سه‌گانه جمعیت جدید (زمان‌بندی‌های جدید) انتخاب می‌شوند. نتایج شبیه‏سازی‏ها نشان می‌دهد که روش پیشنهادی با در نظر گرفتن اهداف مختلف طراحی در مقایسه با روش‏های مشابه پیشین مانند EAG-TA، در زمان اجرای وظایف، انرژی مصرفی و قابلیت اطمینان به ترتیب21.4، 19.4 و20 درصد بهبود داشته است. استفاده از یک راهبرد بهینه‌سازی چندهدفه این امکان را فراهم می‌کند که طی مرحله نگاشت و زمان‌بندی، گزینه‌های متعدد طراحی پیش روی طراح قرار گیرد تا بتواند بین پارامترهای مختلف طراحی سیستم (سخت‌افزاری/نرم‌افزاری) موازنه مدنظر خود را انجام دهد.

به‌طور خلاصه، نوآوری‌های مقاله به شرح زیر است:

1. مدل‌سازی مسئله زمان‌بندی وظایف در سیستم‌های نهفته به‌صورت یک مسئله بهینه‏سازی چندهدفه در قالب الگوریتم ژنتیک

الف) توسعه نحوه نمایش کروموزوم‌ها برای حل مسئله زمان‌بندی

ب) توسعه عملگرهای ژنتیکی برای نحوه نمایش جدید کروموزوم‌ها

2. لحاظ قابلیت اطمینان علاوه بر پارامترهای زمان اجرا، توان مصرفی به‌طور هم‌زمان در حل مسئله زمان‌بندی وظیفه سیستم‏های نهفته.

ادامه مقاله به این صورت زیر سازمان‌دهی شده‌اند: بخش 3 به متدلوژی پیشنهادی طراحی می‌پردازد. طی این بخش، مدل استفاده‌شده برای وظایف و معماری سخت‌افزاری مدنظر بررسی می‌شود. همچنین الگوریتم ژنتیک توسعه داده‌شده برای حل مسئله نگاشت و زمان‌بندی وظایف در سیستم‌های نهفته ارائه می‌شود. در بخش 4 نتایج تجربی ارائه می‌شود و درنهایت، مقاله در بخش 5 جمع‌بندی می‌شود.

3 روش پیشنهادی طراحی چندهدفه مبتنی بر الگوریتم ژنتیک

در این قسمت به نحوه طراحی چندهدفه طراحی مبتنی بر الگوریتم‌های ژنتیک پرداخته شده است. در قسمت اول مدل‌سازی وظایف و معماری سخت‌افزاری ارائه‌شده و در قسمت دوم، به رویه جست‌وجوی فضای طراحی با استفاده از الگوریتم‌های ژنتیک می‌پردازیم.

3.1 مدل‏سازی وظایف و معماری سخت‌افزاری

برای مدل کردن وظایف، از مدل معرفی‌شده در [17]مبتنی بر شبکه فرآیند کاهن (KPN) استفاده می‌شود که یک مدل بسیار مشهور محاسباتی برای مدل کردن سیستم‌های نهفته است. KPN روشی برای نمایش وظیفه است که در آن، وظایف به‌صورت گراف جهت‌دار نشان داده می‌شود. KPN را به شکل گراف نشان می‌دهند که در آن برای هر رأس i یک وظیفه یا پردازه² از گراف را نشان می‏دهد برای هر رأس مجموعه وظایفی که به یکدیگر مرتبط می‌باشند به شکل نشان داده می‌شود. زمانی که رأس برای اجرا به یک مؤلفه سخت‏افزاری تخصیص داده می‏شود، نشان‌دهنده مدت‌زمان اجرا بر روی این سخت‌افزار می‌باشد.

زمانی که وظیفه‌ای امکان اجرا بر روی هسته‌های³ متعددی را داشته باشد. زمان اجرای آن به‌صورت مجموعه نشان داده می شود که نشان دهنده تعداد سخت‌افزاری است که وظایف ‌روی آن ها اجرا می شود.

زمانی که رأس به یک مؤلفه نرم‌افزاری برای زمان‌بندی تخصیص داده می‌شود، نشان‌دهنده زمان اجرا بر روی آن مؤلفه نرم‌افزاری می‌باشد. زمانی که آن وظیفه بر روی مؤلفه‌های نرم‌افزاری متعدد قابلیت اجرا داشته باشد، زمان اجرای آن به‌صورت مجموعه نشان داده می‌شود که نشان‌دهنده تعداد مؤلفه‌های نرم‌افزاری می‌باشد که این وظیفه می‌تواند بر روی آن اجرا شود.

هر یال ،{1, …, ||} j نشان‌دهنده رابطه بین دو وظیفه از گراف می‌باشد. اگر این مسیر ارتباطی به یک حافظه تخصیص داده شود، نشان‌دهنده زمان دسترسی به حامی می‌باشد. اگر در زمان‌بندی بتوان آن را به حافظه‌های متعددی تخصیص داد، زمان دسترسی به شکل مجموعه نشان داده می‌شود. این مجموعه نشان‌دهنده مجموعه وظیفه‌ای است که می‌توان آن‌ها را در زمان‌بندی تخصیص داد.

شکل 1 . مسئله نگاشت و زمان‌بندی در طراحی سیستم‌های نهفته

همچنین مدل معماری به‌صورت گراف نشان داده می‌شود که در آن و به ترتیب نشان‌دهنده مؤلفه‌های معماری و مسیر ارتباطی بین آن می‌باشد. مجموعه مؤلفه‌های معماری شامل دو مجموعه مستقل یعنی مجموعه پردازشگرها ( (Pکه شامل مجموعه مؤلفه‌های سخت‌افزاری، نرم‌افزاری و همچنین مجموعه حافظه‌ها می‌باشد، . تأخیر بین مسیرهای ارتباطی به‌صورت نشان داده‌شده است که در آن p,q {1,…,||} توان مصرفی در طول اجرا برای پردازنده p به شکل و برای حافظه mو مسیر ارتباطی در نظر گرفته‌شده است. در این مقاله، فرض بر این است که بن سازه معماری موجود و مشخص است چراکه هدف اصلی، حل مسئله تعیین بهترین معماری نیست بلکه روش پیشنهادی برای حل مسئله نگاشت زمان‌بندی در طراحی سیستم‌های نهفته است.

مسئله نگاشت و زمان‌بندی، مسئله یافتن بهترین تخصیص وظایف و ارتباطات بین آن‌ها بر روی یک بن سازه معماری سخت‌افزاری است. نمونه‏‏ای از نگاشت و زمان‌بندی وظایف بر بن سازه سخت‌افزاری در شکل (1) آورده شده است. همان‌طور که در شکل مشاهده می‌شود، هر رأس یا یال از گراف که به ترتیب نماینده یک وظیفه یا ارتباط بین دو وظیفه است برای اجرا بر روی یک پردازشگر از بن سازه معماری سخت‌افزاری به آن تخصیص داده‌شده و ضمن لحاظ زمان اجرا وظیفه یا ارتباط مربوطه و همچنین ترتیب اجرای وظایف با توجه به گراف وظایف، زمان‌بندی اجرای آن‌ها نیز مشخص می‌گردد. در این مقاله برای نزدیک شدن به بهترین نگاشت و زمان‌بندی با توجه به اهداف مهم سیستم‌های نهفته اعم از بهترین زمان اجرا، توان مصرفی، قابلیت اطمینان از حل یک الگوریتم بهینه‌سازی چندهدفه مبتنی بر الگوریتم ژنتیک پیشنهاد می‌شود.

3.2 جستجوی فضای طراحی با استفاده از الگوریتم ژنتیک

به‌منظور جستجوی فضای طراحی برای یافتن بهترین نگاشت و زمان‌بندی وظایف از الگوریتم ژنتیک استفاده می‌شود. به علت پیچیدگی‌ها و محدودیت‌هایی که در طراحی سیستم‌های نهفته وجود دارد جستجوی فضای طراحی یک فرآیند چالش‌برانگیز است چراکه این کار، یک مسئله بهینه‌سازی چندهدفه است که این اهداف معمولاً در تضاد با یکدیگر می‌باشند. در ادامه، نحوه مدل‏سازی مسئله زمان‌بندی به کمک الگوریتم ژنتیک ارائه خواهد شد.

3.2.1 ساختار کروموزوم‌ها

نگاشت و زمان‌بندی وظایف بر روی پردازنده‌ها و لبه‌های ارتباطی در هر کروموزوم کدگذاری می‌شود. فرض کنید یک گراف وظایف (G) با مجموعه وظایف (N) و گره‌های ارتباطی M)) و معماری سیستم با (P) پردازنده داشته باشیم، در این شرایط هر کروموزوم با مجموعه ژن‌های 2M + N توصیف می‌شود. ساختار یک کروموزوم در شکل (2) نشان داده‌شده است. هر کروموزوم از دو بخش اصلی تشکیل‌شده است:

شکل 2 . نمایش کروموزوم‌ها

نگاشت: در این بخش، پردازنده منتخب برای اجرا بر روی هر وظیفه مشخص می‌شود. در شکل (2)، N ژن اول نشان داده‌شده مربوط به نگاشت N وظیفه بر روی P پردازنده موجود است. برای مثال، وظیفه B بر روی FPGA 4 نگاشت شده است. ترتیب پر شدن پردازنده‌ها بر روی وظایف بر اساس اولویت وظایف در بخش‌بندی است.

زمان‌بندی: N + M ژن باقیمانده برای زمان‌بندی در نظر گرفته‌شده است. در قسمت اول(N ژن) ترتیب اجرای کارها بر روی پردازنده‌های منتخب‌شده را نشان می‌دهد. قسمت دوم(M ژن) ترتیب انجام انتقال داده از روی مسیرهای ارتباطی را نشان می‌دهد. در قسمت اول، وظایف را بر اساس ترتیب اختصاص داده‌شده درروش بخش‌بندی قرار می‌دهیم(حالت اولیه) و سپس به شکل تصادفی ترتیب قرارگیری وظایف هر بخش را تغییر می‌دهیم.

3.2.2 عملگرهای ژنتیک

در الگوریتم ژنتیک از عملگرهای ژنتیک برای تولید و حفظ تنوع کروموزوم‌ها از یک نسل به نسل دیگر جمعیت استفاده می‌شود. در این مقاله از دو عملگر اصلی ژنتیک، جهش، حفظ تنوع بین اعضا کروموزوم‌های هر جمعیت، و تقاطع، کمک به همگرایی جمعیت به سمت پاسخ‌های بهتر، استفاده می‌شود. در ادامه، به بررسی دقیق این عملگرهای ژنتیک که در ابزار شبیه‌سازی پیشنهادی استفاده‌شده‌اند، می‌پردازیم.

عملگر برش⁴: یکی از عملگرهای ژنتیک است، از این عملگر جهت ترکیب اطلاعات دو والدین⁵ و تولید فرزند جدید استفاده می‌شود. در پیاده‌سازی این الگوریتم در ابزار شبیه‌سازی پیشنهادی ابتدا یک از والدین به شکل تصادفی انتخاب می‌شوند و فن تقاطع محلی که در مقاله [18]ارائه‌شده است بر روی آن اعمال می‌شود. طبقه‌بندی بین دسته کروموزوم به این شکل است که الگوریتم NSGAII [26] بر روی جمعیت اعمال می‌شود و بر اساس غالب بودن کروموزوم‌ها، در دسته‌های مجزا تفکیک می‌شوند. پس از انتخاب شدن والد اول به شکل تصادفی، والد دوم به شکل تصادفی از دسته والد اول انتخاب می‌شود. برای مثال اگر والد اول در دسته یک قرارگرفته باشد، والد دوم نیز از دسته1 انتخاب می‌شود. پس از انتخاب شدن والدین، دو فرزند با احتمال تولید می‌شوند. شکل (3)، نشان‌دهنده عملیات برش می‌باشد.

عملگر جهش⁶: عملگر جهش یا جهش یک عملگر ژنتیک است که برای حفظ تنوع ژنتیک از یک نسل کروموزوم‌ها به نسل بعد استفاده می‌شود. این تغییرات نباید بر روی اولویت وظایف تأثیر بگذارد. در ابزار شبیه‌سازی پیشنهادی، برای پیاده‌سازی این عملگر یک والد به شکل تصادفی از جمعیت فعلی انتخاب می‌شود و دو فرزند از والد انتخاب‌شده تولید می‌شوند.. این تغییرات نباید گراف وابستگی وظایف را از بین ببرد. ازاین‌رو تغییر در کروموزوم با استفاده از بخش‌بندی صورت می‌گیرد. شکل (4) نشان‌دهنده عملیات جهش است.

شکل 3. عملیات برش.

شکل 4. عملیات جهش.

عملگر انتخاب: انتخاب جمعیت بر اساس الگوریتم NSGAII [26] است.

3.3 توابع هدف

در ابزار پیشنهادی، سه شاخص طراحی، زمان اجرا، انرژی مصرفی و قابلیت اطمینان برای رسیدن به پاسخ‌های بهینه در نظر گرفته‌شده‌اند. توابع هدف نسبت داده‌شده به هر یک از این شاخص‌های طراحی برای ارزیابی پاسخ‌های به‌دست‌آمده (زمان‌بندی‌های ارائه‌شده توسط الگوریتم) استفاده می‌شود. این مقادیر پس مشخص شدن ساختار کروموزوم‌ها و تخصیص پردازنده به وظایف محاسبه می‌شوند.

3.3.1 هدف اول: زمان اجرا

اولین تابع هدف حداقل کردن زمان اجرا یا زمان پردازش بر روی مسیر بحرانی است. این مسیر شامل مجموعه‌ای از کل مسیرهای اجرا است. با توجه به نشان‌گذاری‌هایی که پیش‌ازاین انجام‌شده است، تابع هدف مربوط به زمان اجرای وظایف پس از هر بار نگاشت و زمان‌بندی از عبارت زیر به دست می‌آید :[22]

اولین قسمت معادله نشان‌دهنده تأثیر پردازنده‌های سخت‌افزاری بر روی زمان اجرای وظایف در طولانی‌ترین توالی اجرای وظایف (که تحت عنوان مسیر بحرانی تعریف می‌شود) است. قسمت دوم معادله نشان‌دهنده تأثیر مسیرهای برنامه کاری بر روی مدل کردن زمان اجرا است. آخرین قسمت نیز نشان‌دهنده تأثیر مسیرهای ارتباطی بر روی زمان اجرا است درصورتی‌که مسیر ارتباطیj به مؤلفه معماری متصل شده باشد. در اینجا نشان‌دهنده زمان دسترسی به حافظه برای w ، از طرفی نشان‌دهنده تأخیر مسیر هسته معماری k و l و همچنین نشان‌دهنده تأخیر بین هسته معماری m و n و همچنین با m, n می باشد.

متغیرهای ، و و متغیرهای تصمیم‌گیری هستند. این متغیرها نشان می‌دهند برای مثال در هر مرحله، وظیفه iبه سخت‏افزار u و یا نرم‌افزار v ، مسیر ارتباطی درون‌هسته متصل شده است (در این صورت در نظر گرفت می‌شود) به‌صورت متغیرهای تصمیم‌گیری نشان می‌دهد هر وظیفه برای اجرا بر روی کدام‌یک از هسته‌ها تخصیص داده‌شده است. مقدار این متغیرهای تصمیم‌گیری بر روی زمان‌بندی‌های مختلف می‌تواند مختلف باشد، این مقادیر در طول جستجوی فضای حل مسئله بر اساس الگوریتم ژنتیک تولیدشده‌اند.

3.3.2 هدف دوم: توان مصرفی

دومین تابع هدف، حداقل کردن میزان توان مصرفی است که از رابطه زیر محاسبه می‌شود :[22]

(1)

در معادله بالا مدت‌زمان سپری‌شده روی هسته پردازنده برابر و مدت‌زمان سپری‌شده روی مسیر ارتباطی و زمان کل پردازش بر روی هسته می‌باشد.

3.3.3 هدف سوم: قابلیت اطمینان

سومین تابع هدف قابلیت اطمینان سیستم است، که نیاز است حداکثری باشد. برای تخمین قابلیت اطمینان به دلیل سادگی از روش‌های ارائه‌شده در [28][27] استفاده می‌شود. توجه داشته باشید که روش‌های دیگر تخمین قابلیت اطمینان نیز می‌توان استفاده کرد و انتخاب روش ارزیابی هرکدام از این پارامترهای هدف به کلیت روش پیشنهادی خدشه‏ای وارد نمی‌شود. مدل قابلیت انعطاف بر اساس روش زنجیره مارکوفی⁷ (DTMC) است. این مدل‌های گرافیکی شامل یک سری حالت محدود هستند. برای یک‌زمان بندی داده‌شده مدل DTMC از معماری سیستم گرفته‌شده است و سپس قابلیت اطمینان محاسبه می‌شود:

(2)

که در آن S ماتریس پایه DTMC بوده و S(i,j) نشان‌دهنده تعداد بارهای رفتن به حالت j از حالت پایه i هست و n تعداد حالات در مدل است. حداکثر کردن میزان قابلیت اطمینان به شکل حداقل کردن میزان عدم اطمینان نوشته می‌شود:

(3)	R = S(1,n)

(4)

min {1-R}

3.3.4 حل یک مسئله بهینه‌سازی چندهدفه

پس از مدل کردن توابع هدف، می‌توان شکل کلی معادله بهینه‌سازی چندهدفه را به شکل معادله (5) بازنویسی کرد:

در معادله ذکرشده X نشان‌دهنده یک جواب دقیق از مجموعه جواب‌های قابل‌قبول هست. در این مسئله یک پاسخ مناسب برای زمان‌بندی با انتخاب مناسب متغیرهای تصمیم‌گیری که در قسمت 1-2-2 که درباره این‌که چطور با استفاده از این متغیرهای تصمیم‌گیری وظایف به هسته‌ها تخصیص داده می‌شوند توضیح داده شد، به دست می‌آید. هر سه تابع هدف ، ، و به‌طور مشخص از معادله‌های (1)، (2) و (4) به‌دست‌آمده‌اند. تابع نهایی بهینه‌سازی یک پاسخ از مجموعه جواب x از محیط تصمیم‌گیری است که با استفاده از متغیرهای تصمیم‌گیری به یک نقطه از فضای بهینه‌سازی منتسب خواهد شد. در مثال ما فضای هدف سه‌بعدی هست و دارای وزن‌های یکسان هست که با استفاده از سه تابع از معادلات (1)، (2) و (4) به دست می‌آید.

ازآنجاکه مسئله بهینه‌سازی چند هدفه معمولاً دارای جواب یکتای بهینه نیست که بتواند تمام اهداف موردنظر را هم‌زمان بهینه کند، علاقه‏مند به پیدا کردن مجموعه جواب‌هایی هستیم که به آن‌ها راه‌حل‌های پارتو ⁸می‌گویند. پاسخ‌هایی که مجموعه راه‌حل‌های پارتو را شکل می‌دهند مجموعه پاسخ‌هایی هستند که جواب‌های دیگر فضای هدف نمی‌تواند آن‌ها را مغلوب کند. برای حل مسئله ژنتیک الگوریتم و تولید راه‌حل‌های پارتو از الگوریتم‌های تکاملی بهره می‌بریم چراکه این دسته از الگوریتم‌ها قادر هستند هم‌زمان چندین تابع هدف مستقل را بهینه کنند. به‌طور مشخص‏تر در این مقاله، از الگوریتم NSGAII [26] استفاده می‌شود چون این الگوریتم نشان داده است که در مقابل سایر الگوریتم‌های تکاملی دارای مزایای فراوان ای ازجمله راحتی پیاده‌سازی و کم بودن سربار محاسباتی این الگوریتم است [26]. شبه کد این الگوریتم در شکل (5) نشان داده‌شده است. الگوریتم ژنتیک به شکل تکراری فرزندان جدید در جمعیت تولید می‌کند با استفاده از والدین نسل قبل با استفاده از دو عامل گر برش و جهش که در الگوریتم تعبیه‌شده است. در ابتدا الگوریتم نیاز به تولید یک مجموعه جمعیت اولیه دارد؛ جمعیت اولیه، که در ابتدای کار برای سادگی آن را به شکل تصادفی تولید کرده‌ایم. روشی که برای زمان‌بندی کردن به‌کاربرده‌ایم مانند روش ارائه‌شده در [5] است. هر کروموزوم شامل مجموعه گره‌های وظیفه‌ای است که به مؤلفه‌های نرم‌افزاری، مجموعه گره‌های وظیفه‌ای که به مؤلفه‌های سخت‌افزاری و یال‌های ارتباطی است که به مؤلفه‌های حافظه تخصیص داده‌شده‌اند.

(5)	Min(x) z=f(x)= s.t. x

شکل 5. الگوریتم NSGAII

4 نتایج تجربی

روش نگاشت و زمان‌بندی پیشنهادی به زبان برنامه‌نویسی C (که در مقایسه با زبان متلب و یا سایر زبان‌ها، از سرعت‌ بالاتری برای اجرای برنامه به علت نزدیک بودن به زبان ماشین برخوردار است) انجام‌شده است. برای شبیه‏سازی از دو نمونه آزمایشی استفاده‌شده که هردوی آن‌ها در دامنه نرم‏افزارهای خودرو می‌باشند، سیستم ترمز ضد قفل⁹ ABS و سیستم کنترلی سرعت اقتباسی ACC است. سیستم کنترلی ABS و ACC در شکل 6 نشان داده شده است. گراف وظایف ABC و ACC دارای 14 گره و 33 یال است. این دو نمونه آزمایشی از مرجع [16] گرفته‌شده است. متغیرهای وابسته به الگوریتم NSGAII [18] به ترتیب زیر مقداردهی شده‌اند، احتمال برش مقدار 0.7، احتمال جهش 0.05 در نظر گرفته‌شده است. تعداد دفعات تکرار الگوریتم 9000 هزار بار با اندازه جمعیت 100 است. به دلیل آن‌که قابلیت اطمینان، توان مصرفی و زمان اجرای وظایف به‌صورت تابع اهداف چندگانه نشان داده‌شده است، تنها محدودیت‌هایی که در صورت‌بندی مسئله استفاده‌شده است شامل بن سازه سخت‌افزاری و افراز سخت‌افزاری/ نرم‌افزاری برنامه موردنظر است. به‌طور خاص در این مقاله، فرض می‌شود که بن سازه سخت‌افزاری شامل 12 قسمت است که شامل 10 پردازشگر و 2 واحد ارتباطی (حافظه و گذرگاه باس) است، فرض شده است که یال‌های ارتباطی در گراف بر اساس نگاشت حافظه پیاده‌سازی شده‌اند و به این شکل عمل می‌کند که وظیفه منبع در مؤلفه حافظه می‌نویسد و وظیفه مقصد از مؤلفه حافظه می‌خواند. در معماری فرضی ما که در شکل شماره 1 آمده است. مانند طرح پیشنهادی ارائه‌شده در [19] ما دو نوع CPU در نظر گرفته‌ایم نوع اول کم‌مصرف با توان پردازشی پایین و نوع دوم پرمصرف با توان پردازشی بالا است. برای مؤلفه سخت‌افزاری ما دو نوع FPGA متفاوت را در نظر گرفته‌ایم، نوع اول کم‌مصرف با توان مصرفی پایین و نوع دوم پرمصرف با توان مصرفی بالا است. در کل FPGA ها سریع‌تر از CPU در نظر گرفته‌شده‌اند چون با استفاده از موازات بین دستوری با سرعت ‌بالاتری دستورات را اجرا کنند. ممکن است که FPGA ها سریع‌تر از ASIC ها نباشند اما قابلیت بازپیکربندی دارند. ما زمان اجرا و نرخ وقوع خطا و میزان توان مصرفی را از گزارش‌ها ارائه‌شده در [29] اقتباس کرده‌ایم.

در جدول 2 نتیجه اجرا روش پیشنهادی و مقایسه آن با روش حریصانه بر روی‌داده آزمایشی واقعی ABS و ACC آورده شده است. شکل شماره 6 نشان‌دهنده نمودار ABS و ACC می‌باشد. الگوریتم حریصانه، همواره بهترین انتخاب در هر گام از حل مسئله انجام می‌دهد. در هر بار اجرای الگوریتم حریصانه، بر روی نمونه آزمایشی یک تابع هدف برای بهینه‌سازی انتخاب می‌شود و نتیجه نهایی به‌دست‌آمده از این الگوریتم با خروجی روش پیشنهادی مقایسه شده است، همان‌طور که در جدول 2 ملاحظه می‌شود خروجی به‌دست‌آمده توسط روش پیشنهادی به روش حریصانه غالب بوده است یا نتیجه‌ای مشابه داشته است. برای مثال در جدول 2.ج برای محاسبه میزان انرژی مصرفی به خروجی بهتری در مقایسه با الگوریتم حریصانه رسیده‌ایم این مقدار در الگوریتم حریصانه 0.1764 در مقابل مقدار 0.1563 در الگوریتم پیشنهادی می‌باشد.

شکل شماره6.الف- نمودار ABS

شکل شماره6.ب- نمودار ACC

شکل شماره 6. نشان‌دهنده نمودار ABS و ACC [21]

مهم‌ترین عامل اندازه‌گیری عملکرد سیستم بر روی الگوریتم زمان‌بندی گراف محاسبه طول گراف نتیجه از روی خروجی الگوریتم و Speedup می‌باشد که در ادامه این دو معیار را تعریف می کنیم. ازآنجایی‌که تعداد زیادی گراف با خصوصیات متفاوت استفاده‌شده‌اند، لازم است تا این گراف‌ها را به‌گونه‌ای یکسان‌سازی کنیم به کوتاه‌ترین طول ممکن در هر گراف برسیم تا بتوان نرخ مناسبی برای مقایسه آن‌ها به دست آورد، این مقدار طبق الگوریتم ارائه‌شده در[17] به‌صورت رابطه (6) است:

معیار دیگری که برای مقایسه انتخاب شده است معیار Speedup است. این متغیر از تقسیم، اجرای سریال وظایف بر روی سریع ترین وظیفه به زمان اجرای الگوریتم مورد نظر به دست می آید. معادله ی آن در زیر نشان داده شده است.

(6)

(7)

در معادلات بالا CP نشان‌دهنده مسیر بحرانی و W( نشان‌دهنده زمان اجرا کار بر روی پردازشگر می‌باشد. در زمان‌بندی به دست آمده، اگر هزینه محاسبات برای هر وظیفه به‌عنوان حداقل زمان اجرا روی پردازشگر در نظر گرفته شود به شکل نشان داده می‏شود.

جدول شماره 2.الف. مقایسه زمان اجرا روش پیشنهادی با روش حریصانه

تابع هدف	واحد	حريصانه	روش پيشنهادی
زمان اجرا	ثانیه	0.5454	0.0545
توان مصرفی	وات	0.8169	0.8087
عدم قابلیت اطمینان	خرابی در سال	0.7599	0.6581

جدول شماره 2.ب. مقایسه میزان عدم اطمینان درروش پیشنهادی با روش حریصانه

تابع هدف	واحد	حريصانه	روش پيشنهادی
زمان اجرا	ثانیه	0.2727	0.1954
توان مصرفی	وات	0.2154	0.3909
عدم قابلیت اطمینان	خرابی در سال	0.0758	0.0140

جدول شماره 2.ج. مقایسه میزان انرژی مصرفی درروش پیشنهادی با روش حریصانه

تابع هدف	واحد	حريصانه	روش پيشنهادی
زمان اجرا	ثانیه	0.2728	0.3909
توان مصرفی	وات	0.1764	0.1563
عدم قابلیت اطمینان	خرابی در سال	0.9999	0.4304

برای مقایسه عملکرد الگوریتم پیشنهادی با سایر روش‌ها چندین گراف تصادفی با استفاده از نرم‌افزار تولید گراف تصادفی تولید می‌شود. در هر گراف تصادفی تعداد گره‌ها (اندازه گراف وظایف) و تعداد یال‌های هر گره به شکل ایستا از مجموعه و گرفته می‌شود گراف به‌طور با استفاده از توزیع یکنواخت با مقدار میانگی تولید می‌شود و تعداد گره‌ها در هر سطح با توزیع یکنواخت و مقدار میانگین به شکل تصادفی تولید می‌شود در یک گراف تصادفی هزینه ارتباط برای تمام گره‌ها به شکل یکسان در نظر گرفته می‌شود مقدار SLR از نتیجه الگوریتم‏های زمانبندی مختلف برای 100 گراف تصادفی با اندازه 20 محاسبه شده است. نتایج به دست آمده از معیار SLR که در شکل (7) نشان‌ داده شده است، نسبت به SLR روش پیشنهادی نرمال شده اند. همانطور که در شکل (7) مشاهده می شود الگوریتم پیشنهادی از منظر معیار SLRنسبت به تمام الگوریتم های پیشین بهتر عمل کرده است. به عنوان مثال، MOGATS نسبت به بهینه‌ترین الگوریتم پیشین یعنی [19] EGA-TS توانسته SLR را به میزان 50 درصد بهبود بخشد؛ به این معنی که میزان پارتو های نهایی و مجموعه پاسخ‌های بهینه به دست آماده به نسبت 1.5 به 1 بهبود داشته‌اند. مشابه همین روند برای الگوریتم BGA و HEFT_T نیز قابل‌مشاهده می‌باشد تا حدی که می توان گفت MOGATS به طور میانگین در مقایسه با سه الگوریتم منتخب پیشین 58.6 درصد SLR را بهبود داده است.

نتایج به دست آمده از معیار Speedup برای الگوریتم‏های مختلف در شکل شماره 8 نشان داده شده است. شاخص Speedup مشخص می‌کند بهترین پاسخ به‌دست‌آمده توسط یک الگوریتم در هر سه شاخص انرژی مصرفی، قابلیت اطمینان و زمان اجرا نسبت به حالتی که به‌صورت متوالی که روی بهترین سخت‌افزار موجود اجرا شوند چقدر بهبود داشته است. همان‌طور که در شکل شماره 8 مشاهده می‌شود، الگوریتم MOGATS توانسته است نسبت به EGA-TS به در این شاخص نیز به بهبود چشم‌گیری دست پیدا کند و میزان Speedup را از 6 به 8 رسانده است. البته زمان اجرا MOGATS و میزان حافظه موردنیاز جهت اجرای برنامه به ترتیب درصد نسبت به EGA-TS افزایش پیداکرده است که دلیل آن این است در MOGATS چند هدف بهینه سازی وجود دارد و در نتیجه اطلاعات حجم بیشتری از حافظه را اشغال خواهند نمود.

شکل شماره 7. میزان SLR درروش پیشنهادی در مقایسه با سایر روش‌ها

شکل شماره 8. میزان Speed up درروش پیشنهادی در مقایسه با سایر روش‌ها

5 جمع‌بندی

در اين مقاله، یک روش زمان‌بندی وظیفه ایستای چندهدفه برای طراحی سیستم‏های نهفته ارائه‌شده است. در این روش، وظایف به‌صورت یک گراف وظیفه مدل شده و با توجه به معماری سخت‌افزاری موجود، روشی برای نگاشت و زمان‌بندی وظایف بر روی معماری سخت‌افزاری با استفاده از الگوریتم ژنتیک پیشنهاد می‌شود. روش پیشنهادی به بهینه‌سازی چندهدفه برای پارامترهای زمان اجرای وظایف، توان مصرفی و قابلیت اطمینان می‌پردازد و به این منظور، از انتخاب راه‌حل‌های پارتو استفاده می‌نماید. استفاده از یک راهبرد بهینه‌سازی چندهدفه این امکان به طراح سیستمی می‏دهد تا بتواند بین پارامترهای مختلف طراحی سیستم (سخت‌افزاری/نرم‌افزاری) موازنه مدنظر خود را انجام دهد. همان‌طور که در بخش نتایج نشان داده‌شده است در مقایسه با روش EGATS در معیار SLR و Speedup به ترتیب 28.6 و 27.8 درصد بهبود دست‌یافته‌ایم، که نشان می‌دهد توانسته‌ایم مجموعه وظایف را بر روی پردازنده‌های بهینه‌تر اجرا کنیم و درنتیجه به مجموعه پاسخ بهبودیافته نسبت به روش EGATSدست پیداکرده‌ایم.

مراجع

[1]	J. P. Roth, “Diagnosis of automata failures: a calculus and a method,” IBM Res Dev, pp. 278-281, 1966.
[2]	S. A. Cook, “The complexity of theorem proving procedures,” ACM symposium on theory of computing, pp. 151-158, 1971.
[3]	J. Shi, G. Fey, R. Drechsler, A. Glowatz, and F. Hapke, “PASSAT:efficient SAT-based test pattern generation,” Proceedings of the IEEE annual symposium on VLSI, pp. 187-196, 2005.
[4]	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.
[5]	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
[6]	Majd, Amin, et al. "NOMeS: Near-optimal metaheuristic scheduling for MPSoCs." 2017 19th International Symposium on Computer Architecture and Digital Systems (CADS). IEEE, 2017.
[7]	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.
[8]	H. Marijn , M. Järvisalo and A. Biere, “Efﬁcient CNF simpliﬁcation based on binary implication graphs,” International Conference on Theory and Applications of Satisfiability Testing, pp. 201-215, 2011.
[9]	P. Jackson and D. Sheridan, “Clause form conversions for boolean circuits,” International Conference on Theory and Applications of Satisfiability Testing, Berlin Heidelberg, 2004.
[10]	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.
[11]	Majd, Amin, et al. "NOMeS: Near-optimal metaheuristic scheduling for MPSoCs." 2017 19th International Symposium on Computer Architecture and Digital Systems (CADS). IEEE, 2017.
[12]	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.
[13]	G. Tseitin, On the complexity of derivation in propositional calculus, Berlin Heidelberg: Springer , 1983.
[14]	L. T, “Test pattern generation using boolean satisfiability,” IEEE Transactions on Computer-Aided Design, pp. 4-15, 1992.
[15]	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
[16]	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.
[17]	M. Davis and H. Putnam, “A computing procedure for quantification theory,” Journal of the ACM (JACM), Vol. 7, No. 3, pp. 201-215, 1960.
[18]	S. Eggersglüß and R. Drechsler, High Quality Test Pattern Generation and Boolean Satisfiability, Berlin: Springer Science & Business Media, 2012.
[19]	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.
[20]	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.
[21]	W. Lin and X. Jin, "Toward The Flexible Operation Of Integrated Community Energy System: A Two-Stage Multi-Objective Scheduling Method", Science Trends, 2018.
[22]	J. Sanders and E. Kandrot, CUDA by example: an introduction to general-purpose GPU programming, Addison-Wesley Professional, 2010.
[23]	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.
[24]	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.
[25]	M. Bushnell, V. Agrawal, Essentials of electronic testing for digital,memory and mixed-signal VLSI circuits, Boston, USA: Kluwer, 2000.
[26]	K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, “A fast and elitist multiojective genetic algorithm: NSGA-II,”IEEE Trans. On Evolutionary Computation, 2002.
[27]	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.
[28]	G. E. Moore, “Cramming more components onto integrated circuits," IEEE Solid-State Circuits Newsletter, 1996.
[29]	I. Meedeniya, A. Aleti, and L. Grunske, “Architecture-driven reliability optimization with uncertain model parameters”, J.of Systems and Software, 2012.

[1] Chromosome

[2]

[3] Process

[4] Crossover

[5] Parents

[6] Mutation

[7] Markov Chain

[8] Pareto frontier

[9] Anti-Break System

Share To

Article Url

A Task Mapping and Scheduling Algorithm based on Genetic Algorithm for Embedded System Design

Rimag

Links

Related Centers

Technical Support

Official pages