| عنوان فارسی مقاله: | یک الگوریتم موازی برای تخصیص بهینه وظیفه در سیستم های توزیع شده |
| عنوان انگلیسی مقاله: | A Parallel Algorithm for Optimal Task Assignment in Distributed Systems |
| دانلود مقاله انگلیسی: | برای دانلود رایگان مقاله انگلیسی با فرمت pdf اینجا کلیک نمائید |
| سال انتشار | 1997 |
| تعداد صفحات مقاله انگلیسی | 7 صفحه |
| تعداد صفحات ترجمه مقاله | 13 صفحه |
| مجله | پیشرفت در محاسبات موازی و شبکه توزیع شده |
| دانشگاه | هونگ کونگ کشور ژاپن |
| کلمات کلیدی | اولین جستجوی برتر، پردازش موازی، تخصیص موازی، نگاشت، سیستم های توزیع شده |
| نشریه IEEE | آی تریپل ای – IEEE |
فهرست مطالب:
چکیده
۱ مقدمه
۲ تعریف مسئله
۳ بررسی اجمالی تکنیک A*
۱ ۳ شیوه ترتیبی
۴ شیوه موازی سازی
۱ ۴ تقسیم بندی اولیه
۲ ۴ موازنه و تعادل بار پویا
الگوریتم OAPS :
۵ نتایج آزمایشی
۱ ۵ تولید بار کاری
۲ ۵ سرعت بخشی با استفاده از الگوریتم موازی
۶ نتایج
بخشی از ترجمه:
چکیده
تخصیص بهینه وظایف به پردازنده ها برای نیل به زمان گردش کار سریع در محیط موازی یا توزیع شده، ضروری می باشد.مسئله تخصیص به جز در معدود موارد خاص کامل می باشد. بنابراین ازفرایندهای اکتشافی برای دستیابی به راه حل های زیربهینه در مدت زمان مطلوب استفاده شده است. اگرچه ازدیاد چنین ابتکاراتی در ادبیات به ثبت رسیده است، اما در این مقاله، هدف ما توسعه تکنیک هایی برای یافتن راه حل های بهینه تحت کمترین فرضیات است. در اینجا اولین الگوریتم بر مبنای جستجو را پیشنهاد می کنیم که راه حلی بهینه برای تخصیص یک گراف وظیفه اختیاری به یک شبکه اختیاری از پردازنده های همگن یا ناهمگن ارائه می دهد. الگوریتم موازی در حال اجرا برروی مسائل متوسط رو به بزرگ را به گونه ای بهینه تخصیص می دهد. به عقیده ما الگوریتم های معرفی شده جدید بوده و یک مسئله حتمی و لازم الاجرا در محاسبه موازی و توزیع شده را حل می کند.
واژگان کلیدی: اولین جستجوی برتر، پردازش موازی، تخصیص موازی، نگاشت، سیستم های توزیع شده
1. مقدمه
با توجه به برنامه موازی مطرح شده با گراف کارهاو تکالیف و شبکه پردازنده های معرفی شده به صورت گراف، مسئله تخصیص وظایف به پردازنده ها معروف به مسئله تخصیص یا مسئله نگاشت می باشد. در این مسئله، تخصیص وظایف به پردازنده ها به صورت استاتیکی یا ایستا انجام شده و هدف اصلی تخصیص مقدار برابری بار به کلیه پردازنده ها و کاهش سربار برهم کنش میان آنها می باشد. اما این مسئله معروف به بوده و به خاطر اهمیت و پیچیدگی اش موضوع توجه بوده است. تلاشهای پژوهش و تحقیقاتی زیادی با استفاده از تکنیک های مختلف در ادبیات گزارش شده است.
مسئله تخصیص، یک مسئله بهینه سازی تلقی می گردد و تابع هزینه بهینه شده به فرضیات مطرح شده در مورد مدل کاربردی و جزئیات سخت افزاری بستگی دارد (توپولوژی سیستم، پهنای باند ارتباطی و احتمال همپوشانی توابع مختلف). سیستم می تواند یک ماشین موازی یا شبکه ای از ایستگاههای وظیفه متصل به هم به صورت یک ماشین موازی مجازی باشد (نظیر مدل محاسبه PVM یا MPI). سیستم ناهمگن (به عبارتی پردازنده ها سرعت های متفاوتی دارند) محدودیت های بیشتری به مسئله تخصیص اضافه می کند. عموماً بدون فرضیات سخت، الگوریتم تخصیص از لحاظ محاسباتی سخت و وقت گیر می شود.
شیوه های بکاررفته برای حل مسئله تخصیص کار برای راه حل های بهینه یا زیربهینه به تکنیک های نظری گراف، آنیلینگ شبیه سازی شده، تکنیک های ژنتیکی، برشمارش و جستجوی فضای راه حل، برنامه نویسی ریاضی و فرایندهای اکتشافی طبقه بندی می شوند. اکثر راه حل های گزارش شده بر اساس اکتشاف عمل کرده و راه حل های بهینه فقط برای موارد محدود یا مسائل کوچک موجود می باشند.
سهم و کمک این مقاله ارائه اولین الگوریتم موازی بر مبنای جستجوی برتر می باشد که راه حل بهینه برای تخصیص یک گراف کار اختیاری به یک شبکه اختیاری از پردازنده های همگن یا ناهمگن ترسیم می کند. الگوریتم اجرا شده بر روی نگاشت های بهینه ای با سرعت خوب ارائه می دهد.
رئوس این مقاله به شرح ذیل می باشد. در بخش بعدی، مسئله تخصیص وظیفه را تعریف می کنیم. در بخش 3، تکنیک جستجوی را بررسی می کنیم که مبنایی برای الگوریتم پیشنهاد شده به شمار می رود. در بخش 4، الگوریتم پیشنهاد شده را معرفی و نمایش می دهیم. در بخش 5 نتایج آزمایش و در بخش 6 با ارائه نتایج کلی، مقاله به پایان می رسد.
بخشی از مقاله انگلیسی:
1 Introduction
Given a parallel program represented by a task graphand a network of processors also represented as a graph,the problem of assigning tasks to processors is known asthe allocation problem or mapping problem [l]. In thisproblem, the assignment of tasks to processors is done in astatic fashion, and the main goal is to assign equal amountof load to all the processors and reduce the overhead ofinteractjon among them. The problem, however, is a wellknown to be NP-hard [5],a nd has been a focus of attentiondue to its importance and complexity. A considerableamount of research effort using a variety of techniques hasbeen reported in the literature.
The assignment problem is an optimization problem,and the cost function to be optimized depends on theassumptions made about the application model andhardware details (system topology, communicationbandwidth, and the possibility of overlapping differentfunctions). The system may be a parallel machine or anetwork of workstations connected as a virtual parallelmachine (such as in the computing model of PVM orMPI). A heterogeneous system (i.e., the processors are of different speeds) adds more constraints to the assignmentproblem. In general, without making strict assumptions,the assignment algorithm can be computationally veryextensive.The approaches used to solve the task assignmentproblem for optimal or suboptimal solutions can beclassified as graph theoretic [ 13 1141, simulated annealing[8], genetic techniques [6], [7], solution space enumerationand search [ 131 [ 151, mathematical programming [ 1 I], andheuristics [3], [9]. Most of the reported solutions are basedon heurtistics, and optimal solutions exist only forrestricted cases or small problem sizes.The contribution of this paper is a best-first searchbasedparallel algorithm that generates optimal solution forassigning an arbitrary task graph to an arbitrary network ofhomogeneous or heterogeneous processors. The algorithmrunning on the Intel Paragon gives optimal mappings witha good speed-up.The rest of this paper is organized as follows. In thenext section, we define the assignment problem. In Section3, we give an overview of the A* search technique whichis the basis of our proposed algorithm. In Section 4, wepresent the proposed algorithm. Section 5 includes theexperimental results, and the last section concludes thepaper. 2 Problem DefinitionA parallel program can be partitioned into a set of mcommunicating tasks represented by an undirected graphGT = (VT, ET) where VT is the set of vertices, { tI, tz,.., tm},and ET is a set of edges labelled by the communicationcosts between the vertices. The interconnection network ofn processors, (p,,p2,..,pn} is represented by an n*n matrixL, where an entry Lv is 1 if the processors i and j areconnected, and 0 otherwise.A task ti from the set VT can be executed on any one ofthe n processors of the system. Each task has an executioncost associated with it on a given processor. The executioncosts of the tasks are given by a matrix X; where Xi, is theexecution cost of task i on processor p . When two tasks tland t, executing on two different processors need toexchange data, a communications cost will be incurred.
| عنوان فارسی مقاله: | یک الگوریتم موازی برای تخصیص بهینه وظیفه در سیستم های توزیع شده |
| عنوان انگلیسی مقاله: | A Parallel Algorithm for Optimal Task Assignment in Distributed Systems |
خرید ترجمه فارسی مقاله با فرمت ورد
خرید نسخه پاورپوینت این مقاله جهت ارائه