علیرضا دهلقی قدیم

گریدهاي محاسباتی به عنوان پاسخی براي پردازش توزیع شده و ¡.به اشتراك گذاري منابع مطرح هستند

از جمله مسائل مهم در این ضمینه بحث زمانبندي در گرید ¡.می باشد

در بعضی ابعاد مانند تخصیص همزمان بسیار زمان بندهاي موجود¡.ناکارمد هستند

با استفاده از مدل هاي اقتصادي می توان زمان بندهاي کاراتري را ¡.ارائه داد

رفتار شرکت کنندگان در گرید را می توان با مفاهیم نظریه ي بازي ¡.مدل کرد

هدف بررسی سیستم هاي زمان بندي در گرید با تمرکز بر روي ¡.مسئله هاي تخصیص همزمان و بالدرنگ است

2

تعریف گرید¡خصوصیات§مقایسه با سایر سیستم هاي توزیع §

شدهشرح مسئله¡زمانبند¡

معرفی زمان بند§انواع زمان بندي§مدل ها زمان بندي§کارایی زمان بندي§معماري زمان بند§

3

زمان بندي غیر اقتصادي ¡زمانبندي بهترین تالش§زمان بندي با کیفیت سرویس §

تضمین شدهمدل هاي اقتصادي مبتنی بر ¡

تئوري بازارمدل حراجی§

حراج ترکیبیاتی▪کارهاي انجام شده¡نتیجه گیري¡

4

ایده ي اصلی

شبکه ي توزیع برق

اهداف

قدرت محاسباتی

پردازش توزیع شده

مقیاس پذیري

نمونه هاي موجود

Globus

Legion

Gridbus

مشکالت موجود

تطبیق با بستر -ناهمگون

تخصیص منابع-کنترل برخط اجرا-تجارت منابع،-کیفیت سرویس-

. کیفیت خدمات ارائه شده غیر بدیهی است

5

.سیستم ها تحت کنترل یک حوزه ي مشخص نباشند

.استفاده از پروتکل هاي استاندارد، باز و چندمنظوره

نظیر به نظیر گرید کالستر خصوصیت

6

شبکهلبه ها سيستم ها قدرتمند رايانه ها معمولي جمعيتمترمکزغير ، گذار متمرکزشاخص

اطالعت غيرمتمرکزسرويس عضويت اکتشاف

چندگانه چندگانه منفرد مالکيتغير متمرکز غير متمرکز متمرکز کاربرمديريتتوزيع شده توزيع شده متمرکز منابعمديريتتوزيع شده توزيع شده متمرکز زمان بند تخصيص

خير خير بله تصوير منفرد از سيستمميليون ها 1000 100 مقياس پذير

متغير )باال(متغيير شدهتضمين ظرفيتباال باال متوسط توان عملياتي

)پايين(باال )پايين(باال )باال(پايين )پهنا بايد(سرعت

پردازشگر،¡حافظه ي اصلی،¡حافظه ي ثانویه،¡پهناي باند شبکه،¡داده،¡منابع نرم افزاري¡دیگر وسیله ي جانبی¡

7

.با ورود وظیفه هاي جدید کار زمان بند شروع می شود¡.زمان بندي را باال به پایین در نظر می گیریم¡هاي گرید از راهنماي عمومی گرید گرفته اطالعات گره¡

).تصمیم گیري غیر توزیع شده(می شوندارائه ي روشی براي تخصیص به صورتی که پارامتر هاي زیر ¡

:بهینه شودمیزان زمان هاي مرگ از دست رفته کمتر شود؛§؛( )زمان انجام کار کمینه شود §( ).ماکزیمم کردن سود جمعی §

8

åi

iV

å -i

ii StartTimeEndTime

تخصیص منبع به یک¡افزایش توان عملیاتی§در مدل هاي اقتصادي، افزایش سود جمعی§افزایش پایداري قیمت ها§تخصیص هم زمان§).که اغلب از چشم طراحان دور می ماند(تخصیص بالدرنگ §قیمت گذاري پویا§بسیاري از سیستم هاي گرید امروزي از صف ها براي زمان بندي ¡

.کارهاي استفاده می کنند

9

دسته بندي بر اساس بهینه سازي¡زمان بندهاي وظیفه محور §زمان بند هاي منبع محور§زمان بندي کار محور §زمان بندي هاي اقتصادي§دسته بندي بر اساس سطحی کارکرد¡

زمان بندهاي سطح پردازش§زمان بند سطح وظیفه§زمان بند سطح منبع §متا زمان بند §

10

مدل منبع¡

مدل کار¡

معیارهاي کارایی¡

سیاست زمان بندي¡

مدل برنامه نویسی¡

11

کارایی پرتو در حالتی به دست می آید که ماکزیمم رفاه ¡. اجتماعی حاصل شود

:تابع سود تولید کننده برحسب نرخ تجارت¡:تابع سود مصرف کننده برحسب نرخ تجارت¡

یک تخصیص در حالت کارایی پرتو است، در صورتی که نتوان ¡سود یک شرکت کننده را بدون زیان به دیگر شرکت کننده

.افزایش داد

.کارایی بازار در نقطه ي پرتو به دست می آید¡12

prUf i -= )()(rCpf i-=

.کارایی پرتو از دیدگاه اقتصادي به تخصیص نگاه می کند¡:دیگر موارد کارایی¡

توان عملیاتی§بازدهی منابع§تخصیص سریع§تخصیص با اولویت§

13

.با گذشت زمان از ارزش منابع براي مصرف کننده کاسته می شود¡نشان دهنده ي تابع تغییر ارزش در TV،در ¡

.طول زمان است

:براي مثال¡

14

)()()( tTVRURV iiii ´=

å=i

iis RVV )(

کنترل کننده)3تخمین زننده ي قیمت و اندازه )2نگاشت گر )1

