CSE 661 PARALLEL AND VECTOR ARCHITECTURES

Term Project: Assessment of Parallelization Strategies of Metaheuristics for Linear Speed-up while Maintaining Quality

Abstract

Non-deterministic iterative heuristics such as Simulated Evolution (SimE) and Simulated Annealing (SA) are widely utilized to solve a range of hard optimization problems. This interest is attributed to their generality, ease of implementation, and their ability to deliver high quality results. However, depending on the size of the problem, such heuristics may have very large runtime requirements. One practical approach to speeding up their execution is parallelization. In this paper, we present an assessment of various parallelization strategies for both Simulated Evolution and Simulated Annealing as applied to the VLSI Standard Cell Placement problem. Our aim is to evaluate the potential of these strategies for providing near-linear speedups, while sustaining the serial quality. We identify the impact of various issues on the successful parallelization of these algorithms. Issues under consideration are the problem instance being dealt with, characteristics of the heuristic algorithms themselves, and the implementation environment. Based on our findings we also propose some enhancements to some of the strategies.