EE249 Fall 2004, Project List
Here is a list of projects.- Model Adapters
- Fault Tree Generation
- Embedded software for Wireless Sensor Networks
- Maintaining Sensing Fidelity in Low Power Sensor Networks
- A posteriori Time Synchronization in Distributed Sensor Networks
- Guiding architecture mapping by simulation
- Unified events scheduling algorithm in Metropolis simulator
- Integration of Metropolis with Ptolemy II
- Interfacing Metropolis with Petri Nets and QSS (Quasi-Static Scheduling)
- Systolic arrays vs. multithreaded multiprocessors
(Cross listed EE244) - Scalable and Reusable Time-Triggered Scheduling
(Cross listed EE244) - Implementing Tipi Irregular Datapaths in FPGA Fabrics
(Cross listed EE244) - Heterogeneous Models of Computation for Network Processing
(Cross listed EE244)
Model Adapters
In this project we will analyze the interaction between two dif- ferent models of computation, and implement a model adapter in the Metropolis design environment. The project consists of first selecting two models of computation (for example, a pure dataflow model and a synchronous model). The models are then interepreted in the context of a common refinement (for instance, a discrete event model) to define the way they interact. Finally, the ap- propriate communication media and schedulers are implemented in Metropolis so that the original models can be simulated together without the need of the common refinement. In the project, we will study issues related to the non-determinism that arises from the refinement, and to the loss of information that occurs when moving back to the original domains.
Mentors: Roberto Passerone (robp@cadence.com) (Cadence Berkeley Laboratories)
Alessandro Pinto (University of California, Berkeley)
Hybrid Systems Modeling
Hybrid systems modeling is very important in today's development of embedded systems for several reasons. We give three good examples to understand the need of a language for specifying continuous and discrete dynamics together in a unified environment.
Hybrid systems are used as abstraction of complex continuous dynamics. A famous example is the bouncing ball. When the ball hits the ground, energy is exchanged between the the two involved entities and its model is not easy. A bounce is abstracted as a discrete event that change the velocity sign.
Embedded systems interact with the environment to control the dynamic of its physical quantities. While the environment is well characterized by differential equations, embedded systems are discrete in nature.
The same kind of problems arise in modeling mixed signal systems where digital devices interact with analog subsystems.
Many tools are available to simulate and verify hybrid systems but each of them has its own language and set of tools with different properties.
The goal of this project is to define a universal format for describing hybrid systems and implement a domain in the Metropolis framework. It will touch the formal definition of the l language and its implementation using the Metropolis-Meta-Model language.
Mentors: Alessandro Pinto (apinto@eecs, UC Berkeley)
Roberto Passerone (Cadence Berkeley Labs).
Fault Tree generation
In safety critical systems, designers must guarantee that the failure rate of the system is not higher than some given value. Starting from a functional description of the system, designers derive a "fault tree" that can be used to compute the system failure rate, starting from the failure rates of the subsystems or functions. We call this the "unmapped fault tree", because it only refers to the dependencies in the functionality, not to the execution platform components.
Once designers derive a mapping, typically a mapping with redundancy, we can automatically generate a new fault tree that we call the "mapped fault tree".
This tree can be used to compute the system failure rate based on the failure rates of the components in the execution platform.
The mapping information is used to :
- bind the failure rate of a component to the failure rate of the functions mapped to it
- Recreate the fault tree including the information regarding common faults
- determine the set of replicas of a given function, so that its services fail only when there are not enough non-faulty replicas
The aim of this project is to
- create an infrastructure for modeling fault trees for dataflow-like applications
- code a mapped fault tree generator, using this infrastructure
We will draw examples from the automotive domain.
The project can and should start by September 21.
Prerequisites:
Programming skills in either C/C++ or Java
Familiarity with real-time systems and fault-tolerant systems is a plus, but not directly necessary.
Number of students: 2
Mentors:
Claudio Pinello (ClaudioPinello@cal.berkeley.edu)
Sri Kanajan (General Motors)
Embedded software for Wireless Sensor Networks
Menthors: Alvise Bonivento, Alessandro Pinto, Arkadeb Ghosal(alvise@eecs.berkeley.edu)
Wireless Sensor Networks (WSNs) can support a wide variety of applications ranging from habitat and environment monitoring to energy conservation, from ambient intelligence to military applications. This is one of the two reasons why a lot of research effort has been put in this domain over the last few years. On the other hand, WSNs are usually deployed in hostile environments and, since maintenance is problematic, have tight energy consumption constraints. As a result, WSN is a new research field with great opportunities and also great technological challenges.
The complexity of the design task and the variety of skills needed to develop applications and implementation platforms, make the task of developing an effective design methodology for WSN quite challenging. The ideal solution should deal with all phases of the design process from conception to implementation.
Many diferent hardware platform have been proposed (Mica, PicoRadio, Telos) and also protocol synthesis solutions have been formulated (Genesis). It is still an open issue in the design flow how to map the final protocol solution into a target hardware architecture. So far most of the case studies have used the NesC/TinyOS platform for this layer. On the other hand, it is still not clear in the WSN community if this platform is good enough to describe the level of concurrency typical of the embedded networks domain. A designer should be able to describe his protocol solution independently from the target hardare architecture and then it should be a design automation problem to synthesize those algorithms into a feasible solution to be implemented on a given architecture. The goal of this project is to test the xGiotto and Metropolis technology over these issues. In particular protocols should be specified in xGiotto and target architecture modeled in Metropolis. The final go al is to generate a solution that can be implemented on the target architecture, satisfies systems requirements and is verifiable.
Number of people involved: 2
Prerequisites: familiarity with C++, familiarity with comunication protocols.
Maintaining Sensing Fidelity in Low Power Sensor Networks
Distributed sensor networks are an emerging class of embedded systems, where the distributed nodes are equipped with sensors in addition to classical computation and communication system components. While the existence of sensors enables interfacing the network to the physical world, it brings a new dimension to the design and maintenance of such networks. Furthermore, like many other classes of embedded systems, the low power requirement for the distributed networks places a hard constraint that needs to be properly addressed. Studies have shown that the most effective way to maintain the energy in the network is to power-off the radios on the distributed nodes. Therefore, there is a trade-off between the quality of sensing and the power consumption of the nodes in the network.In a previous work, we have made a definition of sensing coverage in a sensor network [Meg01]. This approach relies on finding the Voronoi diagram of the sensor field and transforming the problem into a graph theoretical problem. Using combinatorial techniques, the paths of worst and best sensing coverage are computed as paths on the Voronoi diagram.
A few research projects have addressed the problem of scheduling the activities of the distributed nodes while maintaining the connectivity of the network [Kou03, Che02, Xu01, God04]. However, the problem of powering off the nodes while maintaining the quality of sensing has not been properly addressed yet. The goal of this project is to use the definition of the sensing coverage in the network to maintain the quality of sensing in the network above a sensing threshold. The idea is to exploit the properties of the Voronoi cells of the nodes and deciding on the nodes that have to be active to maintain the sensing fidelity.
Mentor: Farinaz Koushanfar {farinaz@eecs.berkeley.edu}
Notes
-This project requires some basic knowledge and understanding of graphs and algorithms and programming skills in C++/Java or a similar programming language
-This can be a very rewarding project; two last EE249 students who have completed the low power connectivity project had a full paper at ISLPED with 7% acceptance rate [Kou03].
References
[Che02] Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris. "Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks." ACM Wireless Networks 8(5), September 2002.
[God04] P. Brighten Godfrey and David Ratajczak. "Naps: Scalable, Robust Topology Management in Wireless Ad Hoc Networks", In Proc. Information Processing in Sensor Networks (IPSN 2004), 2004.
[Kou03] F. Koushanfar, A. Davare, D. Nguyen, M. Potkonjak, A. Sangiovanni-Vincentelli. "Low Power Coordination in Wireless Ad-hoc Networks." ACM International Symposium on Low Power Electronics and Design (ISLPED), pp. 475-480, August 2003.
[Meg01] S. Meguerdichian, F. Koushanfar, M. Potkonjak, M. B. Srivastava. "Coverage Problems in Wireless Ad-Hoc Sensor Networks." IEEE INFOCOM '01: the Conference on Computer Communications, vol. 3, pp. 1380-1387, April 2001.
[Xu01] Ya Xu, John Heidemann, Deborah Estrin, "Geography-informed Energy Conservation for Ad-hoc Routing", In Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking (ACM MobiCom), July 2001.
A posteriori Time Synchronization in Distributed Sensor Networks
Synchronization is the process of relative time adjustment at different components in a distributed system. Distributed sensor networks are an emerging paradigm for interfacing the embedded systems to the real world. While the synchronization problem is a classical distributed system problem and has been widely addressed before [Lam78], the addition of the sensors and interaction with the physical environment brings a new dimension to this problem. Furthermore, synchronization is crucial for a number of sensor network problems including multi-sensor fusion, power coordination between the nodes, and security.The common base for all the existing synchronization approaches is that they are done a priori where each component informs other components about its internal timing. A specific protocol is then used to relatively adjust the times at the distributed components [Kar03, Els02]. We propose the first a posteriori time synchronization protocol where the time signals are synchronized after the data is collected. There are at least two major advantages of an a posteriori time synchronization approach. First, it is significantly less expensive in terms of energy consumption, bandwidth, and storage requirements. Second, it can achieve time synchronization with an arbitrary high accuracy even beyond time resolution of a single clock cycle.
The a posteriori synchronization problem can be formulated in the following way: n nodes are given and at each node i (0<= i <= n) time series of sensor readings are recorded as a signal si(t). The goal is to find for each signal si, a specific time adjustment Ti in such a way that the sensor fusion of data with the least amount of error can be conducted, i.e. si(t +Ti). The a posteriori synchronization method employs inter-node modeling of the data from the different sensors and adjusting the time of sensor readings by minimizing the discrepancy between the model and the data. We use non-parametric statistical modeling of the sensor data along with standard re-substitution and learn-and-test validation methods to establish the interval of confidence and the quality of our results.
Mentor: Farinaz Koushanfar {farinaz@eecs.berkeley.edu}
Notes
-We use the traces of a real sensor network from a recent deployment at Intel Berkeley lab, to realistically abstract the sensor fusion problem and to examine the accuracy and effectiveness of our approach.
-Programming skill in a standard programming language is required; knowledge of Matlab or a statistical package like Splus/R is a plus but not mandatory; knowledge of statistical modeling and validation is also a plus but not mandatory.
-Students will collaborate closely with the mentor. We have performed a large body of analysis and modeling on the same dataset before and the results of using this paradigm look very promising.
References
[Els02] Jeremy Elson, Lewis Girod and Deborah Estrin. "Fine-Grained Network Time Synchronization using Reference Broadcasts." In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI 2002), December 2002.
[Kar04] Richard Karp, Scott Shenker, Christos Papadimitriou, and Jeremy Elson. Global Synchronization in Sensornets. In Proceedings of LATIN 2004.
[Kar03] Richard Karp, Jeremy Elson, Deborah Estrin, and Scott Shenker "Optimal and Global Time Synchronization in Sensornets." CENS Technical Report 0012, April 10, 2003.
[Lam78] Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, July 1978, 21(7):558-565.
Guiding architecture mapping by simulation
Mentor: Alex Kondratyev (Cadence Berkeley Labs)
Mapping in Metropolis matches up corresponding services in functional model to architecture model. Currently the two services equivalence is stated explicitly using the "synch" keyword. In order to automate the mapping process in metropolis, the functional model profiling is required. To that end translating Metropolis meta-model to CDFG is a one convenient way of representing the flow of the system. The project would involve integrating a CDFG backend to Metropolis. This will require coordinating with the authors of CDFG generation tool from UCLA and learning the API to Metropolis meta-model. Concurrently, utilize the simulation backend to produce one or multiple traces of the functional model execution. Simulated results will be used to run different analyses using the CDFG. An example of information that is useful to reveal through simulation is about the partitioning of the functional specification into "critical" and "non-critical" parts. This information might be annotated in CDFG and serve two purposes a) to drive synthesis efforts b) to estimate "average-case" performance. The project is going to explore different ways of recording information about simulation in CDFG: from annotating data-dependent choices by probabilities to partial unrolling of CDFG loops to explicitly represent the most common scenarios. Exploring methods to create hardware models and refining to an actual implementation is the main task of the project.
Unified events scheduling algorithm in Metropolis simulator
Mentor: Guang Yang (guyang@ic.eecs.berkeley.edu)
Metropolis metamodel has rich semantics esp. on events synchronization. e.g. there are different language constructs for this purpose including await statement, ltl synch (1-way and 2-way), general ltl constraints, etc. These constructs play a very important role in metamodel simulation in that the scheduling algorithm of these constraints has a major impact on the simulation speed. Currently, in the SystemC-based simulator, ad-hoc scheduling algorithms are used for different kinds of constraints for performance and easy handling reasons. However, it might be possible to come up with unified scheduling algorithm esp. for different kinds of ltl synch constraints. The student(s) will research the intrinsic relationships among different kinds of constraints and implement the new scheduling algorithm in the simulator.
Integration of Metropolis with Ptolemy II
Mentors: Guang Yang guyang@ic.eecs.berkeley.edu,Haiyang Zheng(from Ptolemy group) hyzheng@eecs.berkeley.edu
Ptolemy II is a set of Java packages supporting heterogeneous, concurrent modeling and design. It is mainly focusing on the research related to embedded software. Therefore, it emphasizes very much on the execution (simulation) of different MOCs. Metropolis, on the other hand, will be addressing synthesis (software/hardware), verification and architecture exploration in addition to simulation. Currently, what is available in Metropolis design environment includes the metropolis metamodel language, a metropolis compiler, a simulation backend and a SPIN based formal verification backend. This project involves the research of the semantics of Metropolis metamodel and how to construct it with other MOCs in Ptolemy. By doing this, it allows the composition of Metropolis design with designs from other domains, such as continuous time, descrete event, etc. As a side effect, it brings a GUI for Metropolis environment, which would boost productivity for sure.
Interfacing Metropolis with Petri Nets and QSS (Quasi-Static Scheduling)
Mentors: Trevor Meyerowitz (tcm@eecs.berkeley.edu),Yoshi Watanabe (watanabe@cadence.com)
Suggested Number of Students: 2
Petri nets are a highly analyzable model of computation that are good at expressing concurrency and scheduling issues. Quasi-static scheduling (QSS) is work that takes a Petri Net graph and finds a schedule that minimizes the number of dynamic decisions, and thus increasing performance and decreases scheduling overhead. FlowC is a sub-set of C with read and write primitives that is used as an input to QSS.
This project involves two elements.
The first translating a CPU microarchitectural model expressed in the YAPI platform (KPN + non-deterministic select) in metropolis into FlowC and applying QSS on it. Key aspects of this are: the transformation, identifying how to best translate KPN structures into FlowC (and thus petri nets), measuring the performance of the FlowC models before and after applying QSS, and interfacing the FlowC models with Metropolis models.
The second element is the creation of a Metropolis backend that translates metropolis models using the YAPI platform library into a FlowC description that can be interfaced to the QSS tools. It will rely upon the intuition developed in the first part of the project. Specific elements of this include the syntax translation, wrapping/abstracting non-important parts in blackboxes, and defining and including petri-net markings in the underlying code. This tool will be tested on simple examples as well as the CPU models.
Systolic arrays vs. multithreaded multiprocessors
(Cross listed in EE244)Mentor: Will Plishker (plishker@eecs.berkeley.edu)
When designing high performance multiprocessor embedded systems, two natural design paradigms result: systolic arrays and hardware multithreaded systems. Systolic arrays has the benefit determinism while hw multithreaded systems provide higher utilization through non-determinism. An application's execution profile (distribution of execution cycles consumed, memory accesses, communication pattern) determines how well it can exploit these underlying approaches. Students will develop a model incorporating these application and some architectural parameters, which will facilitate design space exploration of the application mapping problem. Metropolis can be used for modeling different architectural configurations and various application mappings and validation of the model can be done with commercial cycle accurate simulators. Optionally students can explore methods for exploring this design space.
Scalable and Reusable Time-Triggered Scheduling
(Wei Zheng)Design a task and bus scheduling tool that works with the automotive design process and captures the constraints that the automotive domain has.
Scheduling is a key component in real-time system design. However, with the upcoming time-triggered technology being introduced in vehicles, the automotive domain requires new solutions that address the automotive constraints in the scheduling arena.
This project will explore metrics which can characterize the scalability and reusability of the distributed embedded system, and through solving a non-linear optimization problem to schedule functionality on a given architecture so that certain design constraints are satisfied.
Let A(legacy) denotes the existing application(task and bus schedule) on the system
A(current) denotes the current application we want to add on the system
A(future) denotes the future application we want to add on the system
A task and bus schedule goal that is reusable or scalable is defined as when we try to do scheduling for the current application on the system that already have A(legacy) running on top of it,
1. All constraints on A(current) and A(legacy) are satisfied
2. Future application A(future) can be on top of the resulting system.
Both reusability and scalability capture the modification cost on any of the temporal attributes of the system when more functionality is added. Reusability focuses on scheduling A(current) on top of A(legacy), while scalability put emphasizes on scheduling A(future) on top of A(current). In general the more detail that is available on the future modifications, the more scalable the schedule could be.
A formal mathematical formulation of the problem will be given, combining with a case study whose functionality and architecture will be modeled in Metropolis: A Design Environment for Heterogeneous Systems .
We would like to implement a SCHEDULER backend which takes a functionality/architecture graph as its inputs to calculate the resulting schedule.
We plan to use the following strategy: the backend converts the application model represented by Metropolis meta-model to AMPL, a Mathematical Modeling Language, input model description.
Then, we use AMPL's built-in Optimization solver to derive an optimal schedule.
Potential extension:
When the input size of the problem is getting bigger and bigger, the problem can not be solved by the existing optimization solver, we might be interested in designing heuristic s to do efficient scheduling.
Design and Integration of the general scheduling tool to Metropolis. Supporting such a design process and providing such a scheduling backend are of critical importance for current and future industrial practice, as the time interval between successive generations of a product is continuously decreasing, while the complexity due to increased sophistication of new functionality is growing rapidly.
Required Skill Set:
- Familiar with scheduling algorithm (real-time system scheduling algorithms is a plus)
- Java Programming (in the phase of integration)
Mentors: Sri Kanajan (General Motors Research)
Number of students: 2
Implementing Tipi Irregular Datapaths in FPGA Fabrics
Mentor: Scott Weber and Andrew MihalThe Tipi system provides a disciplined methodology for designing and deploying application-specific programmable datapaths. We have a code generation framework in place that produces basic synthesizable verilog from a structural Tipi model. However, the verilog we create is not well tuned to FPGAs. We want to take advantage of FPGA features such as block rams and fast carry chains by invoking Xilinx macros whenever possible. Your task is to improve the verilog code generator to produce excellent implementations on FPGAs. We have a Xilinx demo board and the required tools. Design Tipi library components that match the architectural features present in the FPGA. What kind of programmable machines are a good match for the capabilities of the FPGA?
Heterogeneous Models of Computation for Network Processing
Mentor: Andrew MihalThe Click Modular Router is a useful and intuitive framework for designing network processing applications. It combines a library of components with a model of computation to provide a good abstraction for a complex, concurrent application domain. However, the system of push and pull ports, queues, and agnostic elements is only one facet of the Click framework. These abstractions are good for the data plane of a router. Click does not provide a good abstraction for the control plane of a router. There is a great deal of computation that Click implements in C++ that hides beneath the push/pull interaction abstraction. For example, it is assumed that packet headers and data payloads are separated and reassembled outside of the Click model. Also, elements are able to probe the state of upstream and downstream queues using a hidden communication mechanism. In this project, you will develop model of computation abstractions to capture these important facets of network processing applications. We seek to describe all of the different styles of computation that Click sweeps under the rug using formal models. You will implement these formalisms using model transformations in the Cairn environment.
Implementation of Simulation based Deadlock Analysis in Metropolis
Goal:
This project is to implement an automatic simulation based deadlock analysis tool in Metropolis, more specifically, in the SystemC simulation backend. During a simulation of a design, a dependency graph is dynamically built and updated as the dependency state of the system changes, i.e. as one or more processes in the system are blocked from running or released from blocking. Whenever one or more processes are blocked from running, the deadlock detection algorithm is invoked to search the DSDG for any deadlock situation. In other words, the deadlock detection mechanism is implemented as a simulation monitor to simultaneously check deadlocks in the simulation.
Procedures:
1. Study and understand Metropolis Meta-Model, especially the synchronization constructs, await, synch, interface function and etc.
2. Study and understand Metropolis simulation mechanism, i.e. the SystemC simulation backend.
3. Follow the general ideas, data structures and algorithms in [1], and program for the automatic deadlock analysis tool in Metropolis.
4. Use a realistic example to test the tool.
References:
[1] X. Chen, H. Hsieh, A. Davare, A. Sangiovanni-Vincentelli, Y. Watanabe. "Simulation based Deadlock Analysis for System Level Designs", Submitted to DATE '05, located under metroworkspace/papers/DATE05_DEADLOCK.
[2] Manual of Metropolis Meta-Model
Mentor: Xi Chen - xichen@cs.ucr.edu (and maybe Guang Yang)
Architecture Model Refinement Based on Rapid Prototyping Information
Mentor(s): Haibo Zeng, Doug Densmore, Abhijit DavareThis project would involve taking an abstract architecture model developed in the Metropolis Design Environment and refining it to better reflect an architectural implementation on the Xilinx ML310 design platform. This would culminate with an updated model in Metropolis and a methodology to characterize performance capturing issues with Xilinx based architectures.
The steps involved in this investigation would be:
1. Take an application through the design process to the actual ML310 board.
2. Determine which behaviors relating to execution time are not captured by the current model provided in Metropolis. We expect these to be context switch and syncronization related.
3. Devise a scheme to incorporate those behaviors into the model.
4. Characterize those behaviors into general classes of behaviors and propose how to ensure that those behaviors are captured in subsequent modeling efforts.
The student hopefully has some background using the Xilinx FPGA toolflow and java programming experience. However neither of these are required.
For more information contact: densmore@eecs.berkeley.edu