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

مجله فناوری اطلاعات در طراحی مهندسی

مقاله 1، دوره 5، پاییز و زمستان - شماره پیاپی 52، بهمن 1393، صفحه 1-24

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

چکیده

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

کلیدواژه‌ها

زمانبندی وظایف؛ زمانبندی ایستا؛ سوئیچینگ خطی فضای حالت؛ پایداری؛ سیستم های کنترل

اصل مقاله

1 -مقدمه 1 تاکنونجنبههای متفاوتی از زمانبندی وظایف توسط محققان مطرح شده است. زمان بندی وظایف در بسیاری از مسائل واقعی جهان مانند مدیریت پروژه، مدیریت منابع انسانی و مالی و همچنین سیستمهای محاسباتی توزیع شده کاربرد دارد. منابع این کاربردها ممکن است دارای تواناییهای متفاوت (منابع ناهمگن) یا یکسان (منابع همگن) باشند. برای مثال پردازشگرها با توانهای پردازشی مختلف، ناهمگن می باشند. یک سیستم چندپردازندهای علاوه بر سریع بودن، باید منابع موجودش را نیز به صورت مؤثر بکار گیرد. هر کاربرد، چالشهای خاص خود را به همراه دارد. برای مثال، علیرغم پیشرفت مداوم در سخت افزار کامپیوتر، همیشه کاربردهایی وجود دارند که نیازمند توان پردازشی بیشتری از میزان موجود هستند. زمانبندی نامناسب وظایف میتواند، به کارگیری صحیح توان یک سیستم توزیع شده را تحت تأثیر قرار دهد و به سبب ایجاد سربار مفرط ارتباطی یا بهرهوری کم منابع، در موازی سازی، انحراف ایجاد نماید [1 .[ تعریف سادة زمانبندی وظایف، عبارت است از انتساب وظایف به منابع، در حالی که کل زمان 2 اجرا در حالت برون خط حداقل شود. در زمانبندی ایستا، زمان بند وظایف از تمام ویژگیها در مورد وظایف و پردازشگرها قبل از 1- Task Sceduling 2- Offline فرایند اجرا در دنیای واقعی آگاه است؛ بنابراین، یافتن یک زمانبندی قبل از اجرا در دنیای واقعی ممکن است. این مسئله complete-NP است، مگر در دو حالت[2 :[ 1 (زمانبندی وظایف بازمان برابر برروی تعداد دلخواهی از پردازشگرها 2 (زمانبندی وظیفههایی با یک یا دو واحد زمانی بر روی دو پردازشگر. در این حالات، هزینۀ ارتباطی بین وظایف برنامهی موازی در نظر گرفته نمیشود. بنابراین، زمانبندی وظایف به وسیلۀ روشهای سنتی به طور کلی مسئله پیچیدهای است. تاکنون، بسیاری از محققان این مسئله را به وسیلۀ روشهای اکتشافی و جستجوی تصادفی حل نموده اند؛ اما اغلب، قیود خاصی را در نظر گرفته اند که به غیرمؤثر بودن راهکار مورد نظردر دنیای واقعی منتهی گردیده است. ارزیابی کارآیی آنها عددی می باشد و فاقد تضمین های نظری است؛ از اینرو، ایجاد یک مدل کلی برای مسائل زمانبندی وظایف به سبب توانایی در تحلیل دقیق نظری آن لازم به نظر میرسد. در این مطالعه، شیوة مدلسازی جدیدی مبتنی بر نظریۀ سیستمهای سوئیچینگ و تحلیل نظری ارائه مینماییم. این شیوة جدید به سبب قالب کاری مبتنی بر ریاضی، ابزارهای تحلیلی قدرتمندی را برای کسب نتایج محسوس (concrete (در زمینۀ زمانبندی وظایف فراهم میآورد. این در حالیست که اکثر الگوریتمهای رقیب، تنها اکتشافی هستند. بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 3 در اینجا زمانبندی ایستای وظایف وابسته به سیستمهای چندپردازندهای ناهمگن تمرکز میکنیم. فرض میشود که موازی سازی در داخل یک وظیفه وجود ندارد و تمام دستورات به صورت ترتیبی اجرا میشوند. لازم به ذکر است که "منابع" و "پردازشگرها" را با معنای یکسان درنظر گرفته و به صورت جایگزین استفاده نمودهایم. 2 -مسئلۀ زمانبندی وظایف در زمانبندی وظایف، برنامهای که باید زمانبندی شود به وسیلۀ یک گراف وظیفه نشان داده میشود. تعریف1)گراف وظیفه) [6 .[یک گراف وظیفه، 1 گرافی بدون چرخۀ جهتدار (ܿ ,ݓ ,ܧ ,ܸ) = ܩ است که یک برنامظ کاربردیP را براساس مدل گراف نشان میدهد. گرهها (رئوس) درܸ معادل وظایف درP میباشند و یالها درܧ، ارتباطات بین وظایف را نشان میدهند. یک یال ܧ ∋ e୧୨ از گره ܸ ∋ ௝݊ , ، ارتباط از گره ௜݊ به گره ௝݊ ௝ ، ݊ ௜݊ به ௝݊ را نشان میدهد. وزن مثبت (௜݊)ݓ مربوط به گرهܸ ∋ ௝݊ هزینهی محاسباتی آن گره را نشان میدهد و وزن غیرمنفی (௝௜݁)ܿ مربوط به یال ܧ ∋ ௝௜݁ هزینه ارتباطی آن یال را نشان میدهد. قبل از اجرای یک گره، تمام گرههای قبلی آن بایستی اجرا شده و تمام ورودیهای آن بایستی دریافت شوند. بعد از اجرای یک گره، خروجیهای آن به صورت همزمان برای انتقال به گره های بعدی آماده هستند [7.[ 1- DAG = Directed Acyclic Graph مجموعه تمام گرههای قبلی ௜݊، ( ௜ نشان داده {ܧ ∋ ௫ ∈ ܸ: ݁௜௫ ،{݊با ݊)݀݁ݎ݌ میشوند. گره مبداء، گره ܸ ∋ ௜݊ بدون هیچگونه گره ماقبل است، ∅ = (௜݊)݀݁ݎ݌، و گره حفره خروج (گرهsink (یک گره ܸ ∋ ௜݊ بدون هیچ گونه گره بعدی است، ∅ = (௜݊)ܿܿݑݏ. زمانبندی یک DAG فرآیند اختصاص دادن هر گره به یک منبع و تعیین زمان آغاز آن است. برای توصیف یک زمانبندی S از یک (ܿ ,ݓ ,ܧ ,ܸ) = ܩDAG برروی یک سیستم هدف شامل یک مجموعه R از منابع اختصاصی، ௜݊)ݓ به ترتیب زمان ௜݊)௦ݐ و (௝ݎ , واژههای (௝ݎ , ܸ ∋ ௜ برروی آغاز و طول زمان اجرای گره ݊ منبع ܴ ∋ ௝ݎ را نشان میدهند. بنابراین زمان پایان ௜ یک گره به وسیله௙(݊ ݐ ௜݊)௦ݐ = (௝ݎ , ௜݊)ݓ(௝ݎ , (௝ݎ , محاسبه میشود. (௜݊)݁ܿݎݑ݋ݏ݁ݎ منبع r که به آن ௜݊ اختصاص داده شده است را نشان میدهد . برای رسیدن به یک زمانبندی مناسب، دو شرط وجود دارد که بایستی برای تمام گره ها در G برآورده شوند[7 .[ شرط 1)قید منبع اختصاصی). در هر زمان به هر منبع حداکثر یک وظیفه اختصاص داده می ،݊௝ شود. به عبارت دیگر، برای هر دو گرهܸ ∋ ௝݊ , اگر: ௜݊)݁ܿݎݑ݋ݏ݁ݎ ௝݊൫ܿ݁ݎݑ݋ݏ݁ݎ = ( ൯ ݎ௝ ቊ ௙ݐ ൫݊௜ ௝ݎ , ൯ ≤ ݐ௦ ൫݊௜ ௝ݎ , ݎ݋ ,൯ ௙ݐ ൫݊௜ ௝ݎ , ൯ ≤ ݐ௦ ൫݊௜ ௝ݎ , ൯ (1) ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 4 شرط 2)قید تقدم گره) برای n୧ , n୨ ∈ ܸ ، e୧୨ ∈ ܧ، r୩ ∈ ܴ، ௦ݐ ൫݊௝ ௞ݎ , ௙ݐ ≤ ൯ ൫݁௜௝൯,(2) که در آن ௙ݐ ൫݁௜௝൯ = ݐ௙ (݊௜ ) + (3) ቊ ௜݊)݁ܿݎݑ݋ݏ݁ݎ݂݅ 0 ௝݊൫ܿ݁ݎݑ݋ݏ݁ݎ = ( ൯ ݁ݏ݅ݓݎ݁ℎݐ݋൯݁௜௝൫ܿ که (௝௜݁)௙ݐ زمان پایان ارتباط بین وظیفه i و ௜݊ است. ً وظیفه j است و ݊)௙ݐ (௜ زمان پایان گره یک مدل زمانبندی دارای سه جزء اساسی شامل برنامه کاربردی، محیط محاسباتی هدف، و یک معیار کارآیی برای زمانبندی می باشد [11-8 .[این مدل که در زیر تعریف میشود شامل یک تعمیم برای منابع ناهمگن است. یکی از مهمترین ویژگیهای یک DAG ،رتبه 1 روبه بالا است که به صورت زیر محاسبه میشود: تعریف 2)رتبه روبه بالا). رتبه روبه ܸ ∋ ௜ به صورت بازگشتی به وسیلۀ رابطه بالای ݊ زیر تعریف میشود: ݎ݇݊ܽ௨ (4) (݊௜ ഢ௡ݓ = ( ݔܽ݉ + തതതത ௡ೕ∈௦௨௖௖(௡೔ ) ቀܿ൫݁పఫ൯ ቁ݆݊ݑ݇݊ܽݎ + തതതതതതതതതതതതതതതത که در آن (௜݊)ܿܿݑݏ مجموعهی گرههای مابعد (పఫ ௜ ܿ(݁ ، بلافصل وظیفه݊ میانگین هزینه ارتباطی ധധധധധധധ از یال (j,i (و ௡ݓ ഢ ധധധധധ میانگین هزینۀ محاسباتی از 1- Upward ௜݊ است. برای وظیفۀ خروج ௧௜௫) ݊௘گره وظیفه sink ،(رتبه رو به بالا برابراست با: (5) ௨ܽ݊݇ݎ (݊௘௫௜௧) = ݓ௘௫ప௧ തതതതതതത. مسئله زمانبندی وظایف دارای شرایط و فرضهای زیر است:  وظایف دارای وابستگی به یکدیگر هستند که بوسیله ی DAG نشان داده میشود.  بین وظایف در DAG هزینهی ارتباطی وجود دارد (هزینه ارتباطی هنگامی که وظایف وابسته بروی پردازشگرهای متفاوت زمانبندی می شوند، درنظر گرفته میشود).  محیط مسئله ایستاست و تمام اطلاعات در ابتدا مشخص است.  پردازشگرها ناهمگن هستند و به صورت توپولوژی کاملا متصل به یکدیگر متصل شده اند.  یک سیستم ارتباطی مستقل وجود دارد که پیامهای ارتباطی بین پردازشگرها را انتقال میدهد. 3 -کارهای مرتبط زمانبندی سیستمهای توزیع شده چالشی جدید در حوزه مسئله زمانبندی وظایف است که حجم قابل توجهی از مطالعات را در سالهای اخیر به خود اختصاص داده است. عموماً، روشهای موجود بدون در نظر گرفتن جنبه مدلسازی فقط به ً حل نمودن مسئله زمانبندی وظایف پرداختهاند. روشهای سنتی که برای حل این مسئله استفاده میشوند میتوانند به طور کلی به دو دسته اکتشافی (زمانبندی مبتنی بر لیست) و جستجوی تصادفی (مانند الگوریتم ژنتیک، بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 5 anealing simulated و PSO (تقسیمبندی شوند. Kong و همکاران (٢٠٠٨(PSO را با زمانبندی مبتنی بر لیست ترکیب کردند و یک الگوریتم PSO دیگر را برای زمانبندی وظایف بر روی چندپردازندهایها توسعه دادند. برخلاف بیشتر الگوریتمهای اکتشافی مبتنی بر تکثیر که سعی در تکثیر تمام گرههای اجداد ممکن یک گره افزوده شده مینمایند، shin و همکاران (٢٠٠٨ (١١ یک الگوریتم مبتنی بر تکثیر جدید پیشنهاد نمودند که برخی گره ها را بدون تکثیرهای افزونه براساس بعضی پارامترها مانند زمان آغاز و زودترین شکاف آزاد، تکثیر مینماید. به یک تکثیر هنگامی افزونه گفته میشود که به بهبودی در کارآیی یا کاهشی در طول زمانبندی یک پردازشگر مفرد منجر نگردد. روش آنها دارای دو گام است. در گام اول، لیست اولویت وظایف ساخته میشود؛ و در گام دوم، بهترین پردازشگر ممکن، که پردازشگری است که زودترین زمان آغاز را اجازه میدهد، انتخاب میشود تا وظیفه با بالاترین اولویت را اجرا نماید. Kuo و همکاران (٢٠٠٨ (makespan]13 [را در مسئله زمانبندی shop-flow حداقل نموده و PSO ترکیبی جدیدی با نام HPSO را معرفی نمودند. آنها شیوه یکدینگ کلید- تصادفی (RK ،(شیوه افزایش (Enhancement (فردی (IE ،(و PSO را ترکیب نمودند. Choi و همکاران (٢٠٠٨ (١٤کارهای دارای تأخیر در یک زمانبندی shop flow ترکیبی دو مرحلهای را حداقل نمودند. هر کار از طریق دو گام فرآوری به طوری سری پردازش میشود که هر یک دارای چندین ماشین موازی یکتا میباشند. برای حل مسئله، یک الگوریتم انشعاب و تحدید، که روشی برای به دست آوردن حدود پایین و بالا و همچنین بدست آوردن ویژگیهای غالب برای کاهش فضای جستجو است، پیشنهاد شده است که راه حلهای بهینه را ارائه میدهد. علاوه براین، الگوریتم های اکتشافی دو مرحلهای پیشنهاد شدهاند تا راه حلها را برای مسائل بزرگ در یک مقدار قابل قبول از زمان محاسباتی بیابند. Yoo) ٢٠٠٩ (١٠ بوسیله یک الگوریتم ژنتیک چند هدفه (MOGA (کل تاخیر و تعداد کل پردازشگرهای مورد استفاده در زمانبندی DAGهای بلادرنگ نرم را برروی سیستمهای چندپردازندهای همگن حداقل مینماید. برای ارزیابی کروموزمها در یک جمعیت، Yoo به وسیلهی رهیافت تطبیق وزن (AWA (مسئله چند هدفه را به مسئله تک هدفه تبدیل نمود. در این رهیافت، اطلاعات مفید از جمعیت فعلی برای تنظیم مجدد وزنهای هدف استفاده میشود تا یک فشار جستجو به سمت یک نقطه ایده آل مثبت به دست آید. Hwang و همکاران (٢٠٠٨ (١٥ با استفاده از الگوریتم ژنتیک، یک DAG را بر روی سیستم چندپردازندهای زمانبندی نمودند تا بهترین زمانبندی را با حداقل makespan بدست آورند. آنها مکانیزم کدینگ جدیدی با یک کروموزوم چند وظیفهای طراحی نمودند که از نمایش اولویت استفاده مینماید. نمایشی که چند کروموزوم مبتنی بر اولویت نامیده میشود از 11 (٢٠١٠) Sinnen و Shahul .(PMC) ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 6 الگوریتم *A برای زمانبندی وظایف بر روی پردازندههای همگن به صورت بهینه استفاده نمودند. *A یک الگوریتم جستجو با ارزیابی اولین و بهترین رکورد میباشد و تضمین مینماید تا راه حلهای بهینه را با یک تابع هزینه قابل تصدیق و سازگار بیایبد. آنها یک تابع هزینه مبتنی بر سه مؤلفه: 1 -حد پایین محاسبات، 2-زمان بیکاری و3 -زمان آمادگی داده پیشنهاد کردند. آنها از یک تکنیک هرس برای حذف نمودن زیر درختهای نامناسب در فضای جستجو استفاده کردند. در برخی از مقالات مانند (2010](19 [و (2010](21 ،[نویسندگان یک راه حل اولیه غیر تصادفی را فرض نمودند. در (2010](19 [زمانبند، یک رهیافت مبتنی بر اکتشاف را به کار می گیرد تا به سرعت زمانبندیهای مؤثری را بیابد؛ در حالی که احتمال اینکه منابع در طول گام تولید یک زمانبندی، بیکار شوند را کاهش دهد. این موضوع برای GA راه حل آغازین قابل قبولی را فراهم میآورد در مقایسه با آغاز از یک جمعیت اولیهای که به طور کامل تصادفی تولید شده است، Zamfirache و همکاران (2011](21 [یک مکانیزم زمانبندی توسعه دادند که با یک الگوی زمانبندی اولیه که به وسیله یک الگوریتم GA تولید شده است شروع میشود و سپس به منظور تطبیق الگوی زمانبندی با محیط، تغییرات در منابع محاسباتی در طول زمان را بعد از هر رخداد زمانبندی در نظر میگیرد. Long و همکاران (2011](22 [یک قالب شبیهسازی توزیع شده مبتنی بر عامل و یک روش زمانبندی بهینه شده توزیع شده با اطلاعات جزئی را پیشنهاد نمودند. زمانبند، فاکتور تنظیم بار را نیز در نظر میگیرد. یکی از بهترین الگوریتمهای اکتشافی شناخته شده در مسئله زمانبندی وظایف روش HEFT است که در [3 [معرفی شده است. این الگوریتم در مقایسه با الگوریتمهای دیگر برحسب میانگین نرخ طول زمانبندی و تسریع به صورت قابل ملاحظهای بهتر عمل مینماید [20, 3 .[بنابراین این روش را به عنوان یک الگوریتم محک در این مقاله مورد استفاده قرار میدهیم. شکل (1( الگوریتم HEFT را نشان میدهد. شکل (1 :(الگوریتم HEFT همانگونه که نشان داده شده است، HEFT دارای دو بخش است. در اولین بخش، HEFT گرهها را براساس رتبه ی روبه بالا مرتب مینماید. در دومین بخش، HEFT وظیفه با بالاترین مقدار رتبه رو به بالا را در هر گام انتخاب مینماید و وظیفه انتخابی را بر روی پردازشگری که زمان پایان آن را حداقل مینماید، زمانبندی مینماید. این گام تا زمانی که تمام وظایف بر روی پردازشگرها زمانبندی شوند، تکرار میشود. پیچیدگی زمانی اولین بخش بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 7 الگوریتم HEFT برای مرتب سازی وظایف (ܶ݃݋݈ܶ)ܱ است و پیچیدگی زمانی دومین بخش، (ܯ .ܶ)ܱ است، به سبب خطوط 4 و 5 در شکل (2 (که T تعداد وظایف و M تعداد پردازشگرها است. به طور کلی پیچیدگی زمانی الگوریتم HEFT برابر است با (ܯ .ܶ)ܱ. 4 -مقدمهای بر سیستم های سوئیچینگ سیستم سوئیچینگ، یک سیستم متغیر در زمان است که شامل تعدادی متناهی از زیرسیستمها و یک قانون منطقی است که سوئیچینگ بین این زیرسیستمها را هماهنگ مینماید. به شکل ریاضی، این زیر سیستمها معمولاً توسط یک مجموعه از معادلات دیفرانسیل اندیس دار یا معادلات تفاضلی توصیف میشوند. در این مقاله، برروی سیستم های سوئیچینگ که زیرسیستمهایشان، سیستمهایی با یک مجموعه از سیستمهای ثابت خطی گسسته زمانی (LTI( هستند، تمرکز مینماییم [4 :[ (1) ܺ[݇ + 1] = ܣ + [݇]ܺ௜ܤ} ∋ ݅,[݇]ܷ௜1,2, 3, …, ܰ}(6) ܻ (2) [݇] = ܥ + [݇]ܺ௜ܦ} ∋ ݅ ,[݇]ܷ௜1,2, 3, …, ܰ} در رابطه فوق، [݇]ݔ متغیر وضعیت در گام k ୧ܦ ماتریس های زیرسیستم iام از ୧ܥ، ୧ܤ، ୧ܣ، و ان دادن اعداد ା برای نش فضای حالت هستند، و ܼ غیر منفی استفاده میشود. مجموعه متناهی Q یک مجموعهی اندیس است و برای مجموعهی حالتهای گسسته استفاده میشود. قانون منطقی که سوئیچینگ را بین این زیرسیستمها هماهنگ مینماید، سیگنالهای سوئیچینگ را تولید می کند، که معمولاً به عنوان کلاسهایی از نگاشتهای ثابت ܳ → ା توصیف میشوند. منظور از تکهای ܼ نگاشت ثابت تکهای این است که سیگنال سوئیچینگ (݇)σ تعدادی متناهی از ناپیوستگیها را در اختیار ା را بر روی هر بازه متناهی از ܼ دارد. این نیازمندی همیشه بوسیلهی سیستمهای سوئیچینگ گسسته زمانی برآورده میگردد. زیرا یک حد آستانهای حداقل زمان انتظار در اجتناب 1 از تصادمهای ممکن در سیگنال سوئیچینگ کمک مینماید. تصادم در سیستمهای سوئیچینگ زمانی اتفاق میافتد که سیگنال سوئیچینگ از یک زیرسیستم به دیگری به سرعت اتفاق افتد، به گونهای که حداقل زمان مورد نیاز برای ماندن سیستم در یک زیرسیستم خاص برآورده نشود[4 .[ معمولاً معادله فضای حالت سیستمها را به یک مدل سیستم سوئیچینگ شکلدهی مجدد مینماییم، زیرا با استفاده از این شکل، مسئله تعیین بردارهای کنترل به یک مسئلهی بهینه سازی تبدیل میشود که برای یک کنترلگر سوئیچینگ مناسب جستجو مینماید [5 .[شکل (2 (مثالی را از سیستم سوئیچینگ خطی و فرموله بندی آن نشان میدهد. 1-Chattering ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 8 شکل (2 :(سیستم سوئیچینگ خطی 5 -مدل زمانبندی پیشنهادی در فضای حالت حل مسائل زمانبندی وظایف ناهمگن به ً وسیله رهیافتهای سنتی مدلسازی/جستجو به طور کلی complete-NP میباشند. ً از اینرو، یک شیوه ً مدلسازی متفاوت مبتنی بر شیوه فضای حالت غیرخطی در اینجا پیشنهاد شده است. فرض کنید یک شکل کلی از یک سیستم غیرخطی در زمان گسسته: [ܶ߂݇,[ܶ߂݇]ܷ,[ܶ߂݇]ܺ]݂ = [ܶ߂(1ܺ[(݇ + [ܶ߂݇,[ܶ߂݇]ܷ,[ܶ߂݇]ܺ]݃ = [ܶ߂݇]ܻ ݇ ∈ {1,2,3,… }, ܺ ∈ ℝ௡ ,ܻ ∈ ℝ௡ , ܷ ∈ ℝ௠ (4) که در آن ݂ و ݃ بردار غیرخطی توابع، ܺ یک بردار از متغیرهای وضعیت، ܷبردار کنترل، ܻ خروجی سیستم و ܶ∆ طول گامهای زمانی میباشند. در اینجا پیشنهاد مینماییم تا زمانبندی وظایف را در شکل غیرخطی فوق مدل نماییم، معادله (7 .(اجزاء مختلف این مدل در زیربخشهای بعدی نشان داده شده اند. 1-1 -تعاریف اولیه در مدل پیشنهادی  متغیرهای وضعیت متغیرهای وضعیت در این مدل متناظر با یک بردار (X (است که اندازه ی آن برابر با تعداد وظایف است، و هر عنصر دارای یک مقدار بین 0 (وظیفه کامل شده است) و 1) اجرای وظیفه آغاز ௝ نشده است). از اینرو، هر عنصر ݔ [݇] متناظر با فرآیند باقیمانده از یک وظیفهی داده شدهی j در k امین گام است. ଵݔ] = [݇]ܺ ଶݔ [݇] ்ݔ . . . [݇] [݇]] ′ (۵) که در آن (|V=|T (و تمام عناصر [k[X معمولاً به 1 مقداردهی شدهاند.  بردار کنترل بردار کنترل [k[U ماتریسی ܶ × ܯ است، که |V=|T| ،R=|M ،و وضعیت اجرای هر وظیفه و هر منبع در k امین گام زمانی را نشان میدهد. هر عنصر در این ماتریس بین 0 و 1 است و توان پردازشی موجود هر منبع را نشان میدهد. ویژگیهای این ماتریس این است که در هر گام حداکثر یک عنصر غیرصفر در هر سطر و هر ௝,௜ݑ در k امین گام ستون وجود دارد. عنصر [݇] زمانی درصد بهرهوری منبع i در اجرای وظیفهی ௝,௜ j را نشان میدهد. اگر ݑ 1 ، [݇]=گفته میشود که وظیفهی jدرk امین گام زمانی، کاملاً بر روی پردازشگر i اجرا شده باشد. یک قید مهم در بردار کنترل این است که تمام وظایف، که به صورت همزمان در گام زمانی k ام اجرا میشوند، باید از یکدیگر مستقل باشند. به عبارت دیگر، هر وظیفه بایستی بتواند تنها بر روی یک منبع پردازش شود، و هر منبع میتواند حداکثر یک وظیفه را در هر زمان پردازش نماید.  قیود در طراحی کنترلگر بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 9 تحلیل و طراحی پایداری الگوریتم کنترل باید قیود مسئله را در نظر بگیرد. این قیود به صورت زیر خلاصه میشود: قید مقداردهی اولیه: بردار وضعیت اولیه به یک ستون از یک برابر میشود. در ابتدا تمام وظایف نیاز دارند اجرا شوند. ܺ[0] = [1 1 . . . 1] ′ (6) تمام عناصر بردار کنترل U در بازه ی [1,0[ انتخاب میشوند. ∀݅,݆ 0 ≤ ݑ ≥ ௝,௜1 (7) قید استقلال: در هر ستون و هر سطر از بردار کنترل،U ،حداکثر یک عنصر غیر صفر وجود دارد. به عبارت دیگر، در هر زمان حداکثر یک منبع اختصاص داده شده به هر وظیفه وجود دارد. و همچنین در هر زمان حداکثر یک وظیفه انتساب داده شده به یک منبع وجود دارد. ݆∀} ⇒ 0௜,௝ ≠ ݑ∃ ݂݅ ௝,௜ݑ݆ =/ ′ ′ = 0 , ∀݅ ௜ݑ݅ =/ ′ ′ ,௝ = 0} (8) قید گرههای ماقبل: براساس رابطهی تقدم در DAG ،هر وظیفه میتواند تنها بعد از اجرای گره (های) ما قبلش اجرا شود. به عبارت دیگر (9) ௝݊൫݁݀ݎ݌ ∋ ݎ∀) ⇒ 0௜,௝ ≠ ݑ ∃ ݂݅ ൯ ݔ = ௥0) قید استقلال وظایف همروند: براساس رابطهی تقدم در DAG ،تمام وظایفی که به صورت همروند اجرا میشوند، از یکدیگر مستقل هستند. به عبارت دیگر، ⇒ 0൯ ≠ ௦௥,ݑ& 0௜,௝ ≠ ݑ൫݂݅ݏ ,ݎ ,݆,݅∀ (ߤ,௝௦ = 0 &ߤ௦,௝ = 0) (10) قید هزینه ارتباطی: اگر دو وظیفه با رابطه تقدم بر روی پردازشگرهای مختلف زمانبندی شوند، هزینه ارتباطی غیرصفر درنظر گرفته میشود. قید تکمیل وظیفه: پس از تکمیل اجرای وظیفه، منبع متناظر آزاد میگردد. به عبارت دیگر، ௝ݔ݂݆݅,݅∀ ௝,௜ݑ ⇒ 0[݇] = [݇ + 1] = 0 (11) قید تمامیت: از آن جایی که یک وظیفه، یک منبع را تا زمانی که به طور کامل اجرا نشود، آزاد نمیکند، تمام وظیفههای داده شده باید منتسب شوند و کامل شوند. ௝,௜ݑ݇ ∃ ݅ ∃ ݆∀ [݇] ≠ 0 (12) 5-2 -تابع سیستمی غیرخطیf تابع f در پویایی سیستم، معادلهی (6 ،( پارامترهای تعریف کنندهی سیستم مانند بردار متغیرهای وضعیت X ،بردار کنترل U ،گام زمانی k ،و همچنین DAG را مرتبط مینماید. برای مسئلهی زمانبندی وظایف، f در شکل زمان گسسته به صورت زیر تعریف میشود، (13) ܺ[݇ + 1] = ݉ܽݔ ቆ0,ܺ[݇] − ∆ܶ ∗ ܦ)݃ܽ݅ቈ 1 ቇ௜௝ ቉ ∗ ܷ)ߠ که در آن ܶ∆ گام زمانی بر حسب ثانیه، ݃ܽ݅ܦ ࡹ∗ࢀ[ است، که ௝௜ قطر اصلی ماتریس A و ߠ] = ߠ در آن ௝௜ߠ زمان محاسباتی وظیفه ی i برروی پردازشگر j را نشان میدهد. عملگر ݔܽ݉ برای تضمین منفی نشدن متغیر وضعیت منفی انتخاب ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 10 شده است. به عبارت دیگر، از آنجا که زمان اجرای هر وظیفه متفاوت است، برخی از وظایف ممکن است قبل از دیگر وظایف در طول بازهی گسسته زمانی یکسان کامل شوند؛ لذا لازم است تا از عملگر ݔܽ݉ استفاده نماییم. همچنین، هزینه ارتباطی بین وظایف (برروی پردازشگر های یکسان و یا مختلف) به وسیله ߤ نشان داده شده است که یک ماتریس T*T است. هزینه ارتباطی در فرآیند تعیین بردارهای کنترل فرض میشود. این بردارهای کنترل هنگامی که ارتباطات بین دو وظیفه در حال انجام است، یکسان باقی میمانند. به محض تکمیل ارتباط، پردازشگرها اجرای عملیاتشان را همانگونه که توسط بردار کنترل دستور داده میشود، ادامه میدهند. برای مثال، ௟ اگر ܷ ، l امین بردار کنترل، در گام بازه [b,a[ ାଵ ௟اعمال شود، سپس بردار کنترل ܷ قابل اعمال است اگر تمام اطلاعات آن دریافت گردد. بنابراین ܷ ௟ାଵ در گام بازهی [d,c [که ܾ ≤ ܿ اعمال میشود. در طول گامهای b تا c ،بردار کنترل ௟ جاری، همچنان بردار کنترل قبلی ܷ است، که تأثیری بر وضعیت سیستم ندارد. 5-3 -تابع خطیࡸࢌ به منظور سادهسازی یک مدل پیچیده و استفاده کردن از نتایج نظری گسترده در زمینه سیستمهای خطی، معادلات غیرخطی معمولا به معادلات خطی تبدیل میشوند [16 .[سیستمهای کنترل خطی برای طراحی ساده تر هستند، اما این تبدیل معمولاً به نتایج تقریبی منتهی می گردد که ممکن است غیرقابل قبول باشند. در اینجا، ساختن سیستمهای کنترل خطی برای یافتن کنترلگرهای سوئیچینگ خطی مناسب (مسئله بهینه سازی) استفاده شده است. قیود غیرخطی به صورت مجزا از کنترلگر سوئیچینگ خطی درنظر گرفته شده اند؛ از این رو مدل حاصل دقیق است. به وسیله ساده سازی مدل به یک کنترلگر سوئیچینگ خطی، این قیود به صورت مؤثری فضای جستجو برای کنترلگرهای مناسب را "کاهش میدهد"[٥ .[به صورت ویژهتر، به وسیله در نظر گرفتن تمام غیرخطی بودنها به عنوان قیود غیرخطی در فرآیند طراحی کنترلگر، یک تابع ௟݂ برای همتای غیرخطی آن ݂ جایگزین خطی نمودیم. مدل حاصل، سپس آن را به یک مسئله کنترل خطی تبدیل میکند. به همین سبب، عملگرهای max و Diag بایستی از معادله (16( حذف شوند. زیربخشهای بعد این مسئله را با جزئیات بیشتر مورد بررسی قرار می دهد. 5-3 -1 -حذف عملگر Diag و ساده سازی به وسیله نظریه زیر، عملگر Diag از ضرب دو ماتریس کلی حذف میشود. نظریه 4 -شکل خطی از (ܷ × ܳ)݃ܽ݅ܦ، که Q یک ماتریس ܾ × ܽ و U یک ماتریس ܽ × ܾ هستند، به صورت زیر است: بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 11 (ܷ × ܳ)݃ܽ݅ܦ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ݍଵଵ … ݍଵ௕ 0 . . . . . . 0 0 ݍଶଵ … ݍଶ௕ 0 . . . . . 0 0 0 ݍଷଵ … ݍଷ௕ 0 . . . . 0 . . 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 . . . . . . 0 ݍ௔ଵ … ݍ⎦௕௔ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤  ∗ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ଵଵݑ ଶଵݑ ଷଵݑ ⋮ ଵ௕ݑ ଵଶݑ ଶଶݑ ଷଶݑ ⋮ ଶ௕ݑ ⋮ ௔ଵݑ ௔ଶݑ ௔ଷݑ . . . ⎦௔௕ݑ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ (17) اثبات- میتوانیم ௕×௔ܳ و ௔×௕ܷ را به صورت بردار نشان دهیم: ܳ௔×௕ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ തݍ ଵ തݍ ଶ . തݍ ௜ . . തݍ ௔ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ തݍ , തଵݍ] = ௜ തଶݍ ௜ ௜ ௕തݍ . . . ௜ ] (18) തݑ] = ௔×௕ܷ ଵ ݑത ଶ തݑ . ௝ തݑ . . തݑ ,[௔ ௝ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ തଵݑ ௝ തଶݑ ௝ . . . ௕തݑ ௝ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ . (19) بنابراین، میتوانیمQ را به عنوان یک بردار با a سطر و یک ستون و همچنین، U را به عنوان یک بردار با یک سطر و b ستون بنویسیم. میتوانیم بنویسیم: ) ݃ܽ݅ܦ = (ܷ × ܳ)݃ܽ݅ܦ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ തݍ ଵ തݍ ଶ . തݍ ௜ . . തݍ ௔ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ തݑ] ∗ ଵ ݑത ଶ തݑ . ௝ തݑ . . ௔]) ൥)݃ܽ݅ܦ = തݍ ଵݑത ଵ ⋯ ݍത ଵݑത ௔ ⋮ ⋱ ⋮ തݍ തݑ௔ ଵ ⋯ ݍത തݑ௔ ௔ ൩ ) തݍ] = ଵݑത ଵ ݍത ଶݑത ଶ തݍ . . . തݑ௔ ௔] (20) ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 12 همچنین میتوانیم بنویسیم: ( ܷ × ܳ)݃ܽ݅ܦ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ݍଵଵ … ݍଵ௕ 0 . . . . . . 0 0 ݍଶଵ … ݍଶ௕ 0 . . . . . 0 0 0 ݍଷଵ … ݍଷ௕ 0 . . . . 0 . . 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 . . . . . . 0 ݍ௔ଵ … ݍ⎦௕௔ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ∗ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ଵଵݑ ଶଵݑ ଷଵݑ ⋮ ଵ௕ݑ ଵଶݑ ଶଶݑ ଷଶݑ ⋮ ଶ௕ݑ ⋮ ௔ଵݑ ௔ଶݑ ௔ଷݑ . . . ⎦௔௕ݑ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ (21) براساس نظریه 4 ،معادله) 16 (تبدیل میشود به ܺ[݇ + 1] ݔܽ݉ = ⎝ ⎜ ⎜ ⎜ ⎜ ⎛ ∗ ܶ߂ − [݇]ܺ,0 ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ തݍ ଵ 0 . . . . . . 0 0 ݍത ଶ 0 . . . . . 0 0 0 ݍത ଷ 0 . . . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . . . . . . 0 ݍത ் ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ∗ ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ തݑ ଵ തݑ ଶ . . . തݑ ்⎦ ⎥ ⎥ ⎥ ⎥ ⎤ ⎠ ⎟ ⎟ ⎟ ⎟ ⎞ (22) maxعملگر سازی خطی- 2 -3-5 اینجا، عملگر max را به وسیله درنظر گرفتن یک قید برروی طراحی بردارهای کنترل حذف میکنیم. این فرآیند به وسیله مثال زیر نشان داده شده است. مثال- اگر سه منبع و همچنین سه وظیفه مستقل وجود داشته باشد، یک بردار کنترل ممکن به صورت زیر را در نظر می گیریم: شکل (3 :(یک بردار کنترل ممکن طول زمان اجرای هر وظیفه فرض میشود باشد: بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 13 طول زمان اجرای اولین وظیفه بر روی اولین منبع 10 واحد است. طول زمان اجرای دومین وظیفه بر روی دومین منبع 5 واحد است. طول زمان اجرای سومین وظیفه بر روی سومین منبع 12 واحد است. سپس، ممکن است تا بردار کنترل شکل 3 را به صورتی که در شکل (4 (است به چندین بردار کنترل تجزیه شود. شکل (4 :(الف) بردار کنترل 1 ،ب) بردار کنترل 2 ، پ) بردار کنترل 3 به عبارت دیگر، ما وظایف متناظر را در بردار کنترل در یک ترتیب صعودی از طول زمان اجرا،از صفر خارج می نماییم. بوسیله ی این روش، اگر اجرای یک وظیفه پایان یابد، منبع متناظرش آزاد میشود، و عناصر متناظرش از متغیرهای وضعیت منفی نمیشوند.با درنظرگرفتن این قید جدید برروی بردار کنترل، میرسیم به یک مدل خطی به صورت زیر: ܶ߂ − [݇]ܺ = [1ܺ[݇ + ∗ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ തݍ ଵ 0 . . . . . . 0 0 ݍത ଶ 0 . . . . . 0 0 0 ݍത ଷ 0 . . . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . . . . . . 0 ݍത ் ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ∗ ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ തݑ ଵ തݑ ଶ . . . തݑ ்⎦ ⎥ ⎥ ⎥ ⎥ ⎤ (23) 5-4 -مدل سوئیچینگ در مسائل زمانبندی وظایف در معادله) 23،(U یک ورودی خطی با قیود غیرخطی است. ً اکنون مناسب است تا یک شیوه ساده برای طراحی کنترلگر بیابیم. با تبدیل این مدل به یک مدل سوئیچینگ فضای خطی میتوانیم روشهای متفاوت بهینه سازی/طراحی را برای حل آن استفاده نماییم. اگر معادله) 23 (به صورت زیر نوشته شود: ,[݇]ܷ௜ܤ + [݇]ܺ௜ܣ = [1ܺ[݇ + ݅ ∈ {1, 2, 3, … , ܰ} (٢۴) سپس در مدل سوئیچینگ، ௜ܣ = ܣݏ = ݅ , ܵ , ... ,3,2,1 = ݏ∀) ௜ܤ = ܤ, ) ௦ܷܤ + [݇]ܺܣ = [1ܺ[݇ + (25) که S تعداد زیرسیستم ها است. حداقل مقدار زیرسیستم های S برابر با تعداد سطوح در DAG است؛ به سبب اینکه در هر سطح وظایف مستقل از یکدیگر هستند؛لذا آنها می توانند احتمالا به صورت موازی اجرا شوند. حداکثر تعداد زیرسیستم ها برابر با تعداد وظایف در DAG است؛ در هر شکاف زمانی، تنها یک وظیفه اجرا میشود. بنابراین ما میتوانیم بنویسیم: ܵ ≥ ܩܣܦ݂݋ݏ݈݁ݒ݁ܮ݂݋ݎܾ݁݉ݑܰ ݏ݇ݏ݂ܽܶ݋ݎܾ݁݉ݑܰ ≥ (26) سیگنال سوئیچینگ یک سیگنال گسسته است که تعیین می نماید کدام زیرسیستم در kامین گام فعال است. طراحی کنترلگر معادل، تعیین سیگنال ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 14 سوئیچینگ و سپس یافتن مقادیر مناسب برای اندیس های سوئیچینگ است. (پ) شکل (5 :(یک مثال عددی: الف) DAG ،ب) جدول زمانی، پ) بردارهای کنترل جدول (1 :(مقادیر متغیر وضعیت بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 15 شکل (6 :(نمودار گانت مثال عددی 5-5 -تبدیل مسئلهی زمانبندی وظایف به شکل فضای حالت در این بخش، ابتدا یک مسئله زمانبندی داده شده را به شکل فضای حالت تبدیل میکنیم. سپس یک شیوه سیستماتیک برای تعیین بردارهای کنترلی که DAG ها را با حداقل کل زمان اجرا زمانبندی مینمایند، ارائه مینماییم. ما فرض میکنیم که تمام منابع به طور کامل موجود بوده و میتوانیم تمام توان پردازشی آنها را برای حل مسئله زمانبندی وظایف استفاده نماییم؛ بنابراین هر عنصر بردار کنترل، U ،صفر یا یک است.DAG و ماتریسهای ߠ در مثال شکل (5( نشان داده شده اند. در این مثال، بردارهای کنترل را به صورت دستی طراحی میکنیم. همانگونه که در جدول فوق نشان داده شده است، در 25امین گام (25=time (تمام عناصرX صفر هستند؛ بنابراین کل زمان اجرا برابر با 25 است. شکل (6 ،(نمودار گانت این مسئله را نشان میدهد. جدول 1 مقادیر متغیر وضعیت را براساس (16( در گام [ 25,0 ݇ ∈ [نشان میدهد. شکل (7 :(سیگنال سوئیچینگ ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 16 6 -یک روش سیستماتیک برای تعیین بردارهای کنترل: کنترلگر مبتنی بر ارتفاع مرتب شده در زیربخش قبل، یک مثال عددی چگونگی حل دستی مسئله زمانبندی وظایف را نشان داد؛ اما تعیین دستی بردارهای کنترل همیشه ساده نیست. دراین بخش، یک رهیافت ساده و سریع به نام HS را که نتایج مشابه به نسبت یک زمانبندی بهینه مبتنی بر HEFT را حاصل مینماید، پیشنهاد می کنیم [٣ .[ در ابتدا گرهها را در DAG براساس ارتفاعشان برچسب میزنیم: (27) ℎ݁݅݃ℎݐ௜݊) ) = ൝ ௜݊)݀݁ݎ݌݂݅ 0 ) = ∅ 1 + max ௡ೕ∈௣௥௘ௗ (௡೔ ) {ℎ݁݅݃ℎݐ൫݊௝ ݁ݏ݅ݓݎ݁ℎݐ݋ {൯ براساس تعریف، در هر بردار کنترل، وظایف با ارتفاع یکسان دارای ارتباطات تقدم نیستند، آنها میتوانند بر روی پردازشگرهای متفاوت به صورت همزمان اجرا شوند. بنابراین گره ها را براساس مقدار ارتفاعشان گروه بندی می نماییم. بردارهای کنترل به صورت صعودی از مقادیر ارتفاع مرتب میشوند. پس از گروه بندی، نیاز داریم تا وظایف در هر گروه را به پردازشگرهای مختلف اختصاص دهیم تا کل طول زمان اجرا را حداقل نماییم. در این گام، هر وظیفه را به پردازشگری که بتواند آن را زودتر از دیگر پردازشگرها تمام نماید، اختصاص میدهیم. سپس زمان آغاز و پایان بردارهای کنترل براساس این اطلاعات (گروه ها و پردازشگرها) حاصل میشوند، و سپس کنترلگر اجرا میشود. زمان آغاز هر شکاف برابر با زمان آماده شدن وظایف شامل شده و زمان پایان هر شکاف برابر با حداکثر زمان پایان وظایف شامل شده است. همانگونه که در شکل (9 (نشان داده شده است، تمام قیود (که در بخش 1.4 بیان شدهاند) برروی بردارهای کنترل به وسیله الگوریتم برآورده شدهاند. برای مثال، در هر سطر از بردار کنترل، همیشه تنها یک '1 'وجود دارد، تمام وظایف اجرا میشوند و تمام ارتباطات تقدم در نظر گرفته میشوند. بنابراین براساس نظریه 3 ،الگوریتم پیشنهادی پایدار است. شکل (8 :(الگوریتم HS بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 17 شکل (9 :(حل یک مسئله عددی به وسیله HS .الف) DAG ،ب) ماتریس ી ،پ) ارتفاع وظایف، ت) دسته بندی وظایف براساس مقدار ارتفاع، ث) بردارهای کنترل، ج) زمانبندی حاصل پیچیدگی زمانی اولین بخش از الگوریتم HSبرای مرتب سازی وظایف (ܶ݃݋݈ܶ)ܱاست و پیچیدگی زمانی بخش دوم (ܯ .ܶ)ܱ است، به سبب خطوط 8 و 9 که T تعداد وظایف و M تعداد پردازشگرهاست. به طور کلی، پیچیدگی زمانی الگوریتم HS برابر با (ܯ .ܶ)ܱ است. شکل (9 (یک مثال عددی که بوسیله ی این روش حل شده است را نشان میدهد. شکل (8( الگوریتم HS را نشان میدهد. 6-1 -مقایسه بین راه حل بهینه،HEFT ، HS در این زیربخش، نتایج HEFT وHS را با راه حل بهینه مقایسه مینماییم. راه حل بهینه به وسیله یک روش خطی که تمام زمانبندیهای ممکن را مییابد و زمانبندی با حداقل makespan را انتخاب مینماید، در نظر گرفته شده است. این مقایسه برای یک DAG کوچک انجام شده است زیرا یافتن راه حل بهینه برای DAGها و شبکه ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 18 پردازشگرهای بزرگ به سبب پیچیدگی زمانی آنها ناممکن است. به عبارت دیگر، این مسئله-NP Completeاست و به صورت ساده، قابل حل توسط روشهای سنتی نیست. شکل (10(DAG و ماتریس ߠ را نشان میدهد. در این مثال، راه حل بهینه دارای 514makespan میباشد. از آنجا که آن کوچک است، تمام دیگر روشها، HEFT و HS و زمانبندی بهینه را باmakespan برابر با 514 مییابند. شکل (10 :(مثال عددی. (الف) DAG) ، ب) ماتریس ࣂ 7 -نتایج آزمایشات در این بخش، کارآیی الگوریتم کنترلگر پیشنهادی HS را بر روی چندین مثال تصادفی شامل گراف وظایف (DAGها) تولید شده به وسیله روش P) Method-P (توصیف مینماییم [١٩ .[در این روش، DAG براساس ساختن احتمالی یک ماتریس مجاورت از یک DAG تولید میشود. عنصر ௝௜ܽ از ماتریس به صورت 1 ௝ به ݐ ௜ تعریف میشود اگر یک رابطه تقدم از ݐ وجود داشته باشد؛ در غیر اینصورت، ௝௜ܽ صفر است. ماتریس مجاورت یک گراف بدون سیکل، یک ماتریس بالامثلثی است، تمام عناصر برروی قطر و مثلث پایینی صفر هستند. هر عنصر مثلث بالایی براساس فرآیند برنولی با پارامتر p ،که احتمال موفقیت را نشان میدهد، تعیین میشود. برای هر عنصر، هنگامیکه آزمایش برنولی موفق است، یک مقدار 1 به عنصر انتساب داده میشود؛ برای شکست یک مقدار صفر به عنصر داده میشود. پارامتر 1=p یک گراف وظایف به طور کلی ترتیبی را می سازد، و 0=p یک گراف وظایف ذاتاً موازی را میسازد. مقادیر p که در بین این دو کرانه قرار می گیرند، به طور کلی DAG هایی که بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 19 دارای ساختارهای بینابینی هستند، تولید مینماید [.١٩] برای ارزیابی روش پیشنهاد شده، DAG های تولید شده به صورت تصادفی با ویژگیهای نشان داده شده در جدول (1 (استفاده شده اند. نسبت ارتباطات به محاسبات CCR معیاری است که رفتار کلی زمانبندی با توجه به ارتباطات را منعکس می نماید 6.پراکندگی DAG پارامتر برنولی است که معیاری برای ارتباطات تقدم بین وظایف است. جدول (2 :(ویژگی های مثال های تصادفی پراکندگی DAG CCR تعداد وظایف {10, 20, 30, 40, 50, 100, 150, 200, 250} 1 0.5 50 {0.1, 1, 10} 0.5 50 1 {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9} در این آزمایشات، تعداد پردازشگرهای ناهمگن برابر با 10 است و توپولوژی آنها به صورت کاملاً متصل است. هزینه محاسبات و هزینهی ارتباطات بین وظایف در گراف وظایف به صورت تصادفی براساس توزیع نرمال مشابه با [10 ,8, 1 [انتخاب شده اند. پارامترهای توزیع نرمال در جدول (3 (گزارش شده اند. هر آزمایش را 50 بار تکرار نمودیم و میانگین نتایج در هر آزمایش را گزارش نمودیم. نتایج آزمایشات با HEFT مقایسه شده اند 3 .همانگونه که در شکل (11 (نشان داده شده است، نتایج کنترلگرهای پیشنهادی بسیار نزدیک به HEFT هستند و در آزمایشات با کمتر از 50 وظیفه نتایج روشهای پیشنهادی بهتر از HEFT می باشند. شکل (11 :(مقایسهmakespan کنترلگر HS و HEFT برروی DAG های با اندازه های مختلف ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 20 همچنین، به منظور نشان دادن تفاوت بین روشهای پیشنهادی و HEFT ،نمودار درصد بهبود را در شکل (12 (ترسیم نمودیم. درصد بهبود به وسیله رابطه زیر محاسبه می شود: ݐ݊݁݉݁ݒ݋ݎ݌݉ܫ % = ௥௘௟௟௢௥௧ܽ݊஼௢௡݌ݏ݁݇ܽܯ − ்ுாிܽ݊݌ݏ݁݇ܽܯ ்ுாிܽ݊݌ݏ݁݇ܽܯ (14) همانگونه که در شکل (12 (نشان داده شده است، درصد بهبود روشهای ما در آزمایشات با تعداد وظایف کمتر از 50 ،غیر منفی است؛ این بدین معنی است که کنترلگرهای پیشنهادی زمانبندیهای بهتر و یا مساوی با HEFT یافتهاند. همچنین، حداقل درصد بهبود ٧/٢ %است. شکل (12 :(درصد بهبود makespan در رهیافت پیشنهادی HS در مقابل HEFT در آزمایشات با کمتر از 50 وظیفه، از آنجا که DAGهای تصادفی با توزیع برنولی را تولید مینماییم، ممکن است در برخی DAGها بیش از یک گره مبداء (گرهی بدون هیچ گونه گره ماقبل) وجود داشته باشد. برای مثال در DAG زیر، گره 1 و 8 گره های مبداء هستند؛ زیرا آنها هیچگونه گره ماقبلی ندارند. برخی اوقات، برخی از گرههای مبداء نزدیک به گره های حفره (sink - گره هایی بدون هیچ گره مابعد) هستند، مانند گره 8 و بنابراین دارای رتبه بالایی پایینتری میباشند. با این DAGها، HEFT به صورت زیر عمل مینماید: محاسبه رتبه بالایی تمام گره ها و سپس مرتب نمودن گره ها به ترتیب نزولی رتبه بالایی. بنابراین گره هایی مانند گره 8 که در سطوح میانی از لیست مرتب شده قرار داده میشوند، به زمانبندی با تأخیر برای آنها منتهی میشود. اگرچه چنین گره هایی رتبه بالایی پایینی را دارند، تأثیر زیادی برروی زمانبندی دارند. در HS ،از آنجا که براساس سطح عمل مینماییم، گرههای 1 و 8 دارای سطح یکسان هستند و بنابراین نسبت به HEFT زودتر زمانبندی میشوند. در DAGهایی با تعداد وظایف بیشتر، تأثیر گره هایی با زمانبندی دارای تأخیر مانند گره 8 کم است؛ بنابراین در آزمایشاتی با تعداد بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 21 وظایف زیاد، اگرچه makespan مربوط به HEFT کمتر از HS است، نزدیک به یکدیگر می باشند. شکل (13 :(یک DAG نمونه آزمایش بعدی در مورد پراکندگی DAG است. این آزمایشات برای 50 وظیفه و 10 پردازشگر که به طور کامل متصل شده اند، انجام میشود. علاوه براین، هر آزمایش 50 بار تکرار شده است و مقدار میانگین گزارش شده است. جدول (3( پارامترهای توزیع نرمالی که برای تولید تصادفی زمانهای محاسبات و ارتباطات در DAG استفاده شده است را نشان میدهد. شکل (14 (نتایج آزمایش را نشان میدهد. همانگونه که در این شکل نشان داده شده است، makespan کنترلگر HS و HEFT در تمام مقادیر پراکندگی نزدیک به یکدیگرند. شکل (14 :(مقایسهmakespan به وسیله کنترلگر HS و HEFT برروی DAG هایی با پراکندگی متفاوت علاوه براین، همانگونه که در جدول (4 (نشان داده شده است، آزمایشات بیشتری انجام شده است. هر سلول میانگین نتایج 50 اجرای مجزا از آزمایش با DAG هایی که به صورت تصادفی با پارامترهای مشخص شده ایجاد شده اند را نشان میدهد. زمان محاسبات و ارتباطات وظایف در آزمایشات به صورت تصادفی براساس توزیع نرمال تولید شده اند. شکل (3 (پارامترهای تابع توزیع نرمالی که استفاده شده است را نشان میدهد. ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 22 جدول (3 :(پارامترهای توزیع نرمال زمان محاسبات زمان ارتباطات میانگین واریانس میانگین واریانس آزمایشات با تعداد متغیری از وظایف 10 4 10 6 آزمایشات با مقدار پراکندگی متغیر 10 4 10 5 6 10 4 100 CCR=0.1 با آزمایشات 6 20 4 20 CCR=1 با آزمایشات 2 100 3 10 CCR=10 با آزمایشات جدول (4 :(آزمایشات بیشتر- میانگین و انحراف استاندارد makespanتکرار شده برای 50 اجرای مستقل # Proc Method CCR=0.1 CCR=1 CCR=10 Average STD Average STD Average STD 4 HEFT 12122.97 474.2812 3221.97 103.7077 2523.06 212.9125 HS 12221.74 482.745 3301.14 88.4415 5950.41 211.6781 5 HEFT 11989.52 551.376 3182.87 133.0228 2453.74 172.7356 HS 12071.97 544.0969 3260.24 119.5259 6000.65 280.7522 6 HEFT 12053.30 515.0406 3192.24 102.8087 2460.88 141.3361 HS 12145.20 510.445 3264.83 104.6349 5970.45 240.0112 7 HEFT 11983.04 581.9847 3182.45 107.3619 2566.24 232.5873 HS 12069.28 582.9445 3260.53 106.2959 5983.41 273.3193 8 HEFT 11980.84 553.7696 3197.57 121.3184 2479.69 167.3255 HS 12067.02 545.0182 3279.69 118.1766 6005.92 239.7304 9 HEFT 12020.58 541.7361 3188.88 126.1868 2434.67 137.639 HS 12113.87 537.4327 3270.41 117.8027 5966.56 230.7038 10 HEFT 12058.53 575.948 3183.51 114.2389 2491.59 190.4354 HS 12155.29 570.4473 3252.69 113.9986 5976.21 244.231 در این آزمایشها، تعداد وظایف T و پارامتر پراکندگی DAG به ترتیب به 200 و 5.0 ثابت شده است. تعداد پردازشگرهای متصل شده به صورت کامل و پارامتر CCR از DAG به ترتیب بین 4 تا 10 و {10،1،1.0 {تغییر می کند. همانگونه که در جدول (4 (نشان داده شده است، هنگامیکه 1.0=CCR یا 1=CCR است، نتیجه HS به طور کلی یا بهتر و یا مشابه با نتایج HEFT است. در مرحله گروهبندی HS ،تنها ارتفاع وظایف در DAG در نظر گرفته میشود که یک دیدگاه محلی به DAG دارد و انتخاب وظایف را از دیگر سطوح محدود میکند؛ هنگامی که 10=CCR ،HEFT از کارآیی HS تجاوز می نماید. بایستی ذکر شود که برنامههای کاربردی در دنیای واقعی با 10=CCR کمتر رایج می باشند، بندی ایستای و ارائه یک مدل زمان ایف با استفاده از سوئیچینگ خطی فضای حالت ظ 23 زیرا DAG هایی با 10=CCR آنهایی هستند که کل ارتباطات در آنها، 10 برابر محاسبات است. 8 -نتیجه گیری و کارهای آتی در این مقاله، مسئله زمانبندی ایستای وظایف (TS (را به وسیله پیشنهاد یک شیوه کلی جدید مبتنی بر مهندسی سیستم مطرح نمودیم. این شیوه جدید مدلسازی به سبب گستردگی توسعههای نظری آن امیدبخش است. ما نشان دادیم چگونه زمانبندی وظایف می تواند از طریق فضای حالت غیرخطی نگاشت شود و از طریق تحلیل نظری، آزمایشی از قابلیت پایداری برای سیستم حاصل را ارائه کردیم. در ادامه یک روش تبدیل پیشنهاد شده است تا این مدل از فضای حالت را به سوئیچینگ خطی فضای حالت با قیود غیر خطی تبدیل نماید. سپس دو روش سیستماتیک ارائه شدند تا بردارهای کنترل را براساس این مدل تعیین نمایند. تحلیل نظری پایداری مجانبی مدل زمانبندی وظایف حلقه بسته را تأیید مینماید. با استفاده از اصطلاحات زمانبندی وظایف، نشان داده شد که در صورت داشتن زمان کافی تمام وظایف میتوانند با کنترلگر پیشنهادی کامل شوند. سپس کنترلگرهای پیشنهادی HS با شیوه HEFT بر روی چندین آزمایش که به صورت تصادفی ایجاد شده اند، مقایسه شدند. نتایج کارآیی مقایسهای را نشان داد.این مقاله محیطهای زمانبندی وظایف ایستا را در نظر گرفت، همچنانکه برای بسیاری از تحقیقات پیشین مورد توجه بوده است؛ اما بیشتر مسائل دنیای واقعی در محیطهای پویا تعریف میشوند (تغییرات در زمان). در آینده، هدفمان در ً نظر گرفتن چگونگی اعمال این شیوه مدلسازی جدید برای چنین محیطهایی است و همچنین محیطهایی که با قابلیت پس گرفتن روبرو هستند.

مراجع

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.