Gushing Models of Computation in The Ptolemy Project .

Uploaded on:
Ptolemy Project Participants. Director:Edward A. LeeStaff:Christopher HylandsSusan Gardner (Chess)Nuala MansardMary P. StewartNeil E. Turner (Chess)Lea Turpin (Chess)Postdocs, Etc.:Joern Janneck, PostdocRowland R. Johnson, Visiting Scholar Kees Vissers, Visiting Industrial FellowDaniel L
Slide 1

Gushing Models of Computation in The Ptolemy Project Edward A. Lee Professor UC Berkeley Workshop on Streaming Systems, Endicott House, Dedham, MA August 22-23, 2003

Slide 2

Ptolemy Project Participants Graduate Students: J. Adam Cataldo Chris Chang Elaine Cheong Sanjeev Kohli Xiaojun Liu Eleftherios D. Matsikoudis Stephen Neuendorffer James Yeh Yang Zhao Haiyang Zheng Rachel Zhou Director: Edward A. Lee Staff: Christopher Hylands Susan Gardner (Chess) Nuala Mansard Mary P. Stewart Neil E. Turner (Chess) Lea Turpin (Chess) Postdocs, Etc.: Joern Janneck, Postdoc Rowland R. Johnson, Visiting Scholar Kees Vissers, Visiting Industrial Fellow Daniel Lázaro Cuadrado, Visiting Scholar

Slide 3

At Work in the Chess Software Lab Chess = Center for Hybrid and Embedded Software Systems

Slide 4

Software Legacy of the Project Gabriel (1986-1991) Written in Lisp Aimed at flag preparing Synchronous dataflow (SDF) square graphs Parallel schedulers Code generators for DSPs Hardware/programming co-test systems Ptolemy Classic (1990-1997) Written in C++ Multiple models of calculation Hierarchical heterogeneity Dataflow variations: BDF, DDF, PN C/VHDL/DSP code generators Optimizing SDF schedulers Higher-arrange parts Ptolemy II (1996-2022) Written in Java Domain polymorphism Multithreaded Network coordinated and disseminated Modal models Sophisticated sort framework CT, HDF, CI, GR, and so forth. Each of these served us, most importantly, as a research facility for exploring outline. PtPlot (1997-??) Java plotting bundle Tycho (1996-1998) Itcl/Tk GUI structure Diva (1998-2000) Java GUI system Focus has dependably been on installed programming.

Slide 5

Ptolemy Classic Example From 1995 (versatile nulling in a reception apparatus exhibit) streams various leveled comonents Ptolemy application created by Uwe Trautwein, Technical University of Ilmenau, Germany

Slide 6

Ptolemy II Ptolemy II: Our current system for experimentation with on-screen character situated plan, simultaneous semantics, visual punctuations, and progressive, heterogeneous outline. Hierarchical segment modular model dataflow controller case Ptolemy II display: half and half control framework

Slide 7

Actor-Oriented Design Actors with Ports and Attributes Model of Computation: Messaging blueprint Flow of control Concurrency Examples: Dataflow Process systems Synchronous Time activated Discrete-occasion frameworks Publish & subscribe called a "bit," "step," … Most Ptolemy II models of calculation are "performing artist arranged." But the exact semantics relies on upon the chose "executive," which actualizes a model of calculation.

Slide 8

Other Examples of Actor-Oriented Component Frameworks Simulink (The MathWorks) Labview (National Instruments) Modelica (Linkoping) OCP, open control stage (Boeing) GME, performing artist arranged meta-demonstrating (Vanderbilt) SPW, flag handling worksystem (Cadence) System studio (Synopsys) ROOM, continuous question situated displaying (Rational) Easy5 (Boeing) Port-based items (U of Maryland) I/O automata (MIT) VHDL, Verilog, SystemC (Various) Polis & Metropolis (UC Berkeley) … Unlike Ptolemy II, these characterize a settled model of calculation.

Slide 9

Ptolemy Project Principle The model of calculation is not inherent to the product system. Chief from a library characterizes part cooperation semantics Example of Ptolemy II show: Large, space polymorphic segment library.

Slide 10

Actor View of Producer/Consumer Components Models of Computation are actualized in Ptolemy II by an "executive" and a "beneficiary" (which is provided by the chief). Cases we have fabricated: dataflow (a few variations) handle systems push/pull nonstop time CSP (meet) discrete occasions synchronous time-driven distribute/subscribe … Ptolemy II utilizes the question situated standard of polymorphism to understand different on-screen character arranged models of calculation.

Slide 11

