Abstract:

Moore�s law, first presented in 1965, states that the number of transistors in a digital integrated circuit grows exponentially by doubling every two years. This trend has held true for more than half a century. Today�s integrated circuit can contain more than a billion transistors, making the design of these circuits a very complex process.

The focus of this talk is the physical design stage of the design of the integrated circuits. The Physical Design is the stage where the physical shape of a circuit is determined. Circuit layout is an important part of physical design in which the position of all the components of the circuit (placement step) and the paths of the interconnecting wires (routing step) are determined. In this talk first an overview of the placement and routing steps and their mathematical formulations are given. The complexity of these algorithms and the problems associated with the existing algorithms are considered. Then, multilevel algorithms designed to tackle the increasing sizes are discussed.