Software Compilation Techniques for MPSoCs - Signal Processing Systems - page 1211

after partitioning is a major research topic and a requisite for an MPSoC compiler.
Several techniques, under the name of Performance Estimation ,areappliedinorder
to get such execution times: Worst/Best/Average Case Execution Time (W/B/ACET)
[ 84 ] . These techniques can be roughly categorized as:

￿ Analytical : Analytical or static performance estimation tries to find theoretical

bounds to the WCET, without actually executing the code. Using compiler
techniques, all possible control paths are analyzed and bounds are computed by
using an abstract model of the architecture. This task is particularly difficult in the
presence of caches and other non-deterministic architectural features. For such
architectures, the WCET might be too pessimistic and thus induce bad decisions
(e.g. wrong schedules). There are already some commercial tools available,
aiT [ 6 ] is a good example.

￿ Simulation-based : In this case the execution times are measured on a simulator.

Usually cycle accurate virtual platforms are used for this purpose [ 24 , 78 ] . Virtual
platforms allow full system simulation, including complex chip interconnects and
memory subsystems. Simulation-based models suffer from the context-subset
problem, i.e. the measurements depend on the selection of the inputs.

￿ Emulation-based : The simulation time of cycle accurate models can be pro-

hibitively high. Typical simulation speeds range from 1 to 100 KIPS (Kilo
Instructions per Second). Therefore, some techniques emulate the timing behav-
ior of the target platform in the host machine without modeling every detail of
the processor by means of instrumentation. Source level timing estimation has
proven to be useful for simple architectures [ 37 , 42 ] , the accuracy for VLIW
or DSP processors is however not satisfactory. The authors in [ 27 ] use so-
called virtual back ends to perform timing estimation by emulating the effects of
the compiler back end and thus improving the accuracy of source level timing
estimation considerably. With these techniques, simulation speeds of up to 1
GIPS are achievable.

Performance estimation plays an important role when compiling for MPSoCs.
Granularity, discussed in Sect. 2.2 , is directly related to the timing of the code
blocks. Is the execution time of a code block too short compared to the other blocks,
then it can be merged with into other blocks or simply ignored during the timing
analysis. Additionally, the timing information is key for driving the scheduling and
mapping decisions. As an example consider a platform with two types of PEs, RISCs
and DSPs, for the application in Fig. 4 a . Assume that the performance estimation
determines an average time t f for the execution of function f on processing type p .
Figure 10 shows possible scheduling traces for the sample application with different
partitioning and mapping. The following timing variables are used in the figure to
simplify the visualization:

t risc
f 3

t risc
f 4

t risc
f 3

t risc
f 4

Δ t 1 = + + 3 · max ( , )

t risc
f 2

Δ t 2 =