اندازه، مصرف انرژی و … نیز وجود دارند. مدیریت بودجه زمانی برای عملیات مختلف طراحی مانند اندازه‌بندی گیت‌ها و کابل‌ها و تهیه‌ی نقشه کتابخانه بکار برده می‌شود. معمولا یک ارتباط و تناسب بین زمان‌بندی و معیارهای دیگر طراحی مانند اندازه، مصرف انرژی، خروجی و… وجود دارد. بنابراین بودجه‌بندی می‌تواند در طول کل جریان طراحی به وسیله کامپیوتر^[۲] استفاده شود تا معیارهای دیگر مانند محیط و مصرف انرژی را ارتقا دهد. هرچه بودجه بیشتر به طراحی اختصاص داده شود، انعطاف پذیری بیشتری برای بهینه‌سازی محدودیت‌های دیگر طراحی اعطا می‌شود. از یک دیدگاه دیگر، حد بالای بیشتر برای هزینه ، بهینه‌سازی را راحت‌تر می‌کند، بنابراین منجر به جمع‌بندی و زمان طراحی سریعتر می‌شود[۸].

( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

هر طراحی توسط یک گراف غیرمدور جهت دار G=(V,E) نشان داده می‌شود که به هر گره، هزینه اختصاص داده شده است. هزینه یا دیرکرد در خروجی با محاسبه‌ی هزینه طولانی‌ترین مسیر در گراف از ورودی به خروجی محاسبه می‌شود. هزینه در طول هر مسیر عبارتست از جمع هزینه‌های اختصاص داده شده به گره‌ها و یا یال‌ها در طول مسیر. در یک محدوده‌ی زمانی معین، بودجه در هر گره میزان تاخیر اضافه‌ای است که هر جزء می‌تواند تحمل کند تا حدی که هیچ محدوده‌ی زمانی زیرپا گذاشته نشود. تعریف مشابهی می‌تواند برای بودجه‌ی یک یال تعریف شود. بودجه‌ی هر گره/یال مرتبط با زمان شناور گره/یال است(حداکثر زمانی که فعالیت‌های واقع بر یک مسیر می‌توانند به تاخیر بیافتد بدون آنکه بر زمان کل مسیر و پروژه تاثیر بگذارند). اگر گره یا یالی با شناور منفی موجود باشد، محدوده‌ی زمانی زیر پا گذاشته شده است. با این حال به دلیل وابستگی موجود بین گره‌ها، شناور زمان کل گره‌ها/یال‌ها برابر با بودجه‌ی کلی که گره/یال‌ها می‌توانند متحمل شوند نیست.
به کارگیری پردازنده‌گرافیکی در محاسبات عمومی جایگاه جدیدی برای کارت‌گرافیک‌های قدرتمند ایجاد کرده است، جایی که از پردازنده‌گرافیکی دیگر برای پردازش محاسبات گرافیکی بازی‌های‌کامپیوتری استفاده نمی‌شود، در عوض در نقش یک پردازنده کمکی، بخشی یا تمامی بار محاسباتی پردازنده‌مرکزی را تقبل کرده و به عملیات پردازش سرعت می‌بخشد. دلیل استفاده از پردازنده‌گرافیکی این است که در پردازش اطلاعات به خاطر ساختار و معماری خود سرعت به مراتب بالاتر از واحد پردازنده مرکزی می باشد. در این پایان نامه بر آنیم تا الگوریتمی برای حل مسئله مدیریت منابع زمانی ارائه داده و پیاده سازی نموده و سپس مجددا آن را به زبان کودا بازنویسی نماییم تا بر روی واحد پردازنده گرافیکی اجرا شود.
در فصل اول پایان نامه، مفاهیم مقدماتی مورد نیاز و متغیر‌های پیش فرض را معرفی می‌نماییم. در فصل دوم مروری بر تحقیقات انجام شده روی این موضوع و موضوع‌های مرتبط که در حل این مسئله استفاده شده‌اند و همچنین کاربردهای آن‌ها انجام می‌دهیم. در فصل سوم روش تحقیق و نحوه پیاده سازی الگوریتم را بیان نموده و در فصل چهارم نتایج حاصل از الگوریتم ارائه می‌گردد. در فصل پنجم نیز به بحث و نتیجه گیری در رابطه با این پایان نامه می‌پردازیم.
ساختار واحد پردازنده گرافیکی
واحد پردازش گرافیکی^[۳] ابزاری اختصاصی برای رندر کردن گرافیکی )به طور طبیعی به نظر رسیدن تصویر) در کامپیوترهای شخصی، ایستگاه‌های کاری یا در کنسول‌های بازی است. این واحد گاهی اوقات واحد پردازندهء بصری^[۴] نیز نامیده می‌شود. ویژگی‌های واحدهای پردازش گرافیک جدید برای پردازش و ارائه دادن کارهای دیداری (گرافیکی)، آن‌ها را بسیار کارآمدتر از واحدهای پردازندهء مرکزی^[۵] جهت پردازش الگوریتم‌های پیچیده کرده است. در واقع واحد پردازش گرافیکی همانند واحد پردازنده مرکزی است ولی وظیفه اصلی آن پردازش اطلاعات مرتبط با تصاویر است. یک واحد پردازش گرافیکی معمولاً بر روی کارت‌های گرافیکی قرار می‌گیرد، اگرچه کارت‌های گرافیکی غیر حرفه‌ای مستقیما بر روی بُرد مادر^[۶] قرار می‌گیرند. واحد پردازش گرافیکی‌های امروز بسیار پیشرفته شده اند و دستورات بسیاری را به صورت موازی پردازش می‌کنند، آن‌ها بسیاری از دستورات را بهتر و سریعتر از پردازنده اصلی کامپیوتری انجام می‌دهند. مقایسه عملکرد پردازنده‌گرافیکی با پردازنده ‌مرکزی به این صورت می‌باشد که، پردازنده‌گرافیکی، نوعی پردازنده‌ موازی است که بر روی کارت گرافیک‌ها قرار دارد.
به کارگیری پردازنده‌گرافیکی در محاسبات عمومی‌جایگاه جدیدی برای کارت‌گرافیک‌های قدرتمند ایجاد کرده است، جایی که از پردازنده‌گرافیکی دیگر برای پردازش محاسبات گرافیکی بازی‌های‌کامپیوتری استفاده نمی‌شود، در عوض در نقش یک پردازنده کمکی، بخشی یا تمامی‌بار محاسباتی پردازنده‌مرکزی را تقبل کرده و به عملیات پردازش سرعت می‌بخشد.
.
مقایسه توانایی‌های واحد پردازش گرافیکی با واحد پردازنده مرکزی
امروزه، واحد های پردازش گرافیکی توان محاسباتی بهتری در مقایسه با پردازنده‌های مرکزی جدید دارند در تصویر ۱-۱ این مقایسه و کاربرها را می توان مشاهده نمود و در انواع کاربردها از آن‌ها استفاده می‌شود.

