مقدمه

الگوی von-newman اساس کار رایانهی همه کاره است. هدف این الگو تبدیل دستورات پیچیده به ساده است . گاهگان نتیجه که بعد از اجرای هر دستور موجود در حافظه با گذر از چرخه ی الزامی fetch-decode-execute حاصل می شود در حافظه ذخیره خواهد شد. گذر از مراحل fetch-decode موجب افزایش زمان اجرای دستورات می شود. در این نوع رایانه ها قابلّیّت اجرای انواع متنّوعی از برنامه ها در ازای هزینه در زمان اجرا به دست می آید. با پذیرش این روّیّه اجرای ترتیبی دستورات که ذاتﹰا موازی پذیر نیست اجتنابناپذیر است . زمان اجرا با موازیسازی دستورات کاهش می یابد. در این الگو موازی سازی ، شبیه سازی می شود.
مدار سازگار با برنامه یکی از روش های موازی سازی دستورات است . هدف ، طّرّاحی مدار مجتمع بر اساس ماهّیّت برنامه است. این پیشنهاد باعث بالا رفتن کارایی می شود اما قابلّیّت استفاده ، تنها در مجموعه ای خاص از برنامهها محدود می شود. عدم انعطاف در اجرای متنّوّع برنامه ها مشکل این روش است. تلاش مح ﹼققین برای ایجاد توازن بین انعطاف پذیری و کارایی٧ باعث پی شنهاد تغییر آرایش مدار مجتمع در حین اجرا شد. این معماری قابلّیّت بازآرایی دارد. از این جهت می توان این الگو را معماری بازآراپذیر ٨ نامید. در این الگو ، پیکربندی بدون هزینه زیاد در زمان اجرا برای بالا بردن کارایی یک برنامه خاص تغییر می کند.
این نوع معماری با تکامل تدریجی آرایه ی منطقی برنامه پذیر٩حاصل شد. به آرایه ای با واحدهای منطق و شبکه ارتباطی که تغییر بیت های پیکربندی سبب تغییر پیوندهای شبکه و در نتیجه تغییر پردازش خواهد شد آرایه ی منطقی برنامه پذیر گفته می شود. انتقال بیت های پیکربندی و تغییر آن فرایندی پرهزینه است. در تراشه های پیوندی حاصل از آرایه منطقی برنامهپذیر و ریزپردازندهی کمکی١١ هزینه ی دسترسی به حافظه و بازآرایی شبکه کم شد.
نگاشت درست محاسبات بر روی سخت افزار بازآراپذیر و استفاده از ر یزپردازندهی کمکی سبب کارایی بهتر در اجرای برنامه می شود. تقسیم محاسبات بین ریزپردازنده و بقیه اجزا به صورت دستی یا به کمک ابزارهای خودکار و نیمه خودکار امکان پذیر است. محاسباتی که دارای نظارت پیچیده و ساختار گاهگان ویژه باشند توسط ریزپردازنده انجام می شود. تبدیل محاسبات به رمزعدد قابل اجرا توسط ریزپردازنده و تغییر پیکربندی برای بقّیّه اجزا ، نگاشت گفته میشود. پیکربندی اولّیّه با توّجّه به ا ﹼطلاعاتی خواهد بود که قبل از اجرای محاسبات از روی برنامه حاصل می شود . پیکربندی در زمان اجرا برای مجموعهای متفاوت از محاسبات تغییر می یابد.
معماری von-newman نیازمندی های این الگو را برآورده نمی کند ، از این جهت برای بهبود زمانبندی و روشهای نگاشت احتیاج به ی ک سلسله مفاهی م بلنددید است. الگوی محاسباتی بازآرا یکی از این مفاهیم است که با استفاه از آن م یتوان به بهینه سازی نگاشت با روشهای الگوریتمی دست زد. کارایی این گونه محاسبه در زمینه رمزنگاری ،الگوریتم های وراثتی ،پردازش شکل ، معنافهمی پیام و شبکه عصبی …. اثبات شده.
این نوشتار در سه بخش کلّیّات ، نگاه سختافزاری و نگاه نرم افزاری تهیه شده است. در قسمت کلّیّات به پ یشزمی نههای مورد نیاز می پردازیم و در بخشهای دیگر تنها ارجاعی به آن می شود. در نگاه سخت افزاری به شرح الگو و انواع موجود تور بازآرا میپردازیم و در آخر نیز با چگونگی نگاشت و ملاکهای طّراحی بهینه آشنا م یشویم.
بعضی از مطالعات نیز به عهده ی خواننده گذاشته شده است. امید است مورد قبول مخاطب قرار بگیرد.

توربازآرا Reconfigurable Mesh

توربازآرا Reconfigurable Mesh

فهرست مطالب

چکیده…………………………………………………………………………………………………………………………………..١ مقدمه…………………………………………………………………………………………………………………………………..2

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

فصل اّوّل

