مديريت منابع زماني بر روي گراف مبتني بر واحد پردازنده گرافيكي word

 

فهرست مطالب

فهرست مطالب‌و

فهرست جدول‌ها‌ي

فهرست اشکال‌ك

چکيده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

فهرست جدول‌ها

جدول ‏4‑1- هزينه به ازاي عبور هر واحد جريان از يال‌ها در گراف نمونه اول56

جدول ‏4‑2- حداكثر ظرفيت عبور جريان از يال‌ها در گراف نمونه اول56

جدول ‏4‑3- هزينه به ازاي عبور هر واحد جريان از يال‌ها در گراف نمونه دوم57

جدول ‏4‑4- حداكثر ظرفيت عبور جريان از يال‌ها در گراف نمونه دوم57

جدول ‏4‑5- هزينه به ازاي عبور هر واحد جريان از يال‌ها در گراف نمونه سوم58

جدول ‏4‑6- حداكثر ظرفيت عبور جريان از يال‌ها در گراف نمونه سوم59

جدول ‏4‑7- هزينه به ازاي عبور هر واحد جريان از يال‌ها در گراف نمونه چهارم60

جدول ‏4‑8- حداكثر ظرفيت عبور جريان از يال‌ها در گراف نمونه چهارم61

جدول الف‑1 جدول علامت‌ها‌ي اختصاري:93

جدولب‑1- داده‌هاي ورودي آزمايش پنجم95

فهرست اشکال

شکل ‏1‑1 مقايسه توان پردازشي خام پردازنده‌گرافيکي با پردازنده‌مرکزي[22]6

شکل ‏1‑2مقايسه پهناي باند واحد پردازش گرافيکي با واحد پردازنده مركزي[1]7

شکل ‏1‑3 مسئله شناسايي سيستم.13

شکل ‏2‑1 الگوريتم فورد-فالکرسون.29

شکل ‏3‑1 الگوريتم دايکسترا.38

شکل ‏3‑2 الگوريتم ديكسترا38

شکل ‏3‑3 بلمن فورد40

شکل ‏3‑4. الگوريتم ادموندز كارپ43

شکل ‏3‑5. يك گراف نمونه جهت حل مسئله كه هزينه ترين بيشينه جريان44

شکل ‏3‑6. شبه کد الگوريتم پياده سازي47

شکل ‏3‑7. مسير اول با بيشترين جريان48

شکل ‏3‑8. مسير دوم با بيشترين جريان48

شکل ‏3‑9. مسير سوم با بيشترين جريان48

شکل ‏3‑10 تعريف يه گراف براي تخصيص ذرات از سه قاب متوالي[25]53

شکل ‏4‑1نمودار بر اساس تابع پيچيدگي اجرايي69

شکل ‏4‑2نمودار خطي بر اساس مدت زمان اجرا روي سيستم اول(كمتر از 500 راس)69

شکل ‏4‑3نمودار ميله‌اي ‌بر اساس مدت زمان اجرا روي سيستم اول(كمتر از 500 راس)70

شکل ‏4‑4 ميزان تفاوت الگوريتم كودا و C++بر اساس مدت زمان اجرا روي سيستم اول(كمتر از 500 راس)70

شکل ‏4‑5نمودار خطي بر اساس مدت زمان اجرا روي سيستم دوم(كمتر از 500 راس)71

شکل ‏4‑6نمودار ميله‌اي ‌بر اساس مدت زمان اجرا روي سيستم دوم(كمتر از 500 راس)71

شکل ‏4‑7 ميزان تفاوت الگوريتم كودا و C++بر اساس مدت زمان اجرا روي سيستم دوم(كمتر از 500 راس)72

شکل ‏4‑8 مقايسه اختلاف زمان اجرا روي هر دو سيستم(كمتر از 500 گره)72

شکل ‏4‑9نمودار خطي بر اساس مدت زمان اجرا روي سيستم اول(بيشتر از 1000 راس)80

شکل ‏4‑10نمودار ميله‌اي ‌بر اساس مدت زمان اجرا روي سيستم اول(بيشتر از 1000 راس)81

شکل ‏4‑11 ميزان تفاوت الگوريتم كودا و C++بر اساس مدت زمان اجرا روي سيستم اول(بيشتر از 1000 راس)81

شکل ‏4‑12نمودار خطي بر اساس مدت زمان اجرا روي سيستم دوم(بيشتر از 1000 راس)82

شکل ‏4‑13نمودار ميله‌اي ‌بر اساس مدت زمان اجرا روي سيستم دوم(بيشتر از 1000 راس)82

شکل ‏4‑14 ميزان تفاوت الگوريتم كودا و C++بر اساس مدت زمان اجرا روي سيستم دوم(بيشتر از 1000 راس)83

شکل ‏4‑15 مقايسه اختلاف زمان اجرا روي هر دو سيستم(بيشتر از 1000 راس)83

شکل ‏5‑1 .زمان اجراي الگوريتم در C++ و كودا و مغايرت بين آن ها در سيستم A86

شکل ‏5‑2. زمان اجراي الگوريتم در C++ و كودا و مغايرت بين آن ها در سيستم B87

چکيده

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

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

