Traineeship project: Mapping an SDF graph on an MPSOC Architecture
Description
Modern embedded applications usually have real-time constraints and they are implemented using
heterogeneous multiprocessor systems-on-chip (MPSOC). An MPSOC can run multiple of such applications simultaneously, and it has to guarantee that the timing constraints are met. Moreover, the applications can be started and stopped by external events (e.g. user interaction), and when these events
appear, the system has to allocate resources for the new applications, keeping everything allocated for
already running applications unchanged. This assignment will focus on the mapping trajectory part that
is concerned with assigning tasks of applications to processors.
In this project an environment for mapping a real-time application, described by a Synchronous DataFlow (SDF) graph, on a heterogeneous multiprocessor systems-on-chip architecture, is developed. The
actors of the SDF graph correspond to the tasks to be assigned to processors. The target architecture is
abstracted in the form of an architecture graph, where the nodes are processing tiles with processors of
some given types and local memory, and where the edges are point-to-point communication channels
with a given bandwidth and propagation delay. The resulting mapping problem is closely related to the
well-known bin-packing and knapsack problem.
The mapping environment to be developed in this project will consist of two parts:
- A parser that reads the following information from XML files with a specific format and transforms
them into easy-to-use internal data structures.
- Application SDF graph:
- for each actor: execution time for different type of processors, number of consumed and
generated tokens per firing, local memory needed.
- for each channel: maximum buffer size, size of a token.
- timing constraints (a specific actor must fire x times per second).
- Architecture:
- for each processor: type, performance (cycles/s), local memory size.
- for each channel: bandwidth, delay.
- System usage:
- For each channel and processor how many resources are already used (channel:bandwith,
processor:cycles, memory).
- An interface where different mapping algorithms may be plugged.
The scientific part of this project is to implement an existing algorithm [MMBvM05] and to inves-
tigate possible improvements. Besides mapping a real-time application on an MPSOC platform tha
already runs other applications, the algorithm generates also a scheduling for the application (i.e. an exe-
cution order for all tasks assigned to a single processor), such that it will meet the timing constraints. The
aim of the algorithm is to maximize the freedom for mapping the next applications that may appear in the
system. To check the mapping quality and compare different version of algorithms, multiple sequences
of randomly generated application SDF graph are used. The more applications the algorithm could map,
the better the algorithm is.
[MMBvM05] Orlando Moreira, Jan-David Mol, Marco Bekooij, and Jef van Meerbergen. Multiprocessor resource allocation for hard-real-time streaming with a dynamic job-mix. In Proceedings of the 11th IEEE Real Time and Embedded Technology and Applications Symposium,
pages 332341, 2005
Duration
July 2005 - October 2005
Student:
Supervisor:
|