به استفاده ی هم زمان چندین CPU برای اجرای یک برنامه ، پردازش موازی گفته می شود. در حالت مطلوب ، باعث اجرای پرسرعت برنامه خواهد شد چرا که ابزار پردازش را چند برابر کرده ایم. ولی با مانعی روبرو هستیم. در اغلب مواقع تقسیم یک برنامه جهت اجرای هم زمان به چندین بخش مجزا و غیر متداخل سخت و دشوار است. (قانون Amdal)
٢.١ برنامه چیست؟
به یک مجموعه ی دارای ترتیب از اعمال که نوسط رایانه قابل پردازش است برنامه گفته می شود. برنامه با جاگرفتن در حافظه برای رایانه قابل دسترسی خواهد بود. در رایانه های کنونی هر دستورالعمل در یک نبض زمانی توسط CPU اجرا می شود. CPU بعد از اجرای یک دستورالعمل بازیابی شده به سراغ دستورالعمل بعدی خواهد رفت. حافظه حاوی گاهگانی است که دستورالعمل بر روی آن پردازش انجام میدهد.۵
همان گونه که از تعریف برمیآید برنامه مانند یک دستور آشپزی است که شامل فهرستی از مواد اولّیّه (متغّیر ) و یک سلسله دستورات٧ است . ترتیب دستورات به رایانه چگونگی رفتار با متغّیّرها را شرح میدهد. هر متغّیّر می تواند عددی ، متنی ی ا شکلی باشد و حاوی گاهگانی است که برنامه و یا کاربر آن را مهیا کرده. می توان گفت دو جز اصلی برنامه مجموعه ی دستورالعملها و گاهگان است.
٣.١ چگونه می توان یک برنامه را افراز کرد؟
مجموعه دستورالعملها و گاهگان با توجه به تعریف برنامه دو عامل اصلی افراز برنامه است.بر همیناساس موازی سازی به دو نوع متفاوت تقسیم می شود : ١- موازیسازی ساختاری ٢-موازی سازی گاهگان
۴.١ موازی سازی ساختاری :
در این نوع موازی سازی برنامه به چندین واحد پردازشی مجزا شکسته می شود. هر کدام از این بخشها با تعداد معین از هم زادهای خود در ارتباط است. این ارتباط یک طرفه است یعنی خروجی هر بخش ، ورودی بخش دیگر خواهد بود. این نظام را می توان به صورت مجموعه ای گره در نظر گرفت که با یک مجرا ارتباطی یک طرفه به هم متصلند. گاهگان یا مجموعه ای از گاهگان از یک سر لوله وارد و از سر دیگر خارج شود. همگردان۵ مثال خوبی از این دسته است. همگردان از یک پوینده ، تجزیه کننده و مولد متن برنامه تشکیل شده که خروجی پوینده ورودی تجزیه کننده و خروجی تجزیه کننده ورودی مولد متن برنامه است و خروجی مولد متن بر روی انباره ی ا ﹼطلاعات نوشته می شود. هر کدام از این بخش ها می تواند بر روی پردازشگرهای متفاوت جاگیرد. خصوصّیّات این نوع مواز یسازی از قرار زیر است:
1. مفهوم ساده ای دارد.
2. واحدهای پردازشی به آسانی قابل شناخت هستند.
3. سربار١٠ کمی دارد.
4. ساختار ارتباطی سادهای دارد.(Forward) مشکلاتی که در این موازی سازی وجود دارد :
1. به عﹼلت تعداد بخشهای پردازشی محدود ، مقی اسپذیری١١ کمی دارد.
2. در این نوع موازی سازی نمی توان از تعدیل به کارگیری منابع١ استفاده کرد.٢
۵.١ موازی سازی گاهگان :
محاسبات با استفاده از تقسیم گاهگان بین چندین پردازشگر انجام می شود. در این شیوه مجموعه ی حجیم گاهگان به تکه های کوچکتر که قابلیت پردازش همزمان را دارند شکسته می شود. با ترکی ب نتایج پردازش ، به یک مجموعه واحد م یرسیم. این نوع موازی سازی در فرآیندهایی که در یک زمان ، حجم زیادی از گاهگان را پردازش می کنند استفاده می شود. این نوع فرآیندها در زمینه پردازش شکل و دستگاههای تراکنش پایگاه گاهگان استفاده دارند. برای توزیع گاهگان می توان از الگوی »مزرعه « استفاده کرد . در این الگو یک کارفرما گاهگان را بین چند کارگر تقسیم می

شکل شماره ی ١ در برنامه نویسی سنتی حجم وسیعی از گاهگان بر روی یک پردازنده پردازش می شود و بقّیّه بیکار  میماند

شکل شماره ی ١ در برنامه نویسی سنتی حجم وسیعی از گاهگان بر روی یک پردازنده پردازش می شود و بقّیّه بیکار میماند

١.١ پردازش موازی چیست؟ ………………………………………………………………………………………………………… ۶
٢.١ برنامه چیست؟ …………………………………………………………………………………………………………………… ۶
٣.١ چگونه میتوان یک برنامه را افراز کرد؟ …………………………………………………………………………………………… ۶
۴.١ موازیسازی ساختاری : …………………………………………………………………………………………………………… ٧
۵.١ موازیسازی گاهگان : ……………………………………………………………………………………………………………… ٨
۶.١ سطوح موازیسازی : ……………………………………………………………………………………………………………… ٩
٧.١ موازیسازی در حد برنامک : …………………………………………………………………………………………………….. ١٠
٨.١ موازیسازی در حد بررشته ……………………………………………………………………………………………………… ١٠
١.٨.١ پردازش…………………………………………………………………………………………………………………………. ١١
٢.٨.١ بررشته…………………………………………………………………………………………………………………………. ١۴
٣.٨.١ بررشته سطح کاربر :…………………………………………………………………………………………………………. ١۵
۴.٨.١ بررشتهی سیستمی :………………………………………………………………………………………………………. ١٧
۵.٨.١ شیوهی ترکیبی: ……………………………………………………………………………………………………………. ١٨
٩.١ موازیسازی دستورالعمل ………………………………………………………………………………………………………. ١٨
١.٩.١ اجرای گوارشی………………………………………………………………………………………………………………. ١٩
٢.٩.١ مانع ساختاری :…………………………………………………………………………………………………………….. ٢۶
٣.٩.١ مانع گاهگان :……………………………………………………………………………………………………………….. ٢٨
۴.٩.١ مانع نظارتی: ………………………………………………………………………………………………………………. ٢٩
۵.٩.١ ابرگوارش: ………………………………………………………………………………………………………………….. ٣١
۶.٩.١ ابرمیزان :……………………………………………………………………………………………………………………. ٣۴
٧.٩.١ درشترج: …………………………………………………………………………………………………………………….. ٣۵

فصل دوم

