مقدمه

الگوي 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 هزار تومان

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

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