Implementation of a global router for symmetrical FPGAs based on the dual-affine variant of Karmarkar's interior-point method

FPGAs have been among the fastest growing segments of the semiconductor industry and this growth is expected to continue over the next several years. The complexity of FPGAs makes manual designs time consuming and error prone; design automation tools are essential to the effective use of FPGAs. Routing is one part of the design process of VLSI chips that is computational complex and hence very time consuming.The arrival of the interior-point method proposed by N. Karmarkar was an important event in linear programming and several variants have been developed since then. Recent experiments in a variety of areas report that Karmarkar's algorithm performs asymptotically faster than the traditional simplex method and is competitive with simulated annealing.In this thesis, a global router for symmetrical FPGAs is implemented based on the dual-affine variant of Karmarkar's interior-point method. Current approaches in VLSI global routing, the model of symmetrical FPGAs and the formulation of the global-routing problem as a mixed-integer linear program are reviewed. The objective of the global router is to find a routing that balances the channel-segment densities in the symmetrical FPGA. Specific implementation details are covered in depth and experimental results for samples of random global-routing problems are reported