رایانه های تک پردازنده ی همه کاره از نمونه های شناخته شده این دسته هستند. ابررایانه هایی مثل ۶۶٠٠Control Data Corporation و ٧۶٠٠ نیز در این دسته قرار میگیرد. یکی از نکات مبهم که بین SIMD و SISD وجود دارد ، تقسیم بندی پردازندههای برداری است. بردار و آرایه از انواع گاهگان است که تعداد عناصر آن می تواند زیاد باشد. آرایه را می توان مجموعهای از سطرها و یا ستونهای برداری دانست. از این جهت بر روی پردازنده ی برداری می توان محاسبات مربوط به آرایه را نیز انجام داد. در صورتی که عکس لحظه ای از این پردازن دهها بگیریم و یک نگاه ایستا به آن داشته باشیم ، خواهیم دید که با بخشبندی بردار ، محاسبات بر روی آن ها انجام می شود. با این نگاه ، می توان گفت که این نوع پردازنده ها در دستهی SIMD قرار می گیرد. در یک نگاه پویا به این پردازنده خواهیم دید که تنها یک جریان گاهگان ، به صورت گوارشی پردازش می شود. از این جهت ، این نوع پردازنده ها SISD هستند. پیاده سازی های دیگری نیز از پردازنده ی برداری وجود دارد. یکی از عوامل تقسیم بندی پردازنده ی برداری نوع پیاده سازی آن است. می توان از کنار آن با اغماض گذشت و به صورت کﹼلی در SIMD جا داد.
SIMD ٢.٢.٢
ILLIAC-IV محصول مشترک DARPA, Burroughs Corporation, the University of Illinois Institute for Advanced Computation در سال ١٩٧٢ اّوّلین منظومهای است که بر اساس الگویSIMD ساخته شده است. the British corporation ICL و the Goodyear MPP یک الگوی کﹼلی به اسم Distributed Array Processor (DAP) معّرّفی کردند که بر اساس آن ١CM- و ١MasPar MP- ساخته شد. همه ی این انواع از نحوه ی اجرای SIMD تبعّیّت می کنند. STARAN در سال ١٩٧۴ نیز یکی دیگر از نمونه های SIMD است. پردازش با اجرای یک دستورالعمل بر روی چندین عنصر پردازشی که بر روی مجموعه ای از گاهگان کار می کند به جواب نهایی می رسد. این نوع گاهگان را می توان به عنوان یک آرایه در نظر گرفت. یک واحد مجری دستورالعمل و چندین واحد پردازش گاهگان اجزاء تشکیل دهنده ی این معماری هستند. این مجری در اغلب مواقع ناظر نامیده می شود و در آئین نشان گذاری PMS ، با Kمش ﹼخص می شود. واحد های پردازش گاهگان نیز به صورت معمول عناصر پردازشی نام دارند و در PMS با D برچسب گذاری می شوند. PMS یک نشان گذاری جهت توصیف ساختار فیزیکی رایانه است که در بعضی از کتاب های درسی استفاده می شود. ٧ جزء اصلی در معماری رایانه با توّجّه به کاربردشان قابل شناسایی است:
1. حافظه Memory)) در این واحد امکان ذخیره و بازیابی i واحد ا ﹼطلاعات وجود دارد. ذخیرهسازی و آدرسدهی بیش از i واحد نیز در آن قابل اضافه شدن است. یک حافظه را میتوان به عنوان یک تغییرساز نیز در نظر گرفت که بین چند زیرحافظه در حال حرکت است.
2. اﹼتصال (Link) یک مؤلفه که مسئولّیّت انتقال پیام از مبدأ به مقصد را برعهده دارد. انتقال پیام با تعدادی ثابت سامانه ی ارتباطی که به عنوان عرض اﹼتصال هم قابل بیان است ، انجام می شود. در این انتقال هیچ یک از این i واحد نوشته شده برآن تغییر نمی کند.
3. ناظرK,Control)) به جزء پردازنده که یک عنصر پویا است و وظیفهی خود را در زمان اجرا میفهمد بق ّیّهی عناصر ، حالت ایستا دارند و احتیاج به یک واحد است که وظیفهی جدید را به آنها گوشزد کند. هر واحد ، انجام یک سلسله وظایف گسسته را برعهده دارد که هر کدام از این اعمال معادل با یک وضعّیّت متفاوت برای آن واحد است. تعیین وضعّیّت واحدهای ایستا برعهده ی ناظر است.
4. تغییرسازSwitch) ) هر تغییرساز معادل با یک مجموعه اﹼتصال است که ارتباط آنها را قطع یا وصل می کند. از این جهت وظیفه ی برقراری ارتباط را برعهده دارد.
5. مبّدّلTransducer) ) : این مؤلفه با ارجاع به i واحد ورودی ، یک مفهوم معادل با آن را در خروجی ایجاد میکند (به طور مثال تبدیل یک جریان ترتیبی به موازی) . در خروجی ا ﹼطلاعات ورودی حفظ می شود. ولی این بدین مفهوم نیست که تعداد بیت ها نیز یکسان باشد. 6. اعمال بر روی گاهگانData-operartion) ) یک مؤلفه که یک گاهگان جدید تولید میکند.

بخش a )شبکه ارتباطی مبتنی بر یک گذرگاه (شبکه تک گذره) Single-bus systemبخش b) شبکه ی ارتباطی چندگذره یا میتنی بر چند گذرگاه (multi-bus system) بخش (c شبکه ی  چندمرحلهای multi-stage interconnection network بخش d) شبکه ی ناهمسوساز multi-bus system, در قسمت a,b نمونه های  اولیهی گذرگاه دیده می شود. در هر کدام از خطوط تنها ایجاد

بخش a )شبکه ارتباطی مبتنی بر یک گذرگاه (شبکه تک گذره) Single-bus systemبخش b) شبکه ی ارتباطی چندگذره یا میتنی بر چند گذرگاه (multi-bus system) بخش (c شبکه ی چندمرحلهای multi-stage interconnection network بخش d) شبکه ی ناهمسوساز multi-bus system, در قسمت a,b نمونه های اولیهی گذرگاه دیده می شود. در هر کدام از خطوط تنها ایجاد

