A MANY-CORE BASED PARALLEL TABU SEARCH

Yuet M. Lam and Wayne Luk

References

  1. [1] Y.M. Lam, S.Y. Yu, and P. Wang, A parallel threads coordination scheme for solving combinatorial optimization problems, Proceedings of the IEEE TENCON, 2013, 1–4.
  2. [2] T.G. Crainic, M. Toulouse, and M. Gendreau, Synchronous tabu search parallelization strategies for multicommodity location-allocation with balancing requirements, OR Spectrum, 17(2–3), 1995, 113–123.
  3. [3] J.P. Cohoon, W.N. Martin, and D.S. Richards, Genetic algorithms and punctuated equilibra in vlsi, Parallel Problem Solving from Nature, Lecture Notes in Computer Science, 496, 1991, 134–144.
  4. [4] D. Whitley, S. Rana, and R.B. Heckendorn, Optimization using distributed genetic algorithms, Parallel Problem Solving from Nature, Lecture Notes in Computer Science, 496, 1991, 176–185.
  5. [5] T. Matsumura, M. Nakamura, D. Miyazato, K. Onaga, and J. Okech, Effects of chromosome migration on a parallel and distributed genetic algorithm, Proc. of the IEEE Int. Symp. on Parallel Architectures, Algorithms, and Networks, 1997, 357–361.
  6. [6] S.A. Kravitz and R.A. Rutenbar, Placement by simulated annealing on a multiprocessor, IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 6(4), 1987, 534–549.
  7. [7] I. Mavroidis, I. Papaefstathiou, and D. Pnevmatikatos, Hardware implementation of 2-Opt local search algorithm for the traveling salesman problem, Proc. of the IEEE/IFIP Int. Workshop on Rapid System Prototyping, 2007, 41–47.
  8. [8] T.V. Luong, N. Melab, and E.-G. Talbi, GPU computing for parallel local search metaheuristic algorithms, IEEE Transactions on Computers, 62(1), 2013, 173–185.
  9. [9] C. Ababei, Speeding up FPGA placement via partitioning and multithreading, International Journal of Reconfigurable Computing, 2009, Article ID 514754.
  10. [10] W.H. Choi and X. Liu, Case study: GPU-based implementation of sequence pair based floorplanning using CUDA, Proc. of the Int. Symp. on Circuits and Systems, 2010, 917–920.
  11. [11] Y. Han, S. Roy, and K. Chakraborty, Optimizing simulated annealing on GPU: A case study with IC floorplanning, Proc. of the Int. Symp. on Quality Electronic Design, 2011, 1–7.
  12. [12] M.A. O’Neil, D. Tamir, and M. Burtscher, A parallel GPU version of the traveling salesman problem, Proc. of the Int. Conf. on Parallel and Distributed Processing Techniques and Applications, 2011, 348–353.
  13. [13] M. Burtscher and H. Rabeti, A scalable heterogeneous parallelization framework for iterative local searches, Proc. of the IEEE Int. Parallel & Distributed Processing Symp., 2013, 1289–1298.
  14. [14] J.J. Schneider and S. Kirkpatrick, Stochastic Optimization (Springer-Verlag, Berlin Heidelberg, 2006).
  15. [15] S. Lin, Computer solutions of the traveling salesman problem, Bell System Technical Journal, 44, 1965, 2245–2269.
  16. [16] Y.M. Lam, K.H. Tsoi, and W. Luk, Parallel neighbourhood search on many-core platforms, International Journal of Computational Science and Engineering, 8(3), 2013, 281–293.
  17. [17] G. Reinelt, TSPLIB: A traveling salesman problem library, ORSA Journal on Computing, 3, 1991, 376–384.
  18. [18] R. Burkard, S. Karisch, and F. Rendl, QAPLIB – A quadratic assignment problem library, Journal of Global Optimization, 10(4), 1997, 391–403.
  19. [19] A. Choong, R. Beidas, and J. Zhu, Parallelizing simulated annealing-based placement using GPGPU, Proc. of the Int. Conf. on Field Programmable Logic and Applications, 2010, 31–34.
  20. [20] T.V. Luong, L. Loukil, N. Melab, and E.-G. Talbi, A GPU-based iterated tabu search for solving the quadratic 3dimensional assignment problem, Proc. of the Int. Conf. on Computer Systems and Applications, 2010, 1–8.
  21. [21] T.V. Luong, N. Melab, and E.-G. Talbi, Large neighborhood local search optimization on graphics processing units, Proc. of the IEEE Int. Symp. on Parallel and Distributed Processing, 2010, 1–8.
  22. [22] N. Fujimoto and S. Tsutsui, A highly-parallel TSP solver for a GPU computing platform, Numerical Methods and Applications, Lecture Notes in Computer Science, 6046, 2011, 264–271.

Important Links:

Go Back