اسلایدهای 2/8/87

اسلایدهای امروز 2/8/87
البته در ادامه توسط استاد کاملتر خواهد شد
Lecture6 timingOptimization

تمرين‌ كامپيوتري شماره 2

در اين تمرين طراحي يك مدار ترتيبي به دو شيوه طراحي شماتيكي و طراحي مبتني بر HDL خواسته شده است كه در نهايت هر دو طراحي بر روي FPGA سنتز و پارامترهاي زماني آنها با يكديگر مي‌بايست مقايسه گردد.
ملاحظاتي كه براي كد نوشتن در جلسه قبل مطرح شد رو هم نبايد فراموش كنيم.
دانشجويان كه مايل هستند مي‌توانند با هماهنگي با مسئول آزمايشگاه‌ها طراحي‌ خود را در نهايت بر روي برد FGPA دانشگاه نيز پياده سازي كنند.

متن كامل تمرين كامپيوتري شماره 2

تاريخ تحويل 12/2/87

اسلایدهای این هفته

Lecture 4 Design Flow

Lecture 5 SynOptimization

استفده از CUDD در محيط Visual Studio

راه‌كارهاي متعددي براي اجراي برنامه‌هاي تحت لينوكس در ويندوز وجود داره كه Cygwin تنها يكي از اين راه كار ها هست، براي اجراي CUDD هم در سيستم عامل ويندوز چندين راه‌كار ديگر علاوه بر استفاده از Cygwin وجود دارد كه بهترين اونها نسخه پورت شده CUDD داخل Visual Studio 6 هست.

اين ابزار كه در واقع همون CUDD هست توسط آقاي Alan Mishchenko تبديل به يك پروژه Visual Studio 6 C++ گشته كه به سادگي مي‌توان بدون نياز به محيط لينوكس، از پكيجهاي پياده سازي BDD‌ كه CUDD در اختيار قرار مي‌دهد استفاده كرد.

براي استفاده از اين ابزار كافي است آن را دانلود كرده و مطابق راهنما داخل سايت، تنظيمات لازم را محيط VS اعمال نماييد.

ضمنا ابزار BeDD داراي تابعي است كه به كمك الگوريتم ژنتيك بهترين ترتيب متغييرها را جهت حداقل سازي BDD‌ با دقت قابل تنظيم ، پيدا مي‌كند. از اين رو بدون در نظر گرفتن قابليت‌هاي بالقوه‌اي كه BeDD به واسطه بهره‌گيري از BeanShell داره، ميتواند ROBDD را بهينه نموده و ترسيم نمايد.

با تشكر از دكتر غزنوي جهت معرفي ابزارهاي فوق‌الذكر.

بخشي از توضيحات معرف قابليت هاي اين برنامه پورت شده:

This way of using CUDD on Windows has been extensively tested since June 2000. The Windows projects used about 75% of functionality of CUDD - including the basic manipulation of {A,B,Z}DDs, dynamic variable reordering, printing, visualization of graphs via DOT files, etc. - and no problems have been observed.

ابزار ديگر جهت پياده سازي BDD

با توجه به اين‌كه ابزار CUDD تحت لينوكس و برمبناي خط فرمان هست و براي دانشجوياني كه با محيط لينوكس آشناي ندارند نصب و كار با آن كمي زمان بر مي‌باشد، ابزار مشابه ديگري به نام BeDD وجود دارد كه به صورت مستقل از سيستم عامل بر روي ماشين مجازي جاوا اجرا شده و با واسط گرافيكي قابليت ترسيم گراف‌هاي BDD و اجراي عمليات مختلف بر روي آنها را دارد.

بر اجراي اين برنامه تنها كافي است، بسته 640 كيلو بايتي آن را از اينجا دانلود كرده و پس از نصب ماشين مجازي جاوا بر روي كامپيوتر خود، آن را اجرا كنيد نمونه‌اي از يك BDD ترسيم شده توسط BeDD در تصوير زير نشان داده شده است.

اين ابزار توسط آقاي Mihai Munteanu توسعه داده شده است كه متاسفانه صفحه معرفي آن در اينترنت از بين رفته است اما با كيوورد، BeDD mihai مي‌توان آن صفحه را از داخل Cache گوگل مشاهده كرد. با اين وجود مستندات موجود در بسته 640 كيلوبايتي، جهت معرفي اين ابزار و چگونگي عمكلرد آن، كفايت مي‌كند.

اين ابزار را مي‌توانيد از پوشه دكتر غزنوي در سايت دانشجويان كارشناسي ارشد نيز برداريد. در ادامه بخشي از مستندات ضميمه فايل جهت معرفي اين ابزار آورده شده است:

BeDD is an application for BDD (Binary Decision Diagram) manipulation and circuit synthesis. BeDD was not designed for high performance. There are other faster and more complete BDD manipulation packages. BeDD was designed to be simple and easy to use. It is ideal as an educational tool for learning about BDDs and Java programming language. BeDD is distributed under the GNU General Public License. It means that the source code is freely-distributed and available to the general public.

The core of BeDD is not really original. The BDD representation and algorithms are based on the excellent paper “An Introduction to Binary Decision Diagrams” by Henrik Reif Andersen. At this time not all algorithms described in this paper are implemented.

Main Features of BeDD

-Based on BeanShell scripting language

-Can execute standalone commands or scripts

-Builds ROBDD (Reduced Ordered BDD) based on Boolean binary functions

-Can combine more Boolean functions into a SBDD (Shared BDD)s

-Implements routines for applying operations to BDDs

-BDD size optimization using a genetic algorithm

-The number and size of the BDDs is limited only by the computer capabilities

-Draws BDDs

-Save and load BDDs

-Extensible with export plug-ins for exporting synthesized netlists

مجموعه تمرين‌هاي مبحث BDD

فایل تمرین های کامپیوتری مبحث BDD را میتوانید از اینجا دانلود کنید.
برای انجام این تمرینات به یک BDD Package نیاز داریم که در کلاس ابزار CUDD براي اين كار پيشنهاد شد، این ابزار که تحت سیستم عامل لینوکس نصب می شود را می توانید از اینجا دانلود کنید. همچنين تمرين آخر، تعدادي از Exercise هاي منتخب An Introduction to Binary Decision Diagrams مي‌باشد.
برای نصب این برنامه تحت ویندوز میتوان از Cygwin استفاده کرد.
زمان تحویل تمرینات پنجشنبه 29 فروردین هست...
خبر جدید: بر اساس آخرین صحبتی که با آقای دکتر علیزاده در دانشگاه شریف داشتم، لزومی به استفاده از ابزارهای کامپیوتری برای حل این تمرین نیست و می توان پاسخ ها را به صورت دستی بر روی کاغذ کشید و تحویل داد همچنین از دیگر ابزارهای پیاده سازی BDD علاوه بر CUDD هم می توان برای این کار بهره برد.

اسلايدها و مراجع BDD

اسلايدهاي جلسه سوم در مورد BDD را مي‌توانيد از اينجا دريافت كنيد.

مراجع استفاده شده جهت مطالعه بيشتر در داخل اسلايدها ذكر شده است كه از ميان آنها، مراجع زير را پيدا كردم كه بدون نياز به جستجو مي‌توانيد آنها را دريافت و مطالعه نماييد.

An Introduction to Binary Decision Diagrams

Efficient implementation of a BDD package