I am currently writing a tool for electronic design automation. I prototyped it last year on my spare time, and it is now an official research project targeting integrated circuit placement. I called it Coloquinte, hence the name of this blog: its purpose is mostly to present and discuss algorithms.
Electronic design automation (EDA) is a need when integrated circuits feature blocks with millions of logic gates, or when the designs and the processes are as complex as they are now. Therefore, there are many fields in EDA, targeting both circuit synthesis and simulation/verification. The synthesis is the whole process to transform a high-level specification of a circuit into a bare-metal chip.
The high-level specification it receives is usually a dedicated hardware description language (HDL) like Verilog, which provides a description that is still close to the final circuit. Nowadays, this complexity is a burden and higher-level languages are called for: it should is possible to transform C or OpenCL into hardware.
The synthesis flow works as a multipass compiler: it performs optimizations on various representations to output a manufacturable chip. It will transform the specification into boolean logic, place this logic on a chip, then route the wires between them and finally verify that it did not introduce any error. Since an integrated circuit is more constrained than a computer program, these steps often fail and still require a lot of designer input: compiling a circuit is difficult, expensive and time-consuming.
Since the synthesis has such a tremendous influence on cost (area, manufacturing yield and time-to-market) and performance (frequency and power), it has been an area of active research during the past decades. Coloquinte targets part of this synthesis flow, the placement of cells in a block.
Current placement tools are known to be at least 50% away from optimal on some benchmarks. A lot of algorithms have been published but few tools are available in the open: Coloquinte is both a research project and an attempt to have a good placement tool available in a complete toolchain. It is supposed to integrate with the toolchain from Paris VI university, Coriolis, and its database Hurricane.
My next post will be a short presentation of placement algorithms before I can explain the architecture I chosed for Coloquinte and begin posting algorithms and ideas.