ET4054 Methods and algorithms for system design

Topics: System design by logic synthesis, optimization, and combinatorial algorithms
System design is the central topic of this course. We move beyond the methods developed in circuit design (although we shall have interest in those) and consider situations in which the functional behavior of a system is the first object under consideration. There will be an introduction to modeling methods that can be used in the context of system design, followed by a discussion of the main issues that are to be considered when one wants to design a system that satisfies a number of relevant performance indices. We start out with a classical situation in which topics such as space, time and processing cycle are the objects to be optimized on. This will lead to a quest for a variety of optimization methods depending on what kind of information can be assumed chosen and on which data the optimization procedure is going to be executed on. Optimization theory and operations research will always be right around the corner. The particular topics to be covered are:
  • Logic synthesis: starting from a desired logical behavior, we derive a two layer or multilayer logic circuit with a performance that is as optimal as possible. The central technique used hereby is based on the famous 'OBDD'=Ordered Binary Decision Diagram.
  • Optimization in time and space: we consider this classical problem as it arises in systems synthesis.
  • Various methods for scheduling and resource binding will be considered.
  • Timing optimization and retiming of state machines: we consider the problem of optimizing a state diagram and timing behavior in the context of the signal flow diagram of a sequential system.
  • Algorithmic complexity and the NP problem: we encounter the problem of algorithmic complexity and how meaningful statements can be made about it.

Course setup

  • Main topics in the book of De Micheli.
  • One laboratory exercise.
  • A relevant paper from the literature.

Study Goals

  • To set up and use a 'design methodology' for complex data processing systems, in particular to set up its 'design space' and how to explore it.
  • Examples in design methodology.
  • To make parallel implementations for algorithms and use a paralleling compiler for that purpose.
  • To design an 'embedded system for signal processing'.

Teachers René van Leuken

High-level VLSI system design

Last modified: 2019-02-07


Credits: 5 EC
Period: 0/0/4/0
Contact: René van Leuken