A constraint programming scheduling solver for the MPOpt programming environment

3.1 Target architecture

Figure 1 shows a pictorial overview of the STI Cell Broadband Engine Hardware Architecture. The Cell is a non-homogeneous multi-core processor which includes a 64-bit PowerPC processor element (PPE) and eight synergistic processor elements (SPEs), connected by an internal high bandwidth Element Interconnect Bus (EIB).

The PPE is dedicated to the operating system and acts as the master of the system, while the eight synergistic processors are optimized for computation-intensive applications. The PPE is a multithreaded core featuring two levels of on-chip cache. The SPE is a computation-intensive coprocessor designed to accelerate media and streaming workloads. Each SPE consists of a synergistic processor unit (SPU) and a memory flow controller (MFC). The MFC includes a DMA controller, a memory management unit (MMU), a bus interface unit, and an atomic unit for synchronization with other SPUs and the PPE.

Efficient SPE software should heavily consider memory usage, since the SPEs operate on a limited on-chip memory (only 256 KB local store) that stores both instructions and data required by the program. The local memory of the SPEs is not coherent with thePPE main memory, and data transfers to and from the SPE local memories must be explicitly managed by using asynchronous coherent DMA commands.

3.2 Synchronous data-flow graphs

Synchronous Data-Flow Graphs (SDFGs) [26] are used to model periodic applications that must be bound to a Multi Processor System on Chip. They allow modeling of both pipelined streaming and cyclic dependencies between tasks. This model of computation represents data movements between activities through tokens (i.e. dot on the arcs of the graph). To assess the performances of an application on a platform, one important parameter is the throughput. In the following we provide some preliminary notions on synchronous data flow graphs used in this paper.

An SDFG is a pair 〈 V , A 〉 consisting of a finite set V of activities (also called, nodes, tasks or actors) and a finite set A of dependency arcs. A dependency arc e → = 〈 i , j , p , q , δ 〉 denotes a dependency of activity j on i, with i , j ∈ V. When i executes, it produces p tokens on e → and when j executes, it consumes q tokens from e →. Arcs 8 may contain initial tokens δ = tok ( e → ) = tok ( i , j ).

An activity execution is defined in terms of firings. An essential property of SDFGs is that every time an activity fires it consumes a given and fixed amount of tokens from its input edges and produces a known and fixed amount of tokens on its output edges. These amounts are called rates.

SDFGs in which all rates equal 1 are called Homogeneous Synchronous Data Flow Graphs (HSDFGs, [26]). Every SDFG G = 〈 V , A 〉 can be converted to an equivalent HSDFG G H = 〈 V ¯ , A ¯ 〉, by using the conversion algorithm in [27].

In Fig. 3 we report the HSDFG corresponding to the SDFG in Fig. 2 where the (unary) rates areomitted.

4.1 Framework models and languages

4.2 Front-end compiler

This section briefly describes MPOpt-Cell Programming Model, namely the front-end compiler.

MPOpt-Cell adopts a novel programming model based on the familiar C language, augmented with some compiler directives that allow the programmer to easily describe data-flow computation. The front-end compiler automatically outlines a parallel C program – describing tasks and data streams of the SDFG – which is sent to the backend Compiler.

Our approach borrows from the coding style of the well-known shared memory programming model OpenMP.

A compiler is in charge of transforming the annotations into code which spawns parallel threads at runtime and manages data sharing among them.

Therefore we define a set of directives which provide the needed abstractions to model a SDFG (i.e. actors, incoming/outgoing arcs, etc.). The role of our front-end compiler is twofold.

First, the directives inserted by the programmer are processed so as to generate C code which will be compiled for the SPEs.

The main benefits of this approach reside in an increased ease of use and productivity, since a programmer does not have to learn new language constructs or a brand-new programming language.

4.3 Runtime system

The bottom layer of the MPOpt framework consists of a target-specific Backend Compiler, made up of static and dynamic components. At the heart of our execution engine there is a efficient runtime system (RTS) which encapsulates hardware specificities and is in charge of ensuring efficient task management, data transfer and synchronization. The RTS effectively maps computation (tasks) and communication (data-flow) on top of hardware resources, but requires that a schedule for task execution is provided as an input.

The runtime system introduces an abstraction layer which hides the difficulties of the parallel architecture, such as load balancing, synchronization, and communication between the main components of the streaming application. It orchestrates the execution of all the components in the data flow graph application and provides both streaming and event communication primitives to the components. Moreover, using centralized resource management, the runtime can dynamically balance the load over the available SPE processors. The runtime system leverages different structures for its execution, namely SDFG tasks, queues, executors and a resource manager.

