Most of the design flow of an integrated circuit is automated, starting from the specifications using Hardware Description Languages until reaching the physical layout. The flow goes through through different synthesis and analysis phases: behavioral synthesis, logic synthesis, floorplanning, placement, routing, timing analysis, formal verification, etc. This course will review the most important algorithmic aspects in design automation of electronic circuits. A significant part of the course will be devoted to algorithms for minimization of Boolean functions and representation with logic gates. The algorithms for physical design (floorplanning, placement and routing) will be mostly based on solving problems with graph models.
Course Syllabus (summary). Circuit design flow: from specification to layout. Minimization of logic circuits: algorithms for two-level and multi-level logic synthesis.
Technology mapping. Algorithms for physical synthesis: floorplanning, placement and routing. Formal verification: equivalence and model checking.
Person in charge
Jordi Cortadella Fortuny (
Technical Competences of each Specialization
CEE3.1 - Capability to identify computational barriers and to analyze the complexity of computational problems in different areas of science and technology as well as to represent high complexity problems in mathematical structures which can be treated effectively with algorithmic schemes.
CEE3.2 - Capability to use a wide and varied spectrum of algorithmic resources to solve high difficulty algorithmic problems.
CEE3.3 - Capability to understand the computational requirements of problems from non-informatics disciplines and to make significant contributions in multidisciplinary teams that use computing.
Generic Technical Competences
CG1 - Capability to apply the scientific method to study and analyse of phenomena and systems in any area of Computer Science, and in the conception, design and implementation of innovative and original solutions.
CG3 - Capacity for mathematical modeling, calculation and experimental designing in technology and companies engineering centers, particularly in research and innovation in all areas of Computer Science.
CTR6 - Capacity for critical, logical and mathematical reasoning. Capability to solve problems in their area of study. Capacity for abstraction: the capability to create and use models that reflect real situations. Capability to design and implement simple experiments, and analyze and interpret their results. Capacity for analysis, synthesis and evaluation.
CB6 - Ability to apply the acquired knowledge and capacity for solving problems in new or unknown environments within broader (or multidisciplinary) contexts related to their area of study.
CB8 - Capability to communicate their conclusions, and the knowledge and rationale underpinning these, to both skilled and unskilled public in a clear and unambiguous way.
CB9 - Possession of the learning skills that enable the students to continue studying in a way that will be mainly self-directed or autonomous.
Learning of techniques for formal verification of circuits
Learning of techniques for circuit floorplanning and placement
Learning of routing algorithms
The theoretical content of the course is taught in the theory lectures. During the practical classes, practical examples are solved and different types of problems are proposed. These problems will have to be solved during the time of autonomous learning. An algorithmic project will also be proposed during the course. Students will have to solve and implement it during their time of autonomous learning.
Grade = 40% FW + 30% FT + 20% EX + 10% SP
FW = Final Work (graded from 0 to 10) in which each participant is required to present a research paper or section of a book (previously assigned by the lecturer). The presentation consists of:
* 3-5 minutes background on the topic of the paper, a motivation.
* 1 minute overview of the key ideas of the paper.
* 15 minutes presentation with most important details.
* 5 minutes demo of a program that implements the ideas introduced in the paper.
FT = Final test graded from (0 to 10) including all the contents ofcourse.
EX = Exercises assigned to the student and solved during the Autonomous Learning time
SP = Summaries and participation (graded from 0 to 10) in which each participant is required to deliver a summary (1 page extent) of each others presentation and to participate (with questions and comments).