Overview of Optimization Methods in VLSI Design

VLSI design is the backbone of all tech breakthroughs happening around the world. Chip development has followed Moore’s law. Through which chips have been able to pack more transistors in smaller area with less power consumption. Floor planning, a critical step in chip development which distributes design block on silicon, becomes more and more complex as additional transistors are placed with advance process node technologies. This requires a lot of optimizations to minimize the design block footprint, reduce interconnect delay between the same and leave least amount of dead space. This chapter talks about such optimization techniques including Genetic algorithms (GA) and Honey Badger algorithm (HBA). Main objective of this chapter is to compare the performance of various Nature-inspired methods in discrete optimization problems. A floorplan can be discretely viewed as sliceable and non-sliceable floorplan. A sliceable floorplan is achieved by recursively halving the floorplan area until each non-overlapping partition reaches a set defined size of a design block. Some design blocks don’t allow a allow a floorplan to become sliceable. Such non-sliceable floorplan optimization is done with a Genetic algorithm called Lion optimization algorithm (LOA). LOA uses power B* tree crossover operator to solve a multi objective problem. It is inspired by the behaviour of a Lion and Lioness. Both Lion and Lioness from a pride come together and protect the young offsprings as well each other from predators. Implementation of LOA with B*tree crossover operator proves to be an efficient and effective technique for VLSI floorplan optimization. In this chapter, application of Simulated Annealing (SA) on combinatorial optimization is also discussed. This study aims to minimize dead space on the floorplan. SA is like the annealing process used in metallurgy. SA starts with highest degree of randomness (like high temperature in Annealing) as a function while exploring the solution space. We reduce the randomness by coming near to a solution (like low temperatures in Annealing). A solution which decreases randomness of placement explores all possible states. Solution acceptance criteria is defined depending on the initial function value. The acceptance probability distribution decides whether to accept the new solution or to bounce out of it. To overcome an all-in exploration approach in traditional SA algorithm, authors have developed Simulated Spheroidizing Annealing Algorithm (SSAA). In this method, the time for local search is extended at any given incremental solution is increased. Furthermore, to improve the method of finding neighbourhood solutions, additional perturbation pattern approach is used until it reaches the desired iteration. This approach is termed as Improved Simulated Spheroidizing Annealing Algorithm (ISSAA). The results shows that the proposed ISSAA outperformed SSAA for larger circuits. However, perform is comparable while solving for larger die size or dimensions. In addition, by using parallel computation method an attempt is made to reduce the computational time, i.e., CPU time. Particle Swarm Optimization (PSO) based VLSI floorplan optimization is also discussed. A design block or Swarm in this algorithm, is placed in best location possible and its connecting blocks follow this swarm to accommodate itself in the best location in the same neighbourhood. PSO is weak with discrete exploration space and planar systems. Other algorithms can always be appended to get an efficient solution. Moving along, GA is population-based optimization technique. Population is updated after certain amount of time; a set of solutions can be procured with every update for GA to better search in each space. GA uses defined probability rules to fine tune the exploration. Fundamental remains same, converge population to local optimal solution. These principles of mutation and crossover are adopted and incorporated in PSO to achieve better diversity. Experimental results prove the proposed algorithm can achieve optimal solution for complex module placements and can be applied to multi-objective problems in floorplan. It also addresses problems in VLSI floor planning such as fixed-outline floorplan and Thermal-Aware Non-slicing floorplan. Additionally, the use of mathematics-based metaheuristics and hybrid machine learning clustering for discrete optimization problems in VLSI is also explored.