3
3

I've been hearing a lot of enthusiastic comments about GPGPUs in the academia but, as far as I've seen, most people are just rediscovering the wheel of parallel programming.

Does anyone here experienced better results using GPGPUs to approach optimization problems? If so, when, why and how?

asked 24 Nov '11, 08:27

Thiago%20Serra's gravatar image

Thiago Serra
1.2k413
accept rate: 1%


One of the main motivations behind using GPGPUs while designing metaheuristics is to make neighborhood evaluations faster, hence shorter solution times. For example, if you have a very large neighborhood, instead of evaluating randomly-selected sample neighbor solutions or evaluating all the neighbor solutions on single (multiple) CPU(s), you could evaluate a very large number of neighbor solutions simultaneously.

Regarding possibility of better results, if the problem you're facing could be easily solved to optimality via current conventional methods based on utilization of single (multiple) CPU(s), I think you should just hope for shorter solution time in case of utilizing GPGPUs. However, if you're dealing with currently hard to solve problems like large-scale combinatorial problems, then you might find better solutions, specially if you've limited time for solving the problem.

You might find various articles on the web about this approach, but here is a good example. It discusses execution of 6144 simultaneous tabu search algorithms on 128 processors within a single GPU for solving QAP which resulted in 20-40 times faster solution times. In addition, the proposed TS were able to find better solutions in case of limited time for solving the problem.

link

answered 25 Nov '11, 01:26

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 26 Nov '11, 14:23

It seems that most of the effort on using GPGPUs is related to exhaustive or rather heuristic approaches to fit a tight time limit.

(28 Nov '11, 08:04) Thiago Serra

@Matthew Saltzman, @Brian Borchers, @Jeff Linderoth & Co. had an interesting discussion (some links included) on a blog post by @Michael Trick (in 2008). A Google search for "Interior Point" + "(GP)GPU" shows some more recent hits.

link

answered 24 Nov '11, 09:54

fbahr's gravatar image

fbahr ♦
4.6k716
accept rate: 13%

edited 25 Nov '11, 04:12

Thank you for the post. It is a very good starting point.

Still, I would like to know if, for any real-world application, what is being done with GPGPUs already surpasses standard results.

(24 Nov '11, 14:10) Thiago Serra

Haven't really stumbled upon applications in the field of OR (in the traditional sense of the discipline), probably @Matthew Saltzman now has an even more profound insight to share. But: there are a lot of "success stories" in the field of data mining, machine learning and computational intelligence/soft computing, e.g. http://blogs.nvidia.com/2010/05/the-world-is-parallel-mining-data-on-gpus/ http://www.gpucomputing.net/?q=node/122

(25 Nov '11, 04:11) fbahr ♦

Oh... and PS: Here are some earlier discussions on OR-X that might be of interest: GPU and MIP solvers and QR-based simplex?

(25 Nov '11, 08:43) fbahr ♦

They indeed are. Thanks for finding them.

(28 Nov '11, 07:58) Thiago Serra

@fbahr, thanks for the shout-out. Unfortunately, our GPU project wasn't funded, and I haven't had a chance to pursue this area in more depth since then.

(28 Nov '11, 16:44) Matthew Salt... ♦

A thesis presentation I saw a few months ago, tried to implement the ITC2007 curriculum course problem with single-threaded CPU, multi-threaded CPU and GPU.

It's benchmarks results for the GPU were far less than the single-threaded CPU and multi-threaded CPU implementation. IIRC, it concluded that GPU was less efficient, because the GPU's were idle a lot, because of the time lost in transferring memory on the bus.

It was an interesting thesis, but there were some holes in it:

  • The chosen local search didn't lend itself well to parallelization: it only evaluated 1 move at a time. So in the GPU version, only the score calculations were parallel. Although, it does prove that not every metaheuristic lends itself to be more efficient on the GPU, it would have been more fair to the GPU version to see paralell move evaluation in GPU too.
  • It didn't use delta based score calculation (aka incremental score calculation). This is a big speed increase for the non-GPU versions (bigO(n)), so it's important to know if a GPU version can also do that.
link

answered 30 Nov '11, 08:58

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k32764
accept rate: 6%

edited 30 Nov '11, 09:03

Just this morning, @or_exchange tweeted:

Linear Programming on GPUs (a project by 2011 #INFORMS @COIN_OR Cup winner Iain Dunning) - https://github.com/IainNZ/LPG (via @CCoffrin)

link

answered 28 Nov '11, 16:46

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×5
×2

Asked: 24 Nov '11, 08:27

Seen: 1,900 times

Last updated: 30 Nov '11, 09:03

OR-Exchange! Your site for questions, answers, and announcements about operations research.