Using more cores does not necessarily lead to reduced run times on Gurobi 5.0

This post takes a look at performance variability issues when scaling up the number of processors assigned to the Gurobi MIP solver (I did the same study for CPLEX in this post a few months ago). I summarize results from a few computational experiments we’ve made. I show that while increasing the number of processor cores results in quicker runs on average, but the effect on individual instances is quite difficult to predict. The general conclusions are:

  • In general, more processor cores available leads to reduced solution times, up to 16 cores;
  • On average, using 8 cores instead of a single core approximately cuts solution times in half;
  • On a single instance, using more cores may actually lead to considerably longer (or shorter) run times;
  • The run with the most cores (16, in our test) was the fastest about 66% of the time, while 7.8% of our models ran faster on a single core than on 16 cores!

Some background

When mixed-integer linear programming (MIP) models take too much time to solve, a natural option is to run the model on a faster machine. Nowadays, with multi-core processors being commonplace, faster often means having more processors (or cores). On a pure branch-and-bound algorithm (the one you will find in textbooks), adding processors simply leads to more nodes being evaluated per second. However, state-of-the-art MIP solvers are several orders of magnitude faster than a pure BnB code, and for that they use many techniques sur as cutting plane generation, various types of branching, heuristics, as well as probing and preprocessing. That being said, all advanced features often lead to a phenomenon labeled as performance variability [1,2].

Is parallel Gurobi faster than sequential overall?

I ran Gurobi 5.0 on 90 models (85 from the “benchmark” set of MIPLIB 2010 [2] and 5 of my own), on the same machine, using 1, 2, 4, 8, and 16 cores. All runs are performed on the same machine. Rather than do a thorough analysis of run times, I do look at the following question: how many seconds does Gurobi need to solve these models to optimality (with a 0.01% tolerance) given a certain number of cores? As expected, speed-ups are experienced on average when you allow for use of more processor cores.

NbCores-GeoMeans-Gu50

How about individual instances?

This overall estimate on 90 instances isn’ that helpful when you’re trying to solve a particular model. Over our small testbed, how many instances are solved faster when using Y cores instead of X, where Y > X? As we experienced when testing with CPLEX, an significant number of models are actually slower when run with more cores allowed. The thing to remember is that you can get very different solution times by changing the number of processors available to the solver.

NbCores-ScalingFrom-Gurobi500

 

(This table has been updated on 2013/07/22.)  At the instance level, some phenomena are difficult to explain. For instance, neos-1601936 solves in 70 seconds with a single core, in 86.2 seconds with 2 cores, in 830 seconds with 4 cores and in 77.9 seconds with eight cores, all with default settings. While these times may vary slightly from run to run, they are somewhat stable (830 seconds may result in 815 seconds next time you run the model but not in a 100-second run).

Methodological considerations and references

The experiments were made on a IBM x3650 server with Intel Xeon X5650 processors at 2.67 GHz and with 72 GB of RAM operating under Windows Server 2008 R2. A single run was made on each instance. Gurobi 5.0.0 (build 9993) was used for the tests.

[1] Koch, T., T. Achterberg, et al. (2011). “MIPLIB 2010.” Mathematical Programming Computation 3(2): 103-163.

[2] Lodi, A. (2010). Mixed-integer Programming Computation. 50 years of integer programming 1958-2008 [ressource électronique] : the early years and state-of-the-art surveys. M. Jünger, T. M. Liebling, D. Naddefet al. Berlin, Springer.

Trackbacks

  1. […] architecture is one of the industry’s major successes, leading to huge average speedups [1][2] without needing any kind of parametrization on the user’s part. Starting from release […]

Speak Your Mind

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.