Title: Evolutionary Acyclic Graph Partitioning,
Abstract: 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.