ترجمه فارسی عنوان مقاله
کاهش کل زمان تکمیل در یک سیستم کامپیوتری با یک سرور و دو پردازنده ی موازی
عنوان انگلیسی
Total completion time minimization in a computer system with a server and two parallel processors
کد مقاله | سال انتشار | تعداد صفحات مقاله انگلیسی |
---|---|---|
6118 | 2005 | 13 صفحه PDF |
منبع
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computers & Operations Research, Volume 32, Issue 3, March 2005, Pages 599–611
فهرست مطالب ترجمه فارسی
چکیده
کلمات کلیدی
1. مقدمه
2. علامت ها و فرمول ریاضی
2.1. علامت ها
2.2. مدل برنامه نویسی خطی انتگرالی
3. موارد ویژه
3.1. مسئله ی مربوط به (فرمول)
3.2. مسئله ی مربوط به (فرمول)
شکل 1. مثالی که در آن SPT/FAM بهینه نمی باشد.
4. کاهش
شکل 2. زمانبندی S ساخته شده از زمانبندی S’
5. الگوریتم چند جمله ای
شکل 3. مثال پروفایل با h = 1.
6. بسط نتیجه
7. نتیجه گیری
کلمات کلیدی
1. مقدمه
2. علامت ها و فرمول ریاضی
2.1. علامت ها
2.2. مدل برنامه نویسی خطی انتگرالی
3. موارد ویژه
3.1. مسئله ی مربوط به (فرمول)
3.2. مسئله ی مربوط به (فرمول)
شکل 1. مثالی که در آن SPT/FAM بهینه نمی باشد.
4. کاهش
شکل 2. زمانبندی S ساخته شده از زمانبندی S’
5. الگوریتم چند جمله ای
شکل 3. مثال پروفایل با h = 1.
6. بسط نتیجه
7. نتیجه گیری
ترجمه کلمات کلیدی
برنامه ریزی - ماشین آلات های موازی - سرور منفرد - مغازه - جریان ترکیبی
کلمات کلیدی انگلیسی
ترجمه چکیده
موضوع مسئله ای که در این مقاله به آن پرداخته شده است، یک سیستم کامپیوتری ساخته شده توسط یک سرور منحصربفرد و دو ماشین موازی مشابه می باشد. فرض شده است که زمان های پردازش در سرور یکانی بوده و هدف، کاهش کل زمان تکمیل می باشد. این مقاله که با برنامه های زمانبندی با یک سرور سر و کار دارد، اینگونه در نظر می گیرد که فعالیت های نصب بطور همزمان نیازمند سرور و ماشین می باشند. در این مقاله، این محدودیت در نظر گرفته نشده و مسئله ی مطالعه شده، استقرار براساس جریان هیبریدی کار با محدودیت نبود وزن بین دو مرحله می باشد. یک الگوریتم که می تواند این مسئله را بصورت بهینه در زمان حل کند مطرح شده است. در نهایت، نشان داده شده است حل این مسئله بصورت بهینه به یک راه حل بهینه برای مسئله ای که بدون محدودیت نبود وزن می باشد، منجر می شود.
ترجمه مقدمه
پردازش موازی توجهات بسیار زیادی را در سال های اخیر، به خاطر بازده خوب، که بخش حیاتی در موفقیت سیستم های کامپیوتری موازی می باشد، به خود جلب کرده است. یک آرایش کلاسیک با یک سرور از فایل هایی که توسط شبکه به مشتری ها لینک شده اند، ساخته شده است. اولین مرحله ی موازی سازی شامل توزیع کد و داده های هر مسئله ای که می تواند موازی سازی شود، به یک مشتری طرح ریزی شده می باشد. برای هر برنامه ای که باید به یک مشتری فرستاده شود، سرور باید با موفقیت کد و داده های روی هارد دیسک را خوانده و آن ها را بوسیله ی شبکه به مشتری بفرستد. در تخمین اولیه، این دو مرحله می توانند بوسیله ی یک عمل روی سرور مدلسازی شوند. این فرضیه افراطی نیست، زیرا در چنین زمینه ای، طراح سعی می کند زمان های پردازش مربوط به مشتری های مختلف را متعادل سازی کند تا بهترین عملکرد اجرای موازی را بدست آورد. سپس برنامه ها و داده ها اغلب اندازه های مشابه داشته و در نتیجه، خواندن و فرستادن آن ها به زمان برابری نیاز دارد. هدف مورد نظر می تواند در صورتی که کاربر منتظر نتیجه ی سریع باشد، کاهش حداکثر زمان تکمیل باشد. اما اگر هدف استفاده از شبکه با بیشترین بازده باشد، هدفی که باید مورد مطالعه قرار گیرد کاهش متوسط زمان تکمیل یا مجموع زمان های تکمیل می باشد.
ما یک محیط زمانبندی قطعی با m ماشین موازی مشابه و n کار برای زمانبندی را در نظر می گیریم. هر کار باید بدون جلوگیری از تعیین توسط ماشین پردازش شود. قبل از پردازش، یک کار باید روی ماشین بارگذاری شود. این فعالیت بارگذاری یا فعالیت نصب، بوسیله ی ماشین خاص دیگری به نام سرور انجام می پذیرد. بعد از نصب، سرور دوباره در دسترس قرار می گیرد تا فعالیت بارگذاری دیگری انجام دهد. بارگذاری کار باید بلافاصله بعد از پردازش آن انجام پذیرد. در این محیط، ما اینگونه در نظر می گیریم که زمان های نصب نیازمند یک زمان واحد برای هر کاری می باشند. هدف این مقاله یافتن یک زمانبندی امکانپذیر در یک محیط m = 2 ماشینی، و با حداقل زمان کلی تکمیل می باشد، که مربوط به کاهش کار در فرآیند موجود در شبکه می باشد.
بسیاری از نتایج سال های قبلی به مسائل زمانبندی ماشین های موازی با سرور پرداخته اند. کولامانس یک الگوریتم ابتکاری جستجوی پرتو برای محیط استاتیک با دو پردازنده ی موازی و یک سرور منحصربفرد را مطرح می کند که در آن هدف یافتن زمانبندی امکانپذیر است که زمان بیکاری ماشین که حاصل در دسترس نبودن سرور می باشد، را به حداقل می رساند. کراوچنکو و ورنر، هال و همکارانش و براکر و همکارانش نتایج پیچیدگی بسیاری برای این مسائل مطرح کرده اند. گلس و همکارانش مدل های مربوط با ماشین های موازی که برای آن ها کارهایی اختصاص داده شده و نتایج تجزیه و تحلیل الگوریتمی، پیچیدگی و نوآوری را ارائه کرده اند. کراوچنکو و ورنر یک نوآوری برای کاهش مجموع زمان های تکمیل در حالت زمان های واحد طرح ریزی و زمان های دلخواه پردازش پیشنهاد داده اند. با این حال، مسائل بررسی شده در این مقاله ها بطور ضمنی محیط تولید را در نظر می گیرند که در آن سرور می تواند یک اپراتور انسانی، یک روبات یا یک خودروی اتوماتیک راهنمایی شده باشد. در نتیجه فعالیت باردهی معمولا مانند یک عمل چند پردازنده که نیاز به اجرای همزمان ماشین و سرور دارد، در نظر گرفته می شود.
در یک سیستم کامپیوتری، سروری که داده ها را به ماشین می فرستد، سرور شبکه نامیده می شود. طی فعالیت باردهی، نیازی به دسترسی به اجرای ماشین وجود ندارد: آن می تواند بک کار دیگر را پردازش کند. در واقع، ماشین ها دارای یک پردازنده ی ارتباطی می باشند که اجازه می دهد آن ها اطلاعات سرور را در هر زمانی دریافت کنند. در نتیجه، در یک سیستم کامپیوتری، فعالیت باردهی می تواند مانند کاری که تنها نیازمند اجرای سرور می باشد، در نظر گرفته شود.
سیستم کامپیوتری که ما در نظر می گیریم، می تواند بصورت یک استقرار براساس جریان هیبریدی کار یا کارگاه سیار چندپردازنده با یک مشاین در مرحله ی اول، که سرور می باشد و m ماشین موازی در مرحله ی دوم، بدون محدودیت نبود وزن بین دو مرحله در نظر گرفته شود. این مسائل معروف به NP-سخت بودن حتی برای نسخه ی نسخه ی بازدارنده شان می باشند. ویگنیر و همکارانش، و لین و ژنگ یک بررسی به روز بر روی مسائل زمانبندی استقرار براساس جریان کار هیبریدی پیشنهاد داده اند. با این حال، بیشتر مسائل، زمان کل را بعنوان یک معیار در نظر می گیرند. در حالت کاهش مجموع زمان های تکمیل، پیندو نشان می دهد که امکان یافتن یک راه حل بهینه با استفاده از قانون SPT، زمانی که تمامی عملیات یک کار دارای زمان های پردازشی یکسانی دارند، وجود دارد. متأسفانه، این نتیجه دیگر تحت فرضیه ای که ما در نظر می گیریم دیگر صحت ندارد.
در بخش 2، علامت ها معرفی شده و فرمول ریاضی برای مسئله ی کلی داده شده است. در بخش 3، نتایح پیچیدگی و روش های راه حلی برای دو حالت ویژه که در آن ها m = 2 است داده شده است. در بخش 4، ما کاهش چند جمله ای بین مسائل ماشین موازی با سرور و مسائل استقرار براساس جریان کار هیبریدی را ارائه می دهیم. در بخش 5 یک الگوریتم زمانی چند جمله ای برای حل بهینه ی موردی که در آن m = 2 می باشد ارائه شده است. در نهایت، در بخش 6، ما نشان می دهیم که این الگوریتم بهینگی حالت بدون محدودیت نبود وزن را نیز حل می کند.