15

16

17

myopicMin-minMax-minSufferage

HEFT

Hybrid

TANH

¡T :وظیفه¡R :منبع

18

برای وظیفه ی پایانی

برای دیگر وظیفه ھا از پایین به باال

19

20

تقسیم زمان مرگ¡تقسیم بودجه¡

21

22

طبیعت توزیع شده ي منابع در گرید و •حذف نقطه ي کنترل مرکزي؛

محیط رقابتی و تحریک به خرید و •فروش؛

توازن عرضه و تقاضا•ساده سازي درخواست و پاسخ با توجه به •

به خصوص در درخواست (مبناي پولی )همزمان منابع

علت استفاده از مدل هاي اقتصادي

طراحی مکانیزم به صورتی که پارامتر هاي :مفید اجتماعی بهینه شود

بیشینه کردن بهره وري؛•استفاده ي حداکثري از منابع؛•باال بردن توان عملیاتی گرید؛•ماکزیمم کردن سودجمعی؛•تشویق شرکت کنندگان به رفتار •

.صادقانه

طراحی مکانیزم و اهداف آن

)یکنواخت یا متغیر(بازار کاال ¡مدل قیمت ارسال شده¡مدل چانه زنی¡مدل قراردادي و مناقصه اي¡مدل حراجی¡مدل تخصیص نسبی منابع مبتنی بر مزایده¡سهم داران–ائتالف –مدل انجمنی ¡مدل انحصاري و چند انحصاره¡

23

تشویق در جهت به اشتراك گذاري¡توازن عرضه و تقاضا متوازن¡اولویت دهی¡.پایه ي اقتصادي براي مقایسه ي نیاز هاي مشترك کاربران¡رفتار یکسان با تمام منابع¡تقسیم فرآیند تصمیم گیري بین تمام شرکت کنندگان¡

24

25

مذاکره ي خرید چند به چندمذاکره ي خرید یک به چند

حراج انگلیسی•حراج هلندي•حراجی بسته ي اول •

قیمتحراجی ویکري•

زمان گسسته•پیوسته زمان•پیوندي•

حراجی دوطرفهحراجی یک طرفه

!تخصیص همزمان؟

26

m: تعداد کاالها n: تعداد شرکت کننده ها

:تابع ارزشدهی هر بازیکن

مقدمات

iv

پیچیدگی محاسباتی-)NP -کامل(

پیچیدگی نمایش و ارتباط-

رفتار هاي استراتژیک-

مشکالت

استفاده از هیوریستیک-

حل در موارد خاص-

حل با استفاده از تقریب-

مشکالت

تخصیص دسته اي کاال به هر شرکت کننده مثل به .صورتی که و در عین حال رفاه اجتماعی ماکزیمم شود },,,{هدف 21 nSSS K

{}=Ç ji SS

:نگاه نسبی روي مسئله ي تخصیص همزمان¡§SCDA:هدف اصلی بر تخصیص همزمان¡

کارهاي عملی§(AR)رزرو پیشرفته ▪P. Gradwell(زمان بندي ترکیبی منابع به صورت توزیع شده ▪ and J.

Padget,2005(.Li, et al)شماي بازار ترکیبیاتی دو طرفه براي تخصیص منابع در گرید ▪

2008)

کارهاي تئوري روي حراج هاي ترکیباتی§(Maximal In Range)حداکثر در محدوده ▪

27

28

29

30

¡ I. Foster and C. Kesselman, "The Grid: blueprint for a future computinginfrastructure." San Francisco, CA: morgan Kaufmann publishers USA, 1999, p.677.

¡ P. Gradwell and J. Padget, "Distributed combinatorial resource scheduling." FirstInternational Workshop on Smart Grid Technologies., 2005, pp. 17–32.

¡ S. Dobzinski and N. Nisan, "Mechanisms for multi-unit auctions," in Proceedingsof the 8th ACM conference on Electronic commerce, San Diego, California, USA,2007, pp. 346-35 1.

¡ P. Fibich, et al., "Model of grid scheduling problem," in Exploring Planning andScheduling for Web Services, Grid and Autonomic Computing, Menlo Park,California, USA, 2005, pp. 17–24.

¡ A. Mu'Alem and N. Nisan, "Truthful approximation mechanisms for restrictedcombinatorial auctions," Games and Economic Behavior, vol. 64, pp. 612-631,2008.

¡ M. Parvania and M. Fotuhi-Firuzabad, "Demand Response Scheduling byStochastic SCUC," Smart Grid, IEEE Transactions on, vol. 1, pp. 89-98, 2010.

31

¡ A. Pugliese, et al., "Modeling and supporting grid scheduling," Journal of GridComputing, vol. 6, pp. 195-213, 2008.

¡ R .Buyya, et al., "Economic models for resource management and scheduling ingrid computing," Concurrency and computation: practice and experience, vol. 14,pp. 1507-1542, 2002.

¡ R. Buyya, et al., "The grid economy," Proceedings of the IEEE, vol. 93, pp. 698-714, 2005

¡ Z. Tan and J. Gurd, "Market-based grid resource allocation using a stablecontinuous double auction," DOCTOR OF PHILOSOPHY, UNIVERSITY OFMANCHESTER, IEEE, 2007.

¡ I. Foster and C. Kesselman, The grid: blueprint for a new computinginfrastructure: Morgan Kaufmann, 2004

¡ J. Yu, et al., "Workflow scheduling algorithms for grid computing," Metaheuristicsfor Scheduling in Distributed Computing Environments, pp. 173-214, 2008

32