Abstract    Placement process is one of the vital stages in physical design. In this stage, modules and elements of circuit are placed in distinct locations according to optimization basis. So that, each placement process tries to influence on one or more optimization factor. In the other hand, it can be told unequivocally that FPGA is one of the most important and applicable devices in our electronic world. So, it is vital to spend time to better learning its structure. VLSI science looks for new techniques for minimizing expense of FPGA in order to gain better performance. Diverse algorithms are used for running FPGA placement procedures. It is known that particle swarm optimization (PSO) is one of the practical evolutionary algorithms for this kind of applications. So this algorithm is used for solving placement problem. In this work, a novel method for optimized FPGA placement has been used. According to this process, the goal is to optimize two objectives defined as wire length and overlap removal functions. Consequently, we are forced to use multi-objective particle swarm optimization (MOPSO) in the algorithm. Structure of MOPSO is in a way that introduces set of answers, we have tried to find a unique answer with minimum overlap. This is worth noting that discrete nature of FPGA blocks forced us to use a discrete version of PSO. In fact, we need a combination of multi-objective PSO and discrete PSO for achieving our goals in optimization process. Tested results on some of FPGA benchmark (MCNC benchmark) are shown in “experimental results” section, compared with popular method “VPR”. These results show that proper selection of FPGA’s size and reasonable number of blocks can get us good response.

Keywords    Discrete MOPSO; Optimization algorithm; FPGA placement; VLSI design; wire length cost function; overlap removal

چکیده    جادهی یکی از مراحل اساسی در طراحی فیزیکی مدارات است. در این مرحله، ماژول ها و اجزای مداری مطابق اصول بهینه سازی در مکان های مشخص قرار می گیرند. بنابراین، هر فرآیند جادهی سعی در بهینه سازی و اثر گذاری بر یک یا چند فاکتور بهینه سازی دارد. از طرفی می توان گفت که FPGA ها بی شک از مهمترین و کاربردی ترین ابزارها در دنیای روز الکترونیک هستند و نیاز به صرف وقت جهت یادگیری و بررسی ساختاری آن ها الزامی می باشد. دانش VLSI به دنبال یافتن راهکارهایی جهت حداقل سازی هزینه های مرتبط با FPGA ها در کنار تضمین عملکرد مناسب آن هاست. الگوریتم های متعددی در حوزه ی جادهی در FPGA ها به کار رفته اند. الگوریتم گروه ذرات (PSO) یکی از الگوریتم های تکاملی کاربردی در این قبیل از مسائل می باشد. بنابراین ما از این الگوریتم در حل مسئله استفاده مي کنیم. در این پروژه، شیوه ی جدیدی جهت بهینه سازی جادهی در FPGA ها ارائه مي‌شود. در طول فرآیند، هدف بهینه سازی دو تابع هدف با عناوین \"طول سیم\" و \"همپوشانی\" مي‌باشد. در نتیجه مجبور به استفاده از الگوریتم چند هدفه ی گروه ذرات (MOPSO) ِمي باشیم. ساختار MOPSO به نحوی است که دارای دسته ای از جواب ها می باشد. و ما از بین این دسته ی جواب های درست، یک جواب با حداقل همپوشانی را گزینش مي کنیم. شایان ذکر است که ماهیت گسسته ی بلوک های FPGA ما را مجبور به استفاده از نسخه ی گسسته ی PSO مي نمايد. در واقع، ما نیاز به ترکیبی از PSO ی چند هدفه و PSO ی گسسته داريم. داده های تست منطبق بر MCNC benchmark در این پژوهش آورده شده اند. که این داده ها با روش معمول تست جادهی (VPR) مقایسه شدند.نتایج نشان می هند که با انتخاب مناسب سایز FPGA پاسخ های منطقی برای جواب مسئله قابل حصول خواهد بود

References      1.     Kebbati, Y., "Modular approach for an asic integration of electrical drive controls", International Journal of Engineering-Transactions B: Applications,  Vol. 24, No. 2, (2011), 107-115. 2.     Xu, M., Gréwal, G. and Areibi, S., "Starplace: A new analytic method for fpga placement", Integration, the VLSI jouRnal,  Vol. 44, No. 3, (2011), 192-204. 3.     Shi, X., "Fpga placement methodologies: A survey", Dept. of Computing Science, University of Alberta, (2009) 1981-1986. 4.     Xu, W., Xu, K. and Xu, X., "A novel placement algorithm for symmetrical fpga", in ASIC, 7th International Conference on, IEEE. (2007), 1281-1284. 5.     Yang, M., Almaini, A., Wang, L. and Wang, P., "Fpga placement using genetic algorithm with simulated annealing", in ASIC, 6th International Conference On, IEEE. Vol. 2, (2005), 806-810. 6.     Gudise, V.G. and Venayagamoorthy, G.K., "Fpga placement and routing using particle swarm optimization", in VLSI, 2004. Proceedings. IEEE Computer society Annual Symposium on, IEEE. (2004), 307-308. 7.     Rout, P.K., Acharya, D. and Panda, G., "Novel pso based fpga placement techniques", in Computer and Communication Technology (ICCCT), International Conference on, IEEE. (2010), 630-634. 8.     Peng, S.-j., Chen, G.-l. and Guo, W.-Z., "A discrete pso for partitioning in vlsi circuit", in Computational Intelligence and Software Engineering, CiSE. International Conference on, IEEE. (2009), 1-4. 9.     El-Abd, M., Hassan, H. and Kamel, M.S., "Discrete and continuous particle swarm optimization for fpga placement", in Evolutionary Computation, CEC'09. IEEE Congress on, (2009), 706-711. 10.   El-Abd, M., Hassan, H., Anis, M., Kamel, M.S. and Elmasry, M., "Discrete cooperative particle swarm optimization for fpga placement", Applied Soft Computing,  Vol. 10, No. 1, (2010), 284-295. 11.   Sarvi, M., Derakhshan, M. and Sedighizadeh, M., "A new intelligent controller for parallel DC/DC converters", International Journal of Engineering-Transactions A: Basics,  Vol. 27, No. 1, (2013), 131-140. 12.   Hsieh, S.-T., Lin, C.-W. and Sun, T.-Y., "Particle swarm optimization for macrocell overlap removal and placement", in Proc. of IEEE Swarm Intelligence Symposium (SIS’05). (2005), 177-180. 13.   Reddy, M.J. and Nagesh Kumar, D., "Multi‐objective particle swarm optimization for generating optimal trade‐offs in reservoir operation", Hydrological Processes,  Vol. 21, No. 21, (2007), 2897-2909. 14.   Premalatha, M.B., Divya, M.D., Abinaiya, M.N. and Monisha, M.S., "Particle swarm optimization based placement and routing of hardware tasks in 2d homogeneous FPGAS", International Journal of Scientific & Engineering Research, Vol., 4, No. 3, (2013), 1-6. 15.   Alvarez-Benitez, J.E., Everson, R.M. and Fieldsend, J.E., "A mopso algorithm based exclusively on pareto dominance concepts", in Evolutionary Multi-Criterion Optimization, Springer. (2005), 459-473. 16.           MCNC benchmark suits, available:   Http://www.Eecg.Toronto. Edu/~vaughn/vpr/vpr",