Algorithmic results on physical design problems in VLSI and FPGA

Abstract

Various physical design problems in Very Large Scale Integrated (VLSI) circuits and Field-Programmable Gate Arrays (FPGA) are studied in this thesis. Specifically, we study (1) the area minimization problem in floorplans with L-shaped modules; (2) the channel routing problem in the single layer customization technology; (3) the area routing problem in the channelless single layer customization technology; (4) the design of new routing architectures and algorithms for FPGAs; (5) the congestion-balanced approach for the FPGA placement problem.