skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

GPU-based parallel vertex substitution algorithm for the p-median problem

Lim, Gino J. ; Ma, Likang

Computers & industrial engineering, 2013-01, Vol.64 (1), p.381-388 [Periódico revisado por pares]

New York: Elsevier Ltd

Texto completo disponível

Citações Citado por
  • Título:
    GPU-based parallel vertex substitution algorithm for the p-median problem
  • Autor: Lim, Gino J. ; Ma, Likang
  • Assuntos: Algorithms ; Computer architecture ; GPU computation ; Mathematical problems ; p-Median problem ; Parallel computing ; Parallel processing ; Semiconductors ; Studies ; Vertex substitution
  • É parte de: Computers & industrial engineering, 2013-01, Vol.64 (1), p.381-388
  • Descrição: ► First GPU-based parallel vertex substitution algorithm for the p-median problem. ► Improved the computational complexity of the algorithm. ► Gained up to 57 times of speedup compared to the original vertex substitution algorithm. We introduce a GPU-based parallel vertex substitution (pVS) algorithm for the p-median problem using the CUDA architecture by NVIDIA. pVS is developed based on the best profit search algorithm, an implementation of vertex substitution (VS), that is shown to produce reliable solutions for p-median problems. In our approach, each candidate solution in the entire search space is allocated to a separate thread, rather than dividing the search space into parallel subsets. This strategy maximizes the usage of GPU parallel architecture and results in a significant speedup and robust solution quality. Computationally, pVS reduces the worst case complexity from sequential VS’s O(p·n2) to O(p·(n−p)) on each thread by parallelizing computational tasks on GPU implementation. We tested the performance of pVS on two sets of numerous test cases (including 40 network instances from OR-lib) and compared the results against a CPU-based sequential VS implementation. Our results show that pVS achieved a speed gain ranging from 10 to 57 times over the traditional VS in all test network instances.
  • Editor: New York: Elsevier Ltd
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.