Home Page

Dataflow workgroup

Spring 2011:

Schedule and topics to be decided. Initial topics:

• Alta Rica: http://altarica.labri.fr/ (Jannette)
• Fluctuat: http://www-list.cea.fr/labos/gb/LSL/fluctuat/index.html (Jan)
• Spark Ada: http://en.wikipedia.org/wiki/SPARK_ (Chris)
• FijiVM: http://rtjava.blogspot.com/2009/11/new-real-time-vm-was-born-fiji-vm.html (Jia)
• Deterministic Parallel Java: http://dpj.cs.uiuc.edu/DPJ/Home.html
• Fran: http://conal.net/fran/
• Modelica: http://www.openmodelica.org/ (Patricia)

Other topics that we didn't get to look at in 2010:

• Geilen's CODES-ISSS 2010 paper (got "best paper" award): http://chess.eecs.berkeley.edu/dataflow/wiki/uploads/Main/GeilenStujik_Scenarios_CODES_2010
• Distributed system problems, e.g., clock synchronization. Possible papers to study:
  • Leslie Lamport (1978). "Time, clocks, and the ordering of events in a distributed system". Communications of the ACM 21 (7): 558–565.
  • Chandy, K.M., Lamport, L.: Distributed snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems 3(1), 63–75 (1985)
• Intervals project (ETH): http://intervals.inf.ethz.ch/
• Scala: http://www.scala-lang.org/
• Design of a Mouldable Programming Language: http://bldl.ii.uib.no/dmpl.html

Fall 2010: general theme: Parallelism!

• 09/03/2010: First meeting! Edward talked briefly about the Ordered Memory Access architecture:
  • http://ptolemy.eecs.berkeley.edu/publications/papers/93/OMA_ICASSP93/
• 09/10/2010: CUDA and non-interference (Stavros)
  • CUDA: http://www.nvidia.com/object/cuda_home_new.html
  • Non-interference: http://www.usenix.org/events/hotpar10/final_posters/Tripakis.pdf
  • Sample chapter of CUDA book that has info on coalescing: http://developer.download.nvidia.com/books/cuda-by-example/cuda-by-example-sample.pdf
• 09/17/2010: MPI (Soheil)
  • Message Passing Interface (MPI)
  • Disciplined Message Passing
• 09/24/2010: Memory models (Ben)
  • Hans J. Boehm, "Threads Cannot Be Implemented As a Library," PLDI 2005.
• 10/1/2010: Dataflow HW architectures (Soheil)
  • Arvind's Keynote Talk at ISCA'05
• 10/8/2010: Stream processors (Gage)
  • http://cva.stanford.edu/publications/2003/imagine-ieeecomputer/
• 10/15/2010: Multicore Haskel and Id (Chris)
  • http://research.microsoft.com/pubs/74058/parallel_haskell2.pdf
  • http://csg.csail.mit.edu/pubs/memos/Memo-313/Memo-313.pdf
• 10/22/2010: Memory Models (Jan)
  • http://chess.eecs.berkeley.edu/dataflow/wiki/uploads/Main/memorymodels.pptx
  • Paper on generating litmus tests: http://www.cis.upenn.edu/~alur/Cav10-sela.pdf
  • SPIN 07 presentation by Alur on "Concurrent executions on relaxed memory models: Challenges and opportunities for software model checking" http://www.cis.upenn.edu/~alur/Talks/spin07.ppt
• 11/5/2010-11/12/2010: Loop Parallelization Methods and Dependency Analysis (Chris)
  • Lamport's paper: http://portal.acm.org/citation.cfm?id=360844
  • Lengauer's paper: http://www.springerlink.com/index/f9353713t73l824h.pdf
  • Some note slides: http://www.eecs.berkeley.edu/~shaver/docs/LoopPllPres.pdf
• 11/19/2010: Execution time prediction of Streaming applications. (Dai)
  • Input-driven dynamic execution prediction of streaming applications. http://portal.acm.org/citation.cfm?id=1693453.1693494
  • Execution-time Prediction for Dynamic Streaming Applications with Task-level Parallelism. http://portal.acm.org/citation.cfm?id=1302809
• 12/03/2010: Fault tolerant parallel computation (Stavros)

Other potential topics for Fall 2010:

• Languages and programming models:
  • POSIX threads: https://computing.llnl.gov/tutorials/pthreads/
  • OpenMP: http://openmp.org/wp/
  • OpenCL: http://www.khronos.org/opencl/
  • Ct: http://software.intel.com/en-us/data-parallel/
  • Go: http://golang.org/
  • Patterns: http://parlab.eecs.berkeley.edu/wiki/patterns/patterns
  • Titanium: http://titanium.cs.berkeley.edu/
  • StreamIT: http://groups.csail.mit.edu/cag/streamit/
  • Multicore Haskell: http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel/
  • Intervals project (ETH): http://intervals.inf.ethz.ch/
  • Scala: http://www.scala-lang.org/