١.٢ تقسیم بندیهای معماری ……………………………………………………………………………………………………… ۵٣
٢.٢ طبقهبندی نحوهی اجرا ………………………………………………………………………………………………………. ۵۴
٣.٢ طبقه بندی های دیگر …………………………………………………………………………………………………………. ٧١
۴.٢ رایانه های تورگونه …………………………………………………………………………………………………………….. ٧۶

فصل سوم

سازی شده
1. ۴ ضلعی٢ : کف پوش مورد استفاده ی اغلب پردازندههایی که بر اساس الگوی تور طّرّاحی شدهاند. در مراجع علمی این کفپوش به عنوان تور اصلی معّرفی می شود. به صورت معمول از این کف پوش در تور n در n با شکل مربع استفاده می شود. با تغییر اندازه ی تور و حذف محدودّیّت برابری طول و عرض ، تور مستطیل شکل تولی د می شود. ابعاد ١ در n معادل با تور ١ بعدی است. بعد از این واژه تور معادل با الگوهایی خواهد بود که بر اساس کفپوش ۴ ضلعی طّراحی شدهاند.
2. مثلث٣ : تور ۶ گوش بر اساس این کف پوش طّراحی شده است.
3. ۶ ضلعی : کندوتور ٢ از این نوع کف پوش جهت برقراری ارتباط بین عناصر پردازشی استفادهمی کند. برای اّوّلین بار Ben-Natan و Barak این معماری را معّرفی کردند. درجه ی هر گره برابر با ٣ است. کندوتور به طور بازگشتی تعری ف می شود. کندوتور درجهی ١ یک شش ضلعی است. کندوتور درجه ی ٢ با اضافه کردن ۶ شکل مشابه به اضلاع مجاور حاصل می شود. با اضافه کردن ۶ ضلعی به لایه ی بیرونی کندوتور درجه ی k+١ ، k به وجود م یآید.
٢.٣ طاق بندی :
اﹼتصالات بازگشتی سبب تغییر پا یهای در شکل چی نش نمی شود. به این الگوها طاق بندیهای متفاوت از حالت پایه گفته می شود. طاق بندی در بقّیّه ی انواع تور نیز قابل تعریف است.

طاق بندی های متفاوت قطری از حالت پایه ی یک تور. مرجع شکل  : Optimal Deterministic Sorting

طاق بندی های متفاوت قطری از حالت پایه ی یک تور. مرجع شکل : Optimal Deterministic Sorting

١.٣ کفپوش …………………………………………………………………………………………………………………………. ٧٩
٢.٣ طاقبندی : ……………………………………………………………………………………………………………………… ٨٠
٣.٣ معیار مقایسه …………………………………………………………………………………………………………………. ٨٠
۴.٣ تور ثابت …………………………………………………………………………………………………………………………. ٨٢
۵.٣ تور کاهشی ……………………………………………………………………………………………………………………. ٨۵
١.۵.٣ تور کم پشت………………………………………………………………………………………………………………….. ٨۵
٢.۵.٣ تور پوششی …………………………………………………………………………………………………………………. ٨۶
۶.٣ تور تلفیقی : ……………………………………………………………………………………………………………………. ٨٨
٧.٣ تور پویا : ………………………………………………………………………………………………………………………… ٩١
٨.٣ مسیریابی ……………………………………………………………………………………………………………………… ١٠٠
٩.٣ خلاصه : ……………………………………………………………………………………………………………………….. ١٠١

فصل چهارم