Note that this is the only component specifically designed for the Cell platform. Hence, using the framework with another platform is feasible, and only the RTS system would require some changes.

5.1 Constraint programming model

The solver used in this approach is based on CROSS (presented in [18]). The main underlying idea is to focus on a λ-width time window. We adopt a start/end time decomposition similar to that in [34]. The start time of execution 0 of activity i (i.e. start (i, 0)) can be expressed as: start ( i , 0 ) = s i + β i · λ(1) where s _i is a value in the half-open interval [0, λ [ and β _i is an integer number. In practice, β _i identifies the iteration when activity i is first scheduled and s _i is its relative start time within the corresponding λ-width time window, i.e. its modular start time.

Figure 7 shows two different schedules: the former (a) is a classic schedule, computer over a horizon-length time window (usually the sum of the execution times of all activities), while the latter (b) is the relative λ-width time window schedule (based on modular algebra).

Precedence relations are modelled through the following temporal constraint:

s j + β j · λ ≥ s i + ( β i - δ ( i , j ) ) · λ + d i + θ ( i , j )(2)

where δ_(i,j) is the number of tokens on the arc (i, j), d _i is the duration if the activity i, and θ_(i,j) is the latency of the communication between i and j (i.e. a time-lag).

Note that if the (modular) precedence constraints are satisfied for iteration 0, then they are satisfied for every other iteration.

Beside the application model, the Constraint Programming model takes into account the architectural components by describing resource constraints and architectural features.

In this framework, we describe the Cell model as a single cumulative resource of capacity equal to the number of SPU.

The restrictions on the resources are therefore modeled through a cumulative constraint 9 ; the constraint prevents the solver from finding a number of concurrent executions higher than the capacity of the resource.

The basic idea of the solving process is to model the effects of mapping and scheduling choices by means of graph modifications. The solver block assumes a self-timed scheduling policy 10 and the execution order is determined on the modified graph. In details, we modify the graph adding edges that force precedence relations between scheduled tasks so as to prevent tasks from competing for the SPEs. The runtime scheduler processes these edges as fake data communications between actors. Note that differently from a state-of-the-art disjunctive approach presented in [36], where the graph is modified during search, in the MPOpt-Cell solver the augmented graph is constructed when the search stops with a feasible solution.

The self-timed execution of a periodic application modeled with a synchronous data-flow graph consists of two different phases (see [37]): the transition phase and the periodic phase. The former appears only once at the beginning of the execution while the latter is periodically repeated ad infinitum. In this context, a static scheduling strategy [27] should include a different schedule for each execution phase. Conversely, thanks to the use of modular algebra, our solver produces a single static schedule that represents both phases (see Fig. 8). The transient and the periodic phase schedules are easily inferred by considering the iteration values of each task in the solution. In fact, the solution includes the modulus value λ and the set of start times 𝒮 _i and iteration numbers β _i . Before the application enters the periodic behaviour, some of the tasks (namely those for which β _i  > ω, with ω as current execution iteration) simply do notstart.

The type of solution provided by the CROSS solver 11 naturally suggests the use of a time-triggered schedule; on the opposite the MPOpt-Cell runtime system is based on a self-timed policy. The motivation for this choice is that modeling the precedence relations with arcs on the graph allows the solver to obtain flexible solutions. Moreover, if the actual execution times are shorter than the expected times it allows the runtime to deliver higher throughput.

At the end of the search, a novel algorithm translates an assignment of start and iteration variables to graph modifications and constructs the new GDL+ document. Therefore the output of the MPOpt-Cell solver consists of one “enhanced” GDL document (referred to as GDL+), which is essentially the input GDL with additional allocation and scheduling information. Namely, we specify the node affinity that references a resource unit chosen for task allocation or we add dummy arcs (precedence arcs) used to force task ordering on a specific resource. The algorithm operates into two steps:

Allocation: the algorithm extracts from the solution the mapping association for each node (even if the allocation problem is not considered in CROSS). In fact, the use a single shared resource of capacity equal to the number of SPU guarantees that the maximum number of concurrent tasks is equal to the number of SPU (see Section 3 for details).

Note that counter-intuitively an arc ˆ (i, j) can have a negative number δ ̇ of tokens (i.e. δ i , j = δ ̇ < 0). This means that the source activity i has to execute at least δ ̇ times before the first execution of sink activity j.

6.1 Predictability evaluation

Predictability has two main facets: the capability to produce a regular throughput with minor local variations and the ability to predict whether throughput constraints may be satisfied or not before deployment stage.

In the case of real-time applications it is essential to ensure the respect of definite deadlines and consequently a wide variability range is unacceptable.

Figure 9 depicts the results of a first experimental set: it graphically represents the variability of the measured execution times on both CellSs (left side) and MPOpt-Cell (right side).

A numerical scale was not reported in the chart because absolute values are not significant to understand the variability dynamics.

The distance between a point and the chart center shows the execution time of a single experiment. Hence, all points equidistant from the center represent different experimental values with the same execution time. Each application is depicted by a line whose points map the values measured at subsequent application launches. The circularity factor of each line directly traces the regularity of the throughput for the correspondent application: the closer the line to a perfect circle, the more regular execution times.

The experimental values related to MPOpt-Cell have a good circular factor, namely a limited variability. This aspect can be attributed to the high determinism derived by the use of a static scheduler.

Conversely, Cell Superscalar provides a dynamic scheduler which is based on a task dependency graph which sometimes allows locally better results, but exhibits an unpredictable runtime overhead. Therefore, the bad circular factor of corresponding lines highlights this behaviour.

Figure 10 shows the result for a second experimental setup: this was conducted by feeding the solver with task worst case/best case execution times, instead of average ones.

The off-line predicted throughput values are compared with the measured one at runtime, which is based on a schedule obtained by average execution times. In detail, each column in the figure refers to a different schedule, computed by taking into account worst case/average case/best case execution times; for each benchmark, the left- and right-most columns present off-line predicted throughput values of the considered schedule, while the middle column reports an experimentally measured value.

One can see that the worst case execution times (WCET) and the best case execution times (BCET) schedules establish strong bounds for the eligibility range of runtime throughput values (depicted in Fig. 10 by overlying vertical lines). In particular, the solution provided when all tasks are assumed to execute with the BCET provides a conservative upper bound on the throughput. More interestingly, the WCET solution provides an estimate of the best safe throughput value, i.e. the tightest throughput requirement the system can met.

Moreover, by providing the solver with WCETs, the predicted value is very close to the actual one, assessing the high accuracy of the adopted model. This allows to check in the early steps of the design process if the performance requirements can be met or an upstream optimization stage is required. Overall, this can potentially reduce the development time.

6.2 Performance evaluation

Figure 11 shows the results of a bare performance comparison (in terms of throughput) with Cell Superscalar. The figure bars represent the throughput values calculated as a mean of 200 program iterations: overlying vertical lines outline the interval of samples variability, i.e. the range of measured throughput values. The endpoints of these lines represent the maximum and minimum values originated by experimental results.

The throughput mean value is an assessment of the performance one can expect with a high number of iterations: it is particularly significant in a scenario characterized by continuous data streaming and in this context it can be naturally used as a performance indicator. Our approach is comparable to Cell Superscalar on FFT, it has better performance on FM radio and even better performance on matrixmultiplication.

The runtime performance of MPOpt-Cell framework is due to a set of concurrent factors: (1) the effective use of the SDF model, that fully exploits the data parallelism of streaming applications and avoids unnecessary synchronization barriers; (2) the static scheduling technique, which provides low-overhead resolution of possible resource conflicts by compile time allocation and scheduling; (3) the double buffering technique, that reduces the overhead of data transfers; (4) the use of an optimized schedule, which is based on appended precedence relations and allows the framework to stretch to accommodate actual execution times.

The low performance measured on the matrix multiplication benchmark using CellSS (40:1) motivated a deeper analysis. The performance gap appears to be attributable to framework design issues. Since CellSS does not natively support a streaming model, it is necessary to insert a synchronization barrier after the computation of the submatrices multiplication at each iteration step: in this way we can obtain the correct result without using ad-hoc implementation tricks. To investigate the impact of such limitation, we ran some experiments on MPOpt-Cell by introducing an unnecessary barrier. We observed that the barrier represent an important limitation to the application throughput, indeed with this barrier the throughput achieved on MPOpt-Cell is halved. Still, the barrier alone does not explain the remaining performance gap (20:1). A further conjecture involves optimization issues related to data transfers, which are treated by CellSS using a locality-aware heuristic.