HIGH-LEVEL SYNTHESIS AND DESIGN AUTOMATION
HIGH-LEVEL SYNTHESIS AND DESIGN AUTOMATION.
- This class teaches logic, state machine and high level synthesis for ASIC, FPGA and new nano-technology based technologies such as memristors and reversible logic.. Embedded Systems and Image Processing/DSP architectures are emphasized as a source of architectural concepts and design examples.
- The book for the class is “Giovanni De Micheli: Synthesis and Optimization of Digital Circuits”. Look to Amazon.Com for the book. It is however not mandatory to purchase this book, as all information from the book, and more, you can find in class slides.
- The additional (non-mandatory) meetings are on Fridays from 5 p.m. to 9 p.m. in room FAB 150. Everybody is very welcome to participate, but a grade of A is still possible without participating in these meetings. The meetings can be changed to other days and times.
Additional meetings are devoted to solve problems, discuss homeworks, exams and projects, as well as your project ideas not directly related to the class material but where CAD algorithms may be of help.
- My method to teach the class is to repeat the same material again. First we look to an abstract problem. Next we look to it from the software point of view. Finally we look from the hardware point of view. Hopefully this way all students will understand the problem and various approaches and the links between theory, softare and hardware.
- In addition to this page (which will include more class materials), there will be a Facebook page created for this class. You are welcome to send me emails.
- This year our class emphasis is on memristors. We will design from bottom to top architectures based on memristors. We start with gates and logic synthesis methods,next blocks such as arithmetic blocks, next we go to state machines and architectures.
- This year there will be the following projects:
- Systematic characterization of all logic circuits with few levels. Sophie This is theory project.
- Design of Neural Network architectures with memristor-based IMPLY gates. Kamela This is design project.
- Design of SIMD Processor with memristor-based IMPLY gates: Image Processor. ?? This is design project.
- Design of Pipelined/systolic Processor with memristor-based IMPLY gates: Kalman Filter. ?? This is design project.
- Design of Processor with memristor-based IMPLY gates: Logic Machine for learning and optimization. ?? This is design project.
- Design of CAD software with memristor-based IMPLY gates: TANT networks and dissected pairs method. ?? This is software project.
INFORMATION ABOUT PROJECTS, HOMEWORKS AND EXAMS FOR FALL 2013.
ASSIGNED PROJECTS FOR THIS CLASS
- Students Homeworks Exams Projects. LIST OF PROJECTS AND READING.
In this link you will find also information about the topics for the first midterm. PLEASE STUDY FOR THIS EXAM.
It will be one hour, and you can use all books and notes and slides from the class. It will basically include synthesis with IMPLY, cube calculus, generation of prime implicants, and all material discussed so far in our meetings. Please look there for more details.
- Here are materials for PROJECT “Robot Vision”. Please come to me with memory stick to get all software. Mathias will help with Hough of Joliot Chu.
- Here are project materials for PROJECT “Kalman filter”.
- ECE 590 project report.pdf
- Implementation of Faddeev Algorithm
- Kalman Filter.pdf
- Kalman Filtering Systolic. Using Faddeev.
- KALMAN thesis.
- See also a thesis by my student about Faddeev algorithm. I gave it to some student in VHDL class. It is available from office. I will find more on this. But first read other papers.
- More papers about Kalman applications in practical problems.
- Agriculture Kalman GPS.pdf
- GPS Kalman Agriculture.pdf
- Kalman filter application GOOD.pdf
- kalman filter for agrorobot.pdf
- kalman localization slides.pdf
- localization EKF thesis.pdf
- sonar-kalman-ms thesis – kluwer1992.pdf
- unscented EKF – mobile-romanian-GOOD.pdf
- Here are materials for PROJECT “Logic Machine”.
- New chapter 16 to be improved and completed by your team.
- Here are materials for PROJECT “SYNTHESIS OF MEMRISTOR BASED LOGIC BASED ON TANT”.
- TLN Networks This is a variant of TANT with negated all variables.
- TANT NEtworks This is another variant of TANT.
- Perkowski’s slides about Memristors.
- Well known paper about NAND by Lee Davidson.
- MV Tant Networks and Decision Functions to minimize.pptx
- Paper about MV TANT by Perkowski and Jeske. This paper is a base of our new work with Jens.
- Paper by Jens.
- Paper on TANT by Vink.
- Paper about coloring approach to SOP by Ciesielski and Perkowski.
- Paper about coloring approach to SOP by Loc Bao Nguyen and Perkowski.
LECTURES FOR 2013 FALL CLASS.
- Introduction do IMPLY based logic synthesis.
- Introduction to class.
- Interval Graph Coloring – Golumbic”
- Memristor Synthesis
- Fast Intro to Cube-calculus.ppt
- TLN Networks
- Fast Intro to Cube-calculus.ppt
- Fast Intro to Control Data Flow Graphs And FSMs.ppt
- Methodologies = From Combinational To Processor.
- Fast Intro to Data Flow Graph And Scheduling.
- Quick Example Logic Synthesis.
- Two-level – tabulation method.
- Cyclic covering in synthesis.
- Advanced Covering , Coloring, TANT.
- Introduction to MV logic.
- Advanced MV Tautology and Complementation.
- Advanced MVTautology – primes – Sharp.
- Intro to AC decomposition.
- Coloring and Decomposition.
- Advanced AC decomposition.
- Boolean Functions. threshold, symmetry.
GENERAL RESOURCES FOR CLASS.
INTRODUCTION, BASIC HOMEWORKS AND PROJECTS FROM PREVIOUS YEARS.
- Embedded Systems.
- Combinational Circuits.
- Sequential Circuits.
- Basic Cube Cxalculus, basic Binary Decision Diagrams.
- Array/Transfer notation for circuits.
- Finite State Machines (FSM).
- Scheduling Data Flow Graphs (DFGs).
- Lecture 1. Introduction, class information, grading. What are Embedded Systems.
First Homework Assignment EXAMPLE. Combinational Logic Design.
- Lecture 2. From Combinational Circuits to State Machines to FSMD Processor.
Second Homework Assignment EXAMPLE. FSMD (Finite State Machine and Data path) Processor.
- 3.1. Homework Guidelines. Instruction what to do. PPT Format.
Third Homework Assignment. DFG scheduling.
- Lecture 5. Projects to be done in this class.
Fourth Homework Assignment. Write a project proposal as a conference paper.
- Lecture Details of some projects to be done in this class. Old project examples.
- Technologies. Lecture 1.2. From De Micheli. PDF Format. VLSI design. Microelectronics. Array-based design. Technologies. Design space and evaluation space.
- Lecture 1.3. Additional material for review and illustration IC design tools. Design, verification, simulation. Physical design. Design methodologies. PLA.You should be able to solve any problem related to the material of these lectures. Please review Karnaugh Maps, covering problems, Sum of Products, prime implicants and various binary gates. PDF Format.
THRESHOLD AND SYMMETRIC BOOLEAN FUNCTIONS
- Threshold and symmetry Boolean functions.
Threshold functions may be of interest in “Chaotic Logic” project.
Symmetric functions may be of interest in “Memristors” project as we can synthesize absolutely exact minimum circuits with memristors for symmetric functions.
- Fast computation of symmetries of boolean functions. Advanced material.
LATTICE DIAGRAMS AND USE OF SYMMETRY.
- Lecture 4.7. Symmetry of Boolean Functions and Decision Diagrams. Part 1. PDF Format. Lattice Diagrams. Switching structures. Recognizing symmetry. Generalized symmetries.
- Lecture 4.8. Symmetry of Boolean Functions and Decision Diagrams. Part 2. PDF Format. Networks of multiplexers. Shannon Lattices. Types of Decision Diagrams. Graphic methods to create Shannon and Davio lattices. Joining operations on maps and expressions.
MULTIPLE-VALUED LOGIC AND CUBE CALCULUS
- Cube Calculus My lecture about cube calculus. (In my notation.) This material is useful in Cube Calculus Machine Project.
- Introduction to Multivalued logic. This is an informal introduction that covers many topics. This material is useful in Cube Calculus Machine Project.
- Multi valued logic and notation. 1. Cube calculus for MV logic, used also in binary logic CAD. This material is useful in Cube Calculus Machine Project.
- Multi valued logic and notation. 2. Efficient representations and algorithms to synthesize binary circuits using MV logic. This material is useful in Cube Calculus Machine Project.
- Multi valued logic and notation. 3. Efficient representations and algorithms to synthesize binary circuits using MV logic. This material is useful in Cube Calculus Machine Project.
- Multi valued logic and notation. 4. Efficient representations and algorithms to synthesize binary circuits using MV logic. Sharp and other operators, in MV variant. This material is useful in Cube Calculus Machine Project.
- Lecture 4.3. Introduction to Multiple-Valued Logic and Its Applications. PDF Format. Multi-valued signals. Why is multiple-valued logic important. History. Post Literals. Min and Max gates. Maps for multiple-valued logic and their use in synthesis. Expressions versus maps. Decision Trees and Diagrams.
BASIC INTRO TO FINITE STATE MACHINES, CONTROLLERS, DATA PATH AND SCHEDULING.
- Lecture 3. Brief Review of FSMs.
- Lecture 4. Data Flow Graphs and Scheduling.
- Sequential Machines. This material may be useful in controller design for projects and homeworks.
- Minimization of state machines. This material may be useful in controller design for projects and homeworks.
- FSM Implementation. Advanced material.
- Vahid – advanced state machines and concurrent behaviors. Advanced material.
GRAPH COLORING AND BASIC COMBINATORIAL PROBLEMS
- Read chapters 1, 2 and 7 of the De Micheli texbook.
- Lecture 2.2. Graph Coloring of Hypergraphs for combinatorial Problems. From De Micheli. PDF Format. Shortes path problem. Longest path problem. Vertex cover. Heuristics. Graph Coloring. Interval graphs. Clique partitioning. Covering and satisfiability.
- Graph Coloring.
- AUXILIARY: 2-graph-coloring-hypergraphs.
SAT – SATISFIABILITY AND CONSTRAINTS SATISFACTION.
- A* Search
- Dynamic Programming.
- Sudoku as an example of CSP.
- SAT introduction.
- Branch and bound.
- AUXILIARY 1 SAT.
- Lecture 4.1.Combinatorial Problems and Branch and Bound from De Micheli. PDF Format. The essence of Branch and Bound and Backtracking. Bounding functions.
EVOLUTIONARY PROGRAMMING AND STOCHASTIC METHODS TO SOLVE PROBLEMS IN OPTIMIZATION.
- Introduction to Evolutionary Computation.
- Evolutionary Algorithms.
- Simulated Annealing.
- Simulated Annealing And Tabu Search.
INTEGER AND LINEAR PROGRAMMING IN OPTIMIZATION.
- Integer Programming And CPLEX.
- A.10.1. Linear Programming and Integer Programming. PDF Format.
- A.10.2. Example of ILP software. PDF Format.
COMBINATORIAL PROBLEMS AND DATA STRUCTURES IN LOGIC SYNTHESIS
- Lecture 4.2. Boolean Algebra. PDF Format. Set theory and notation. Sets, Cartesian Products and Relations. Functions. Posets and Hasse Diagrams. Lattices. Boolean Algebras. Boolean Functions. Cofactors. Boole/Shannon Expansion Theorem. Minterm Canonical Forms. Boolean Difference. Don’t cares.
ASHENHURST-CURTIS DECOMPOSITION AND RELATED SUBJECTS.
- Lecture 4.4. Review of graph coloring, set covering, cliques and decomposition. Part 1. This review includes more examples, some new algorithms, new applications, industrial importance and some additional discussion. PDF Format.
- Lecture 4.5. Review of graph coloring, set covering, cliques and decomposition. Part 2. PDF Format. Functional Decomposition as a general problem-solving idea. Decomposition of multiple-valued relations.
- Lecture 4.6. Review of graph coloring, set covering, cliques and decomposition. Part 3. PDF Format. Decomposition of functions and relations based on graph coloring.
- Lecture 4.9. Decomposition of Multi-valued relations and its application in data mining. Part 1. PDF Format. The machine learning problem. Data Mining. Logic formulation of learning. Various reductions of decomposition problems to basic combinational problems. Decomposition of multiple-valued relations. Generalizations of Ashenhurst-Curtis Model. Applications of decomposition in VLSI, FPGA and Data Mining.
- Lecture 4.10. Decomposition of Multi-valued relations and its application in data mining. Part 2. PDF Format. Benchmarking and applications of decomposition.
REVIEW FOR MIDTERM EXAMINATION
- 6.1. Problems to review – Midterm Exam. PDF Format. We present here all topics and problems that may occur in the midterm exam. The is an inclusive list of topics for the rehearsal meetings on Fridays, that will be held before the midterm exam.
- 6.2. Problems from Midterm Exam. After the exam, please solve them all as additional homework. This homework will be graded separately from the midter, so if you have done a mistake, you can fix it in the homework. PDF Format.
- 6.3. Solutions to Midterm Exam. PDF Format.
MODELING AND ARCHITECTURE FROM MICHELI
The material for this part is included in chapters 3 and 4 of the De Micheli texbook.
- Lecture 8.1. Modeling Circuit Modeling, Hardware Description Languages – examples. Structural and behavioral views. Silage and Data Flow Graphs. VHLD and Verilog. Simple retiming and transformations on design data. Data Flow examples. Hierarchies. Estimation of costs.
- Lecture 8.2. Architectural issues and tools Synthesis. Trade-offs. Pareto Points. Architectural Level synthesis. Design procedures. Compilation transformations. Constraints and resources. Hardware Modeling. Binding. Design trade-offs.
- Lecture 8.3. Control Data Flow Graphs and FSMs. PDF Format. Place of Finite State Machines in Design methodologies. Examples. Specification of FSMs. Mealy. Moore. Non-deterministic. Probabilistic. Reductions. Equivalence and Minimization. Decomposition. Composition.
- Lecture 8.4. Data Flow Graph and Scheduling. PDF Format. The concept of Data Flow Graph. Examples. Transformations. Allocation. Scheduling and Mapping concepts. Constraints. Various algorithms that operate on CDFGs.
PETRI NETS AND SIMILAR MODELS.
- Lecture 8.5. Petri Nets. PDF Format. Petri Net examples. Uses of Petri Nets. Equivalence. Parallelism. Verification. Reachability. Liveness. Persistence and other properties.
HIGH LEVEL SYNTHESIS AND ARCHITECTURAL DESIGN OVERVIEW.
Read chapters 5 and 6 of the De Micheli texbook.
- High Level Synthesis Overview.
- Architectural Design. Exam Problems.
- A.10.5. Overview of issues in high level synthesis. PDF Format.
- Auxiliary. CAD tools use.
SCHEDULING AND ALLOCATION.
- Scheduling, not ILP, not Force Scheduling.
- Register allocation using graph coloring.
- Scheduling and Allocation, complete example for exam.
- Lecture 10.1. Scheduling I. PDF Format. Scheduling. Taxonomy. ASAP and ALAP scheduling. Mobility. Constraint graphs. Scheduling under timing constraints. Integer Linear Programming approach to scheduling.
- Lecture 10.2. Scheduling II. PDF Format. Hu’s algorithm. List scheduling. Force-directed scheduling. Scheduling with chaining.
- Lecture 10.3. Resource Sharing. PDF Format. Allocation and binding. Compatibility graphs and conflict graphs. Algorithms and heuristics. Perfect graphs. Interval graphs. Left-Edge algorithm. ILP algorithm. Register binding problem. Register sharing data-flow graphs. Memory binding. Bus sharing. Module selection approaches.
- Lecture 10.4. Scheduling and Allocation example. PDF Format. Various practical examples of complete solutions to allocation and scheduling of simple controllers. Exam-related.
- Lecture 10.5. One more scheduling example. PDF Format. Similar but simpler problem may occur on final.
- Lecture 10.6. More examples of scheduling and allocation. PDF Format.
- A.10.3. Scheduling and Assignment. PDF Format.
- A.10.6. Register Allocation. PDF Format.
- A.10.7. Register Allocation using graph coloring. PDF Format.
- A.10.13. Paper by Tseng and Siewiorek. PDF Format.
- A.10.14. Force Directed Scheduling by Paulin et al. PDF Format.
SYNTHESIS OF PIPELINED AND SPECIAL SUB-SYSTEMS.
- Lecture 9.9. Retiming and pipelines. PDF Format. Retiming and resynthesis. Pipelines. Retiming and resynthesis of pipelines. This is useful for many final exam problems. Links to scheduling and allocation.
- Estimations and transformations.
- System Partitioning.
- Pipelining Methods.
- A.10.4. Pipelined Scheduling. PDF Format.
- Memory management.
- A.10.10. Pipelined Design Scheduling and Allocation. PDF Format.
- A.10.15. High-level synthesis for low power. PDF Format.
SYNTHESIS OF EMBEDDED SYSTEMS.
- A.10.8. Embedded Systems. PDF Format.
- A.10.9. Real Time Embedded Systems. PDF Format.
- Design Challenges And Technologies For Embedded Systems.
HARDWARE SOFTWARE CODESIGN.
- A.10.11. Hardware-Software Co-Design. PDF Format.
- A.10.12. Hardware Software Co-Design. Part II. PDF Format.
REVIEW AND ADVANCED FINITE STATE MACHINES AND SEQUENTIAL CIRCUITS
- Lecture 9.1. JK flip-flops and flowcharts. PDF Format. Structures of FSMs. Flowcharts and their transformations. Converto Flowchart to table and graph. Types of flip-flops and creation of equations. Please review all material about basic flip-flops and state machines. It will be used in homeworks and exams.
- Lecture 9.2. MSI Building Blocks. PDF Format. Multiplexers, demultiplexers, applications in control and data path. Synthesis with Muxes. Active levels. ROMs. Decoders.
- Lecture 9.3. Memory. PDF Format. RAM, ROM, timing. Memory systems.
STATE MINIMIZATION AND STATE ASSIGNMENT OF FINITE STATE MACHINES
- Lecture 9.4. Introduction to minimization of completely specified Finite State Machines. PDF Format. Basic ideas of FSM minimization. Graph and tabular algorithms for flowcharts and completely specified machines.
- Lecture 9.5. Advanced methods for Finite State Machine Minimization. PDF Format. Detailed examples of graphical methods that will be tested on the exam. Closed and complete graphs.
- Lecture 9.6. Advanced Algorithms for FSM minimization. From U.C. Berkeley. PDF Format. More examples, formalization.
- Lecture 9.7. State assignment methods for synchronous machines based on rules. PDF Format. Relations between excitation equations and state assignment rules for FSMs. You have to understand the origin of the rules and illustrate how they relate to hardware minimization after realization of the machine.
- Lecture 9.8. State assignment methods based on multiline and partition pair methods. PDF Format. This is an advanced material that is not neccessary for the exam. Any state assignment method is allowed. However, these methods give you a better understanding of partitions and partition pairs which are the fundamental concepts in structural theory of machines by Hartmanis and Stearns, Rhodes, etc.
- A.9.5. Example of using both rule based and multiline method to find a good assignment. PDF Format.
- A.9.6. Additional material on state assignment based on methods developed at University of California, Berkeley, USA. PDF Format. Comparison of methods on a simple FSM. More on state assignment and encoding. Various CAD tools. You can find more detailed information on these topics in the De Micheli book.
- A.9.7. Additional material on sequential circuits, state minimization and state assignment from Yonsei University, Korea. PDF Format. This material is more algorithmic and you can find complete examples of solutions. All problems from this set of slides can be solved of course with any of the methods presented in the class or in the slides from section A.9.
- A.9.9. Additional Material: Concurrent state-minimization in two dimensions and decomposition of a finite state machine. PDF Format. A paper by M.A. Perkowski, L. Jozwiak and W. Zhao, “Symbolic Two-Dimensional Minimization of Strongly Unspecified Finite State Machines”. A new advanced approach to synthesis of machines with many don’t cares. Example of non-standard approaches to FSM synthesis. This is given only for those who have deep interest in FSM design. Not required for exams.
- A.9.8. Additional material on modern methods for state assignment from Eindhoven University in Netherland. PDF Format. The short review of state assignment algorithms and systems. Can be used as a guide to literature for those who want to go into depth of structural synthesis of automata.
DESIGN OF SEQUENTIAL CIRCUITS.
- A.9.1. Bus and Memory. PDF Format. Auxiliary materials only, related to some of your questions from Friday meetings. You should be able to link this information to register-transfer level synthesis.
- A.9.2. Example of controller design – Manchester Encoder. PDF Format. complete design example that includes simple state machine for control and simple data path, but illustrates timing and composition of machines. Related to exams.
- A.9.3. Turing Machine as an example of a controller. PDF Format. Just to show you that Turing machine is also a controller and can be designed as other controllers using methods developed in this class. Useful as exercise in designing controllers.
- A.9.4. Waveform generator. PDF Format. Another complete design example of a system with controller and data path.
PIPELINED AND SYSTOLIC ARCHITECTURES.
- Systolic one dimensional architecture examples.
- Motivation To FPGA Systems. SORTERS.
FIELD PROGRAMMABLE GATE ARRAYS (FPGAs) AND FPGA ARCHITECTURES.
- Digital FPGAs.
- Analog FPGAs. (FPAAs).
- Potential uses of memristors and other technologies.
- FPGAs. Overview.
- Altera Corporate Information.
- FPGA Logic CAD software.
- Design Technologies And CAD.
- FPGA logic emulation and reconfigurable systems.
- Advanced FPGA chips and systems.
- FPGA educational boards and projects.
- FPGA. RECONFIGURABLE high-level.
- Reconfigurable Systems.
- FPGAs and ADOBE PLUG Image Processing.
- 11.1. List of topics and typical problems for the final exam. PDF Format.
- 11.2. Problems from final exam. PDF Format.
- 11.3. Solutions to final exam. Part 1. PDF Format.
- 11.4. Solutions to final exam. Part 2. PDF Format.
TYPICAL PAST HOMEWORKS AND PROJECTS
Ideal hardware/software project would require these stages.
Understand the problem. Write specification of your system.
- Optimize by hand or using various tools from various sources.
- Analyze the results theoretically. Collect statistics.
- Program in VHDL or Verilog.
- Test on VELOCE.
- Synthesize and download to FPGA.
- Test and demonstrate the entire system with a robot, camera, etc.
Most of our projects would include only stages of this process.
- VHDL Spectral Transforms for Object Recognition with Rotation, Scaling, and Translation.
- VHDL Image Processing. Fast Fourier and Matching.
- Student work from previous year. Fast Fourier and Matching. From Satya Nekkalapu
- Student work from previous year. SEBASTIAN SCHUEPPEL. Fast Fourier and Matching.
- Information about boards.
- VHDL Fractal Images Based on Higher Order Algebras.
- Class report from Jessie Armagost. 2007.
- Cellular automata. The software for Cellular Automata Simulation can be found here http://www.mirekw.com/ca/ and here http://cafaq.com/soft/index.php
- Full data from Jessie Armagost. ZIPPED. 2007.
- VHDL Optimizing computer for Quaternions and Clifford algebras.
- GPU and CUDA.
- Constraints Satisfaction problem interface to Adiabatic Quantum Computer.
- Testing Reversible Circuits.
- Image Processing Computer.
- Lego Next Robot with many sensors.
- Dancing Emotion Learning and Mimicking Robot. Dancing and fighting humanoid robot KHR-1 is used in this project.
- Realistic Hand Motion Generation for a Humanoid Robot.
- Maximum Clique program by Dongsoo Lee. PDF Format.
- Documentation. Maximum Clique program by Dongsoo Lee. PDF Format.
- 3.3. Donghyun Kim – Maximum Cliques in the graph using Kerbosh method
- 3.4. Ahn, Ki-yong, A graph coloring algorithm in Chapter 2.4.3 of text book. (Page 62 ALGORITHM 2.4.6)
- 3.5. Hyungock Kim – Graph Coloring in Java
- 3.6. Seon Pil Kim – Shortest and Longest Path in a Directed Graph.
- 3.7. Hwangbo Woong – Vertex covering
- 3.8. HeeJun Shim Unix C program
Index of /~scott/papers
Index of /~eoruklu/IIT/Publications_files