Create README.md

Coloquinte, a global placement tool for VLSI
============================================

Coloquinte is an analytical VLSI placer. It is based on some of SimPL's ideas, with pulling forces toward a legalized position.

Currently, it supports a bound to bound model for wirelength, and uses a quadripartitioning algorithm to obtain a legalized placement.

Ongoing improvement will focus on the models, with Steiner tree calculation, the legalization algorithms and adaptative pulling forces and placement evolution.
In the long run, I will probably add a global router or a global router interface, and a way to control congestion. In particular, it should make use of the Hurricane database from Paris VI University and its routing tools.

## Algorithm overview

### Analytical placement

The analytical placement in Coloquinte is similar to other tools. It models wires by forces that pull cells together, and the positions are calculated by solving a sparse linear system using Eigen.

The forces are currently calculated with a bound-to-bound model, which models net length by the net bounding box's half perimeter.

### Legalization

The legalizer maps a grid on the circuit and legalizes bins that are overfilled.
To do so, it extends a rectangular box gradually in the best direction regarding the current cells in it.

The next step is a quadripartitioning of the cells in it and of the box - tranformed into an array of bins -, which gives a roughly legalized placement. This placement is then used to guide the analytical solver.