EE 574/ EE 674: SYSTEM LEVEL DESIGN AUTOMATION, HIGH LEVEL SYNTHESIS,
AND SOFTWARE-HARDWARE CODESIGN
Marek A. Perkowski
Department of Electrical Enginering.
-
The course teaches new ideas and techniques in high-level
synthesis, system-level synthesis and software-hardware
codesign. Part of it has been organized according to industrial requests and emphasizes
digital design and simulation using modern tools and hardware description languages.
Working knowledge of VHDL is welcome, but is not a must.
-
System-related subjects will be discussed that are of interest to students.
New books by Davio and De Micheli will be used, together with instructor's lecture notes
and journal/conference papers.
Lecture notes will be also available as WWW Pages.
-
The class has been now made independent
and it does not require other classes as prerequisities.
-
There will be several software/hardware design mini-projects.
-
The class will be taught in PSU.
Catalog Description of the proposed Course sequence.
Behavioral, functional, structural and register-transfer descriptions.
Algorithmic State Machines. Fundamentals of Hardware Description Languages.
Simulation. Levels of system simulation.
Current extensions of language VHDL and expandable languages.
Specification of controllers and data path architectures.
Microprogramming and systematic design of control units.
Hardware scheduling and allocation.
Automatic System Verification.
Software-hardware codesign.
VHDL for systems from Field Programmable Gate Arrays.
Emulators and Xputers.
Examples and applications of complete systems.
Several computer-based software mini-projects. Discussion of projects.
TOPICS BY HOUR:
1. Comprehensive design automation systems (3 hours).
2. Regular expressions, Petri Nets and other hardware description methods (3 hours).
3. Problems of system and high-level synthesis and verification (4 hours).
4. Register-transfer notation and design (3 hours).
5. Approaches to Hardware Verification (5 hours).
6. Methods and languages to specify hardware, system hardware-sofware codesign (3 hours).
7. Data path design (4 hours).
8. Scheduling and allocation (3 hours).
9. Design methods for systolic and pipelined computers (2 hours).
10. FPGA technologies, FPGA-based prototyping and emulation (5 hours).
11. Cellular and dynamic architectures (3 hours).
12. Microprograming and microprogram optimization (2 hours).
PREREQUISITE: graduate standing in EE.
TEXTBOOKS:
-
Davio.
-
Giovanni De Micheli - "Synthesis and Optimization of Digital Circuits" McGraw-Hill, 1994.
GOALS:
-
This is the third course in a sequence, but can be taken as a stand-alone class,
because it is graded mostly on projects.
The class will include lectures by the professor, student presentations
and discussion of projects and tools.
-
Continuation of projects from previous classes of this sequence is encouraged.
New students will take new projects.
-
Students learn about advanced topics related to the design
automation of general-purpose and special processors.
The special emphasis is for FPGA-based circuits for robotics, telecommunication and image processing.
-
The emphasis is on using various tools, tool integration,
software-hardware codesign, fast prototyping methods, hardware verification, and
use of simulation methodologies,
use of various programmable devices and design
of innovative computer architectures.
-
Substantial and comprehensive group project that leads to
the design of the state of the art software tool or processor.
LAB PROJECTS
-
There is no formal lab, but the students work on a comprehensive project.
-
These projects vary from year to year.
-
In the past the software projects included
various point tools in the following areas: logic synthesis, state machine design, silicon compilers,
simulators, technology fitters, technology mapping,
microprogramming, and high-level synthesis.
-
There were also projects related to integration of the tools to systems
and testing them in designs.
-
In the past, the hardware projects in Robotics included the following:
- concurrent reactive state machine for control of a walking robot,
- co-processor interface to PC,
- Cube Calculus Machine for solving combinational problems,
- Satisfiability Machine,
- ESOP minimizer based on breadth-first hardware search,
- Petrick Function minimizer based on counting search.
- Image matcher based on maximum cliques,
- Multiplier of multidimensional polynomials,
- Array multiplier,
- Systolic multiplier,
- Systolic Matrix operations using Faddeev algorithm,
- Systolic LU decomposer,
- Rough Set Machine,
- Ashenhurst Decomposer,
- Various microprogrammed units of special applications,
The hardware projects in Telecommunication included the following:
- digital FIR and IIR filters,
- digital stack filter,
- median filter,
- digital convolvers,
- Fast Fourier processor,
- Fast Fast Walsh processor,
- Fast Reed-Muller processor,
- general-purpose Digital Signal Processor,
- image coding and compressing processors.
- Viterbi
- Manchester
- Spread-Spectrum Transmitter,
- Internet switch,
- various coding circuits,
The hardware projects in Image Processing included the following:
- Hough Transform Processor for finding parameters of straight lines in image,
- Image filtering and other transformations based on convolution,
- Image histogramming,
-
This year most projects are tool-related and related to software-hardware codesign, and include:
- Use Mentor Tools for automatic insertion of BIST to VHDL
(this project requires some knowledge of Unix and VHDL).
This project is preferably for students who have already taken my Test class.
- Use Summit Tools (and/or Xilinx Tools) for synthesis of verifiable controllers.
Verification will be by hand.
This project is preferably for students who take my 510FP class, but
other students are also welcome. No other prerequisites are expected.
- Use ORCAD Tools for designing of a logic machine in ALTERA or Xilinx.
(this project requires some knowledge of VHDL, but can be done by mostly schematic capture).
Choice of a logic machine is to be discussed, it can be a sorter/absorber,
satisfiability machine, covering machine or other of your choice.
This project does not require other prerequisities than some elementary
VHDL knowledge on the level of EE 171.
- Re-compile Diades tools of PSU for new Lisp and make them available from WWW.
Re-Design totally automatically all 20 ADL examples from high-level specification.
Investigate the role of encoding, state-minimization and logic synthesis.
(this project requires some knowledge of Unix, html and Lisp).
It is for students with interest in hardware-software codesign and software implementations
of CAD tools.
COMPUTER USAGE:
SUN SPARC Stations are used to run Mentor, Cypress, Orcad, DEC, Analogy Inc., and various public-domain
and university design tools and simulators.
ESTIMATED CONTENT:
- Engineering Science: 2 credits or 50%.
- Engineering Design: 2 credits or 50%.
ADDITIONAL INFORMATION:
-
Besides the textbook, there are very extensive class notes available
from Smart Copy, that include descriptions of all projects
and many references.
-
The students work in groups on the comprehensive projects.
There are no tests or homeworks.
There are graded class presentations by every student.
Every student has to write several reports and deliver piece of computer code
or a hardware design.
-
The grade is based on student's performance in presentations, reports and final project.
The grading policy is as follows:
-
20 %. Written individual reports that document reading and understanding of literature,
class and off-the-class group discussions, new ideas and theoretical
contributions, working computer code, and results of testing the programs.
-
30 %. Project, either software, hardware or software/hardware.
-
10 %. Class lectures presented by students.
They are based on previous
reports of the students. Grading takes into account both the
quality of material, the use of figures, transparencies, and other materials
prepared by students, and also the quality of the oral delivery, and how
well the student is able to handle questions of the class and the professor.
-
10 %. Participation in class and off-the-class discussions. (Evey week there is
an additional meeting just to present the progress of work on reports).
-
30%. Final report, that takes into account the critics of the professor,
additional results from the computer, and feedback from the class.
MORE DETAILED SPECIFICATION OF TOPICS:
-
Comprehensive design automation systems.
System that start from high-level specifications, role of VHDL and Verilog.
Systems for state machines and logic level. Systems for FPGAs and PLDs.
Silicon compilers.
-
Hierarchy of languages, regular languages,
regular expressions. Formal and intuitive
synthesis of Finite State Machines from regular expressions.
Petri Nets as input specifications. Parallel machines and
tokenized machines. State Charts and Spec-Charts. Other hardware description methods
on high and medium level.
-
Problems of system and high-level synthesis and verification.
Predicate calculus methods to specify hardware.
Automatic theorem proving.
Modal operators. Use of higher order logic.
Examples of symbolic simulation, analysis and verification
of combinational logic.
-
Register-transfer notation and design.
Use of invariants in verification and optimization of hardware.
Systematic design of Glushkov machines with control
realized as a finite state machine.
-
Approaches to Hardware Verification.
Verification of Finite State Machines. Use of Decision Diagrams.
Verification of microprograms.
-
Methods and languages to specify hardware. Basic ideas
of hardware description languages. Examples of languages: VHDL, Verilog, ADL, RUBY, and ZEUS.
-
Data path design. Design of arithmetic and logic operators. Use of similarities of
structures and operators. Generalized factorization.
Compilation of Data Path of a processor in VHDL.
-
Algorithms for optimal and quasioptimal scheduling of processor operations
in time. Logical, statistical and knowledge-based approaches.
Simulated annealing and genetic algorithms. Exact and approximate algorithms.
Optimal and quasioptimal allocation of operations to hardware
modules. Applications to optimize an FFT processor.
-
Design methods for systolic and pipelined computers.
Specification of a systolic processor for sorting and median filtering in VHDL.
Optimization of pipelines.
-
FPGA technologies, FPGA-based prototyping and emulation.
Array processors. Xputers. Data Flow techniques.
Very Long Instruction Processors in FPGA.
Neural Nets and Fuzzy logic processors.
-
Cellular and dynamic architectures.
Cellular logic. Cellular automata. Game of life. Modern realizations of
cellular logic and automata.
-
Microprograming and microprogram optimization.
VHDL description of a microprogrammed controller.
Using stack and recursion in hardware.
Examples of architectures with stacks.
Techniques of microprogram optimization.
Some of the topics change every year, depending on selected projects and students' interests.
TUESDAY, MARCH 30
What is this class about.
The goal of the class is to learn how to verify your design
and next how to use CAD tools for automatic design free from errors.
Verification will be done in Prolog.
Next the design will be transformed to VHDL, schematic capture or Summit tools.
Next the design will be synthesized using Xilinx or Altera tools. (option, for some projects only).
The groups of students will be created.
Introduction to Automatic Theorem Proving and Prolog language.
Predicate Calculus versus Boolean Logic, quantifiers (Chapter 12 from my book).
THURSDAY, APRIL 1
Automatic Theorem Proving.
Clauses, Horn Clauses, Substitution, Resolution, Unification.
Examples of reasoning: forward, backward.
Prolog language.
Simple question answering, logic puzzles, family databases.
TUESDAY, APRIL 6
Presentation and discussion of projects.
Brief presentation of the DEC PERLE board and the discussion of mapping to it.
List processing and automatic theorem proving in Prolog.
THURSDAY, APRIL 8
Examples of Test Generation and Verification in Prolog.
Formal Synthesis correct from specification: Regular Expressions in Prolog.
Fundamentals of verification.
Verification of a multiplier.
TUESDAY, APRIL 13
Various approaches to formal verification.
Sequent calculus: Petri Nets, Flowcharts, natural language described machines.
Sequent calculus: Mealy and Moore Machines, Data Path circuits.
THURSDAY, APRIL 15
Student Presentations.
Designs correct from specifications. Transformational design methods.
TUESDAY, APRIL 20
CAD tools for logic specification, simulation and synthesis.
Introduction to EPLDs and FPGAs.
Xilinx chips.
Altera chips.
THURSDAY, APRIL 22
CAD tools for logic verification.
FPGA computing.
TUESDAY, APRIL 27
Formal verification algorithms based on theorem proving in higher order logic.
THURSDAY, APRIL 29
Formal verification in HOL, introduction.
Principle of perfect induction.
TUESDAY, MAY 4
Lecture: Formal verification in HOL, verifying Comparator, Counter, Shifter and Serial
to Parallel converter.
THURSDAY, MAY 6
Lecture: formal verification based on automatic theorem proving.
HOL: Verifying microprograms. Verifying multiplier.
TUESDAY, MAY 11
Lecture: formal verification based on automatic theorem proving.
Using FOL for adder and microprograms.
THURSDAY, MAY 13
Lecture: formal verification based on automatic theorem proving.
Using Boyer-Moore to prove correctness of circuit generators.
TUESDAY, MAY 18
Examples of formal verification on simple examples.
THURSDAY, MAY 20
I am absent, attending ISMVL'99.
Please meet in class and discuss your projects.
Student Presentations (videotaped?).
TUESDAY, MAY 25.
Using Boyer-Moore to proove correctness of circuit generators.
Using Relational System.
Examples of formal verification performed by students on simple examples.
THURSDAY, MAY 27
Repetition and projects discussions. New approaches and systems for formal verification/design.
Student Presentations (videotaped?).
MONDAY, JUNE 1.
Lecture: formal verification based on functions.
Lecture: formal verification based on state machines.
Presentation and discussion of projects.
THURSDAY, JUNE 3.
Classical and Modern Decision Diagrams.
Model Checking.
TUESDAY, JUNE 8.
Model Checking (cont).
THURSDAY, JUNE 10.
Final presentations and discussions of class projects.
SUNDAY, JUNE 13.
Last day of accepting class reports.