Demos




Predictability of Timing through Invasive Computing

Involved Projects:

C2, A1

Contributing Researchers/PIs:

S. Roloff, S. Wildermann, F. Hannig, J. Teich

Abstract

The following demonstration presents the capability of invasive computing to drastically increase the predictability of timing of the execution of complex stream processing applications such as a computer vision algorithm chain - object detection - on Multi-Processor Systems-on-Chip (MPSoC).

Object detection algorithms are used in robotics and other application domains to detect certain objects in a video stream to control, for example, the movement of a robot. A brief overview of the individual tasks in an object detection algorithm chain is depicted in Figure 1.

Object Detection Chain

Figure 1: Object detection task chain.

In the following scenarios, this task chain is executed on an invasive MPSoC. Depending on the claimed resources and interference with other applications, different latency and throughput values as well as different variations of these values (jitter) are determined. It will be shown that using the concepts of invasive computing, these variations as measure of predictability may be reduced by isolating applications through exclusive reservation of resources. The evaluation of the following scenarios was done using the InvadeSIM simulator. The architecture configuration is shown in Figure 2. There exist five quad core RISC tiles, two I/O tiles for input and output, one global memory tile, and one TCPA accelerator tile.

Target Architecture

Figure 2: Target architecture.

Scenario I

The first scenario considers a non-invasive execution of a FIR filter and a motion planning application besides the object detection application. In this case, it might happen that the other applications are mapped on the same tiles as where tasks of the object detection applications are running. The considered application mapping on the architecture tiles is depicted in Figure 1. In order work properly, a user requirement on throughput is defined for the object detection application, it has to process the input stream with a throughput of 25 fps. An animation of the processor utilization during the processing of 12 input images by the object detection task chain is shown in Video 1. The execution trace of this scenario is shown in Figure 2. Here, for each tile and each processor on a tile, there is a blue block on the left side of the trace visualization. The processor utilizations are shown over time on the x-axis.

Mapping

Figure 1: Mapping scenario I.

Video 1: Processor utilization scenario I (12 input images).

The simulation of this scenario results in an average latency of 180 ms (to process one image) and an average throughput of 17.9 fps. Furthermore, the variability of the execution in terms of jitter in throughput and latency as measure for predictability are maximum 30% and 29%, respectively. Due to non-exclusive execution, the required throughput cannot be met in this dynamic scenario. The object detection application is disturbed by the overlapped execution with the other applications and the user requirements on throughput of 25 fps cannot be guaranteed. The next scenarios will show, how Invasive Computing helps to satisfy user requirements, where non-invasive executions cannot guarantee such requirements and to provide predictable timings by exclusive reservation of resources.

Mapping

Figure 2: Trace scenario I.

Scenario II

In this scenario, the same applications are considered, however, they are mapped on the architecture using Invasive Computing concepts. Each application first invades its required resources and then they are executed on them exclusively. The result of the application mapping is shown in Figure 3. The TCPA tile is used by the FIR filter application as well as the memory tile. A quad core RISC tile is occupied by the motion planning application. The object detection application claims all remaining tiles. An animation of the processor utilization during the processing of 12 input images by the object detection task chain is shown in Video 2. The execution trace of this scenario is shown in Figure 4.

Mapping

Figure 3: Mapping scenario II.

Video 2: Processor utilization scenario II (12 input images).

The simulation of this scenario results in an average latency of 92 ms and an average throughput of 25 fps, even that there are two other applications running on the platform. Furthermore, the jitter in throughput and latency are reduced compared to the non-invasive execution. They are maximum 18% and 7%, respectively. This results show that Invasive Computing is able to a) satisfy given user requirements, if an invasion is successful, where non-invasive executions cannot guarantee such requirements and b) provide predictable timings by exclusive reservation of resources. The following scenarios show a characterization of the object detection task chain, when no other applications are interfering in order to determine throughput and latency values according to different task to resource mappings.

Mapping

Figure 4: Trace scenario II.

Scenario III

In this scenario, the TCPA tile is not claimed by the object detection task chain. Instead, a four quad core RISC tiles and two I/O tiles are used for it. The resulting mapping of the different tasks to the tiles on the architecture is depicted in Figure 5. An animation of the processor utilization during the processing of 12 input images by the object detection task chain is shown in Video 3. The execution trace of this scenario is shown in Figure 6.

Mapping

Figure 5: Mapping scenario III.

Video 3: Processor utilization scenario III (12 input images).

The simulation of this scenario results in an average latency of 86 ms and an average throughput of 25 fps as can be seen in Figure 6 as well as the values for latency and throughput jitter. Even, if no other application is interrupting, there is already a jitter in latency and throughput, which mainly results from algorithmic reasons. Depending on the number of detected corners in an image, the two subsequent algorithms SIFT description and SIFT matching require more or less computation time. However, by using invasion, the variability in execution timings are reduced to algorithmic variabilities and disturbances by other applications are excluded.

Mapping

Figure 6: Trace scenario III.

Scenario IV

In this scenario, a TCPA tile is available and claimed by the object detection task chain for acceleration of the Harris Corner task. The resulting mapping of the different tasks to the tiles on the architecture is depicted in Figure 7. An animation of the processor utilization during the processing of 12 input images by the object detection task chain is shown in Video 4. The execution trace of this scenario is shown in Figure 8.

Mapping

Figure 7: Mapping scenario IV.

Video 4: Processor utilization scenario IV (12 input images).

The simulation of this scenario results in an average latency of 57 ms and an average throughput of 52.6 fps as can be seen in Figure 8 as well as the observed values of latency and throughput jitter. Using the TCPA as accelerator speeds up the throughput to more than 50 fps. However, still, there exists a jitter in latency as well as throughput, which cannot be removed by just using invasion. Here, algorithmic changes like rate shaping and pruning techniques are required to also eliminate this jitter.

Mapping

Figure 8: Trace scenario IV.