Top

Soft Computing

Published in:

01-01-2014 | Methodologies and Application

Systolic neighborhood search on graphics processing units

Authors: Pablo Vidal, Francisco Luna, Enrique Alba

Published in: Soft Computing | Issue 1/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we propose a parallel processing model based on systolic computing merged with concepts of evolutionary algorithms. The proposed model works over a Graphics Processing Unit using the structure of threads as cells that form a systolic mesh. Data passes through those cells, each one performing a simple computing operation. The systolic algorithm is implemented using NVIDIA’s compute unified device architecture. To investigate the behavior and performance of the proposed model we test it over a NP-complete problem. The study of systolic algorithms on GPU and the different versions of the proposal show that our canonical model is a competitive solver with efficacy and presents a good scalability behavior across different instance sizes.

previous article An image representation of infrastructure based on non-classical receptive field

next article A novel L1/2 regularization shooting method for Cox’s proportional hazards model

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Alba E (2005) Parallel metaheuristics: a new class of algorithms. Wiley-Interscience, New York

Alba E, Dorronsoro B (2008) Cellular genetic algorithms, operations research/computer science interfaces, vol 42. Springer, Heidelberg

Alba E, Vidal P (2011) Systolic optimization on gpu platforms. In: EUROCAST (1), pp 375–383

Chan H, Mazumder P (1995) A systolic architecture for high speed hypergraph partitioning using a genetic algorithm. In: Yao X (ed) Progress in evolutionary computation, lecture notes in computer science, vol 956. Springer, Berlin, pp 109–126

Chu P, Beasley J (1998) A genetic algorithm for the multidimensional knapsack problem. J Heuristics 4:63–86CrossRefMATH

CUDA (2007) NVIDIA CUDA Compute Unified Device Architecture—Programming Guide

Gavish B, Pirkul H (1986) Computer and database location in distributed computer systems. IEEE Trans Comput 35(7):583–590

Gilmore PC, Gomory RE (1966) The theory and computation of knapsack functions. Oper Res 14(6):1045–1074CrossRefMathSciNet

Glover F, Kochenberger GA (1996) Critical event tabu search for multidimensional knapsack problems. metaheuristics: the theory and applications. Kluwer Academic Publishers, Boston, pp 407–427

Gottlieb J (2001) On the feasibility problem of penalty-based evolutionary algorithms for knapsack problems. In: Applications of evolutionary computing, lecture notes in computer science, pp 50–59

Grama A, Karypis G, Kumar V, Gupta A (2003) Introduction to parallel computing, 2nd edn. Addison Wesley, Pearson

Hanafi CWS (2009) New convergent heuristics for 0-1 mixed integer programming. Eur J Oper Res 195(1):62–74CrossRefMATHMathSciNet

Hanafi S, Wilbaut C (2011) Improved convergent heuristics for the 0-1 multidimensional knapsack problem. Ann Oper Res 183:125–142CrossRefMATHMathSciNet

Hwang J, Park S, Kong IY (2011) An integer programming-based local search for large-scale multidimensional knapsack problems. Int J Comput Sci Eng 3(6):2257–2264

Ke L, Feng Z, Ren Z, Wei X (2010) An ant colony optimization approach for the multidimensional knapsack problem. J Heuristics 16:65–83CrossRefMATH

Kung HT (1979) Let’s design algorithms for vlsi systems. In: Proceedings of the conference on very large scale integration: architecture, design, fabrication, pp 65–90

Lagae A, Lefebvre S, Drettakis G, Dutré P (2009) Procedural noise using sparse Gabor convolution. ACM Trans Graph (Proceedings of ACM SIGGRAPH 2009) 28(3):54:1–54:10

Megson G, Bland I (1998) Synthesis of a systolic array genetic algorithm. In: Parallel processing symposium, 1998. IPPS/SPDP 1998

Shih W (1979) A branch and bound method for the multiconstraint zero one knapsack problem. J Oper Res Soc 30(4):369–378MATH

Thomas DB, Howes L, Luk W (2009) A comparison of CPUs, GPUs, FPGAs, and massively parallel processor arrays for random number generation. In: Symposium on Field Programmable Gate Arrays, pp 63–72

Vasquez M, Hao JK (2001) A hybrid approach for the 01 multidimensional knapsack problem. In: In Proceedings of the international joint conference on artificial intelligence 2001, pp 328–333

Vasquez M, Vimont Y (2005) Improved results on the 0-1 multidimensional knapsack problem. Eur J Oper Res 165:70–81CrossRefMATHMathSciNet

Zhang X, Liu Z, Bai Q (2012) A new hybrid algorithm for the multidimensional knapsack problem. In: Bio-inspired computing and applications, lecture notes in computer science, pp 191–198

Zhou Q, Luo W (2010) A novel multi-population genetic algorithm for multiple-choice multidimensional knapsack problems. In: Cai Z, Hu C, Kang Z, Liu Y (eds) Advances in computation and intelligence, lecture notes in computer science, vol 6382. Springer, Berlin, pp 148–157

Title: Systolic neighborhood search on graphics processing units
Authors: Pablo Vidal
Francisco Luna
Enrique Alba
Publication date: 01-01-2014
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 1/2014
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-013-1041-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2014

Discrete and fuzzy dynamical genetic programming in the XCSF learning classifier system

Danger theory based artificial immune system solving dynamic constrained single-objective optimization

A novel L1/2 regularization shooting method for Cox’s proportional hazards model

Regression analysis of belief functions on interval-valued variables: comparative studies

On the new solutions for a fully fuzzy linear system

Relative negations in non-commutative fuzzy structures

Premium Partner