Focus on Dataflow (a couple of variations) Computation diagrams [Karp & Miller - 1966] Process systems [Kahn - 1974] Static dataflow [Dennis - 1974] Dynamic dataflow [Arvind, 1981] K-limited circles [Culler, 1986] Synchronous dataflow [Lee & Messerschmitt, 1986] Structured dataflow [Kodosky, 1986] PGM: Processing Graph Method [Kaplan, 1987] Synchronous dialects [Lustre, Signal, 1980\'s] Well-acted dataflow [Gao, 1992] Boolean dataflow [Buck and Lee, 1993] Multidimensional SDF [Lee, 1993] Cyclo-static dataflow [Lauwereins, 1994] Integer dataflow [Buck, 1994] Bounded element dataflow [Lee and Parks, 1995] Heterochronous dataflow [Girault, Lee, & Lee, 1997] … Many instruments, programming systems, and equipment models have been worked to bolster at least one of these.

Slide 12

Synchronous Dataflow (SDF) (Lee and Messerschmitt, 1986) SDF executive SDF offers input, multirate, static planning, halt examination, parallel booking, static memory allotment.

Slide 13

Synchronous Dataflow (SDF) Fixed Production/Consumption Rates Balance conditions (one for every channel): Schedulable statically Decidable: support memory necessities stop number of tokens expended number of firings per "emphasis" number of tokens delivered fire A { … create N … } fire B { … devour M … } channel N M

Slide 14

Parallel Scheduling of SDF Models Many planning enhancement issues can be figured. Some can be fathomed, as well! SDF is appropriate for computerized mapping onto parallel processors and combination of parallel circuits. A C B D Sequential Parallel

Slide 15

Selected Generalizations Multidimensional Synchronous Dataflow (1993) Arcs convey multidimensional streams One adjust condition for every measurement per bend Cyclo-Static Dataflow (Lauwereins, et al., 1994) Periodically shifting creation/utilization rates Boolean & Integer Dataflow (1993/4) Balance conditions are comprehended typically Permits information subordinate directing of tokens Heuristic-based planning (undecidable) Dynamic Dataflow (1981-) Firings booked at run time Challenge: keep up limited memory, halt flexibility, liveness Demand driven, information driven, and reasonable approaches all fall flat Kahn Process Networks (1974-) Replace discrete firings with process suspension Challenge: keep up limited memory, stop opportunity, liveness Heterochronous Dataflow (1997) Combines state machines with SDF diagrams Very expressive, yet decidable

Slide 16

Multidimensional SDF (Lee, 1993) Production and utilization of N - dimensional varieties of information: Balance conditions and planning strategies sum up. A great deal more information parallelism is uncovered. (40, 48) (8, 8) Similar (yet changing) multidimensional streams have been actualized in Lucid.

Slide 17

MDSDF Structure Exposes Fine-Grain Data Parallelism However, such projects are amazingly difficult to compose (and to peruse).

Slide 18

Cyclostatic Dataflow (CSDF) (Lauwereins et al., TU Leuven, 1994) Actors go through a consistent creation/utilization design. Adjust conditions get to be: cyclic generation design fire A { … create … } fire B { … devour M … } channel

Slide 19

Boolean and Integer Dataflow (BDF, IDF) (Lee and Buck, 1993) Balance conditions are comprehended typically as far as questions that get to be distinctly known at run time. An explained calendar is developed with predicates guarding every activity. Presence of such a clarified timetable is undecidable (as is gridlock & limited memory) B An E select switch C 1 - b 1 - b D b Production rate is obscure and is spoken to typically by a variable ( b ).

Slide 20

Dynamic Dataflow (DDF) Actors have terminating rules Set of limited prefixes on information groupings For determinism: No two such prefixes are joinable under a prefix arrange Firing capacity connected to limited prefixes yield limited yields Scheduling targets: Do not stop if there are executable performers Execute in limited memory if this is conceivable Maintain determinacy if conceivable Policies that fall flat: Data-driven execution Demand-driven execution Fair execution Many adjusted information/request driven techniques Policy that succeeds (Parks 1995): Execute with limited cushions Increase limits just when gridlock happens DDF, as BDF and IDF is undecidable (halt, limited memory, plan)

Slide 21

Expected Symbol Drift brought on by mistake in estimation First Symbol Dynamic Dataflow and Process Networks are Formally Similar, Practically Different Example from flag insight: Detection of obscure flag (PSK for this situation) Output information succession, at identified baud rate. (not known apriori ) OEP issue under DARPA MoBIES (Model-based plan of implanted programming),

Slide 22

Undecidability (Buck \'93) Sufficient arrangement of on-screen characters for undecidability: boolean capacities on boolean tokens switch and select starting tokens on circular segments Undecidable: gridlock limited cushion memory presence of a commented on calendar 1 b boolean capacity T 1 T select switch F beginning token 1 - b 1 - b 1 BDF, IDF, DDF, and PN are all undecidable in this sense. Luckily, we can recognize a substantial decidable subset, which we call heterochronous dataflow (HDF).

Slide 23

Example of a Heterochronous Dataflow (HDF) Model A performer comprises of a state machine and refinements to the states that characterize conduct.

Slide 24

Heterochronous Dataflow (HDF) (Girault, Lee, and Lee, 1997) An interconnection of on-screen characters. A performing artist is either SDF or HDF. In the event that HDF, then the performer has: a state machine a refinement for every state where the refinement is a SDF or HDF on-screen character Operational semantics: with the condition of every state machine settled, diagram is SDF in the underlying state, execute one finish SDF cycle assess watches and permit state moves in the new state, execute one finish SDF emphasis HDF is decidable yet many-sided quality can be high

Slide 25

Other Stream-Like Models of Computation (all actualized in Ptolemy II) Push/Pull dataflow with restrained nondetermin

View more...