EECS 144/244

Fall 2015

Contents
Home
Overview
Logistics

Lectures
Homeworks
Reading
Resources
Projects
Fall 2015 edition
Fall 2014 edition
Fall 2013 edition
Spring 2013 edition
Fall 2011 edition

bCourses

Course Development
Wiki
SVN

Course Projects

1. Quantitative Analysis of Distributed Algorithm Implementations [Seshia].

   Wireless sense and control networks use distributed algorithms to achieve various tasks such as routing, time synchronization, sensor fusion, etc. In many applications, the implementations of these algorithms must be energy-efficient so as to make the most of scarce energy whether it be from batteries or harvested from the environment. This project seeks to develop a better understanding of how the energy consumption of such programs varies with the algorithm's implementation, state of the platform, and as a function of the input to the algorithm.

   Reference:

   • Quantitative Analysis of Systems Using Game-Theoretic Learning
   • Chapter 15 of Lee & Seshia: Introduction to Embedded Systems
   
   
   
2. Implementation of True-Path Analysis using SMT solvers [Seshia].

   Identification of true paths under the floating-mode delay model can be cast as a satisfiability problem in a logic of difference-bound constraints (difference logic). This project will explore the use of so-called satisfiability modulo theories (SMT) solvers for difference logic for the problem of checking whether a path is a true path. A key goal will be to evaluate how scalable this approach is in practice --- how large a circuit can it handle? Reference:

   • Satisfiability Modulo Theories (book chapter)
   • "Floating-Mode Delay" paper by Devadas et al.
   
   
   
3. Scheduling algorithms for synchronous/reactive models [Lee].

   A synchronous/reactive (SR) model is a model of concurrency that exhibits determinate behavior and is used in the design of embedded and safety-critical systems. Efficient implementation of an SR model requires algorithms that iterate to a fixed point solution to a system of equations in few steps. Although the worst case complexity can be shown to be quadratic in the number of components, simple heuristic techniques yield near linear behavior for practical models. The goal of this project is to implement, assess, and improve existing scheduling algorithms. The implementation can be conveniently done in Ptolemy II.

   Reference:

   • The Semantics and Execution of a Synchronous Block-Diagram Language
   
   
   
4. Synchronous Discrete-Event Modeling [Lee].

   The discrete-event domain in Ptolemy II approximates the ideal semantics of discrete-event models, as explained in Chapter 6 of System Modeling, Design, and Simulation. The goal of this project is to analyze the complexity of an ideal fixed-point semantics and to construct an optimized implementation. The implementation can be conveniently done in Ptolemy II.

   References:

   • Chapter 6 of System Modeling, Design, and Simulation.
   • Leveraging Synchronous Language Principles for Heterogeneous Modeling and Design of Embedded Systems.
   
   
   
5. Implementation of clustering algorithms in DAGs [Lee].

   A DAG is a directed acyclic graph. A clustering algorithm groups the nodes of a given DAG into groups called "clusters." Different clustering algorithms exist with different properties. These algorithms are particularly useful in the context of modular code generation from hierarchical models such as Simulink or Ptolemy. The goal of this project is to implement the so-called "optimal disjoint clustering" algorithm described in the POPL'09 reference below. This algorithm involves formulating and solving successive Boolean satisfiability (SAT) problems. An off-the-shelf SAT solver will be called as a subroutine for this purpose. The implementation could be done in Ptolemy, as part of an extension of an existing framework for modular code generation.

   References:

   • Modular Code Generation from Synchronous Block Diagrams
   • Compositionality in Synchronous Data Flow: Modular Code Generation from Hierarchical SDF Graphs

• Time your presentation for 15 minutes. It's very important to finish on time. Practise your presentation several times.
• Topics to cover:
1. Overview of the project and your approach
2. Main technical challenges -- in algorithm design or implementation -- and how you tackled them. Focus on the top 3, at most one slide on each. Include any cool algorithms or insights that you came up with. Highlight what is new in comparison with related work in the literature.
3. Hardware/software platform and tools used
4. Demo (optional) -- could be interleaved with the presentation or performed right after
5. Finish with a 1-slide summary: what did you achieve, what more can be done?

Guidelines for Project Reports:

• One report per team. Hard deadline: Friday, December 17 at 12 noon. Submit on bSpace.
• Recommended length: 5-10 pages, use at least 11 pt font
• Topics to cover:
  1. Introduction & Problem Definition
  2. Outline of your Approach and how it compares to related work
  3. Algorithms and Models Devised
  4. Major Technical Challenges in the Design/Implementation and how you tackled them
  5. Summary of Results -- what worked, what didn't, why, ideas for future work
  6. A one-paragraph narrative on the roles each team member played in the project
  7. How the project applied one or more of the course topics.
  8. Feedback: List of topics covered in class that came in handy; any topics that weren't covered that would have been useful
• Illustrate algorithms and models with diagrams, and results with graphs, screenshots, pictures of your hardware, etc.
• Keep the report short and precise; avoid lengthy and verbose descriptions!