Skip to main content
SUPERVISOR
Keyarash Bazargan
کیارش بازرگان (استاد راهنما)
 
STUDENT
Milad Ghorbani Moghaddam
میلاد قربانی مقدم

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1387
Improvements in the fabrication technology have resulted in the exponential growth of FPGA size and complexity in recent years. One of the most critical stages in the FPGA CAD flow is the block placement that tries to place the logic elements on the FPGA surface in order to shorten the wire length and the time delay of the circuit. In most designing tools, annealing methods are widely chosen due to superior quality of results and robustness. In terms of desktop computing power, technology improvements have resulted in an increase in the number of parallel cores and consequently, achieving potentially significant speed ups by applying parallelized programming techniques. In recent years, devices such as General Purpose computing on Graphics Processing Units (GPGPU) have offered a promising solution to improve runtime using only commodity hardware. Therefore, changing the serial version of an algorithm to a parallel one, which is able to act on multiple threads, is a suitable way for gaining a high speed-up. In this thesis we studied the VPR tool, which is one of the most popular FPGA placement and routing tools in research and industry. The VPR placement algorithm works based on the simulated annealing method that acts serially; as a result finding a proper parallel method to achieve a good speed-up on multiple threads and maintain exactly the same deterministic result as the serial version seems difficult. On the other hand, if one is to implement a fully parallel implementation using completely independent annealing moves, the speedup would be great but the quality drastically worse than the serial version. Therefore, our goal was to conquer this serial nature using multiple threads concurrently to obtain proper speed-up without a significant reduction in the quality of result. We proposed and analyzed four parallel methods and finally simulated them on a CPU, mimicking to be able to run on SIMD device architecture such as a GPGPU with hundreds of concurrent threads. The parallel moves method, which tries to distribute the swapping function between the threads, can yield good speed-up on a number of limited threads, but the quality might be reduced when we increase the number of the threads. While the upper bound of the speed-up achieved by a method based on the speculative computation, which is dependent on the rate of the move acceptance in the VPR, was limited. The idea was starting a new move, using the predicted result of the current move. The third method, called the average coordination of the blocks, failed due to irresolvable block conflicts. It tried to derive the new placement by gathering the results of all of Key Words Parallelizing, FPGA, Placement, VPR, Simulated Annealing
پیشرفت تکنولوژی، افزایش پیچیدگی در مدارات و نیز افزایش تعداد ترانزیستورهای بکار رفته در تراشه ها و به دنبال آن گسترش سایز FPGA ها را به دنبال داشته است. از طرفی فرآیند طراحی و پیاده سازی مدارات روی FPGA، فرآیندی زمانگیر بوده که با گسترش پیچیدگی مدار و سایز FPGA ها، به صورت نمایی افزایش می یابد. بر این اساس، از آنجایی برنامه های کاربردی که از FPGA استفاده می کنند نیاز به زمان ارائه به بازار محدودی دارند، یکی از مهمترین چالش های پیش روی طراحان، به خصوص در طراحی سیستم های با قابلیت پیکربندی مجدد به طورپویا، کاستن این زمان طراحی، بدون کاهش در کیفیت نهایی راه حل مورد نظر می باشد. یکی از گام های اصلی و بحرانی در فرآیند طراحی FPGA به کمک کامپیوتر (CAD)، گام چینش است که وظیفه مکان دهی بلوک های منطقی را با هدف کاهش طول سیم بکار رفته و تأخیر زمانی مدار، برعهده دارد. در اکثر ابزارهای طراحی، از میان روش هایی که برای چینش ابداع شده، روش های مبتنی بر شبیه سازی گداختگی فلزات که بر اساس سرد شدن تدریجی فلزات بنا نهاده شده، به خاطر ارائه نتایج و راه حل های با کیفیت بالا و قدرت عملیاتی مناسب، به صورت گسترده ای مورد توجه قرار گرفته است که در آن میلیون ها حرکت تصادفی، سعی در تغییر مکان بلوک های منطقی به منظور بهبود پارامترهای کیفی دارند. در سال های اخیر موازی سازی به دلیل تمایل به افزایش نمایی تعداد هسته ها، می تواند راه حل تضمین شده ای برای کنترل افت سرعت طراحی با افزایش نمایی زمان محاسباتی با گسترش سایز FPGA ها محسوب شود. یکی از امکانات موازی سازی که اخیرا رایج شده و مورد استقبال طراحان قرار گرفته، استفاده از قدرت محاسباتی واحدهای پردازشی گرافیکی همه منظوره است که به خاطر داشتن سخت افزار خاص و تعبیه صدها هسته پردازشی بر اساس معماری اتصالی و ارتباطی مناسب، راه حل موازی سازی تضمین شده ای را برای بهبود زمان اجرایی کاربردهای مورد نظر ارائه می کند. در این پایان نامه،VPR که یکی از محبوب ترین ابزارهای چینش و مسیریابی در طراحی FPGA با کمک کامپیوتر محسوب می شود، بحث شده و الگوریتم و کد در دسترس آن به خصوص برای گام چینش مورد مطالعه و ارزیابی قرار گرفته است. از آنجایی که الگوریتم چینش در VPR براساس روش گداختگی شبیه سازی شده عمل می کند و ذات و عملکردی سریال گونه دارد، بدین صورت که عملیات بعدی منوط به استفاده از نتایج عملیات فعلی می باشد، انتخاب روش مناسب برای موازی سازی آن با استفاده از تعداد زیادی ترد، کاری دشوار می باشد و ممکن است راه حل های بدست آمده از لحاظ کیفیت، بسیار دورتر از راه حل نهایی حاصل از اجرای سریال چینش از طریق الگوریتم بکار گرفته شده توسط VPR باشد. بنابراین در این پایان نامه سعی شده با در نظر قرار دادن معماری واحدهای پردازشی گرافیکی همه منظوره، به ارائه روشی مناسب برای غلبه بر ذات سریال گونه چینش VPR و استفاده همزمان از تعداد زیادی ترد برای دستیافتن به افزایش سرعتی درخور، بدون کاهش معنی دار در کیفیت نهایی راه حل پرداخته شود. بدین منظور چهار روش جهت پیاده سازی با استفاده از تنوعی از تعداد تردها مورد تحلیل و شبیه سازی قرار گرفتند. روش حرکات موازی در صورت پیاده سازی مناسب می تواند به ازای تعداد تردهای محدود، افزایش سرعتی تا حدی مناسب را نتیجه دهد. کلمات کلیدی: موازی سازی، FPGA، مکان دهی، VPR، گداختگی شبیه سازی شده

ارتقاء امنیت وب با وف بومی