Parallelization of Simulated Annealing Algorithm for FPGA Placement and Routing
This paper aims to parallelize the simulated annealing algorithm used for the placement of circuit elements in the logic blocks of an FPGA. It intends to introduce the simulated annealing algorithm and the placement problem, analyzes the complexities invo
- PDF / 568,502 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 74 Downloads / 287 Views
Abstract This paper aims to parallelize the simulated annealing algorithm used for the placement of circuit elements in the logic blocks of an FPGA. It intends to introduce the simulated annealing algorithm and the placement problem, analyzes the complexities involved, and justifies the use of simulated annealing as the algorithm for placement ahead of other algorithms. It explains the accuracy of the simulated annealing algorithm using a simple example which, also aims to explore parallelization techniques currently in use, such as parallel moves, area-based partitioning, Markov chains, and suggests possible improvements in the same using a combination of the above, using GPGPUs and investigate further the effects of move biasing. Also, the VPR (versatile placement and routing) CAD tool is introduced and key functions related to placement are explained [1]. The use of GPGPUs to achieve the required parallelism and speedup is discussed, along with the difficulties involved in implementing the same.
Rajesh Eswarawaka (&) P.K. Pagadala B. Eswara Reddy T. Rao Dayananda Sagar College of Engineering, Bangalore, India e-mail: [email protected] URL: http://www.springer.com/aisc P.K. Pagadala e-mail: [email protected] B. Eswara Reddy e-mail: [email protected] T. Rao e-mail: [email protected] Rajesh Eswarawaka P.K. Pagadala B. Eswara Reddy Bharat Institute of Technology, Hyderabad, India Rajesh Eswarawaka P.K. Pagadala B. Eswara Reddy Jawaharlal Nehru Technological University, Hyderabad, Hyderabad, India © Springer Science+Business Media Singapore 2016 M. Pant et al. (eds.), Proceedings of Fifth International Conference on Soft Computing for Problem Solving, Advances in Intelligent Systems and Computing 436, DOI 10.1007/978-981-10-0448-3_84
1001
1002
Rajesh Eswarawaka et al.
Keywords Field-programmable gate array Genetic algorithm Genetic annealing Parallel genetic algorithm Simulated annealing Stochastic tunneling
1 Introduction Placement is the process that maps the circuit components to the logic blocks of the FPGA. The inputs required are the architecture description of the FPGA (number of CLBs, pin positions, etc.) and the net list describing the circuit. The placement process gives the exact blocks which each circuit component will occupy. Figure shows a typical FPGA whose logic blocks will be occupied by various circuit components. The challenge is to obtain an optimal placement where the placement cost function is minimized [2]. The cost function generally includes the total wirelength congestion of wire channel widths. Figure 1 highlights the difference between a random placement of blocks and the final placement after running the algorithm. It is therefore evident that the placement algorithm is critical to reduce the wirelength. Our contribution in this paper is another sequence of slicing lines which is more adequate for FPGA circuits than the traditional methods. This sequence reduces the maximum cut size and the total wirelength of the circuit. The rest o
Data Loading...
