Date assigned

Assigned Readings

Jan. 21

• De Micheli, Preface + Chapter 1
• Handout #5: The Quine-McCluskey Method
• Lecture #1 Slides

Jan. 28

• Handout #6: Multi-Output Functions (pp. 160-165)
• Handout #7: Heuristic Minimization of Two-Level Circuits (pp. 185-191 top)
• Handout #8: Rudell's PhD Thesis
  • read: abstract, ch. 1, ch. 2.1-2.4 (note: can skim defs. in 2.2 for multi-valued functions, but read others carefully), 2.8 intro. + 2.8.1, 2.9-2.11
• Lecture #2 slides (pt. 1, pt. 2)

Feb. 4

• De Micheli: ch. 7.1, ch. 7.2 (read pp. 270-276, skim 277-283), ch. 7.4.5
• Handout #10: pp. 191-194 -- focus on Defs. 5.2.1-5.2.2; skim rest
• Handout #11: (fast tautology check) read introduction, basic rules (B), miscellaneous rules (M)
• Handout #12: read cofactor section only
• Lecture #3 slides

Feb. 11

• Handout #10: ch. 5.2-5.3 (we cover in a better order, and more systematically)
• Handout #11: (fast tautology check) read remainder
• Handout #12: read remainder (text + examples)
• Handout #14: read 'solved problems' on single- and multi-output co-factor, tautology, unateness, etc.
• Handout #15: (fast complementation) read all

Feb. 18

• Handout #10: chs. 5.4, 5.6, 5.7
• Handout #16 (optional): read/skim on last-gasp/super-gasp/make-sparse
• Handout #17 (fast prime generation): read all
• Handout #18 (prime generation example): read all
• De Micheli (intro. to multi-level logic synthesis): read ch. 3.3.2, ch. 8.1-8.2 (to end of 8.2.1)
• Lecture #5 slides

Feb. 25

• De Micheli (intro. to multi-level logic synthesis): read rest of ch. 8.2 (8.2.2-8.2.3), start of ch. 8.3 (pp. 360-365 bottom)
• Lecture #6 slides

March 3

• Handout #20 (kernels/co-kernels/extraction): read all
• De Micheli, ch. 8.3 (intro. to multi-level logic synthesis): read p. 366-top p. 370
• De Micheli, ch. 8.3 (intro. to multi-level logic synthesis): read top p. 374-top p. 380
• De Micheli, ch. 8.3 (intro. to multi-level logic synthesis): skim only top p. 370-top p. 374 (we cover somewhat differently in Handout #20)
• De Micheli, ch. 10.1-10.2 (technology mapping): read all

March 10

• Handout #24 (basic tree-based covering [area-oriented]): read all
• De Micheli, ch. 2.3.4 (dynamic programming): read pp. 49-51
• De Micheli, ch. 10.3 (tech map basics): ch. 10.3, read only pp. 509-517
• De Micheli, ch. 10.3 (tree-based covering): ch. 10.3, read only pp. 522-524 bottom

March 24

• Handout #26 (advanced tree-based covering [delay-oriented, load-dependent]): read all
• Handout #27 (advanced tree-based covering [power-oriented]): read abstract, secs. 1-3.3
• Handout #27a (advanced tree-based covering [power-oriented]): read all (errata/clarifications on #27)
• De Micheli, ch. 10.3 (tree-based covering): ch. 10.3, read bottom p. 524 - top p. 526
• De Micheli, ch. 10.6 (perspectives): read all

March 31

• Circuit Partitioning:
  • Handout #29: skim Abstract, sec. I; read/study sec. II, p. 93 - top left p. 95 (end of "Partitioning" subsection); skim rest
  • Handout #30: read all
  • Handout #31: read pp. 30-36, skim pp. 37-40

Apr. 7

• Retiming: complete approach
  • Handout #33: Leiserson/Saxe, read Abstract and Section 1; read Sections 2-5 carefully (skip proofs; focus on concepts, theorems and algorithms)
  • (basics) De Micheli, ch. 9.3.1 Retiming, p. 462-bottom p. 469
  • (advanced) De Micheli, ch. 9.3.1 Retiming, bottom p. 469 - mid. p. 471 (skip from "Note that the timing feasibility problem" to end of section)
• Retiming: additional supporting algorithms
  • Bellman-Ford algorithm: De Micheli, ch. 2.4.1, top p. 54-mid p. 57
  • Floyd-Warshall algorithm: you find (many resources available, incl. Wiki pages online)
  • T.H. Cormen, C.E. Leiserson et al., "Introduction to Algorithms" (3rd edition) [digital access through Columbia libraries]: see Handout #34b for relevant reading

Apr. 14

• Architectural (High-Level) Synthesis:
  • Handout #35: read all
  • Handout #36: read all
  • Lecture #12 slides
  • DIFFEQ example: De Micheli, pp. 18-19
  • CDFG's: De Micheli, ch. 3.3.4, pp. 119-123 bottom
  • HLS overview: De Micheli, ch. 4.1-4.2, ch. 4.3 (to end of 4.3.2)
  • Handout #38 (scheduling): read ch. 8.13-8.14, pp. 375-384
  • Handout #37 (resource sharing [variable/operation usage]): read ch. 8.4, bottom p. 336-top p. 342
  • Handout #37 (resource sharing [bus minimization]): skim ch. 8.4, top p. 342-top p. 343

Apr. 21

• Asynchronous Design:
  • Handout #40 (overview slides): read all
  • Handout #41 (overview article): read all (but skim "Pipelining" section, pp. 13-16)
  • Handout #42 (hazard-free logic minimization): read pp. 1-74, read pp. 79-88

Apr. 28

• Introduction to Approximate Computing:
  • Lecture #14 slides
  • Handout #43: read all (but focus on concepts, do not need to learn all details)
• Synthesis and Optimization of Digital Microfluidic Biochips:
  • Handout #44: read all (but focus on concepts, do not need to learn all details)
  • Handout #45: read abstract, sec. 1-2, 4-6 (focus on basic concepts, skim rest -- do not need to learn all details)