١.۴ معماری بازآراپذیر
دو شکل عمدهی توسعه ی نرم افزار وجود دارد :١- اجرای انواع نرمافزار بر معماری ایستا که اساس پردازش رایانه ی همه کاره است. ٢- پیادهسازی یک معماری ایستا بر اساس یک برنامه خاص جهت کم کردن زمان اجرا.
استفاده ی عمومی از سخت افزار ، اصلی ترین خصوصّیّت رایانه ی همه کاره است. این قابلّیّت با انجام محاسبات بر اساس چرخه ی بازیابی- مهربرداری-اجرا به وجود آمده که سبب طولانی شدن زمان پردازش می شود. قابلّیّت استفادهی عمومی از سختافزار در پیاده سازی دوم به عﹼلت طّرّاحی معماری بر اساس نیاز یک برنامه خاص وجود ندارد. ابزار لازم جهت ترکیب اجرای پرسرعت و استفادهی عمومی از سخت افزار با ایجاد تغییر پیکربندی در آرایه ی منطقی امکانپذیر شد. سرعتبخشی اجرای برنامه با صرف کم ترین زمان بازآرائی و وارد کردن بازآرائی در الگوهای محاسباتی دو هدف عمدهی پیدایش تغییر پیکربندی در آرایه ی منطقی بود. بازآرائی به مفهوم تغییر چینش عناصر پردازشی در شبکه ی ارتباطی است. فواید بازآرایی را می توان در موارد زیر خلاصه کرد :
1. اصلاح در بهره گیری از منابع سخت افزاری در جهت بالا بردن کارایی.
2. تغییر چینش عناصر پردازشی با توّجّه به نیاز الگوریتم.
3. مطرح شدن مطالب جدید در طّراحی الگوریتم مانند مقیاس پذیر بودن آن .
بازآرایی مبحث جدیدی در طّرّاحی الگوریتم نیست. گذرگاه خودکار یکی از اّولین طرحهایی بود که چینش عناصر پردازشی را با توّجّه به شرایط محﹼلی تغییر می داد. Reconfigurable mesh ، PARBS ، Polymorphic Torus۵ از نمونههای بعدی معماری بازآرا هستند. با پیدایش پیاده سازی های فوق ، تحقیقات جهت طّرّاحی انواع الگوریتم بر اساس الگوی بازآرا نیز صورت گرفت.
الگوریتم های متفاوتی بر اساس آن طّراحی و پایه ی حل مسائل بزرگتر شدند. نتیجه ی این تحقیقات سبب معّرّفی الگوی محاسباتی بازآرا به عنوان یک ابزار قوی جهت طّرّاحی انواع الگوریتم شد. هم زمان ، توسعه های جدیدی نیز در فن آوری شکل گرفت. اضافه کردن بازآرایی به آرایه ی منطقی یکی از این موارد بود. تهّیّه ی سری ﹺع نمونه ی سخت افزارﹺی یک دستگاه کاربرد اصلی آرایه ی منطقی است. سرعت بازآرائی موجود در آرایه ی منطقی هم متناسب با این هدف است. الگوی محاسباتی بازآرا امکان تغییر چینش در هر گام محاسباتی را فراهم می آورد. سرعت و انجام بدون سربار بازآرائی از ویژگی های اجتنابناپذیر این توانایی است. به این نوع تغییر چینش ، بازآرایی پویا گفته میشود. شبیه سازیبازآرائی پویا بر روی آرای هی منطقی با سربار و پایین آمدن کارایی همراه و بازآرایی زمان اجرا گفته می شود. بازآرائی زمان اجرا و پویا همان گونه که دیده می شود کام ﹰلا متفاوتند. برای کم کردن سربار شبیه سازی بازآرایی پویا در آرایه ی منطقی می توان از بهبودهای چون بازآرایی جزئی۴ ، تعویض متن پردازشی و خودآرایی استفاده کرد. پردازنده ی بازآرا در بسیاری از حوزهها ، سریع تر و کاراتر نسبت به پردازندههای س ﹼنتی عمل می کند. به همین عﹼلت می تواند به جای معماریهای ایستا به عنوان کمک پردازنده استفاده شود. بازآرائی در طّرّاحی سخت افزار مبتنی بر برنامه نیز با ایجاد توازن بین سرعت و بهره گیری مناسب از منابع سبب افزایش کارایی می شود. پردازش شکل ، رمزنگاری ، معنافهمی پیام از جمله پردازشهایی هستند که از بازآرایی جهت رسیدن به کارایی بهتر استفاده می کنند. طّرّاحی عمومی تر در سخت افزارهای مبتنی بر برنامه یکی دیگر از موضوعات جدیدی بود که با پیدایش بازآرایی پویا مطرح شد. با این کار ، تعداد برنامه هاﹺی قابل اجرا بر سخت افزارهای مبتنی بر برنامه بیشتر می شود و به کاربرد عمومی از این پردازندهها می رسیم. در ادامه به بررسی بازآرایی در الگوهای انتزاعی و موضوعات پیرامونی آن می پردازیم. در مرحله ی اّول به تشریح گذرگاه تفکیک پذیر یک بعدی و با توسعهی آن به تور بازآراپذیر می رسیم.

در قسمت a معماری رایج در تور جهت دار نشان داده شده و در قسمت b یک پردازنده ی نمونه به همراه  بخشبندی های شرح داده شده ترسیم شده.مرجع شکل  : کتاب Dynamic Reconfiguration   با Ramachandran Vaidyanathan, Jerry L. Trahan نوشته ی Architectures and Algorithms  ٨٨ شابک ۴٨۴٢٨-٣٠۶-٠ صفحه ی

در قسمت a معماری رایج در تور جهت دار نشان داده شده و در قسمت b یک پردازنده ی نمونه به همراه بخشبندی های شرح داده شده ترسیم شده.مرجع شکل : کتاب Dynamic Reconfiguration
با Ramachandran Vaidyanathan, Jerry L. Trahan نوشته ی Architectures and Algorithms ٨٨ شابک ۴٨۴٢٨-٣٠۶-٠ صفحه ی

١.۴ معماری بازآراپذیر ……………………………………………………………………………………………………………… ١٠۵
٢.۴ تور بازآرا در یک نگاه …………………………………………………………………………………………………………… ١٠۶
١.٢.۴ گذرگاه تفکیکپذیر ……………………………………………………………………………………………………………. ١٠۶
٢.٢.۴ جمع N عدد…………………………………………………………………………………………………………………… ١٠٧
٣.٢.۴ انجام OR بر روی N بیت ……………………………………………………………………………………………………. ١٠٨
۴.٢.۴ محدوّدّّیت ها…………………………………………………………………………………………………………………. ١١٠
۵.٢.۴ طّرّاحی الگوریتم بر الگوهای بازآراپذیر……………………………………………………………………………………… ١١١
۶.٢.۴ تور بازآراپذیر یک بعدی……………………………………………………………………………………………………….. ١١٣
٧.٢.۴ جمع بندی…………………………………………………………………………………………………………………….. ١١۴
٣.۴ تور بازآراپذیر دو بعدی ………………………………………………………………………………………………………….. ١١۵
۴.۴ الگوریتم های تور بازآراپذیر …………………………………………………………………………………………………….. ١١٩
۵.۴ انواع تور بازآراپذیر ………………………………………………………………………………………………………………. ١٢٠
١.۵.۴ تحدید ساختار اصلی گذرگاه………………………………………………………………………………………………… ١٢١
٢.۵.۴ اندازه ی گاهگان………………………………………………………………………………………………………………. ١٢٣
٣.۵.۴ دسترسی به گذرگاه………………………………………………………………………………………………………….. ١٢۴
۴.۵.۴ جهت دهی پیام ………………………………………………………………………………………………………………. ١٢۶
۵.۵.۴ تعمیم تور بازآراپذیر……………………………………………………………………………………………………………. ١٢٨

فصل پنجم

