عنوان پایان‌نامه
طراحی و پیاده سازی هسته های سخت افزاری برای الگوریتم های ملهم از طبیعت
- رشته تحصیلی
- مهندسی کامپیوتر-معماری کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه دانشکده برق و کامپیوتر شماره ثبت: E1380;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 37032
- تاریخ دفاع
- ۲۱ بهمن ۱۳۸۶
- دانشجو
- امین فرمهینی فراهانی
- استاد راهنما
- سعید صفری
- چکیده
- الگوریتم های تکاملی الگوریتم های جستجوی عام منظوره ای هستند که برای حل بسیاری از مسائل بهینه سازی مهندسی و پیچیده به کار گرفته شده اند. این الگوریتم ها تکامل طبیعی را بر روی جمعیتی از راه حل های احتمالی همانند سازی می کنند. الگوریتم بهینه سازی دسته ای ذرات یک الگوریتم بهینه سازی جدید با گستره ی رو به رشدی از کاربرد ها می باشد. با این وجود، این الگوریتم عموما یک روش به شدت محاسباتی می باشد که از زمان اجرای بسیار بالا رنج می برد. بنابراین، استفاده از آن در کاربرد های واقعی که رسیدن به یک راه حل مناسب در یک زمان محدود ضروری است مشکل به نظر می رسد. برای بسیاری از کاربرد های واقعی، الگوریتم بهینه سازی دسته ای ذرات مانند دیگر الگوریتم های تکاملی ممکن است برای روز ها در حال اجرا باشد، حتی زمانی که بر روی یک دستگاه با قدرت محاسباتی بالا اجرا شود. بنابراین، عمده ترین مانع استفاده از این الگوریتم زمان اجرای بالای آن می باشد. پیاده سازی های سخت افزاری الگوریتم بهینه سازی دسته ای ذرات برای کم کردن هزینه ی بالای محاسباتی آن در مسائل بهینه سازی پیچیده به خدمت گرفته شده است. کاربرد های پیچیده ی سیستم های هوشمند نیازمند طراحی و توسعه ی معماری های سخت افزاری با کارایی بالا هستند. این پایان نامه، یک معماری سخت افزاری جدید برای الگوریتم بهینه سازی دسته ای ذرات بر اساس مفهوم سیستم بر روی یک تراشه ی برنامه پذیر ارائه می دهد. سیستم بر روی یک تراشه ی برنامه پذیر بستری برای طراحی سیستم های انعطاف پذیر با پیچیدگی بالا ارائه می دهد. در این معماری، یک هسته ی خط لوله برای الگوریتم بهینه سازی دسته ای ذرات طراحی شده است که عملیات محاسباتی الگوریتم را انجام می دهد. پردازنده های نهفته نیز برای ارزیابی مقدار برازندگی به طور موازی به کار گرفته شده اند. با معرفی مفهوم زیرذره، معماری کاملا مقیاس پذیر و مستقل از عرض بیتی ذرات است. بنابراین، مسائل پیچیده و دارای فضای جستجوی بزرگ بدون نیاز به تغییر معماری قابل پیاده سازی است. در یک کار دیگر، توری دو بعدی به عنوان معماری اتصالات برای پیاده سازی موازی سخت افزاری الگوریتم بهینه سازی دسته ای ذرات استفاده شده است که هم کارایی بالا و هم مقیاس پذیری را به همراه دارد. این معماری از واحد های پردازشی تشکیل شده است که توسط کانال های ارتباطی با یکدیگر در ارتباط هستند. در آخر، پیاده سازی سخت افزاری الگوریتم بهینه سازی دسته ای ذرات در کاربرد واقعی آموزش شبکه های عصبی مورد استفاده قرار گرفته است. معماری پیشنهادی از الگوریتم بهینه سازی دسته ای ذرات برای تکامل وزن های شبکه های عصبی و یک روش ابتکاری به نام بخش بندی لایه ها برای پیاده سازی شبکه استفاده می کند. در نتیجه، این معماری برای آموزش و پیاده سازی انواع شبکه های عصبی چند لایه ای رو به جلو قابل پیکربندی مجدد است. معماری برای کاربرد های شبکه های عصبی واقعی با در نظر گرفتن هزینه ی سخت افزاری و سرعت طراحی شده است.
- Abstract
- Evolutionary Algorithms (EAs) are general-purpose search algorithms used to solve difficult engineering optimization problems by simulating natural evolution over populations of candidate solutions. Particle Swarm Optimization (PSO) is a new optimization algorithm with a growing field of applications. Nevertheless, PSO is generally a computationally-intensive method which suffers from long execution time, and hence, makes it very difficult to be used in real-world applications in which reaching a proper solution in a limited time is essential. For many real applications, PSO as other EAs might be running for days, even when it is executed on a high performance workstation. Thus, the major obstacle limiting the use of PSO in real-time applications is its long execution time. Hardware implementation of PSO has been employed to alleviate the high computational cost of complex optimization problems. Complex applications of intelligent systems are computationally intensive which point to design and to develop high performance hardware architectures. This thesis presents a novel hardware framework for PSO based on system-on-a-programmable-chip (SOPC) concept. SOPC offers a platform to effectively design flexible systems with a high degree of complexity. A pipelined PSO core is applied with which the required computational operations of the algorithm are performed. Embedded processors have also been employed to evaluate the fitness in parallel. By introducing the subparticle concept, the system is fully scalable and independent of particle length. Therefore, more complex and larger problems can be addressed without modifying the architecture. As another approach, the two-dimensional mesh is considered as the interconnect architecture for the hardware implementation of parallel PSO which provides either scalability or performance. The architecture is composed of processing elements connected by communication channels. Finally, hardware implementation of PSO has been exploited in the real application of neural network training. The proposed architecture exploits PSO algorithm to evolve network weights as well as a method called layer partitioning to implement neural networks. In the proposed method, a neural network is partitioned into groups of neurons and the groups are sequentially mapped to the available functional units. Consequently, the architecture is reconfigurable for training and implementing different multilayer feedforward neural networks without the need for modifying the architecture. The implementation of the architecture is intended for real-world applications regarding hardware cost and speed.
