Keywords: Multi-core, many-core, dataflow, mapping, scheduling, SMT solver

Ab s t rac t

In order to achieve performance gains in the software, computers have evolved to multi-core and many-core platforms abounding with multiple processor cores. However the problem of finding efficient ways to execute parallel software on these platform is hard. With a large number of processor cores available, the software must orchestrate the communication, synchronization along with the execution of the code. Communication corresponds to the transport of data between different processors, which either can be handled transparently by the hardware or explicitly managed by the software. Synchronization is a requirement of proper selection of start time of computations e.g. the condition for software tasks to begin execution only after all its dependencies are satisfied.

Models which represent the algorithms in a structured and formal way expose the available parallelism. Deployment of the software algorithms represented by such models needs a specification of which processor to execute the tasks on (mapping) and when to execute them (scheduling). Mapping and scheduling is a hard combinatorial problem to solve with a huge design space containing exponential number of solutions. In addition, the solutions are evaluated according to different costs that need to be optimized, such as memory consumption, time to execute, static power consumption, resources used etc. Such a problem with multiple costs is called a multi-criteria optimization problem. The solution to this problem is not a unique single solution, but a set of incomparable solutions called Pareto solutions. In order to track multi-criteria problems, special algorithms are needed which can approximate the Pareto solutions in the design space.

In this thesis we target a class of applications called streaming applications, which process a continuous stream of data. These applications typically apply similar computation on different data items. A common class of models called dataflow models conveniently expresses such applications. In this thesis, we deal with mapping and scheduling of dataflow applications on many-core platforms. We encode this problem in form of logical constraints and present it to satisfiability modulo theory (SMT) solvers. SMT solvers, solve the encoded problem by using a combination of search techniques and constraint propagation to find an assignment to the problem variables satisfying the given cost constraints.

In dataflow applications, the design space explodes with increased number of tasks and processors. In this thesis, we tackle this problem by introducing symmetry reduction techniques and demonstrate that symmetry breaking accelerates search in SMT solvers, increasing the size of the problem that can be solved. Our design-space exploration algorithm approximates the Pareto front of the problem and produces solutions with different cost trade-offs. We validate these solutions by executing them on a real multi-core platform.

Further we extend the scheduling problem to the many-core platforms which are assembled from multi-core clusters connected by network-on-chip. We provide a design flow which performs mapping of the applications on such platforms and automatic insertion of additional elements to model the communication. We demonstrate how communication with bounded memory can be performed by correctly modeling the flow-control. We provide experimental results obtained on the -processor Kalray MPPA- platform.

Ac kno wle dg e m e nt s

Foremost I would like immensely thank Oded Maler who is my thesis supervisor, but much more. He persistently helped me throughout my PhD. and provided motivation, research directions to carry out my work. But more importantly he gave me unparalleled freedom to explore my varied interests while choosing a topic for my thesis. He made me understand research and many other things in general and broader sense. He has been a continuous source of inspiration and motivation, to carry out the work, especially in times when things were obscure. He always provided me more than enough time and guidance where it was utmost necessary and ensured that I remained focussed on my topic. It was a privilege to work at Verimag especially with Oded, since he always provided a healthy and relaxed work atmosphere. He always blended humor with our daily chores at Verimag which teared down undesired tensions and frustrations. I had a great time at Grenoble working under his supervision. He was like a friend when we met over many lunches or dinners, with his entertaining and knowledgeable discussions on diverse topics. I will forever cherish the time that we shared during these years.

I am deeply thankful to Peter Poplavko who inspired me to work on dataflow models. Although according to Oded, he hijacked me to this domain. Peter played a very important role in my thesis. He was providing me a continuous feedback on my work. He enabled me to understand how to persistently attack a problem. He was actively guiding me throughout all my PhD. I thank him for all our discussions, code reviews, publication writing exercises etc. in which he invested a lot of his time. Especially the feedback on my thesis even when he was on vacation was of great help. I am confident that I would never have been able to complete this thesis without him.

I would like to thank the jury members and the reviewers for attending my thesis defense. I especially thank them for their valuable feedback on the manuscript. The feedback gave me an additional perspective to my own work. I am very happy to have such a jury.

I also want to thank the group at Technical University of Eindhoven who supported me for an internship. It was a very different and wonderful experience to work there. Prof. Sander Stuijk and his team were immensely supportive during my work. A few names I would like to mention are Hamid Reza Pourshaghaghi, Francesco Comaschi, Sebastian Moreno, Rosilde Corvino, Karthik Chandrasekar. Out of my office I made many friends in Eindhoven who accompanied me in several evenings for dinner, playing cards, skating and many other things. I will always remember the time that I spent with Deepak Jain, Srivathsa Bhat, Sushil Shirsath, Sandip Pawar, Aroa Izquierdo and many others.

I want to thank all my colleagues in Verimag. Sophie Quinton, Irini-Eleftheria Mens, Abhinav Srivastav, Alexios Lekidis and many of them. We always crack jokes on PhD. life and make fun of our situations which seemed to be going nowhere. I believe I had a great working environment, sharing my views, talks, presentation etc. with my friends. I would like to convey my thanks to the administrative staff which was a life-line for me in France. I still remember my struggles as a non-french speaking foreigner and without their help I would have been nowhere.

A special thanks goes to Dorit Maler. I enjoyed the time that we spent with her in informal meetings. We shared such memorable discussions, that I would cherish for rest of my life. I i still remember how confident I felt after I talked with her just before my defense. She is a wonderful person, and I feel lucky to know her closely.

Finally, I want to thank most supportive and loveable parents, who have been there for me always, irrespective of all the things. I am indebted to them to the last bit for being there and bringing the best out of me. Along with them, I thank my sisters and extended family for their support even if I am far away for a long time. I want to thank my wife "Vrushali", for her constant support in good and bad times. She accompanied me without any complain irrespective of my negligence towards her. I am grateful to have such companion. I dedicate this thesis to my parents and my wife. M ulti-core processors are now an unavoidable fact of the information processing industry.

Over the years, technology advancement has seen the scaling of Moore's law []. While the technology evolved for smaller and smaller transistor size, more amount of hardware could be fabricated on chip with same area. Increasing clock speed to gain performance improvement, a technique followed for many years, could no longer provide performance benefits, because of several issues like power consumption, current leakage, electrical interference, chip-design issues etc. []. In order to exploit the advantages of technology scaling, multi-core processor came into existence. It became clear that adding multiple processor cores to the same chip provides more benefits and performance rather than over-clocking a single processor []. This trend is illustrated in Figure ., where the evolution of the processors gradually shifts towards multi-core approach.

Another motivational factor for multi-core processing was the advancements in data processing algorithms, which demanded extra computational power. Applications which perform video processing, audio-video rendering, and many other signal processing applications became computationally heavy with their evolution. In addition, such applications have stringent deadline requirements to be met on a platform having limited resources. They also provide a degree of freedom, which involve exploitation of different levels of parallelism. Multi-core approach is often a suitable solution for parallel applications. It is well-known that the speedup due to multi-core processor is less than proportional to their number, nevertheless, it still remains attractive in power-performance trade-offs.

 . mult i -c or e p r oc e s s or s y s t e m a r c h i t e c t ur e A typical embedded system has to perform various tasks. For example, a cellphone would display images, play video/audio, send and receive messages, perform data transfer and do more. In real-time systems, the tasks have strict deadlines. For example, a cell-phone is receiving a message in background while it is decoding audio and video data and displaying it on the screen. It has timing constraints such that it should not drop frames while doing audio/video processing to ensure quality of the service. At the same time, the communication protocol to receive messages requires messages to be exchanged at definite time intervals. Handling such a wide variety of tasks using only one processor is difficult in practice. This will require a processor with high clock frequency, which in turn will incur higher power consumption. On mobile platforms, the resources such as energy resource are limited and must be optimally used.

In order to satisfy these constraints, designers use a piece of hardware called as MPSoC (MultiProcessor System on Chip) []. MPSoC's typically have dedicated hardware for some functions. For example, there is a dedicated IP (Intellectual Property) block, to process the input from keyboard. Suppose that instead of dedicated IP block, the general purpose processor (GPP) handled this task in the software, which is a possibility. This will increase the load on the processor, which will have to continuously poll for updated status from the keypad. With the IP block, this polling is offloaded to the dedicated hardware and it informs the GPP only when it has some relevant information to process. Suppose a key is pressed by the user, it is processed by the IP block and checked for its validity. And then it generates an interrupt to the GPP to process this information. Thus GPP is responsible for management of many such blocks, in addition to management of the software. Figure . shows an example MPSoC, where different functions such as Display, Camera, Keyboard, etc. are offloaded to a dedicated reduced instruction set computing (RISC) hardware. However, the hardware itself is managed by a GPP.

Dedicated hardware is a long-debated trade-off between performance and flexibility. Application Specific Instruction-set Processor (ASIP) can be optimized to provide high performance at low energy cost. The price to be paid is in terms of flexibility. If there is need to change in protocols, this hardware cannot be used. For example, if there is dedicated hardware for H. video, it cannot be used for newer specification H.. In order to support newer algorithms and their respective upgrades, it is desirable to add more GPPs on the chip rather than to develop a dedicated hardware. Owing to this fact, there were two interesting types of processors were developed. First one is SIMD (Single Instruction Multiple Data), the chip . Taken from [] In this architecture, the processors execute independently of each other. This is the class of multi-core systems that we target for our work.

The design of multi-core processor architectures are driven mainly by the design costs pertaining to its application. Typical design and manufacturing of such systems requires investments in millions of dollars. Thus re-usability of such designs are also of primary importance. To make these systems generic and applicable in a wide range of applications typical system architectures have been followed. The dedicated IP blocks are re-used in the design, which brings lot of benefits, especially for verification of the design. Figure . shows an example of a multi-core architecture. Such multi-core systems consists of following hardware components -

.. Host Processors

Host Processors consist of a single or a group of general purpose processors which are used mainly for management tasks. Typically these group of processors are responsible for running operating systems or firmware and launching applications. They also handle other tasks like serving the hardware requests, running single-threaded program etc. The host processors are the masters of the systems and their main job is to control all the other pieces of hardware components and serve their requests.

.. Peripheral Devices

Peripheral devices typically consist of Application Specific Instruction-set Processor (ASIP) which are dedicated to a specific functionality. As seen in Figure ., the peripheral devices like USB, Display etc. are the ASIP processors which are dedicated to their respective functions. They provide a minimum instruction set, which can be used to perform a restricted task. The advantage of ASIP is that, they are optimized to run a specific function efficiently. Thus they provide high performance and reduce power consumption. However, it comes at the cost of limited flexibility and reprogramming. In contrast, GPP are less efficient compared to ASIP, but they provide high flexibility. In addition to ASIPs, some architecture also have Digital Signal Processor (DSP) which have SIMD or VLIW (Very Long Instruction Word) execution model. These processors are highly optimized to process data in parallel by using a single instruction. They are helpful in efficient execution of signal processing algorithms like filter banks, Fourier transforms, convolution etc. Application Specific Integrated Circuit (ASIC) also form a part of peripheral devices. These hardware circuits are devised to perform only specific tasks and are more efficient than ASIPs or GPPs, but at a cost of no flexibility.

.. Multi-core Fabric

The motivation behind introduction of multi-core accelerator is to improve the response time of the programs that have portions executing in parallel as shown in Figure .. Multi-core fabric is typically used to offload the parallel computation of the program to execute it faster than on a single processor.

The multi-core fabric typically consists of multiple symmetric processors. Sometimes the symmetric cores are grouped in clusters [, ]. The obvious benefit of having clusters is to limit number of processors sharing common resources, resulting in less contentions and faster access. Typically, memory is a resource which is extensively used by the processor. If thousands of processors access memory, then memory will be a huge bottleneck, resulting in worse performance. Clustering helps to reduce number of processors to contend for such resources, for example by adding local memories to every cluster, which are synchronized with the main memory using either explicit transfers or synchronous hardware mechanisms (cache).

Seq 0 A 0 A 1 B 0 B 1 B 2 B 3 C 0 C 1 C 2 C 3 Seq 1
(a) Sequential execution on single processor The memory access in a computer system is the biggest bottleneck in the advancement of the processor technology. The gap between the the processor and memory speeds is increasingly becoming larger. Caches were added to processor systems which helped to close this gap. Multilevel caches became necessary to further boost the performance. In multi-core processors, they bring additional problems like extra area and power overhead, maintaining cache coherence (maintaining same copy of data in all the caches of the system) which limits scalability [, , ] etc.

Seq 0 A 0 A 1 B 1 B 0 B 2 B 3 C 0 C 1 C 2 C 3
Owing to such and many other issues, the multi-cores generally follow a Non-Uniform Memory Access (NUMA) model, where though all the memory is directly or indirectly accessible to all the cores, the access times differ according to hierarchy. Another problem with the cache in hierarchical memory, is that the access time for the cache is unpredictable (or in a wide range). If data is not found in cache, the amount of time required to bring data from main memory to cache depends on various factors like memory access latency, contentions on network, DRAM architecture and so on. Further, when processing is done in parallel, it can trigger cache coherence mechanism, maintaining the same copy of data in different caches to update the copies. This data traffic brings a further unpredictability in the software. Many a times, handling of cache coherence is offloaded to the software, making hardware design simpler. Some architectures provide scratchpad memories, which is located on-chip close to the processor. The difference is fast and predictable access as contrary to slower and with larger variation in access time for off-chip memories.

.. Network Interconnect

With increasing number of transistors and hardware on the chip, as discussed before, it became increasingly difficult to maintain a single clock source with small skew across the entire chip. Due to this Globally Asynchronous Locally Synchronous (GALS) approach was introduced, which involves using different clocks in different region of the chip. Traditional approaches like Point-to-Point connections, shared bus, etc. incurred number of issues to connect high number of hardware blocks. These issues include performance, dynamic power dissipation, wire delay, crosstalk, global routing congestion etc. In addition, with the increasing complexity, performance requirements, power issues, real-time requirements, Network On-Chip (NoC) came into existence []. In NoC, the communication message is split into packets which are eventually transmitted on the packet-switched network. Due to their regular structure, fragmentation of wires and data multiplexing, they resolve many of the abovementioned problems. A detailed survey of various NoC techniques and architectures are found in [, ].

 . mult i -c or e s oft wa r e

Given that we have a multi-core processor architecture, with the applications executing on them as a software, the question is how much speed-up can be acquired compared to the single core execution and how to optimize it. In this context, given a parallel application and a parallel processing architecture, the software programmer has a very high number of design choices at various levels.

These choices can be briefly described as -■ Software : programming model and languages, portability, performance, re-use ■ Algorithm : exposing the parallelism, and a set of design parameters influencing its execution, that can be chosen by the programmer.

■ Models : abstraction of hardware platform, abstraction of software details to focus on the timing properties.

■

Optimization tools and methods : heuristics and formal methods to be used for optimization, mapping and scheduling algorithms Given with all these choices, it is not practically possible to evaluate every combination. In many cases, these decisions are made by intuition rather than by theory. It becomes hard to analyze if the design choices made by the programmer were correct and ensure optimal utilization of the resources. With these mentioned points, we can roughly describe the theoretical and practical issues in design and implementation of software on multi-core processors.

.. Theoretical issues ... Theoretical limit for the speedup When an application is executed in parallel, the speedup obtained compared to its sequential execution is theoretically limited by the Amdahl's Law.

Amdahl's Law for maximum speedup in parallel execution of a program on n processors is given by -

Speed up = 1 (1 -p) + p n
where, n ∈ N number of parallel threads in execution p ∈ [0, 1], is the proportion of the program that can be made parallel Thus we can observe that, the maximum speedup is directly dependent on the sequential and the parallel parts of the program. Even if we have infinite processors for the execution of the software, still the speedup obtained will be limited by the factor 1 1-p . We should note that this is only a theoretical limit. In practice, the program execution faces various issues like cache conflicts, network contentions, synchronization and communication overheads etc. It is difficult to take into account all these factors; however it becomes apparent that the actual speedup that is obtained will be less than the theoretical speedup.

... Parallelization of the Software

Designing a parallel algorithm and expressing the parallelism efficiently is a challenging task. It refers to the concurrent execution of different parts of an algorithm. There are several types of parallelism, as discussed below.

Task Parallelism refers to different tasks in an application, that can be executed in parallel. For example, in a word processor, one task waits for input from the user and displays it on the screen, whereas another parallel task immediately processes the input in parallel and check for error in a given dictionary. These  tasks can run in parallel and can be represented in a task graph. An example of task parallelism is shown in Figure .(a). Maximum amount of task parallelism is equal to the task graph width.

Data Parallelism is the same task executing on different data. Single Instruction Multiple Data (SIMD) and Single Program Multiple Data (SPMD) are different implementation schemes which benefit from data parallelism. The difference between them is that, in SIMD on every piece of data, each processor executes the same instruction. This is the type of input suits vector processors like GPUs. In the case of SPMD, each processor executes same software subroutine on a separate piece of data. Thus due to coarse granularity, the instructions may differ between different data-parallel tasks (because of data dependent operations). Due to this characteristic, different data-parallel tasks can have different execution times.

For example, if we execute a blur filter on an image, in the output each pixel is replaced by the mean value of its x neighborhood. This filter can operate independently on each pixel. Figure .(b) illustrates data parallelism. It looks similar to task parallelism, however with some key differences. In data parallelism, the tasks execute same piece of software on different piece of data, making the execution times of data-parallel tasks same (or nearly the same). Further the granularity and the number of tasks can be an option for the programmer, which is less the case for task parallelism. For example we can join tasks A 0 and A 1 into one task of higher granularity.

Pipeline Parallelism is the possibility of executing another instance of the entire task graph, before the completion of previous instance. Figure .(c) shows an example of such execution of task graph shown in Figure .(a). We call execution of the graph once as an iteration of the graph. We observe that the execution of iteration  finishes with execution of task E, however, task A of the next iteration starts before task E of the first iteration finishes. This increases the throughput of the application, which is the number of graph instances executing per unit time. It brings extra efficiency to execute such pipelined schedule, however the analysis of such schedule is more complex. Further, programming such schedule also has to ensure the data communication between tasks. The pipelined parallelism can be partly modeled by task and data parallelism if we concatenate multiple instances of the task graph into one more complex instance.

Instruction-level Parallelism (ILP) is different from that of SIMD data parallelism operating at the instruction level. In ILP, different instructions of a sequential program can be executed in parallel. For example, if the program has two instructions without dependency between them, they can execute in parallel in hardware by using hardware pipeline. Superscalar processors perform pipeline dependency analysis in hardware for parallel execution. To write such code explicitly would be a complex process which results in unportable code, specific to the processor. Further the benefits gained by this optimization would be minimal, and therefore we don't explore this parallelism. It is taken care of by hardware and compiler.

... Programming Models and Languages

Given an algorithm for performing tasks and processing data, it should be represented with a model of computation. The model abstracts the algorithm in order to hide the fine details of a program, but still represent important characteristics of the algorithm, primarily its parallelism, that can be used for optimization. For example, in Figure . the model used is task graph. It represents the precedence of the tasks and also indicates about which tasks can be executed in parallel. There are different models of computation available for specific class of problems. We discuss this issue detail in Chapter .

In addition to the programming models, there is need of programming languages which can express the data processing in these models in order to enable their execution on the hardware platforms. Today there is no standard way of programming parallel platforms. There have been various efforts to develop languages in the context of different target architectures and programming models. OpenMP [] is an extension to C/C++ language, which consists of set of compiler directives and library routines to specify parallel computations for a shared memory architecture. It annotates the loops and parallelizable code in a sequential program, which is used by the OpenMP compiler and runtime to effectuate a parallely executing code on the hardware. Recent versions of OpenMP support task parallelism. However, OpenMP is designed more for shared memory programming. There have been efforts to implement it on MPSoC architectures [, , ].

OpenCL [] and CUDA [], target typically the GPU architectures. They are efficient in expressing and optimizing the SIMD kind of operations. In addition they support the typical GPU hardware which has different levels and types of memories. There have been recent work [] on using OpenCL for multi-core platform with certain restrictions. There are many other works like MPI [], Cilk [], PGAS [], ZPL [] etc.

Overall the programming languages and models should provide the following ■ Abstraction of the application algorithm, independent of the hardware platform with a separation between algorithm and implementation.

■

Data abstraction and sharing conventions, in order to utilize different levels of memory in the hardware platform effectively.

■

Portability to different hardware platforms.

■

Execution model transparency, which in turn will help the tools and provide the programmer with a better understanding of how the code will execute on the hardware platform, facilitating the design choices.

■

Interoperability with existing code. With new programming languages, one should not have to always completely rewrite all the programs that have already been written in other languages. It should be easy to migrate the code from other languages.

... Deployment of Parallel Applications

Deployment of applications refers to organizing the execution of the program on the hardware platform. It consists mainly of two steps: ■ Mapping is the spatial allocation of processor resources to the tasks to execute in parallel. It aims at optimizing the properties related to the amount of allocated resources, like power consumption, communication cost, load-balancing etc.

■

Scheduling is the temporal allocation of processors between different tasks. It aims at optimizing the properties that depend on task execution order like response time, communication buffer size etc.

Embedded systems typically operate under extra-functional constraints. Hence deployment of applications has to consider various requirements such as throughput, response time, power consumption, load balancing, data communication etc. All these variables are elements of a multi-criteria optimization [] problem where the cost variables are in conflict with each other. For example, if we use two processors instead of three, shown in Figure .(c), we have to execute task D on either processor P 1 or P 2 . This will delay the execution of task E, thus increasing the response time of the application.

In such case, the optimal solution is not unique, but rather a set of incomparable solutions called Pareto [] set. These solutions represent different trade-offs between the cost variables.

Exploring the design space and finding the Pareto solutions requires a model of computation as well as a model of the hardware platform. The application model captures different aspects of algorithms, such as concurrency, data communication, precedence constraints etc. In contrast, the hardware platform models capture the hardware resources such as number of processors, communication links, interconnect bandwidth, power consumption, memory capacity etc. Deployment involves finding a solution which can make efficient use of all these resources in the hardware meeting the performance goals. Both the models, while abstracting information, lose some fine level details. This is a natural trade-off between efficiency in finding solutions and accuracy, giving rise to performance gap between the predicted properties and its actual execution.

Unavailability of parallel programming expertise

Due to all these factors, the multi-core software development faced difficulties. A variety of different architectures made it impossible to standardize programming models and tools for this domain. Current software development tools for multi-core processors are far less matured than those for single core processors and even those for hardware development of multi-core processors. It is evident that the software development for multi-core processor requires highly skilled work-force.

 . s oft wa r e de s i g n flow

The software design process commonly follows the Y-chart approach [, ] as shown in Figure .. This approach involves an application model and a hardware platform used as an input to the optimization solver. Optimization solver is particularly a set of tools which is used to determine the optimal configurations in which the application code can execute on the hardware platform satisfying different cost constraints. These solver tools need profiling information from the application code, such as task execution times, memory consumption, communication data size etc. This information varies from one hardware platform to another, and can be either calculated by the WCET (Worst Case Execution Time) analysis tools or estimated by running the code on the platform and profiling it. The performance analyzer part is optional in the design flow, and it can provide a feedback to the solver in terms of extra constraints to avoid performance problems observed during measurements.

The solver which forms the heart of this methodology, employs different solution space search algorithms to solve the mapping and scheduling problem. There exists a vast literature on algorithms for mapping and scheduling. The ultimate goal of the solver is to use such algorithms to solve this problem, and produce a solution (or set of Pareto optimal solutions).

 . r e lat e d t ools .. SDF SDF [] is a design flow based on synchronous dataflow (SDF) model. This design flow starts from architecture and application specification and proceeds to mapping, scheduling and performance prediction. The input to this tool is an application and architecture graph along with different constraints, like throughput, processors used etc. The tool performs static performance analysis on the input and determines if the constraints are feasible. If any constraint is violated, the bottlenecks can be analyzed. This tool is oriented to a specific predictable hardware platforms. Apart from SDF model, it also supports some other (more expressive) application models in particular SADF (Scenario Aware Data Flow).

.. MAMPS

MAMPS [] extends SDF for code generation for an FPGA based platform. The inputs to this tool are same as SDF plus a template to generate hardware platform. This tool then takes input application along with its throughput requirements, generates a hardware platform and executable code which can satisfy these requirements. This hardware platform then can be programmed on an FPGA and the application can be run on the platform. This tool uses a simple Xilinx Microblaze processor and point-to-point links or a simple NoC to minimize the prediction error due to network contentions. [] is a similar tool to that of SDF/MAMPS, focussing on the throughput constraints of an application. It consists of four parts-a front-end compiler which generates SDF graphs from annotated C code. A solver, based on constraint programming, solves the allocation and scheduling problem. A back-end compiler responsible for generation of C code which can be executed on the target hardware. And finally the description languages which allows interfacing between all these components.

.. MP-Opt

MP-Opt

.. StreamIT

StreamIT is a programming language and a compiler which can compile the dataflow applications []. The language models SDF with various programming patterns like filters (same as actors) and split-join mechanism (edges). In this work, application data streams are explicitly split and merged in order to exploit the available parallelism. StreamIt can analyze and optimize sliding window extensions of SDF which are not taken into consideration in SDF. For example it supports peek construct, which allows a filter to read the token without removing it from the channel.

.. StreamRoller

Another interesting work is StreamRoller compiler [] which maps the StreamIT code on the Cell platform. It uses an algorithm SGMS (Stream Graph Modulo Scheduling) to schedule the actors on the processors using ILP (Integer Linear Programming). SGMS applies a pipelining technique at coarse-grain level in order to achieve concurrent execution and hidden communication, minimizing stalls. It is done in two steps. First step involves splitting of the actor and partitioning in order to evenly balance the work among the processors. It is done by integer linear programming. Second stage is where actors are assigned to the pipeline stage in order to overlap communication and computation. It is done by greedy heuristic partitioning which assigns filters to processors.

.. Discussion

SDF tool does extensive performance analysis on SDF and other variants of the model. It also offers mapping and scheduling tools for a multiprocessor on-chip network platform with TDM scheduling. It does not support multiple core clusters accessing local shared memory without network and does not provide a run-time environment, although MAMPS as well as CompOSe operating system (see Section .) offer support for SDF. MAMPS on other hand deals with combined design space exploration of architecture and application. It has a run-time management system which performs online resource management considering the requirements of the application. MP-Opt offers optimization and runtime environment for Cell processor architecture which assumes one processor per cluster. It is designed to use the DMA communication (see Section .) of the processor but does not model it explicitly. The major optimization goal of SDF, MAMPS and MP-Opt is optimization of throughput, which requires pipelined scheduling. StreamIT is a compiler based approach to optimize the execution of streaming applications based on actor splitting and fusion. In this thesis we present our infrastructure which deals with mapping and scheduling problem on multi-core taking DMA communication into account. We consider application latency as the timing metric to optimize in our work. Our infrastructure deals with eliminating symmetrical solutions in the design space and accelerating the search for optimal solutions.

 . or g a ni z at i on of t h e s i s

In this thesis we study the problem of mapping and scheduling dataflow applications on multi-core processors. The thesis is organized as follows: ■ Chapter  introduces the application programming model used in this work. We discuss briefly different programming models and similarity with our model that we introduce.

■

Chapter  presents the hardware architecture model that we follow for our investigation. We describe the important parameters of the hardware platform that must be taken into account for modeling. Further we describe the working of DMA on Cell processor and introduce a model to estimate performance of the applications using it.

■

Chapter  introduces the satisfiability solvers and briefly describe the mechanism behind them. We give a small example of how a scheduling problem can be encoded and presented to such solvers. Further, we describe the multi-criteria optimization problem, where multiple costs must be optimized simultaneously. We present algorithms to efficiently track solutions to such problems.

■

Chapter  explains the method of deployment and evaluation of our solutions. We briefly describe the framework in which we carry out the experiments and a runtime environment which is used to execute and validate the solutions discovered by our methods.

■

In Chapter  we introduce the symmetry in the dataflow graphs and a method to encode them in to satisfiability constraints in order to accelerate the search for solutions. We present the constraints by which the scheduling problem can be encoded in order to optimize latency, communication buffer size and number of processors.

■

Chapter  introduces a new multi-stage approach for the scheduling problem for the Kalray processor. We demonstrate the modeling of communication and network flowcontrol to orchestrate the application execution in bounded distributed memory.

■

In Chapter  we study the parallel applications with regular access pattern, which bring the data from main memory to the limited local memory, process it and write back the results again to the main memory. We present the work on optimizing the DMA transfer size, for such applications.

■

In Chapter  we present a runtime system which optimizes resource usage of the system by dynamically reconfiguring the applications. We present a predictable method for such reconfiguration, without affecting other running applications. T he description of a multi-core mapping and scheduling problem starts with a model for applications. Models are encoded and presented to the optimization solvers to find correct and efficient parallel schedules.

While studying an algorithm specification, one encounters numerous parameters, details available to the designer consideration. It is very important to select few of them which make the most significant impact towards the solution of the problem. If the model captures too fine-grain details, then it becomes difficult for the optimization solvers and any other search strategies to find optimal solutions. This makes the model of computation or the programming model, a very important aspect of embedded system design. It gives a structured view of how a given computation will execute and is annotated by important characteristics of the program. The model helps us to study the behavior of the entire system depending on the behavior of individual components. By study of such model using timed system formalisms, the designer can estimate the required resources. It is very helpful in order to gain an insight of the algorithms and performance of the machines on which applications represented by such models execute.

A programming model, in general, should provide the following information: A class of applications called streaming applications, process a continuous stream of data for indefinite time. The input data arrives at a given rate, and is processed by algorithms defining such applications. JPEG decoder, MPEG decoder, H- encoder, filter banks etc. are examples of streaming applications. These applications perform a predetermined set of operations on input stream of data and can be easily represented with the type of models referred to as dataflow graphs.



