Gsoc
Gsoc.Gsoc History
Hide minor edits - Show changes to output
Changed lines 93-94 from:
->The Ptolemy group is developing a code generator that uses template files to build C code from Ptolemy models. The current template effort synthesizes C code from certain Ptolemy II models ([[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/sdf/doc/body.htm |SDF]], [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |FSM]] and [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/hdf/doc/body.htm |HDF]]).
->PTIDES is a programming model targeting distributed real-time embedded systems The current code generator for PTIDES model does not yet support heterogeneous models, meaning no PTIDES actor can yet be refined by any other Ptolemy II models such as SDF, FSM, and HDF. Thus the goal of this project is to integrate PTIDES code generator with other models. Since any model that supports heterogeneity is likely to be big, an efficient implementations is needed to reduce the overhead introduced by high level abstraction of models. To address this we use partial evaluation as an optimized compilation technique for actor-oriented models. For more details see [[http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-8.html |Ptolemy Design Document]] (Vol.2, Chap.7).
->PTIDES is a programming model targeting distributed real-time embedded systems
to:
->The Ptolemy group is developing a code generator that uses template files to build C code from Ptolemy models. The current template effort synthesizes C code from certain Ptolemy II models ([[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/sdf/doc/body.htm |SDF]], [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |FSM]] and [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/hdf/doc/body.htm |HDF]]). For more details see [[http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-8.html |Ptolemy Design Document]] (Vol.2, Chap.7).
->A simpler idea for this project would be to implement code generator for [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/de/doc/body.htm | Discrete-Event]] models.
->A related but more advanced project would do the same for the PTIDES programming model which targets distributed real-time embedded systems. The current code generator for PTIDES model does not yet support heterogeneous models, meaning no PTIDES actor can yet be refined by any other Ptolemy II models such as SDF, FSM, and HDF. Thus the goal of this project is to integrate PTIDES code generator with other models. Since any model that supports heterogeneity is likely to be big, an efficient implementations is needed to reduce the overhead introduced by high level abstraction of models. To address this we use partial evaluation as an optimized compilation technique for actor-oriented models.
->A simpler idea for this project would be to implement code generator for [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/de/doc/body.htm | Discrete-Event]] models.
->A related but more advanced project would do the same for the PTIDES programming model which targets distributed real-time embedded systems. The current code generator for PTIDES model does not yet support heterogeneous models, meaning no PTIDES actor can yet be refined by any other Ptolemy II models such as SDF, FSM, and HDF. Thus the goal of this project is to integrate PTIDES code generator with other models. Since any model that supports heterogeneity is likely to be big, an efficient implementations is needed to reduce the overhead introduced by high level abstraction of models. To address this we use partial evaluation as an optimized compilation technique for actor-oriented models.
Changed line 100 from:
* '''Further Reading''': [[http://ptolemy.eecs.berkeley.edu/viptos/VIPTOS]], [[http://www.ece.umd.edu/~ankush/publications/varma-j2c-thesis.pdf |A Retargetable Optimizing Java-to-C Compiler for Embedded Systems]]
to:
* '''Further Reading''': [[http://chess.eecs.berkeley.edu/pubs/251.html | Code Generation with Partial Evaluation]], [[http://chess.eecs.berkeley.edu/pubs/401.html | Software Synthesis]]
Added lines 185-187:
[[http://ptolemy.eecs.berkeley.edu/viptos/ |VIPTOS]], [[http://www.ece.umd.edu/~ankush/publications/varma-j2c-thesis.pdf |A Retargetable Optimizing Java-to-C Compiler for Embedded Systems]]
Changed line 94 from:
->PTIDES is a programming model targeting distributed real-time embedded systems. Our approach defines "helper" classes associated with Ptolemy II actors (i.e. model components) that define the C code implementation for actors. The current code generator for PTIDES model does not yet support heterogeneous models, meaning no PTIDES actor can yet be refined by any other Ptolemy II models such as SDF, FSM, and HDF. Thus the goal of this project is to integrate PTIDES code generator with other models. Since any model that supports heterogeneity is likely to be big, an efficient implementations is needed to reduce the overhead introduced by high level abstraction of models. To address this we use partial evaluation as an optimized compilation technique for actor-oriented models. For more details see [[http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-8.html |Ptolemy Design Document]] (Vol.2, Chap.7).
to:
->PTIDES is a programming model targeting distributed real-time embedded systems. The current code generator for PTIDES model does not yet support heterogeneous models, meaning no PTIDES actor can yet be refined by any other Ptolemy II models such as SDF, FSM, and HDF. Thus the goal of this project is to integrate PTIDES code generator with other models. Since any model that supports heterogeneity is likely to be big, an efficient implementations is needed to reduce the overhead introduced by high level abstraction of models. To address this we use partial evaluation as an optimized compilation technique for actor-oriented models. For more details see [[http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-8.html |Ptolemy Design Document]] (Vol.2, Chap.7).
Changed lines 16-18 from:
''' *** 03/25/09: We added two new project ideas. Please scroll down towards the end of the page. *** '''
to:
''' ***** 03/25/09: We added two new project ideas. Please scroll down towards the end of the page. ***** '''
Changed lines 16-18 from:
to:
''' *** 03/25/09: We added two new project ideas. Please scroll down towards the end of the page. *** '''
Changed lines 16-18 from:
to:
"" 03/25/09: We added two new project ideas. Please scroll down towards the end of the page.""
Changed lines 16-18 from:
'''-> !! 03/25/09: We added two new project ideas. Please scroll down towards the end of the page.'''
to:
'''' 03/25/09: We added two new project ideas. Please scroll down towards the end of the page.''''
Changed lines 16-18 from:
''' !!! 03/25/09: We added two new project ideas. Please scroll down towards the end of the page.'''
to:
'''-> !! 03/25/09: We added two new project ideas. Please scroll down towards the end of the page.'''
Changed lines 15-16 from:
''' 03/25: We added two new project ideas. Please scroll down towards the end of the page.'''
to:
''' !!! 03/25/09: We added two new project ideas. Please scroll down towards the end of the page.'''
Changed lines 15-16 from:
to:
''' 03/25: We added two new project ideas. Please scroll down towards the end of the page.'''
Changed line 159 from:
!!!Project Idea 8
to:
!!!Project Ideas 8
Changed line 170 from:
!!!Project Idea 9
to:
!!!Project Ideas 9
Changed line 175 from:
->[[http://gnuradio.org/trac |GNU Radio]] provides a library of signal processing blocks and the glue to put the system together by creating a graph of blocks. It is primarily used as a platform for Software Defined Radio (radio partially implemented in software). The GNU Radio software is organized in a two-tier structure. All the performance-critical signal processing blocks are implemented in C++, while the higher-level glue code is done using Python. There is also a graphical environment tool, the [[http://www.gnuradio.org/trac/wiki/GNURadioCompanion |GNU Radio Companion]], which allows GNU Radio components to be put together graphically.
to:
->[[http://gnuradio.org/trac |GNU Radio]] provides a library of signal processing blocks and the glue code to put the system together by creating a graph of blocks. It is primarily used as a platform for Software Defined Radio (radio partially implemented in software). The GNU Radio software is organized in a two-tier structure. All the performance-critical signal processing blocks are implemented in C++, while the higher-level glue code is done using Python. There is also a graphical environment tool, the [[http://www.gnuradio.org/trac/wiki/GNURadioCompanion |GNU Radio Companion]], which allows GNU Radio components to be put together graphically.
Changed line 161 from:
* '''Title''': Simulation as Education Tool
to:
* '''Title''': Simulation as Educational Tool
Changed line 163 from:
->The objective of this project is to add features to Ptolemy in order to improve its capability of being used as an educational tool. Two roles would be involved, the instructor (docent, tutor, etc.) and the students. The instructor would pass some challenges to the students, giving some gaming aspect to Ptolemy, that could be in form of new models creation or modifications on existing models. The accomplishment of those challenges would be conditioned to some prerequisites, like time to complete a model, simulation time, number and types of actors on model, configuration of same parameters, set of output data generated by some actors and so on. It is also important the possibility to follow the students progress. Therefore, the instructor could check how many challenges some students accomplished and how was their production during a period. So, the main objective is to enable the Ptolemy to create and manage challenges to the user, transforming it in something more interactive, playful and educational.
to:
->The objective of this project is to add features to Ptolemy in order to improve its capability of being used as an educational tool. Two roles would be involved, the instructor (docent, tutor, etc.) and the students. The instructor would pass some challenges to the students, giving some gaming aspect to Ptolemy, that could be in the form of new models creation or modifications of the existing models. The accomplishment of these challenges would be conditioned to some prerequisites, like time to complete a model, simulation time, number and types of actors on model, configuration of same parameters, set of output data generated by some actors and so on. It is also important the possibility to follow the students progress. Therefore, the instructor could check how many challenges students accomplished and how was their production during a period. So, the main objective is to enable the Ptolemy to create and manage challenges to the user, transforming it in something more interactive, playful and educational.
Changed line 170 from:
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Software_defined_radio |Software Defined Radio]], [[http://en.wikipedia.org/wiki/Digital_Signal_Processing |Digital Signal Processing]], [[http://en.wikipedia.org/wiki/Source_code_generation |Code Generation]], [[http://en.wikipedia.org/wiki/Wireless_networks |Wireless Networks]]
to:
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/GNU_Radio |GNU Radio]], [[http://en.wikipedia.org/wiki/Software_defined_radio |Software Defined Radio]], [[http://en.wikipedia.org/wiki/Digital_Signal_Processing |Digital Signal Processing]], [[http://en.wikipedia.org/wiki/Source_code_generation |Code Generation]]
Changed line 174 from:
->GNU Radio provides a library of signal processing blocks and the glue to put the system together by creating a graph of blocks. It is primarily used as a platform for Software Defined Radio, radio partially implemented in software. . The GNU Radio software is organized in a two-tier structure. All the performance-critical signal processing blocks are implemented in C++, while the higher-level glue code is done using Python. There is also a graphical environment tool, the GNU Radio Companion, which allows GNU Radio components to be put together graphically.
to:
->[[http://gnuradio.org/trac |GNU Radio]] provides a library of signal processing blocks and the glue to put the system together by creating a graph of blocks. It is primarily used as a platform for Software Defined Radio (radio partially implemented in software). The GNU Radio software is organized in a two-tier structure. All the performance-critical signal processing blocks are implemented in C++, while the higher-level glue code is done using Python. There is also a graphical environment tool, the [[http://www.gnuradio.org/trac/wiki/GNURadioCompanion |GNU Radio Companion]], which allows GNU Radio components to be put together graphically.
Changed lines 158-165 from:
!!!Project
*
*
* '''Technical Details''':
->Compute WCET
* '''Further Reading''': [[http://osl.cs.uiuc.edu/~ksen/cute/ | jCute]] - A execution path analysis tool for Java, [[http://en.wikipedia.org/wiki/Max-plus_algebra | Max-plus algebra]]
to:
!!!Project Idea 8
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Educational_game |Educational Game]], [[http://en.wikipedia.org/wiki/Computer_simulation |Computer Simulation]]
* '''Mentors''': Alisson Brito
* '''Title''': Simulation as Education Tool
* '''Technical Details''':
->The objective of this project is to add features to Ptolemy in order to improve its capability of being used as an educational tool. Two roles would be involved, the instructor (docent, tutor, etc.) and the students. The instructor would pass some challenges to the students, giving some gaming aspect to Ptolemy, that could be in form of new models creation or modifications on existing models. The accomplishment of those challenges would be conditioned to some prerequisites, like time to complete a model, simulation time, number and types of actors on model, configuration of same parameters, set of output data generated by some actors and so on. It is also important the possibility to follow the students progress. Therefore, the instructor could check how many challenges some students accomplished and how was their production during a period. So, the main objective is to enable the Ptolemy to create and manage challenges to the user, transforming it in something more interactive, playful and educational.
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Educational_game |Educational Game]], [[http://en.wikipedia.org/wiki/Computer_simulation |Computer Simulation]]
* '''Mentors''': Alisson Brito
* '''Title''': Simulation as Education Tool
* '''Technical Details''':
->The objective of this project is to add features to Ptolemy in order to improve its capability of being used as an educational tool. Two roles would be involved, the instructor (docent, tutor, etc.) and the students. The instructor would pass some challenges to the students, giving some gaming aspect to Ptolemy, that could be in form of new models creation or modifications on existing models. The accomplishment of those challenges would be conditioned to some prerequisites, like time to complete a model, simulation time, number and types of actors on model, configuration of same parameters, set of output data generated by some actors and so on. It is also important the possibility to follow the students progress. Therefore, the instructor could check how many challenges some students accomplished and how was their production during a period. So, the main objective is to enable the Ptolemy to create and manage challenges to the user, transforming it in something more interactive, playful and educational.
Added lines 165-176:
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn more about how Ptolemy works inside. Learn gaming and educational issues. Learn to contribute on a specific subject in a large project (Ptolemy II). Practice Java programming and algorithm design.
* '''Benefits to the Community''': An educational tool to assist docents and students to learn more abstract subjects that are often not trivial to understand just by books.
!!!Project Idea 9
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Software_defined_radio |Software Defined Radio]], [[http://en.wikipedia.org/wiki/Digital_Signal_Processing |Digital Signal Processing]], [[http://en.wikipedia.org/wiki/Source_code_generation |Code Generation]], [[http://en.wikipedia.org/wiki/Wireless_networks |Wireless Networks]]
* '''Mentors''': Slobodan Matic
* '''Title''': GNU Radio with Ptolemy
* '''Technical Details''':
->GNU Radio provides a library of signal processing blocks and the glue to put the system together by creating a graph of blocks. It is primarily used as a platform for Software Defined Radio, radio partially implemented in software. . The GNU Radio software is organized in a two-tier structure. All the performance-critical signal processing blocks are implemented in C++, while the higher-level glue code is done using Python. There is also a graphical environment tool, the GNU Radio Companion, which allows GNU Radio components to be put together graphically.
->The goal of this project would be to make Ptolemy a front-end for GNU Radio, i.e., to provide Ptolemy with the features of the GNU Radio Companion tool. A student would start with a certain set of most frequently used blocks in GNU Radio (out of about 100 blocks) and see how they match with already existing Ptolemy actors for signal processing. Some of the Ptolemy actors or GNU Radio blocks would potentially have to be adapted. The project would then focus on building the Ptolemy infrastructure that would generate GNU Radio glue code for a model built from the selected set of actors. Another idea would be to make Ptolemy a back-end for GNU radio programs, i.e., to make software oscilloscope or spectrum analyzer tools using existing Ptolemy code.
* '''Skills''': Java [required], C++ or Python [recommended]
* '''Benefits to the Student''': Learn more about how Ptolemy works inside. Learn gaming and educational issues. Learn to contribute on a specific subject in a large project (Ptolemy II). Practice Java programming and algorithm design.
* '''Benefits to the Community''': An educational tool to assist docents and students to learn more abstract subjects that are often not trivial to understand just by books.
!!!Project Idea 9
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Software_defined_radio |Software Defined Radio]], [[http://en.wikipedia.org/wiki/Digital_Signal_Processing |Digital Signal Processing]], [[http://en.wikipedia.org/wiki/Source_code_generation |Code Generation]], [[http://en.wikipedia.org/wiki/Wireless_networks |Wireless Networks]]
* '''Mentors''': Slobodan Matic
* '''Title''': GNU Radio with Ptolemy
* '''Technical Details''':
->GNU Radio provides a library of signal processing blocks and the glue to put the system together by creating a graph of blocks. It is primarily used as a platform for Software Defined Radio, radio partially implemented in software. . The GNU Radio software is organized in a two-tier structure. All the performance-critical signal processing blocks are implemented in C++, while the higher-level glue code is done using Python. There is also a graphical environment tool, the GNU Radio Companion, which allows GNU Radio components to be put together graphically.
->The goal of this project would be to make Ptolemy a front-end for GNU Radio, i.e., to provide Ptolemy with the features of the GNU Radio Companion tool. A student would start with a certain set of most frequently used blocks in GNU Radio (out of about 100 blocks) and see how they match with already existing Ptolemy actors for signal processing. Some of the Ptolemy actors or GNU Radio blocks would potentially have to be adapted. The project would then focus on building the Ptolemy infrastructure that would generate GNU Radio glue code for a model built from the selected set of actors. Another idea would be to make Ptolemy a back-end for GNU radio programs, i.e., to make software oscilloscope or spectrum analyzer tools using existing Ptolemy code.
* '''Skills''': Java [required], C++ or Python [recommended]
Added lines 178-190:
* '''Benefits to the Student''': Learn compilation and code generation techniques for graphical block-oriented languages. Learn basic signal processing building blocks. Learn to use source version control systems.
* '''Benefits to the Community''': Expand the space of open-source visual programming environments for software radio.
(:if false:)
!!!Project Idea 6
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Worst-case_execution_time | Worst-Case Execution Time]], [[http://en.wikipedia.org/wiki/Program_analysis_%28computer_science%29 | Program Analysis]], [[http://en.wikipedia.org/wiki/Max-plus_algebra | Max-plus algebra]]
* '''Mentors''': Thomas Feng / Jia Zou / Slobodan Matic
* '''Title''': A program analysis tool for WCET (worst-case execution time) of Ptolemy actors written in Java.
* '''Technical Details''':
->Compute WCET as the maximum execution time on all the execution paths of an actor, assuming that the WCET of atomic operations used by the actor, such as library function calls, is given. Use jCute to discover all feasible execution paths of the actor's fire() method, which is invoked on each firing. Combine the information obtained by separately analyzing each path with a max-plus algebra to produce the WCET of a firing of the actor.
* '''Further Reading''': [[http://osl.cs.uiuc.edu/~ksen/cute/ | jCute]] - A execution path analysis tool for Java, [[http://en.wikipedia.org/wiki/Max-plus_algebra | Max-plus algebra]]
* '''Skills''': Java [required]
* '''Level''': Intermediate
* '''Benefits to the Community''': Expand the space of open-source visual programming environments for software radio.
(:if false:)
!!!Project Idea 6
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Worst-case_execution_time | Worst-Case Execution Time]], [[http://en.wikipedia.org/wiki/Program_analysis_%28computer_science%29 | Program Analysis]], [[http://en.wikipedia.org/wiki/Max-plus_algebra | Max-plus algebra]]
* '''Mentors''': Thomas Feng / Jia Zou / Slobodan Matic
* '''Title''': A program analysis tool for WCET (worst-case execution time) of Ptolemy actors written in Java.
* '''Technical Details''':
->Compute WCET as the maximum execution time on all the execution paths of an actor, assuming that the WCET of atomic operations used by the actor, such as library function calls, is given. Use jCute to discover all feasible execution paths of the actor's fire() method, which is invoked on each firing. Combine the information obtained by separately analyzing each path with a max-plus algebra to produce the WCET of a firing of the actor.
* '''Further Reading''': [[http://osl.cs.uiuc.edu/~ksen/cute/ | jCute]] - A execution path analysis tool for Java, [[http://en.wikipedia.org/wiki/Max-plus_algebra | Max-plus algebra]]
* '''Skills''': Java [required]
* '''Level''': Intermediate
March 20, 2009, at 07:57 AM
by - Don't apply
Changed lines 31-32 from:
-> If you would like to contact us, but rather not use the group, please send an email to '''gsoc@chess.eecs.berkeley.edu''' .
to:
-> If you would like to contact us, but rather not use the group, please send an email to @@gsoc at chess dot eecs dot berkeley dot edu@@ .
-> If you are interested in applying for a Google Summer of Code position please '''do not request membership on this website at this time'''. Website accounts will be created after applicants have been selected.
-> If you are interested in applying for a Google Summer of Code position please '''do not request membership on this website at this time'''. Website accounts will be created after applicants have been selected.
Changed lines 31-32 from:
-> If you would like to contact us, but rather not use the group, please send an email to '''gsoc@ptolemy.eecs.berkeley.edu''' .
to:
-> If you would like to contact us, but rather not use the group, please send an email to '''gsoc@chess.eecs.berkeley.edu''' .
Changed line 48 from:
* '''Title''': Building Ptides Models or/and Infrastructure
to:
* '''Title''': Modeling and/or Ptolemy Infrastructure
Changed lines 147-148 from:
* '''Technical Details''': ERG (Event Relationship Graphs) is a formal language for discrete-event simulation. It has a visual syntax similar to FSM ([[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |Finite State Machines]]), but it is much more expressive. Model verification of ERG is a challenging problem because the event queue in a model is potentially unbounded. This project aims to build a prototype for model verification. For a subset of models, it can be statically checked whether the event queue is bounded, and whether one event is causally dependent on another. The task of this project is to identify such a subset, and create a verification tool that can handle it.
to:
* '''Technical Details''':
->ERG (Event Relationship Graphs) is a formal language for discrete-event simulation. It has a visual syntax similar to FSM ([[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |Finite State Machines]]), but it is much more expressive. Model verification of ERG is a challenging problem because the event queue in a model is potentially unbounded. This project aims to build a prototype for model verification. For a subset of models, it can be statically checked whether the event queue is bounded, and whether one event is causally dependent on another. The task of this project is to identify such a subset, and create a verification tool that can handle it.
->ERG (Event Relationship Graphs) is a formal language for discrete-event simulation. It has a visual syntax similar to FSM ([[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |Finite State Machines]]), but it is much more expressive. Model verification of ERG is a challenging problem because the event queue in a model is potentially unbounded. This project aims to build a prototype for model verification. For a subset of models, it can be statically checked whether the event queue is bounded, and whether one event is causally dependent on another. The task of this project is to identify such a subset, and create a verification tool that can handle it.
March 16, 2009, at 04:35 PM
by - Copied from home page
Changed lines 1-6 from:
<a href="http://code.google.com/soc/">Google Summer of Code</a>.
<p>This page is for our current interactions.
<p>See <a href="http://chess.eecs.berkeley.edu/gsoc/wiki">The Ptolemy/GSOC Wiki</a> for details.
to:
!! Ptolemy Google Summer of Code (GSoC)
'''Contents'''
* '''Introduction'''
** '''Ptolemy'''
(:if false:)
** '''Ptides'''
** '''Model Transformation'''
(:ifend:)
* '''Google Summer of Code 2009'''
** '''Contact'''
** '''Instructions for Student Applicants'''
** '''Project Ideas'''
!!Introduction
!!!Ptolemy
->The [[http://ptolemy.eecs.berkeley.edu|Ptolemy project]] studies modeling, simulation, and design of concurrent, real-time, embedded systems. The focus is on assembly of concurrent components. The key underlying principle in the project is the use of well-defined models of computation that govern the interaction between components. A major problem area being addressed is the use of heterogeneous mixtures of models of computation. A software system called [[http://ptolemy.eecs.berkeley.edu/ptolemyII|Ptolemy II]] is being constructed in Java. Ptolemy II differs from other commonly used graphical block-diagram languages in that they typically support only one model of computation. In addition, Ptolemy II is a more open architecture in that its infrastructure is open source, and the interfaces to the core mechanisms in the software are published and documented.
(:if false:)
!!!Ptides
->The [[http://chess.eecs.berkeley.edu/ptides|Programming temporally integrated distributed embedded systems (PTIDES)]] concurrency model uses discrete-event models as programming specifications for distributed real-time systems and extends discrete-event models with the capability of mapping certain events to physical time. We use model time to define execution semantics and add constraints that bind certain model time events to physical time. We limit the relationship of model time to physical time to only those circumstances where this relationship is needed. This approach enables an execution model that permits out of order processing of events without sacrificing determinacy and without requiring backtracking.
!!!Model Transformation
->The model transformation technique based on graph rewriting helps to systematically modify and manage complex actor-based models. A transformation rule specifies a "atomic" transformation that can be applied to a model with a part of it matching to the pattern of the transformation rule. By combining transformation rules in a Ptolemy model, more complicated transformation can be created. Applications of model transformation include but are not limited to model optimization and simplification, design reuse, behavior-preserving conversion between formalisms, etc.
(:ifend:)
!!Google Summer of Code 2009
!!!Contact
-> A preferred means of communication with us during the application period would be the '''Ptolemy GSoC 2009''' group at Google Groups. That way, everyone can benefit from the discussion.
-> '''http://groups.google.com/group/ptolemy-gsoc-2009'''
-> If you would like to contact us, but rather not use the group, please send an email to '''gsoc@ptolemy.eecs.berkeley.edu''' .
!!!Instructions for Student Applicants
-> We do not use a specific application template for this program. However, this is what we will be looking for in an application:
** Summary of your previous programming projects (open-source/class/research).
** Summary of your university-level education.
** What interests you about our projects? What would you like to learn or improve?
** What other activities (exams, vacation, etc.) you plan for the summer? How much of your time you think you can devote to project per week, per day?
!!!Project Ideas
!!!Project Ideas 1
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]], [[http://en.wikipedia.org/wiki/Real-time |Real-time]], [[http://en.wikipedia.org/wiki/Distributed_systems |Distributed]], [[http://en.wikipedia.org/wiki/Sensor_networks |Sensor Networks]]
(:if false:)
, [[http://en.wikipedia.org/wiki/Sound_synthesis |Sound Synthesis]], [[http://en.wikipedia.org/wiki/Algorithmic_trading |Algorithmic Trading]]
(:ifend:)
* '''Mentors''': Christopher Brooks / Slobodan Matic
* '''Title''': Building Ptides Models or/and Infrastructure
* '''Technical Details''':
->- The best code developers are typically users first. Select a discrete-event system or application of your choice and model it in Ptolemy. In discrete-event models, the components interact via signals that consist of time-stamped events. Here are some ideas in Ptolemy: [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/de/doc/body.htm|Timing Paradox]] or [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/wireless/doc/body.htm |Wireless Networks]]. Start with [[http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-129.html |Ptolemy Tutorial]]. Think about using [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/de/doc/body.htm | Discrete-Event]], [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |Modal]] or [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/dde/doc/body.htm |Distributed Discrete-Event]] models of computation.
(:if false:)
, and from the web, [[http://osw.sourceforge.net/ |Sound Processing]] or [[http://www.automatedtrader.net/automated-trader-technology-workshop-596.xhtm |Algorithmic Trading]].
(:ifend:)
->- Projects for GSoC 2009 could involve modeling of networking protocols in the Ptolemy environment. For instance, [[http://en.wikipedia.org/wiki/TTEthernet |TTEthernet]], [[http://en.wikipedia.org/wiki/Flexray |Flexray]], or [[http://en.wikipedia.org/wiki/Precision_Time_Protocol |Precision Time Protocol]]. An interesting approach would be to integrate or port to Ptolemy open source code developed within the [[http://en.wikipedia.org/wiki/Omnet%2B%2B |OMNET++]] project.
->- A version of the [[http://chess.eecs.berkeley.edu/ptides/ |Ptides]] model of computation for Real-time and Distributed systems based on the DE model will be available during summer. Build Ptides components that are not yet supported. Start with [[http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-9.html |Ptolemy Design Document]](Vol.3, Chap.1,4,7). Some ideas include implementing and testing different event schedulers or modeling standard networking components within Ptides.
(:if false:)The created models will both test the infrastructure and user interfaces of Ptides and serve as examples for other models.(:ifend:)
* '''Further Reading''': [[http://chess.eecs.berkeley.edu/pubs/221/RealTimeComputing_RTAS_Lee.pdf |Real-Time Computing]], [[http://ptolemy.eecs.berkeley.edu/presentations/06/PtidesOnIEEE158806.pdf |Ptides]]
* '''Skills''': Block-diagram language (e.g. Matlab) or Java [recommended]
* '''Level''': Beginning - Advanced
* '''Benefits to the Student''': Model and study properties of a system of interest. Get to know and build upon Ptolemy infrastructure. Learn to use source version control systems.
* '''Benefits to the Community''': Expand open computational models and open-architecture design frameworks.
* '''Comments''': More than one student.
!!!Project Ideas 2
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Distributed_systems |Distributed]], [[http://en.wikipedia.org/wiki/Real-time |Real-time]], [[http://en.wikipedia.org/wiki/Real-time_operating_system |Real-Time Operating Systems]], [[http://en.wikipedia.org/wiki/Task_scheduling |Task Scheduling]], [[http://en.wikipedia.org/wiki/Event_queue |Event Queue]]
* '''Mentors''': Slobodan Matic / Jia Zou
* '''Title''': PtidyOS Development
* '''Technical Details''':
->In this project we will be working on PtidyOS, a novel lightweight embedded operating system based on PTIDES, a programming model for distributed real-time systems. In PtidyOS, all event processing is done in interrupt service routines, and we only use interrupts to ensure correct mutually exclusive accesses to memory. Our approach combines PTIDES semantics with traditional scheduling methods. The first implementation leverages Earliest-Deadline First scheduling algorithm and guarantees correct event order defined by PTIDES. It is deployed on an ARM based micro-controller.
->We would like this project to address the distributed character of PtidyOS. Our implementation testbed will probably consist of micro-controllers synchronized in time using [[http://ptpd.sourceforge.net/ |PTPd]], an open-source implementation of the [[http://en.wikipedia.org/wiki/Precision_Time_Protocol |Precision Time Protocol]]. Another idea for this project could be to implement efficient event queue structures or experiment with other scheduling algorithms for real-time processing of events. This project may build on recent open-source real-time projects, such as [[http://shark.sssup.it/ |S.Ha.R.K.]]: Soft Hard Real-Time Kernel (for dynamic priority schedulers) or [[http://www.ocera.org/ |OCERA]]: Open Components for Embedded Real-time Applications (for resource reservation or publish/subscribe middleware mechanisms).
* '''Further Reading''': [[(Attach:)PtidyOS]], [[http://portal.acm.org/citation.cfm?doid=63039.63045 |Calendar queues]]
* '''Skills''': C [required]
* '''Level''': Intermediate - Advanced
* '''Benefits to the Student''': Learn about embedded middleware, discrete-event model semantics and real-time event processing. Learn to use source version control systems.
* '''Benefits to the Community''': Expand the space of open-source real-time embedded and middleware solutions.
* '''Comments''': Visit to UC Berkeley recommended.
(:if false:)
[[http://en.wikipedia.org/wiki/Concurrent_computing |Concurrent Computing]],
, [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]]
Event Scheduler for Real-time Event Processing
[[http://www.redhat.com/f/pdf/mrg/mrg_realtime_whitepaper.pdf |MRG Realtime]], [[http://www.oreilly.com/catalog/linuxkernel/chapter/ch10.html |Linux: Process Scheduling]],(:ifend:)
!!!Project Ideas 3
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]], [[http://en.wikipedia.org/wiki/Source_code_generation |Code Generation]]
* '''Mentors''': Jia Zou / Slobodan Matic
* '''Title''': C Code Generation for Ptides Models
* '''Technical Details''':
->The Ptolemy group is developing a code generator that uses template files to build C code from Ptolemy models. The current template effort synthesizes C code from certain Ptolemy II models ([[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/sdf/doc/body.htm |SDF]], [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |FSM]] and [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/hdf/doc/body.htm |HDF]]).
->PTIDES is a programming model targeting distributed real-time embedded systems. Our approach defines "helper" classes associated with Ptolemy II actors (i.e. model components) that define the C code implementation for actors. The current code generator for PTIDES model does not yet support heterogeneous models, meaning no PTIDES actor can yet be refined by any other Ptolemy II models such as SDF, FSM, and HDF. Thus the goal of this project is to integrate PTIDES code generator with other models. Since any model that supports heterogeneity is likely to be big, an efficient implementations is needed to reduce the overhead introduced by high level abstraction of models. To address this we use partial evaluation as an optimized compilation technique for actor-oriented models. For more details see [[http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-8.html |Ptolemy Design Document]] (Vol.2, Chap.7).
->Test the implementation on simple demo models with a limited actor library. The generated code could be targeted for an embedded micro-controller used in the Ptolemy group.
(:if false:)
->In this project we would like to build the same feature for the [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/de/doc/body.htm |DE]] models. In the first iteration all models could use the same (manually written) event scheduler and user would provide C code functionality for all actors. More efficient implementations will have to reduce the overhead introduced by high level abstraction of models.
This project may lead to code generation for real-time [[http://chess.eecs.berkeley.edu/ptides/ |Ptides]] models and other research efforts.
(:ifend:)
* '''Further Reading''': [[http://ptolemy.eecs.berkeley.edu/viptos/ |VIPTOS]], [[http://www.ece.umd.edu/~ankush/publications/varma-j2c-thesis.pdf |A Retargetable Optimizing Java-to-C Compiler for Embedded Systems]]
* '''Skills''': Java, C [required]
* '''Level''': Intermediate - Advanced
* '''Benefits to the Student''': Learn compilation and code generation techniques for graphical block-oriented languages. Learn about discrete-event model semantics and implementation. Learn to use source version control systems.
* '''Benefits to the Community''': Broaden the space of open-source C code generators from higher level languages.
* '''Comments''': High importance to us.
!!!Project Ideas 4
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Model_Driven_Engineering |Model_Driven_Engineering]], [[http://en.wikipedia.org/wiki/Real-time_operating_system |Real-Time Operating Systems]], [[http://en.wikipedia.org/wiki/Scheduling_(computing) |Scheduling]]
* '''Mentors''': Slobodan Matic / Jia Zou
* '''Title''': Performance Analysis Tool for Ptolemy
* '''Technical Details''':
->Model-based design and languages are gaining traction in industrial practice as evidenced by commercial tools such as [[http://en.wikipedia.org/wiki/Simulink |Simulink]]/[[http://www.mathworks.com/products/rtw/ |Real-Time Workshop]], [[http://en.wikipedia.org/wiki/Labview |LabVIEW]] or [[http://en.wikipedia.org/wiki/Labview |Rhapsody]]. The development tools are more often designed with support for performance requirements, such as latencies and buffer sizes of components. For instance, models (programs) can be extended with timing, activation and distribution properties of components, and schedulability analysis can be performed to certify that real-time constraints can be met on a certain platform. A more refined analysis would take into account computation and communication times as well as timing properties of the input signals. The goal of this project is not to define new techniques for analyzing real-time and embedded systems, but to integrate already existing ones into the Ptolemy design environment.
->A potential GSoC project might apply recent compositional performance analysis techniques, such as open-source [[http://www.mpa.ethz.ch/Rtctoolbox/Overview |Real-Time Calculus]] or event-flow based [[http://www.symtavision.com/symtas.html |SymTA/S]]. Another approach may be based on techniques developed in the open-source project [[http://mast.unican.es/ |MAST]].
* '''Further Reading''': [[ftp://ftp.tik.ee.ethz.ch/pub/people/psimon/publications/PWTHSHREG08.pdf |Performance Analysis Hard Real-Time Systems]]
* '''Skills''': Java [required]
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn model-based design tools. Explore certain performance and schedulability analysis techniques. Learn to use source version control systems.
* '''Benefits to the Community''': Expand the space of open-source performance analysis tools.
* '''Comments''': Research potential.
!!!Project Ideas 5
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Distributed_systems |Distributed]], [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]], [[http://en.wikipedia.org/wiki/Concurrent_computing |Concurrent Computing]], [[http://en.wikipedia.org/wiki/Multi-core |Multi-Core]]
* '''Mentors''': Jia Zou / Slobodan Matic
* '''Title''': Distributed Discrete-Event Simulator
* '''Technical Details''':
->The number of distributed event processing applications is increasing. Start with the discussion of related implementation problems for a distributed discrete-event (DDE) [[http://www.cs.wustl.edu/~kjg/CS333_SP97/devs.html |example]]. Ptolemy also comes with the [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/dde/doc/body.htm |DDE]] domain. The objective of this project is to build infrastructure for distributed event processing that will subsequently be used in other projects. This approach could build on the code already developed during GSoC 2008.
->A student could implement discrete-event simulator distributed over locally connected servers. S/he would program in C or C++ most likely using [[http://www.redhat.com/rhel/ |Red Hat Enterprise Linux]]. We plan to experiment with the [[http://www.redhat.com/mrg/messaging/ |Messaging]] component of the Red Hat [[http://www.redhat.com/mrg/ |MRG]] framework that implements open standard protocol [[http://en.wikipedia.org/wiki/Advanced_Message_Queuing_Protocol |AMQP]]. The other approach in a similar setting could build upon recent open-source projects such as [[http://dre.sourceforge.net/ |DREAM]]: Distributed Real-time Embedded Analysis Method. Another interesting idea with research potential would be to build an efficient simulator on a multi-core processor. It could also leverage related enhancements of 2.6 Linux kernels. Test on a simple distributed discrete-event application of interest.
* '''Further Reading''': [[http://portal.acm.org/citation.cfm?id=84545&dl=ACM&coll=portal |Parallel Discrete Event Simulation]], [[http://oss.intel.com/pdf/mclinux.pdf |Multi-Core and Linux]]
* '''Skills''': C or C++ [required]
* '''Level''': Intermediate - Advanced
* '''Benefits to the Student''': Learn to program distributed and/or parallel applications. Learn about discrete-event model semantics and implementation. Learn to use source version control systems.
* '''Benefits to the Community''': Increase the efficiency of open-source parallel discrete-event simulation/execution platforms.
* '''Comments''': More than one student. Research potential.
!!!Project Ideas 6
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]], [[http://en.wikipedia.org/wiki/Event_queue |Event Queue]], [[http://en.wikipedia.org/wiki/Real-Time_Java |Real-Time Java]], [[http://en.wikipedia.org/wiki/Concurrent_computing |Concurrent Computing]]
* '''Mentors''': Jia Zou / Slobodan Matic
* '''Title''': Java Discrete-Event or Ptides Execution Platform
* '''Technical Details''':
->There are a lot of open-source discrete-event ''simulation'' [[http://www.topology.org/soft/sim.html |frameworks]]. Much less work has been done in adapting these models as an ''execution'' platform for embedded software. Such a platform has to take into account real-time interaction with the environment. In this project a student could adapt the current implementation of Ptolemy [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/de/doc/body.htm |Discrete-Event]] or [[http://chess.eecs.berkeley.edu/ptides/ |Ptides]] simulation frameworks. This project will not address the distributed aspects of Ptides models. The student would program in Java and test on [[http://www.redhat.com/rhel/ |Red Hat Enterprise Linux]]. We plan to experiment with the [[http://www.redhat.com/mrg/realtime/ |Realtime]] component of the Red Hat [[http://www.redhat.com/mrg/ |MRG]] framework. If standard Java programming model is used, the student will have access to the [[http://www-306.ibm.com/software/webservers/realtime/ |IBM WebSphere Real Time]] platform that performs automatic garbage collection. Other approaches could use more difficult programming models according to the [[http://www.rtsj.org/ |Real-Time Specification for Java]]. Debug using Eclipse based [[http://domino.research.ibm.com/comm/research_projects.nsf/pages/metronome.tenedor.html |Tuning Fork]] visualization tool. Test on a simple discrete-event application of interest.
* '''Further Reading''': [[http://www.redhat.com/f/pdf/mrg/mrg_realtime_whitepaper.pdf |MRG Realtime]], [[http://java.sun.com/developer/technicalArticles/Interviews/Bollella_qa2.html |RTSJ]], [[http://chess.eecs.berkeley.edu/pubs/221/RealTimeComputing_RTAS_Lee.pdf |Ptides]] (from slide 32)
* '''Skills''': Java [required], JNI [recommended]
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn high-level real-time programming in Java. Learn about discrete-event model semantics and implementation. Learn to use source version control systems.
* '''Benefits to the Community''': Advance real-time programming under Java and Linux.
* '''Comments''': Visit to UC Berkeley recommended.
!!!Project Ideas 7
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]], [[http://en.wikipedia.org/wiki/Formal_language |Formal Language]], [[http://en.wikipedia.org/wiki/Finite_state_machine |Finite State Machine]]
* '''Mentors''': Thomas Feng / Slobodan Matic
* '''Title''': Model Verification
* '''Technical Details''': ERG (Event Relationship Graphs) is a formal language for discrete-event simulation. It has a visual syntax similar to FSM ([[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |Finite State Machines]]), but it is much more expressive. Model verification of ERG is a challenging problem because the event queue in a model is potentially unbounded. This project aims to build a prototype for model verification. For a subset of models, it can be statically checked whether the event queue is bounded, and whether one event is causally dependent on another. The task of this project is to identify such a subset, and create a verification tool that can handle it.
* '''Further Reading''': [[http://www.google.com/url?sa=t&source=web&ct=res&cd=1&url=http%3A%2F%2Fportal.acm.org%2Fcitation.cfm%3Fid%3D358460&ei=Icq-SZnaE4mMsAOy3tiwDA&usg=AFQjCNEkJzC_lAk56Yjc8JX18TuctkiN-w&sig2=rl71NW0-pfLQunutQsO6KA |Simulation modeling with event graphs]]
* '''Skills''': Java [required], formal languages and verification [preferred]
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn event-oriented modeling. Learn model verification techniques. Learn to contribute on a specific subject in a large project (Ptolemy II). Practice Java programming and algorithm design.
* '''Benefits to the Community''': A prototype of a model verification tool that can be easily extended to solve general problems.
* '''Comments''': Visit to UC Berkeley recommended.
(:if false:)
!!!Project Idea 6
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Worst-case_execution_time | Worst-Case Execution Time]], [[http://en.wikipedia.org/wiki/Program_analysis_%28computer_science%29 | Program Analysis]], [[http://en.wikipedia.org/wiki/Max-plus_algebra | Max-plus algebra]]
* '''Mentors''': Thomas Feng / Jia Zou / Slobodan Matic
* '''Title''': A program analysis tool for WCET (worst-case execution time) of Ptolemy actors written in Java.
* '''Technical Details''':
->Compute WCET as the maximum execution time on all the execution paths of an actor, assuming that the WCET of atomic operations used by the actor, such as library function calls, is given. Use jCute to discover all feasible execution paths of the actor's fire() method, which is invoked on each firing. Combine the information obtained by separately analyzing each path with a max-plus algebra to produce the WCET of a firing of the actor.
* '''Further Reading''': [[http://osl.cs.uiuc.edu/~ksen/cute/ | jCute]] - A execution path analysis tool for Java, [[http://en.wikipedia.org/wiki/Max-plus_algebra | Max-plus algebra]]
* '''Skills''': Java [required]
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn to use an automatic path exploration tool, and learn program analysis with path exploration.
* '''Benefits to the Community''': Provide a mechanism to automatically analyze WCET for certain kind of structured Java code, which is essential to real-time guarantees.
!!!Project Idea 7
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Model_transformation | Model Transformation]], [[http://en.wikipedia.org/wiki/Subgraph_isomorphism | Subgraph Isomorphism Problem]]
* '''Mentors''': Christopher Brooks / Thomas Feng
* '''Title''': An extension to the current model transformation tool in the Ptolemy framework to support imprecise matching to the user-defined graph pattern.
* '''Technical Details''':
->It is very useful to specify a pattern that allows structural variance in it, such as a one that matches a variable number of interconnected nodes. The current implementation does not support this because the number of nodes must be known and fixed at design time. The student will develop a visual syntax for the pattern designer to specify this variance in the structure. The student will also extend the model transformation tool to perform pattern matching on this kind of specifications, and apply transformation on the matched model parts.
* '''Further Reading''': [[http://www.eecs.berkeley.edu/~tfeng/transformation.html | Model Transformation in Ptolemy]]
* '''Skills''': Java [required]
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn the basic techniques for model transformation and graph rewriting. Creatively develop a useful algorithm.
* '''Benefits to the Community''': Develop a more flexible pattern matching algorithm for graph rewriting.
* '''Comments''': Research potential.
!!!Project Idea 8
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Model_transformation | Model Transformation]], [[http://en.wikipedia.org/wiki/Subclass_%28computer_science%29 | Subclassing]], [[http://en.wikipedia.org/wiki/Actor_model | Actor Model]]
* '''Mentors''': Christopher Brooks / Thomas Feng
* '''Title''': Bring the concept of object-oriented programming (OOP) to the modeling world with actor-oriented subclassing.
* '''Technical Details''':
->Model transformation based on graph transformation is a well-studied technique. However, it is creative to apply this technique to effectively reuse model designs in the sense of subclassing. Often times, a previous design needs to be slightly modified before it can be used in a new context. If the desired modification affects the structure of the design, then model transformation is a powerful backend to rely on. The student will extend the current implementation of model subclassing (which does not take advantage of model transformation) and implement extra checks to ensure properties to be preserved by a subclass model obtained by transformation. Example properties that the student will work on include input/output interface, expected data types of the input/output, behavioral properties expressed with interface automata, etc.
* '''Further Reading''': [[http://www.eecs.berkeley.edu/~tfeng/transformation.html | Model Transformation in Ptolemy]], [[http://ptolemy.eecs.berkeley.edu/publications/papers/07/classesandInheritance/index.htm | Actor-Oriented Subclassing]], [[http://springerlink.metapress.com/content/w22e59m4ghb9ewac/ | Behavioral Types with Interface Automata]]
* '''Skills''': Java [required]
* '''Level''': Advanced
* '''Benefits to the Student''': Learn the basics of model checking and actor-oriented subclassing.
* '''Benefits to the Community''': Explore the idea of actor-oriented subclassing, which potentially improves the current approach of model reuse (mainly by composition of components).
* '''Comments''': Research potential.
!!!Project Idea 9
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Static_code_analysis | Static Code Analysis]]
* '''Mentors''': Man-kit Leung / Hiren Patel
* '''Title''': An environment for program analysis on C programs generated from the Ptolemy Code Generation Framework.
* '''Technical Details''':
->Traditional embedded programming almost always uses C as an entry language. This however, is tedious and difficult to implement correctly when applications mandate a certain degree of concurrency. As a result, the Ptolemy framework provides higher-level models of computation that aid in better managing the concurrency inherent in embedded system applications. It also provides a code generation framework to C from the Process Network and Synchronous Data Flow models of computation. Since these models of computation are untimed, no notion of time is inserted into the generated C code. However, many embedded systems have real-time requirements that need to be met. For eventual implementation on a platform, it is necessary to do program analysis on the generated C code to estimate execution bounds for real-time embedded systems. We'll focus on a potential SPARC v8 based architecture that will serve as a target platform for code generation from the Ptolemy Framework
* '''Further Reading''':
* '''Skills''': C [required], Static analysis experience [helpful]
* '''Level''': Advanced
* '''Benefits to the Student''': Extend understanding of program analysis on source compiled by GCC.
* '''Benefits to the Community''': Extension for Ptolemy's code generation framework for providing execution bounds for particular instruction set architectures for model-based embedded programming.
* '''Comments''': Research potential.
(:ifend:)
!!About pmwiki
A local copy of PmWiki's
documentation has been installed along with the software,
and is available via the [[PmWiki/documentation index]].
To continue setting up PmWiki, see [[PmWiki/initial setup tasks]].
The [[PmWiki/basic editing]] page describes how to create pages
in PmWiki. You can practice editing in the [[wiki sandbox]].
More information about PmWiki is available from http://www.pmwiki.org .
'''Contents'''
* '''Introduction'''
** '''Ptolemy'''
(:if false:)
** '''Ptides'''
** '''Model Transformation'''
(:ifend:)
* '''Google Summer of Code 2009'''
** '''Contact'''
** '''Instructions for Student Applicants'''
** '''Project Ideas'''
!!Introduction
!!!Ptolemy
->The [[http://ptolemy.eecs.berkeley.edu|Ptolemy project]] studies modeling, simulation, and design of concurrent, real-time, embedded systems. The focus is on assembly of concurrent components. The key underlying principle in the project is the use of well-defined models of computation that govern the interaction between components. A major problem area being addressed is the use of heterogeneous mixtures of models of computation. A software system called [[http://ptolemy.eecs.berkeley.edu/ptolemyII|Ptolemy II]] is being constructed in Java. Ptolemy II differs from other commonly used graphical block-diagram languages in that they typically support only one model of computation. In addition, Ptolemy II is a more open architecture in that its infrastructure is open source, and the interfaces to the core mechanisms in the software are published and documented.
(:if false:)
!!!Ptides
->The [[http://chess.eecs.berkeley.edu/ptides|Programming temporally integrated distributed embedded systems (PTIDES)]] concurrency model uses discrete-event models as programming specifications for distributed real-time systems and extends discrete-event models with the capability of mapping certain events to physical time. We use model time to define execution semantics and add constraints that bind certain model time events to physical time. We limit the relationship of model time to physical time to only those circumstances where this relationship is needed. This approach enables an execution model that permits out of order processing of events without sacrificing determinacy and without requiring backtracking.
!!!Model Transformation
->The model transformation technique based on graph rewriting helps to systematically modify and manage complex actor-based models. A transformation rule specifies a "atomic" transformation that can be applied to a model with a part of it matching to the pattern of the transformation rule. By combining transformation rules in a Ptolemy model, more complicated transformation can be created. Applications of model transformation include but are not limited to model optimization and simplification, design reuse, behavior-preserving conversion between formalisms, etc.
(:ifend:)
!!Google Summer of Code 2009
!!!Contact
-> A preferred means of communication with us during the application period would be the '''Ptolemy GSoC 2009''' group at Google Groups. That way, everyone can benefit from the discussion.
-> '''http://groups.google.com/group/ptolemy-gsoc-2009'''
-> If you would like to contact us, but rather not use the group, please send an email to '''gsoc@ptolemy.eecs.berkeley.edu''' .
!!!Instructions for Student Applicants
-> We do not use a specific application template for this program. However, this is what we will be looking for in an application:
** Summary of your previous programming projects (open-source/class/research).
** Summary of your university-level education.
** What interests you about our projects? What would you like to learn or improve?
** What other activities (exams, vacation, etc.) you plan for the summer? How much of your time you think you can devote to project per week, per day?
!!!Project Ideas
!!!Project Ideas 1
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]], [[http://en.wikipedia.org/wiki/Real-time |Real-time]], [[http://en.wikipedia.org/wiki/Distributed_systems |Distributed]], [[http://en.wikipedia.org/wiki/Sensor_networks |Sensor Networks]]
(:if false:)
, [[http://en.wikipedia.org/wiki/Sound_synthesis |Sound Synthesis]], [[http://en.wikipedia.org/wiki/Algorithmic_trading |Algorithmic Trading]]
(:ifend:)
* '''Mentors''': Christopher Brooks / Slobodan Matic
* '''Title''': Building Ptides Models or/and Infrastructure
* '''Technical Details''':
->- The best code developers are typically users first. Select a discrete-event system or application of your choice and model it in Ptolemy. In discrete-event models, the components interact via signals that consist of time-stamped events. Here are some ideas in Ptolemy: [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/de/doc/body.htm|Timing Paradox]] or [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/wireless/doc/body.htm |Wireless Networks]]. Start with [[http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-129.html |Ptolemy Tutorial]]. Think about using [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/de/doc/body.htm | Discrete-Event]], [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |Modal]] or [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/dde/doc/body.htm |Distributed Discrete-Event]] models of computation.
(:if false:)
, and from the web, [[http://osw.sourceforge.net/ |Sound Processing]] or [[http://www.automatedtrader.net/automated-trader-technology-workshop-596.xhtm |Algorithmic Trading]].
(:ifend:)
->- Projects for GSoC 2009 could involve modeling of networking protocols in the Ptolemy environment. For instance, [[http://en.wikipedia.org/wiki/TTEthernet |TTEthernet]], [[http://en.wikipedia.org/wiki/Flexray |Flexray]], or [[http://en.wikipedia.org/wiki/Precision_Time_Protocol |Precision Time Protocol]]. An interesting approach would be to integrate or port to Ptolemy open source code developed within the [[http://en.wikipedia.org/wiki/Omnet%2B%2B |OMNET++]] project.
->- A version of the [[http://chess.eecs.berkeley.edu/ptides/ |Ptides]] model of computation for Real-time and Distributed systems based on the DE model will be available during summer. Build Ptides components that are not yet supported. Start with [[http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-9.html |Ptolemy Design Document]](Vol.3, Chap.1,4,7). Some ideas include implementing and testing different event schedulers or modeling standard networking components within Ptides.
(:if false:)The created models will both test the infrastructure and user interfaces of Ptides and serve as examples for other models.(:ifend:)
* '''Further Reading''': [[http://chess.eecs.berkeley.edu/pubs/221/RealTimeComputing_RTAS_Lee.pdf |Real-Time Computing]], [[http://ptolemy.eecs.berkeley.edu/presentations/06/PtidesOnIEEE158806.pdf |Ptides]]
* '''Skills''': Block-diagram language (e.g. Matlab) or Java [recommended]
* '''Level''': Beginning - Advanced
* '''Benefits to the Student''': Model and study properties of a system of interest. Get to know and build upon Ptolemy infrastructure. Learn to use source version control systems.
* '''Benefits to the Community''': Expand open computational models and open-architecture design frameworks.
* '''Comments''': More than one student.
!!!Project Ideas 2
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Distributed_systems |Distributed]], [[http://en.wikipedia.org/wiki/Real-time |Real-time]], [[http://en.wikipedia.org/wiki/Real-time_operating_system |Real-Time Operating Systems]], [[http://en.wikipedia.org/wiki/Task_scheduling |Task Scheduling]], [[http://en.wikipedia.org/wiki/Event_queue |Event Queue]]
* '''Mentors''': Slobodan Matic / Jia Zou
* '''Title''': PtidyOS Development
* '''Technical Details''':
->In this project we will be working on PtidyOS, a novel lightweight embedded operating system based on PTIDES, a programming model for distributed real-time systems. In PtidyOS, all event processing is done in interrupt service routines, and we only use interrupts to ensure correct mutually exclusive accesses to memory. Our approach combines PTIDES semantics with traditional scheduling methods. The first implementation leverages Earliest-Deadline First scheduling algorithm and guarantees correct event order defined by PTIDES. It is deployed on an ARM based micro-controller.
->We would like this project to address the distributed character of PtidyOS. Our implementation testbed will probably consist of micro-controllers synchronized in time using [[http://ptpd.sourceforge.net/ |PTPd]], an open-source implementation of the [[http://en.wikipedia.org/wiki/Precision_Time_Protocol |Precision Time Protocol]]. Another idea for this project could be to implement efficient event queue structures or experiment with other scheduling algorithms for real-time processing of events. This project may build on recent open-source real-time projects, such as [[http://shark.sssup.it/ |S.Ha.R.K.]]: Soft Hard Real-Time Kernel (for dynamic priority schedulers) or [[http://www.ocera.org/ |OCERA]]: Open Components for Embedded Real-time Applications (for resource reservation or publish/subscribe middleware mechanisms).
* '''Further Reading''': [[(Attach:)PtidyOS]], [[http://portal.acm.org/citation.cfm?doid=63039.63045 |Calendar queues]]
* '''Skills''': C [required]
* '''Level''': Intermediate - Advanced
* '''Benefits to the Student''': Learn about embedded middleware, discrete-event model semantics and real-time event processing. Learn to use source version control systems.
* '''Benefits to the Community''': Expand the space of open-source real-time embedded and middleware solutions.
* '''Comments''': Visit to UC Berkeley recommended.
(:if false:)
[[http://en.wikipedia.org/wiki/Concurrent_computing |Concurrent Computing]],
, [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]]
Event Scheduler for Real-time Event Processing
[[http://www.redhat.com/f/pdf/mrg/mrg_realtime_whitepaper.pdf |MRG Realtime]], [[http://www.oreilly.com/catalog/linuxkernel/chapter/ch10.html |Linux: Process Scheduling]],(:ifend:)
!!!Project Ideas 3
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]], [[http://en.wikipedia.org/wiki/Source_code_generation |Code Generation]]
* '''Mentors''': Jia Zou / Slobodan Matic
* '''Title''': C Code Generation for Ptides Models
* '''Technical Details''':
->The Ptolemy group is developing a code generator that uses template files to build C code from Ptolemy models. The current template effort synthesizes C code from certain Ptolemy II models ([[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/sdf/doc/body.htm |SDF]], [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |FSM]] and [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/hdf/doc/body.htm |HDF]]).
->PTIDES is a programming model targeting distributed real-time embedded systems. Our approach defines "helper" classes associated with Ptolemy II actors (i.e. model components) that define the C code implementation for actors. The current code generator for PTIDES model does not yet support heterogeneous models, meaning no PTIDES actor can yet be refined by any other Ptolemy II models such as SDF, FSM, and HDF. Thus the goal of this project is to integrate PTIDES code generator with other models. Since any model that supports heterogeneity is likely to be big, an efficient implementations is needed to reduce the overhead introduced by high level abstraction of models. To address this we use partial evaluation as an optimized compilation technique for actor-oriented models. For more details see [[http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-8.html |Ptolemy Design Document]] (Vol.2, Chap.7).
->Test the implementation on simple demo models with a limited actor library. The generated code could be targeted for an embedded micro-controller used in the Ptolemy group.
(:if false:)
->In this project we would like to build the same feature for the [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/de/doc/body.htm |DE]] models. In the first iteration all models could use the same (manually written) event scheduler and user would provide C code functionality for all actors. More efficient implementations will have to reduce the overhead introduced by high level abstraction of models.
This project may lead to code generation for real-time [[http://chess.eecs.berkeley.edu/ptides/ |Ptides]] models and other research efforts.
(:ifend:)
* '''Further Reading''': [[http://ptolemy.eecs.berkeley.edu/viptos/ |VIPTOS]], [[http://www.ece.umd.edu/~ankush/publications/varma-j2c-thesis.pdf |A Retargetable Optimizing Java-to-C Compiler for Embedded Systems]]
* '''Skills''': Java, C [required]
* '''Level''': Intermediate - Advanced
* '''Benefits to the Student''': Learn compilation and code generation techniques for graphical block-oriented languages. Learn about discrete-event model semantics and implementation. Learn to use source version control systems.
* '''Benefits to the Community''': Broaden the space of open-source C code generators from higher level languages.
* '''Comments''': High importance to us.
!!!Project Ideas 4
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Model_Driven_Engineering |Model_Driven_Engineering]], [[http://en.wikipedia.org/wiki/Real-time_operating_system |Real-Time Operating Systems]], [[http://en.wikipedia.org/wiki/Scheduling_(computing) |Scheduling]]
* '''Mentors''': Slobodan Matic / Jia Zou
* '''Title''': Performance Analysis Tool for Ptolemy
* '''Technical Details''':
->Model-based design and languages are gaining traction in industrial practice as evidenced by commercial tools such as [[http://en.wikipedia.org/wiki/Simulink |Simulink]]/[[http://www.mathworks.com/products/rtw/ |Real-Time Workshop]], [[http://en.wikipedia.org/wiki/Labview |LabVIEW]] or [[http://en.wikipedia.org/wiki/Labview |Rhapsody]]. The development tools are more often designed with support for performance requirements, such as latencies and buffer sizes of components. For instance, models (programs) can be extended with timing, activation and distribution properties of components, and schedulability analysis can be performed to certify that real-time constraints can be met on a certain platform. A more refined analysis would take into account computation and communication times as well as timing properties of the input signals. The goal of this project is not to define new techniques for analyzing real-time and embedded systems, but to integrate already existing ones into the Ptolemy design environment.
->A potential GSoC project might apply recent compositional performance analysis techniques, such as open-source [[http://www.mpa.ethz.ch/Rtctoolbox/Overview |Real-Time Calculus]] or event-flow based [[http://www.symtavision.com/symtas.html |SymTA/S]]. Another approach may be based on techniques developed in the open-source project [[http://mast.unican.es/ |MAST]].
* '''Further Reading''': [[ftp://ftp.tik.ee.ethz.ch/pub/people/psimon/publications/PWTHSHREG08.pdf |Performance Analysis Hard Real-Time Systems]]
* '''Skills''': Java [required]
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn model-based design tools. Explore certain performance and schedulability analysis techniques. Learn to use source version control systems.
* '''Benefits to the Community''': Expand the space of open-source performance analysis tools.
* '''Comments''': Research potential.
!!!Project Ideas 5
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Distributed_systems |Distributed]], [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]], [[http://en.wikipedia.org/wiki/Concurrent_computing |Concurrent Computing]], [[http://en.wikipedia.org/wiki/Multi-core |Multi-Core]]
* '''Mentors''': Jia Zou / Slobodan Matic
* '''Title''': Distributed Discrete-Event Simulator
* '''Technical Details''':
->The number of distributed event processing applications is increasing. Start with the discussion of related implementation problems for a distributed discrete-event (DDE) [[http://www.cs.wustl.edu/~kjg/CS333_SP97/devs.html |example]]. Ptolemy also comes with the [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/dde/doc/body.htm |DDE]] domain. The objective of this project is to build infrastructure for distributed event processing that will subsequently be used in other projects. This approach could build on the code already developed during GSoC 2008.
->A student could implement discrete-event simulator distributed over locally connected servers. S/he would program in C or C++ most likely using [[http://www.redhat.com/rhel/ |Red Hat Enterprise Linux]]. We plan to experiment with the [[http://www.redhat.com/mrg/messaging/ |Messaging]] component of the Red Hat [[http://www.redhat.com/mrg/ |MRG]] framework that implements open standard protocol [[http://en.wikipedia.org/wiki/Advanced_Message_Queuing_Protocol |AMQP]]. The other approach in a similar setting could build upon recent open-source projects such as [[http://dre.sourceforge.net/ |DREAM]]: Distributed Real-time Embedded Analysis Method. Another interesting idea with research potential would be to build an efficient simulator on a multi-core processor. It could also leverage related enhancements of 2.6 Linux kernels. Test on a simple distributed discrete-event application of interest.
* '''Further Reading''': [[http://portal.acm.org/citation.cfm?id=84545&dl=ACM&coll=portal |Parallel Discrete Event Simulation]], [[http://oss.intel.com/pdf/mclinux.pdf |Multi-Core and Linux]]
* '''Skills''': C or C++ [required]
* '''Level''': Intermediate - Advanced
* '''Benefits to the Student''': Learn to program distributed and/or parallel applications. Learn about discrete-event model semantics and implementation. Learn to use source version control systems.
* '''Benefits to the Community''': Increase the efficiency of open-source parallel discrete-event simulation/execution platforms.
* '''Comments''': More than one student. Research potential.
!!!Project Ideas 6
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]], [[http://en.wikipedia.org/wiki/Event_queue |Event Queue]], [[http://en.wikipedia.org/wiki/Real-Time_Java |Real-Time Java]], [[http://en.wikipedia.org/wiki/Concurrent_computing |Concurrent Computing]]
* '''Mentors''': Jia Zou / Slobodan Matic
* '''Title''': Java Discrete-Event or Ptides Execution Platform
* '''Technical Details''':
->There are a lot of open-source discrete-event ''simulation'' [[http://www.topology.org/soft/sim.html |frameworks]]. Much less work has been done in adapting these models as an ''execution'' platform for embedded software. Such a platform has to take into account real-time interaction with the environment. In this project a student could adapt the current implementation of Ptolemy [[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/de/doc/body.htm |Discrete-Event]] or [[http://chess.eecs.berkeley.edu/ptides/ |Ptides]] simulation frameworks. This project will not address the distributed aspects of Ptides models. The student would program in Java and test on [[http://www.redhat.com/rhel/ |Red Hat Enterprise Linux]]. We plan to experiment with the [[http://www.redhat.com/mrg/realtime/ |Realtime]] component of the Red Hat [[http://www.redhat.com/mrg/ |MRG]] framework. If standard Java programming model is used, the student will have access to the [[http://www-306.ibm.com/software/webservers/realtime/ |IBM WebSphere Real Time]] platform that performs automatic garbage collection. Other approaches could use more difficult programming models according to the [[http://www.rtsj.org/ |Real-Time Specification for Java]]. Debug using Eclipse based [[http://domino.research.ibm.com/comm/research_projects.nsf/pages/metronome.tenedor.html |Tuning Fork]] visualization tool. Test on a simple discrete-event application of interest.
* '''Further Reading''': [[http://www.redhat.com/f/pdf/mrg/mrg_realtime_whitepaper.pdf |MRG Realtime]], [[http://java.sun.com/developer/technicalArticles/Interviews/Bollella_qa2.html |RTSJ]], [[http://chess.eecs.berkeley.edu/pubs/221/RealTimeComputing_RTAS_Lee.pdf |Ptides]] (from slide 32)
* '''Skills''': Java [required], JNI [recommended]
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn high-level real-time programming in Java. Learn about discrete-event model semantics and implementation. Learn to use source version control systems.
* '''Benefits to the Community''': Advance real-time programming under Java and Linux.
* '''Comments''': Visit to UC Berkeley recommended.
!!!Project Ideas 7
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Discrete_event_simulation |Discrete-Event]], [[http://en.wikipedia.org/wiki/Formal_language |Formal Language]], [[http://en.wikipedia.org/wiki/Finite_state_machine |Finite State Machine]]
* '''Mentors''': Thomas Feng / Slobodan Matic
* '''Title''': Model Verification
* '''Technical Details''': ERG (Event Relationship Graphs) is a formal language for discrete-event simulation. It has a visual syntax similar to FSM ([[http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/fsm/doc/body.htm |Finite State Machines]]), but it is much more expressive. Model verification of ERG is a challenging problem because the event queue in a model is potentially unbounded. This project aims to build a prototype for model verification. For a subset of models, it can be statically checked whether the event queue is bounded, and whether one event is causally dependent on another. The task of this project is to identify such a subset, and create a verification tool that can handle it.
* '''Further Reading''': [[http://www.google.com/url?sa=t&source=web&ct=res&cd=1&url=http%3A%2F%2Fportal.acm.org%2Fcitation.cfm%3Fid%3D358460&ei=Icq-SZnaE4mMsAOy3tiwDA&usg=AFQjCNEkJzC_lAk56Yjc8JX18TuctkiN-w&sig2=rl71NW0-pfLQunutQsO6KA |Simulation modeling with event graphs]]
* '''Skills''': Java [required], formal languages and verification [preferred]
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn event-oriented modeling. Learn model verification techniques. Learn to contribute on a specific subject in a large project (Ptolemy II). Practice Java programming and algorithm design.
* '''Benefits to the Community''': A prototype of a model verification tool that can be easily extended to solve general problems.
* '''Comments''': Visit to UC Berkeley recommended.
(:if false:)
!!!Project Idea 6
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Worst-case_execution_time | Worst-Case Execution Time]], [[http://en.wikipedia.org/wiki/Program_analysis_%28computer_science%29 | Program Analysis]], [[http://en.wikipedia.org/wiki/Max-plus_algebra | Max-plus algebra]]
* '''Mentors''': Thomas Feng / Jia Zou / Slobodan Matic
* '''Title''': A program analysis tool for WCET (worst-case execution time) of Ptolemy actors written in Java.
* '''Technical Details''':
->Compute WCET as the maximum execution time on all the execution paths of an actor, assuming that the WCET of atomic operations used by the actor, such as library function calls, is given. Use jCute to discover all feasible execution paths of the actor's fire() method, which is invoked on each firing. Combine the information obtained by separately analyzing each path with a max-plus algebra to produce the WCET of a firing of the actor.
* '''Further Reading''': [[http://osl.cs.uiuc.edu/~ksen/cute/ | jCute]] - A execution path analysis tool for Java, [[http://en.wikipedia.org/wiki/Max-plus_algebra | Max-plus algebra]]
* '''Skills''': Java [required]
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn to use an automatic path exploration tool, and learn program analysis with path exploration.
* '''Benefits to the Community''': Provide a mechanism to automatically analyze WCET for certain kind of structured Java code, which is essential to real-time guarantees.
!!!Project Idea 7
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Model_transformation | Model Transformation]], [[http://en.wikipedia.org/wiki/Subgraph_isomorphism | Subgraph Isomorphism Problem]]
* '''Mentors''': Christopher Brooks / Thomas Feng
* '''Title''': An extension to the current model transformation tool in the Ptolemy framework to support imprecise matching to the user-defined graph pattern.
* '''Technical Details''':
->It is very useful to specify a pattern that allows structural variance in it, such as a one that matches a variable number of interconnected nodes. The current implementation does not support this because the number of nodes must be known and fixed at design time. The student will develop a visual syntax for the pattern designer to specify this variance in the structure. The student will also extend the model transformation tool to perform pattern matching on this kind of specifications, and apply transformation on the matched model parts.
* '''Further Reading''': [[http://www.eecs.berkeley.edu/~tfeng/transformation.html | Model Transformation in Ptolemy]]
* '''Skills''': Java [required]
* '''Level''': Intermediate
* '''Benefits to the Student''': Learn the basic techniques for model transformation and graph rewriting. Creatively develop a useful algorithm.
* '''Benefits to the Community''': Develop a more flexible pattern matching algorithm for graph rewriting.
* '''Comments''': Research potential.
!!!Project Idea 8
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Model_transformation | Model Transformation]], [[http://en.wikipedia.org/wiki/Subclass_%28computer_science%29 | Subclassing]], [[http://en.wikipedia.org/wiki/Actor_model | Actor Model]]
* '''Mentors''': Christopher Brooks / Thomas Feng
* '''Title''': Bring the concept of object-oriented programming (OOP) to the modeling world with actor-oriented subclassing.
* '''Technical Details''':
->Model transformation based on graph transformation is a well-studied technique. However, it is creative to apply this technique to effectively reuse model designs in the sense of subclassing. Often times, a previous design needs to be slightly modified before it can be used in a new context. If the desired modification affects the structure of the design, then model transformation is a powerful backend to rely on. The student will extend the current implementation of model subclassing (which does not take advantage of model transformation) and implement extra checks to ensure properties to be preserved by a subclass model obtained by transformation. Example properties that the student will work on include input/output interface, expected data types of the input/output, behavioral properties expressed with interface automata, etc.
* '''Further Reading''': [[http://www.eecs.berkeley.edu/~tfeng/transformation.html | Model Transformation in Ptolemy]], [[http://ptolemy.eecs.berkeley.edu/publications/papers/07/classesandInheritance/index.htm | Actor-Oriented Subclassing]], [[http://springerlink.metapress.com/content/w22e59m4ghb9ewac/ | Behavioral Types with Interface Automata]]
* '''Skills''': Java [required]
* '''Level''': Advanced
* '''Benefits to the Student''': Learn the basics of model checking and actor-oriented subclassing.
* '''Benefits to the Community''': Explore the idea of actor-oriented subclassing, which potentially improves the current approach of model reuse (mainly by composition of components).
* '''Comments''': Research potential.
!!!Project Idea 9
* '''Wikipedia Keywords''': [[http://en.wikipedia.org/wiki/Static_code_analysis | Static Code Analysis]]
* '''Mentors''': Man-kit Leung / Hiren Patel
* '''Title''': An environment for program analysis on C programs generated from the Ptolemy Code Generation Framework.
* '''Technical Details''':
->Traditional embedded programming almost always uses C as an entry language. This however, is tedious and difficult to implement correctly when applications mandate a certain degree of concurrency. As a result, the Ptolemy framework provides higher-level models of computation that aid in better managing the concurrency inherent in embedded system applications. It also provides a code generation framework to C from the Process Network and Synchronous Data Flow models of computation. Since these models of computation are untimed, no notion of time is inserted into the generated C code. However, many embedded systems have real-time requirements that need to be met. For eventual implementation on a platform, it is necessary to do program analysis on the generated C code to estimate execution bounds for real-time embedded systems. We'll focus on a potential SPARC v8 based architecture that will serve as a target platform for code generation from the Ptolemy Framework
* '''Further Reading''':
* '''Skills''': C [required], Static analysis experience [helpful]
* '''Level''': Advanced
* '''Benefits to the Student''': Extend understanding of program analysis on source compiled by GCC.
* '''Benefits to the Community''': Extension for Ptolemy's code generation framework for providing execution bounds for particular instruction set architectures for model-based embedded programming.
* '''Comments''': Research potential.
(:ifend:)
!!About pmwiki
A local copy of PmWiki's
documentation has been installed along with the software,
and is available via the [[PmWiki/documentation index]].
To continue setting up PmWiki, see [[PmWiki/initial setup tasks]].
The [[PmWiki/basic editing]] page describes how to create pages
in PmWiki. You can practice editing in the [[wiki sandbox]].
More information about PmWiki is available from http://www.pmwiki.org .
Changed lines 1-6 from:
to:
In 2008, the <a href="http://ptolemy.eecs.berkeley.edu">Ptolemy Project</a> participated in the
<a href="http://code.google.com/soc/">Google Summer of Code</a>.
<p>This page is for our current interactions.
<p>See <a href="http://chess.eecs.berkeley.edu/gsoc/wiki">The Ptolemy/GSOC Wiki</a> for details.
<a href="http://code.google.com/soc/">Google Summer of Code</a>.
<p>This page is for our current interactions.
<p>See <a href="http://chess.eecs.berkeley.edu/gsoc/wiki">The Ptolemy/GSOC Wiki</a> for details.