١.۵ الگوهای نوری ………………………………………………………………………………………………………………….. ١٣١
١.١.۵ تبادل گوار شی……………………………………………………………………………………………………………….. ١٣١
٢.١.۵ آدرس دهی انطباقی ………………………………………………………………………………………………………… ١٣٢
٣.١.۵ تور بازآرای نوری ………………………………………………………………………………………………………………. ١٣۴
۴.١.۵ بردار بازآرای گوارشی………………………………………………………………………………………………………… ١٣۵
۵.١.۵ تور گوارشی بازآرا…………………………………………………………………………………………………………….. ١٣۶
٢.۵ پیادهسازی مبتنی بر آرایه ی منطقی ……………………………………………………………………………………… ١۴٠
١.٢.۵ بازآرائی زمان اجرا ، مهمترین چالش……………………………………………………………………………………… ١۴٢
٢.٢.۵ پیکربندی آرایه ی منطقی …………………………………………………………………………………………………. ١۴۴
٣.٢.۵ شبیه سازی بازآرائی زمان اجرا ………………………………………………………………………………………….. ١۴٧
۴.٢.۵ استفادهی عمومی از بازآرائی…………………………………………………………………………………………… ١۵٢
٣.۵ جمعبندی ……………………………………………………………………………………………………………………… ١۶٠

فصل ششم نتیجه گیری و پیشنهادات

١.۶ قدرت محاسباتی ………………………………………………………………………………………………………………. ١۶۴
٢.۶ تأخیر انتشار پیام ………………………………………………………………………………………………………………. ١۶٧
١.٢.۶ اندازهگیری تأخیر گذرگاه …………………………………………………………………………………………………… ١۶٨
٣.۶ پیادهسازی یک تور ……………………………………………………………………………………………………………. ١٧٠
۴.۶ مقیاسپذیری ……………………………………………………………………………………………………………………. ١٧١
١.۴.۶ مقیاسپذیری عمومی یا شبیهسازی مقیاسپذیری ……………………………………………………………………… ١٧٣
٢.۴.۶ مقیاسپذیری الگوریتم ……………………………………………………………………………………………………….. ١٧٧
۵.۶ طّرّاحی الگوریتمهای بازآرا مبتنی بر آرایه ی منطقی ………………………………………………………………………. ١٨٢
١.۵.۶ طّّراحی سازگار مدار با توّجّه به ورودی ……………………………………………………………………………………. ١٨٢
٢.۵.۶ حساب توزیع شده……………………………………………………………………………………………………………. ١٨۵
٣.۵.۶ بازآرائی قسمتی از مدار و کار کردن بقیه ی اجزاء ………………………………………………………………………. ١٨۵
۶.۶ الگوی توسعه …………………………………………………………………………………………………………………… ١٨٧
١.۶.۶ انواع بازآرایی………………………………………………………………………………………………………………….. ١٨٩
٢.۶.۶ آرایهی منطقی……………………………………………………………………………………………………………….. ١٩٠
٣.۶.۶ معماری های ترکیبی………………………………………………………………………………………………………… ١٩٢
۴.۶.۶ محاسبات بازآراپذیر الگوریتمی ……………………………………………………………………………………………… ١٩٢

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

فهرست جداول

جدول شماره ی ١ سطوح موازی سازی ساختاری ………………………………………………………………………………… ٩ جدول شماره ی٢ سطوح موازی سازی گاهگان ……………………………………………………………………………………. ٩ جدولشمارهی ٣… محک های متفاوت اجرای برنامه های یکسان ………………………………………………………………. ١٧ جدول شماره ی ۴ مقایسه بین انواع بسترهای سخت افرار تجاری …………………………………………………………….. ۵٠ جدول شماره ی ١ طبقه بندی نحوه ی اجرا ………………………………………………………………………………………… ۵۴ جدول شماره ی ٢ مقایسه بین کمک پردازنده های تجاری. ………………………………………………………………………. ۶٧ جدول شماره ی ٣ مقایسه ی انواع کمک پردازنده های تجاری بر مبنای دستورالعمل ………………………………………… ۶٨ جدول شماره ی ١ مقایسه بین انواع مختلف تور …………………………………………………………………………………… ٨١

فهرست شکل ها

