{'fraction_non_alphanumeric': 0.026563029686667634, 'fraction_numerical': 0.005617705457891423, 'mean_word_length': 4.702706434686551, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Evolutionary Acyclic Graph Partitioning

Directed graphs are widely used to model data flow and execution dependencies in streaming applications. This enables the utilization of graph partitioning algorithms for the problem of parallelizing computation for multiprocessor architectures. However due to resource restrictions, an acyclicity constraint on the partition is necessary when mapping streaming applications to an embedded multiprocessor. Here, we contribute a multi-level algorithm for the acyclic graph partitioning problem. Based on this, we engineer an evolutionary algorithm to further reduce communication cost, as well as to improve load balancing and the scheduling makespan on embedded multiprocessor architectures.


Practical Motivation
Computer vision and imaging applications have high demands for computational power. However, these applications often need to run on embedded devices with severely limited compute resources and a tight thermal budget. This requires the use of specialized hardware and a programming model that allows to fully utilize the compute resources.
The context of this research is the development of specialized processors at Intel Corporation for advanced imaging and computer vision. In particular, our target platform is a heterogeneous multiprocessor architecture that is currently used in Intel processors. Several VLIW processors with vector units are available to exploit the abundance of data parallelism that typically exists in imaging algorithms. The architecture is designed for low power and typically has small local program and data memories. To cope with memory constraints, it is necessary to break the application, which is given as a directed dataflow graph, into smaller blocks that are executed one after another. The quality of this partitioning has a strong impact on performance. It is known that the problem is NP-complete [22] and that there is no constant factor approximation algorithm for general graphs [22]. Therefore heuristic algorithms are used in practice.
We contribute (a) a new multi-level approach for the acyclic graph partitioning problem, (b) based on this, a coarse-grained distributed evolutionary algorithm, (c) an objective function that improves load balancing on the multiprocessor architecture and (d) an evaluation on a large set of graphs and a real application. Our focus is on solution quality, not algorithm running time, since these partitions are typically computed once before the application is compiled. The rest of the paper is organized as follows: we present all necessary background information on the application graph and hardware in Section 2 and then briefly introduce the notation and related work in Section 3. Our new multi-level approach is described in Section 4. We illustrate the evolutionary algorithm that provides multi-level recombination and mutation operations, as well as a novel fitness function in Section 5. The experimental evaluation of our algorithms is found in Section 6. We conclude in Section 7.

Background
Computer vision and imaging applications can often be expressed as stream graphs where nodes represent tasks that process the stream data and edges denote the direction of the dataflow. Industry standards like OpenVX [13] specify stream graphs as Directed Acyclic Graphs (DAG). In this work, we address the ( Fig. 1. Subfigure (a) shows an invalid partition with minimal edge cut, but a bidirectional connection between blocks and thus a cycle in the quotient graph. A valid partitioning with minimal edge cut is shown in (b).
problem of mapping the nodes of a directed acyclic stream graph to the processors of an embedded multiprocessor. The nodes of the graph are kernels (small, self-contained functions) that are annotated with code size while edges are annotated with the amount of data that is transferred during one execution of the application. The processors of the hardware platform have a private local data memory and a separate program memory. A direct memory access controller (DMA) is used to transfer data between the local memories and the external DDR memory of the system. Since the data memories only have a size in the order of hundreds of kilobytes they can only store a small portion of the image. Therefore the input image is divided into tiles. The mode of operation of this hardware usually is that the graph nodes are assigned to processors and process the tiles one after the other. However, this is only possible if the program memory size is sufficient to store all kernel programs. For the hardware platform under consideration it was found that this is not the case for more complex applications such as a Local Laplacian filter [24]. Therefore a gang scheduling [10] approach is used where the kernels are divided into groups of kernels (referred to as gangs) that do not violate memory constraints. Gangs are executed one after another on the hardware. After each execution, the kernels of the next gang are loaded. At no time any two kernels of different gangs are loaded in the program memories of the processors at the same time. Thus all intermediate data that is produced by the current gang but is needed by a kernel in a later gang needs to be transferred to external memory.
A strict ordering of gangs is required, because data can only be consumed in the same gang where it was produced and in gangs that are scheduled at a later point in time. If this does not hold, there is no valid temporal order in which the gangs can be executed on the platform. Such a partitioning is called acyclic because the quotient graph, which is created by contracting all nodes that are assigned to the same gang into a single node, does not contain a cycle for a valid acyclic partitioning. Figure 1 shows an example for an invalid and a valid partitioning.
Memory transfers, especially to external memories, are expensive in terms of power and time. Thus it is crucially important how the assignment of kernels to gangs is done, since it will affect the amount of data that needs to be transferred. In this work, we develop a multi-level approach to enhance our previous results.

Preliminaries
Basic Concepts. Let G = (V = {0, . . . , n − 1}, E, c, ω) be a directed graph with edge weights ω : E → R >0 , node weights c : V → R ≥0 , n = |V |, and m = |E|. We extend c and ω to sets, i.e., c(V ) := v∈V c(v) and ω(E ) := e∈E ω(e). We are looking for blocks of nodes V 1 ,. . . ,V k that partition V , i.e., . If a node v has a neighbor in a block different of its own block then both nodes are called boundary nodes. An abstract view of the partitioned graph is the so-called quotient graph, in which nodes represent blocks and edges are induced by connectivity between blocks. The weighted version of the quotient graph has node weights which are set to the weight of the corresponding block and edge weights which are equal to the weight of the edges that run between the respective blocks.
A matching M ⊆ E is a set of edges that do not share any common nodes, i.e., the graph (V, M ) has maximum degree one. Contracting an edge (u, v) means to replace the nodes u and v by a new node x connected to the former neighbors of u and v, as well as connecting nodes that have u and v as neighbors to x. We set c(x) = c(u) + c(v) so the weight of a node at each level is the number of nodes it is representing in the original graph. If replacing edges of the form (u, w),(v, w) would generate two parallel edges (x, w), we insert a single edge with ω((x, w)) = ω((u, w)) + ω((v, w)). Uncontracting an edge e undoes its contraction. In order to avoid tedious notation, G will denote the current state of the graph before and after a (un)contraction unless we explicitly want to refer to different states of the graph. Problem Definition. In our context, partitions have to satisfy two constraints: a balancing constraint and an acyclicity constraint. The balancing constraint demands that ∀i ∈ {1..k} : c(V i ) ≤ L max := (1 + ) c(V ) k for some imbalance parameter ≥ 0. The acyclicity constraint mandates that the quotient graph is acyclic. The objective is to minimize the total edge cut i, The directed graph partitioning problem with acyclic quotient graph (DGPAQ) is then defined as finding a partition Π := {V 1, . . . , V k } that satisfies both constraints while minimizing the objective function. In the undirected version of the problem the graph is undirected and no acyclicity constraint is given.
Multi-level Approach. The multi-level approach to undirected graph partitioning consists of three main phases. In the contraction (coarsening) phase, the algorithm iteratively identifies matchings M ⊆ E and contracts the edges in M . The result of the contraction is called a level. Contraction should quickly reduce the size of the input graph and each computed level should reflect the global structure of the input network. Contraction is stopped when the graph is small enough to be directly partitioned. In the refinement phase, the matchings are iteratively uncontracted. After uncontracting a matching, a refinement algorithm moves nodes between blocks in order to improve the cut size or balance. The intuition behind this approach is that a good partition at one level will also be a good partition on the next finer level, so local search converges quickly.
Relation to Scheduling. Graph partitioning is a sub-step in our scheduling heuristic for the target hardware platform. We use a first pass of the graph partitioning heuristic with L max set to the size of the program memory to find a good composition of kernels into programs with little interprocessor communication. The resulting quotient graph is then used in a second pass where L max is set to the total number of processors in order to find scheduling gangs that minimize external memory transfers. In this second step the acyclicity constraint is crucially important. Note that in the first pass, the constraint can in principle be dropped. However, this yields programs with interdependencies that need to be scheduled in the same gang during the second pass. We found that this often leads to infeasible inputs for the second pass.
While the balancing constraint ensures that the size of the programs in a scheduling gang does not exceed the program memory size of the platform, reducing the edge cut will improve the memory bandwidth requirements of the application. The memory bandwidth is often the bottleneck, especially in embedded systems. A schedule that requires a large amount of transfers will neither yield a good throughput nor good energy efficiency [23]. However, in our previous work, we found that our graph partitioning heuristic while optimizing edge cut occasionally makes a bad decision concerning the composition of gangs. Ideally, the programs in a gang all have equal execution times. If one program runs considerably longer than the other programs, the corresponding processors will be idle since the context switch is synchronized. In this work, we try to alleviate this problem by using a fitness function in the evolutionary algorithm that considers the estimated execution times of the programs in a gang.
After partitioning, a schedule is generated for each gang. Since partitioning is the focus of this paper, we only give a brief outline. The scheduling heuristic is a single appearance list scheduler (SAS). In a SAS, the code of a function is never duplicated, in particular, a kernel will never execute on more than one processor. The reason for using a SAS is the scarce program memory. List schedulers iterate over a fixed priority list of programs and start the execution if the required input data and hardware resources for a program are available. We use a priority list sorted by the maximum length of the critical path which was calculated with estimated execution times. Since kernels perform mostly data-independent calculations, the execution time can be accurately predicted from the input size which is known from the stream graph and schedule.
Related Work. There has been a vast amount of research on the undirected graph partitioning problem so that we refer the reader to [29,3,4] for most of the material. Here, we focus on issues closely related to our main contributions. All general-purpose methods for the undirected graph partitioning problem that are able to obtain good partitions for large real-world graphs are based on the multi-level principle. The basic idea can be traced back to multigrid solvers for systems of linear equations [30] but more recent practical methods are based on mostly graph theoretical aspects, in particular edge contraction and local search. For the undirected graph partitioning problem, there are many ways to create graph hierarchies such as matchingbased schemes [32,18,25] or variations thereof [1] and techniques similar to algebraic multigrid, e.g. [20]. However, as node contraction in a DAG can introduce cycles, these methods can not be directly applied to the DAG partitioning problem. Well-known software packages for the undirected graph partitioning problem that are based on this approach include Jostle [32], KaHIP [27], Metis [18] and Scotch [7]. However, none of these tools can partition directed graphs under the constraint that the quotient graph is a DAG. Very recently, Hermann et al. [14] presented the first multi-level partitioner for DAGs. The algorithm finds matchings such that the contracted graph remains acyclic and uses an algorithm comparable to Fiduccia-Mattheyses algorithm [11] for refinement. Neither the code nor detailed results per instance are available at the moment.
Gang scheduling was originally introduced to efficiently schedule parallel programs with fine-grained interactions [10]. In recent work, this concept has been applied to schedule parallel applications on virtual machines in cloud computing [31] and extended to include hard real-time tasks [12]. An important difference to our work is that in gang scheduling all tasks that exchange data with each other are assigned to the same gang, thus there is no communication between gangs. In our work, the limited program memory of embedded platforms does not allow to assign all kernels to the same gang. Therefore, there is communication between gangs which we aim to minimize by employing graph partitioning methods.
Another application area for graph partitioning algorithms that does have a constraint on cyclicity is the temporal partitioning in the context of reconfigurable hardware like field-programmable gate arrays (FPGAs). These are processors with programmable logic blocks that can be reprogramed and rewired by the user. In the case where the user wants to realize a circuit design that exceeds the physical capacities of the FPGA, the circuit netlist needs to be partitioned into partial configurations that will be realized and executed one after another. The first algorithms for temporal partitioning worked on circuit netlists expressed as hypergraphs. Now, algorithms usually work on a behavioral level expressed as a regular directed graph. The proposed algorithms include list scheduling heuristics [5] or are based on graph-theoretic theorems like max-flow min-cut [16], with objective functions ranging from minimizing the communication cost incurred by the partitioning [5,16] to reducing the length of the critical path in a partition [5,17]. Due to the different nature of the problem and different objectives, a direct comparison with these approaches is not possible.
The algorithm proposed in [6] partitions a directed, acyclic dataflow graph under acyclicity constraints while minimizing buffer sizes. The authors propose an optimal algorithm with exponential complexity that becomes infeasible for larger graphs and a heuristic which iterates over perturbations of a topological order. The latter is comparable to our initial partitioning and our first refinement algorithm. We see in the evalu-ation that moving to a multi-level and evolutionary algorithm clearly outperforms this approach. Note that minimizing buffer sizes is not part of our objective. Multi-level techniques have been widely used in the field of graph partitioning for undirected graphs. We now transfer the techniques used in the KaFFPa multi-level algorithm [27] to a new algorithm that is able to tackle the DAG partitioning problem. More precisely, to obtain a multi-level DAG partitioning algorithm, we integrate local search algorithms that keep the quotient graph acyclic and handle problems that occur when coarsening a DAG.
Before we give an in-depth description, we present an overview of the algorithm (see also Figure 2). Recall that a multi-level graph partitioner has three phases: coarsening, initial partitioning and uncoarsening. In contrast to classic multi-level algorithms, our algorithm starts to construct a solution on the finest level of the hierarchy and not with the coarsening phase. This is necessary, since contracting matchings can create coarser graphs that contain cycles, and hence it may become impossible to find feasible solutions on the coarsest level of the hierarchy. After initial partitioning of the graph, we continue to coarsen the graph until it has no matchable edges left. During coarsening, we transfer the solution from the finest level through the hierarchy and use it as initial partition on the coarsest graph. As we will see later, since the partition on the finest level has been feasible, i.e. acyclic and balanced, so will be the partition that we transferred to the coarsest level. The coarser versions of the input graph may still contain cycles, but local search maintains feasibility on each level and hence, after uncoarsening is done, we obtain a feasible solution on the finest level. The rest of the section is organized as follows. We begin by reviewing the construction algorithm that we use, continue with the description of the coarsening phase and then recap local search algorithms for the DAG partitioning problem that are now used within the multi-level approach.

Initial Partitioning
Recall that our algorithm starts with initial partitioning on the finest level of the hierarchy. Our initial partitioning algorithm [22], creates an initial solution based on a topological ordering of the input graph and then applies a local search strategy to improve the objective of the solution while maintaining both constraintsbalance and acyclicity.
More precisely, the initial partitioning algorithm computes a random topological ordering of nodes using a modified version of Kahn's algorithm with randomized tie-breaking. The algorithm maintains a list S with all nodes that have indegree zero and an initially empty list T . It then repeatedly removes a random node n from list S, removes n from the graph, updates S by potentially adding further nodes with indegree zero and adds n to the tail of T . Using list T , we can now derive initial solutions by dividing the graph into blocks of consecutive nodes w.r.t to the ordering. Due to the properties of the topological ordering, there is no node in a block V j that has an outgoing edge ending in a block V i with i < j. Hence, the quotient graph of the solution is cycle-free. In addition, the blocks are chosen such that the balance constraint is fulfilled. The initial solution is then improved by applying a local search algorithm. Since the construction algorithm is randomized, we run the heuristics multiple times using different random seeds and pick the best solution afterwards. We call this algorithm single-level algorithm.

Coarsening
Our coarsening algorithm makes contraction more systematic by separating two issues [27]: A rating function indicates how much sense it makes to contract an edge based on local information. A matching algorithm tries to maximize the summed ratings of the contracted edges by looking at the global structure of the graph. While the rating function allows a flexible characterization of what a "good" contracted graph is, the simple, standard definition of the matching problem allows to reuse previously developed algorithms for weighted matching. Matchings are contracted until the graph is "small enough". In [15], the rating function expansion * 2 (u, v) := ω(u,v) 2 c(u)c(v) works best among other edge rating functions, so that we also use this rating function for the DAG partitioning problem.
As in KaFFPa [27], we employ the Global Path Algorithm (GPA) as a matching algorithm. We apply the matching algorithm on the undirected graph that is obtained by interpreting each edge in the DAG as undirected edge without introducing parallel edges. The GPA algorithm was proposed by Maue and Sanders [19] as a synthesis of the Greedy algorithm and the Path Growing Algorithm [9]. This algorithm achieves a half-approximation in the worst case, but empirically, GPA gives considerably better results than Sorted Heavy Edge Matching and Greedy (for more details see [15]). The GPA algorithm scans the edges in order of decreasing weight but rather than immediately building a matching, it first constructs a collection of paths and even cycles, and for each of those computes optimal solutions.
Recall that our algorithm starts with a partition on the finest level of the hierarchy. Hence, we set cut edges not to be eligible for the matching algorithm. This way edges that run between blocks of the given partition are not contracted. Thus the given partition can be used as a feasible initial partition of the coarsest graph. The partition on the coarsest level has the same balance and cut as the input partition. Additionally, it is also an acyclic partition of the coarsest graph. Performing coarsening by this method ensures nondecreasing partition quality, if the local search algorithm guarantees no worsening. Moreover, this allows us to use standard weighted matching algorithms, instead of using more restricted matching algorithms that ensure that the contracted graph is also a DAG. We stop contraction when no matchable edge is left.

Local Search
Recall that the refinement phase iteratively uncontracts the matchings contracted during the first phase. Due to the way contraction is defined, a partitioning of the coarse level creates a partitioning of the finer graph with the same objective and balance, moreover, it also maintains the acyclicity constraint on the quotient graph. After a matching is uncontracted, local search refinement algorithms move nodes between block boundaries in order to improve the objective while maintaining the balancing and acyclicity constraint. We use the local search algorithms of Moreira et al. [22]. We give an indepth description of the algorithms in Appendix A and shortly outline them here. All algorithms identify movable nodes which can be moved to other blocks without violating any of the constraints. Based on a topological ordering, the first algorithm uses a sufficient condition which can be evaluated quickly to check the acyclicity constraint. Since the first heuristic can miss possible moves by solely relying upon a sufficient condition, the second heuristic [22] maintains a quotient graph during all iterations and uses Kahn's algorithm to check whether a move creates a cycle in it. The third heuristic combines the quick check for acyclicity of the first heuristic with an adapted Fiduccia-Mattheyses algorithm [11] which gives the heuristic the ability to climb out of a local minimum.

Evolutionary Components
Evolutionary algorithms start with a population of individuals, in our case partitions of the graph, which are created by our multi-level algorithm using different random seeds. It then evolves the population into different populations over several rounds using recombination and mutation operations. In each round, the evolutionary algorithm uses a two-way tournament selection rule [21] based on the fitness of the individuals of the population to select good individuals for recombination or mutation. Here, the fittest out of two distinct random individuals from the population is selected. We focus on a simple evolutionary scheme and generate one offspring per generation. When an offspring is generated, we use an eviction rule to select a member of the population and replace it with the new offspring. In general, one has to take both, the fitness of an individual and the distance between individuals in the population, into consideration [2]. We evict the solution that is most similar to the offspring among those individuals in the population that have a cut worse or equal to the cut of the offspring itself. The difference of two individuals is defined as the size of the symmetric difference between their sets of cut edges.
We now explain our multi-level recombine and mutation operators. Our recombine operator ensures that the partition quality, i.e. the edge cut, of the offspring is at least as good as the best of both parents. For our recombine operator, let P 1 and P 2 be two individuals from the population. Both individuals are used as input for our multi-level DAG partitioning algorithm in the following sense. Let E be the set of edges that are cut edges, i.e. edges that run between two blocks, in either P 1 or P 2 . All edges in E are blocked during the coarsening phase, i.e. they are not contracted during the coarsening phase. In other words, these edges are not eligible for the matching algorithm used during the coarsening phase and therefore are not part of any matching computed. As before, the coarsening phase of the multi-level scheme stops when no contractable edge is left. As soon as the coarsening phase is stopped, we apply the better out of both input partitions w.r.t to the objective to the coarsest graph and use this as initial partitioning. We use random tie-breaking if both input individuals have the same objective value. This is possible since we did not contract any cut edge of P. Again, due to the way coarsening is defined, this yields a feasible partition for the coarsest graph that fulfills both constraints (acyclicity and balance) if the input individuals fulfill those.
Note that due to the specialized coarsening phase and specialized initial partitioning, we obtain a high quality initial solution on a very coarse graph. Since our local search algorithms guarantee no worsening of the input partition and use random tie breaking, we can assure nondecreasing partition quality. Also note that local search algorithms can effectively exchange good parts of the solution on the coarse levels by moving only a few nodes. Due to the fact that our multi-level algorithms are randomized, a recombine operation performed twice using the same parents can yield a different offspring. Each time we perform a recombine operation, we choose one of the local search algorithms described in Section 4.3 uniformly at random.
Cross Recombine. This operator recombines an individual of the population with a partition of the graph that can be from a different problem space, e.g. a k -partition of the graph. While P 1 is chosen using tournament selection as before, we create P 2 in the following way. We choose k uniformly at random in [k /4, 4k] and uniformly at random in [ , 4 ]. We then create P 2 (a k -partition with a relaxed balance constraint) by using the multi-level approach. The intuition behind this is that larger imbalances reduce the cut of a partition and using a k -partition instead of k may help us to discover cuts in the graph that otherwise are hard to discover. Hence, this yields good input partitions for our recombine operation.
Mutation. We define two mutation operators. Both mutation operators use a random individual P 1 from the current population. The first operator starts by creating a k-partition P 2 using the multi-level scheme. It then performs a recombine operation as described above, but not using the better of both partitions on the coarsest level, but P 2 . The second operator ensures nondecreasing quality. It basically recombines P 1 with itself (by setting P 2 = P 1 ). In both cases, the resulting offspring is inserted into the population using the eviction strategy described above.
Fitness Function. Recall that the execution of programs in a gang is synchronized. Therefore, a lower bound on the gang execution time is given by the longest execution time of a program in a gang. Pairing programs with short execution times with a single long-running program leads to a bad utilization of processors, since the processors assigned to the short-running programs are idle until all programs have finished. To avoid these situations, we use a fitness function that estimates the critical path length of the entire application by identifying the longest-running programs per gang and summing their execution times. This will result in gangs, where long-running programs are paired with other long-running programs. More precisely, the input graph is annotated with execution times for each node that were obtained by profiling the corresponding kernels on our target hardware. The execution time of a program is calculated by accumulating the execution times for all firings of its contained kernels. The quality of a solution to the partitioning problem is then measured by the fitness function which is a linear combination of the obtained edge cut and the critical path length. Note, however, that the recombine and mutation operations still optimize for cuts.
Miscellanea. We follow the parallelization approach of [28]: Each processing element (PE) has its own population and performs the same operations using different random seeds. The parallelization / communication protocol is similar to randomized rumor spreading [8]. We follow the description of [28] closely: A communication step is organized in rounds. In each round, a PE chooses a communication partner uniformly at random among those who did not yet receive P and sends the current best partition P of the local population. Afterwards, a PE checks if there are incoming individuals and if so inserts them into the local population using the eviction strategy described above. If P is improved, all PEs are again eligible.

Experimental Evaluation
System. We have implemented the algorithms described above within the KaHIP [27] framework using C++. All programs have been compiled using g++ 4.8.0 with full optimizations turned on (-O3 flag) and 32 bit index data types. We use two machines for our experiments: machine A has two Octa-Core Intel Xeon E5-2670 processors running at 2.6 GHz with 64 GB of local memory. We use this machine in Section 6.1. Machine B is equipped with two Intel Xeon X5670 Hexa-Core processors (Westmere) running at a clock speed of 2.93 GHz. The machine has 128 GB main memory, 12 MB L3-Cache and 6×256 KB L2-Cache. We use this machine in Section 6.2. Henceforth, a PE is one core.
Methodology. We mostly present two kinds of data: average values and plots that show the evolution of solution quality (convergence plots). In both cases we perform multiple repetitions. The number of repetitions is dependent on the test that we perform. Average values over multiple instances are obtained as follows: for each instance (graph, k), we compute the geometric mean of the average edge cut for each instance. We now explain how we compute the convergence plots, starting with how they are computed for a single instance I: whenever a PE creates a partition, it reports a pair (t, cut) where the timestamp t is the current elapsed time on the particular PE and cut refers to the cut of the partition that has been created. When performing multiple repetitions, we report average values (t, avgcut) instead. After completion of the algorithm, we have P sequences of pairs (t, cut) which we now merge into one sequence. The merged sequence is sorted by the timestamp t. The resulting sequence is called T I . Since we are interested in the evolution of the solution quality, we compute another sequence T I min . For each entry (in sorted order) in T I we insert the entry (t, min t ≤t cut(t )) into T I min . Here min t ≤t cut(t ) is the minimum cut that occurred until time t. N I min refers to the normalized sequence, i.e. each entry (t, cut) in T I min is replaced by (t n , cut) where t n = t/t I and t I is the average time that the multi-level algorithm needs to compute a partition for the instance I. To obtain average values over multiple instances we do the following: for each instance we label all entries in N I min , i.e. (t n , cut) is replaced by (t n , cut, I). We then merge all sequences N I min and sort by t n . The resulting sequence is called S. The final sequence S g presents event based geometric averages values. We start by computing the geometric mean cut value G using the first value of all N I min (over I). To obtain S g , we sweep through S: for each entry (in sorted order) (t n , c, I) in S we update G, i.e. the cut value of I that took part in the computation of G is replaced by the new value c, and insert (t n , G) into S g . Note that c can be only smaller or equal to the old cut value of I.
Instances. We use the algorithms under consideration on a set of instances from the Polyhedral Benchmark suite (PolyBench) [26] which have been kindly provided by Hermann et al. [14]. In addition, we use an instance of Moreira [22]. Basic properties of the instances can be found in Appendix Table 2.

Evolutionary DAG Partitioning with Cut as Objective
We will now compare the different proposed algorithms. Our main objective in this section is the cut objective. In our experiments, we use the imbalance parameter = 3%. We use 16 PEs of machine A and two hours of time per instance when we use the evolutionary algorithm. We parallelized repeated executions of multi-and single-level algorithms since they are embarrassingly parallel for different seeds and also gave 16 PEs and two hours of time to each of the algorithms. Each call of the multi-level and singlelevel algorithm uses one of our local search algorithms at random and a different random seed. We look at k ∈ {2, 4, 8, 16, 32} and performed three repetitions per instance. Figure 3 shows convergence and performance plots and Tables 3, 4 in the Appendix show detailed results per instance. To get a visual impression of the solution quality of the different algorithms, Figure 3 also presents a performance plot using all instances (graph, k). A curve in a performance plot for algorithm X is obtained as follows: For each instance, we calculate the ratio between the best cut obtained by any of the considered algorithms and the cut for algorithm X. These values are then sorted.
First of all, the performance plot in Figure 3 indicates that our evolutionary algorithm finds significantly smaller cuts than the single-and multi-level scheme. Using the multi-level scheme instead of the singlelevel scheme already improves the result by 10% on average. This is expected since using the multi-level scheme introduces a more global view to the optimization problem and the multi-level algorithm starts from a partition created by the single-level algorithm (initialization algorithm + local search). In addition, the evolutionary algorithm always computes a better result than the single-level algorithm. This is true for the average values of the repeated runs as well as the achieved best cuts. The single-level algorithm computes average cuts that are 42% larger than the ones computed by the evolutionary algorithm and best cuts that are 47% larger than the best cuts computed by the evolutionary algorithm. As anticipated, the evolutionary algorithm computes the best result in almost all cases. In three cases the best cut is equal to the multi-level, and in three other cases the result of the multi-level algorithm is better (at most 3%, e.g. for k = 2, covariance). These results are due to the fact that we already use the multi-level algorithm to initialize the population of the evolutionary algorithm. In addition, after the initial population is built, the recombine and mutation operations can successfully improve the solutions in the population further and break out of local minima (see Figure 3). Average cuts of the evolutionary algorithm are 29% smaller than the average cuts computed by the multi-level algorithm (and 33% in case of best cuts). The largest improvement of the evolutionary algorithm over the single-and multi-level algorithm is a factor 39 (for k = 2, 3mm0). Table 1 shows how improvements are distributed over different values of k. Interestingly, in contrast to evolutionary algorithms for the undirected graph partitioning problem, e.g. [28], improvements to the multi-level algorithm do not increase with increasing k. Instead, improvements more diversely spread over different values of k. We believe that the good performance of the evolutionary algorithm is due to a very fragmented search space that causes local search heuristics to easily get trapped in local minima, especially since local search algorithms maintain the feasibility on the acyclicity constraint. Due to mutation and recombine operations, our evolutionary algorithm escapes those more effectively than the multi-or single-level approach.

Impact on Imaging Application
We evaluate the impact of the improved partitioning heuristic on an advanced imaging algorithm, the Local Laplacian filter. The Local Laplacian filter is an edge-aware image processing filter. The algorithm uses the concepts of Gaussian pyramids and Laplacian pyramids as well as a point-wise remapping function to enhance image details without creating artifacts. A detailed description of the algorithm and theoretical background is given in [24]. We model the dataflow of the filter as a DAG where nodes are annotated with the program size and an execution time estimate and edges with the corresponding data transfer size. The DAG has 489 nodes and 631 edges in total in our configuration. We use all algorithms (multi-level, evolutionary), the evolutionary with the fitness function set to the one described in Section 5. We compare our algorithms with the best local search heuristic from our previous work [22] The time budget given to each heuristic is ten minutes. The makespans for each resulting schedule are obtained with a cycle-true compiled simulator of the hardware platform. We vary the available bandwidth to external memory to assess the impact of edge cut on schedule makespan. In the following, a bandwidth of x refers to x times the bandwidth available on the real hardware. The relative improvement in makespan is compared to our previous heuristic in [22]. In this experiment, the results in terms of edge cut as well as makespan are similar for the multi-level and the evolutionary algorithm optimizing for cuts, as the filter is fairly small. However, the new approaches improve the makespan of the application. This is mainly because the reduction of the edge cut reduces the amount of data that needs to be transferred to external memories. Improvements range from 1% to 5% depending on the available memory bandwidth with high improvements being seen for small memory bandwidths. For larger memory bandwidths, the improvement in makespan diminishes since the pure reduction of communication volume becomes less important. Using our new fitness function that incorporates critical path length increases the makespan by 40% to 10% if the memory bandwidth is scarce (for bandwidths ranging from 1 to 3). We found that the gangs in this case are almost always memory-limited and thus reducing communication volume is predominantly important. With more bandwidth available, including critical path length in the fitness function improves the makespan by 3% to 33% for bandwidths ranging from 4 to 10. Hence, using the fitness function results in a convenient way to fine-tune the heuristic for a given memory bandwidth. For hardware platforms with a scarce bandwidth, reducing the edge cut is the best. If more bandwidth is available, for example if more than one DMA engine is available, one can change the factors of the linear combination to gradually reduce the impact of edge cut in favor of critical path length.

Conclusion
Directed graphs are widely used to model data flow and execution dependencies in streaming applications which enables the utilization of graph partitioning algorithms for the problem of parallelizing computation for multiprocessor architectures. In this work, we introduced a novel multi-level algorithm as well as the first evolutionary algorithm for the acyclic graph partitioning problem. Additionally, we formulated an objective function that improves load balancing on the target platform which is then used as fitness function in the evolutionary algorithm. Extensive experiments over a large set of graphs and a real application indicate that the multi-level as well as the evolutionary algorithm significantly improve the state-of-the-art. Our experiments indicate that the search space has many local minima. Hence, in future work, we want to experiment with relaxed constraints on coarser levels of the hierarchy. Other future directions of research include multi-level algorithms that directly optimize the newly introduced fitness function.