Name
Title | ||
|---|---|---|
A Dvnd Local Search Implemented On A Dataflow Architecture For The Minimum Latency Problem |
Abstract | ||
|---|---|---|
This paper proposes a dataflow implementation for a local search to solve the Minimum Latency Problem (MLP), a variant of the Traveling Salesman Problem (TSP). Since the problem is NP-Hard, best results in literature report the use of metaheuristic strategies, mainly based on the concept of variable neighborhoods. The dataflow architecture was proposed in the 70's with programs represented as dependency graphs, but von Neumann architecture became the standard computing platform and dataflow has been only considered for theoretical experiments. Many state-of-the-art metaheuristics are harnessing computational power from emerging heterogeneous computing platforms, such as Graphics Processing Units (GPU), requiring to rethink some ideas of classic optimization algorithms in order to properly explore the architecture. We propose a hybrid dataflow architecture (simulated over CPU), where each node contains a GPU implementation that enumerates a neighborhood for the problem. The dataflow architecture uses a distributed network that provides scalability for solving large MLP instances, where each neighborhood exploration is part of a state-of-the-art Distributed Variable Neighborhood Descent (DVND). The whole scenario yield an heterogeneous multi-level parallelization approach that can be used to solve time consuming problems, not being coupled to specific instance or problem. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/IPDPSW.2018.00194 | 2018 IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS (IPDPSW 2018) |
Keywords | Field | DocType |
local search, dataflow, minimum latency problem, graphics processing unit | Dataflow architecture,Computer science,Parallel computing,Symmetric multiprocessor system,Dataflow,Travelling salesman problem,Local search (optimization),Von Neumann architecture,Distributed computing,Metaheuristic,Scalability | Conference |
ISSN | Citations | PageRank |
2164-7062 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rodolfo Pereira Araujo | 1 | 0 | 0.34 |
| I. M. Coelho | 2 | 58 | 12.95 |
| Leandro A. J. Marzulo | 3 | 49 | 11.56 |