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
The class requires a team project with teams of two or three
students. Suggested projects include: (more to be added soon)

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
energyefficient 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:

Implementation of TruePath Analysis using SMT solvers [Seshia].
Identification of true paths under the floatingmode delay model can
be cast as a satisfiability problem in a logic of differencebound
constraints (difference logic).
This project will explore the use of socalled
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:

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 safetycritical 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:

Synchronous DiscreteEvent Modeling [Lee].
The discreteevent domain in Ptolemy II approximates the ideal semantics
of discreteevent 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 fixedpoint semantics
and to construct an optimized implementation.
The implementation can be conveniently done in Ptolemy II.
References:

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 socalled
"optimal disjoint clustering" algorithm described in the POPL'09 reference
below. This algorithm involves formulating and solving successive Boolean
satisfiability (SAT) problems. An offtheshelf 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:
Guidelines for Project Presentations:
 Time your presentation for 15 minutes.
It's very important to finish on time. Practise your presentation several times.
 Topics to cover:
 Overview of the project and your approach
 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.
 Hardware/software platform and tools used
 Demo (optional)  could be interleaved with the presentation or performed right after
 Finish with a 1slide 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: 510 pages, use at least 11 pt font
 Topics to cover:
 Introduction & Problem Definition
 Outline of your Approach and how it compares to related work
 Algorithms and Models Devised
 Major Technical Challenges in the Design/Implementation and how you tackled them
 Summary of Results  what worked, what didn't, why, ideas for future work
 A oneparagraph narrative on the roles each team member played in the project
 How the project applied one or more of the course topics.
 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!
Last modified: Sun Aug 28 16:20:12 PDT 2011
