Project topics and materials
Get Complete Project Material File(s) Now! »
System-Level Architecture Model: S-LAM
S-LAM [38] is developed as a part of a prototyping tool called PREESM for Par-allel and Real-time Embedded Executives scheduling Method. S-LAM provides a simple description of modern architecture platforms at high level of abstrac-tion. Its description is a topology graph de ning the data exchanges in modern platform such as heterogeneous architecture.
Case studies – RVC-CAL applications
Orcc provides a complete environment for users to exploit and develop current and future video decoders by using dynamic data ow programming. We use the existing RVC-CAL applications such as MPEG4 Part 2 and MPEG High E ciency Video Coding (HEVC) which are implemented in Orcc to study all dynamic behaviors of these complex data ow applications.
MPEG4 Part 2 standard, also known as MPEG4 visual, was developed by the Moving Picture Experts Group (MPEG), a working group of the International Organization for Standardization (ISO). It was standardized in 1999 by the joint ISO/ITU (the International Telecommunication Union). It provides a highly exible toolkit of coding techniques and resources. There is a set of coding tools, organised into ‘pro les’, recommended groupings of tools suitable for certain applications. Classes of pro les comprise ‘simple’ pro les (coding of rectangular video frames), object-based pro les (coding of arbitrary-shaped visual objects), still texture pro les (coding of still images or ‘texture’), scalable pro les (coding at multiple resolutions or quality levels) and studio pro les (coding for high-quality studio applications).
Static data ow models
There are numerous data ow MoCs, which are known as static models. This kind of model assumes that actors have a xed token production and consumption on each ring.
SDF is also known as Weighted Marked Graphs in Petri Net literature. Schedulability and memory consumption of SDF applications can be known at compile-time [51]. Pioneering works on SDF graphs were published by Lee et al. in [23]. Prof. Edward Lee is famous with the Ptolemy project [52]. This project studies modeling, simulation, and design of concurrent, real time, embedded sys-tems. In this project, di erent kinds of data ow models have been developed and exploited. A free tool set for generating and analyzing SDF, CSDF and so-called Scenario-Aware Data ow (SADF) are available in the SDF 3 project [37]. Diverse studies in the literature investigate SDF model in the eld of multimedia applications such as [53, 54, 55, 56, 57, 58]. In [59], authors present a method for throughput analysis of SDF applications. Their approach is based on explicit state-space exploration and avoids the translation to Homogeneous SDF (HSDF) application. HSDF model is a special case of SDF model in which all token production and consumption rates are 1. In [60], authors address the problem of mapping HSDF applications on multiprocessor platform with the objective of maximizing application throughput by using Sat-based techniques. The au-thors in [54] propose a method to compute throughput of an SDF applications in which the execution time of actors can be parameters. To explore the parallelism with heterogeneous architectures, authors in [57] present a methodology for im-proving the system throughput by using SDF transformations. Many researchers [56, 60, 61, 58] consider their applications as SDF or HSDF model. This kind of models is also known as static model, which is easier to analyze and predict at design-time. Researchers in [55, 62] provide a complete approach to solve the allocation and scheduling of SDF applications on MPSoCs.
CSDF model extends SDF with the notion of state. With CSDF model, authors in [63] present a practical and accurate throughput analysis since their method can give tight estimates on the minimum throughput. A comparison between SDF and CSDF model were explored in [64]. The need for a tradeo between expressiveness and predictability has brought the de nition of so-called \quasi-static » data ow model [26, 65, 66].
As static data ow models are restricted in the kinds of applications they can express, these models can not express the dynamic behaviors of modern video applications. This leads to many studies of MoCs that can express the dynamic behaviors of modern multimedia applications.
Dynamic data ow models
In contrast to static model, dynamic data ow models are able to capture the behaviors of dynamic applications. In dynamic data ow domain, it is impossible to know production and consumption behavior of actors at compile time since each actor has a set of ring rules and can be red if one of them is satis ed. SADF [67] extends SDF with scenarios, which represent di erent modes of operation based on resource requirements. This makes it possible to capture a dynamic behavior of application to save resources. SADF improves SDF in terms of expressiveness to express dynamism. Di erent scenarios may di er in their execution time and communication rates. However, all scenarios are generated by a probability of occurrence and each scenario can be modeled with SDF model. Authors in [15] surveys SADF and compares di erent data ow MoCs according to their expressiveness, expressiveness, analyzability and implementation e ciency.
KPN is another MoC that can be used to express behaviors of dynamic ap-plication. However, KPN requires a complex run-time mechanism that leads to a large implementation overhead [15]. Lee et al. were pioneers in a theory of data ow process network (DPN) [22]. DPN is a special case of KPN but it can be used to model the most general form of data ow MoCs. Therefore, recent researches employ KPN, DPN models as in [68, 69, 70, 15, 71]. Hence, with embedded multimedia becoming more complex, the trade-o be-tween analyzability and expressiveness moved towards more expressive models.
Data ow tools for RVC
The initial work for introducing the MPEG Recon gurable Video Coding (RVC) framework [29] started in 2004. Both academia and industries have developed a set of tools supporting RVC framework. The key characteristics of MPEG RVC are exibility, re-usability and platform independent data ow models. In this innovative framework, the MPEG RVC working group has adopted CAL (the Cal Actor Language) [30] as part of their standardization e orts as shown in Fig. 2.1. CAL actor language was developed at University of California at Berkeley in 2001. This language was born from Ptolemy II project [52] to modeling complex signal processing systems dedicated to software and hardware code synthesis.
Table of contents :
1 Introduction
1.1 Evolution and trends in parallel systems
1.1.1 In General Purpose Domain
1.1.2 In Embedded Domain
1.1.3 Embedded parallel platforms
1.1.3.1 Homogeneous versus heterogeneous platform
1.1.3.2 Memory architectures in MPSoCs
1.1.4 Embedded system design
1.2 Data ow approach
1.2.1 Data ow models of computation
1.2.1.1 Kahn process networks
1.2.1.2 Data ow process networks
1.2.1.3 Synchronous data ow
1.2.1.4 Cyclo-static data ow
1.2.1.5 Quasi-static data ow
1.2.2 Taxonomy of Data ow models of Computation
1.2.3 Existing tools used in this thesis
1.2.3.1 Open RVC-CAL Compiler: Orcc
1.2.3.2 SDF For Free: SDF3
1.2.3.3 System-Level Architecture Model: S-LAM
1.2.4 Case studies – RVC-CAL applications
1.3 Mapping problem
1.3.1 Problem denition
1.3.2 Challenges in mapping problem
1.4 Our Contributions
1.5 Outline
2 Mapping Methodologies of Data ow Applications on Parallel Ar- chitectures
2.1 Data ow Programming Models
2.1.1 Embedded data ow models
2.1.1.1 Static data ow models
2.1.1.2 Dynamic data ow models
2.1.2 Data ow tools for RVC
2.1.2.1 OpenDF
2.1.2.2 Orcc
2.2 Embedded parallel architectures
2.3 Mapping Methodologies
2.3.1 Static mapping
2.3.2 From static mapping to dynamic mapping
2.3.3 Dynamic mapping
2.3.3.1 On-they mapping
2.3.3.2 Hybrid mapping
2.3.3.3 The perspective of hybrid mapping with runtime remapping
2.4 Conclusion
3 Communication Model Based Embedded Mapping
3.1 Problem denition
3.1.1 Application model
3.1.2 Architecture model
3.1.3 Communication model
3.2 Heuristic mapping algorithm
3.2.1 Evaluation metrics
3.2.2 GB4M2 Algorithm
3.2.2.1 Initialization phase
3.2.2.2 Computation phase
3.2.2.3 Communication phase
3.3 Experimental results
3.3.1 Simulation on Cadence virtual system platform – VSP
3.3.2 METIS – Graph partitioning for heterogeneous multiprocessor architectures
3.3.3 Results with SDF benchmarks
3.3.4 Results with real video applications
3.3.4.1 The need of run-time mapping
3.3.4.2 MPEG4-SP and HEVC decoder
3.4 Conclusion
4 Move Based Algorithm
4.1 Problem denition
4.1.1 Application model
4.1.2 Architecture model
4.1.3 Communication model
4.2 Move based mapping algorithm
4.2.1 Parameters and evaluation metrics
4.2.2 Pre-processing – PP
4.2.3 Runtime mapping initialization – RMI
4.2.3.1 Algorithm principle
4.2.3.2 Computation phase
4.2.3.3 Communication phase
4.2.4 Runtime remapping – RR
4.2.4.1 Finding the possible moves
4.2.4.2 Trade-o between migration cost and performance improvement
4.2.5 Runtime scenario based simulation – RSS
4.3 Experimental results
4.3.1 Setup environment
4.3.2 The need of runtime remapping
4.3.3 Generated application graphs
4.3.4 Impact of migration cost at runtime
4.3.5 Real application graphs
4.4 Conclusion
5 Conclusion
5.1 Conclusion
5.2 Perspectives
5.2.1 Short term
5.2.2 Long term
Bibliography
