مدیریت منابع زمانی بر روی گراف مبتنی بر واحد پردازنده گرافیکی

مدیریت منابع زمانی بر روی گراف مبتنی بر واحد پردازنده گرافیکی

تعداد صفحات : 98 با فرمت ورد و قابل ویرایش

چکیده

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

واژه های کلیدی: مدیریت منابع زمانی، مدیریت زمان، مدیریت هزینه، گراف منابع زمانی، کم هزینه ترین بیشینه جریان، مدیریت منابع زمانی بر روی گراف، واحد پردازشگر گرافیکی، بهینه سازی طزاحی.



چکیده1

فصل 1. کلیات تحقیق2

1-1. مقدمه3

1-2. ساختار واحد پردازنده گرافیکی4

1-3. مقایسه توانایی‌های واحد پردازش گرافیکی با واحد پردازنده مرکزی5

1-4. تکنولوژی کودا9

1-5. شناسایی سیستم12

1-6. گراف14

1-6-1.مقدمه14

1-6-2. آشنایی با گراف15

1-6-3. ماتریس وقوع و ماتریس مجاورت15

1-6-4. زیرگراف15

1-6-5. مسیرها16

1-6-6. دورها17

فصل 2. مروری بر تحقیقات انجام شده19

2-1. مقدمه20

2-2. کاربردهای بودجه بندی در یک گراف20

2-3. کم هزینه‌ترین جریان22

2-3-1.تعریفمسئله و شرایط22

2-4. بیشینه جریان23

2-4-1. تاریخچه23

2-4-2. تعریف24

2-4-3. کاربردهای مسئله در دنیای واقعی25

2-4-4. الگوریتم‌های حل مسئله بیشینه جریان28

فصل 3. روش تحقیق31

3-1. مقدمه32

3-2. تحلیل مسئله و مشخص نمودن پیش فرض ها32

3-2-1.تعریف صورت مسئله32

3-2-2.مسئله کوتاه‌ترین مسیر33

3-2-3.بیشینه جریان41

3-3. شرح پیاده سازی44

3-4.کاربردها49

3-4-1. مسیریابی در شبکه49

3-4-2. شبکه زنجیره‌ای ‌تامین50

3-4-3. انتساب تطابق کم هزینه ترین جریان بهینه در ردیابی جریان ذرات50

فصل 4. نتایج54

4-1. اجراهای کم هزینه ترین بیشینه جریان با ورودی‌ها و گراف‌های دارای کمتر از 500 راس55

4-1-1.اجرای اول55

4-1-2.اجرای دوم56

4-1-3.اجرای سوم58

4-1-4.اجرای چهارم60

4-1-5.جرای پنجم62

4-1-6.اجرای ششم62

4-1-7. اجرای هفتم63

4-1-8. اجرای هشتم63

4-1-9. اجرای نهم63

4-1-10. اجرای دهم64

4-1-11. اجرای یازدهم64

4-1-12. اجرای دوازدهم65

4-1-13. اجرای سیزدهم65

4-1-14. اجرای چهاردهم65

4-1-15. اجرای پانزدهم66

4-1-16. اجرای شانزدهم66

4-1-17. اجرای هفدهم67

4-1-18. اجرای هجدهم67

4-1-19. اجرای نوزدهم67

4-1-20. اجرای بیستم68

4-2. نمودارهای نتایج برای گراف های دارای راس های کمتر از 50068

4-2-1.پیچیدگی زمانی الگوریتم68

4-2-2.زمان اجرای الگوریتم در سیستم اول69

4-2-3.زمان اجرای الگوریتم در سیستم دوم71

4-2-4.مقایسه دو سیستم در گراف های کمتر از 500 راس72

4-3. اجراهای کم هزینه ترین بیشینه جریان با ورودی‌ها و گراف‌هایی دارای بیشتر از 1000 راس73

4-3-1.اجرای اول73

4-3-2.اجرای دوم73

4-3-3.اجرای سوم74

4-3-4.اجرای چهارم74

4-3-5.اجرای پنجم75

4-3-6.اجرای ششم75

4-3-7.اجرای هفتم75

4-3-8. اجرای هشتم76

4-3-9. اجرای نهم76

4-3-10. اجرای دهم77

4-3-11. اجرای یازدهم77

4-3-12. اجرای دوازدهم77

4-3-13. اجرای سیزدهم78

4-3-14. اجرای چهاردهم78

4-3-15. اجرای پانزدهم79

4-3-16. اجرای شانزدهم79

4-4. نمودارهای نتایج برای گراف های دارای راس های بیشتر از 100080

4-4-1.زمان اجرای الگوریتم در سیستم اول80

4-4-2.زمان اجرای الگوریتم در سیستم دوم81

4-4-3.مقایسه دو سیستم83

فصل 5. جمع بندی و نتیجه گیری84

5-1. نتیجه85

5-2. نتایج کسب شده از اجرای الگوریتم86

مراجع88

پیوست الف92

پیوست ب94