• HW architectures, execution platforms (GPUs, multicores, clusters, etc.)
  • dataflow HW architectures, streaming processors, TRIPS (http://userweb.cs.utexas.edu/~trips/)
• Applications, case studies
• Implementation: mapping, scheduling, automatic parallelization, ...
  • NI: from dataflow to parallel HW
• Memory models, memory consistency, transactional memories
• Robustness, reliability, fault-tolerance
• Theory, e.g., complexity theory, PRAMs, P-completeness, ... See also:
  • http://en.wikipedia.org/wiki/List_of_important_publications_in_concurrent,_parallel,_and_distributed_computing
  • http://www.cs.berkeley.edu/~satishr/cs273/
  • https://agora.cs.illinois.edu/display/cs498tpc/Theory+of+Parallel+Computing
• Interesting links:
  • http://parlab.eecs.berkeley.edu/2010bootcamp
  • http://parlang2010.pbworks.com/

Spring 2010:

• Marc (3/3/2010): Introduction to SDF as a subclass of KPN. Timed SDF.
• Maarten (3/9/2010 and 3/16/2010): Relating SDF conservative modeling with implementations. Maarten discussed how SDF models make assumptions that break during implementations (e.g., infinite instead of finite buffers, fixed instead of variable execution times, etc.). He showed how some of these characteristics of implementations can be nevertheless captured in dataflow models.
• 3/23/2010: We discussed how KPNs, because they are deterministic, cannot model shared resources in a satisfactory manner. Edward observed that contention is inherently non-deterministic. We built some simple models that were essentially attempting to model rendez-vous. Languages with such primitives include:
  • OCCAM programming language: http://en.wikipedia.org/wiki/Occam_programming_language
  • REO coordination language from CWI: http://reo.project.cwi.nl/
  • BIP from Verimag: http://www-verimag.imag.fr/BIP,196.html?lang=
• 3/30/2010: Properties of KPNs: deadlocks, fairness, boundedness.
• 4/6/2010: Execution policies for KPNs; defined soundness, completeness, and boundedness preservation for such policies; two policies are described in:
  • Lee-Parks' 1995: http://ptolemy.eecs.berkeley.edu/papers/95/processNets/
  • Geilen-Basten's 2003: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.7148&rep=rep1&type=pdf
• 4/13/2010: Throughput: how to define it and how to compute it. References:
  • Ghamarian et al. ACSD 2006: http://dx.doi.org/10.1109/ACSD.2006.33
  • Stuijk et al. IEEE TOC 2008: http://dx.doi.org/10.1109/TC.2008.58
  • Tripakis et al. IEEE TOC 2008: http://www-verimag.imag.fr/~tripakis/papers/tc08-revised.pdf
• 4/20/2010: Latency: how to define it and how to compute it.
• 4/27/2010: We discussed the paper: http://ptolemy.eecs.berkeley.edu/publications/papers/06/concurrentsemantics/
• 5/4/2010: Marc talked about using model checking to derive buffer-optimal schedules. References:
  • M.C.W. Geilen, T. Basten, S. Stuijk. Minimising Buffer Requirements of Synchronous Dataflow Graphs with Model Checking. DAC 2005, pages 819-824. ACM Press, New York, NY, USA, 2005. http://doi.acm.org/10.1145/1065579.1065796
  • Hartel, P.H., Ruys, T.C. and Geilen, M.C.W. Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow. 8th Int. Conf. on Formal Methods in Computer Aided Design, 17-20 Nov. 2008, Portland, Oregon. pp. 161-170. IEEE Computer Society Press. http://dx.doi.org/10.1109/FMCAD.2008.ECP.25
  • S. Stuijk, M.C.W. Geilen, T. Basten. Throughput-Buffering Trade-off Exploration for Cyclo-Static and Synchronous Dataflow Graphs. IEEE Trans. Computers. 57(10):1331-1345, 2008. http://dx.doi.org/10.1109/TC.2008.58
  • Liu, W., Gu, Z., Xu, J., Wang, Y., and Yuan, M. 2009. An efficient technique for analysis of minimal buffer requirements of synchronous dataflow graphs with model checking. CODES+ISSS '09, Grenoble, France, October 11 - 16, 2009). ACM, New York, NY, 61-70. http://doi.acm.org/10.1145/1629435.1629445
  • O. Moreira, T. Basten, M.C.W. Geilen, S. Stuijk. Buffer Sizing for Rate-optimal Single-rate Dataflow Scheduling Revisited. IEEE Trans. on Computers. 59(2):188-201, February 2010. http://dx.doi.org/10.1109/TC.2009.155
• 5/11/2010: We discussed the paper: http://chess.eecs.berkeley.edu/ptolemy/wiki/uploads/StudyGroup/jonsson1989fat.pdf
• 5/18/2010: We discussed reactive process networks, scenarios, and heterochronous data flow. References:
  • M.C.W. Geilen and T. Basten. Reactive Process Networks. In EMSOFT 2004, Proc., pages 137-146. Pisa, Italy, 27-29 September, 2004. ACM Press.
  • B.D. Theelen, et al. A Scenario-Aware Data Flow Model for Combined Long-Run Average and Worst-Case Performance Analysis. Proc. MEMOCODE 2006, pp. 185-194, IEEE Computer Society, Los Alamitos, California, USA, 2006.http://doi.ieeecomputersociety.org/10.1109/MEMCOD.2006.1695924
  • M.C.W. Geilen. Synchronous Dataflow Scenarios. ACM Trans. Embedded Computing Systems. To appear. (Special issue on Model-driven Embedded System Design.)
  • http://ptolemy.eecs.berkeley.edu/papers/98/starcharts/
• 5/25/2010: Marc presented the SDF3 tool: : http://www.es.ele.tue.nl/sdf3/
• 6/1/2010 and 6/8/2010: NI talks about their projects.
• 6/15/2010: Chris talked about Faust: http://faust.grame.fr/. Papers are linked at http://faust.grame.fr/pubs.php:
  • Specifically, http://www.grame.fr/Ressources/pub/faust-jim2002.pdf presents an argument regarding the span of diagrams that can be represented fully with Faust's syntax.
• 6/29/2010: The Pthales multi-dimensional dataflow domain in Ptolemy II.
• 7/6/2010 and 7/13/2010: Examples of refinement with actor interfaces. See technical report:
  • http://www.ics.ele.tue.nl/~mgeilen/publications/techrep/tai_techrep.pdf
• 7/20/2010: Tatsuaki talked about the Cell processor.

List of Topics

• Verification
  • Firing vs Reachability - Connection between reachability in state machines vs fireability in dataflow model (prove that evil actor never fires) - eal
  • Questions on algorithms - decidability questions, specifically for "timed" dataflow models (like DE) - stavros
  • System theory for dataflow - compositionality and abstraction - stavros
• Multicore issue
  • Dataflow as a software component architectures vs StreamIt (programming language for multicore) - eal
• C+++++
  • develop textual syntax in C or C++ to support actor oriented language - eal
• Multidimensional dataflow (Thales)
  • Handling shared data structures in dataflow models (arrays, GR, reactable) - eal
• Expressiveness + indeterminacy - mark
  • Beyond the turning complete expression
  • Reactive process networks - mark
• Performance / Prediction / Timing / Resource allocation
• Beyond HDF
  • Some applications that you can't model with HDF which are relevant. Can we find a conservative answer? - Maarten
  • HDF foundation as a programming model? Is there a variant that is modular with the same attractive properties? Can be used in programming languages? - eal
• Role of Time in Dataflow
• Review of KPN, BDF, HDF, SDF, DE
• Deeper understanding of research from
  • Maarten
  • Mark
  • Eleftherios
• Maybe this is interesting: http://boom.cs.berkeley.edu/
• Other possibilities (beyond those mentioned in the topics list above):
  • Max-plus algebra and its use in throughput, etc., computation for SDF
  • Resource-aware dataflow
  • Average vs. worst-case methods
  • DE denotational semantics and execution policy
  • Dataflow and Petri nets:
    • http://www.cs.unc.edu/~montek/teaching/spring-04/murata-petrinets.pdf
  • Pipelining (Guang)
  • Bridging the gap between SDF and SR (Guang)
  • Raising timing to the modeling level (Gerald): see http://ptolemy.eecs.berkeley.edu/publications/papers/98/asilomar98/

Links:

• Ptolemy (UC Berkeley): http://ptolemy.eecs.berkeley.edu/
• Computational Process Networks (U Texas): http://users.ece.utexas.edu/~allen/CPN/
• SDF3 (TU Eindhoven): http://www.es.ele.tue.nl/sdf3/
• Compilation of Matlab to Process Networks (Compaan): http://www.liacs.nl/~cserc/compaan/
• Actors Project (EU): http://www.actors-project.eu/index.php?page=public-deliverables
• Complexity results for scheduling problems: http://www.mathematik.uni-osnabrueck.de/research/OR/class/