Multidimensional Data Models

Edward A. Lee, Stavros Tripakis1, Dai Bui and Christopher Shaver

Center for Hybrid and Embedded Software Systems, National Science Foundation 0720882 (CSR-EHS: PRET), National Science Foundation 1035672 (CPS: PTIDES), National Science Foundation 0931843 (ActionWebs), Multiscale Systems Center (MuSyC), Army Research Office W911NF-11-2-0038 (DDoSoS), Air Force Research Lab, Robert Bosch GmBH, National Instruments, Thales and Toyota

Multidimensional Data Models (Pthales)

The Pthales project aims at researching models of computation in which actors operate on multidimensional arrays of data. As opposed to models where actors produce to and consume from linear sequences of tokens, multidimensional data models involve actors that produce and consume patterns of data in structured data spaces traversed in a manner specified on the level of the model.

The primary motivating platform on which this work is based is a proprietary system used by Thales called SpearDE, targeted at multidimensional signal processing. Other similar systems include ArrayOL [2] developed at INRIA, and Multidimensional SDF (MDSDF) specified in [3] by Lee and Murthy. These platforms all share the common characteristics of acting on rectilinear data space and being static in their traversal specifications. More specifically, SpearDE and MDSDF only have rectilinear traversals, whereas ArrayOL supports more complex traversals (as does Generalized MDSDF [4]).

The diversity of approaches to multidimensional data models suggests a family of different specific models of computation structured around the use of different sets of constraints regarding how dynamic the model is in its parameters, how data spaces are structured, and how it is integrated into larger hybrid systems. Different specific models of computation also admit different kinds of static analyses and scheduling procedures, as well as different ways to generate code and map models to hardware.



The Pthales Domain

The Pthales model of computation has been developed in Ptolemy with the intention of capturing the semantics of SpearDE and providing a means of doing research and extending these semantics in several ways. Some integration with Synchronous Dataflow (SDF) models has also been developed. The Pthales domain is described in a technical report [1].



Current Research Areas :

The following research aims are being currently pursued.

  1. Interface Generalization and Heterogeneous Integration in Ptolemy:

    The current implementation of the Pthales domain was intended initially to develop and research models that are entirely Pthales models or at most contain SDF composites. This implementation is being reformulated to provide a generic interface to both internal composites and containing models so that it can be used broadly in heterogeneous systems.
  2. Modal and Dynamic Models:

    In the current Pthales domain, as well as in the above given specifications, the semantics for specifying data spaces, patterns, and traversals is static; that is, it cannot change during execution. This constraint can be relaxed in several ways to make multidimensional models more dynamic. Each of these areas are being considered and investigated:
  3. Code Generation and Hardware Mapping:

    We plan to work on a code generation framework for MDSDF based on available open source streaming language compiler such as StreamIt or CAL. The main advantage of doing code generation for MDSDF is that it has more detailed semantics for image processing algorithms than SDF, then thus several compiler optimization techniques could be used to optimize generated code in terms of memory and computational methods. For example, we could optimize for buffer sizes by not transferring whole images at a time, instead, we could gradually transfer separate pieces of images. We could also partition MDSDF applications and map them to multicore platforms based on MDSDF's inherence task level parallelism. We could also apply vectorization techniques to MDSDF.

    4. [1]
    Remi Barrere, Eric Lenormand, Dai Bui, Edward A. Lee, Christopher Shaver and Stavros Tripakis, An Introduction to the Pthales Domain of Ptolemy II, EECS Department University of California, Berkeley Technical Report No. UCB/EECS-2011-32, April 26, 2011
    [2]
    Pierre Boulet, Array-OL Revisited, Multidimensional Intensive Signal Processing Specification, 2007
    [3]
    Praveen K. Murthy, Edward A. Lee, Multidimensional Synchronous Dataflow, IEEE Transactions on Signal Processing, vol. 50, no. 8, pp. 2064-2079, August 2002.
    [4]
    Praveen K. Murthy, Edward A. Lee, An Extension of Multidimensional Synchronous Dataflow To Handle Arbitrary Sampling Lattices, In the proceedings of the ICASSP 96, Atlanta, GA, May 7-10, 1996.
    [5]
    B.D. Theelen, M.C.W. Geilen, T. Basten, J.P.M. Voeten, S.V. Gheorghita and S. Stuijk, A Scenario-Aware Data Flow Model for Combined Long-Run Average and Worst-Case Performance Analysis, 2006 4th IEEE/ACM International Conference on Formal Methods and Models for Co-Design.

    1Researcher