In this chapter we describe a few relevant dataflow graph models which are typically used in signal processing applications. We focus on synchronous dataflow graph (SDF) model in detail. We present a model namely split-join graph which can be regarded as a sub-class of SDF model. Further we describe the semantics and behavior of this model. We conclude the chapter by defining method to convert a split-join graph to an acyclic task graph which is a commonly used model for mapping and scheduling tasks with dependencies.

.  data flow g r a p h s

Dataflow graph is a popular class of model of computation related to Petri Nets, which describes a computational process with evolving availability of the data. Dataflow graphs have nodes called actors, which represent the computation performed on a data. The edges between the actors carry tokens represents the communication of the data, which is processed by the actors. It emphasizes only on the dependency between execution of different actors. Dataflow graph does not describe any timing notions explicitly, however there are common extension of time for actors and/or edges. In the dataflow terminology, the nodes called as actors produce or consume an amount of data on the edges called as rate. Different data flow graph models are distinguished by the rules that determine the number of tokens produced and consumed by actors. Dataflow graphs can be classified into static and dynamic depending on whether the rate of production and consumption of tokens is statically known. We discuss some of the dataflow models below.

.. Static Dataflow

These are very simple models which assume that the amount of data is known a priori to the execution. These models have completely predictable execution times and various other parameters of the model. This is a trade-off that has to be made in order to achieve simplicity and analyzability of the model.

Homogeneous synchronous data flow (HSDF) are the simplest dataflow graph similar to shown in Figure ., where rate of every edge is equal to . Thus every actor produces a token on outgoing edge while it consumes one token on an incoming edge. They can be seen as an extension to the acyclic task graph by cyclic paths and data tokens.

Synchronous Dataflow (SDF) graphs is a restricted version of dataflow in which the production and consumption rates (can be non-unity) are known at the compile time. Each actor fires or executes by consuming and producing a predefined number of tokens at its input and output respectively. Each actor may have different rates, however to an individual actor the actual rates are invariant. This restrictive property makes the model analyzable and easy to predict and produce a static schedule which can be repeatedly executed in bounded memory. Marked graphs [], a class of Petri nets, are similar to HSDF graphs, while SDF can be regarded as equivalent to weighted marked graphs [].

Computation graphs [], another type of static dataflow model, are similar to the SDF, which are represented by a finite set of nodes connected with directed queues. In addition to token rates, it adds a threshold value, which is a minimum number of tokens that must be present at the input queue. SDF can be regarded as special case of computation graphs, where this threshold is equal to the consumption rate. Threshold property of this model is helpful in modeling sliding window algorithms, where the nodes need to read the data tokens without consuming them. These graphs find applications in DSP systems, where it is common to operate on a continuous stream of data, e.g. FIR filters, FFT algorithms etc.

There are various extension of SDF. Cyclo Static dataflow model [, ] enhances the SDF model by allowing periodically changing token production and consumption rates in contrast to the static rates of SDF. Multidimensional Data Flow (MDSDF) [] supports the multi-dimensional tokens, such that an actor fires only if the tokens/space in all the dimensions are available. Such models are useful in applications like image processing where the data is represented in two or multiple dimensions. Windowed Synchronous Data Flow (WSDF) [] is an extension of MDSDF, which supports sliding window algorithms.

.. Dynamic Dataflow

With the development of new applications and algorithms, the static models are not able to accommodate the conditional execution of the actors or varying data rates []. Dynamic dataflow are the models in which a set of parameters like the production and consumption rates are not completely known at compile time. This allows flexibility in modeling modern applications, however at the cost of analyzability of such models.

An example of dynamic dataflow is Process Networks. Kahn Process Networks (KPN or simply PN) [] is model of concurrent computations which has a set of deterministic processes which communicate by unbounded FIFO (first-in first-out) queues. The processes block only when trying to read an empty queue, but the queues grow indefinitely when writing processes add data to them. Termination of a PN program is undecidable in finite time, as is boundedness of the queues. This property of queues makes an actual implementation infeasible in limited amount of memory. There are various algorithms to execute a process network in bounded memory, one such is described in section . of []. As compared to SDF, KPN is more expressive but difficult to make static analysis [].

Boolean dataflow model (BDF) [] is a extension of SDF model supporting conditional execution of an actor. It has two special actors called as switch and select. The switch actor has two output and one input, while select actor has two input and one output ports respectively. The former determines to which output port the tokens are produced, while the latter determines from which input port the tokens are consumed. The selection in both the cases is done with the help of a control port. This property makes the model difficult for compile time analysis. For example it is difficult to check boundedness of memory, absence of deadlock, compute a timed schedule, and the model in general is Turing complete. Scenario Aware Dataflow (SADF) [] is a class of extensions of SDF model, introducing the concept of scenarios. A predefined set of scenarios can be seen as different modes of operation of the model, in which the resource requirements, like communication rates and structure, differ considerably. While some properties of these graphs like deadlock and throughput in many cases are analyzable at design time, in practice this analysis can be computationally expensive.

There are many parametric extensions of SDF which allow updating of the parameters of the the dataflow graphs at run-time. Parameterized synchronous dataflow (PSDF) [], Variable rate dataflow (VRDF) [], Schedulable parametric data-flow (SPDF) [] are a few examples of such extensions.

In this thesis, we use static dataflow models, typically SDF. Since our model of computation is closely related with SDF, we discuss it first in brief and then describe the split-join graphs which can be considered as a restriction to the SDF model.

.  s y nc h r onous data flow

SDF is one of the static dataflow models for computation. This model, introduced by Lee and Messerschmitt [], provides a compact representation of applications which communicate data in regular fashion. The graph consists of actors which are connected by edges. An actor corresponds to a piece of code which has input and/or output. It performs some computation on the input tokens and as a result produces output tokens. The edges are marked with input and output rates. The actors communicate using buffers which are of limited size. An actor can fire when its input buffers have enough tokens available for firing and output buffers have enough space for tokens. The numbers marked on the edge connecting A to B denote the rates. Thus for this edge, the production rate is  and consumption rate is . It implies that when actor A executes, it will produce two tokens on the edge, while when actor B executes, it will consume  tokens on this edge.

An iteration of a graph is execution of all the actors of SDF for a fixed number of times greater than or equal to one. In an iteration, consistency property [] of an SDF states that, for all edges in SDF, the amount of data produced on the edge of an SDF is equal to the data consumed on that edge. In short, the graph should return to the initial state after an iteration. Thus in the above example, initially there are zero tokens on the edge. If actor A executes  times, it will produce  tokens on its output edge, and if actor B executes for  times, then it consumes all the  tokens. Thus an iteration can be defined for this example for A executing three and B two times. Note that they can also execute for multiple of these values, for example  and  times respectively, but we always refer to the minimal values. An array which gives minimal number of times for execution of actor for graph to be consistent is also called repetition vector.

Definition  (Repetition Vector) -Repetition Vector is an array of length equal to number of actors in SDF, such that if each actor is invoked for the number of times equal to its entry, the number of tokens on each edge of SDF remains unchanged.

Any SDF graph which is not consistent requires unbounded memory to execute or deadlocks []. When an SDF graph deadlocks, no actor is able to fire, which is due to an insufficient number of tokens in a cycle of the graph. Any SDF graph which is inconsistent or deadlocks is not useful in practice.

A B 2 3 3 2  Figure . -SDF with backward edge
The edge between actor A and B represents a FIFO which carries data from the writer of the FIFO to the respective reader. In the example, if actor A fires continuously, the size of the FIFO will grow continuously and the graph will require unbounded memory for execution. SDF graph models bounded memory with the help of backward edges with initial tokens (similar to algorithm in []) as shown in Figure .. The initial tokens represent the free space available in the forward edge. For every execution of actor A, it produces  (data) tokens on the forward edge, while it consumes  (space) tokens from the backward edge. Similarly actor B consumes  data tokens and produces  space tokens. The model itself does not differentiate between these tokens, and gives an opportunity to represent the communication using bounded memory.

A, 1.0 B, 2.0 2 3 3 2  Figure . -Timed Synchronous DataFlow Graph
SDF graphs without timing notions are used to check correctness of the system (e.g. consistency and deadlock) or for property analysis (e.g. determining buffer-size). For performance analysis, timed variants are introduced (shown in Figure .). The execution time of each actor is denoted with a number in the actor. Thus according to Figure ., actor A takes . time unit, while actor B takes . time units for execution. However, the actors in this case has a fixed execution time and any variation in the execution time is not modeled, which makes it statically analyzable.

When scheduling the SDF graphs, fully static approach uses fixed actor execution times and schedules the actors according to strict timing and data dependency. Since dataflow applications continuously process a stream of data, the execution is periodic in nature. The periodic scheduling of the SDF can be classified into two types : (i) different iterations of graphs don't overlap (non-pipelined) (i i) different iterations execute in overlapping fashion (pipelined).

Figure . shows an example of non-pipelined and pipeline schedules. In the case of pipelined scheduling, there are two phases execution of SDF graph. The transition system consists of a finite sequence of states and transitions, called the prologue (or transient phase), followed by a sequence of states and transitions which is repeated infinitely often and is called the periodic phase. The periodic phase is very useful in analyzing the properties of the It is difficult to predict and control the length of the prologue phase even for small SDF graphs. However, in the case of strictly periodic schedule one can indirectly enforce it, at the cost of some optimality loss []. In the case of non-pipelined schedule, the prologue is absent, while the schedule can be executed infinitely with bounded resources. For more details, the reader is referred to [].

A 0 A 1 A 2 B 0 B 1 A 0 A 1 Time P roc 1 P roc 2 P roc 3 i terati on 0 i terati on 1 (a) Non-pipelined A 0 A 1 A 2 B 0 B 1 A 0 A 1 A 0 A 1 A 2 B 0
Pipelined scheduling is a complex task. From real-time scheduling point of view it incurs satisfaction of three cost/objective constraints at the same time: latency, processor count and throughput. Handling these three constraints at the same time is rarely studied in the literature of SDF and task graphs. Usually only two types of the above constraints are considered. In this thesis we also restrict to two of them -processor count and latency, sometimes adding buffer storage cost as an extra. Multi-criteria optimized scheduling is often done by using different generic solution search methods such as constraint programming [], linear programming [, ], as well as model checking [], genetic programming [] etc. In this thesis we focus on non-pipelined scheduling, while pipelined scheduling is a future work. An interested reader can refer to [] for our preliminary results on pipelined scheduling with throughput, latency and processor count criteria, using SMT solvers.

.  s p li t-joi n g r a p h s

SDF is a general programming model which can accommodate a wide range of streaming applications, and supports features like stateful actors, odd production and consumption rates etc. However in this work, we would like to focus on regular data-parallel applications. We would like to simplify this model in order to facilitate analysis while still covering most of the SDF applications. Thus, we define the split-join graphs, which can be thought as a sub-class of SDF graphs.

Definition  (Split-Join and Task Graphs) -A split-join graph S is defined by S = (V, E, d, , ) where (V, E) is a directed acyclic graph (DAG), that is, a set V of actors, a set E ⊆ V × V of edges. The function d : V → R + defines the node execution time, : E → {a, 1/a | a ∈ N + } assigns a parallelization factor to every edge. An edge e is a split, join or neutral edge depending on whether (e) > 1, < 1 or = 1. (e) denotes the size of data tokens sent to each spawned task in the case of split, or received from each joined task in the case of join, or just sent and received once per execution if the edge is neutral. A split-join graph with (e) = 1 for every e is called an acyclic task-graph and is denoted by T = (U, E, , ), where the four elements in the tuple correspond to V, E, d, and . The decomposability of a task into parallelizable sub-tasks is expressed as a numerical label (parallelization factor) on a precedence edge leading to it. A label on the edge from A to B means that every executed instance of task A spawns instances of task B. Likewise, a 1/ label on the edge from B to C means that all those instances of B should terminate and their outputs be joined before executing C (see Figure .). An acyclic task graph can thus be viewed as derived from the split-join graph by making data parallelism explicit .

We call the nodes of the split-join graphs actors and those of the acyclic task graph tasks. The edges of a split-join graph e ∈ E are called channels, and those in an acyclic task graph ∈ E are called dependency arcs or just dependencies.

.. The Semantics of Split-join Graphs

In split-join graphs, the tasks (i.e. instances of an actor) can execute in parallel unless there are dependencies between them. In Figure . actor A spawns instances of actor B, which can execute in parallel. Still, for convenience, we explain the functional behavior from sequential-execution point of view.

In sequential execution, channel e = (v, v ′ ) can be seen as a FIFO (first-in-first-out) buffer. Let the task instances of each actor v execute in a fixed order, which determines their index: v 0 , v 1 , v 2 etc. Let ↑ (e) be the amount of tokens (also called production rate) that are produced by actor v on channel e. The instances v q of the writer actor of channel (v, v ′ ) produce ↑ (v, v ′ ) tokens each in the FIFO channel; in the derived task graph ↑ also corresponds to the number of outgoing dependency arcs of v q . Similarly, ↓ (v, v ′ ) denotes the number of tokens consumed (called consumption rate) and the number of incoming dependencies of instances v ′ r of the channel reader actor. Mathematically these rates can be described as:

↑ (e) =        (e) (e) ≥ 1 1 (e) < 1 ; ↓ (e) =        1 (e) ≥ 1 (e) -1 (e) < 1
Split-join graphs also follow the consistency property which was defined for SDF graphs in Section .. Let c(v) denote the repetition count of an actor v obtained from the repetition vector of the graph. The equations that express the consistency requirement are known as balance equations; are given for an edge(v, v ′ ) as:

(v,v ′ )∈E ↑ (v, v ′ ) • c(v) = ↓ (v, v ′ ) • c(v ′ ) (.)
Note that if Equation . has a solution c(v) then k • c(v), ∀k ∈ N + is a solution as well. However, we assume the minimal positive integer solution and use the notation c(v) for it. Executing each actor c(v) number of times is defined graph iteration.

The amount of data that is communicated in an iteration, on an edge can be then easily quantified. The tokens have size bytes, and the amount of data produced by an instance of v and consumed by an instance of v ′ , for an edge e is:

w ↑ (e) = ↑ (e) • (e); w ↓ (e) = ↓ (e) • (e)
where w ↑ (e) and w ↓ (e) is total amount of data produced and consumed on edge e respectively.

Given this description of the split-join graph, it can be easily converted into another graph namely task graph. In Chapter , we introduce well formedness, a strong property for split-join graphs (can be seen as a restriction on SDF graphs), where we define a strict nested structure. Split-join graph is comparable to SDF in terms of decidability and complexity of analysis. However it presents structured view of regular nested loops that appear in programs and hence it is easier for implementation []. Further with the well-formedness restriction we apply on split-join graphs, it is relatively easier to present the theory of symmetry elimination on identical task instances derived from the same actor.

.. Derived Task Graph

The task graph derived from a split-join graph models one graph iteration.  For each actor v the task graph contains c(v) tasks {v 0 , v 1 , . . . v c(v)-1 }, i.e. the instances of actor v.

Let us define the edges of the derived task graph. For a split-join channel (v, v ′ ) with (v, v ′ ) = a/b let us consider the sequence of a • c(v) tokens produced in the FIFO buffer in one iteration. Let us number these tokens by index i in the order they are produced by the instances of actor v : v 0 , v 1 , . . . . Obviously, token i is produced by task v q where q = ⌊i/a⌋. The actor instances consume the tokens in the same order as they are produced (the FIFO order). Therefore, the first b tokens will be consumed by task v ′ 0 , then the next b tokens by v ′ 1 , etc. In general, the token i is consumed by task v ′ r where r = ⌊i/b⌋. To model this producer-consumer dependency of token production and consumption, the task graph should contain edge (v q , v ′ r ). The derived task graph then can be defined formally as: Definition  (Derived Task Graph) -From a consistent marked split-join graph S = (V, E, d, , ) we derive the task graph T = (U, E, , ) as follows:

U = {v h | v ∈ V, 0 ≤ h < c(v)} E = {(v h , v ′ h ′ ) | (v, v ′ ) ∈ E ∧ (v, v ′ , h, h ′ )}
where is predicate defined by:

(v, v ′ , h, h ′ ) : ∃ i ∈ N : h = ⌊i/ ↑ (v, v ′ )⌋, h ′ = ⌊i/ ↓ (v, v ′ )⌋, v h , v ′ h ∈ U and: ∀(v h , v ′ h ′ ) ∈ E (v h , v ′ h ′ ) = (v, v ′ ), ∀v h ∈ U (v h ) = d(v)

.. Marked Split-join Graphs

We have seen two different extension of acyclic task graphs : graph with initial tokens and split-join graphs. Here we combine them into one. In order to model the graph in bounded . In SDF terminology, deriving a task graph is equivalent to deriving a homogeneous SDF graph. buffer, marked graphs introduce notion of channel marking, an equivalent of SDF with initial tokens.

Definition  (Marked graph) -The marked (split-join) graph S can be defined as a split-join graph extended by allowing cyclic paths and introducing an extra edge parameter -the marking: m : E → N ≥0 . The extended tuple for a marked graph is thus: , d, , , m), where m represents the marking on the edges. We assume that any split-join graph is a marked graph with zero marking.