فصل 1. كليات تحقيق

1-1. مقدمه

به دليل پيچيدگي طراحي سيستم و نامعين بودن مسائل زمانبندي و معيارهاي کيفي، اينکه عملکرد را در مراحل اوليه‌ي طراحي كامپيوتري مدارهاي مجتمع[1] بهينه‌سازي کنيم چندان موثر نيست. در عوض بهينه‌سازي بايد معطوف به تضمين صحيح بودن و همگرايي طراحي باشد. براي کم کردن پيچيدگي طراحي، هر طرح بايد به مجموعه‌اي از طراحي‌هاي کوچکتر تقسيم شوند.

محدوديت اصلي در طول بهينه‌سازي طراحي، محدوديت زماني است. همراه با زمان‌بندي، محدوديت‌هاي ديگري نظير اندازه، مصرف انرژي و ... نيز وجود دارند. مديريت بودجه زماني براي عمليات مختلف طراحي مانند اندازه‌بندي گيت‌ها و کابل‌ها و تهيه‌ي نقشه کتابخانه بکار برده مي‌شود. معمولا يک ارتباط و تناسب بين زمان‌بندي و معيارهاي ديگر طراحي مانند اندازه، مصرف انرژي، خروجي و... وجود دارد. بنابراين بودجه‌بندي مي‌تواند در طول کل جريان طراحي به وسيله كامپيوتر[2] استفاده شود تا معيارهاي ديگر مانند محيط و مصرف انرژي را ارتقا دهد. هرچه بودجه بيشتر به طراحي اختصاص داده شود، انعطاف پذيري بيشتري براي بهينه‌سازي محدوديت‌هاي ديگر طراحي اعطا مي‌شود. از يک ديدگاه ديگر، حد بالاي بيشتر براي هزينه ، بهينه‌سازي را راحت‌تر مي‌کند، بنابراين منجر به جمع‌بندي و زمان طراحي سريعتر مي‌شود[8].

هر طراحي توسط يک گراف غيرمدور جهت دار G=(V,E) نشان داده مي‌شود که به هر گره، هزينه اختصاص داده شده است. هزينه يا ديرکرد در خروجي با محاسبه‌ي هزينه طولاني‌ترين مسير در گراف از ورودي به خروجي محاسبه مي‌شود. هزينه در طول هر مسير عبارتست از جمع هزينه‌هاي اختصاص داده شده به گره‌ها و يا يال‌ها در طول مسير. در يک محدوده‌ي زماني معين، بودجه در هر گره ميزان تاخير اضافه‌اي است که هر جزء مي‌تواند تحمل کند تا حدي که هيچ محدوده‌ي زماني زيرپا گذاشته نشود. تعريف مشابهي مي‌تواند براي بودجه‌ي يک يال تعريف شود. بودجه‌ي هر گره/يال مرتبط با زمان شناور گره/يال است(حداكثر زماني كه فعاليت‌هاي واقع بر يك مسير مي‌توانند به تاخیر بيافتد بدون آنكه بر زمان كل مسير و پروژه تاثير بگذارند). اگر گره يا يالي با شناور منفي موجود باشد، محدوده‌ي زماني زير پا گذاشته شده است. با اين حال به دليل وابستگي موجود بين گره‌ها، شناور زمان کل گره‌ها/يال‌ها برابر با بودجه‌ي کلي که گره/يال‌ها مي‌توانند متحمل شوند نيست.

به كارگيري پردازنده‌گرافيكي در محاسبات عمومي جايگاه جديدي براي كارت‌گرافيك‌هاي قدرتمند ايجاد كرده است، جايي كه از پردازنده‌گرافيكي ديگر براي پردازش محاسبات گرافيكي بازي‌هاي‌كامپيوتري استفاده نمي‌شود، در عوض در نقش يك پردازنده كمكي، بخشي يا تمامي بار محاسباتي پردازنده‌مركزي را تقبل كرده و به عمليات پردازش سرعت مي‌بخشد.دليل استفاده از پردازنده‌گرافيكياين است كه در پردازش اطلاعات به خاطر ساختار و معماري خودسرعت به مراتب بالاتر از واحد پردازنده مرکزي مي باشد. در اين پايان نامه بر آنيم تا الگوريتمي براي حل مسئله مديريت منابع زماني ارائه داده و پياده سازي نموده و سپس مجددا آن را به زبان کودا بازنويسي نماييم تا بر روی واحد پردازنده گرافیکی اجرا شود.

در فصل اول پايان نامه، مفاهيم مقدماتي مورد نياز و متغير‌هاي پيش فرض را معرفي مي‌نماييم. در فصل دوم مروري بر تحقيقات انجام شده روي اين موضوع و موضوع‌هاي مرتبط كه در حل اين مسئله استفاده شده‌اند و همچنين كاربردهاي آن‌ها انجام مي‌دهيم. در فصل سوم روش تحقيق و نحوه پياده سازي الگوريتم را بيان نموده و در فصل چهارم نتايج حاصل از الگوريتم ارائه مي‌گردد. در فصل پنجم نيز به بحث و نتيجه گيري در رابطه با اين پايان نامه مي‌پردازيم.