Novel Approach for Solving Multi-objective Optimization Problems: A Case of VLSI Thermal Placement

Abstract

We often confront with optimization problems that require optimizing multiple objectives. Such multi-objective optimization problems are often non-linear in nature and are hard to solve. In such situations conventionally heuristic methods are used to arrive at some reasonably good solutions. VLSI standard cell placement problems traditionally have to handle multiple objectives such as area, delay, thermal distribution and so on, to arrive at a reliable design. One of the key concerns in this area is to simultaneously (i) optimize the thermal distribution of the heat dissipated by the logic gates on the chip and (ii) minimize the total wirelength required to interconnect these gates. This in turn helps in reducing the chances of occurrence of hot spots on the chip, on-chip delay and the total chip area. Optimizing these objectives individually is known to be NP-hard and hence simultaneous optimization of the two objectives is a challenging problem. In this work, we have also proposed a game-theoretic formulation to the problem and developed some novel heuristic algorithms for solving this problem. The proposed algorithms have been implemented, and the experimental results are quite encouraging