Implementation of Partitioning for Placement of a VLSI Design

Decomposing a system into two or more smaller parts which are relatively independent can be very useful in solving a wide variety of problems. This decomposition is called partitioning. Placement is the process in which layout blocks of a VLSI design are placed at “optimal” locations in order to minimize some cost function. The first stage of a placement algorithm involves the efficient partitioning of the design into many smaller parts.

The goal of this project is to implement two partitioning algorithms and compare their results. The input to the tool that runs the algorithm is a file which contains the gate level description (in Verilog format) of a VLSI design and a LEF file which includes the dimensions of each cell in the cell library.

The design and the LEF data will be read by a tool called Rsyn. Rsyn is an open-source C++ framework for physical synthesis research aiming at shifting the workload from infrastructure (e.g. parsing, data model, visualization) to core algorithm development. The framework integrates parsers for common academic and industrial formats as Bookshelf, LEF/DEF, Verilog, Liberty, SDC and SPEF. A built-in graphics user interface (GUI) is also available.

In this project the student will learn about: VLSI physical design flow basics, industrial design formats (Verilog / LEF / DEF / SPEF), partitioning algorithms. The project will also require C++ programming in Linux environment.

Prerequisites : Graph Algorithms, Background in programming.

Supervisor : Konstantin Moisev (Intel)