Date | Topics |
Jan 5 |
Introduction, course logistics, a couple of challenge problems
to motivate a systematic study of digital system design, examining
a few algorithms for integer division with the intent of implementing
these as digital logic circuits |
Jan 8 |
Delving deeper into the design of a divider: identification of
a controller and a datapath to implement a division algorithm,
role of registers and delays, discussion on the tradeoff between
space (circuit size) and delay |
Jan 12 |
Examining the integer division datapath more closely:
moving registers around, and their impact on the computation;
a naive controller design for integer division, and the importance
of sequencing operations correctly; a differential equation solver:
another example of control and datapath design starting from a
given algorithm
|
Jan 15 |
Controlling updates of registers: controlling clock input
versus controlling data input; multiplexors: their role in
datapath design, and their implementation; designing a
controller for the integer division algorithm; need for
hidden state variables in the controller. Slides showing datapath and controller of divider. |
Jan 19 |
Controller design: state transition tables and diagrams.
Implementing state transition logic as a Boolean circuit:
naive truth-table based approach using sum-of-product circuits,
K-map based approach and the benefits of identifying large cubes,
limitations of both approaches. Don't cares in compact
specification of logic functions. Partial specifications of
logic functions. Introduction to Binary Decision Diagrams
for representing logic functions. |
Jan 22, 29 |
Datapath design lectures by Prof. Ashwin Gumaste: adders,
subtractors, multiplier, comparator, decoder, encoder, multiplexer,
de-multiplexer, priority encoder.
Slides for material covered in class.
|
Feb 2 |
Datapath design lectures by Prof. Ashwin Gumaste: D-, JK- and
T-flip-flops, state equations and state machines, sequence detector
example.
Slides for material covered in class
(ignore the slides on the implication chart method).
|
Feb 5 |
Taking stock of CS226 and CS254 so far. Using ROBDDs to represent
and manipulate Boolean functions, multiplexer circuits from ROBDDs,
variable ordering and ROBDD size, negation and binary operations
on ROBDDs.
Slides -- ignore the point
about "quantification" on slide 13. You can also ignore slides 21
and 22. You need to see up to slide 23 for ROBDDs.
|
Feb 9 |
More about ROBDDs: binary operations, if-then-else operation,
function composition, counting satisfying assignments, etc.
Some simple rules of thumb for good variable
ordering -- swapping adjacent variables in an order and
dynamic "sifting". |
Feb 12 |
More about swapping adjacent variables in an order, use of
unique table and computed table to construct ROBDDs, brief
discussion on garbage collection of unused nodes in an ROBDD.
|
Feb 16 |
Solving example problems on ROBDDs; Quiz 1 |
Feb 19 |
Discussing solutions to quiz 1; ROBDDs with complement edges, rules
to choose between alternate ROBDDs with complement edges
representing the same function; simplifying functions using don't
cares on K-maps and using a recursive formulation with ROBDDs.
|
Mar 1 |
And-inverter graphs (AIGs): definition, non-canonicity,
simple operations, advantages and disadvantages. Operations to
simplify AIGs: simplify, strash, fraig. Importance of SAT solving
in simplifying AIGs.
|
Mar 4 |
More on simplification of AIGs: balance, refactor, collapse.
Linear-time conversion from AIG to equisatisfiable CNF formula:
Tseitin encoding. Brief discussion on mid-sem solutions.
|
Mar 8 |
Simplifying ROBDDs using don't cares (or cares). Deciding
termination cases in recursive formulation of simplification.
Discussion on why local optima may not lead to global optimum
when using a recursive (divide-and-conquer) approach to
simplification; illustration of this phenomenon through
an example.
|
Mar 11 |
Different kinds of don't cares: satisfiability don't cares
(SDC), observability don't cares (ODC), external don't cares
(EXDC). EXDCs resulting from unreachable states of sequential
state machines. Computing SDCs in a combinational circuit and
simplifying digital circuits using SDCs.
|
Mar 15 |
Computing ODCs in a
combinational circuit, and using them to simplify digital
circuits. Static and dynamic timing analysis: simple
algorithms and their applications; false paths in timing
analysis.
|
Mar 18 |
More on static timing analysis (STA) and simple
shortest/longest STA algorithms; setup and hold time of
flip-flops, identifying safe clock periods. Calculating
latest and earliest required times of change at gates in a
given combinational circuit; identifying gates whose delays
need to be changed to ensure required minimum and maximum
circuit delays
|
Mar 22 |
More on how delays of gates in a combinational circuit can
be altered to meet minimum and maximum delay requirements
through the circuit.
|
Mar 29 |
Lecture by Prof. Ashwin Gumaste: All about FPGAs ( Slides)
|
Apr 1 |
Re-timing: overview and simple applications for reducing
flip-flop count and minimum clock period in a given sequential
circuit.
|
Apr 5 |
Finding conditions for propagating transitions from inputs
along specific paths with prescribed delays; formulation as a
constraint solving problem, and illustration through examples.
Automatic formal verification: Significance of the reachability
problem, and some naive ways of computing reachable states;
representing sets of states using Boolean functions.
|
Apr 12 |
Automatic formal verification: Symbolic algorithms for solving
the reachability problem, and applications in logic optimization.
Slides
on symbolic reachability analysis.
|
Apr 15 |
Revision, problem clearing session
|