z1EECS 249 Guest LectureBerkeley, CASeptember 20, 2007Overview of the Ptolemy ProjectEdward A. LeeRobert S. Pepper Distinguished Professor andChair of EECS, UC BerkeleyLee, Berkeley 2Elevator SpeechThe 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.z2Lee, Berkeley 3Concurrent Composition of Subsystems,In Mainstream SW Engineering in 2007| Component technologiesz Objects in C++, C#, or Javaz Wrappers as service definitions| Concurrencyz Threads (shared memory, semaphores, mutexes, …)z Message Passing (synchronous or not, buffered, …)| Distributed computingz Distributed objects wrapped in web services, Soap, CORBA, DCOM, …Lee, Berkeley 4Our Approach: Actor-Oriented Models of ComputationActor oriented:actor namedata (state)portsInput dataparametersOutput dataWhat flows through an object is streams of dataclass namedatamethodscallreturnWhat flows through an object is sequential controlTraditional component interactions:z3Lee, Berkeley 5Software Legacy of the Project| Gabriel (1986-1991)z Written in Lispz Aimed at signal processingz Synchronous dataflow (SDF) block diagrams z Parallel schedulersz Code generators for DSPsz Hardware/software co-simulators| Ptolemy Classic (1990-1997)z Written in C++z Abstract Actor Semanticsz Multiple models of computationz Hierarchical heterogeneityz Dataflow variants: BDF, DDF, PNz C/VHDL/DSP code generatorsz Optimizing SDF schedulersz Higher-order components| Ptolemy II (1996-2022)z Written in Javaz Behavioral polymorphismz Multithreadedz Network integrated and distributedz Modal modelsz Sophisticated type systemz CT, HDF, CI, GR, etc.Each of these served us, first-and-foremost, as a laboratory for investigating design.Focus has always been on system modeling and embedded software.Lee, Berkeley 6Where it started: SDF: Synchronous Dataflow and the Balance Equations (1985-86)⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−−=Γ102120011⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=321qqqq⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡==Γ0000rqActor 1Connector 1balance equationsfiring vectorproduction/consumption matrixz4Lee, Berkeley 7Gabriel and Ptolemy Classic Leveraged SDF to Generate Parallel CodeSDF model, parallel schedule, and synthesized assembly code (1990)It is an interesting (and rich) research problem to minimize interlocks in complex multirateapplications.Lee, Berkeley 8Many 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, KluwerAcademic Press, 1996, for a summary of the single processor optimization problems.z5Lee, Berkeley 9Minimum Buffer ScheduleA B A B C A B C A B A B C A B C D E A F F F F F B A B C A B C A B A B C D EA F F F F F B C A B A B C A B C A B A B C D E A F F F F F B C A B A B C A B CD E A F F F F F B A B C A B C A B A B C A B C D E A F F F F F B A B C A B C AB A B C D E A F F F F F B C A B A B C A B C A B A B C D E A F F F F F E B C AF F F F F B A B C A B C D E A F F F F F B A B C A B C A B A B C A B C D E A FF F F F B A B C A B C A B A B C D E A F F F F F B C A B A B C A B C A B A B CD E A F F F F F B C A B A B C A B C D E A F F F F F B A B C A B C A B A B C AB C D E A F F F F F B A B C A B C A B A B C D E A F F F F F E B C A F F F F F BA B C A B C A B A B C D E A F F F F F B C A B A B C A B C D E A F F F F F B AB C A B C A B A B C A B C D E A F F F F F B A B C A B C A B A B C D E A F F FF F B C A B A B C A B C A B A B C D E A F F F F F B C A B A B C A B C D E A FF F F F B A B C A B C A B A B C A B C D E A F F F F F E B A F F F F F B C A B CA B A B C D E A F F F F F B C A B A B C A B C A B A B C D E A F F F F F B C AB A B C A B C D E A F F F F F B A B C A B C A B A B C A B C D E A F F F F F BA B C A B C A B A B C D E A F F F F F B C A B A B C A B C A B A B C D E A FF F F F B C A B A B C A B C D E F F F F F E F F F F FSource: Shuvra BhattacharyyaLee, Berkeley 10Scheduling Tradeoffs(Bhattacharyya, Parks, Pino, Lee)264170Best minimum code size schedule1021170Worst minimum code size schedule 329400 Minimum buffer schedule, with looping3213735 Minimum buffer schedule, no loopingDataCodeScheduling strategySource: Shuvra Bhattacharyyaz6Lee, Berkeley 11Gabriel and Ptolemy Classic Provided Co-Simulation of Hardware and Generated SoftwareAn 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 12Example of Model-Based Design: ADPCM Speech CodingModel of a speech coder generated to DSP assembly code and executed using a DSP debugger interface with host/DSP interaction (1993).z7Lee, Berkeley 13Example: Heterogeneous Architecture with DSP and Sun Workstation (1995)DSP card in a Sun SparcWorkstation runs a portion of a Ptolemy model; the other portion runs on the Sun.SparcCDSP CardM56KLee, Berkeley 14Gradually Increasing Emphasis on Modeling: Ptolemy Classic Example Showing Higher-Order Components(adaptive nulling in an antenna array, 1995)Ptolemy application developed by Uwe Trautwein, Technical University of Ilmenau, Germanystreamshierarchical componentshigher-order componentsz8Lee, Berkeley 15Higher-Order Components Realizing Recursion in Ptolemy ClassicFFT implementation in Ptolemy Classic (1995) used a partial evaluation strategy on higher-order components.recursive referenceLee, Berkeley 16Extension of SDF: Multidimensional SSDF(1993)| Production and consumption of N-dimensional arrays of data:| Balance equations andscheduling policiesgeneralize.| Much more data parallelism is exposed.(40, 48)(8, 8)Similar (but dynamic) …
View Full Document
Unlocking...