The student after completing the course will be able to:|
• derive recurrent relations from mathematical expressions;
• design a data dependency graph based on the recurrent relations;
• transform the data dependency graph into a signal flow graph using projection and scheduling;
• describe mathematical expressions that specify data dependencies and operations in a graph by means of a functional programming (FP) language;
• synthesize hardware circuits using the FP descriptions.
• describe the results of the project assignment in a report.
Tasks to be executed by digital hardware become more and more complex. For that reason, it is desirable to have a structured design process to come from task (algorithm) to hardware. Besides that, powerful concepts to express the algorithms in a formal way are required. This course aims at providing in-depth knowledge of the relation between an algorithm and the possible architectures that execute the algorithm. We will discuss methods to transform a sequentially expressed algorithm via single assignment code and a dependency graph into a signal flow graph. From there on various hardware implementations will be developed in the form of array processors or systolic arrays. In case of an irregular dependency graph, the hardware will take the form of a simple von Neumann architecture with a dedicated instruction set. |
Topics included are:
• Linear (static) scheduling
• Re-timing and design transformations.
A second aim of the course is to specify the resulting hardware alternatives in a formal way, by means of mathematical equations. Using the evaluation mechanisms of a functional programming language, these equations can be directly evaluated leading to a simulation of the hardware. Besides, these specifications open the possibility to prove that the functionality of the various hardware alternatives is the same.
Theory concerning the structured design process and the specification of hardware in a formal way will be discussed during lectures. The students gain hands-on experience in a project assignment where an algorithm is described in a formal way and synthesized towards hardware.