Παραλληλοποίηση της τοποθέτησης FPGA με βάση τον Simulated Annealing
Parallelizing FPGA placement based on Simulated Annealing
Field Programmable Gate Arrays (FPGAs) allow fast and cheap implementation of logic circuits and they consist a widely used method for design of electronic circuits for the past few decades. The growing market demands that more logic can potentially be packed into them especially now that the integration scale becomes smaller every few years. This unavoidably lead to the pursuit of a better programming method for the FPGAs as it is evident that the more the logic that is packed into them the more computational time is required in order to compile the hardware description program. The research trend at the moment is searching for a new algorithm that can potentially speed the process of placement of the logic blocks on the FPGA since that part of the program flow can take up to 50% of the total time spent in compilation. Most of the CAD programs responsible for the compilation process, implement a serial version of Simulated Annealing algorithm. The execution time of this algorithm increases exponentially the more logic is required to be implemented on the FPGA which threatens to take away some of the advantages of using an FPGA over an ASIC in the future. Fortunately the evolution of computational systems appears to be systems that rely on multiple processors that allow large throughput and that can work independently. Thus it is crucial that research focuses on parallel processing. Unfortunately, most papers posted on this subject to day, show either underwhelming speedups or sacrifice quality for speed resulting in subpar implementations. This thesis proposes a method of Simulated Annealing parallelization that can be applied to any multicore/manycore system albeit optimized for SIMD systems. Examples are given that use NVidia's GPUs to serve as the means to increase the throughput using CUDA C language extension and the C++ library Thrust. Our goal is to propose an alternative version of the Simulated Annealing algorithm that takes advantage of parallel programming concepts without sacrificing much of the final product quality if any at all.