= (V, E
The conversion of marked split-join graph is similar to that of un-marked graph. A non-zero marking m ′ = m(v, v ′ ) has the semantics of initial availability of m ′ tokens in the channel. Therefore, for the case of a marked graph in the above example we have to calculate r as r = ⌊(i + m ′ )/b⌋. Without initial tokens the consumer of the token i produced on the channel (v, v ′ ) is task v ′ r where r = ⌊i/b⌋. However, now this consumption can be seen as shifted by value m. The derivation of the task graph then can be updated as follows.

Definition  (Derived Task Graph) -From a consistent marked split-join graph S = (V, E, d, , , m) we derive the task graph T = (U, E, , ) as follows:

U = {v h | v ∈ V, 0 ≤ h < c(v)} E = {(v h , v ′ h ′ ) | (v, v ′ ) ∈ E ∧ (v, v ′ , h, h ′ )}
where is predicate defined by:

(v, v ′ , h, h ′ ) : ∃ i ∈ N : h = ⌊i/ ↑ (v, v ′ )⌋, h ′ = ⌊(i + m(v, v ′ ))/ ↓ (v, v ′ )⌋, v h , v ′ h ∈ U and: ∀(v h , v ′ h ′ ) ∈ E (v h , v ′ h ′ ) = (v, v ′ ), ∀v h ∈ U (v h ) = d(v)
.  s p li t-joi n g r a p h a p p li c at i on e xa mp le : jp e g de c ode r

V LD I Q/ I D CT CC 12 1 12 Figure . -JPEG decoder Figure .
 shows a JPEG decoder expressed as Split-Join graph. It has three main actors: variable length decoding (VLD), inverse quantization combined with inverse discrete cosine transform (IQ/IDCT) combined and color conversion (CC). The VLD actor is responsible for decoding the JPEG parameters which are added to the image as header. After the header is decoded, it performs variable length decoding on the image data which is then converted into blocks. These image blocks are then passed to the IQ/IDCT actor which first performs inverse quantization and then performs inverse discrete cosine transform on these blocks. Finally the color actor performs color conversion which then finishes the decoding from JPEG image to Bitmap image format.

The edges in this application are used to communicate JPEG image parameters which are defined in the header and the image data. The rates are proportional to the size of image that is being decoded 32 × 24 pixels in our case.

.  c onc lus i on

In this chapter we discuss various aspects of programming model and how streaming application can be expressed in our model, namely split-join graph. Split-join graph model is similar to the fork-join model used in []. Both typically represent a well-structured nested loop computation which is typically observed in certain class of applications. In fork-join graphs, the tasks are divided in stages and segments. This model has a stricter requirement that tasks in the same stage can execute concurrently, while tasks in preceding stages must complete before. In split-join graph, we have a general expression of parallelism in which precedence constraints are expressed only via connected actors. Further we annotate the edges with the amount of data transfer to model the communication.

We also discussed other existing models, which can also be used for expressing such applications. However, in order to perform formal analysis, in further chapters, we need a simple model. Our model can be regarded as a subset of SDF graphs, thus enabling us to readily use some of the SDF benchmarks, or many of them with little or no modifications.

In next chapter we discuss characteristics of various hardware platforms and important parameters to model them. We further show how these parameters are effectively used in solving the mapping and scheduling problem on these hardware platforms using satisfiability solvers.

cha pte r 3 Arc hi t e c t ure Mo de l After having considered the application programming model, in this chapter we introduce the hardware architecture model, which is used to model the multi-core hardware platforms.

M any-core / Multi-core processors exploit a collection of complex mechanisms and sub- systems, designed for specific purpose to accelerate certain functions. For example, SIMD (Single Instruction Multiple Data) instruction accelerates execution of instructions by executing same operations concurrently on multiple data. Such mechanism is typically used in signal processing manipulations, like matrix multiplication, where the same operation can be performed on multiple elements in parallel. DMA (Direct Memory Access) is another example, where the DMA engine facilitates the overlapping of computation and communication by performing asynchronous data transfer without intervention of a processor. Multi-core processors operate at a different level of granularity than SIMD, and they can be used to accelerate data-parallel applications. In the previous chapter we observed different programming models and how they can be used to express parallelism in certain applications. Applications, represented by such parallel models, can be accelerated on multi-core processors by executing concurrently.

With multi-core platforms the space of design-parameters is huge. They include the number of processors used, the amount of memory used, power / energy consumption, communication costs, latency, throughput and many more. If all these parameters were considered together with hardware platform low-level details such as instruction-level details (like instruction-set in simulation), the combinatorial problem of mapping and scheduling would be unmanageable. Thus with the large design space, the decisions for executing an application on these platforms must be taken at higher level of abstraction. Scheduling is an old problem and different formalisms and approaches have been developed in order to solve it. In order to study scheduling, the tasks in the application are annotated with the timing parameters, typically worst case execution time of the task. Thus the instruction-level details of the tasks are abstracted away, which simplifies the decision-making process for application execution. If an application is to be deployed efficiently on a platform, then we need accurate models of the platform as well. A similar approach is applied to multi-core processors, where the minute details of the platform are abstracted away retaining only important parameters. A decisionmaking theory then can be applied on the combined models of application and platform in order to find an efficient solution to the scheduling problem specific to the platform.

In this chapter, we discuss the multi-core and many-core processor architectures in general and we give details of some particular architectures. Then we describe the way we model these architectures.

.  mult i -c or e a nd ma ny-c or e p r oc e s s or s When multi-core processor came into existence, they typically consisted of few processors with large caches located near the processor in shared global address space. These processors were rich with instruction-level acceleration mechanisms such as multi-stage pipeline, branch prediction, cache coherency etc. Further scaling of such sophisticated cores is difficult owing to various issues such as power consumption, design complexity, physical layout etc. which became a strong motivation for development of many-core processors.

In a many-core platform, multiple multi-core clusters are networked on a chip. The platform has a powerful general-purpose processor which can be located either on-chip or off-chip. This processor has full capabilities such as cache and cache coherency, coprocessor support, floating point engine etc. This processor is also called a host CPU. The accelerator fabric, the many-core system itself, contains simplified processor cores which can accelerate computation by executing application code in parallel. The processor cores in the accelerator fabric are grouped in clusters. The processors (in the cluster) share a finite amount of resources like local memory and can function independent of each other. Such processor architectures, although complex, can be efficiently utilized for various applications. One important usage scenario is when a host CPU runs all the usual software stack and general-purpose tasks, whereas computationally expensive highly parallel kernels are forwarded to the many-core fabric. We discuss the components and terminology of these processors below.

.. Clusters

In order to facilitate the development of both software and hardware, multiple cores are grouped together as clusters which share finite resources like DMA engines, local or intracluster memory etc. The processors inside the cluster typically are light-weight processors (with limited capabilities in terms of pipeline stages, cache mechanism, or virtual addressing). Power consumption and design challenges are the fundamental reason behind such architecture. These processors are designed to perform computations independent of each other and communicate efficiently. Within a cluster, the processors can communicate using various mechanisms such as shared memory, common registers, etc. The communication outside the cluster is managed with help of asynchronous mechanisms such as DMA (discussed further). Typically, communication and synchronization inside a cluster is faster than between clusters.

.. Shared Memory

A limited amount of memory is generally made accessible to all the processors inside the cluster. Memory is usually multi-bank in order to provide good performance scalability by preventing memory conflicts due to usage of different banks. It is also called intra-cluster memory or local memory. This local memory ranges typically from some kilobytes to a few megabytes and has access latency usually less than  clock cycles. The main memory has access latency of around hundreds to a few thousand clock cycles and is of several order of megabytes or gigabytes. Typically the program is first loaded in the main memory and the program execution is started. The clusters must fetch the program data into intra-cluster memory, and subsequently perform computations on it. The processors don't have direct access to the main memory, but can fetch data from main memory to local memory. The data movement between them is facilitated by asynchronous mechanisms namely DMA, explained further. This hierarchical organization of memory provides the programmer benefit of performing computations on a part of local memory concurrently with, asynchronous data transfer between local and main memory or different local memories.

.. Network-On-Chip

The multi-core / many-core processors contain network on chip (NoC) in order to facilitate data movement between clusters or between cluster and other hardware peripherals like I/O devices. A processor which is connected to the NoC via a network interface initiates a data transfer. Data is pushed on the network in form of packets. The size of these packets depends on the NoC architecture. It may also contain other information like the route, the destination address etc. The role of the NoC is also to provide arbitration between packets with conflicting routes and to ensure correct delivery of data from the source to destination. There are various arbitration policies such as round-robin, priority-based, etc. which can be used to resolve the conflicts.

.. DMA

A DMA controller is a piece of hardware used to move data between isolated memories, possibly asynchronously with respect to the core program execution. If data transfer is synchronous, the processor remains blocked as long as data transfer is in progress. The main memory access latency can reach few thousands of clock cycles. If the processor had access only to that memory, it will spend most of its time in blocking for memory access rather than performing useful computations. This scenario can be improved by having a local memory in the cluster such that data is fetched from the main memory to the local memory and then the processors perform the computation in the local memory. When the computation is finished, the results are written back to the main memory. This data movement is performed by the DMA controller. In order to efficiently overlap computation and communication, the DMA controller, after being setup, can function without any intervention from the processor to move the data. Different parameters such as amount of data to be transferred, the stride, the source and destination address are specified by the programmer in the setup of a DMA controller. Stride is an optional argument which is explained in later section. The DMA controller can signal back to the main processor upon completion of the data transfer by mainly two methods: polling and interrupt. In polling method the processor can check for a flag for completion of data transfer, using an interrupt mechanism the processor is interrupted of its current task and a service routine is executed to process the transfer completion.

We discuss in detail different platforms that admit such mechanisms.

.  t i le r a t i le

Tilera Tile Pro [] processor architecture consists of  symmetrical processors (shown in The Cache engine of this platform contains Translation Look-aside Buffers (TLB), which are used to support virtual memory, required for the Linux platform. The platform contains a multi-level cache. Each tile contains KB of Level- (L) Instruction cache, KB of L data Cache and  KB of Level- (L) cache. This accounts for total of .MB on-chip cache. Each tile also has a D DMA engine for data transfer between the tiles and main memory, however it is currently unsupported by the software.

Every tile is also connected to different networks mentioned below -■ User Dynamic Network (UDN): It is the only visible network to the user which is exposed by C library routines for streaming the data between tiles.

■

Memory Dynamic Network (MDN): It is interfaced with the cache engine to carry the memory traffic between tiles (such as cache misses, DMA) and between tile and main memory.

■

Coherence Dynamic Network (CDN): It carries the cache protocol messages to maintain the hardware cache coherence and is invisible to the programmer. In addition there are other three networks which support traffic for I/O devices and other purposes, but are not relevant to our work. The network channels include hardware flow control and buffering mechanisms to enable asynchronous data transfers. The dynamic networks are packet-switched mesh networks which employ "XY-routing" mechanism. The packets from source to destination are switched along x-axis first and then to y-axis. Thus the hardware is robust and efficient in maintaining coherent data across all the processors and our software can use such mechanisms in order to perform communication transparently.

In addition it contains SIMD instructions for sub-word parallelism and instructions like saturating arithmetic for acceleration of DSP algorithms. We assume that the compiler is responsible for utilizing the available instruction-level parallelism.

We use this architecture to demonstrate the constraint-based solving of scheduling problem using SMT solvers. We produce solutions with different resource usages and validate them by executing on this platform. The details of the experimentation are given in Chapter .

.  k a lr ay mp pa -

Kalray MPPA- [] platform is shown in Figure .. This platform consists of  symmetrical processors which are grouped together,  processors in groups called compute clusters. These compute clusters are connected by a network of D toroidal topology. Apart from compute clusters, the platform also has four I/O subsystems, which are group of four cores each, called I/O clusters. There are two NoCs on the chip; one is for data transfer (data NoC), optimized for bulk transfers, while the other is for control messages (control NoC), mainly optimized for low latency. A cycle accurate timer is also integrated inside a cluster, accessible by any processor in the cluster and used for time measurement. The Kalray platform has a host processor, an Intel CPU, which is connected to the multi-core chip via PCI bus.

Each compute cluster contains  VLIW cores with a -bank shared memory of  MB capacity. Out of  cores, one core is called Resource Manager(RM), and is dedicated to operating system functions. The remaining  cores, called Processing Elements (PE), can be used for executing application threads based on the pthread model of execution. Every core implements a -bit -issue Very Long Instruction Word (VLIW) architecture with a -stage instruction pipeline. It includes two arithmetic and logic units, a multiply-accumulate/floatingpoint unit, a load/store unit, and a branch and control unit. These five execution units are connected through a shared register file of  -bit general-purpose registers (GPRs). It also has independent KB instruction cache and KB data cache to hide the access latency to the MB shared memory. There is no hardware cache coherency in compute clusters, and it has to be explicitly managed by the software. Kalray MPPA software library provides an abstraction layer which provides efficient communication and synchronization primitives by hiding low-level hardware details. It provides the API (Application Programmer Interface) for setting up the DMA, for communication between compute clusters, IO clusters and host. The RM core is a privileged core and is responsible for executing the kernel routines. The main task on RM core is waiting on events from PE which are system calls to execute kernel routines. The PE is blocked till the system call is being processed, and after finished is unblocked by an event from RM core. The RM core being privileged is responsible for initiating the data transfers by setting up the DMA engines and can be accessed with MPPA library API. It also handles the hardware interrupts.

C 0 C 1 C 2 C 3 C 8 C 9 C 10 C 11 C 4 C 5 C 5 C 6 C 12 C 13 C 14 C 15
The host is connected to the IO cluster subsystem via PCI/e connection. The MPPA library also provides API which facilitates synchronization and data transfer to and from IO subsystem via PCI. More details about the architecture and its software library are given in [].

In Tilera architecture, the data movement between the processors was managed by the hardware using cache coherence mechanism. However such a mechanism does not exist on Kalray architecture and data movement is managed explicitly by the software. Moreover the cost of moving the data is non-negligible and has to be modeled to predict the software performance accurately. We explicitly model the inter-cluster communication and orchestrate it along with the scheduling of the computation tasks. We execute a number of benchmarks on this platform to validate our results. Further details are presented in Chapter .

.  c omp s oc p lat for m

The CompSOC platform [] (see Figure .) , is a research platform developed by the Eindhoven University of Technology. It is a tile-based architecture in which a set of processing and memory tiles are connected to each other via the AEthereal network-on-chip []. Each processor tile contains a Microblaze processor running the CompOSe real-time operating sys- tem []. CompOSe provides composable and predictable application scheduling. Composable means starting or stopping of a certain application doesn't affect timing behavior of other applications running on the same processor.

A processor tile contains also a non-shared local memory for instructions and data, as well as communication memories which are used by a DMA for communication with remote tiles. Memory tiles contain a memory sub-system that can be accessed from the processing tiles. The tiles that communicate with memory and other processing tiles using AEthereal NoC. This NoC has slots which are reserved by applications, guarantees a fixed bandwidth.

The CompSOC platform provides a predictable and composable timing behavior to applications running on the platform []. In order to provide composability, it uses a composable scheduling strategy such as time-division multiplexing (TDM), where the presence or absence of requests from one application cannot affect the scheduling decisions for other applications. In addition, it uses preemption after a fixed time to prevent one application from starving another. Furthermore, it delays scheduling of another task till the end of the time slice to avoid that the early completion of one request will cause subsequent requests to be scheduled earlier. In order to provide predictability, it requires that all data needed for a request must be locally available and that there should be enough local storage space to store the response of this request. In combination with the use of predictable resources with bounded worst-case execution times and the use of a predictable TDM scheduler, it is possible to compute a worstcase response time for any task running on a resource. The TDM scheduler can be thought as a time wheel with fixed number of time-slices. Each application has a dedicated number of slices for execution, and is pre-empted on completion of its slices. This guarantees the amount of time an application will have in the time wheel. The sequence of these time slices is then repeatedly executed until the platform is stopped explicitly. Thus the worst-case response time can easily be calculated, and depends on the number of slices allocated to the application, total number of slices, and worst case execution time of the application. Complete details about this platform can be found in [, ].

In Chapter  we discuss how we can perform reconfiguration of the applications for global optimization of the resources. For such a reconfiguration, the system must be able to predictably migrate the tasks of an application, without affecting execution of other applications. This can be achieved with a support from hardware. For more details the reader is referred to Chapter .

.  i bm c e ll be p r oc e s s or

The Cell Broadband Engine Architecture [, ]

Figure . -IBM Cell BE processor
The PPE is composed of a general-purpose -bit RISC processor called PowerPC Processor Unit (PPU) integrated with cache mechanism and bus interface. Each SPE is composed of a Synergistic Processing Unit (SPU) which is a vector processing unit, a SRAM local store (LS) of size  kbytes shared between instructions and data, and a Memory Flow Controller (MFC) to manage DMA data transfers. The PPE has a single shared address space across SPEs and the memory translation units in MFC handle the required address translation. An SPE can access the external DRAM and the local store of other SPEs only by issuing DMA commands. The PPU does not have its own MFC but can initiate DMA on behalf of an SPU, by exclusively accessing its MFC. An MFC supports aligned DMA transfers of , , , ,  or a multiple of  bytes, the maximum size of one DMA transfer request being K. To transfer more than K, DMA lists are supported.

The cell processor operates in virtual memory environment. The MFC of each SPE is composed of a Direct Memory Access Controller (DMAC) to process DMA commands queued in the MFC and of a Memory Management Unit (MMU) to handle the translation of DMA generated addresses. The MMU has a translation look-aside buffer (TLB) for caching recently translated addresses, which is explained in detail ahead. After the address translation, the DMAC splits the DMA command into smaller bus transfers and peak performance is achievable when both the source and destination address are -byte aligned and the block size is multiple of  bytes []. We can observe reduction in performance when this is not the case.

Processors use a technique called virtual memory, where an application executing on them is presented is presented with a contiguous virtual address space representing the main memory and secondary storage. This memory is divided in a unit called pages. A virtual page is mapped to a physical page when accessed and the translation information is marked in a page table. Page size is a design-parameter and has its own tradeoffs. For example, if we increase the page size, it will cause lesser number of page table entries, but will require larger area in physical memory a part of which might remain unutilized [].

When an application accesses an address, a virtual address translated to physical one referring to the page table. For every memory access, a corresponding entry in the page table is fetched and its physical address is calculated. Thus one virtual memory access requires two physical memory accesses (one for page table entry and other for data). Since memory is generally much slower than the processor, a special cache is added to the hardware called Translation look-aside buffer (TLB), which contains recently accessed page table entries. On a TLB miss the hardware has to locate the required entry in the page table. The application has view of all the memory available, however not all the physical pages are allocated at the start of the page execution to avoid the wastage of the physical memory in case if it remains unused. If the accessed physical page corresponding to the virtual address is unallocated, a new physical page is allocated by invoking complex kernel memory allocation routines. The page table entry is updated and then loaded in TLB. This allocation and translation costs many thousands of cycles on the Cell processor and should be avoided if possible []. In order to avoid this overhead we allocate huge pages, where the page size is MB. Note that one page has one entry in TLB, thus for this entire MB of data there will be only one entry in TLB. We allocate the application data strictly in this page. In our experiments (see Section .) a warm-up run is performed where we access this page, loading the entry in the TLB of SPE. Next time the address of application data is accessed, it takes only a few cycles for address translation.

In the Cell Simulator that we use [] the PPE and SPE processors run at .GHz clock frequency and the interconnect is clocked with half the frequency of the processors. The Cell-simulator gives performance predictions close to the actual processor. The cell-simulator approximates the memory performance by using a DDR memory model. Further the TLB replacement policies in the SPE uses a Replacement Management Table (RMT) for replacement of TLB entries. The simulator does not support RMT. However in our measurements, we subside the effect of TLB using large pages and a warm-up run thus does not affect our model. Further details of the architecture can be obtained at [].

We study data-parallel applications with regular access patterns and how they perform uniform computation by fetching the data from main memory to the local memory and writing back the results again to the main memory. The entire application data doesn't fit in the local memory and hence must be brought in the local memory in batches. The transfer granularity influences the performance of the application and is an optimization problem. We study this problem for the Cell architecture. More details are available in Chapter .

.  dma c ont r olle r i n c e ll p r oc e s s or

In this section, we present the details of the DMA controller of the Cell processor and how it can be modeled. The model can be trivially adapted to the Kalray processor, which also supports DMA transfers. The DMA controller then selects a data transfer command following some complex set of rules. If the command is a write then it will access the local store to fetch the data to be written to a remote memory. The TLB unit provides the address translation for the memory requests. The DMA command is split into chunks of  bytes which is the size of the data transfer on the network, which is then enqueued into bus interface unit (BIU). The BIU then pushes the data on the interconnect performing handshake with the memory interface controller. For read requests similar steps are performed, except that the direction of data is reversed and local store is accessed by BIU to write when fetched from a remote memory. For more details please refer to []. The DMA controller is a complex piece of hardware and it is difficult indeed to model it accurately. However we make simplified version of the model by observing the amount of time the controller takes to read or write the data. A DMA transfer constitutes of two main phases: ■ Initialization Phase: This phase includes time to write the command in the DMA controller. Typically during this time the processor is blocked and cannot be used for any computation. The time required for this phase is independent of the amount of data to be transferred.

■

Data Transfer Phase: This phase is where the command is ready and the data is actually transferred on the network. The duration of this phase is naturally proportional to the amount of data that is being transferred. It is more efficient to transfer few large chunks of data than many small ones, as the controller can amortize the initialization phase costs.

.. Strided DMA

Remember that memory is made up of contiguous locations which are accessed by specifying addresses. For example a kbytes of memory can be accessed by address  to . When the software allocates an array in the memory, it will allocate it in a contiguous address space. In image processing applications a raw image will therefore be stored incrementally A DMA controller transfers contiguous as well as non-contiguous (strided) data blocks between the local store and main memory, as shown in Figure .. In the case of a contiguous (or non-strided) transfer the data blocks residing in a contiguous address space are transferred from source to destination. In the case of strided DMA shown in Figure .(b), the data can be located in uniformly spaced non-contiguous locations. Typically, the DMA controller is responsible to manage the stride by splitting the strided data into multiple requests which are contiguous in nature. The distance between two non-contiguous locations is referred to as stride as shown in Figure .(b). A point to note is that in general the stride can be supported either at source or destination of the DMA transfer or both, depending on the hardware architecture. For the strided DMA, the DMA controller has some extra overhead, in order to appropriately decode command and issue a DMA transfer incrementally. Thus the transfer delay will certainly depend not only on the amount of data being transferred but also on the number of non-contiguous blocks being transferred.

.. DMA list

The strided DMA command is supported by Cell architecture in a more generic way using DMA list. DMA list contains upto  elements where each element determines the size and remote memory address. The local store address is not specified in the list and passed explicitly in setup. A DMA list transfer can move data between a contiguous area in an local store and possibly a non-contiguous area in the remote memory. Cell architecture has a limitation that the SPU issuing the strided DMA does not support stride in its local store either for fetching or putting data into a remote memory. Thus stride is available only for a remote address. DMA list is placed in the local store of the SPE and is passed to MFC for processing. MFC fetches the list element by element and transfers the data. The local address is incremented by size in the element for every transfer. The DMA transfer is performed until the entire list is processed.

The software is responsible for allocating the DMA list and initializing its parameters. The waiting on the list transfer can be done using a single routine call. More details about DMA lists are available in [, ]. DMA transfer is provided with an identifier which can be later used to poll for its completion.

.  mode li ng dma c ont r olle r

The DMA transfer time for a contiguous block of size s, denoted by T(s), consists of two parts, a fixed initialization cost I and data transfer delay proportional to the data to be transferred. This delay is given by g • s, where g refers to transfer delay in time units per byte, s refers amount of data transferred in bytes. The DMA communication delay is summarized in Equation ..

T(s) = I + g • s (.)
It is important to note that during the time I both the compute core and the DMA channel are busy for setting up the transfer, whereas during the remaining time G = g • s only the DMA channel is still busy, pushing the data into the NoC, while the core can proceed to other tasks in parallel. At any time later, the processor may decide to wait for the completion of the transfer. DMA transfer completion status can be polled from any core inside the cluster. This operation is blocking until time T(s) has elapsed plus it may take some additional timing delay to return the control back to the thread waiting for the transfer completion In the case of strided transfer, the data transferred consists of multiple contiguous blocks. Let the transfer consists of s 1 blocks each of size s 2 bytes. The DMA set up call incurs a fixed initialization cost for the transfer given by I 0 . The hardware transfers s 1 blocks successively. After transmission of each s 2 block, the source/destination address is incremented with an amount equal to the stride of the transfer. This incurs a fixed cost which is proportional to number of s 1 blocks and given by I 1 • s 1 . The time required for entire data to be sent through the network is proportional to the cost per byte, and is given by g • (s 1 • s 2 ). The DMA transfer delay for strided DMA is shown in Equation ..

T(s 1 , s 2 ) = I 0 + I 1 • s 1 + g • (s 1 • s 2 ) (.)
Obviously from this formula, it is always costlier to perform the strided DMA rather than a contiguous DMA for the same amount of data. But it is always more beneficial to perform a strided DMA than to perform s 1 DMA transfers of contiguous blocks. The observations above can be summarized by the following inequality:

T(1, s 1 • s 2 ) ≤ T(s 1 , s 2 ) ≤ s 1 × T(s 2 )

.  p lat for m mode l

We consider the hardware platform as an interconnection of different clusters. Each cluster consists of some number of processors. The processors within the cluster are connected to a shared memory and communicate with each other without any extra overhead or cost. Clusters can have caches in them, in order to provide a faster access to frequently accessed data. However, to avoid modeling complex and difficult to predict cache functionality, we do not model execution time variations due to cache misses but assume average-case execution times instead. The communication between the clusters is facilitated by a mechanism called DMA (Direct Memory Access). Further we assume a fixed routing between global interconnect terminals with distances known statically.

Given the notions above, we can formally define the hardware architecture model as :

Definition  (Architecture Model) -An architecture model A = (X, , M, D , I, g, ) is a tuple, X is a set of clusters, ⊆ X × X is a set of

communication paths between pairs of clusters, whereas

x,x ′ ∈ N 0 gives the distance between any two clusters (x, x ′ ) ∈ X × X. M and D are the number of cores and DMA channels per cluster respectively. I ∈ R ≥0 is the DMA initialization time and g ∈ R + 0 is the cost per byte for a transfer. ∈ R ≥0 refers to the constant time required to check if the DMA transfer is complete.

.  c onc lus i on

In this chapter we discussed multi-core and many-core processor architectures encountered in our work and how they can be modeled. We abstract from minute details of the hardware platforms and while retaining the important parameters which are useful for mapping and scheduling. The architecture model presented in this chapter, has a meaningful application to the architectures that we used during this work. In the next chapter we discuss formalisms that ensure application and architecture models can be used to map and schedule application efficiently on such complex platforms. cha pte r 4 Sat i s f i a b i li t y s o lve rs a nd m ult i -c ri t e ri a Opt i m i z at i o n

This chapter introduces the notions of multi-criteria optimization problem and SMT solver which we use to solve multi-criteria scheduling problems.

G iven a many-core hardware platform and a parallel application, to find an optimal mapping and scheduling solution is a hard combinatorial problem. Scheduling tasks on a processor is a well-known research topic, and there are various theories and techniques developed to solve this problem. Scheduling can be viewed as a constrained optimization problem. The constraints are typically precedences (coming from the precedences in the task graph) and resource constraints (e.g. no two tasks can use the same processor simultaneously). Other constraints can concern memory usage, schedule latency, the number of processors used etc. In fact, any performance measure of the system can sometimes be viewed as a constraint and sometimes as an optimization objective. In our work, we use SMT (satisfiability modulo theory) solvers, which collect techniques to solve the problem presented in the form of linear constraints.

Solution to the problem described above with multiple costs is not unique, rather it is a set of incomparable points called Pareto points. Such problems are called multi-criteria optimization problems. In these problems, the costs generally conflict with each other, such that reducing one cost may require increase in another one and vice-versa.

In this chapter we present some basic facts on SMT solvers which we apply to optimize mapping and scheduling for many-core processors. We explain briefly the theory behind them. Then we introduce multi-criteria optimization, for which we would like to apply the SMT solvers. Multi-criteria problems need specialized algorithms in order to track their solutions. We conclude the chapter by discussing such algorithms.

 . s at i s fi a bi li t y s olve r s

The scheduling problem can be approached with different forms of expressing the problem and corresponding solution methods. A technique called Linear programming [] is applicable when the problem is expressed in terms of conjunction of linear inequalities, and the set of feasible solutions is a convex polyhedron. Applicable for unbounded resources, this theory can produce quick solutions. However, scheduling under resource constraints is a non-convex problem. For example the mutual exclusion constraint, when a pair of tasks share a processor so that they should not overlap in time, can be expressed only as a disjunction of inequalities. For example, for a pair of tasks A and B allocated to the same processor, task A can start either after task B has finished or vice-versa. Due to such constraint, the solution space of the problem consists of a number of disjoint convex sets. A branch of linear programming called Mixed Integer Linear Programming (MILP), also known as disjunctive linear programming, is used for scheduling problems in operations research area []. However the MILP-based methods can solve scheduling problems typically upto a few tens of tasks [, ]. Thus, the applicability of disjunctive linear programming is severely limited.

However there are techniques which we believe to be better scalable specialized in solving Boolean combinations of constraints, popularly known as constraint logic programming (CLP) [], which explore the search space for a solution and employ techniques like constraint propagation to prune the search space. A CLP problem is composed of atoms. An atom is a linear inequality of a Boolean variable. A literal is either an atom or its negation. The constraint logic program contains different clauses (or constraints) which are disjunctions of literals that impose rules on the values that can be assigned to the variables. The solver performs search over the domains of the variables in order to find an assignment which satisfies all the constraints. For example if X is defined as a variable in the constraint logic program, X f alse will be a constraint, due to which X will be always assigned with a true value. The solvers which solve problems expressed in a Boolean CNF (conjunctive normal form) form are called satisfiability (SAT) solvers. In the course of its development, the SAT theory was generalized to non-Boolean variables arranged in predicates "theory constraints as more complex atoms". For example xy > c, a linear inequality, can be expressed in these solvers. Such kind of solvers are called satisfiability modulo theories (SMT) solvers []. These solvers can take advantage of existing SAT solver search engine either by converting a SMT problem to a Boolean SAT problem (eager approach) or by using theories which can perform constant propagation and conflict analysis in order to solve the problem (lazy approach).

An algorithm called DPLL [], which involves backtracking-based search procedures for deciding the satisfiability, enhanced the performance of these solvers. Further improvements were made to the solvers, like for example CHAFF SAT solver [] incorporated carefully engineered data structures and algorithms to accelerate the search. GRASP (Generic seaRch Algorithm for the Satisfiability Problem) [] is another example of a novel algorithm which unified several search-space pruning methods and improved back-tracking techniques. Modern SMT solvers such as Yices [], Z [] and many more employ such efficient techniques and are widely used in the verification community.

The SAT solver problem context typically consists of Boolean variables, their negations and disjunctions. For SMT, in addition to Boolean variables, there are other variable types such as integer, real, arrays, interpreted functions etc. The solver checks whether there is an assignment of values to the variables which satisfies all the mentioned constraints. If solver is unable to find such an assignment (due to conflicting clauses), the problem is said to be unsatisfiable. SAT or SMT solvers use backtracking algorithm which incrementally builds the solution to the problem. In case if an assignment of a value to a variable creates a conflict (unsatisfiable solution), this assignment can be retracted and checking continues with other assignments. This procedure is carried out recursively. DPLL algorithm provides rules for backtracking. We explain them briefly for satisfiability solvers.

■

Unit Propagation is done when a clause is a unit clause containing only one literal. In such cases, the variables are assigned values to make the problem satisfiable, and the opposite value for these variables is not evaluated.

■

Clause Elimination is done when a variable is assigned such a value, that clauses containing this variable become true. These clauses do not constrain the search and can be safely eliminated. Advanced backtracking techniques have enhanced the performance of SMT solvers so that they can solve large problems using multiple theories. When the problem is presented in form of variables and clauses to the solver, it uses different theories depending on the nature of the problem and produces a solution. Within a limited time budget, the SAT solver can return an answer as sat (satisfiable), unsat (unsatisfiable) or timeout (unable to decide). If the answer returned is sat, then the solver builds up a model which describes the values which are assigned to the variables. If the answer is unsat, it implies that the problem contains conflicting clauses and cannot be satisfied. In case the result is timeout, it means that with the time budget the solver could not decide upon its satisfiability if the problem is sat or unsat. This suggest that we should either increase the time budget, or the problem is too difficult to solve.

 . a n e xa mp le of s mt c ons t r a i nt s

We present an example of SMT constraints for scheduling a split-join graph shown in Figure . for = 3. The derived task graph, T = (U, E, , ), will have tasks A 0 , B 0 , B 1 , B 2 and C 0 . Let s(u) and e(u) denote the start and end time of a task u, and (u) be the processor on which it will execute.

The constraints which express the task graph for scheduling to the solver are given as:

■ Non-negative start times: indicating that there are no negative start times of the task. Note that this kind of constraints are implicit as we will see later they follow directly from definition of variable domains, like s(u) ∈ R ≥0 in this case. In sequel we do not explicitly specify such constraints.

■

End times: The task always finishes when the time equal to its execution time has elapsed after the starting time.

u u ′ ∈U ( (u) = (u ′ )) ⇒ (e(u) ≤ s(u ′ ) ∨ (e(u ′ ) ≤ s(u)) ■
Processor cost: The tasks should use only M processors or less.

u∈U (u) ≥ 0 ∧ (u) < M
Thus the scheduling of task graph can be encoded as an SMT problem with linear arithmetic theory. A more detailed encoding of the problem is presented in Section ..

.. Non-retractable and retractable constraints

A constraint solver can be used for optimization by adding to the constraint satisfaction problem a condition of form x ≤ C that can be used for cost optimization, where x is a tight upper bound on the cost and C is a constant. In order to find an optimal cost, the solver must be queried for different values of the cost to detect feasible (satisfiable) and unfeasible (unsatisfiable) cost points. In such an exploration, the set of constraints remains the same, except for the value of constant C. To recall, the problem context of an SMT solver consists of variables and constraints defined on these variables. We take advantage of two specific types of constraint typically supported by the SMT solver tools: non-retractable constraints are the one which cannot be removed from the problem context, and retractable constraints which can be removed from the problem context in the order reverse from their addition order, which leads to incremental update of the problem definition without redefining the problem from scratch. This can save some solver computation time across multiple queries. In the above example, we can put all the constraints as non-retractable and the processor cost as retractable. For every query, the retractable constraint must be updated with a new value of constant M.

As explained above, if a problem has only one cost, the optimal cost can be searched using successive queries with different values of the cost (binary search) using a retractable constraint. However when the problem admits multiple costs we need a more elaborate exploration of the cost space, because in such problems there is typically no unique single solution, but rather a set of incomparable solutions (points in the cost space). Such a problem is called multi-criteria problem, which is discussed further in detail.

.  mult i -c r i t e r i a p r oble m

In optimization problems, a search is performed to reduce the cost to a feasible minimum value satisfying the constraints. For example, in binary search, a solution with higher cost is discarded, when a solution with lower cost is found, narrowing down the space of explored costs. With respect to a given point, a solution point in the cost space with higher cost is called dominated point and while the point with a lower cost is called dominating point. If we consider a problem with multiple costs, then the dominated point should have a distinct cost that is no better than reference point in all dimensions. Formally, dominated points can be defined as follows.

Definition  (Dominated Points) -Any two points c and c' belonging to same cost space, point c dominates c', if for every dimension

i ∈ [1..d], c i ≤ c ′ i and c c ′ .
If we eliminate dominated by other points from set of solutions for such multi-dimensional problem, the resulting set consists of alternative solutions which represent the best trade-offs A typical example in scheduling for such multi-criteria problem will be optimizing the latency cost of a schedule and the number of processors used in it which is proportional to amount of static power consumption. Given that there is enough parallelism available in the application, if we increase number of processors, the application can run concurrently, which will decrease the latency of execution. Similarly if we decrease number of processors, then a larger portion of application will execute sequentially thus increasing the latency of execution. It is desirable to reduce both latency and number of processors used. However, if we try to reduce one cost the other cost increases and vice-versa. Such problems are called multi-criteria optimization problems [], and are being studied since a long time [, , ]. Some of these multi-criteria problems exhibit a monotonic behavior. For example, in processors and latency trade-off, if a point C 1 = (2, 5) is feasible, then the point C 2 = (3, 9) will also be feasible. This can be thought as if a schedule satisfies cost of  processors and latency cost of  units, then another point with cost of  processors and loose latency of  units will also be feasible, owing to the fact that some processors and/or some time intervals might remain unused. Similarly, if the point C 2 = (3, 9) is infeasible, then point C 1 = (2, 5) will be infeasible because if problem cannot be scheduled with  processors, it cannot be satisfied with  processors and a tighter latency.

s B + (s) B -(s) s ′ < s s ′ > s s ′ || s s ′ || s
For such monotonic problems, we can assume that all points above a feasible cost are feasible and those below an infeasible cost are infeasible. More formally, as shown in Figure ., if point s is a sat point, then the forward cone represented by B + (s) contains only feasible points. Similarly if point s is unsat point, then the backward cone represented by B -(s) contains only infeasible points. The remaining s ′ || s are incomparable points with respect to s. Also if s is a sat, then the algorithm must explore the B -(s) and s ′ || s for Pareto solutions. If it explores the forward cone B + (s), then it is waste of effort, since the solver will always return sat or timeout. Similarly for unsat point, the algorithm must explore B + (s) and s ′ || s.

. c os t-s pac e e xp lor at i on

The optimal solution for a multi-criteria optimization problem is the set of Pareto points. To find or approximate this set, we need to explore the cost space. Typically the cost space is huge and intelligent algorithms are needed to obtain quickly a good approximation of the Pareto front. There are various approaches and algorithms for this exploration. One approach is to consider the cost of a problem as a weighted sum of multiple costs and solving it for one-dimension using binary search and repeating the process with different weight vectors.

C 0 C 1 C 1 = B + (C 1 ) C 0 = B -(C 0 ) C (a) (b)
Certain other popular approaches depend on heuristic search techniques to find solutions.

Examples of such approaches are evolutionary / genetic algorithms [, ]. In [], a distance based algorithm was proposed which approximates the Pareto front by aiming at reducing the distance between the sat and unsat points. It involves a complex algorithm to explore the cost space which depends on the current state of the exploration and can be viewed as a multi-dimensional form of binary search. Instead we use a simple grid-based exploration algorithm which relies on successive refinement of cost space in the grid. First we briefly describe below the problem formally and then we discuss the grid based algorithm. Let Q(c) be a shorthand for the satisfiability query ∃ ∃s s.t. ( , s, c), which asks whether there is a feasible deployment (mapping , schedule s), whose cost vector is less than or equal to c. If the solver answers affirmatively with some cost c we have a solution and may also conclude any cost in forward cone of c that B + (c) = {c ′ | c ′ ≥ c} is feasible, which follows directly from the cost constraints. If the answer is negative we can conclude that any cost in the backward cone B -(c) = {c ′ | c ′ ≤ c} is infeasible. After submitting a number of queries with different values of c we face a situation illustrated in Figure .. The sets C 0 and C 1 are, respectively, the maximal costs known to be infeasible (unsat) and minimal feasible costs found (sat). Sets C 0 and C 1 are defined as the sets of all points known to be unsat and sat, they are equal to the union of forward/backward cones of the extremal points. The feasibility of costs which are outside C 0 ∪ C 1 is unknown. The set C 1 constitutes an approximation of the Pareto front and its quality, defined as a kind of Hausdorff distance to the actual front, is bounded by its distance to the boundary of the backward cone of C 0 .

 . di s ta nc e ba s e d e xp lor at i on

The algorithm presented in [] calculates the Hausdorff distance between the sat and unsat sets C 0 and C 1 , and tries to reduce it by successively querying the solver for different costs. The exploration algorithm maintains a list of currently explored points and updates the distance between the two sets with newly added points. The distance is then reduced by repeatedly querying at mid-way between the two points which give a maximum distance. The query returning sat are added to C 0 , while those returning unsat are added to C 1 . Every query that is asked to the SMT solver has a time limit (query time out). Since there will possibly be a large number of Pareto points, to restrict the runtime of the algorithm a global time out is applied, after which the algorithm stops at the current state. For more details, the reader is referred to [].

 . g r i d ba s e d e xp lor at i on

Instead of the distance-based algorithm in this thesis, we use here a simpler exploration algorithm based on grid refinement. In the multi-dimensional cost space, a grid is placed initially at each dimension in midway(see Figure .). We perform the queries on the intersecting points of the grid. At every stage of the algorithm we refine the grid defined on the cost space, making it denser and ask Q(c)-queries with c ranging over the newly-added grid points which are outside C 0 ∪ C 1 . Note that not all these new points will necessarily be queried because each query increases the size of C 0 ∪ C 1 so as to include some of these points. The description so far was based on the assumption that all queries give a definite answer (sat or unsat). However it is known [] that as c gets closer to the boundary between sat and unsat, the computation time may grow prohibitively and the solver can get stuck. To tackle this problem we bound the time budget per query and when this bound is reached we mark the given point as timeout Choosing the appropriate value for the time budget is a matter of trial and error.

We use a parameter , which determines the current relative granularity of the Pareto exploration in all dimensions. In every dimension we perform linear search. In particular, in dimension p we make 1/ steps of equal size from C min The top level procedure of our algorithm is illustrated in Algorithm . The whole exploration has a global timeout, globalTimeOut. To accumulate the current knowledge on the cost space, the algorithm maintains two set variables, C 0 and C 1 (in the actual implementation we just keep track of the extremal points C 0 and C 1 along with the timeout points C t ). The initial exploration granularity is set to = 1/2, and we recursively reduce it by a factor 1/2 after the entire exploration at the given step is finished. Thus with more iterations, the algorithm explores the cost space with finer granularity.

Each iteration executes a nested loop, one level of nesting per dimension. Procedure explore, shown in Algorithm , executes one level of loop nesting and calls itself recursively to explore in the next dimension. This procedure lets the current dimension of vector c assume all linear search values, whereas the other lower dimensions remain constant, initially set to C max . The lower dimensions assume their currently explored value, whereas the current dimension p is explored between C mi n p and C max p bounds. There can be three possible results for a SMT query: sat, unsat, and timeout, the latter occurring when the satisfiability conclusion was not reached within the timeout, and in this case marked as timeout. If, on the contrary, satisfiability has been computed, then one of the

Algorithm  Pareto Exploration Algorithm C 0 := ∅ ⊲ unsat points C 1 := {C max } ⊲ sat points C t = ∅ ⊲ timeout points := / while algoRunTime() ≤ globalTimeOut do p := firstDimension() c := C max explore( , p, c, C 0 , C 1 ) := /  end while C 1 := minimalPoints(C 1 ) return C 1 Algorithm  explore( step , dimension p, cost c, cost set C 0 , C 1 )
⊲ Explore cost dimension p and higher for := 0 to 1 step do

c p := round ( (1 -) • C min p + • C max p ) if c C 0 ∧ c C 1 ∧ c C t then result := satQ uery(Q(c), satTimeout) if result = sat then C 1 := C 1 ∪ B + (c) else if result = unsat then C 0 := C 0 ∪ B -(c) else C t := C t ∪ c end if end if if c ∈ C 1 ∧ ¬lastDimension(p) then explore( , nextDimension(p), c, C 0 , C 1 ) end if end for
two sets are extended by point c as a minimal/maximal point. For a solver query, we impose a per query timeout satTimeout, which is much smaller than globalTimeOut and determined by manual calibration of this setup.

Note that procedure explore calls the solver directly only until the first sat answer or a C 1 point has been reached. After this, all the remaining values to be explored for c p automatically fall into the 'known sat' area, C 1 and thus the solver is called only for the deeper recursion levels, with lower cost values in the higher dimensions. In order to speed up the algorithm, instead of linear search, a binary search method is used in the actual implementation.

 . c onc lus i ons

We briefly discussed the SMT solvers and the theory behind them. We also discussed the multi-criteria optimization problems. These problems have multiple conflicting costs to be optimized, and the solution to such problems is not unique, but rather consists of multiple incomparable solutions also called Pareto solutions. The exploration of these problems in their respective cost-space require specialized algorithms to track the Pareto solutions. We presented the grid-based exploration algorithm which is used in our work to explore the multi-dimensional cost space.

In further chapters we talk about how to encode the deployment problem as SMT constraints and efficiently find solutions using such exploration algorithms. We also discuss how the solutions discovered by the SMT solver can be deployed on a multi-core system. cha pte r 5

D e p lo ym e nt a nd E va luat i o n M e t ho do lo g y

This chapter describes our framework to explore, deploy and evaluate the solutions on a multi-core platform.

T he SMT solver is responsible to analyze and produce solutions to the scheduling problem, according to different costs and platform constraints that are specified in the optimization problem. In order to produce these solutions the solver needs inputs in the form of constraints which represent the structure of application including timing information of tasks, token sizes, channel parallelization factors etc. The problem expressed in the form of constraints is then explored by the cost-space exploration algorithm which is described in the previous chapter. The result is in the form of Pareto solutions, which expresses the configuration of the hardware platform on which the application must execute to produce expected results.

Given such a situation, we need a software infrastructure which can perform all the mentioned tasks. We implement a software tool in Java which is used to convert the splitjoin graph information to constraints which can be presented to the solver. We call this tool StreamExplorer. StreamExplorer also incorporates the cost-space exploration algorithm described previously. Further on the hardware platforms we implement a run-time system which deploys the solution produced by the solver. The run-time software is equipped with profiler functionality which can provide accurate timing information of the application to StreamExplorer.

In this chapter we briefly describe StreamExplorer and the run-time system. The run-time system consists of different sub-systems which initialize the application as per the specified configuration, perform different measurements and report statistical data back to StreamExplorer. The first task of the run-time is to profile the actor execution times. StreamExplorer feeds the measured times to the split-join graph. It then performs cost-space exploration to find multiple solutions to the scheduling problem. The approximate Pareto solutions are then verified on the hardware platform using run-time system. We describe the infrastructure of StreamExplorer and run-time system in this chapter.



Property Analyzer

Workload Latency

Graph Models

Split-join SDF

Z Library

Cost-space Explorer

■

Property Analyzer: This part performs different analyses on the split-join graph. For example it performs deadlock analysis and checks for the consistency of the graph. In addition it can provide different properties like total execution time in the graph, longest path etc. It also provides support functions to determine the connected actors / tasks, get split join factors etc.

■

Input Parsers: The parsers form a vital part of the StreamExplorer which parses the input XML file, containing the information about the split-join graph model (rates, number of actors, interconnections etc.). It also contains a parser to parse the specification of hardware platform defined in Chapter .

■

Solver Interface: This part of the StreamExplorer performs the conversion of the splitjoin graph and platform model to constraints which are presented to the SMT solver. We have integrated Z SMT solver tightly with the StreamExplorer. The StreamExplorer creates variables and constraints for non-pipelined scheduling, from the split-join graph model and platform parameters.

■

Cost-space Explorer: This part of the StreamExplorer consists of the cost-space exploration algorithms (grid-based, binary search etc.). The algorithms in this part are generic and can be easily configured for different exploration like latency vs buffer size, latency vs processors etc.

■

Output Generators: The output generators produce the results of different analyses and optimizations performed. The most commonly used for analysis of inputs and results, are the dot graph generation for graphical representation of split-join graphs, Gantt chart generation for a schedule, schedule XML generation for run-time system.

StreamExplorer consists of total K+ lines of code written in Java and K+ lines of code written in C++ for runtime system. It is interfaced with the SMT solver using Z library. Z solver in the tool, can be easily replaced by another solver by performing minimal changes. The link between the StreamExplorer and the run-time system is provided with bash scripts which automates the process.

.  p r ofi li ng t h e a p p li c at i on

The profiling of the application is done mainly in order to measure the execution time of different actors. The execution times of actors are used for scheduling in the solver. We use the XML format similar to that in SDF tool [] to present the split-join application graphs in the form of an equivalent SDF graph. The profiling of application is done on the platform, which uses the run-time system for measurement and produces a XML file which contains the timing information of the application. In order to run the profiled application, the run-time system must be initialized (for data-structure, FIFOs etc.) and hence must be provided with a schedule XML. Thus it is a cyclic requirement, where for initial profiling we need a schedule XML, but also an XML is generated by the run-time based on the profiling. It is possible to create a front-end parser, which can detect the parameters of split-join application graph (for example MpOpt []) automatically. However it is an extra effort and out of scope of this thesis. In order to satisfy this cyclic dependency, we provide a default XML configuration file, which is able to configure the split-join application graph to execute on a single processor with an arbitrary valid sequential schedule and the required buffer size for that schedule.

This default configuration is used to profile the application graph in the run-time. In its sequential schedule neither shared memory contention on the bus nor network contentions are present. Thus we measure the timing which is unaffected by these two factors. In profiling, the application is executed for  graph iterations and a statistical data is produced on the execution times. It contains minimum, maximum, average values for every actor present in the application. Thus the profiling reports worst case and average case value of the actors and either of them can be chosen for the optimization purpose.

.  run-t i me e nvi r onme nt

The run-time system is a piece of software written in C++, which requires an input schedule XML file that describes the split-join application graph and is linked with the functional code of the actors. It is used to deploy the scheduling solutions on the platform and consists of three parts: ■ Initialization : allocate data structures for execution.

■

Execution : execute different schedules on the processors.

■

Release : collect results and deallocate data structures.

.. Initialization of the application

The first phase performs the initialization of the application graph on the platform. It first reads the buffer size of the all the channels allocated in the schedule, and it allocates the memory and initializes the data structures for them. Further it initializes every processor that is supposed to execute tasks and provides it with the static order of tasks according to the schedule. The information of the static schedule described in the schedule XML file is discarded, however the ordering between the actors is retained. The name of actors in the schedule XML file are resolved to the functions which execute as functional code for the actors. Every application defines a standard translation function which associates the name of the actor to the function that can be executed on behalf of it. The run-time is thus able to associate a piece of code to every actor. When this resolution is finished, the run-time system then calls application specific initialization where the pre-execution functions are performed such as memory allocations specific to the application.

From programmers perspective, an actor is a function which will be called by the runtime to execute it on the platform. It will be provided with the data structures where it can access the tokens in input and output FIFO.

.. Execution of the application

After the initialization is finished on the hardware platform, the run-time enters Execution phase. In this phase, the run-time spawns a thread on every processor to which a schedule is allocated. The remaining processors remain idle. Every processor executes its respective static-order schedule in a self-timed way for a fixed number of iterations. In later subsection, we explain how due to our FIFO design, the precedence between the reader and writer are respected. We enforce a barrier synchronization between iterations, since we assume a nonpipelined execution. The run-time measures the time required for execution of the actor instance which is also used for debugging purpose. The latency is measured for every graph iteration on every processor. The maximum of the values measured on all the processors, gives the latency of the graph iteration.

.. Release of the resources

After the execution has finished, the run-time calls the application specific exit calls for application to release any allocated resources and transfer of the application output data (e.g. decoded JPEG image). Then it deallocates all the data structures and gathers the measurements that were done on the platform. Finally it performs statistical analysis on the measurements and generates the output XML. The output XML generated by the run-time system contains statistical information about actor execution as well as latency. The latter is compared with the model predicted latency.

.. Hardware Specific Implementation

Depending on the hardware platform, the run-time system is adapted accordingly. We discuss the hardware-specific implementation briefly.

... Kalray MPPA-

On the Kalray architecture, the host processor and the MPPA platform are connected with a PCI bridge. The run-time system implements a data transfer part, which allows communication of data over the PCI to the MPPA fabric. The data is first uploaded to the IO clusters and then from there it is distributed to the compute clusters. In the initialization phase this data consists of schedule information for the involved compute clusters. At the release phase, collected measurement and the application output is fetched from the compute clusters to the host via I/O clusters.

The barrier synchronization on this platform is performed in two phases. Inter-cluster synchronization is done using IO cluster which communicated with 0 th processor of every compute cluster. After all the compute clusters are synchronized, the synchronization inside a cluster (intra-cluster synchronization) is performed using a pthread library barrier.

The I/O cluster reads the schedule XML file for the application and starts the compute clusters accordingly. It keeps the unallocated clusters inactive.

... Tilera Tile Pro

The Tilera processor architecture has support for hardware cache coherency. Thus the run-time execution system can execute as if it had just one cluster. It does not need any explicit data transfer mechanisms between processor cores, as it is taken care by coherency mechanism.

In order to execute plain application code without any interruption from the operating system, the Tilera software supports bare-metal environment. The processors configured this way execute only the application code in the pthread parallel programming library. We configure only one processor for execution of operating system and another one for handling I/O devices. The remaining  processors execute the application tasks.

The processor running the operating system starts a thread on every allocated processor. Each thread then executes the allocated schedule for a fixed number of iterations. We use the low-level hardware primitives provided by the Tilera software library which implements locks, barriers, atomic operations etc. These primitives significantly speed-up the software execution compared to the pthread primitives.

.  c ommuni c at i on buffe r s

In the split-join graph application model, the actors communicate via channels. The writer actor of the channel generates the tokens on the channel, while the reader actor of the channel removes them.

Following the model semantics, the split-join graph channels should use a bounded memory. To suit this requirements, the communication memory should be re-used efficiently. Moreover, to exploit the data parallelism of the split-join channels, it should be possible to execute different concurrent task instances of channel writer and reader on different cores. The requirements of the communication buffers can be listed as follows :

■ Correct token delivery from the writer of the token to its reader.

■

Reuse of the communication buffers (i.e. of the token space positions inside).

■ Arbitration between writers and readers of the same token position.

■ Support for concurrent instances of writer and reader that access the same reused token position.

■

In the case of inter-cluster channel, the delivery of data and its status between writer and reader. We created a software FIFO buffer implementation that satisfies these requirements. To support concurrent writers and readers we exploit the fact that in a split-join graph each writer/reader instance writes/reads statically known amounts of data at statically known offsets. Therefore, each token data is extended with status record that can be updated independently, indicating whether the given token is ready to be written or read. For the reuse of bounded token memory, we use standard circular buffer with a wrap-around mechanism.

It is very important to note the following. The term FIFO here indicates a certain ordering restriction between the concurrent instance of writer and reader that write and read to the same reused token position in the buffer. The task instances with a smaller task index should execute earlier than those with a larger index. This restriction on the schedule coincides with the notion of task symmetry introduced in Chapter , where we also prove that restricting the schedule like this does not lead to sub-optimality.

The FIFO buffer can be regarded as a collection of a memory allocated for a data structure that includes token data and token status. In the FIFO buffer implementation, the status record for every token consists of  parts. The first part is the index of the token, while the second part consists of a state of the token which can be {'e '-empty, 'b'-busy, 'd'-contains data}. Every writer task of the FIFO buffer can acquire token only when the token is empty, similarly, a reader task posi ti on 0 posi ti on 1 st 0 st 1 (a) FIFO structure in memory, st i is status of the FIFO buffer can acquire token only when the token contains data. The reader and writer both, when acquiring a token change the state to busy. When writer task finishes, it updates the state part to from busy to contains data. Similarly when reader task finishes, it updates the state part from busy to empty. In addition to state, the index part identifies to which instance the token belongs. Before execution, the tokens are assigned index ,,... The instance  of the writer can access only the tokens in index range [0, ↑ ), instance  can access [ ↑ , 2 • ↑ ) and so on. In general any instance i of a writer can access tokens in range [i • ↑ , (i + 1) • ↑ ). Similarly, any instance j of reader can access tokens having index [j • ↓ , (j + 1) • ↓ ). In a bounded buffer with size b tokens, a token space at position k is first used for token k then reused for tokens k + b, k + 2b etc. Therefore, the value of index is monotonically increasing and the reader instance increases it by the size of the FIFO buffer upon its completion. The index value also implies the position in the FIFO buffer. The writer and reader of the FIFO buffer, both access statically known positions in the FIFO buffer, which can be easily calculated from their task index. Thus, a combination of index and state gives an accurate information about which task has a right over the token position in the FIFO buffer. An important point to note is, the FIFO design does not make any assumption about execution time of its producers and consumers. The FIFO is robust against the variation in the execution time. ■ Initially posi ti on 0 and posi ti on 1 are marked with status 0 e and 1 e , indicating two empty tokens with index  and  respectively. ■ writer instance A 0 acquires token 0 and marks it as busy. Similarly A 1 marks token 1 as busy.

A 0 A 1 B 0 A 2 A 3 B 1 0 e 1 e 0

.. FIFO buffer example

Suppose in a split-join graph (A, B) is a channel with parameters = 1/2, c(A) = 4, c(B) = 2 ↑ AB = 1, ↓ AB = 2,

■

After A 0 finishes execution, token 0 contains data which changes its status to 0 d indicating it contains data. Similarly A 1 changes the status of token 1 .

■ reader instance B 0 , who should read from both token 0 and token 1 , waits till both of them contain data. At the beginning of its execution it marks both them as busy.

■

After B 0 finishes execution and increments the index of token 0 and token 1 to  and  respectively. Also it marks them as empty.

■ A 2 and A 3 waited for token status 2 e and 3 e respectively. Now they can continue execution and the rest follows similarly. Table . shows the token status before and after execution of each instance. From this table, we can see that each actor instance awaits and modified token status records at pre-known locations with unique index and status. Thus we can conclude that irrespective if the reader and writer instances are executing in parallel, they will wait for each other to maintain the correct order of production and consumption of tokens. This logic guarantees that the tokens are delivered correctly.

Table . -FIFO buffer token status before and after execution of tasks token 0 token 1 instance before after before after FIFO buffer used by Erbium compiler [] to map streaming applications on shared memory processors use similar notions.

A 0 0 e 0 d - - A 1 - - 1 e 1 d A 2 2 e 2 d - - A 3 - - 3

.. Inter-cluster FIFO buffer in Kalray

In Kalray MPPA, we have a possibility of allocating communicating actors on different clusters if memory or processor resources of a single cluster are insufficient. In such a case, the FIFO buffer must be adapted to transport the tokens from one cluster to another. The run-time checks the cluster assignment of writer and reader to detect inter-cluster FIFO. Such FIFO buffer has the writer actor and reader actor allocated on different clusters. In the FIFO buffer implementation, the same amount of memory is allocated at the source and destination cluster. Also in addition to the token status at the writer side, it also contains remote token status which is updated by the reader side when consuming of the token is finished. At the end of its execution, the writer starts a DMA transfer from the source cluster to destination cluster. It can start writing only if the remote token status indicates a free token at the same position. Similarly, when the reader finishes execution, it starts a DMA transfer to update the token status at the positions that it has finished reading, back to the writer side. Such a communication is referred to as flow control. It allows the reader and writer of the FIFO buffer to be in sync with each other. More details on inter-cluster FIFO buffer will follow in Chapter .

.  c onc lus i ons

In this chapter we described the tool StreamExplorer, that we have developed, which performs a task of converting a split-join application graph, represented in form of XML, to SMT constraints and provides a run-time environment to deploy the SMT solutions on the platform. We also describe how StreamExplorer performs profiling of the application code via run-time system. The profiling information is used by the StreamExplorer to annotate the split-join application with actor execution times to be used in SMT solver scheduling constraints. The problem is explored by the StreamExplorer to find solutions, which are are implemented and verified for accuracy by measurements in the run-time system. The run-time system produces statistics for every solution, which is used to evaluate the accuracy of solutions produced by the solver. Such infrastructure allows us to experiment with various split-join applications represented by their respective XML files in SDF format. In the next chapter we will discuss how the split-join graph can be represented using SMT solver constraints in order to solve the scheduling problem on a hardware platform, first restricting ourselves to one shared memory cluster to extend later to multiple clusters. We will also discuss the techniques enabling the SMT solver to accelerate the discovery of the solutions. W e encode the multi-core deployment for split-join graphs as a quantifier-free SMT prob- lem, defined by a combination of linear constraints. The major computational obstacle is the intractability of the mapping and scheduling problems aggravated by the exponential blow-up while expanding the graph from symbolic (actors) to explicit (tasks) form (refer to Section .). We tackle this problem by introducing "symmetry breaking" constraints among identical processors and identical tasks. For the latter we prove a theorem concerning the optimality of schedules where instances of the same actor are executed according to a fixed lexicographical order.

In this chapter we discuss the symmetry breaking constraints and the theorem which underlies them. We present the experimental results of exploration with and without the symmetry constraints. We conclude this chapter by presenting the results with real JPEG decoder and Video decoder applications.

.  s y mme t r y i n s p li t-joi n g r a p h s

The data-parallel tasks encoded in the split-join graph model are symmetrical in nature. They represent equal computations which can be executed in parallel. A permutation of instances of an actor in a schedule of a split-join graph can produce an equivalent schedule, such that the properties of the schedule (latency, number of processors used etc.) remain the same. Such equivalent schedules do not give any additional benefit to the programmer, rather they prove to be a hurdle in satisfiability proving of the problem. The amount of permutations grow exponentially with the number of data-parallel tasks. Thus these equivalent schedules must be excluded, without losing optimal solutions in the cost space. We discuss the symmetry in the split-join graphs further in detail.

Recall that in a split-join graph the decomposability of a task into parallelizable sub-tasks is expressed as a numerical label (parallelization factor) on a split edge leading to it. In To distinguish between these two types of graphs we call the nodes of the split-join graphs actors (task types) and those of the task graph tasks.

In Chapter  we have defined the notions of consistency of split-join graphs and showed how a task graph can be derived from a consistent split-join graph. In this section we formally define a sub-class of consistent split-join graphs called well-formed split-join graphs. Most of practical split-join graphs are well-formed. For these graphs we prove a theorem leading to symmetry breaking for identical data-parallel tasks.

The DAG structure of a split-join graph naturally induces a partial-order relation ∠ over the actors such that v∠v ′ if there is a path form v to v ′ . The set of minimal elements with respect to ∠ is V • ⊆ V consisting of nodes with no incoming edges. Likewise, the maximal elements V • are those without outgoing edges. An initialized path in a DAG is directed path

= v 1 • v 2 • • • v k starting from some v 1 ∈ V • . Such a path is complete if v k ∈ V • .
With any such path we associate the multiplicity signature

( ) = (v 1 , 1 ) • (v 2 , 2 ) • • • (v k-1 , k-1 )
where i = r((v i , v i+1 )). We will also abuse to denote the projection of the signature on the multiplication factors, that is

( ) = 1 • 2 • • • k-1 .
To ensure that different instances of the same actor communicate with the matching instances of other actors and that such instances are joined together properly, we need an indexing scheme similar to indices of multi-dimensional arrays accessed inside nested loops. Because an actor may have several ancestral paths, we need to ensure that its indices via different paths agree. This will be guaranteed by a well-formedness condition that we impose on the multiplicity signatures along paths.

Definition  (Parenthesis Alphabet) -Let = {1} ∪ { ∪ } be any set of symbols consisting of a special symbol 1 and two finite sets { and } admitting a bijection which maps every ∈ { to ′ ∈ } , for > 1, ∈ N.

Intuitively and ′ correspond to a matching pair consisting of a split and its inverse join 1/ . These can be viewed also as a pair of (typed) left and right parentheses.

Definition  (Canonical Form) -The canonical form of a sequence over a parentheses alphabet is the sequence ¯ obtained from by erasing occurrences of the neutral element 1 as well as matching pairs of the form • ′ .

For example, the canonical form of = 5

• 1 • 3 • 1 • 1 • 1/3 • 1 • 2 is ¯ = 5 • 2.
Note that the (arithmetic) products of the factors of and of ¯ are equal and we denote this value by c( ) and let c( ) = 1. A sequence is well-parenthesized if ¯ ∈ * { , namely its canonical form consists only of left parentheses. Note that this notion refers also to signature prefixes that can be extended to well-balanced sequences, namely, sequences with no violation of being well-parenthesized by a join not compatible with the last open split.

Definition  (Well Formedness) -A split-join graph is well formed if:

. Any complete path satisfies c( ( )) = 1; . The signatures of all initialized paths are well parenthesized.

In fact, the first condition implies SDF consistency. It ensures that the graph is meaningful (all splits are joined) and that the multiplicity signatures of any two paths leading to the same actor v satisfy c( ) = c( ′ ). We can thus associate unambiguously this number with the actor itself and denote it by c(v). Note that it coincides with the repetition count defined in Section ..

The repetition count is the number of instances of actor v that should be executed.

The second condition forbids, for example, sequences of the form 2 • 3 • 1/2 • 1/3. It implies an additional property: every two initialized paths and ′ leading to the same actor satisfy ¯ ( ) = ¯ ( ′ ). Otherwise, if two paths would reach the same actor with different canonical signatures, there will be no way to close their parentheses by the same path suffix. Although consistent split-join graphs not satisfying Condition  can make sense for certain computations, they require more complicated mappings between tasks and they will not be considered here. As for the restrictions that we imposed on the split-join graph compared to more general SDF graphs admitting non-divisible token production and consumption rate, let us first remark that the main result of this chapter, Theorem ., can be extended, somewhat less elegantly, to an acyclic SDF, as we do in []. Moreover, the extensive study of StreaMIT benchmarks found in [] reports that most actors in most applications, fall into the category of well-formed split-join graphs that we treat  . For well-formed graphs, a unique canonical signature, denoted by ¯ (v), is associated with every actor.

Definition  (Indexing Alphabet and Order) -An actor v with

¯ (v) = 1 • • • k defines an indexing alphabet A v consisting of all k-digit sequences h = a 1 • • • a k such that 0 ≤ a i ≤ i -1.
This alphabet can be mapped into {0, . . . , c(v) -1} via the following recursive rule:

N ( ) = 0 and N (h

• a j ) = j • N (h) + a j
We use ≪ v to denote the lexicographic total order over A v which coincides with the numerical order over N (A v ).

Every instance of actor v will be indexed by some h ∈ A v and will be denoted as v h . We use notation h and A v to refer both to strings and to their numerical interpretation via N . In the latter case v h will refer to the task in position h according to the lexicographic order ≪ v . See for example, tasks B 0 , B 1 , . . . in Figure ..

Recall from Definition , that a derived task graph consists of tasks U which are connected by edges E. In the context of well-formed graphs, we establish a relation between the tasks and dependency arcs on the one hand and their corresponding actors and channels on the other hand as follows:

U = {v h |v ∈ V, h ∈ A v } E = {(v h , v ′ h ′ ) | (v, v ′ ) ∈ E, (h ⊑ h ′ ∨ h ′ ⊑ h)} ∀v, ∀h ∈ A v (v h ) = d(v)
Notation h ⊑ h ′ indicates that string h ′ is a prefix of h. To take an example, according to the definition, a split edge (v, v ′ ) is expanded to a set of dependency arcs

{(v h , v ′ h•a ) | a = 0 . . . -1}, where = r((v, v ′ ))
. The tasks can be partitioned naturally according to their actors, letting

U = v∈V U v and U v = {v h : h ∈ A v }. A permutation : U → U is actor-preserving if it can be written as = v∈V v and each v is a permutation on U v .
Definition  (Deployment) -A deployment for a task graph T = (U, E, ) on an execution platform with a finite set M of processors consists of a mapping function : U → M and a scheduling function s : U → R + indicating the start time of each task. A deployment is called feasible if it satisfies precedence and mutual exclusion constraints, namely, for each pair of tasks we have:

Precedence: (u, u ′ ) ∈ E → s(u ′ ) -s(u) ≥ (u)
Mutual exclusion:

(u) = (u ′ ) → [(s(u ′ ) -s(u) ≥ (u)) ∨ (s(u) -s(u ′ ) ≥ (u ′ ))]
. From a total of  application benchmarks, it is observed that % of the actors in a program have same repetition count. An average of % of the actors have a repetition count of . Non-divisible communication rates, for example in CD-DAT benchmark, are rare.

Note that (u) and s(u) are decision variables while (u) is a constant. The latency of the deployment is the termination time of the last task, max u∈U (s(u) + (u)). The problem of optimal scheduling of a task-graph is already NP-hard due to the non-convex mutual exclusion constraints. This situation is aggravated by the fact that the task-graph will typically be exponential in the size of the split-join graph. On the other hand, it admits many tasks which are identical in their duration and isomorphic in their precedence constraints. In the sequel we exploit this symmetry by showing that all tasks that correspond to the same actor can be executed according to a lexicographic order without compromising latency.

Definition  (Ordering Scheme) -An ordering scheme for a task-graph T = (U, E, ) derived from a split-join graph G = (V, E, r, d) is a relation ≺= v∈V ≺ v where each ≺ v is a total order relation on U v .

In the lexicographic ordering scheme ≪, the tasks v h ∈ U v are ordered in the lexicographic order ≪ v of their indices 'h'. We say that a schedule s is compatible with an ordering scheme

≺ if v h ≺ v h ′ implies s(v h ) ≤ s(v h ′ ).
We denote such an ordering scheme by ≺ s and use notation v[h] for the task occupying position h in ≺ s v .

Lemma  -Let s be a feasible schedule and let v and v ′ be two actors such that

(v, v ′ ) ∈ E. Then . If r(v, v ′ ) = ≥ 1, then for every h ∈ [0, c(v) -1] and every a ∈ [0, -1] we have s(v ′ [ h + a]) -s(v[h]) ≥ d(v). . If r(v, v ′ ) = 1/ then for every h ∈ [0, c(v) -1] and every a ∈ [0, -1] we have s(v ′ [h]) -s(v[ h + a]) ≥ d(v).
Proof. The precedence constraints for Case  are in fact s(v ′ h+a )s(v h ) ≥ d(v), and we have to prove that in this expression the lexicographic index v h can be replaced by schedule-compatible index v[h]. Let j = h + a and j ′ = j + 1. Since each instance of v is a predecessor of exactly instances of v ′ , the execution of v ′ [j] must occur after the completion of at least ⌈j ′ / ⌉ instances of v. By construction, this is not earlier than the termination of the first ⌈j ′ / ⌉ instances of v to occur in schedule s. In our notation this can be written as:

s(v ′ [j]) ≥ s(v[⌈j ′ / ⌉ -1]) + d(v)
Substituting j and j ′ into the above formula we obtain our hypothesis. A similar argument holds for Case .

Theorem . (Lexicographic Ordering) -Every feasible schedule s can be transformed into a latency-equivalent schedule s ′ compatible with the lexicographic order ≪.

Proof. Let s be an actor-preserving permutation on U defined as s (v h ) = v[h]. In other words, s maps the task in position h according to ≪ to the task occupying that position according to ≺ s . The new deployment is defined as

′ (v h ) = ( s (v h )) and s ′ (v h ) = s( s (v h )).
Permuting tasks of the same execution time does not influence latency nor the satisfaction of resource constraints. All that remains to show is that s ′ satisfies precedence constraints. Each v h is mapped into v[h] and each of its v ′ sons (respectively parents) is mapped into v ′ [ h + a], 0 ≤ a ≤ -1. Hence a precedence constraint for s ′ of the form For example, in Figure . we illustrate a task graph, a feasible schedule and the same schedule transformed into a lexicographic-compatible schedule by a permutation of the task indices. The implication of this result is that we can introduce additional constraints to the formulation of the scheduling problem requiring lexicographic compatibility of the schedule without losing optimality. These constraints enforce one ordering of equivalent tasks in time out of many possible, thus significantly reducing the search space.

s ′ (v h•a ) -s ′ (v h ) ≥ d(v) is equivalent to s(v[ h + a]) -s(v[h]) ≥ d(v) A 0 B 1 B 0 B 2 C 0 C 1 C 2 D 0 (a) A task graph A 0 B 0 B 1 B 2 C 2 C 1 C 0 D 0 Time Proc. P P (b) A schedule A 0 B 2 B 1 B 0 C 0 C 1 C 2 D 0

.  s mt c ons t r a i nt s

Expressing scheduling problems using constraint solvers is fairly standard [, , , ] and various formulations may differ in the assumptions they make about the application and the architecture and the aspects of the problem they choose to capture. For split-join graphs, we need to adapt these constraints and re-invent them in order to accommodate the calculation of communication buffer size. In the following section we write down the constraints that define a feasible schedule and its cost in terms of latency, number of processors and buffer size.

u ′ ∈U ( (u) = (u ′ )) ⇒ (e(u) ≤ s(u ′ ) ∨ (e(u ′ ) ≤ s(u)) (.) ■
Communication buffer: these constraints compute the buffer size of every channel (v, v ′ ) ∈ E. They are based on the observation that buffer utilization is piecewiseconstant over time, with jumps occurring upon initiation of writers and termination of readers. Hence the peak value of memory utilization can be found among one out of finitely-many starting points.

Recall that in Section . we define w ↑ and w ↓ as functions on split-join graph channel specifying the size of data in bytes produced and consumed on the channel by execution of one writer or reader instance respectively. Below we use w ↑ v,v ′ and w ↓ v,v ′ for the values of these functions for channel (v, v ′ ). The first constraint defines w↑ (u, u * ), the contribution of writer u ∈ U v to the filling of buffer (v, v ′ ) observed at the start of a writer u * ∈ U v :

(v,v ′ )∈E u∈U v u * ∈U v (s(u) > s(u * )) ∧ ( w↑ (u, u * ) = 0) ∨ (s(u) ≤ s(u * )) ∧ ( w↑ (u, u * ) = w ↑ v,v ′ )
Likewise the value w↓ (u ′ , u * ) is the (negative) contribution of reader u ′ to buffer (v, v ′ ) observed at the start of writer u * :

(v,v ′ )∈E u ′ ∈U v ′ u * ∈U v ((e(u ′ ) > s(u * )) ∧ w↓ (u ′ , u * ) = 0) ∨ (e(u ′ ) ≤ s(u * )) ∧ ( w↓ (u ′ , u * ) = w ↓ v,v ′ ) The total amount of data in buffer (v, v ′ ) at the start of task u * ∈ U v , denoted by R v,v ′ (u * ),
is the sum of contributions of all readers and writers already executed:

(v,v ′ )∈E u * ∈U v R v,v ′ (u * ) = u∈U v w↑ (u, u * ) - u ′ ∈U v ′ w↓ (u ′ , u * )
The buffer size for (v, v ′ ), denoted by B v,v ′ is the maximum over all the start times of tasks in U v :

(v,v ′ )∈E v * ∈U v R v,v ′ (u * ) ≤ B v,v ′ ■ Costs:
The following constraints define the cost vector associated with a given deployment, which is C = (C L , C M , C B ), where the costs indicate, respectively, latency (termination of last task), number of processors used and total buffer size.

u∈U e(u) ≤ C L ∧ u∈U (u) ≤ C M ∧ (v,v ′ )∈E B v,v ′ ≤ C B
We refer to the totality of these constraints as ( , s, C) which are satisfied by any feasible deployment ( , s) whose cost is C. ■ Symmetry breaking: We add two kinds of symmetry-breaking constraints, which do not change optimal costs. ⋄ Task Symmetry: We add the lexicographic task ordering constraints justified by Theorem .

v∈V v h ,v h+1 ∈U v s(v h ) ≤ s(v h+1 )
where v h denotes the instance of v at the h th position in the order ≪ v . ⋄ Processor Symmetry: Secondly we add fairly standard constraints to exploit the processor symmetry: processor 1 runs task 1, processor 2 runs the lowest index task not running on processor 1, etc. Therefore, let us number all tasks arbitrarily with a unique index: u 1 , u 2 , etc. The processor symmetry breaking is defined by the following constraint:

(u 1 ) = 1 ∧ 2≤i≤|U| (u i ) ≤ max 1≤j<i (u j ) + 1
It can be easily checked that the costs such as latency, number of processor used, buffer size etc. remain unchanged with such restrictions.

.  e x p e r i me nt s

In this section we investigate the performance of the cost-space exploration algorithm using the constraints defined in the previous section. First, we assess the contribution of the symmetry reduction constraints on the execution time and the quality of solutions for a synthetic example. Then we explore the cost space for a split-join graph derived from a real video application. These experiments use version . of the Z Solver [] running on a Linux machine with Intel Core i processor at 1.73 GHz with 4 GB of memory. Finally, we validate the model used to derive the solution by deploying a JPEG decoder on the Tilera platform [] according to the derived schedule. The measured performance is very close to the predicted one.

.. Finding Optimal Latency

We use the split-join graph of Figure . with various values of to explore the effect of the symmetry reduction constraints on the performance of the solver. We start with a single cost version of the problem and perform binary search to find the minimum latency that can be achieved for a fixed number of processors. We solve the same problem using four variations of the constraints: without symmetry reduction, with processor symmetry, with task symmetry and with both. Figure . depicts the computation times for finding the optimal latency as a function of on platforms with 5 and 20 processors. We use time-out per query of 20 minutes, which is much larger than the one minute we typically use because we want to find the exact optimum in order to compare the effects of different symmetry constraints. Scheduling problems are known to be easy when the number of processors approaches the number of tasks. For the difficult case of 5 processors, task symmetry starts dominating beyond 10 tasks and the combination of both gives the best results. It increases the size of graphs whose optimal latency can be found (with no query executing more than  minutes) from = 12 to = 48. Not surprisingly, for 20 processors, the relative importance of processor symmetry grows. In Figure .(b) we see no advantage from the task symmetry, as the problem suffers mainly from processor symmetry.

We perform a similar experiment but now we explore not only for different but also for different number of processors. In this experiment, we fix the number of processors and . Again we perform binary search in order to find the minimal latency that can be achieved. This time we put a time-limit of three minutes on each of the query. We do not change the time-out settings. We perform this experiment for all four settings of symmetry. The results We observe in this experiment the peak levels where the solver takes maximum time when no symmetry breaking is applied to the problem. When the task symmetry constraints are applied to the exploration, we see the reduction in exploration time for larger . However the symmetry due to large number of processors still prevails. When we apply just processor symmetry constraints, we lose the benefit of the task symmetry, but the solver time for larger number of processors is reduced significantly (seen in Figure .(c)). When both task and processor symmetry are applied to the problem, we get a significant reduction, for both and large number of processors, as observed in Figure .(d).

Thus we observe the benefits of task symmetry and processor symmetry constraints for the problem.

.. Processor-Latency Trade-offs

To demonstrate the effect of symmetry reductions on the Pareto front exploration we fix = 30 and seek trade-offs between latency and the number of processors. We use a time budget of one minute per query and a total time budget to  minutes, but is never reached. x (10) 4x

(1)

4

(2) The square points show the unsat points whereas the circle are the sat points. The black curve is the approximation of the Pareto front, connecting all the minimal sat points. Points whose queries took long time to answer are surrounded by a dark halo whose intensity is proportional to the time (the darkest areas are around the timeout points). As one can see from the figure, symmetry constraints reduce significantly the number of time-outs. From additional experiments we noticed that processor symmetry reduces the upper-left part of the curve while task symmetry is useful around the middle. The total exploration time observed is 42 minutes without symmetry, and 16 minutes with both types of symmetry constraints.

1 (2) 1 (2) 1 (2) 4 (2) 1 (1) 1 (1) 4x (1) 1/4x (

.. A Video decoder

Next we perform a 3-dimensional cost exploration for a model of a video decoder taken from []. In our video decoder programming model, a complete video frame can be processed by a repeated execution of the split-join graph shown in Figure .. Every edge is marked with a parallelization factor and data token size in blocks (in parentheses) for buffer size computations. The V LD actor parses the input bitstream, extracting the subsequent macroblocks. The parameter x selects the number of macroblocks processed per one graph iteration. The larger x the more macroblocks can be processed in parallel, but the more difficult it is to generate an optimal schedule. The actors indexed by 'L' process four luminance blocks per macroblock and the actors indexed by 'C' process two chrominance blocks. The Color actor converts the frame into the RGB format. The Fetch actors fetch the reference blocks from the previous frame for motion compensation, done by MC actors. Actor U pscale scales 2 chrominance blocks into 8. The weights w of the channels (in blocks) are depicted in parentheses in the figure. We perform the exploration for x = 5 which yields a task-graph with 122 tasks.

Without any symmetry constraints the solver quickly times out for most queries of interest. Symmetry constraints do not completely eliminate time-outs but reduce them significantly and therefore the quality of the Pareto front approximation is much better, as shown in Figure .. Note that for a sequential implementation (C M = 1) the constraints improve the best buffer size found from 276 to 182 and for the most parallel deployment (C M = 122) they reduce the best latency from 10 K to 7 K and the buffer size from 333 to 229. The Pareto point (14, 333, 62) found without symmetry constraints is strongly dominated by the point (10, 229, 31) found with symmetry breaking. This solution improves the latency and buffer usage by roughly a third while using half of the processors. We believe it is a promising indication of the applicability of our approach and of the potential performance gains in treating the optimization problem globally. [] which is a -core symmetric multi-core platform running at . MHz (described in Section .). Unlike the real execution on the platform, theoretical scheduling problem that we solve is deterministic where task execution times are assumed to be precisely known. The obtained schedule is time-triggered, given in terms of the exact start time function s. In reality, there are variations in execution times and in our implementation we use static order schedules, preserving only the order of task execution on each processor (as described in Section .). This is a common way to generate schedules for task graphs and SDF, see for example []. When task execution times agree with the nominal values used in the optimization problem, this scheduling policy for a non-lazy schedule coincides with s. Unlike the traditional work on dataflow mapping, we support mappings where the writers and readers of the same buffer storage can be spread over more than two different processors. Our experience confirms that this scheduling policy can be implemented with a reasonable amount of additional synchronization between the cores. Note also that when the schedule is compatible with lexicographical task order (justified by Theorem .), the accesses to the channels automatically become FIFO and this facilitates the implementation of cyclic buffers (described in Section .).

The JPEG decoder has three main actors: variable length decoding (V LD ), inverse quantization and inverse discrete cosine transform (I Q/I D CT) combined and color conversion (Color). To measure execution times we run the decoder several times on a single processor and measure the execution time of each actor. To mitigate cache effects, we consider the average execution time rather than worst case, which occurs only in the first execution due to cache misses. We use these average execution times in the model we submit to the solver. We then deploy the decoder on the platform and run it 100 times (again to dampen cache effects). The relation between the average latency (in mi crosecond s) observed experimentally and the Pareto points computed by the SMT solver is depicted below and the deviation is typically smaller than %. We observe in these results, that the predicted latency decreases with the increasing number of processors. However, in practice, we see the minimum latency with four processors and then an increase with the increasing number of processors. This effect is observed due to the fact that we do not model communication in this architecture. When multiple processors use the same FIFO buffers, it causes frequent data movement between them resulting from the cache coherency protocol. This movement of data is difficult to model and causes prediction errors in our experiment. From this we conclude that for better accuracy the communication should be modeled explicitly.

.  c onc lus i ons

In this chapter we discussed the effect of symmetry constraints on the scheduling of splitjoin graphs. We presented results that prove that symmetry breaking constraints accelerates the exploration process for the SMT solver. We proved strength of these constraints first using synthetic benchmarks, and then with real-life applications such as JPEG and Video decoder (with  tasks) by a -dimensional cost-space exploration.

Various approaches to facilitate the task of the solver by additional symmetry breaking constraints have been tried, for example [] for graph coloring or an automated method for discovering graph automorphism [] which can lead to significant improvements [] . However, our deployment problem does not require complex detection of isomorphic subgraphs. Instead we exploit the knowledge about the structure of the task graphs coming from the original split-join graph and not relying in any way on the graph automorphism. We gave a simple proof of the lexicographic for arbitrary nesting, Theorem ., thus improving the results of [], which was restricted to one level of nesting as it was relying on isomorphic sub-graphs.

SMT solvers have been used to solve the scheduling problem previously []. There have been attempts to use constraint programming techniques to solve this problem [, ].

In [] a quantitative model checking engine is developed using a variant of timed automata for combined scheduling and buffer storage optimization of SDF graphs.

In the next chapter, we solve the same scheduling problem for Kalray processor architecture. We observe that the inherently complex nature of the platform, restricts us from solving the problem as a whole. In addition, the explicit communication must be modeled in order to predict the performance of the application correctly. Thus, in addition to scheduling problem, which in that case becomes more complex, we employ the solver for additional optimization problems that concern with planning the communication on the platform. cha pte r 7

Mult i -s tag e s c he duli ng f o r di s t ri b ut e d m e m ry pro c e s s o rs

This chapter introduces the multi-stage approach that we use for scheduling applications on the Kalray processor architecture.

I n previous chapters we observed that on the Tilera platform, with help of the symmetry reduction constraints, the SMT solver was able to handle a scheduling problem with  tasks. Tilera is a, programming-wise, simple shared-memory platform with hardware support of single consistent memory space visible from all cores. Due to this support, the data transfer between the processor cores was managed by the hardware, and transparent to the software. Hence the number of decision variables in the optimization problem was relatively small. In contrast to the Tilera platform, the Kalray platform has a richer and more complex set of mechanisms which are exposed to the user. The processors are grouped into clusters so that processors on the same cluster communicate rapidly via shared memory while tasks that run on different clusters communicate via more expensive means (DMA channels over the NoC) which are under explicit control of the programmer. A modeling and optimization framework that does not reflect communication costs will not be useful for this architecture.

Thus the optimization problem on Kalray has many more decision variables that affect costs such as load-balancing, communication, number of used clusters etc. If all these decision variables as a monolithic optimization problem are presented to the SMT solver, it would result in a very complex set of constraints, practically solvable only for a small number of tasks. Thus in order to be able to schedule larger applications on this architecture, the problem must be split into a few sub-problems. After splitting, the top-level decisions about load-balancing and cluster allocation are made first and later the scheduling inside the clusters is done, combined with mapping to cores and buffer size allocation. This makes the problem solving better tractable.

Our design flow consists of three stages. First we partition the actors into software clusters, then we map them into the clusters of the platform and finally scheduling (of execution and communication) for each cluster. The inter-cluster communication, performed using DMA, must be modeled correctly to obtain good latency prediction. We discuss the constraints in detail and the modeling of communication by inserting new actors and edges representing the data transfer and flow control, to support program execution using limited resources. Finally we present the results of experiments that were performed on the Kalray processor using a number of streaming applications.

 . de s i g n flow

Kalray platform has explicit communication mechanisms which have costs that cannot be ignored and must be taken into account in order to perform a faithful communication modeling. We explain in Section . how inter-task communication is implemented depending on whether or not the two communicating tasks reside on the same cluster. As we shall see, when they are not on the same cluster, we need to augment the split-join/task graphs with additional communication tasks which are based on the DMA cost model introduced in Section .. Moreover, in case of communication channels between two different clusters we need to model synchronization as well. As a result we obtain models that yield constrained optimization problems too large to be solved monolithically and we need to split (as suggested in []) the design flow into stages described below.

■

Software partitioning: We partition the actors into groups (software clusters) with the intention that each software cluster is executed on one (hardware) cluster of the platform. Solutions are evaluated according to three criteria: the number of soft clusters (which determines the number of hardware clusters that will be used for the application), the maximal computational workload over the soft clusters, and the amount of communication between tasks belonging to different clusters. These are conflicting criteria and we provide a set consisting of the best trade-offs provided by our cost exploration procedure.

■

Mapping software to hardware clusters: Due to the toroidal architecture of the interconnect, the distance between pairs of clusters is not uniform and hence, while mapping soft clusters to hard ones we attempt to optimize inter-cluster communication multiplied by the distance. This is a standard optimization problem applied to each of the solution obtained in the previous stage.

■

Mapping and scheduling: In this stage we map the tasks into the cores of their respective clusters and perform scheduling on shared resources: cores that run numerous tasks and DMA channels that serve many software channels. To this end the original split-join and task graphs are modified to reflect tasks associated with DMA transfers as well as synchronization mechanism. The outcome of the process is a set of solutions in terms of schedules, representing different trade-offs between latency, amount of memory used in a cluster and number of clusters. Our run-time environment executes these multi-cluster schedules produced by the SMT solver, where we measure the latency and compare with the value predicted by the model. Below we provide a detailed description of those steps.

.. Software partitioning

In the first step, we partition the actors of the application graph. We follow the partitioning technique of [], adapted here to our application model. We experimentally observed (not reported here) that combined partitioning and placement is a hard problem, which significantly limits the size of problems that can be solved. Thus we decide to keep them as two different sub-problems.

In this step, all the actors of the applications are grouped so that each actor is assigned to a unique group called soft cluster. The workload assigned to a soft cluster is then equal to the product of the execution time of the actor and its repetition count. We calculate the total computation workload allocated to each soft cluster and try to minimize the maximal one.

Every two actors that communicate via a split-join channel incur zero communication cost if they are allocated to the same soft cluster. Otherwise the channel contributes to the communication cost proportionally to the total amount of data communicated through the channel in one graph iteration.

The maximal workload per soft cluster and communication cost are conflicting criteria. If we try to minimize the workload per soft cluster (equally distribute the workload among the soft clusters), we increase the communication cost (communicating actors allocated to different soft clusters). Similarly if we try to reduce the communication cost by assigning more actors to the same soft cluster, the maximum workload in a soft cluster increases. We apply our grid based design-space algorithm to this multi-criteria optimization problem to estimate the Pareto front.

Problem Inputs:

-Application Graph S M = (V M , E M , d, , ) . -Hardware Architecture Model A = (X, , M, D , I, g, ) Output:
-A partition of at most |X| soft clusters represented by a mapping z : V → Z, where Z = {1, 2, 3..., |X|} is a set of soft clusters identified by unique numbers.

M d(v) • c(v) v∈V M d(v) • c(v) C Estimated communication cost  (v,v ′ )∈E M c(v) • w ↑ (v, v ′ ) C Z Number of soft clusters  |X|

Constraints:

Values z(v) for all actors are decision variables that have to be computed by the solver. The partitioning variables have to satisfy the following constraints: ■ Workload Calculation: Let variables (a) signify the total workload assigned to soft cluster a. The workload of an actor can be easily calculated by the execution time times its repetition count. The workload allocated to a soft cluster is the sum of workload of actors allocated to it.

a∈Z (a) = v∈V M : z(v)=a d(v) • c(v)
■ Estimated Communication Cost for soft cluster: Let (v, v ′ ) be the estimated communication cost associated with channel (v, v ′ ). The channel will incur communication cost only if the reader and writer of the channel are allocated to different soft clusters. The estimated communication cost is equal to the amount of data that is being produced (or consumed) on the channel.

(v,v ′ )∈E M : z(v) z(v ′ ) (v, v ′ ) = c(v) • w ↑ v,v ′ = c(v ′ ) • w ↓ v,v ′
If the reader v and the writer v ′ are in the same soft cluster, then the communication cost for them is zero.

(v,v ′ )∈E M : z(v)=z(v ′ ) (v, v ′ ) = 0
The last three constraints simply define the three cost criteria.

■

Partition Cost: This constraint defines the partitioning cost of the solution in terms of number of soft clusters. The number of soft clusters to which the actors are assigned should be less than the cost C Z .

v∈V M z(v) ≤ C Z ■ Total Estimated Communication Cost:
The total communication cost is subject to cost constraint and is equal to the sum of communication cost of all the channels.

(v,v ′ )∈E M (v, v ′ ) ≤ C ■ Workload Cost: C is the maximum workload. a∈Z (a) ≤ C
The solution expresses the assignment of actors to their respective soft clusters. The communication cost and the workload incurred by each soft cluster can be trivially derived from it.

Our cost exploration algorithm produces an approximation of a three-dimensional Pareto front of solutions, and each of the discovered solutions is then subject to subsequent steps of placement and scheduling.

.. Mapping software to hardware cluster

The placement step allocates a unique physical cluster to every soft cluster. In this step, the communication cost is based on the distance between the clusters. We do a one-dimensional minimization of the total communication cost by a binary search method.

Problem Inputs:

-Application Graph S M . -Hardware Architecture Model A.

-Partitioning scheme z.

Output:

x : Z → X : represents assignment of a soft cluster to platform cluster where we assume that clusters are identified by positive numbers: X = { , , ..., |X|}

Costs and bounds:

Bounds Symbol Cost Description Lower Upper C Total communication cost  (v,v ′ )∈E M : z(v) z(v ′ ) c(v) • w ↑ v,v ′ • max

Constraints:

The values for decision variables {x(a) : a ∈ Z} for soft clusters computed by the solver at this step should satisfy the following constraints.

■ Allocation of soft cluster to platform cluster: We assign the soft cluster a to a cluster from set X of clusters available on the platform. The solution of the placement step expresses a mapping of each soft cluster to a unique cluster on the platform.

(a, b) = (v,v ′ )∈E M : z(v)=a z(v ′ )=b (v, v ′ ) • x(a)
cluster 0 A 0 A 1 F st0 F st1 pos w 0 st w 0 rs w 0 pos w 1 st w 1 rs w 1 D MA 0 D MA 1    cluster 1 B 0 pos r 0 st r 0 pos r 1 st r 1 D MA 0 D MA 1     Figure . -Working of inter-cluster FIFO  . i nt e r-c

lus t e r fi fo

Before we further describe the design flow, we need to explain how we implement communication between tasks that reside in different clusters. The basic ideas have been already introduced in Section ., whereas here we give more implementation details by means of an illustrative example. We implement an inter-cluster FIFO which transparently handles the data transfer and synchronization between the readers and writers of the FIFO. We follow the same example as in subsection .. where we assumed a simpler, intra-cluster case. Suppose in a split-join graph, where A and B are connected actors with parameters = 1/2, c(A) = 4, c(B) = 2 ↑ AB = 1, ↓ AB = 2, and m AB = 2. Also suppose that z(A) z(B), so they have to communicate using a DMA channel. Let us recall that the FIFO buffer is split to writer and reader sub-buffers. Figure . demonstrates such a scenario, where A 0 , A 1 , F st 0 etc. are the tasks running on the processors of the writer cluster (cluster 0 ). Here F st represents a special task which is needed to detect the completion of DMA transfer in the writer cluster. It is explained in detail later. The token data and token status entries in the FIFO buffer located in the local shared memory of the writer cluster is shown as pos w 0 , st w 0 etc. The corresponding data structures at the reader cluster (cluster 1 ) are shown as pos r 0 , st r 0 . The writer cluster has an additional status denoted by rs w 0 which indicates FIFO status at reader cluster for this position. The following steps illustrate how the inter-cluster communication takes place using the FIFO.

■

Step : Task A 0 checks for the status st w 0 in the FIFO if the token status at position zero (pos w 0 ) indicates an empty token. If the token status is 'e'-empty, then it marks the token as busy and starts to produce data in this position of the FIFO. Similarly task A 1 checks for status st w 1 and starts to produce data in position  of the FIFO. A point to note here is that A 0 and A 1 are not necessarily synchronized. They can execute on the same or different processors. Flags rs w 0 and rs w 1 are initialized empty before the execution of the schedules indicating free space for tokens on cluster 1 .

■

Step : After task A 0 finishes, the position  of the FIFO contains data and updated status, 'd' -contains data, the task A 0 starts a DMA transfer of token data and its status together, but not before the remote status rs w 0 indicates an empty token space at remote cluster, to move the data in position  and its status (pos w 0 and st w 0 in Figure

■

Step : The DMA transfer copies the data from pos w 0 and st w 0 to the reader cluster pos r 0 and st r 0 respectively. When the DMA transfers initiated by tasks A 0 and A 1 are finished, task B 0 which is continuously polling on the status at position  (st r 0 ) and position  (st r 1 ), can start its execution owing to the availability of the data.

■

Step : Task F st0 , executing in the same cluster as task A 0 , is continuously polling on the status of DMA transfer started by task A 0 . Once it detects completion of this transfer, it marks the status of the position  (st w 0 ) as empty and available for re-use. Similarly task F st1 marks st w 1 when it is available. Note that step  and step  may execute concurrently.

■

Step : After task B 0 finishes execution, its marks the local status st r 0 and st r 1 of token as free. Task B 0 initiates a DMA transfer explicitly, which copies st r 0 to rs w 0 and st r 1 to rs w 1 .

After these steps, similarly tasks A 2 , A 3 and B 1 can execute on same or different processors, repeating the same sequence of communication and synchronization operations as A 0 , A 1 and B 0 respectively. The advantage of using such FIFO is that it decouples the two clusters, meaning that the writer cluster can immediately re-use the FIFO buffers when the DMA transfer has finished transferring the data to the reader cluster without waiting for reader to finish.

 . mode li ng c ommuni c at i on

With the background of inter-cluster FIFO we continue discussion of design flow steps. In the scheduling step we perform a joint scheduling of the computation tasks (the tasks of the application graph) and the communication tasks (the DMA transfers). Our approach to define the scheduling problem is to first describe the model that reflects both the computation and the communication in a many-core system and then to explain how this model is encoded in terms of constraints. The model is obtained from a series of graph transformations, which gradually changes the application graph into a final schedule graph which models all the deployment decisions.

In this section we focus on modeling the communication, and assume that we are given a ready partitioning solution (from the partitioning step) and the buffer allocation, which is part of the combined solution computed at the scheduling step (described later).

.. Partition-Aware Graph

For defining the graph transformations, in particular for adding new actors, it is convenient to introduce notation v : [d(v), z(v)], which represents an actor v with delay d(v) and soft cluster number z(v). Similarly, e : [ (e), (e), m(e)] represents an edge e with parallelization factor (e), token size (e) and marking m(e). When the latter two parameters are omitted, the default values are considered zero. Note that if is zero, the given edge models an execution order constraint and does not have a memory buffer for communication.

We assume to have a ready partitioning solution z(v), calculated earlier in the design flow. In order to model the communication delay, we need to introduce additional actors in the split-join graph, representing the DMA transfers.

Recall from Equation . that a DMA transfer consists of two phases: DMA transfer initialization and network communication. We model these two phases of DMA transfer by two actors : I wr and G wr . In this case the channel (A, B) is split into writer and reader sub-buffers. The FIFO buffers that are allocated at the writer and reader side are modeled by e wt and e rt respectively. The working of inter-cluster FIFO was explained in detail in the previous section.

Edge e wt ( ê) models the writer sub-buffer; = 1 indicating that one writer instance is followed by exactly one data transfer (where and w ↑ represents the data size (in bytes) of one token and the total data size of tokens produced by one writer instance respectively. Refer to Section ..), whereas (e wt ) = w ↑ ( ê) indicates that the ↑ tokens produced by an instance of the writer actor is encapsulated into one token. Edge e wn ( ê) reflects the sequential order between the two DMA phases. Channel e rt ( ê) corresponds to the reader sub-buffer. It has the same parameters as the original edge ê.

Let E M Z denote the set of inter-cluster channels crossing the partition boundaries and E M Z its complement. Formally,

E M Z = {(v, v ′ ) ∈ E M | z(v) z(v ′ )} E M Z = E M \ E M Z
Definition  (Partition-Aware Graph) -A partition-aware graph S P = (V P , E P , d, , ) is a splitjoin graph obtained by replacement of application graph edges E M Z by a sub-graph with new actors and edges as defined below.

The delay for the newly added actors is the DMA initialization time I and the network sending time g • w ↑ ( ê).

V P = V M ∪ {I wr ( ê), G wr ( ê) | ê = (v, v ′ ) ∈ E M Z } Actors Parameters Predecessor Successor I wr ( ê) [I, z(v)] v G wr ( ê) G wr ( ê) [g • w ↑ ( ê), z(v)] I wr ( ê) v ′
The edges of partition-aware are given by- The partition-aware graph implicitly models the application execution on the platform with unbounded resources, such as buffer memory, cores and DMA channels. The remaining graph transformations model the synchronization on bounded resources.

E P = E M Z ∪ {e wt ( ê), e wn ( ê), e rt ( ê) | ê = (v, v ′ ) ∈ E M Z }

.. Buffer Aware Graph

The next transformation after obtaining a partition-aware graph has for the purpose to model the bounded buffer capacity allocated to the channels. Note that we do not allocate buffers for the channels e wn , as they model the ordering of the actors. Let E P ′ denote the the subset of all edges in E P except for e wn edges.

Definition  (Buffer Allocation) -b : E P ′ → N + defines the bounded capacity assigned to the channels of the partition-aware graph. It is part of the solution of the combined scheduling and buffer allocation problem. d,,,m) obtained from the partition-aware graph by adding marked channels that model the allocated buffer capacity and new actors that model the DMA polling and flow control.

Definition  (Buffer Aware Graph) -is a cyclic marked split-join graph B = (V B , E B ,
In this graph, for each channel ê ∈ E P ′ in we add a new backward channel -in the opposite direction, marked with the buffer allocation b( ê), signaling the free space availability in the channel. If ê is an intra-cluster channel then the backward channel is the inversion of ê, with inversely proportional parallelization factor, see Figure .. Recall that the marking represents the initial number of tokens in the channel. In the backward channel the marking b( ê) indicates the free space that is available initially i.e. the total buffer space. At every execution, the writer takes ↑ tokens of space and produces ↑ tokens of data, and the reader takes ↓ tokens of data and produces ↓ tokens of space.

precedence dependency (data) backward dependency (space) processor blocked

A 0 F st0 A 1 A 2 I wr0 I wr1 I wr2 G wr0 G wr1 I rd0 G rd0 B 0 Time P roc 1 D MA 1 P roc 2 D MA 2 Figure . -Double buffering example schedule
If the channel is an inter-cluster channel, involving DMA, then we model the free space of the writer sub-buffer, e wt and the reader sub-buffer, e rt by separate backward channels. To model the communication we also add additional actors, see Figure ..

Consider the writer sub-buffer e wt . The direct reader of this sub-buffer is the DMA transfer actor. The space in this sub-buffer becomes available when the DMA transfer is complete. Detecting the transfer completion takes non-negligible processor time denoted by , modeled by a new actor F st . This actor produces the space tokens on the backward channel of e wt . The reader sub-buffer e rt is written by the DMA transfer actor, which copies the data from e wt to e rt . Recall that for flow control purposes, the status of the tokens of the reader sub-buffer have to be communicated back to the writer. The DMA transfer required for the flow control is modeled by I rd and G rd , and it is actually the flow control itself that is represented by the backward channel of e rt . The number of tokens on this channel represents the number of empty rs w i status records (see Figure .) which indicate the empty (i.e. free) state of the token positions.

Let us consider an example to illustrate the working of our model for inter-cluster FIFO. We assume that two actors A and B are connected with a neutral channel ( = 1) and assigned to different clusters. Suppose that we use well-known double-buffering approach, such that b(e wt (A, B)) = b(e rt (A, B)) = 2 tokens. Initially, the available space in both buffers is . Let us simulate the execution of the model in

■

When G wr0 finishes, B 0 receives the input data tokens. At the end it releases the space occupied by these tokens and triggers a DMA transfer to update the writer accordingly. This transfer is modeled by I rd0 and G rd0 .

■

Before A 2 can execute, the task F st0 must finish, which releases the necessary free space tokens in the backward channel. This concludes a complete flow-control cycle between the writer and reader. We formalize addition of the new actors and channels as:

V B = V P ∪ {F st ( ê), I rd ( ê), G rd ( ê) | ê = (v, v ′ ) ∈ E M Z } Actors Parameters Predecessor Successor F st ( ê) [ , z(v)] G wr ( ê) v I rd ( ê) [I, z(v ′ )] v ′ G rd ( ê) G rd ( ê) [ ↓ ( ê) • 0 • g, z(v ′ )] I rd ( ê) I wr ( ê)
The edges of partition-aware are given by-The delay of network sending node ↓ • 0 • g corresponds to the delay of sending 0 bytes of status record for all ↓ tokens read in the channel, where 0 depends on the implementation. E B = E P ∪ {e ws ( ê), e wb ( ê), e rs ( ê), e rn ( ê), e rb ( ê), e be ( ê

) | ê = (v, v ′ ) ∈ E M Z } ∪ {e be ( ê) : [ -1 ( ê), 0, b( ê)] | ê = (v, v ′ ) ∈ E M Z }

Edge

Parameters Edge-writer Edge-reader e ws ( ê) [1] I wr ( ê)

F st ( ê) e wb ( ê) [1, 0, b(e wt ( ê))] F st ( ê) v e rs ( ê) [1] v ′ I rd ( ê) e rn ( ê) [1] I rd ( ê) G rd ( ê) e rb ( ê) [ -1 ( ê), 0, b(e rt ( ê))] G rd ( ê) I wr ( ê)
The important point to remember is that the buffer allocation b for channels is decided by the SMT solver and the corresponding solver constraints are described in subsection ...

.. Communication Aware Graph

In our implementation, the compute core remains busy until the completion of the DMA initialization tasks (I wr or I rd ), started after the completion of the corresponding computation actor (writer or reader). Moreover, if the computation actor instance starts multiple DMA transfers (as a writer/reader of multiple channels), then none of these DMA transfers can start until the initialization of the previous transfer has finished. This restriction can be modeled by adding extra edges between the actors modeling the DMA initialization phase, to enforce a sequential execution order in the schedule. ,,m) is obtained from the buffer aware graph S B by adding the edges to model the ordering of the DMA transfers with regard of their transfer initialization phase.

Definition  (Communication Aware Graph) -Communication Aware Graph S K = (V K , E K , d,
The set of actors of the communication aware graph is same as in the buffer aware graph V K = V B . To define the new edges, we first introduce function I(v), representing an ordered set of DMA transfer initialization actors (I wr or I rd ) connected to the output of given actor v, i.e.

I(v) = {v ′ | (v, v ′ ) ∈ E B ∧ ∃ ê ∈ E M : v ′ = I wr ( ê) ∨ v ′ = I rd ( ê)} The ordering (I 1 , I 2 , . . . | I k ∈ I(v)
) is selected arbitrarily, but it must be the same in the model and the implementation. Then, we have:

E K = E B ∪ {(I i , I i+1 ) : [1] | I i , I i+1 ∈ I(v), v ∈ V B }
The final transformation to model the communication is the derivation of the task graph T K = (U K , E K , , ) from the communication aware split-join graph S K . This is done according to Definition , of deriving the task graph from a split-join graph. In addition we require that the task graph inherit the partitioning from the split-join graph: ∀v h ∈ U.z(v h ) = z(v). This derived task graph is called Preliminary schedule graph.

Having shown the model for communication, we proceed to the scheduling model in the next section.

 . s c h e duli ng

The schedule graph represents a final solution which can be deployed on the platform. It consists of processor allocation and ordering scheme for tasks, buffer sizes for different channels, and the start times of the tasks. It is described below.

.. Schedule Graph

The schedule graph T S = (U S , E S , , ) is obtained from preliminary schedule graph T K by adding the mutual exclusion edges, according to the given schedule s and intra-cluster mapping , where: ■ : U S → N ≥0 maps every task to a core (for computation tasks) or a DMA channel (for transfer tasks); ■ s : U S → R + associates each task with a start time. Like buffer allocation, b, the schedule and the mapping should be computed by the solver during the scheduling step of the design flow, as discussed later.

Let us recall and introduce some notations. C+ is the set of computation tasks connected to DMA transfers:

U S C+ = {u ∈ U S C | I (u) ∅} ■ U S
C∅ is the set of the remaining computation tasks, i.e. those with no DMA transfer tasks at the output. Note that not all tasks introduced for communication are transfer tasks, as the tasks F st (see Figure .) are computation tasks, as they are executed on the compute cores.

Due to a limited number of the compute cores and DMA channels, multiple tasks are mapped to the same core or channel, and their execution intervals should not overlap in time. This requirement is modeled by adding mutual exclusion edges. The edges of the schedule graph are obtained from:

E S = E K ∪ E T ∪ E C∅ ∪ E C+
E T are the mutual exclusion edges for the transfer tasks mapped at the same DMA channel.

E T = {(u, u ′ ) : [1] | u, u ′ ∈ U S T , z(u) = z(u ′ ), (u) = (u ′ ), s(u ′ ) ≥ s(u)
} Similarly, we insert an edge for the computation tasks without any DMA task at the output, allocated on the same core.

E C∅ = {(u, u ′ ) : [1] | u ∈ U S C∅ , u ′ ∈ U S C , z(u) = z(u ′ ), (u) = (u ′ ), s(u ′ ) ≥ s(u)}
Finally, when the earlier task u starts some DMA transfers upon its completion, let I max (u) represent the last transfer in the ordered set (I 1 (u), I 2 (u), . . . ). The compute core becomes available to a later task u ′ after the last transfer has finished:

E C+ = {(I max (u), u ′ ) : [1] | u ∈ U S C+ , u ′ ∈ U S C , z(u) = z(u ′ ), (u) = (u ′ ), s(u ′ ) ≥ s(u)} ..

 Mapping and scheduling using SMT

In the previous sections, we have described a sequence of rules to derive a schedule graph, which can model the effect of a joint scheduling/buffering solution to be calculated by the SMT solver. The solver constraints for this problem are therefore directly generated from the schedule graph. Below we present the corresponding definition of the optimization problem solved at the scheduling step of the design flow.

Problem Inputs:

-partition-aware graph S P -hardware architecture model A -partitioning solution z Output: -(T S , b, , s), where T S = (U S , E S , , ) is the schedule graph obtained from S P , the partitionaware graph by adding extra actors and edges based on buffering b, mapping and scheduling s. According to the calculated buffer allocation b, mapping , and schedule s, which are also part of the solution.

-: U S → N ≥0 maps every task to a processor or DMA channel inside its soft cluster s : U S → R ≥0 associates each task with a start time b : E P ′ → N + associates each channel in the partition-aware graph to a buffer size measured in tokens.

Costs and bounds: Bounds

Symbol

Cost Description Lower Upper

C B max. communication memory per cluster mi n z (v,v ′ )∈E P ′ : z(v ′ )=z w ↑ v,v ′ + w ↓ v,v ′ -gcd(w ↑ v,v ′ , w ↓ v,v ′ ) max z (v,v ′ )∈E P ′ : z(v ′ )=z c(v) • w ↑ v,v ′ C L schedule latency longest path delay in task graph derived from S P v∈V P d(v) • c(v)
Constraints:

■ Application and Schedule: The schedule should respect all the dependencies, including the application dependencies, bounded buffer space, DMA transfer ordering, and mutual exclusion, all represented by edges in the schedule graph:

(u,u ′ )∈ E S (b,s, ) s(u ′ ) ≥ s(u) + (u)
As we explicitly indicate here, the set of schedule dependencies is a function of the problem solution. However, the SMT solvers require a static set of constraints. Therefore, observing that the set U S is static we rewrite the constraints as:

u,u ′ ∈U S S (u, u ′ , , s, b) =⇒ s(u ′ ) ≥ s(u) + (u)
where S is a predicate that determines whether (u, u ′ ) ∈ E.

For the mutual exclusion edges, this predicate can be trivially obtained from the definition of sets E , and, in the case of no DMA (i.e. single cluster) the result is equivalent to Equation ..

■

Communication buffer: The constraints for modeling the communication buffer are included in the above constraints through the backward edges. Predicate for these edges can be obtained from predicate (v, v ′ , h, h ′ ) in Definition , by substituting the buffer allocation to marking m. However, in practice we do not include these constraints, instead reuse the buffer constraints explained in Section .. For the intra-cluster channels, we use exactly the same constraints as there. In the case of inter-cluster channels we take into account that for the writer sub-buffer the free space is produced by F st actor. Therefore, it is this actor, instead of the direct reader of the channel, I wr , who plays the reader role in the buffer constraints for the edge that models the writer sub-buffer. Similarly for reader sub-buffer, the data is produced by G wr actor and free space is produced by G rd actor instead of the intra-cluster channel reader..

■

Resource constraints: These constraints express bounded number of DMA channels and cores per cluster.

u∈U S T (u) < |D | ∧ u∈U S C (u) < |M|
Bounded buffer memory per cluster:

a∈Z e=(v,v ′ )∈E P ′ : z(v ′ )=a b(e) • (e) ≤ C B ■
Latency constraint: The schedule must observe the latency cost constraint. We also require that the initialization and network phases of DMA transfers follow immediately one after the other and on the same DMA channel:

ê=(v,v ′ )∈E M Z 0≤h<c(v) s(I wr h ( ê)) + I = s(G wr h ( ê))) ∧ (I wr h ( ê)) = (G wr h ( ê))) ê=(v,v ′ )∈E M Z 0≤h ′ <c(v ′ ) s(I rd h ′ ( ê)) + I = s(G rd h ′ ( ê))) ∧ (I rd h ′ ( ê)) = (G rd h ′ ( ê)))
where h and h ′ correspond to the index of task instance of channel writer and channel reader.

■ Symmetry Constraints: Last but not the least, we add task and processor symmetry breaking constraints (explained in Section .), which improve the performance of the constraint solvers. For feasible costs and tractable problem sizes the solver produces the scheduling problem solutions, which include the mapping of tasks to the compute cores and DMA channels, as well as task start times and channel buffer allocations.

 . s c h e dule i mp r ove me nt

The schedule generated by the solver is not necessarily optimal in terms of latency and processor usage. For example, even if a task is enabled ( i.e. it has all input data and output buffer space and the core at its disposal), the solver might schedule it for later execution.

Similarly, even if a processor is idle when the task should start, the solver might allocate a new processor to run a task. This happens because when the exploration algorithm makes queries at the points lying away from the Pareto front, the solver might produce a schedule with under-utilization of resources like processors or time without violating the cost constraints. Such a schedule must be improved in terms of latency and number of processors used, to efficiently utilize the resources. If such improvement constraints are included in our query, it complicates the problem and makes it harder for the solver to produce a solution. Hence this improvement must be done separately.

To summarize, the solutions obtained by the solver are correct but often not tight, in terms of latency and processing resources. In two steps: () we improve the latency and () we improve the mapping.

.. Improvement of latency

According to task graph scheduling theory, the schedule constraints imply that each task can be scheduled in [ASAP(u), ALAP(u)] interval (see e.g. []), where ASAP and ALAP stand for as soon as possible and as late as possible start time for the given mapping and resource access ordering. They are obtained by longest-delay path algorithms in the schedule graph. The solver typically computes start times s(u) somewhere inside this interval, whereas using ASAP(u) would allow tightening the latency constraint and it would directly correspond to our 'non-lazy' (self-timed) online scheduling policy.

To realize this improvement, upon a "satisfiable" response from the SMT solver query we extract the solver-computed mapping, the task execution order per core and DMA channel and the buffer allocation per edge and calculate the corresponding schedule graph. In the schedule graph, we set all start times according to s(u) = ASAP(u) and update the latency cost C L attributed to the obtained solution to the completion time of the latest task.

.. Processor Optimal Schedule

When we acquire a non-lazy schedule from the above procedure, we fix the task start-times, and apply the left edge algorithm  to recompute the mapping (u). As a result, we obtain an improved scheduling solution with a compact schedule and mapping.

The tasks are assigned to processors in non-decreasing start time order. The processor usage is optimized such that processors are assigned an index in increasing order inside a cluster starting from zero. The processor with higher index is assigned only when the processor of lower index has an overlapping task with the current task which is to be assigned.

This optimization of schedule helps the cost-space exploration process, as the loose points in the solution provided by the solver are tightened with the above mentioned process. As tighter solutions are obtained, it reduces number of queries in the exploration.

 . e x p e r i me nt s

In this section we give an empiric evaluation of the validity of our many-core scheduling approach, using a set of application benchmarks. We run our design flow in order to approximate the Pareto points of feasible schedules. We execute every solution obtained on the real hardware of the MPPA platform and compare its real performance to the one predicted by our scheduling solution. Our application benchmarks consist of the JPEG Image Decoder, and a subset of StreamIt benchmarks []. The characteristics of the benchmarks are summarized in Table .. The exploration experiments use version . of the Z Solver [] running on a . A classical algorithm used in design automation for this purpose [].

P s0       P s1       P s2       P s3      
Linux machine with Intel Core i processor at . GHz with  GB of memory. We use the JPEG decoder as an example to illustrate the experiments done for each benchmark in detail.

For the partitioning step, the exploration is done in a -dimensional cost space: (C , C , C Z ) i.e. the maximal workload per soft cluster, communication cost estimate and number of soft clusters. There is a trade-off between these costs, and our grid-based exploration strategy, finds four Pareto points as shown in Table 

..
At the placement step, the soft clusters are mapped to neighbor clusters. We perform a binary search in order to find the minimal feasible total communication cost.

In the scheduling step, the exploration is done for each partitioning solution in a dimensional space (C L , C B ), i.e. latency and maximal buffer size per soft cluster. We plot all four Pareto fronts in Figure .. We observe some Pareto fronts cross because they differ in the number of available soft clusters, which leads to the following effect. On the top-left side of the cost diagram a large buffer memory per soft cluster is allowed. Therefore, even a single soft cluster solution has enough buffer memory to minimize the latency, and it dominates the solutions with more soft clusters because it does not use DMA transfers. On the bottom-right side, the parallelism available to the solutions with less soft cluster count is restricted by small amount of buffer memory, whereas adding more soft clusters results in a larger total buffer memory, allowing to run more tasks in parallel and get a better latency. Therefore, a larger number of clusters may yield a solution with a smaller latency, even despite the larger DMA cost. The combination of these individual Pareto fronts can be pruned, retaining only the overall Pareto solutions. These solutions will be a mix of multi-cluster and single-cluster ones, showing interesting deployment trade-offs. This proves that it is not a trivial problem to select the number of clusters, and we observe the true multi-criteria nature of the problem.  shows the results obtained for the scheduling solutions when executed on the Kalray platform. We plot the minimum and maximum observed latency on the platform as well as the predicted one. The maximum error that was observed in this configuration, as well as for the entire JPEG experiment, was %.

Figure . shows the summary of results obtained for all benchmarks. Firstly, we have plotted the total number of scheduling solutions obtained for an application benchmark, adding up those obtained for different partitioning solutions. Note that this solution number depends on the amount of parallelism available in the application as well as on the structure of the application graph. For example, for an application graph as shown in Figure . there is no latency-buffer size trade-off irrespective of the parallelism factor , the buffer size required is tokens for each channel, the application cannot execute with less and will not improve with more.

Secondly, we plot the the maximum error of the predicted latency vs the one measured on the platform for  iterations. The overall maximum error (%) was observed in the In the schedule that resulted in this error we observed that there were  simultaneous DMA transfers between a pair of clusters, which contributed to network contention and hence a less accurate latency prediction. However, we believe that another factor contributing to inaccuracy is the contention on the shared memory bus inside the clusters. We also believe that the error could be larger if we ran with caches enabled.

.  c onc lus i ons

In this chapter, we presented a multi-stage approach which was used to schedule split-join application models on the Kalray processor architecture. The major contribution in this work is an accurate modeling of network communication with buffering that supports multiple parallel writers and readers per channel, as well as network DMA transfers and flow control. We validate the framework using a dozen of real applications from the well-known StreamIt set of benchmarks for signal-processing For the optimal schedules generated for benchmarks, we performed latency measurements on real many-core hardware. Despite the fact that we ignored the network contention in scheduling, the maximal error of scheduler's timing estimation was only % and typically in the range of -%. We obtain this level of precision by exploiting non-cached shared local memory system at the cluster level. The maximal benchmark size we could handle had  tasks, where the solver's performance started to saturate. This chapter borrows some ideas from previous work. Implementation-aware graphs, a formalism similar to our schedule graphs were proposed in [] and we extend this work by a more realistic modeling which consider processor blocking and verify it on a real platform. A DMA model similar to ours is considered in [] who also use an SMT solver to compute schedules, but only for uni-processor systems. The work of [] considers the network routing and pipelined scheduling (which is outside the scope of this thesis) but they do not combine their the network communication model with parallel scheduling in shared-memory clusters.

S o r t D c t  D c t  D c t  D c t  D c t  D c t  D c t  D c t  D c t C o a r s e D c t F i n e C o m p . c o u n t M a t r i x M u l t . F f t 0
Data-parallel applications apply uniform computations on large amount of data. Due to large size, the input and output data cannot be placed in relatively small local memory. Thus the data must be processed in small parts. The amount of the data that should be fetched in the local memory has an impact on performance of the applications and is an optimization problem that we discuss in the next chapter. D ata parallel applications, like filtering in image processing, apply the same computation to different blocks of data. Such type of application benefit from available data parallelism when executed concurrently on multi-core platforms. The processors connected to main memory with DMA have to explicitly fetch the data into local memory from the main memory, on which the computation should be performed and finally the results written back in main memory. However the choice of the amount of data to be brought to the local memory in each DMA transfer, which is obviously limited by the size of local memory, is a design choice to be made by the programmer.

In this chapter we discuss influence of DMA transfer granularity and access pattern by DMA on performance of data-parallel applications. We start by discussing the data parallelism in applications and how software pipelining helps to achieve the overlap between data transfer and computation. With this software pipelining into consideration, the non-trivial choice of granularity of DMA transfer is described in detail. Further, different mechanisms to exchange the shared data between different processors and its effect on the optimal granularity are discussed. We conclude this chapter with experiments performed on the Cell processor architecture.

.  data -pa r a lle l a p pli c at i ons

There are different types of parallelism available in parallel applications, as discussed in Section .. A class of applications known as embarrassingly parallel, performs uniform computation on a large amount of data blocks. In this chapter, we focus on such applications, which have a regular memory access pattern that can be modeled for static optimization. Our application structure consists of computation Y = f (X), where X and Y are large input and output arrays respectively. For simplicity, we assume that both have the same dimensions. The computation f () is applied uniformly to every element of this array.

If the input (and the output) array is one-dimensional, then each element of this array can be computed as Y(i) = f (X(i)), where i represents the position of an element in the array. However,

 n n k /  k /  Figure . -Neighborhood pattern of size k
in some applications like filtering in image processing, the input and output data arrays are two dimensional instead of one. Such a computation can be represented as

Y(i 1 , i 2 ) = f (X(i 1 , i 2 )),
where both the input and output arrays are two-dimensional. In such cases, the position of element in the array must be determined by two indices i 1 and i 2 . Applications compute data for more than two dimensions, however we restrict ourselves to two dimensions for simplicity.

Given such a scenario, the computations can be further classified as:

■ independent computations: This type of computations does not require any surrounding data, but the one which is being processed.

Y(i) = f (X(i)) and Y(i 1 , i 2 ) = f (X(i 1 , i 2 )
) are examples of independent computations.

■ overlapped data computations: In this case, the computation requires surrounding block of data to produce output. For example, in the case of two dimensional data,

Y(i 1 , i 2 ) = f (V(i 1 , i 2 )) is an example of overlapped computation, where V(i 1 , i 2 ) is a (k + 1) × (k + 1) matrix  , V(i 1 , i 2 ) = X(j 1 , j 2 ) : (i 1 -k/2 ≤ j 1 ≤ i 1 + k/2) (i 2 -k/2 ≤ j 2 ≤ i 2 + k/2) (.)
We refer to V as the shared data required for the computation. We assume a symmetric window of size k around the data block as shown in Figure .. In practice it is possible that algorithms require shared data only from one side around the data block and we consider it later.

.. Buffering schemes

Semantically, a one-dimensional data-parallel algorithm can be specified by the following sequential program.

Algorithm  Sequential Data Processing for i:= to n do Y[i]:=f(X[i]) end for
However, for the processors with hierarchical memory, the data must be brought from the main memory, into a memory closer to the processor. Typically the entire input and output array does not fit into the local memory and one needs to split the data into parts for processing.

. for convenience k is assumed an even integer.

In such case, the processor will have to prefetch the data (dma_get), then process it and write back (dma_put) the results to the output, as shown in Algorithm . The meaning of e i n and e out variables used is that there is an identifier to check completion of dma_get or dma_put.

Algorithm  Single Buffering for i:= to m- do dma_get (in_buf,X[i • s + 1 .. (i + 1) • s],e in );
⊲ fetch in-buffer dma_wait (e in ); for j:= to s do

⊲ compute out_buf[j]= f(in_buf[j]); end for dma_put (out_buf,Y[i • s + 1 .. (i + 1) • s], e out );
⊲ write out-buffer dma_wait (e out ); end for However if we implement this single buffering algorithm, the processor remains idle when the input and output arrays are being transferred. To improve this situation double buffering is employed, where the input and the output buffer are split into two parts. While the processor performs computation on first part of the buffer, the transfer is carried on the other part and vice-versa. This is done to overlap the computation and communication.

Algorithm  Double Buffering d:=; dma_get (in_buf[],X[..s],e in []); ⊲ first read for i:= to m- do if i < m -1 then dma_get (in_buf[d⊕],X[(i + 1) • s + 1..(i + 2) • s],e in [d⊕]); ⊲ fetch next end if dma_wait (e in [d]); ⊲ wait for current input for j:= to s do ⊲ process current out_buf[d][j]= f(in_buf[d][j]); end for if i > 0 then dma_wait (e out [d⊕ ]); ⊲ wait for previous write end if dma_put (out_buf[d], Y[i) • s + 1..(i + 1) • s], e out [d]); ⊲ write current d:=(d⊕ );
⊲ toggle buffer end for dma_wait (e out [d⊕]);

⊲ wait for last write to complete Algorithm  defines a software pipeline with  stages: input transfer, computation and output transfer. In this algorithm, the processor issues a fetch for a block of data and proceeds to the computation of previously fetched data. After finishing the computation it issues a write of the computed results and completes the iteration. Fetching the first block and waiting for the write of the last block are respectively the beginning (prologue) and the end of the pipeline (epilogue). The input data to be processed must be distributed among the available processors for parallel processing. Depending on the number of dimensions, the data can be split in various ways. We discuss the splitting and distribution of one-dimensional and two-dimensional data below.

... One-dimensional data

In the case of one dimensional data without any shared data computations, it is simple to cut the input array uniformly into parts equal to the number of processors and allocate one part per processor. This allocation can be done in two types : (a) contiguous : where the adjacent blocks j and j + 1 are allocated to the same processor or (b) periodic where the blocks j and j + p are allocated to the same processor, where p is the number of processors. Figure ., shows both schemes for four processors P 0 to P 3 . These solutions are equivalent in the amount of distribution of data.

In the case of one dimensional data, when there is need for shared data for computation, periodic allocation can be beneficial as the processors can exchange the data amongst themselves. In the case of contiguous allocation the processor has to fetch the computation data as well as shared data into its local memory to perform the processing, thus increasing the granularity of data transfer. Contiguous allocation is favorable when processor stores the shared data locally at the end of current iteration and reuses it for the next. We discuss this further in Section ..

... Two-dimensional data

Two dimensional data can be divided equally into various shapes as illustrated in Figure .. Again such solutions are equivalent in amount of data that is being transferred from the main memory. However, depending on the shape, the data maybe contiguously transferred in one DMA transfer or by using expensive strided DMA (additional delay due to stride is described in Section .).

In the case of shared data for two-dimensional data, the geometry of the data partitioning scheme determines the amount of data that will be shared between the processors. For example, as shown in Figure . we see that for completely horizontal or vertical blocks of the same area, the amount of shared data, is greater than for square shaped blocks. .  op t i ma l g r a nula r i t y for data t r a ns fe r s For one-dimensional or two-dimensional data, finding the optimal granularity for the data transfer, that minimizes the total execution time of the application is a non-trivial problem. In order to derive the optimal granularity, the performance of the pipelined execution of the double buffering algorithm must be analyzed. In this section we first analyze the performance of this algorithm for different size and shapes for independent computations, without any shared data.

s 2 = 4 s 1 = 1 s 2 = 2 s 1 = 2 s 1 = 4 s 2 = 1 (s 1 , s 2 ) = (1, 4) (s 1 , s 2 ) = (2, 2) (s 1 , s 2 ) = (4, 1)
For one-dimensional data we assume that the application performs a computation on a block of data s consisting of elements, where each element is of b bytes of data. Figure . shows an input array, composed of m blocks. We assume that the computation time to perform f on one element is time units. Since we already have assumed data independent computation time, if the deviation in this time is not significant, then we can assume an average value of which gives a good approximation of reality. Therefore the computation time of s elements can be given by C(s) = • s.

For two-dimensional data, we that the computation time depends only on the area of the rectangle is given by:

C(s 1 , s 2 ) = • s 1 • s 2
In practice, C(s 1 , s 2 ) has a component which depends on number of lines s 1 , due to expensive loop overheads for inner and the outer loop on certain architectures. We assume that this overhead is negligible and discuss it further in the experiments section.

For transfer time, we use the formula in Equation . for a non-strided DMA:

T(s) = I + g • s • b
and from Equation . for strided DMA:

T(s 1 , s 2 ) = I 0 + I 1 • s 1 + g • (s 1 • s 2 ) • b
As discussed before, the software pipeline has  stages, namely, input data transfer, computation and output data transfer. Depending on the ratio between computation time for one block C, and transfer time per block T for input and output blocks, the execution pipeline can be classified into two types : As mentioned earlier, the execution of the pipeline stage has an epilogue and prologue stage which equals to the transfer time of a block. Now, we can observe in Figure .(b) a transfer regime, in which the total execution time of the pipeline is dominated by the transfer time. Whereas in computation regime shown in Figure .(a), the execution time is dominated by the computation time. We can see that apart from the computation time, the prologue and the epilogue also contribute to the execution time. Let m be number of blocks which are grouped for the the pipeline stage. The total execution time , of the pipeline can easily be estimated with the help of transfer time and computation time and given by -

=        m • C + 2T
in the computation regime (m + 1) • T + C in the transfer regime (.) The ratio between computation time of a block C and its transfer time T is not fixed but varies with the block size and shape. We can therefore control it to some extent in order to optimize performance, but which relation is preferred? The answer depends on which resource is more stressed by the application, which is either computation or communication, and this characterized by the parameter , where g is the cost per byte for DMA transfer (refer to Section .). In fact gives the difference in cost per element for computation and communication.

= -g • b (.)
If ≤ 0, then it signifies that the pipeline would always execute in the transfer regime where transfer time is dominating the computation time. The optimal transfer granularity for this case is easy to calculate and should be equal to the maximum size limited by the local store. This will improve the performance of the application by reducing the idle time between computations. Similarly if > 0, then the pipeline is in computation regime, and we consider this case for further analysis.

As we see in Figure .(a) if s is small we are still in the transfer regime, because the transfer time T(s) is dominated by DMA initialization time. However, when > 0 the computation grows faster for larger s than the transfer time and for a certain block size s * we enter the computation regime. To see the impact of s on the total pipeline time (Figure .(b)) we have to substitute m = n s into Equation ., where n is the size of the array. For small enough s, where the transfer regime is dominated by DMA initialization time, the total pipeline time mainly depends on m giving the number of DMA initialization, and the latter decreases inverse proportional to s. However for larger s the component proportional to s starts to dominate. In the computation regime the total computation time m • C can be seen as constant as the total computation time for n elements is roughly • n. In this regime, prologue and epilogue times 2T result in growth of pipeline time with s. Because in computation regime the pipeline time thus always grows with s, our strategy is to make s small enough so that we get into the transfer regime. In this regime we have to find s yielding minimal T(s).

We also have a constraint that the block granularity is between one element and the full input array size, provided that its size does not exceed the maximum local buffer size B imposed by the local store limited capacity. This leads to following constrained optimization problems for one or two-dimensional data:

T(s) ≤ C(s) T(s 1 , s 2 ) ≤ C(s 1 , s 2 ) s ∈ [1..n] s 1 , s 2 ∈ [1..n 1 ] × [1..n 2 ] b • s ≤ B b • s 1 • s 2 ≤ B
For this problem, we analyze the case with single and multiple processors for one-dimensional and two-dimensional data separately.

.. Single Processor

... One-dimensional data

We plot the computation time and the transfer time in Figure .(a). The ratio between the computation time and the DMA transfer time of the block splits the domain of solutions into computation domain and transfer domain.

The intersection of functions T(s) and C(s) for one-dimensional data blocks where the computation domain corresponds to the interval [s * , n], and the overall execution switches from a transfer regime to a computation regime for granularity s * , as illustrated in Figure .(b).

The total execution time for a large n is then approximated by:

(s) =        2 • T(s) + m • C(s) ≃ 2 • g • s • b + n • f or s > s * ( n s + 1) • T(s) + C(s) ≃ (n • I)/s + (n • g • b) f or s ≤ s * (.)
Recall that according to our strategy we search for optimal values of s by minimizing T(s) for s ≤ s * . From Figure . we see that (s) is a decreasing function for s ≤ s * . Therefore the optimal value is s * given by: If for any granularity s the execution is always in the computation regime (due to high ), the optimal unit of transfer is a block, that is s * = 1, which guarantees minimal prologue and epilogue.

s * = I/( -gb) (.) s 1 s 2 T = C n 1 n 2 I 1 / Transfer domain T > C Computation domain T < C (a) s 1 s 2 H n 1 n 2 s s 1 s 2 = s ′ 2 s ′ s ′ 1 s * 1 H(1) (b)

... Two-dimensional data

For two-dimensional data, we should find an optimal rectangular block which should give minimal execution time for the pipeline. For rectangular blocks, the dependence of T(s 1 , s 2 ) and C(s 1 , s 2 ) on their arguments is illustrated in Comparing the transfer time of the different shapes is not trivial since the computation domain forms a partially ordered set where possibly two different shapes s and s ′ are such that s 1 < s ′ 1 and s 2 > s ′ 2 . This is due to the fact that if these shapes have the same area, then the shape with smaller number of lines has a smaller transfer overhead, that is T(s 1 , s 2 ) < T(s ′ 1 , s ′ 2 ). Observe that the computation domain is convex where for any point s inside the domain, we can always find another point s ′ on the boundary such that s ′ 2 = s 2 and s ′ 1 < s 1 and hence with a smaller transfer time. Therefore the candidates for optimality are restricted, as for the one-dimensional case, to the intersection T(s 1 , s 2 ) = C(s 1 , s 2 ). These points are of the form (s 1 , H(s 1 )) where, H(s 1 ) = (I 0 + I 1 /s 1 )/ and their transfer time is expressed as a function of the number of clustered horizontal blocks s 1 :

T(s 1 , H(s 1 )) = c • (I 0 + I 1 s 1 )
where c is the constant 1 + (gb/ ). This function is linear and monotone in s 1 , meaning that as we move upwards in the hyperbola H the transfer time increases, and hence the optimal shape is, (s * 1 , s * 1 ) = (s 1 , H(s * 1 )) = (1, H(1)) which constitutes a contiguous block of one line of the physical data array. This is not surprising as the asymmetry between dimensions in memory access prefers flat blocks with s 1 = 1. Without data sharing and memory size constraints the problem becomes similar to the onedimensional case where it is only the size of the block that needs to be optimized.

.. Multiple Processors

Given p identical processors having the same processing speed and the same local store capacity, the input array is partitioned into p chunks of data distributed among the processors to execute in parallel. We assume that processors have enough memory to that each of it can implement double buffering algorithm. We extend our granularity analysis to this case assuming all processors implement the same granularity.

Data transfers in this setting may happen in parallel, leading to network contentions and we model the corresponding increase in transfer time as proportional to the number of processors. It also reduces the workload per processor as computation happens in parallel. We assume that each processor has its own DMA so that it can issue request irrespective of the other processors and all the processors start at the same time in a synchronized manner. Thus the DMA initialization phase is overlapped in time. Arbitration of these requests is left to the hardware which performs the data transfers at a low granularity (packet based) in round robin fashion. We assume that the time difference between processors receiving their blocks is negligible.

We model by parameterizing the transfer cost per byte g with the number of active processors such that g p that increases linearly with p. Obviously this changes the ratio between the computation time and the transfer time of a block and consequently the optimal granularity. Figure . shows the evolution of the computation domains and optimal granularity for one-dimensional and two-dimensional data as we increase the number of processors. The reasoning is similar to the previous one, where functions T and H become T p and H p , yielding an optimal data granularity for each p. For more details the reader is referred to [, ].

.  s h a r e d data t r a ns fe r s

A shared data computation is a data-parallel loop in which the computation for each block needs additional data from the neighboring blocks. In the one-dimensional case the processing of the input block is assumed to be:

Y i = f (X[i], V[i])
where V[i] is additional data taken from the input left neighbor X[i -1]. For two dimensional case, the assumed data sharing V(i 1 , i 2 ) was defined in Section .. For both one and two dimensional case the shared data is illustrated in Figure .. This shared data, can be transferred between the processors in various ways. We consider three strategies/mechanisms for transferring shared data that mainly differ in the component of the architecture which carries the burden of the transfer, . Replication: transfer via the global interconnect from main to local memory. In this method, the processor issues the DMA get for input and shared data for both X and V. . Inter-processor communication: transfer via the global interconnect the cores.

In this method, the processors synchronize at the beginning of the iteration and transfer the shared data using DMA, and then proceed to computations. . Local buffering: transfer by the core processors themselves. In this method, the processor after computation of current iteration copies the shared data from current iteration to a new position in the local store to be used in the next iteration. We can observe that in the second case, we need to do periodic allocation of data, while for the third case we have to do contiguous allocation of data as shown in Figure .. These strategies can be compared with respect to the overhead for communication time or replication time in the third case.

In general we observe that replication performs better in the computation regime because even if the data transfer time has extra overhead for V which is overlapped with the computation time and hence compensated. In transfer regime, execution time depends also on other factors like amount of shared data k, cost for locally copying the data etc. A detailed analysis of how to select the best strategy is given in [, ], and we omit it here for brevity.

.  dma p e r for ma nc e of t h e c e ll p r oc e s s or

We measure the DMA transfer time and accordingly the cost per byte as we increase the block size in one transfer, as shown in Figure .. The DMA cost per byte is reduced significantly for block size larger than  bytes. On Cell architecture if the DMA is not multiple of -bytes or unaligned at source and/or destination to -byte boundary, the interconnect performs poorly []. We observe this effect in Figure .(b), where below  bytes the cost per byte is significantly high and is consistent for higher sizes. For large block sizes the ratio converges to cost per byte g p proportional to the number of processors. As we increase the number of processors and synchronize concurrent DMA transfers, we can observe that transfer time is not highly affected for a small granularity because the initial phase of the transfer is done in parallel in each processor's MFC, whereas for large granularity the transfer time is proportional to the number of processors due to the contentions of concurrent requests on the bus and bottleneck at the Memory Interface Controller (MIC) as explained in [].

The initialization phase time for one-dimensional blocks I is about  cycles and the DMA transfer cost per byte to read from main memory g 1 is about . cycles per byte, and it increases proportionately to the number of processors to reach p • g 1 (for high granularity transfers). For two-dimensional data blocks DMA transfers are implemented using DMA lists (explained in Section .), for which we derive the DMA parameter values based on profiling information. As modeled in Section ., these parameters consist of a fixed initialization cost I 0 = 108 cycles and an initialization cost per line I 1 = 50 cycles which corresponds to the cost of the processing of each list element. The transfer cost per byte g is subject to variations that are more visible and amplified for data block transfers with increasing block height s 1 . These variations are due to several factors such as concurrent reading and writing requests of the same processor, packet-level arbitration between requests of different processors as well as the effect of stridden accesses of main memory. The minimal, maximal and average values of g p measured for two-dimensional data are shown in Table . and we use the average value in our model used to calculate the optimal granularity. Note that due to the characteristics of the Cell B.E. not all block size and shape combinations are possible. The limit for number of elements in a DMA list is K, where each element is a contiguous block transfer of upto KBytes. However, the Cell B.E. has a strict alignment requirements on -byte boundary for both DMA transfers and SPU vector instructions for which the processor is optimized. If this is not taken care of, the DMA engine aligns the data by itself causing data transfers to local memory at shifted offsets. To consider the shifting in application code would become too complex, and hence the scenario is avoided altogether by restricting to aligned transfers. In the experiments, we implement a double buffering algorithm for different benchmarks, some of them are applications where computations are completely independent and others have shared data. For each benchmark, we vary the block size and shape, along with the number of processors. We compare the performance (and the optimal solution) obtained in practice with those predicted by our analytical model. Our benchmarks consist of, first synthetic algorithms of (independent/shared) computations where f is a synthetic function for which we vary the computation workload per byte and the size of shared data k.

We then implement a convolution algorithm (a FIR filter) that computes an output signal on as a convolution of an input signal and an impulse response signal. These signals are encoded as one-dimensional data arrays and the size of the impulse response signal determines the size of the data window required to compute one output item. We vary the size of the impulse signal to vary the size of the shared data.

Our last benchmark is a mean filtering algorithm working on a bitmap image, encoded as a two-dimensional data array. This algorithm computes the output for each pixel as the average of the value of its neighborhood.

.. Independent Data Computations

To validate our analytical results for independent computations, we use synthetic algorithms and focus only on one-dimensional data, since, as explained previously, optimizing data granularity for independent two-dimensional data is similar to the one-dimensional case where it is about optimizing the granularity (and not the shape) of data.

For the synthetic algorithms, we fix the size b of an element to  bytes and the size n of input data array to K elements, the total size of the array being Mbytes. The local storage memory capacity K and two double buffers allocated then limit the possible clustered elements in one transfer to B=K elements, not taking into account the memory space allocated for code and the memory required for other data structures. We vary the size of block s and the number of processors. We compare both predicted and measured optimal granularity, and the total execution time for both transfer and computation regimes. Figure . shows the predicted and measured values for ,  and  processors. We can observe that the values are very close to each other. The predicted optimal points are not exactly the measured ones but they give very good accuracy. Performance prediction in the computation regime is better than in the transfer regime, the dominant part of the total execution time is due to the processors which have more predictable performance than the interconnect. Besides, as mentioned in [] in this regime we hide delays due to the interconnect latency and bandwidth.

.. Shared Data Computations

For shared data computations we perform the experiments for two shared data sizes k=,  bytes for  and  processors. Observe that as expected in the computation regime the replication strategy performs always better than local buffering and IPC as shown in Figure .. Further we also observe that IPC performs worse than local buffering owing to the high synchronization overheads between the processor for the inter-processor data transfer. The synchronization cost using barrier is between  and  cycles at each iteration, which is comparatively larger than overhead replicating data in the computation regime.

In the transfer regime, performance varies according to the value of k and number of processors. We can observe in Figure . that the costs of local buffering and replication are nearly the same, and that replication performs even better for a transfer of blocks size between  bytes and K. This demonstrates that using DMA for transferring additional data can perform sometimes better than local buffering even for a small value of k, and that keeping shared data in the local store may have a non-negligible cost. Therefore, even when considering contiguous partitioning of data, shared data redundant fetching using a replication strategy can be as efficient, if not more efficient than keeping shared data in the local store. However, the cost of transferring shared data using replication becomes higher than other strategies when the number of processors increase because of the contentions even for small values of k. Convolution is an algorithm [] benchmark (FIR filter) used commonly in signal processing applications. In a FIR (finite impulse response) filter, convolution is done between a given finite impulse response signal of size r and the the input signal. The algorithm assumes D input array share r -1 data elements between the subsequent iterations. The equation to calculate the output Y for an input arrays X and C is given as:

Y[i] = m j=0 X[i -j] • C[j]
In our experiments, the size of input array X is chosen to be Mbytes of data, so it cannot fit in the scratchpad memory, whereas C, the filter coefficients are small enough to be permanently stored in the local store of each SPU. Hence double buffering is implemented to transfer data blocks of array X (respectively Y). The measured computation cost per element is about 53 cycles, owing to the SIMD (single instruction multiple data) floating point operations performed on double data type. Note that for this algorithm, despite an optimized implementation using vector operations the computation cost per byte is much higher than the transfer cost per byte with maximum contentions g 8 , resulting from the use of maximum number of available cores. Therefore, the overall execution is always in a computation regime for all strategies.

Figure . summarizes performance results for size of b = 8 bytes and r = 32 samples, using  and  processors. In the computation regime, replication strategy outperforms local buffering and IPC strategies since it avoids the computational overhead at each iteration of copying shared data locally or exchanging data between neighboring processors using synchronous DMA calls. This overhead is proportional to the number of iterations and therefore decreases with higher granularities to be eventually negligible which leads all strategies to perform with nearly the same efficiency for large granularities.

.. Mean Filter Algorithm

We use a mean filter algorithm which works on a bitmap image of 512 × 512 pixels. Each pixel is characterized by its intensity ranging over [0 -255]. The output for a pixel is the average of the values in its neighborhood defined as a square (mask) centered around it. We have experimented with different mask sizes and focus on the presentation of the results for a  x  mask, that is, k = 8. Note that the Cell architecture does not support SIMD instructions for char (-byte) datatype, and non-SIMD operations are highly inefficient on SPU. In order to use SIMD operations for efficient execution of the filter code, we encode a pixel as an integer (b = 4 bytes). Based on profiling information, the computation workload per element obtained, is roughly = 62 cycles.

Figure . illustrates the influence of the shape of the block (and its implied replicated area) on the transfer time calculated using formula mentioned in []. We consider in this plot different feasible combinations of (s 1 , s 2 ) so that s 1 × s 2 = 4096. A shape (s 1 , s 2 ) yields a Block height s 1 Pipeline total execution time (cycles) Finally we evaluate the effect of the granularity and shape of the blocks and the total execution time of the pipeline for different numbers of processors. The distance between the predicted and measured values is rather small except for large values of s 1 . The major reason for the discrepancy between the model and the reality is that C(s 1 , s 2 ) has non negligible component that depends on s 1 for two reasons. The first is due to the overhead at each computation iteration related to the setting required between the outer loop and the inner loop like adjustment of the pointers for every row, pre-calculation of sums of borders etc. Secondly, the creation of DMA list elements equal to s 1 , occupies the processor as discussed in Section . and this overhead is also added to the overall execution time.

meas s 1 × s 2 = 2K pred s 1 × s 2 = 2K (b) s 1 × s 2 = 2048
We observed that overall predicted results are close to the measured ones. However, some error in prediction results from -■ Variation in the DMA cost per byte parameter g, with respect to contentions in the global interconnect, which is difficult to model accurately.

■

Cell SPU are vector processors, which have high overheads for non-vector instructions like branching, scalar calculations etc. Owing to this fact, the code which performs initialization of the data structures, adjustments of pointers etc. requires considerably large amount of time.

■

In the case of strided DMA the overhead of formulating a DMA list is significantly higher, which results in poor prediction for rectangular blocks with higher s 1 value.

A further detailed explanation of the experiments is given in [, ] and skipped here to keep the text concise.

.  c onc lus i ons

In this chapter, we presented a way to model the DMA transfer granularity problem for data-parallel applications, under simplified assumptions. The selection of such parameters is an additional burden to the application programmer and in general a non-trivial issue, owing to various factors that must be considered such as dimensionality, amount of shared data etc., combined with the hardware architecture parameters. We captured the essential parameters of the applications with or without shared data and presented a method to calculate the optimal data-transfer granularity for double-buffering algorithms. We presented real-life application benchmarks in the experiments section to prove validity of our results.

Pre-fetching the data to the local processor memory is an old technique to close the gap between the speed of the processor and the main memory. Caches used for this reason faced the problem of area and speed overhead in supporting cache coherency []. Scratchpad Memories (SPMs) is an alternative solution to caches where data (and sometimes code) transfers through the memory hierarchy explicitly by the software. In architectures supporting scratchpad memories, buffering techniques have been suggested previously to hide the access latencies []. In [], the author performs parametric analysis for calculating optimal buffer size for data independent parallel loops for a cache based architecture. However the work doesn't consider multi-processor scenario or data sharing. Effect on multiple processors performing DMA concurrently is studied in []. Our work on one-dimensional data is very close to one in [], where the author presents a formal analysis on the optimal buffer size on a single processor system. We extend the problem with multiple processors accessing the resources. Work has been done in context of parallel loop partitioning [, , ] for effective distribution of data on multiple processors. However, we deal with DMA-based architectures instead of cache-based, and study the problem formally. This is a joint work and is also published in [].

Despite the fact that for each application the SMT solver can generate different Pareto configurations which can optimally execute an application maintaining the given costs, this is not always sufficient in practice due to fundamental problem that the exact set of applications executing on the on the platform at the same time is often unknown at compile time, as it is dynamically decided at run time. In order to make an efficient execution of all the applications, decisions must be made at system-level at run-time to optimize the utilization of the resources by a dynamically changing set of applications. In next chapter we describe such a run-time system which manages applications dynamically. This chapter introduces a run-time management system to handle the applications dynamically starting at unknown time in the on resource-constrained multi-core processors.

I n contemporary MPSoCs, the number of applications that run concurrently is increasing rapidly. It is often the case that the designer has only a predefined set of applications, which can be launched by the user. However, launching of an application depends on the user requirements. For example, if user is playing a video on a mobile device, the audio related to it should also be decoded in parallel. In background, the device may update its messages or emails, which is happening transparently to the video application. Thus even if the applications are known at compile-time, the set of simultaneously running applications varies. In addition each application has its own Pareto optimal configurations which defines the trade-offs between various system parameters like resource usage, energy consumption etc. Due to this situation there is a need for having a runtime manager which will launch or reconfigure all the applications in order to globally optimize the resources of the device, while satisfying the requirements of the applications. This launching or reconfiguration should also be done transparently without affecting running applications like an MPEG decoder, which have strict deadlines. In short, the application launching and reconfiguration should be predictable (should finish in a definite amount of time) and composable (should not affect the running applications).

In this chapter we describe a run-time manager which guarantees predictable and composable behavior. We describe how the system-level resource manager manages applications and provides configuration decisions to the application-level resource-manager. The application resource manager then, depending on the configuration provided, reconfigures the application(s) in a predictable and composable way. We demonstrate this run-time manager on a real hardware platform. We perform a case-study of JPEG decoder application on this platform and demonstrate its performance. .  runt i me r e s our c e ma nag e r

At design time, the design flow generates multiple configurations for a given application which represent the available trade-offs between resource usage and quality. Configurations could for example provide a trade-off between the use of different resources, such as different processors, or trade-offs between processing and memory usage, or through DVFS, between energy consumption and resource utilization. The configurations determined at design time are Pareto optimal trade-offs between the various quantities considered at run-time (i.e., resource usage, energy usage and quality). The configurations are determined at design time on a per-application basis. The run-time resource manager must combine these configurations at run-time to investigate system-wide trade-offs. After combining the trade-off spaces of the individual applications, the resource manager can decide on the optimal system-wide configuration of all running applications and subsequently it can implement this decision by reconfiguring the individual running applications. As mentioned before, all of these steps need to be performed by the run-time resource manager while providing timing guarantees to the running applications. A resource manager which fulfills these constraints is introduced here. The resource manager uses the predictable and composable multi-dimensional multiplechoice knapsack (MMKP) heuristic presented in [] to select an optimal configuration for all applications running on the platform. The configuration selected by this heuristic may trigger a reconfiguration of these applications. Our proposed run-time mechanism ensures that this reconfiguration process is completed within a bounded amount of time (i.e, the reconfiguration is predictable). Moreover, the timing behavior of applications of which the resource assignment is not changed will not be affected (i.e., the reconfiguration is composable).

.. System-level resource manager

In order to perform a predictable and composable migration, we need a hardware platform which supports such features. In composable execution, starting and stopping of an application does not affect other applications running on the platform. Depending on the allocated resources a guaranteed worst-case response time for an application is called a predictable execution. The CompSOC platform discussed in Section . which runs CompOSe operating system provides an infrastructure for predictable and composable execution of applications.

The platform is equipped with techniques such as TDM based task and network scheduling etc. as discussed in Section .. Every processor in the platform has a fixed number of time slots which can be allocated to different applications.

The system-level and application-level resource managers will be running on top of Com-pOSe. The system-level resource manager is implemented as a separate application running on the platform. Because of the composability offered by CompSOC, it is guaranteed that the manager itself will not interfere with the timing behavior of other applications. The systemlevel resource manager can optimize the resource budget distribution using an algorithm such as the MMKP heuristic presented in [].

... MMKP Algorithm

This algorithm assumes that the set of applications that execute on the hardware platform are known at the compile-time. A Pareto set of solutions can be calculated with methods such as cost space exploration discussed in Chapter  for each application. This algorithm decides on the optimal configuration of every application in a bounded amount of time (i.e., it is predictable) while considering multiple costs, with the goal of globally efficient execution of all applications satisfying the resource constraints.

The inputs to this algorithms are the Pareto points for each application, where every point indicates the amount of resources used and a value associated with the point which indicates its optimality. Suppose an application is already running on the platform. A maximumvalue configuration can be selected for optimized execution of this application. When a new application starts on the platform this algorithm combines the Pareto configurations of the new application and the currently running application(s) to form a new set of configurations. In order to speed up the computation of new set, the multi-dimensional cost space is transformed to a two-dimensional space by aggregating the resource usage. In this transformed space the dominated points for every application are eliminated. Every Pareto point of newly started application is combined with every Pareto point in the current set such that it satisfies the resource constraints. If the combination of the configurations does not satisfy the platform resource constraints the point is eliminated. The dominated points in the combined set of solutions obtained are again eliminated. Thus the resultant set consists of combined configurations of already running applications and the newly starting application annotated with total resource usage and optimality value. A tunable parameter L provides a bound on how many total combined solutions are retained. If the above combination generates more Pareto points than the parameter L, it eliminates some of them heuristically. A Pareto point with maximum-value is then chosen which provides a configuration for every application running on the platform. Given an MMKP instance I with N newly starting applications, the bounds on the execution time can be given by:

T(I) ≤ C • N • L 2
where C is a processor dependent constant.

In this work, we use the MMKP heuristic in our system-level resource manager. For further details on the algorithm the reader is referred to []. It is possible to replace the MMKP algorithm with any other one that would to decide reasonably optimal configuration for all the applications in predictable amount of time. The configuration of applications represented by the chosen Pareto point by system-level resource manager can call for reconfiguration of application(s) running on the hardware platform. We focus on the application-level resource manager which implements the resource allocation decisions taken by the system-level resource manager within a bounded amount of time.

.  i mp le me ntat i on

In this section, we describe the mechanism by which the application-level resource manager handles the application reconfiguration.

.. Application-level resource manager

The implementation of a reconfiguration decision, which is handled by the applicationlevel resource manager, may require that actors from an application are migrated from one processing tile to another. This process is triggered from inside the application which is being reconfigured. This is because from the perspective of the CompOSe operating system, our application-level resource manager is part of the application. The application programmer does not have to code for the application manager, but only add the application manager task in its schedule.

Our application-level resource manager uses a master-slave configuration (see Figure .). The master stores the active resource configuration of the application. Whenever the MMKP algorithm decides to reconfigure the application, the master will send a set of reconfiguration commands to the slaves. For this purpose, a pair of dedicated FIFOs is used between the master processor and each slave in the platform.

Since the whole reconfiguration process takes place only during the TDM time slices allocated to the application, it is guaranteed that the other applications will not be affected by the reconfiguration (i.e., the run-time resource manager is composable). In order to arrive at a predictable run-time mechanism it is however also important that the reconfiguration process itself can be completed within a bounded and known amount of time. Otherwise, the application which is being reconfigured may miss its own timing deadlines.

.. Migration Point

To reduce the migration overhead, a reconfiguration can only be performed at specific moments during the execution of the application. In the SDF MoC (model of computation), actors have no state that needs to be preserved across firings. Any state (data) that needs to be stored between firings should be stored explicitly as a token that circulates on a special self-source self-sink edge (self-edge) of an actor. Allowing actor migrations only when an actor is not executing (firing) ensures that no state (other than the initial token on the self-edge) needs to be transferred. This implies, no processor context needs to be migrated, which reduces the migration overhead considerably.

Whenever an actor is migrated to a different processor, the edges connected to this actor must also be reconfigured. Tokens that are present in these edges must then be migrated from the old edges to the newly created edges. Throughout the execution of the SDF graph, the number of tokens in the edges may vary. Hence, the amount of tokens that needs to be transferred may vary depending on the moment when an actor would be migrated. As a result, the time needed to migrate an actor and its connected edges might depend strongly on the number of tokens in these edges. In order to provide timing guarantees, design-time analysis techniques must take the worst-case situation into account when analyzing whether a particular reconfiguration would be feasible given the timing constraints of the application. When actor migrations are allowed to occur at any moment when an actor is inactive, this could lead to very pessimistic estimates on the number of tokens that needs to be transferred. As a result, design-time analysis techniques would most probably indicate that many reconfiguration options cannot be performed within the given timing constraints. To address this issue, we use a special property of SDF. Since the production and consumption rates of the actors on the edges are constant in an SDF graph, there exists an execution interval called graph iteration (see Section .), where each actor has been fired for a certain number of times, the token distribution in an SDF graph returns to its original state. At this moment, the number of tokens in all edges connected to an actor are equal to the number of initial tokens. Since this is a well defined amount, it can be easily taken into account in the timing analysis performed at design-time. Therefore, our application-level resource manager will only migrate an actor and its connected edges when the actor and all actors connected to the edges of this actor have completed an iteration. Note that this condition is not sufficient. The actors that communicate with migrating actor should also be halted at the start of an iteration. Otherwise during the migration, tokens may be added or removed from these edges unequal to the number of initial tokens and taking this into account it too complex.

.. Actor and FIFO Migration on CompOSe

When migrating an actor, the schedule on the processor on which this actor was originally running as well as the schedule on the processor to which the actor is moved must be changed. In CompOSe, actors from the same SDF graph are scheduled using a static-order schedule. To modify these schedules, CompOSe requires that the complete schedule of all actors that belong to the same SDF is removed from a processor and subsequently a new schedule can be loaded. This implies that the application (SDF) should be stopped on the processor from which the actor is migrated away as well as the processor to which the actor is moved. When migrating an actor, the channels (FIFOs) connected to the actor must also be migrated. This can be done through CompOSe by removing the old FIFOs and adding the FIFOs to the new migrated actor. If initial tokens are present in the old FIFO, they are retained and copied to the new FIFO. CompOSe requires that the application whose set of FIFOs is modified on a processor is not running during this reconfiguration. Hence, the application must be stopped on the processor from which migrated actor departs, the processor receiving the migrated actor and all processors that run actors which have at least one FIFO channel connected to migrated actor. In many practical situations, this will often imply that the application must be halted on all processors. Considering this aspect and in order to reduce the number of messages exchanged between the master and slave components of our application-level resource manager, the resource manager

V LD I Q/ I D CT CC 1 1 1 36 1 1 1 36 1 36 1 Figure . -JPEG decoder SDF graph
will halt the application on all processors. Next, it will perform the reconfiguration. When this process is completed, the application will be resumed on all processors. Note that during this whole process, the other applications running on these processors are not interrupted which ensures that our run-time reconfiguration is composable.

The next section presents in detail the messages that are exchanged between the master and slave components in our application-level resource manager when reconfiguring an application. As explained in that section, each individual operation during the reconfiguration process (e.g., reconfiguration decision, actor migration, FIFO creation, etc.) can be performed in a bounded amount of time. Since the complete set of operations that needs to be performed in order to migrate an actor is known at design-time, it is possible to provide a timing guarantee on the completion of the whole reconfiguration. Hence, the run-time resource manager offers a predictable reconfiguration mechanism.

.  a p p li c at i on-le ve l ma nag e r

We demonstrate our resource manager with a running example of a JPEG decoder where actors migrated from one processor to another. The application SDF graph shown in Figure ., consists of three actors, namely Variable Length Decoder (VLD), Inverse Quantizer combined with Inverse Discrete Cosine Transform (IQ/IDCT) and Color Conversion (CC). The VLD actor has a state that needs to be preserved across actor firings. In between firings, this state is stored as an initial token on the self-edge connected to this actor. One pair of edges from the VLD to IQ/IDCT respectively CC actor is used to communicate JPEG header parameters (e.g., image size) between the actors. The remaining edge from the VLD to the IQ/IDCT actor and the edge from the IQ/IDCT to the CC actor are used to communicate the actual image data.

.. Run-Time Actor and FIFO Migration

Figure . illustrates the actor migration process. Initially the VLD and IQ/IDCT actors are running on the second tile and the CC actor is running on the first tile. Next to these actors, the second tile is also running the system-level resource manager as well as the master application-level resource manager for this application. The other two tiles are running a slave application-level resource manager for our JPEG decoder application. On each tile, if the application does not execute, a small time slice is allocated to application level resource manager which checks for any migration decisions. It facilitates to migration of applications on the tile where the application is not executing previously. In this example, no other applications are active on the platform. At some point in time, the system-level resource manager decides to migrate the CC actor from tile  to tile . (This decision would normally be triggered when a new application is started on the platform, but for simplicity we assume in this example that the system-level resource manager takes this decision without any new application entering the system). Once the system-level resource manager has taken the decision to reconfigure the Since the application-level resource manager is part of the JPEG application running on tile , it will be periodically scheduled on this tile. The first time it gets scheduled after the system-level resource manager took the decision to reconfigure, it will start the actual reconfiguration process. This process starts by sending a command to all tiles to halt the application (step  in Figure .). This is done by sending a message through the dedicated FIFOs between the master and slave application-level resource managers. Whenever an application-level resource manager is scheduled on a processor, it will check this FIFO to verify whether new commands are available in this FIFO. If so, these commands will be processed. Once the command to halt the application on the tile has been completed, the slave application-level resource manager will inform the master application-level resource manager by sending an acknowledgment (step  in Figure .). When all slaves has confirmed that the application has been halted and the application has also been halted on the tile running the master application-level resource manager, the resource manager continues with the next step of the reconfiguration process. Since after reconfiguration there will be no actors of this application running on tile , the number of time slices allocated to the application can be reduced on tile  to just one (which is needed to periodically execute the slave resource manager). Furthermore, the number of TDM slices allocated on tile  may have to be increased. This is done as step  in Figure .. In this step, the master resource manager instructs the slave resource managers to make this change in the TDM allocation.

Step  involves the removal of the old FIFOs from tile  to tile  and in step  new FIFOs are created between tile  and .

These FIFOs are immediately connected to the VLD actor on tile  and a new instance of the CC actor on tile . (Note that we assume that the instruction code of all actors is available on all tiles. Hence, no code migration is required). Next, the static-order schedule on tile  is updated (i.e., the CC actor is added to it). Subsequently (step ), a message is sent to all tiles to resume the execution of the application. At this moment, the reconfiguration process of the application has ended and the master application-level resource manager confirms this to the system-level resource manager (step ). This completes the complete reconfiguration process of the application.

As mentioned before, in order to ensure a predictable reconfiguration process, it is important that each of the steps described above can be completed within a bounded amount of time. Our implementation ensures that this constraint is met. Table . lists the number of clock cycles needed to perform the various steps in the reconfiguration process. These times depend on the tile which ultimately needs to perform the operation. When the operation (e.g., removal of application from TDM) needs to be performed on a slave tile, then we need to consider the overhead of sending a message from the resource manager running on the master tile to the resource manager on a slave tile. The time required to remove an application from the TDM schedule (step ) depends on the application. As explained before, an application may only be stopped on a tile when the application has completed a full iteration of the SDF graph. In the worst-case, the application may have just started a new iteration on all tiles when a request to remove the application from the TDM schedule is received. In that case, a complete iteration of the SDF graph must be finished before the request can be executed. Hence, the worst-case time needed to complete step  is bounded by the worst-case time needed to complete one iteration of the SDF graph on the platform. Since all resources in the platform are predictable and since we assume that the worst-case execution time of all actors are known, we can compute the worst-case time needed to complete step  at design-time. Table . shows the time required to reconfigure a FIFO. Depending on the tiles to which a FIFO is connected the time required to add or remove a FIFO varies. If the source and destination of a FIFO are both on the master tile, then there is minimal overhead to remove or add the FIFO. In this case, the overhead is limited to the allocating/freeing the data structure associated with the FIFO. When a FIFO is used to communicate between different tiles, for example between a tile running the master resource manager and a tile running a slave resource manager, the overhead will also include communication overhead to send a message to add or remove a FIFO and to send an acknowledgment after adding or removing the FIFO. The highest overhead occurs when a FIFO is connected between two different slave cores. In this scenario, the master application-level resource manager has to communicate messages between two different slaves and wait for their acknowledgments. It follows from Table . and Table . that the amount of time taken to complete an actor migration depends on the old and new configuration of the application on the system. We have performed an experiment in which the JPEG decoder is reconfigured several times. Initially all three actors are mapped to tile  i.e., configuration ,, in Comparing these two parts it is clear that the actual run-time of the reconfiguration process as well as the worst-case run-time of the reconfiguration process are dominated by step  (i.e., the worst-case of all other steps is always very close to the measured run-time for these steps). The fact that step  is the bottleneck in the reconfiguration process is not unexpected. As explained in Section ., the run-time resource manager must in step  halt the execution of the application on all resources. In the worst-case this may require the application to execute a complete iteration before it can be halted. Even in the typical situation, it will require that many actors finish their execution before this step is completed. Hence the long worst-case and measured run-times for this step. The only option to reduce the time taken by step  would be to relax the constraint that an application can only be reconfigured at the end of an iteration. However, as discussed in Section ., this could in the worst-case lead to a large overhead in migrating tokens when reconfiguring FIFOs. An experiment with a small test application have confirmed that this overhead for most realistic applications by far exceeds the worst-case time needed to complete an iteration of the graph. From this we concluded that the choice to allow reconfigurations only at an iteration boundary is still the best option.

.  c onc lus i ons

In this chapter we introduced a run-time reconfiguration mechanism which provides timing guarantees on the time needed to migrate actors and their communication channels in a MPSoC. The mechanism guarantees that the reconfiguration of one application will not affect the timing behavior of other applications running on the same resources ensuring a composable behavior enables predictable and composable MPSoC reconfiguration. The proposed run-time mechanism is demonstrated on a realistic MPSoC (called CompSOC), which is running a JPEG decoder application. In our implementation we make a design choice of migrating the application only at the end of the iteration. However when relaxing this constraint, the amount of data that will be needed to be migrated will cause a very pessimistic prediction of the actor migration.

Task migration in a multi-processor system is performed for various reasons like thermal [, ], load-balancing [], fault-tolerance [] etc. We can classify the task migration work briefly in two types depending on the underlying architecture which is shared memory or distributed memory. We consider a scalable approach for multiprocessor with private memory for each processor, where the migration is done only at pre-decided checkpoints []. Taking the advantage of SDF programming model, in our case the programmer need not explicitly store the context for migration.

A comprehensive survey of the run-time resource managers and their optimization strategies is provided in []. It divides the run-time resource manager into two parts; one which deals with optimization decision making while the second is responsible for implementation of this decision. Casavant et. al. in [] provides with the classification of different optimization algorithms that can be used for resource manager. We use MMKP [], which guarantees us predictability and flexibility. Owing to the private shared memory for each core, we implement the master-slave configuration of the resource manager, where the master is responsible for the decision making process, while the implementing the decision is performed collectively by all the responsible cores. This gives us an advantage of managing the data-structures in a simple way []. We belong to the (type ) adaptive applications classified in [], where applications are allocated certain resource budgets, and is responsible to manage them efficiently.

Master-slave configuration for task migration with copy of task in all processors is presented in [], is similar to our work. However they require sufficiently large queue size between the communicating actors to avoid the deadline misses in the application during the task migration. We migrate the application only the end of iteration, in a predictable one time slot in order to avoid any deadline misses and disturbances to other applications.

Almeida et al. in [] propose tasks migration to provide workload balance in multiprocessor system to optimize the throughput. There is no indication of amount of time required to migrate the task and its related resources. Further, their task migration is not capable of migrating stateful actors.

In [], the author proposes locking of caches for hard-real time tasks which can provide predictable task migration. Their work focuses on cache based techniques, which become unscalable with increasing amount of processors on chip. Whereas we focus on private memory for each core, which has own instances of tasks running.

Hardware mechanisms [, , ] are proposed in order to offload the task of scheduling and migration to the hardware in order to save from the run-time overhead. However it is essentially a trade-off between the speed, flexibility and scalability of the system. Definitely, we do not outperform the hardware mechanisms, but our methodology gives a predictability and composability without requiring specialized hardware. In AsyMOS [], a different approach is taken, where the system management functions are handled by dedicated cores. Ours is a flexible approach where we dedicate TDM slices in our framework for the management tasks.

In the next chapter we conclude this thesis and discuss the future work.

cha pte r 10

Co nc lus i o ns a nd Fut ure Wo rk

This chapter concludes the thesis and discusses about the possible future work.

I n this thesis, we used a constraint satisfaction approach to solve mapping and scheduling problems on multi-core architectures. This thesis can be seen as an elaboration and extension of work started in [] which utilized multi-criteria optimization exploration algorithm to find efficient mapping and scheduling solutions for a multi-processor architecture. It experimented on relatively simple architectures and small problem sizes. In this thesis, we tried to overcome the limitations of this work and provide experiments on real platforms. We established symmetry breaking techniques for data-parallel computations which significantly improved the performance of the SMT solver and increased the size of the application model that could be solved. In this experiment we observed that task symmetry and processor symmetry applied in conjunction amplify the effect symmetry reduction in SMT. Either of them applied separately has a smaller effect on the reduction.

We used SMT solver to further perform mapping and scheduling of applications on the Kalray many-core architecture. The processors were grouped into clusters and connected by network-on-chip, communicate with each other via DMA. We used the DMA model in order to characterize the data transfers between different clusters. Our framework provided an automated way of performing distribution of tasks across the clusters and generating communication-aware models. These models were used to deploy the solution on the hardware platform. We verified the performance on the hardware platform and found it to be fairly accurate. We believe that with additional modeling of network route selection and contentions, we will be able to further reduce the error in performance prediction.

We also addressed the problem of optimization of DMA data transfer granularity for dataparallel applications with regular memory access patterns. We compared different methods by which the shared data could be exchanged between the processors in an efficient way. We built a model of the DMA mechanism with which we were able to successfully demonstrate a methodology to differentiate between the transfer and computation regimes, and how they affect the performance of the application. We experimented our formalization on the Cell processor architecture and proved it to be reasonably realistic considering the assumptions we made.

Further in this thesis, we demonstrated a necessity of a runtime manager on the multi-core platforms that chooses the configurations of the applications in execution in order to optimize resource-utilization globally. We discussed how an algorithm like MMKP can decide an optimal   chapt e r . con clusion s an d f ut ure work configuration out of available Pareto set for an application and take a decision to migrate the tasks dynamically. We demonstrate how this application reconfiguration can be performed in a predictable (i.e. amount of time known at design time) and composable (i.e. without affecting other applications running on the platform) way. For this work, we performed experiments on a platform designed for predictability. We run experiments using the JPEG decoder application and prove that a predictable migration of application can be performed, in a composable way.

We believe that, this thesis can be further extended in many possible directions, some of which are discussed below.

■ Scheduling under variation in execution time: In our case, we always consider the worst-case execution time for the actors (or tasks). However in reality the execution time between tasks of the same actor differ due to many reasons such as data-dependent execution. Predictions made this way are good when the range of execution times is small, but their quality degrades when variations become large. It will be interesting to incorporate this variation in execution time of tasks into the formulation of the constraints and costs. As we observe in the experiments that, the SMT solver is overwhelmed with increase in the problem size (number of tasks). This variation of execution time can cause additional burden on the solver. Probably it will involve support of special formalism such as probabilistic scheduling under uncertainty.

■

Splitting of actor over multiple clusters: In our multi-stage design-flow for Kalray processor architecture, we assign an actor to a partition in the partitioning step. This makes the granularity of assignment equal to an actor. However, if an actor has a very high repetition count (for example  tasks or more), we could possibly split the actor between multiple clusters. Actor splitting will introduce additional decision variables and further overhead to the solver. This will also have an impact on the communication buffer memory and must be studied in detail.

■

Network route selection and communication scheduling: In the mapping and scheduling on the Kalray processor, the second stage places the communicating partitions as close as possible. In reality the NoC is fast enough and the distance between clusters is a factor of less importance. We made an attempt by putting them close so that the network contentions are reduced to a minimal value, as the contentions can cause an error in performance prediction. We believe that if we perform network route selection and scheduling of communication, we will be able to eliminate this source of error completely. Finding optimal routes for communication is a hard problem and will need special encoding techniques to solve it using the SMT solver.

■

Combination of DMA transfer granularity results with split-join graphs: We model the DMA transfer size optimization problem for application which have regular memory access pattern. It is possible to model such applications using split-join graph model. If we use such application model, then the DMA transfer size can affect the split-join factor of the application. As choosing a DMA transfer size implies combining of blocks for processing. It also means combining tasks which can actually execute in parallel. It will be interesting to see how the SMT solver can decide between data parallelism and data transfer granularity. Also extending split-join graphs to multiple dimensions and shared data are other related work directions.

■

Pipelined scheduling on the platform: Streaming application have an another important constraint in addition to latency, called throughput. It emphasizes the number of graph iterations that can execute in a unit time. For meeting this requirement, multiple iterations of the application execute in parallel in a pipelined execution. A constraint formulation for pipelined scheduling will require additional variables, modulo arith-metic operation and special mutual exclusion constraints and these clauses make the problem solving harder. We would like to experiment with such pipelined scheduling on and see it in action on the multi-processor hardware platform. Currently we are in process of experimenting with three different encodings of the pipelined scheduling, a problem not so simple for SMT solvers []. For the moment we can solve typically problem upto size of - tasks. However, the benefits of pipeline parallelism for the performance justify such a restriction.

. 

  Evolution of multi-core processors . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . MPSoC architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Multi-core architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Execution of a program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Parallelism in a program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Software design flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Basic dataflow graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Simple SDF with two actors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . SDF with backward edge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Timed Synchronous DataFlow Graph . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Example schedule of a Synchronous DataFlow graph . . . . . . . . . . . . . . . . . .  . Split-Join graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . JPEG decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Tilera Tile- processor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Kalray MPPA- platform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . CompSOC platform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . IBM Cell BE processor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . IBM Cell processor DMA controller . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Image stored in memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . DMA transfers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Pareto points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Forward and backward cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Sat and Unsat sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Grid based exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Structure of StreamExplorer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . FIFO token example for actors A and B with buffer size =  . . . . . . . . . . . . . .  . Illustration of the lexicographic ordering theorem . . . . . . . . . . . . . . . . . . .  . Time to find optimal latency as a function of the number of tasks for 5 and 20 processors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Exploration time to find optimal latency as a function of the number of tasks and processors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Result of Pareto exploration for = 30 . . . . . . . . . . . . . . . . . . . . . . . . . .  . Video decoder example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Video decoder exploration result . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Multi-stage design flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  x list of f igure s xi . Working of inter-cluster FIFO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Communicating tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Partition aware communicating tasks . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Buffer aware graph model for a channel without DMA . . . . . . . . . . . . . . . . .  . Buffer aware graph model for a channel with DMA . . . . . . . . . . . . . . . . . . .  . Double buffering example schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .  scheduling solutions for  partitioning solutions . . . . . . . . . . . . . . . . . . .  . Jpeg decoder solutions measured on Kalray platform . . . . . . . . . . . . . . . . . .  . Application benchmarks: summary of results . . . . . . . . . . . . . . . . . . . . . .  . Neighborhood pattern of size k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Contiguous vs periodic allocation of data . . . . . . . . . . . . . . . . . . . . . . . . .  . Distribution of D data of same size, but different shapes . . . . . . . . . . . . . . .  . Influence of block shape on the amount of shared data . . . . . . . . . . . . . . . . .  . Decomposition of one dimensional input array . . . . . . . . . . . . . . . . . . . . .  . Pipelined execution using double buffering on one processor . . . . . . . . . . . . .  . Regimes depending on the block size . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Rectangular blocks: (a) computation and transfer domains, (b) optimal granularity candidates and optimal granularity. . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . The dependence of computation C and transfer T on the granularity (s 1 , s 2 ). . . . .  . Pipelined execution in the transfer regime using multiple processors . . . . . . . . .  . Evolution of the computation domain and optimal granularity as we increase the number of processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Shared data communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . DMA performance for contiguous blocks . . . . . . . . . . . . . . . . . . . . . . . . .  . Independent data computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Measurements for shared data in computation regime . . . . . . . . . . . . . . . . .  . Measurements for shared data in transfer regime . . . . . . . . . . . . . . . . . . . .  . Convolution algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Predicted transfer time for different block shapes with shared data . . . . . . . . . .  . Predicted and measured values for different combinations of s 1 × s 2 . . . . . . . . .  . Run-time resource manager (conceptual view). . . . . . . . . . . . . . . . . . . . . .  . Run-time resource manager (deployment view). . . . . . . . . . . . . . . . . . . . . .  . JPEG decoder SDF graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Actor migration steps example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Measured and predicted reconfiguration times . . . . . . . . . . . . . . . . . . . . .  A. Gantt chart for schedule XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  cha pte r 1 I nt ro duc t i o n The first chapter introduces the embedded systems domain. It explains the multi-core scenario and technological challenges associated with it.

Figure

  Figure . -Evolution of multi-core processors 

Figure

  Figure . -MPSoC architecture

  Figure . -Multi-core architecture

  Figure . -Execution of a program

  Figure . -Parallelism in a program

  Figure . -Software design flow

■

  Chapter  concludes the thesis and presents the future work. cha pte r 2 Pro g ra m m i ng Mo de l This chapter introduces the role of programming model and split-join graphs which we use to model streaming class of applications.

■

  Structure of the program■ Amount of computation of different elements ■ Interaction among different elements of the program Depending on the target class of applications and modeling objectives, there are different types of models to choose from. Timed Automata, Petri Nets, acyclic task graphs, Process Networks are examples of models. They are developed for different goals e.g. analyze deadlocks, ensure safe operations etc., and hence different formalisms are applied on the models to achieve these goals.

Figure

  Figure . -Basic dataflow graph

Figure

  Figure . -Simple SDF with two actors

Figure

  Figure . -Example schedule of a Synchronous DataFlow graph

Figure

  Figure . -A simple split-join graph and its expanded task graph. Actor B has instances.

  Figure . shows a functional diagram of such a processor.

  Figure .(a)), running at . MHz. Each processor (also called tile) is connected to a switch engine which can route communication packets on six independent networks in a mesh topology (seen in Figure .(b)). Each processor core contains three-way VLIW processor with three instructions per bundle. It contains three computing pipelines P, P and P. ■ P: executes arithmetic and logical operations.

■Figure

  Figure . -Tilera Tile- processor

Figure

  Figure . -Kalray MPPA- Platform (with zoom into a compute cluster)

  Figure . -CompSOC platform

Figure  .

   shows a basic flow of a DMA command inside the SPE of the Cell processor. The SPU initiates a DMA transfer command through the channel interface. Then the command is enqueued in the DMA controller (DMAC) which can serve at maximum  pending requests.

  Figure . -IBM Cell processor DMA controller

  Figure . -Image stored in memory

  Figure . -DMA transfers

  u∈U e(u) = s(u) + (u) ■ Precedence relations: No task can start before the finish of its predecessors. (u,u ′ )∈E e(u) ≤ s(u ′ ) ■ Non-overlapped execution on a processor: Tasks running on same processor should not overlap in time.

  Figure . -Pareto points

Figure

  Figure . -Forward and backward cones

  Figure . shows a sample exploration of design space for two costsnumber of processors used and latency of the schedule (we ignored the communication cost).

Figure  .

  Figure . -(a) Sets C 0 (unsat) and C 1 (sat) represented by their extremal points C 0 and C 1 ; (b) The state of our knowledge at this point as captured by C 0 (infeasible costs) C 1 (feasible costs) and C (unknown). The actual Pareto front is contained in the closure of C.

Figure

  Figure . -Exploring the cost space via grid refinement. The dark points indicate the new candidates for exploration after each refinement.

  p to C max p , where C min p and C max p are the lower and upper bound respectively for exploration in dimension p.

  Figure . -Structure of StreamExplorer

  Figure . -FIFO token example for actors A and B with buffer size = 

  and buffer size b AB = 2.

  Figure .(a) shows how the FIFO buffer is allocated in the local memory of the processor andFigure .(b) shows an execution of this example. We use the notation i nd ex state for the status record. The execution happens as follows:

cha pte r 6

 6 Sc he duli ng i n s ha re d m e m o ryThis chapter deals with the scheduling problem in shared memory multi-processors using SMT solvers and a technique to eliminate the symmetry.

  Figure . an integer label on the edge from A to B means that every executed instance of task A spawns instances of task B. Likewise, a 1/ label on the edge from B to C means that all those instances of B should terminate and their outputs be joined before executing C. The derived task graph can thus be viewed as obtained from the split-join graph by making data parallelism   chapt e r . sche dulin g in share d me mory explicit (see Figure .).

Figure

  Figure . -Illustration of the lexicographic ordering theorem

■

  Completion time and precedence: e(u) is the time when task u terminates and a task cannot start before the termination of its predecessors. u∈U e(u) = s(u) + (u) ∧ (u,u ′ )∈E e(u) ≤ s(u ′ ) ■ Mutual exclusion: tasks running on same processor should not overlap in time.

  u

  Figure . -Time to find optimal latency as a function of the number of tasks for 5 and 20 processors.

  Figure . -Exploration time to find optimal latency as a function of the number of tasks and processors.

  Figure . depicts the results obtained with and without symmetry breaking constraints.

  Figure . -Result of Pareto exploration for = 30

  Figure . -Multi-stage design flow

■

  Unique cluster for every soft cluster: No two soft clusters should be placed on the same cluster: a,b∈Z : a b x(a) x(b) ■ Communication costs between soft clusters: The distance aware communication cost (a, b) between two soft clusters a,b is the weighted sum of the communication between respective actors with the weight given by the distance between the clusters. a,b∈Z

■

  Total communication cost: The total communication cost is the sum of communication costs of all the soft clusters. It is a cost constraint which is subject to minimization. a,b∈Z:a b (a, b) ≤ C

  Figure . -Communicating tasks

Figure  .

  Figure . -Partition aware communicating tasks

  Figure . shows an application graph channel and Figure . shows its partition-aware graph for the case where actors A and B are assigned to different soft clusters.

Edge

  Parameters Edge-writer Edge-reader e wt ( ê) [1, w ↑ ( ê)] v I wr ( ê) e wn ( ê) [1] I wr ( ê) G wr ( ê) e rt ( ê) [ ( ê), ( ê)] G wr ( ê) v ′ A B e : [ (e), (e)] e be (e) : [ -1 (e), 0, b(e)]

Figure  ., 0

 0 Figure . -Buffer aware graph model for a channel without DMA

  Figure . unfolded for three actor instances: A 0 , A 1 , A 2 . ■ A 0 executes and consumes one space token. ■ At the end, A 0 triggers an initialization of DMA transfer, modeled by I wr0 ■ Data is sent to the network, which is represented by G wr0 . In parallel, A 1 picks the second space token and triggers another DMA transfer: I wr1 and G wr1 .

■US

  = U S T ∪ U S C is the task partitioning into: ⋄ transfer tasks U S T , derived from DMA transfer actors: I wr , G wr I rd , and G rd . ⋄ computation tasks U S C ■ I (u) are the transfer tasks connected to the output of task u, by analogy to I(v) of the computation-aware graph. ■ U S

■

  Extra constraints:In our implementation we require the writer and reader sub-buffers to have equal buffer memory: ê∈E M Z b(e wt ( ê)) • (e wt ( ê)) = b(e rt ( ê)) • (e rt ( ê))

Figure

  Figure . - scheduling solutions for  partitioning solutions

Figure  .

  Figure . -Jpeg decoder solutions measured on Kalray platform

Figure  .

  Figure . -Application benchmarks: summary of results

cha pte r 8

 8 Op t i m i z i ng t he DMA c o m m uni c at i o nThis chapter introduces the DMA transfer granularity optimization for data parallel computations with regular memory access patterns.

Figure

  Figure . -Contiguous vs periodic allocation of data

Figure

  Figure . -Distribution of D data of same size, but different shapes

Figure  .

  Figure . -Influence of block shape on the amount of shared data

■

  Computation Regime: In this case, the computation time dominates the transfer time C > T, shown in Figure .(a). ■ Transfer Regime: Here the transfer time dominates the computation time C ≤ T, shown in Figure .(b).

Figure

  Figure . -Pipelined execution double buffering on one processor

  Figure . -Regimes depending on the block size

Figure

  Figure . -Rectangular blocks: (a) computation and transfer domains, (b) optimal granularity candidates and optimal granularity.

Figure

  Figure . -The dependence of computation C and transfer T on the granularity (s 1 , s 2 ).

  Figure . (assuming > I 1 ). Similarly, the intersection of these two surfaces separates the domain of (s 1 , s 2 ) into two sub-domains, the computation domain where T < C and the transfer domain where T > C, see Figure ..

  Figure . -Pipelined execution in the transfer regime using multiple processors

Figure  .

  Figure . -Evolution of the computation domain and optimal granularity as we increase the number of processors

  Figure . -DMA performance for contiguous blocks

  Figure . -Independent data computations

Figure  .

  Figure . -Measurements for shared data in computation regime

Figure  .

  Figure . -Convolution algorithm

  Figure . -Predicted transfer time for different block shapes with shared data

  Block height s 1 Pipeline total execution time (cycles)meas s 1 × s 2 = 1K pred s 1 × s 2 = 1K (a) s 1 × s 2 = 1024

Figure  .

  Figure . -Predicted and measured values for different combinations of s 1 × s 2

cha pte r 9

 9 Run-t i m e a p p li c at i o n m a nag e m e nt a nd re c o nf i g urat i o n

  Figure . -Run-time resource manager (conceptual view).

Figure

  Figure . -Actor migration (Steps performed by resource manager. For steps (), (), () etc. refer to Table .).

  Figure . -Measured and predicted reconfiguration times

  Figure . which indicates that the three actors VLD, IQ/IDCT and CC are running on tile . As a first reconfiguration, the IQ/IDCT actor is migrated to tile . The left-most bar in Figure . shows the run-time (in clock-cycles) needed to perform this reconfiguration. This run-time is measured using an actual implementation of our run-time reconfiguration mechanism on the CompSOC platform. The squared box above the bar indicates the worst-case reconfiguration time as computed using the run-times listed in Table . and Table .. The next bar in Figure . shows the time needed to migrate the CC actor to tile  (configuration ,, to configuration ,,). The other bars indicate other reconfiguration options that have been tested. Each time the label left to the bar indicates the configuration prior to the reconfiguration. The top part of Figure . shows that the reconfiguration time is dominated by step . The bottom part of Figure . shows the run-time of the reconfiguration process when excluding step .

aFigure

  Figure A. -Gantt chart for schedule XML

  is a -core heterogeneous multi-core architecture, consisting of a Power Processor Element (PPE) linked to  Synergistic Process-ing Elements (SPE) acting as coprocessors, connected through internal high speed Element Interconnect Bus (EIB) as shown in Figure ..

		SPU (Synergistic Processor Unit)		SPE (Synergistic Processor Element)	SPE		SPE	SPE
		LS	MFC (Memory
		(Local Store)	Flow Controller)
	PPE
	(PowerPC Processor		EIB (Element Interconnect Bus)
	Element)
	PPU (PowerPC Processor Unit)	MIC (Memory Interface Controller)	SPE	SPE	SPE	SPE	BIC (Bus Interface Controller)

Table  .

   provides us the summary of parameters that has been used in this work for the respective architectures.

	Parameter	Symbol	Unit	IBM Cell Tilera TILE Kalray MPPA
	Number Of Clusters Proc. Per cluster	|X| M	Number Number	 	 	 
	On-chip memory per cluster		Bytes	 kB	. MB	 MB
	DMA Per Cluster	D	Number			
	DMA Init. Time	I	Cycles			
	DMA Cost per byte	g	Cycles per byte	.		.
	DMA Completion time		Cycles per transfer			

Table  .

   -Summary of hardware platform parameters

Table  .

 

		Actor	Execution Time
	1)	V LD F etch L I D CT L	300 • x 150 130
	1/x (8)	Mc L Chr -Spli t F etch C	100 40 300
	1/4 (2)	I D CT C U pscale	260 40
		Mc C	200
		Chr -J oi n Color	30 680 • x
	Figure . -Video decoder example

 -Execution times

