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.
Code (0)
등록된 구현이 없습니다.
Tasks
graph partitioningSchedulingSimilar Papers 제목 키워드 기반
Multilevel Acyclic Hypergraph Partitioning
A directed acyclic hypergraph is a generalized concept of a directed acyclic graph, where each hyperedge can contain an arbitrary number of tails and heads. Directed hypergraphs can be used to model data flow and executi…
hypergraph partitioningSchedulingGraph Partitioning with Acyclicity Constraints
Graphs are widely used to model execution dependencies in applications. In particular, the NP-complete problem of partitioning a graph under constraints receives enormous attention by researchers because of its applicabi…
graph partitioningSchedulingDistributed Evolutionary Graph Partitioning
We present a novel distributed evolutionary algorithm, KaFFPaE, to solve the Graph Partitioning Problem, which makes use of KaFFPa (Karlsruhe Fast Flow Partitioner). The use of our multilevel graph partitioner KaFFPa pro…
graph partitioningRecent Progress on Graph Partitioning Problems Using Evolutionary Computation
The graph partitioning problem (GPP) is a representative combinatorial optimization problem which is NP-hard. Currently, various approaches to solve GPP have been introduced. Among these, the GPP solution using evolution…
Combinatorial Optimizationgraph partitioningSurveyEvolutionary n-level Hypergraph Partitioning with Adaptive Coarsening
Hypergraph partitioning is an NP-hard problem that occurs in many computer science applications where it is necessary to reduce large problems into a number of smaller, computationally tractable sub-problems. Current tec…
Evolutionary Algorithmshypergraph partitioning