Lecture Schedule
| Date | Topics |
|---|
| Jan 3 |
Introduction, course logistics, a couple of real-world
problems to motivate a systematic study of digital system
design, truth-tables and designing circuits from them,
introduction to Karnaugh maps (K-maps) |
| Jan 6 |
More on K-maps and optimizing inputs of AND/OR gates in
two-level AND-OR circuits, design of some basic building
blocks: half-adder, full-adder, n-bit ripple-carry adder,
n-bit carry lookahead adder, n-bit comparator, multiplexors
and their variants. Comparison of nominal delays through
ripple carry adder and carry lookahead adder. |
| Jan 10 |
Two's complement representation of numbers and it's use in
computer arithmetic
(see this
for some more details), design of a combined adder/subtractor
unit, design of de-muliplexors, encoders and decoders.
Discussion on designing a divider: need to get to a circuit from
an algorithm, necessity of feedback and problems caused by
unfettered feedback in digital circuits, need for flip-flops to
break feedback loops and allow sequencing of steps, a simple
device (latch) for use in breaking feedback loops
|
| Jan 13 |
More on D-latches and D-flip-flops, need for care in choosing
delays when implementing latches and flip-flops with gates,
their use in breaking feedback loops in data-processing paths.
Implementing a sequential integer division algorithm using
a simple datapath and appropriately sequenced control signals.
Importance of good datapath design, and the sequential control
synthesis problem.
|
| Jan 17 |
Complete design of controller for a new integer division
algorithm with a new datapath (some slides), different ways of updating
values of registers: controlling the data input vs controlling
the clock input
|
| Jan 20 | Reduced Ordered Binary Decision Diagrams (ROBDDS)
for representing and manipulating Boolean functions: Shannon
decomposition, variable ordering and reduced forms, canonicity of
representation, constructing ROBDDs of "f op g" from those of "f"
and "g" (Slides -- read only the part taught in class) |
| Jan 24 |
Quiz 1
|
| Jan 27 |
More about ROBDDs: binary operations, if-then-else operation,
function composition, counting satisfying assignments, etc. and
their complexities
|
| Jan 31 |
Variable ordering problem in ROBDDs, static and dynamic
reorderin gof variables, swapping adjacent variables in an
ROBDD
|
| Feb 3 |
Don't cares and ROBDDs: representing don't care sets and
using them to simplify ROBDDs in a recursive way,
analyzing termination cases.
|
| Feb 7 |
Problem session, and discussion of Quiz 1 solutions
|
| Feb 10 |
Discussion of some solutions of Quiz 1; Quiz 2
|
| Feb 14 |
More usage of don't cares: satisfiability don't cares (SDC)
and observability
(some
slides from University of Maryland, although not
everything in the slides is relevant for us)
|
| Feb 17 |
Problem solving session on ROBDDs in preparation for midsem
|
| Feb 23 |
Mid semester exam |
| Feb 28 |
Discussion of some mid-sem questions; introduction to
And-Inverter Graphs (AIGs): definition, boolean operations on AIGs and
complexities, illustration of compose operation, rewrite, fraig,
strash, importance of SAT solving when operating with AIGs
(Slides) |
| Mar 3 |
Discussion of midsem solutions
|
| Mar 7 |
More discussion on AIGs: random simulation based heuristic
to reduce fraig-ing times, converting an AIG to an
equisatisfiable CNF formula using Tseitin encoding,
illustration of Tseiting encoding on a sample AIG,
demonstration of AIG operations on
the abc
tool.
|
| Mar 10 |
Further demonstration of
the abc
tool; introduction to static timing analysis: formulating delay
calculation as finding longest/shortest paths in a directed
acyclic graph, simple timing constraints for correct operation
of a sequential circuit -- relation between clock period,
clock-to-q delays, and minimum and maximum combinational logic
delays between flip-flops
|
| Mar 14 |
Timing constraints for correct operation of a sequential
circuit: effect of clock skew, setup and hold times. The
timing closure problem and definitions of required times and
arrival times, illustrating why some delays in a circuit may
have no effect on timing closure.
Some online resources for static timing analysis: a
nice blog
(you can ignore advanced topics in parts 7 onwards), a good set
of slides(not everything covered in class)
|
| Mar 17 |
Static timing analysis: formulating simple timing closure
as a constraint satisfaction problem (CSP) with boolean
combinations of linear inequalities, greedy heuristics with
required and arrival time intervals for timing closure
|
| Mar 21 |
Static timing analysis: calculating slacks, different
kinds of slacks, and using slacks to identify paths along
which delays need to be modified for timing closure
|
| Mar 24 |
Discussion on asynchronous reset and synchronous reset;
effect of increasing/delaying delays on different kinds of
slacks, slack based iterative heuristic for timing closure
|
| Mar 27 |
Need for testing and verification of circuits, motivation
for reachability analysis (slides)
|
| Mar 31 |
More on reachability analysis, explicit and symbolic reachability
analysis, basic steps of symbolic reachability analysis
|
| Apr 3 |
Symbolic unbounded reachability analysis, demonstration using
abc, bounded reachability as a SAT problem, k-inductive reachability
as a SAT problem
|
| Apr 7 |
Solving practice problems on symbolic unbounded
reachability analysis, more on bounded reachability and k-inductive
reachability; introduction to re-timing
|
|
Lab Schedule
| Date | Topics |
|---|
| Jan 4 |
Introduction, lab logistics, a quick introduction to VHDL
(Aniruddha's
slides on VHDL)
Xilinx ISE related links:
download local copy,
installation and licensing ,
getting started with ISE
|
|
| Jan 11 | More on VHDL, use of Xilinx ISE for design entry in
VHDL, compilation and simulation using testbenches. Design of a simple,
hierarchical 3-bit ripple-carry adder using half-adders and full-adders.
|
|
| Jan 18 | Implementing FindSmallestIndex module in VHDL and
mapping a simple design to the Atlys FPGA board (couldn't be completed).
Useful resources for FPGA mapping using Adept2: Windows pack, Ubuntu runtime, Linux utilities
A useful link for Linux users trying to install Adept2
Digilent Atlys master constraints file
|
|
| Jan 25 | Mapping a simple design all the way down to
an FPGA board using Xilinx ISE and Adept2 (go through
this document
carefully for instructions)
Lab Assignment 1: Designing encryption and
decryption modules of a simple ATM controller
(problem
statement, VHDL skeleton
files: Controller
top
module, debouncer
module, constraints file for mapping on Digilent Atlys board)
|
| Feb 1 | Evaluation of Lab Assignment1
|
| Feb 8 | Disscussion of problems in Lab Assignment1, and fixes
|
| Feb 15 | Lab Assignment 2: Communicating between the
Digilent Atlys board and a host machine (laptop) using FPGALink
Useful resources for using FPGALink:
FPGALink user
manual (the manual is for the 2012 edition of FPGALink and most of
it works for the 2014 edition that we will be using; however there are
a few changes to the command line
interface flcli), detailed
instructions to build FPGALink (2014 edition) libraries and get a
small VHDL demo "cksum" working (the Linux installation works
perfectly and is preferred).
|
| Mar 1 | Updated problem statement for implementing
communication between Digilent Atlys board and a host program.
|
| Mar 8 | Evaluation of Lab assignment 2
|
| Mar 15 | Problem statement for implementing
full ATM controller, sample backend csv file, sample constraints file (do not change this file)
|
| Mar 22 | Designing a full ATM controller (continued)
|
| Mar 29 | Evaluation of full ATM controller design
|
| Apr 5 | Discussion on project,
problem
statement
See here
for an open source FPGA Ethernet MAC design in VHDL from Philipp
Kerling,
updated
constraints file for mapping the ports in the Ethernet MAC design
to Digilent Atlys board pins
|
|