سشمارهی ١ اجرای حجم وسیعی از گاهگان بر روی یک پردازنده ………………………………………………………………… ٨ شکل شماره ی ٢ موازی سازی گاهگان. ……………………………………………………………………………………………… ٩ شکل شمارهی ٣ انواع پیاده سازی بررشته …………………………………………………………………………………………. ١۵ شکل شمارهی ۴ نتیجه اجرای حاصل از اعمال گوارش ……………………………………………………………………………. ٢٣ شکل شماره ی۵ نمایش ناسازگاری ………………………………………………………………………………………………….. ٢۴ شکل شماره ی۶ از بین بردن موانع ساختاری ……………………………………………………………………………………….. ٢۵ شکل شماره ی ٧ عﹼلت جداسازی مسیر گاهگان و دستورالعمل …………………………………………………………………. ٢٧ شکل شمارهی ٨ اجرا با طفره ………………………………………………………………………………………………………… ٢٨ شکل شماره ی ٩ نمایش ناسازگاری …………………………………………………………………………………………………. ٢٩ شکل شمارهی ١٠ ایجاد طفره در اجرای دستور شرطی ………………………………………………………………………….. ٣٠ شکل شمارهی ١١ کاهش خسارت پرش ……………………………………………………………………………………………. ٣٠ شکل شمارهی ١٢ طّرّاحی MIPS …………………………………………………………………………………………………….. ٣٢ شکل شماره ی ١٣ ر.یزپردازنده ی ۴٠٠٠MIPS R……………………………………………………………………………………. ٣٣ شکل شماره ی ١۴ ابرمیزان درجه ی ٢ ……………………………………………………………………………………………… ٣٣ شکل شمارهی ١۵ اجرا با هیچ عمل ………………………………………………………………………………………………. ٣۵ شکل شمارهی ١۶ نمایش ناسازگاری ………………………………………………………………………………………………. ٣٧ شکل شمارهی ١٧ انواع توسعه و بهینه سازی بر الگوی گوارشی ………………………………………………………………. ٣٩ شکل شماره ی ١٨ مقایسه بین معماری های نوین ……………………………………………………………………………….. ۴٢ شکل شماره ی ١٩ نمایه ای از طرح افزار مزرعه ……………………………………………………………………………………. ۴۶
شکل شمارهی ٢٠ انواع گوارش ……………………………………………………………………………………………………… ۴٧ شکل شماره ی ٢١ نمایه ای از طرح افزار تقسیم و حل ………………………………………………………………………….. ۴٨
شکل شماره ی ١ تقسیم بندی نحوه ی اجرا ……………………………………………………………………………………… ۵۴ شکل شماره ی ٢ جریان ا ﹼطلاعات و نحوه ی اجرا ……………………………………………………………………………….. ۵٩ شکل شماره ی ٣ انواع پیاده سازی های موجود از الگوی SIMD ………………………………………………………………. ۶٠ شکل شماره ی ۴ دو بخش عمده ی موجود در THINKING MACHINE ……………………………………………………….. ۶٢ شکل شماره ی ۵ یک نمایش ممکن از ١‐CM و ٢‐CM ……………………………………………………………………………. ۶٣ شکل شماره ی ۶ تقسیم واحد پردازش مرکزی CM به ٢ قسمت ……………………………………………………………….. ۶۴ شکل شماره ی ٧ انواع دستوالعمل معمول در SIMD ……………………………………………………………………………… ۶٨ شکل شماره ی ٨ پردازنده ی برداری گوارشی………………………………………………………………………………………..۶٨ شکل شماره ی ٩ یک رایانه ی برداری تجاری………………………………………………………………………………………..۶٨
شکل شماره ی ١٠ شکل یک ILLIAC IV …………………………………………………………………………………………. ٧٠ شکل شماره ی ١١ نمونه های تجاری از دسته بندی نحوه ی اجرا …………………………………………………………….. ٧١ شکل شماره ی ١٢ تعداد پردازنده هایی در اجرای مطلوب ………………………………………………………………………. ٧٢ شکل شماره ی ١٣ شبکه ارتباطی مبتنی بر یک و چند گذرگاه ………………………………………………………………… ٧٣ شکل شماره ی ١۴ طبقه بندی بر اساس چینش …………………………………………………………………………………. ٧۴ شکل شماره ی ١۵ یک تور N×N …………………………………………………………………………………………………….. ٧۶
شکل شماره ی ١ کندوتور …………………………………………………………………………………………………………….. ٧٩ شکل شماره ی ٢ یک تور دوبعدی به همراه ٩ گره و طاق بندی های متفاوت ………………………………………………… ٨٠ شکل شماره ی ٣ الگوی پایه کندوتور درجه ی ٢و٣ و طاق بندی ……………………………………………………………….. ٨٠ شکل شماره ی ۴ اﹼتصال بازگشتی با به هم آمیختگی گره های ………………………………………………………………. ٨٢ شکل شماره ی ۵ یک MSN ۴ در ۴ ………………………………………………………………………………………………… ٨٣ شکل شماره ی ۶ گرفتن پیام از همسایه ها ……………………………………………………………………………………… ٨۴ شکل شماره ی ٧ تور کم پشت ٨ در ٨ …………………………………………………………………………………………….. ٨۵ شکل شماره ی ٨ یک تور پوششی ٢ بعدی ………………………………………………………………………………………. ٨۶ شکل شماره ی ٩ ارتباط در تور ……………………………………………………………………………………………………….. ٨٨ شکل شماره ی ١٠ ایجاد اتصال بازگشتی …………………………………………………………………………………………. ٨٩ شکل شماره ی ١١ طاق بندی های قطری ………………………………………………………………………………………….. ٨٩ شکل شماره ی ١٢ تور با گذرگاه ………………………………………………………………………………………………………. ٩١ شکل شماره ی ١٣ IMMB و GMMB ………………………………………………………………………………………………….. ٩١ شکل شماره ی ١۴ دو تورگونه …………………………………………………………………………………………………………. ٩٣ شکل شماره ی ١۵ بهبود تأخیر در گذرگاه ……………………………………………………………………………………………. ٩۴ شکل شماره ی ١۶ اضافه کردن تغییرساز به گذرگاه ……………………………………………………………………………….. ٩۵ شکل شماره ی ١٧ طرح های متفاوتی از تغییر حالت پردازنده …………………………………………………………………….. ٩٧ شکل شماره ی ١٨ انواع شماره گذاری …………………………………………………………………………………………….. ١٠١ شکل شماره ی ١٩ نمونه ی مجهز به مؤلفه ی قابل پیکربندی ………………………………………………………………….. ١٠١
شکل شماره ی ٢٠ GPU و CUDA …………………………………………………………………………………………………… ١٠٢
شکل شماره ی ١ یک گذرگاه قابل تفکیک ………………………………………………………………………………………….. ١٠٧ شکل شماره ی ٢ جریان گاهگان …………………………………………………………………………………………………….. ١٠٨ شکل شماره ی ٣ به دست آوردن OR در گذرگاه ………………………………………………………………………………….. ١٠٨ شکل شماره ی ۴ شمردن تعداد ١ های موجود در ورودی ……………………………………………………………………….. ١١١ شکل شماره ی ۵ یک تور بازآراپذیر یک بعدی. …………………………………………………………………………………….. ١١٣ شکل شماره ی ۶ یک تور بازآراپذیر دو بعدی ٣×۵ …………………………………………………………………………………. ١١۶ شکل شماره ی ٧ انواع ارتباط مجاز بین درگاه ها در یک تور ٢ بعدی. …………………………………………………………… ١١۶ شکل شماره ی ٨ پیکربندی گذرگاه با انواع ارتباط مجاز …………………………………………………………………………… ١١٧ شکل شماره ی ٩ شکل یک پردازنده به همراه تغییرساز موجود درآن ………………………………………………………….. ١١٧ شکل شماره ی ١٠ انواع ارتباط مجاز بین درگاه ها در یک تور ٢ بعدی …………………………………………………………. ١١٧ شکل شماره ی ١١ نمونه ای از پیکربندی تور پیوندی ……………………………………………………………………………. ١٢٢ شکل شماره ی ١٢ یک تور سطری و ستونی ، یک تور خ ﹼطی و تور درختی …………………………………………………. .١٢٣ شکل شماره ی ١٣ تفاوت پیکربندی در تورهای جهت دار و پایه …………………………………………………………………. ١٢٧ شکل شماره ی ١۴ معماری رایج در تور جهت دار نشان داده شده …………………………………………………………….. ١٢٧ شکل شماره ی ١۵ معماری رایج در چندگذار بازآرا ………………………………………………………………………………… ١٢٨
شکل شماره ی ١ یک تور یک بعدی بازآرا …………………………………………………………………………………………… ١٣٢ شکل شماره ی ٢ ارسال گوارشی در الگوی بازآرا ………………………………………………………………………………… ١٣٣ شکل شماره ی ٣ آدرس دهی انطباقی برای محاسبه ی تعداد یک ها ………………………………………………………… ١٣۴ شکل شماره ی ۴ نحوه ی ایجاد تأخیر و بازآرائی در تور نوری …………………………………………………………………… ١٣٧
شکل شماره ی ۵ یک عنصر پردازشی در تور نوری ………………………………………………………………………………. ١٣٨ شکل شماره ی ۶ انواع ارتباطات مجاز در تور نوری و یک پیکربندی …………………………………………………………….. ١٣٩ شکل شماره ی ٧ ایجاد اﹼتصال U شکل ………………………………………………………………………………………….. ١۴٠ شکل شماره ی ٨ ساختار یک آرایه ی منطقی ………………………………………………………………………………….. ١۴١ شکل شماره ی ٩ ساختار یک سلول از آرایه ی منطقی XILINX VIRTEX …………………………………………………… ١۴۶ شکل شماره ی ١٠ ساختار یک PAM ……………………………………………………………………………………………… ١۴٨ شکل شماره ی ١١ یک گذرگاه غیرهمسوساز به همراه حالات مجاز ………………………………………………………….. ١۴٩ شکل شماره ی ١٢ ساختار یک GARP ……………………………………………………………………………………………. ١۵٠ شکل شماره ی ١٣ در شکل A ساختار الگوی پایه ی HYSAM و نمونه ی مبتنی بر آن ……………………………………… ١۵٢ شکل شماره ی ١۴ ساختار یک RISC ………………………………………………………………………………………………. ١۵۶ شکل شماره ی ١۵ رابطه ی بین مؤلفه های RAGE ………………………………………………………………………………. ١۵۶ شکل شماره ی ١۶ هدررفت فضا در صورت به اشتراک گذاری آرایه …………………………………………………………….. ١۵٩ شکل شماره ی ١٧ فشرده سازی برنامک ها ……………………………………………………………………………………. ١۶٠
شکل شماره ی ١ قدرت محاسباتی انواع تور بازآرا و الگوهای سنتی …………………………………………………………. ١۶۵ شکل شماره ی ٢ مقایسه بین قدرت محاسباتی انواع تور بازآرا و PRAM ……………………………………………………. ١۶۶ شکل شماره ی ٣ شبیه سازی چندگذار بر روی تور سطری و ستونی ………………………………………………………. ١۶٧ شکل شماره ی ۴ تأخیر چرخشی ………………………………………………………………………………………………… ١۶٩ شکل شماره ی ۵ ساختار یک گذرگاه سطری و ستونی ………………………………………………………………………. ١٧١ شکل شماره ی ۶ یک تغییرساز تور خ ﹼطی ………………………………………………………………………………………. ١٧٢
شکل شماره ی ٧ گذرگاه نمونه از تور خ ﹼطی ……………………………………………………………………………………. ١٧٢ شکل شماره ی ٨ نگاشت یک تور بازآرای ٩×۶ بر ٣×٣ …………………………………………………………………………. ١٧۵ شکل شماره ی ٩ یک KCM با ٨ بیت ورودی ……………………………………………………………………………………… ١٨۴ شکل شماره ی ١٠ اعدادی در جدول یابش KCM ای با ۵۶K= ……………………………………………………………….. ١٨۴ شکل شماره ی ١١ همزمانی انجام محاسبات و تغییر پیکربندی ……………………………………………………………… ١٨۶ شکل شماره ی ١٢ روتوش مراحل گوارشی A برای اجرا بر B …………………………………………………………………. ١٨٧ شکل شماره ی ١٣ طرح افزارها از دید بستر اجرا ………………………………………………………………………………. ١٨٨ شکل شماره ی ١۴ تأثیر بازآرائی در زمان اجرا ………………………………………………………………………………….. ١٨٩ شکل شماره ی ١۵ نمایی از آرایه ی منطقی …………………………………………………………………………………… ١٩١ شکل شماره ی ١۶ آرایه ی منطقی تجاری ……………………………………………………………………………………… ١٩٢ شکل شماره ی ١٧ نحوه ی طّرّاحی الگوریتم……………………………………………………………………………………. ١٩٣ شکل شماره ی ١٨ عوامل مؤثر در طّرّاحی الگوریتم …………………………………………………………………………… ١٩٣ شکل شماره ی ١٩ چگونگی نگاشت برنامه بر روی سخت افزار …………………………………………………………….. ١٩۴ شکل شماره ی ٢٠ توسعه الگوریتم های بازآرا مستقل از سخت افزار ……………………………………………………… ١٩۴ شکل شماره ی ٢١ طّرّاحی الگوریتم ها با پیکربندی ایستا …………………………………………………………………… ١٩۵ شکل شماره ی ٢٢ طّرّاحی الگوریتم ها با پیکربندی پویا …………………………………………………………………….. ١٩۵

 

ABSTRACT
Reconfigurable Mesh is a type of Computational Model which is made by interfering of dynamic connection. Primary is Parallel Programming and next mesh definition and afterward how an algorithm is implemented on the RM and what the restricrion is are explained.


قیمت 25 هزار تومان

250,000RIAL – اضافه‌کردن به سبدخرید

خرید فایل pdf به همراه فایلword

قیمت:35هزار تومان

350,000RIAL – اضافه‌کردن به سبدخرید