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

۱۱۵ هزار تومان ۸۵ هزار تومان
افزودن به سبد خرید

جهت خرید و دانلود پاياننامه ارشد نرم افزار منابع زماني گراف مبتني پردازنده گرافيكي روی دکمه افزودن به سبد خرید کلیک و یا با ایمیل زیر در ارتباط باشید

sellthesis@gmail.com


پايان‌نامه کارشناسي ارشد کامپيوتر نرم افزار مديريت منابع زماني بر روي گراف مبتني بر واحد پردازنده گرافيكي


پاياننامه ارشد نرم افزار منابع زماني گراف مبتني پردازنده گرافيكي


چکیده:

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

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


فهرست مطالب

چکيده    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. نمودارهاي نتايج براي گراف هاي داراي راس هاي كمتر از 500    68
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. نمودارهاي نتايج براي گراف هاي داراي راس هاي بيشتر از 1000    80
4-4-1. زمان اجراي الگوريتم در سيستم اول    80
4-4-2. زمان اجراي الگوريتم در سيستم دوم    81
4-4-3. مقايسه دو سيستم    83
فصل 5. جمع بندی و نتیجه گیری    84
5-1. نتيجه    85
5-2. نتايج کسب شده از اجراي الگوريتم    86
مراجع    88
پيوست الف    92
پيوست ب    94


ساختار واحد پردازنده گرافيكي

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

مقايسه توانايي‌هاي واحد پردازش گرافيکي با واحد پردازنده مركزي

امروزه، واحد هاي پردازش گرافيکي توان محاسباتي بهتري در مقايسه با پردازنده‌هاي مرکزي جديد دارند و در انواع کاربردها از آن‌ها استفاده مي‌شود. مدل برنامه‌نويسي برنامه‌هايي که براي پردازنده ‌مرکزي نوشته مي‌شوند در اصل يک مدل سريال است به اين معني که شبه کد‌هاي تشکيل دهنده يک برنامه به ترتيب از بالا به پايين خوانده شده و پس از ترجمه، اجرا ‌شده و در آن به ندرت از موازي‌سازي در پردازش داده‌ها استفاده مي‌شود. معماري در نظر گرفته شده براي آن نيز بر مبناي اين مدل پايه ‌ريزي شده است و قابليت‌هاي چنداني براي اجراي چندين دستورالعمل مشابه را به صورت همزمان ندارد. در حالي که مدل برنامه‌نويسي برنامه‌هاي پردازنده‌گرافيکي که جريان نام دارد، در اصل يک مدل موازي است و قابليت بهره گيري از تکنيک‌هاي موازي‌سازي در آن گنجانده شده است. هرچند، پردازنده‌هاي ‌مرکزي جديد با قابليت‌هايي نظير نخ كش بيش از حد، اس اس اي و بکارگيري‌ معماري‌هاي چند‌هسته‌اي نويد موازي‌سازي بيشتر را مي‌دهند، اما نرخ موازي‌سازي آن ها بسيار کمتر از يک پردازنده‌گرافيکي با 320 واحد پردازشي است.

تكنولوژي کودا

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

آشنايي با گراف

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

كاربردهاي بودجه بندي در يك گراف

بودجه بندي کاربردهاي مختلفي در بهينه‌سازي طراحي دارد، که عبارتند از:
• طراحي محدوده زمان‌بندي: در طول جريان بهينه‌سازي طراحي، بودجه‌ي زماني تحت يک محدوده زماني به هر گره تخصيص داده مي‌شود و بهينه‌سازي بکار برده مي‌شود. اگر محدوديت زمان‌بندي رعايت نشود، بودجه تاخير مجددا تخصيص داده مي‌شود. توزيع بودجه تاخير براي تعيين طول مسير تحت محدوده‌هاي زماني داده شده بکار گرفته مي‌شود.
• جايگذاري بر طبق زمان و برنامه ريزي حداقل: بودجه بندي تاخير در طول جايگذاري و برنامه ريزي حداقل بصورت گسترده توسط محققان مختلف ازجمله آ كاهنگ و همكاران،… و همكاران و… ]23[،]2[،]6[،]5[ مورد مطالعه قرار گرفته است. در جايگذاري بر طبق زمان، هدف بهينه‌سازي تاخير مسيرها با کم کردن تکرارهاست. بودجه‌ي تاخير به يال‌ها در گراف اختصاص داده مي‌شود. محدوده‌هاي تاخير به ازاي هر دور در نظر گرفته مي‌شوند تا توزيع بهتري از بودجه‌هاي تاخير در گراف داشته باشيم. در منابع 24 و 23 جايگذاري و بودجه بندي مجدد ترکيب شده اند. مساله‌ي بهينه‌سازي بودجه در يال‌هاي يک گراف بصورت يک تابع خطي هدف و بصورت مقطعي فرمول سازي مي‌شود و با استفاده از يک الگوريتم ساده سازي گراف اصلاح شده حل مي‌شود.

برنامه‌ريزي خطوط هوايي

يکي از مسائل مهم در صنايع خطوط هوايي، برنامه‌ريزي براي خدمه‌ي پرواز است. مسائل برنامه‌ريزي در خطوط هوايي مي‌تواند به عنوان کاربردي از تعميم مسئله‌‌ي بيشينه‌ي جريان مطرح شود. ورودي مسئله، مجموعه‌اي از پرواز‌ها (F) است که شامل مکان و زمان پرواز‌هاي ورودي و خروجي است. در يک مدل از برنامه‌ريزي، هدف اين است که يک برنامه‌ريزي عملي صورت گيرد به طوري که حد‌اکثر k خدمه فعاليت کنند.

الگوريتم‌ ديكسترا

الگوريتم ديكسترا يكي از الگوريتم‌هاي پيمايش گراف است كه توسط دانشمند هلندي علوم رايانه، اِدْسْخِر دِيكسْترا در سال ۱۹۵۹ ارايه شد. الگوريتم ديكسترا به نام كوتاه‌ترين مسير تك منبع نيز معروف است و مشابه الگوريتم پريم مي‌باشد در صورتيكه گراف يال با وزن منفي داشته باشد، اين الگوريتم درست كار نمي‌كند و مي‌بايست از الگوريتم‌هاي ديگر نظير الگوريتم بلمن-فورد كه پيچيدگي زماني آنها بيشتر است استفاده كنيم. خط مشي الگوريتم ديكسترا، مشابه با روش حريصانه استفاده شده در الگوريتم پريم براي پيدا كردن زير درخت فراگير بهينه است.

مرور

هیچ دیدگاهی برای این محصول نوشته نشده است.