شکل ‏۱‑۱ مقایسه توان پردازشی خام پردازنده‌گرافیکی با پردازنده‌مرکزی[۲۲]
در این شکل توان پردازشی خام با واحد تعداد محاسبات ممیز شناور در ثانیه سنجیده شده است[۲۲]. خطوط آبی نمایانگرتعداد ممیز شناور در ثانیه توسط واحد پردازنده مرکزی و خطوط سبز توسط واحد پردازش گرافیکی می‌باشد. همانطور که مشاهده می‌کنید توان پردازشی خام پردازنده‌های گرافیکی‌ بسیار بیشتر از سریع‌ترین پردازنده‌های مرکزی بوده و رفته رفته فاصله میان این دو بیشتر می‌شود.
در شکل ۱-۲- پهنای باند تعدادی واحد پردازنده مرکزی و واحد پردازش گرافیکی نشان داده شده است.
شکل ‏۱‑۲مقایسه پهنای باند واحد پردازش گرافیکی با واحد پردازنده مرکزی[۱]
مدل برنامه‌نویسی برنامه‌هایی که برای پردازنده ‌مرکزی نوشته می‌شوند در اصل یک مدل سریال است به این معنی که شبه کد‌های تشکیل دهنده یک برنامه به ترتیب از بالا به پایین خوانده شده و پس از ترجمه، اجرا ‌شده و در آن به ندرت از موازی‌سازی در پردازش داده‌ها استفاده می‌شود. معماری در نظر گرفته شده برای آن نیز بر مبنای این مدل پایه ‌ریزی شده است و قابلیت‌های چندانی برای اجرای چندین دستورالعمل مشابه را به صورت همزمان ندارد. در حالی که مدل برنامه‌نویسی برنامه‌های پردازنده‌گرافیکی که جریان نام دارد، در اصل یک مدل موازی است و قابلیت بهره گیری از تکنیک‌های موازی‌سازی در آن گنجانده شده است. هرچند، پردازنده‌های ‌مرکزی جدید با قابلیت‌هایی نظیر نخ کش بیش از حد^[۷]، اس اس ای^[۸] و بکارگیری‌ معماری‌های چند‌هسته‌ای نوید موازی‌سازی بیشتر را می‌دهند، اما نرخ موازی‌سازی آن ها بسیار کمتر از یک پردازنده‌گرافیکی با ۳۲۰ واحد پردازشی است.
برخلاف واحد پردازش گرافیکی، زیرسیستم حافظه در نظر گرفته شده برای پردازنده‌‌های مرکزی برای کاربردهایی که نیاز به دسترسی به حافظه با تاخیر کم دارند بهینه شده است نه برای برنامه‌هایی که به پهنای باند حافظه وسیعی نیاز دارند، با توجه به مدل برنامه نویسی سریال پردازنده‌مرکزی، بخش‌های یک برنامه باید مرجع‌های حافظه را برای به جریان افتادن قسمت بعدی برنامه، به سرعت برگردانند که لازمه این امر تاخیر کم در دسترسی به حافظه است، به همین دلیل در سلسله مراتب حافظه‌ی پردازنده‌مرکزی چندین لایه حافظه نهان گنجانده شده تا این تاخیر را به حداقل برساند.در مقابل، در مدل برنامه‌نویسی جریانی که برنامه‌های پردازنده‌گرافیکی در چهارچوب‌ آن نوشته می‌شوند، پهنای باند گسترده‌تر برای دسترسی به حافظه اهمیت بیشتری نسبت به تاخیر دسترسی به حافظه دارد، چرا که در این مدل، برنامه‌های پردازنده‌گرافیکی به صورت موازی اجرا شده و وابستگی چندانی میان‌ آن‌ها وجود ندارد. به همین دلیل برنامه‌هایی که نیاز به پهنای ‌باند حافظه‌ زیادی دارند، با پردازنده‌گرافیکی‌ سریعتر‌ از پردازنده‌ مرکزی‌ اجرا می‌شوند.
واحد پردازنده مرکزی یک پردازنده کاملا عمومی‌است که هر نوع عملیات محاسباتی و پردازشی را می‌توان با آن انجام داد اما واحد پردازش گرافیکی یک پردازنده کاملا اختصاصی است که ویژه پردازش گرافیکی طراحی شده است. افزایش روز افزون عملکرد کارت‌های گرافیکی، محققین را به فکر بهره‌گیری از توان پردازشی آن‌ها در کاربردهای غیر‌گرافیکی انداخته است. درهمین راستا شاخه جدیدی در علوم کامپیوتر به نام محاسبات با اهداف همه منظوره روی واحد پردازش گرافیکی ایجاد شده است. هدف فعالان این عرصه بهره‌گیری از کارت گرافیک به عنوان یک کمک پردازنده محاسباتی در برنامه‌های غیرگرافیکی و برنامه‌های عمومی است. پردازنده‌های گرافیکی امروزی از چندین پردازنده با کارایی بالا تشکیل شده‌اند که قادر به محاسبات بسیار سنگین هستند و قابلیت پشتیبانی از رابط‌های برنامه نویسی و زبان‌های استاندارد مانند C را دارند.
نمونه‌ای ‌از کاربرد‌های غیرگرافیکی پردازنده‌های‌گرافیکی
– برنامه‌های پیچیده ضرب ماتریسی و برداری
– روش‌های حل دستگاه معادلات خطی و دستگاه معادلات دیفرانسل
– برنامه‌های شبیه‌سازی ساختار پروتئین
– برنامه‌های مسیریابی شعاع نور
– برنامه‌های شبیه‌سازی فیزیکی مانند شبیه سازی جریان سیال یا تصادم
– برنامه‌های پیمایش و تولید گراف
– برنامه‌های پردازش صوت یا تصویر
– برنامه‌های بینایی ماشین
– برنامه‌های محاسبه تبدیل فوریه سریع
مطابق بررسی‌های انجام شده قدرت محاسباتی یک واحد پردازش گرافیکی تسلا^[۹]، چیزی بالاتر از پانصد برابر قدرت یک پردازنده چهار هسته‌ای ‌اینتل است[۱]. با توجه به مطالب ذکر شده و مفاهیم پایه‌ای موازی‌سازی، واحد پردازش گرافیکی ها را می‌توان پردازنده‌هایی بهینه‌ شده در راستای موازی‌سازی وظایف و داده‌ها دانست. واحد پردازش گرافیکی ها به دلیل معماری خاصی که دارند از چنین توانایی‌هایی برخوردار بوده و معماری آن‌ها برای پیاده‌سازی یک واحد پردازنده مرکزی مناسب نیست. زیرا با توجه به معماری کنونی پلتفرم x86، دستگاه‌ها و تجهیزات مختلفی در سیستم موجود هستند که مدیریت آن‌ها بر عهده پردازنده بوده و برای حفظ ارتباطات مناسب و مدیریت جامع، واحد پردازنده مرکزی ناگزیر از داشتن چنین معماری و به تبع آن پردازش کندتری است[۱].
تکنولوژی کودا^[۱۰]
کودا دارای معماری بر پایه پردازش موازی می‌باشد. کودا نام مجموعه فناوری‌‌های سخت‌افزاری و نرم‌افزاری است که شرکت انویدیا^[۱۱] جهت اجرای محاسبات غیر‌گرافیکی روی پردازنده‌گرافیکی عرضه کرده است. از جمله امکاناتی که کودا در اختیار برنامه‌نویسان قرار داده تا از قابلیت‌های سخت‌افزاری کارت‌های گرافیکی این شرکت در برنامه‌های غیرگرافیکی خود بهره برده و سرعت اجرای الگوریتم‌های پیچیده خود را به کمک قابلیت‌های پردازنده‌گرافیکی افزایش دهند، تکنیک‌ها و ابزارهای برنامه‌نویسی موازی به‌همراه یک کامپایلر است که دستورالعمل‌های پردازنده‌گرافیکی انویدیا را تولید می‌کنند. کلیه کارت‌های گرافیکی سری ۸۰۰۰ به بعد شرکت انویدیا مجهز به این فناوری هستند. برای استفاده از پلتفرم کودا و برنامه‌نویسی برای استفاده از قدرت واحد پردازش گرافیکی، محصولات مختلفی تولید و عرضه شده‌اند که عموما در راستای توسعه کد در محیط‌های برنامه‌نویسی پیشرفته به‌کار می‌روند.
در واقع کودا یک موتور قدرتمند محاسباتی(پردازش) واحد پردازش گرافیکی ‌های کارت گرافیک‌های انویدیا است. فناوری کودا باعث می‌شود واحد پردازش گرافیکی توانایی اجرای چندین پردازش به طور همزمان را داشته باشد در نتیجه راندمان کارت گرافیک را افزایش می‌دهد. دلیل استفاده از واحد پردازش گرافیکی این است که در پردازش اطلاعات به خاطر ساختار و معماری واحد پردازش گرافیکی سرعت به مراتب بالاتر از واحد پردازنده مرکزی می‌باشد. دلیل ساده دیگر اینکه مثلا شما تصور کنید یک واحد پردازنده مرکزی اینتل ci7 2600 3.4 دارید که نهایتا ۴ تا هسته(۸هسته مجازی)دارد، اما یه کارت گرافیک ساده مثل Geforce 550 ti به کمک کودا دارای ۱۹۲ هسته است.
به عبارت دیگر کودا امکان دسترسی به واحد پردازش گرافیکی را برای برنامه نویسان یک برنامه فراهم کرده و بار محاسباتی را از دوش واحد پردازنده مرکزی به کارت گرافیک منتقل می کند. این تکنولوژی همچنین امکان دسترسی برنامه‌نویسان به مجموعه دستورالعمل‌های اختصاصی و اجزای حافظه در پردازش موازی را نیز فراهم می‌کند که این امر توانایی برنامه‎نویس را در کنترل سخت‌افزار بسیار بالا می‌برد. بنابراین با بهره گرفتن از کودا، معماری واحد پردازش گرافیکی ها هم مثل واحد پردازنده مرکزی ها باز می‌شود، گرچه واحد پردازش گرافیکی ها برخلاف واحد پردازنده مرکزی ها دارای یک معماری “بسیار هسته‌ای” موازی هستند که طی آن هسته‌ها توانایی پردازش هزاران نخ را به طور همزمان دارند. بنابراین اگر برنامه‌ای منطبق با این معماری باشد، می‌تواند راندمانی بسیار بالاتر از اجرا بر روی واحد پردازنده مرکزی به ارمغان بیاورد.
در صنایع بازی‌های کامپیوتر، علاوه بر رندر گرافیکی، واحد پردازش گرافیکی در محاسبات فیزیک بازی نیز مورد استفاده قرار می‌گیرد (جلوه‌های فیزیکی مانند دود یا آتش یا …). کودا برای سرعت دادن به برنامه‌های غیر گرافیکی در بیولوژی کامپیوتری، کدگذاری و دیگر رشته‌ها مورد استفاده قرار می‌گیرد.
کودا هم برنامه های کاربردی^[۱۲] سطح پایین و هم سطح بالا را فراهم می‌کند. کودا (کیت توسعه) اولیه در ۱۵ فوریه ۲۰۰۷ بطور عمومی برای ویندوز مایکروسافت و لینوکس عرضه شد. مک بعدها نسخه‌ی ۲ از آن را پشتیبانی کرد که نسخه‌ی بتای آن ۱۴ فوریه ۲۰۰۸ ارائه شد. کودا با تمام واحد پردازش گرافیکی های انویدیا از سری G8x به بعد کار می‌کند که شامل خط تولید‌های جی فرس^[۱۳]، کوادرو ^[۱۴]و تسلا می‌باشد [۱].
ویژگی‌های کودا
استفاده از زبان Cاستاندارد برای نوشتن برنامه‌های پردازش موازی بر روی واحد پردازش گرافیکی ها
کتابخانه‌های عددی استاندارد برای انجام تبدیل فوریه سریع و زیر روال‌های اصلی جبرخطی
درایور کودا اختصاصی برای انتقال سریع داده‌ها بین واحد پردازش گرافیکی و واحد پردازنده مرکزی
درایور کودا اختصاصی برای عمل متقابل با OpenGL و DirectX
پشتیبانی از ویندوز، لینوکس و Mac OS
مزایای کودا
کودا دارای چندین مزیت نسبت به روش‌های معمول پردازش توسط واحد پردازش گرافیکی است که در ادامه ذکر شده‌اند:
خواندن پراکنده: کدها می‌توانند از چندین آدرس مختلف از حافظه خوانده شوند.
دانلود و بازخوانی سریع‌تر به و از واحد پردازش گرافیکی
حافظه اشتراکی: کودا می‌تواند بخشی از حافظه را بین نخ‌ها با سرعت بالا به اشتراک بگذارد که در واقع مثل کشی عمل می‌کند که توسط کاربر کنترل می‌شود و پهنای باند بالاتری ایجاد می‌کند.
پشتیبانی کامل از عملیات صحیح و بیتی
محدودیت‌های کودا
کودا از یک زبان C، بدون توابع بازگشتی و بدون اشاره‌گر استفاده می‌کند و یک پردازش ساده، در بخش‌های پراکنده حافظه پخش می‌شود، برخلاف حالت عادی که از یک بخش یکپارچه از حافظه استفاده می‌گردد.
رندر بافت‌ها^[۱۵] را پشتیبانی نمی‌کند.