Overview of the Ptolemy Project Edward A Lee Robert S Pepper Distinguished Professor and Chair of EECS UC Berkeley EECS 249 Guest Lecture Berkeley CA September 20 2007 Elevator Speech The 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 Ptolemy II is being constructed in Java and serves as the principal laboratory for experimentation Lee Berkeley 2 z1 Concurrent Composition of Subsystems In Mainstream SW Engineering in 2007 Component technologies z z Concurrency z z Objects in C C or Java Wrappers as service definitions Threads shared memory semaphores mutexes Message Passing synchronous or not buffered Distributed computing z Distributed objects wrapped in web services Soap CORBA DCOM Lee Berkeley 3 Our Approach Actor Oriented Models of Computation Traditional component interactions class name What flows through an object is sequential control data methods call return Actor oriented actor name data state parameters ports Input data Output data What flows through an object is streams of data Lee Berkeley 4 z2 Software Legacy of the Project Gabriel 1986 1991 z z z z z z Each of these served us first and foremost as a laboratory for investigating design Ptolemy Classic 1990 1997 z z z z z z z z Written in Lisp Aimed at signal processing Synchronous dataflow SDF block diagrams Parallel schedulers Code generators for DSPs Hardware software co simulators Written in C Abstract Actor Semantics Multiple models of computation Hierarchical heterogeneity Dataflow variants BDF DDF PN C VHDL DSP code generators Optimizing SDF schedulers Higher order components Ptolemy II 1996 2022 z z z z z z z Written in Java Behavioral polymorphism Multithreaded Network integrated and distributed Modal models Sophisticated type system CT HDF CI GR etc Focus has always been on system modeling and embedded software Lee Berkeley 5 Where it started SDF Synchronous Dataflow and the Balance Equations 1985 86 production consumption matrix 1 1 0 0 2 1 2 0 1 Actor 1 balance equations Connector 1 q1 q q2 q3 firing vector 0 r q 0 0 0 Lee Berkeley 6 z3 Gabriel and Ptolemy Classic Leveraged SDF to Generate Parallel Code SDF model parallel schedule and synthesized assembly code 1990 It is an interesting and rich research problem to minimize interlocks in complex multirate applications Lee Berkeley 7 Many Scheduling and Optimization Problems and Some Solutions Resulted Optimization criteria that might be applied Minimize buffer sizes Minimize the number of actor activations Minimize the size of the representation of the schedule code size See S S Bhattacharyya P K Murthy and E A Lee Software Synthesis from Dataflow Graphs Kluwer Academic Press 1996 for a summary of the single processor optimization problems Lee Berkeley 8 z4 Minimum Buffer Schedule ABABCABCABABCABCDEAFFFFFBABCABCABABCDE AFFFFFBCABABCABCABABCDEAFFFFFBCABABCABC DEAFFFFFBABCABCABABCABCDEAFFFFFBABCABCA BABCDEAFFFFFBCABABCABCABABCDEAFFFFFEBCA FFFFFBABCABCDEAFFFFFBABCABCABABCABCDEAF FFFFBABCABCABABCDEAFFFFFBCABABCABCABABC DEAFFFFFBCABABCABCDEAFFFFFBABCABCABABCA BCDEAFFFFFBABCABCABABCDEAFFFFFEBCAFFFFFB ABCABCABABCDEAFFFFFBCABABCABCDEAFFFFFBA BCABCABABCABCDEAFFFFFBABCABCABABCDEAFFF FFBCABABCABCABABCDEAFFFFFBCABABCABCDEAF FFFFBABCABCABABCABCDEAFFFFFEBAFFFFFBCABC ABABCDEAFFFFFBCABABCABCABABCDEAFFFFFBCA BABCABCDEAFFFFFBABCABCABABCABCDEAFFFFFB ABCABCABABCDEAFFFFFBCABABCABCABABCDEAF FFFFBCABABCABCDEFFFFFEFFFFF Source Shuvra Bhattacharyya Lee Berkeley 9 Scheduling Tradeoffs Bhattacharyya Parks Pino Lee Scheduling strategy Code Data Minimum buffer schedule no looping 13735 32 Minimum buffer schedule with looping 9400 32 Worst minimum code size schedule 170 1021 Best minimum code size schedule 170 264 Source Shuvra Bhattacharyya Lee Berkeley 10 z5 Gabriel and Ptolemy Classic Provided CoSimulation of Hardware and Generated Software An SDF model a Thor model of a 2 DSP architecture a logic analyzer trace of the execution of the architecture and two DSP code debugger windows one for each processor 1990 Lee Berkeley 11 Example of Model Based Design ADPCM Speech Coding Model of a speech coder generated to DSP assembly code and executed using a DSP debugger interface with host DSP interaction 1993 Lee Berkeley 12 z6 Example Heterogeneous Architecture with DSP and Sun Workstation 1995 DSP card in a Sun Sparc Workstation runs a portion of a Ptolemy model the other portion runs on the Sun Sparc C DSP Card M56K Lee Berkeley 13 Gradually Increasing Emphasis on Modeling Ptolemy Classic Example Showing Higher Order Components adaptive nulling in an antenna array 1995 streams hierarchical components higher order components Ptolemy application developed by Uwe Trautwein Technical University of Ilmenau Germany Lee Berkeley 14 z7 Higher Order Components Realizing Recursion in Ptolemy Classic FFT implementation in Ptolemy Classic 1995 used a partial evaluation strategy on higher order components recursive reference Lee Berkeley 15 Extension of SDF Multidimensional SSDF 1993 Production and consumption of Ndimensional arrays of data 40 48 8 8 Balance equations and scheduling policies generalize Much more data parallelism is exposed Similar but dynamic multidimensional streams have been implemented in Lucid Lee Berkeley 16 z8 More interesting Example Two dimensional FFT constructed out of onedimensional actors Lee Berkeley 17 MDSSDF Structure Exposes Fine Grain Data Parallelism A B L M M N 1 1 1 M N 1 Transpose Repeat Original Matrix Repeats T 1 M N 1 1 N Original Matrix 1 1 1 M M Repeat L 1 1 L L N N Element wise product 0 1 0 Repeats 1 M 1 Downsample 1 1 1 L 1 N However such programs are extremely hard to write and to read Parameter 3 1 2 Transpose T From this a precedence graph can be automatically constructed that reveals all the parallelism in the algorithm Parameter 1 3 2 L N 1 Lee Berkeley 18 z9 Another Extension Cyclostatic Dataflow CSDF Lauwereins et al TU Leuven 1994 z z Actors cycle through a regular production consumption pattern Balance equations become R 1 R 1 i 0 i 0 q A ni mod P q B mi mod Q R lcm P Q cyclic production pattern fire A produce Ni channel n0 K nP 1 m0 K mQ 1 fire B consume M Lee Berkeley 19 Further
View Full Document
Unlocking...