Table  .

   -Application benchmark characteristics

	BenchMark	#Actors #Channels #Tasks	Total Exec. Time (cycles)	Total Comm. Data (bytes)
	JPEG Decoder					
	Beam Former					
	Insertion Sort					
	Merge Sort					
	Radix Sort					
	Dct					
	Dct					
	Dct					
	Dct					
	Dct					
	Dct					
	Dct					
	Dct					
	Dct Coarse					
	Dct Fine					
	Comparison Count					
	Matrix multiplication					
	Fft					

Table  .

   -Jpeg decoder : Partitioning step solutions

	Allocated soft cluster Solution VLD IQ Color	Exploration Cost C C C Z

  pref etch 1 pref etch 2 pref etch 3 pref etch 4 pref etch 5 wri teback 1 wri teback 2 wri teback 3 wri teback 4 wri teback 5

							s=
	Output Transfer	Prologue				wri teback 0	wri teback 1	wri teback 2
	Computation	i d le			compute 0	compute 1	compute 2	i d le
	Input Transfer	pref etch 0	pref etch 1	pref etch 2	Epilogue
						Time
					(a) Computation Regime
							s=
	Output Transfer Computation Input Transfer	Prologue pref etch 0 i d le	compute 0	Time compute 3 wri teback 0 (b) Transfer Regime compute 1 compute 2	compute 4	Epilogue compute 5 i d le

Table  .

   -DMA performance for contiguous blocks

Table  .

   -Actor migration overhead (in clock cycles).

	Step Description	Master	Slave
	()	Instruct application RM to reconfigure		n/a
	()	Request removal of application from TDM		
	()	Remove application from TDM and ack.	App. dependent
	()	Resize TDM allocation		
	(/) Add/remove FIFO

Table  .

   Table .

	()	Add application to TDM		
	()	Inform system RM about completion		n/a

Table  .

   -FIFO add/remove overhead (in clock cycles).

	Src	Master Master Slave Slave- Slave-
	Destination	Master Slave Master Slave- Slave-
	Time to remove FIFO					
	Time to add FIFO					