Lecture #1 5th Aug. 1998

Objectives and scope of the course; Design steps; Major design processes: Synthesis and Simulation; History of Design Automation; Course outline; Evaluation creteria.

Lecture #2 6th August, 1998

Moore's Law; Gajski's Y-Chart; Representation of design and design processes in Y-Chart.

Lecture #3 10th August, 1998

Features required in a HDL; Brief History of HDL's

Lecture #4 12th August, 1998

Overview of VHDL concepts; Entity and Architecure; Behavioural and Structural Descriptions in VHDL; Examples of simple components.

Lecture #5 13th August, 1998

Description of sequential behaviour using PROCESS; Sensitivity List; Simplification of behavioural description using functions. Examples.

Lecture #6 17th August, 1998

Representing Timing and delays in VHDL; Transactions and Events; Inertial and Transport Delays; Signals and signal assignment.

Lecture #7 19th August, 1998

Structural Description in VHDL; Component declaration and instantiation; Use of GENERATE statement to specify iterative structures.

Lecture #8 20th August, 1998

Test Bench Specification in VHDL; User defined types: Example of 4-valued logic; Function overloading: Example of overloading of AND operator; declaration and use of constant arrays.

Lecture #9 24th August, 1998

Gaurded Signal assignment; Resolution function.

Lecture #10 26th August, 1998

Application of Gaurded statements and Resolution functions for describing Data Flow descriptions and FSM.

Lecture #11 27th August, 1998

Semantics of VHDL PROCESS; shared signals among concurrent processes; Various variations of WAIT statements and their application to represent timing constraints and synchronous behaviour.

Lecture #12 31 August, 1998

Case Studies: Two wire handshake protocol, Bus Arbiter, Asynchronous Serial reciever.

Lecture #13 2nd Sept., 1998

What is High Level Synthesis?; RTL description; Data Flow and Sequence Flow graph for representing sequential behaviour.

Lecture #14 3rd Sept., 1998

Representation of complex sequential computation using Sequence Flow Grahp; Resources and Constraints in High Level Synthesis; Important tasks in High Level Synthesis: Scheduling, Binding and Allocation.

Lecture #15 9th Sept., 1998

Basic Scheduling Algorithms: ASAP and ALAP; Importance of ASAP and ALAP schedules; Representation of minimum and maximum delay constraints in sequence graph.

Lecture #16 10th Sept., 1998

Mapping Scheduling problem to a shortest path problem; Dijkstra and Bellman -Ford algorithms for shortest path problem; Introduction to mapping scheduling problem to Integer Linear Programming problem.

Lecture #17 14th Sept., 1998

Representation of dependency constraints and resource constraints as ILP constraints; Reducing number of constraints. Basic idea of list scheduling; giving priority to nodes in resource constrained list scheduling; "longest distance from the sink" heuristic for deciding priority of nodes.

Lecture #18  16th Sept., 1998

Force Directed Scheduling Algorithm: Computation of Distribution Graph and  Self Force on operations.

Lecture #19  17th Sept., 1998

Force Directed Scheduling (Cont.): Successor-Predecessor Force Computation. Incorporating  pipeline operation units in Force Directed Scheduling algorithm.

Lecture #20   21th Sept., 1998

Introduction to Allocation and Binding problem; Compatibility Graph and resource sharing; Conflict graph and graph coloring problem;  A heuristic algorithm for Clique Partitioning Problem, Interval graph and left edge algorithm

Lecture #21    24th Sept., 1998

ILP formulation of operator binding problem; introduction to register binding and interconnection binding.

Lecture # 22   5th Oct., 1998

Register binding for hierarchical sequence graphs; Mapping interconnection binding to clique partitioning of compatibility graph; Interrelationship between register binding , operator binding with interconnection binding.

Lecture #23  7th Oct. 1998

Control Part Synthesis: Modelling of control path using FSM, Extended FSM  and Petri Nets
Representation of Concurrency and  synchronization in EFSM. Firing rules for transitions.
Safeness and Liveness of Petri-nets.

Lecture # 24  8th Oct., 1998

R-Nets (Modified Petri-Nets) for representing digital systems. Direct Hardware synthesis of R-Nets.

Lecture #25  12th Oct.,  1998

Microprogram Control Design: Horizontal and Vertical formats. Format optimization: Autonomy Heuristic.

Lecture # 26   14th Oct., 1998
Four ideas for  Format optimization: Autonomy Heuristic; Clique Partitioning; Variable Length encoding for vertical encoding of fields of different sizes;  Horizontal encoding of very small field.

Lecture # 27   15th Oct., 1998

Context of Logic Synthesis in system design process. Various problems in Logic Synthesis.
Combinational Logic Design: Two Level Optimization, Multi-Level Logic optimization
Sequential Logic Design: State minimization, State Encoding and Retiming

Lecture #28   21st Oct. 1998

Exact Two Level optimization problem formulations: Hyper graph node covering, set covering, ILP.
Heuristic solution based on operators working on a cover: Expand, Reduce, Reshape and Redundancy Removal.

Lecture #29   26th Oct. 1998

Heuristic algorithm for implementing Expand operation: Positional cube notation; Heuristic for deciding the order of implicant expansion; heuristic for deciding the order of literals to be raised to don't care.

Lecture #30   28th Oct. 1998
Heuristic Algorithm to implement Reduce operator: order in which the implicants are considered for reduction; Maximally recuded cube and its computation.

Lecture #31   29th Oct. 1998
Multi-level logic optimization, Basic ideas: factorization and common subexpression extraction. Boolean vs. algebraic division(factorization).  Why is finding good boolean factors hard? Algorithm for boolean division. Kernels and co-kernels .

Lecture #32   5st  Nov. 1998
Levels of kernels; Kernel set computation algorithm;  Estimate of improvement for using kernels and co-kernels;
Kernel intersection and common sub-expressions.

Lecture #33   9th Nov. 1998

Finding kernel intersections and co-kernel intersections by finding co-kernels of auxiliary functions; Rectangular cover problem and its application to kernel  and co-kernel extraction.

Lecture #34  11th  Nov. 1998
State minimization of incompletely specified  FSM: compatible states, maximal compatible state set, generation of maximal compatible sets. Introduction to state assignment problem, introduction to state partitioning for state assignment.

Lecture #35   12th Nov. 1998

Relationship between closed state partitioning to  FSM implementation; Algorithm to generate close partitions;
product and sum of partitions; output consistent and input consistent partitions.
 

Lecture #36   16th Nov. 1998
State Assignment for two level logic optimization; Introduction to state assignment for Multilevel Logic optimization.

Lecture #37 18th Nov. 1998 

State Assignment for Multilevel Logic optimization( MUSTANG procedure): Fan-in and Fan-out Algorithm; Graph embedding in hypercube; Wedge Clustering heuristic.