Class announcement | Time and Location | Teaching Staff| Text Book | Grading Policy | Additional Info | Course Syllabus

Class announcements

• (5/12) HW assignment #3 is posted.
• (4/22) Here is HW assignment #2
• (4/08) Please submit your project proposals by 5pm on Friday April 17. The proposal has to clearly define the problem, outline an approach (work plan), and evaluation methodology.
• (4/06) HW assignment #1 and corresponding 10-node, 100-node, 1000-node and 5000-node graphs are posted.
• (4/06) There will be no lecture on Monday 4/13.
• (3/30) Topic Survey and presentations
• (3/30) Class projects
• (3/30) Covered material and references
• (3/30) Please check out class webpage regularly for announcements.

Time and location

• MW 2:10-4pm @1062 Bainer Hall

Teaching Staff

• Soheil Ghiasi
  • Office Hours: by appointment
  • Office Location: 3171 Kemper Hall

Text Books

• No text book is required. A collection of books and research papers will be used throughout the quarter.
• Referenced papers are available through online digital libraries. pointers to papers will be posted on class webpage.
• Texts on embedded computing and combinatorial algorithms would be helpful. Examples include:
  • Wayne Wolf, "Computers as Components", Morgan Kaufmann Publishers, Second Edition (2008), ISBN: 978-0-12-374397-8
  • Phillip A. Laplante, "Real-Time Systems Design and Analysis", Wiley-IEEE Press, 3 edition (2004), ISBN: 978-0471228554
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, "Introduction to Algorithms", MIT Press and McGraw-Hill (2001), ISBN: 978-0262032933

Grading Policy

• Participation 10%
• Homework 20%
• Midterm (take-home, ~8th week) 20%
• Project 50%

Additional Information

• Prerequisites: EEC 170 (computer architecture). Experience with digital systems beyond EEC 170 (e.g. 180B), and algorithm design (e.g. ECS 122) would help, but are not required.
• All work must be done individually (or by the team, if teams are allowed). Brainstorming, discussion and collaboration (not duplication), however, improve learning and are encouraged. Please consult the UC-Davis code of academic conduct or the instructor, if you are unclear if a specific activity would violate the honor code.

Syllabus

• Introduction
  • Embedded computing systems
  • Optimization techniques
  • Target models of computations
• Combinatorial optimization
  • Complexity and NP-completeness
  • Approximation algorithms
  • Graph algorithms overview
  • Shortest path
  • Network flow
  • Graph coloring, cliques, independent sets
  • Randomized and online algorithms
  • Continuous vs. discrete optimization
  • Linear and Integer Programming
  • Convex optimization
• Design and optimization of embedded systems
  • Architectures and platforms
  • Operating systems, compilers and virtual machines
  • Realtime systems
    • Worst-case execution time estimation
    • Soft vs. hard realtime systems
  • Scheduling
    • Task scheduling
    • Communication scheduling
    • Voltage scheduling
  • Partitioning
    • Min-cut partitioning
    • Min-quotient partitioning
    • Temporal partitioning
  • Hardware synthesis
    • High-level synthesis
    • Implementation selection
    • Programmable and reconfigurable platforms
  • Compilation and code generation
    • Overview of classic transformations
    • Memory access optimizations
    • Template generation and matching
    • Compilation for reconfigurable computers
  • Networked Embedded Systems
    • Collaborative applications
    • Code migration
    • Incremental analysis