5
$\begingroup$

I have some attempts to solve a scheduling problem using the Gurobi and doCPLEX API in python and .NET on Ubuntu-server installed on a hyper-computing cluster with 64 physical cores. Unfortunately, both solvers cannot exploit more than 32 cores and it seems a bit weird to me! Even I attempted to force using 64 cores with the Threads parameter; however, it deteriorated the convergences speed. Appreciate someone has any interpretations of this case and of course a solution to this issue.

enter image description here

UPDATE #1:

The machine is deployed with 64 physical cpus. Here is the detail of cpu #26:

*-cpu:25
        description: CPU
        product: Intel(R) Xeon(R) CPU E5-2698 v4 @ 2.20GHz
        vendor: Intel Corp.
        physical id: 419
        bus info: cpu@25
        version: RHEL 7.6.0 PC (i440FX + PIIX, 1996)
        slot: CPU19
        size: 2GHz
        capacity: 2GHz
        width: 64 bits

and cpu #64:

 *-cpu:63
        description: CPU
        product: Intel(R) Xeon(R) CPU E5-2698 v4 @ 2.20GHz
        vendor: Intel Corp.
        physical id: 43f
        bus info: cpu@63
        version: RHEL 7.6.0 PC (i440FX + PIIX, 1996)
        slot: CPU3f
        size: 2GHz
        capacity: 2GHz
        width: 64 bits

UPDATE #2:

The architecture of CPUs:

enter image description here

UPDATE #3:

From the Gurobi community support center (link):

Gurobi always aims to count physical cores. To do this, the operating system is queried for the number of physical and logical cores. Gurobi license files always contain the (maximal) number of (physical) cores for which they are valid. (For reasons of backward-compatibility, they also contain the number of sockets if it is greater than 1.) On virtual machines, the number of physical cores is more difficult to obtain, since VMs typically hide the difference between physical and logical cores. In a properly configured VM with hyper-threading, a total number of 16 logical cores would be counted as 8 physical cores. To check how many physical cores are measured by Gurobi, you can download and install Gurobi and use the grbprobe utility.

So, I tried the grbprobe and here is the result:

info  : grbprobe version , build v9.1.1rc0
HOSTNAME=packer-Ubuntu-18
HOSTID=a6400be
PLATFORM=linux64
USERNAME=ubuntu
SOCKETS=64
CORES=64
CPU=Intel(R) Xeon(R) CPU E5-2698 v4 @ 2.20GHz
Improve this question
$\endgroup$
1
  • $\begingroup$ Intel(R) Xeon(R) CPU E5-2698 v4 @ 2.20GHz has 20 cores and 40 threads on each of 2 chips. So something is certainly strange with your setup. But I'm certain that you do not have 32 physical cores on any single chip. $\endgroup$ – Nike Dattani Dec 27 '20 at 9:09
7
$\begingroup$

You need to distinguish between threads and (physical) cores. Is it possible that the cores you see in your machine are actually just hyperthreads, i.e. 2 cores resemble one physical core?

Furthermore, using many cores is not always very helpful to solve a MIP. You may want to try something like Concurrent Optimization in Gurobi to exploit performance variability and run several settings at once.

Did you already tune the solver parameters? In most cases, this is way more effective in reducing the solving time than just throwing more cores into the mix.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you for the answer. Actually, I tested both deterministic concurrent and the normal concurrent; the performance worsened. I tested a couple of parameters setting and the best was: m.params.MIPFocus=2, m.params.Heuristics=0.2, m.params.PreCrush = 1, m.params.Cuts = 1. $\endgroup$ – Mohammad Namakshenas Dec 18 '20 at 9:54
  • $\begingroup$ For your first question please see: imgur.com/G5cvoLO $\endgroup$ – Mohammad Namakshenas Dec 18 '20 at 9:55
  • $\begingroup$ Just to be sure: you also tried ConcurrentSettings? Then I guess you are kind of out of luck - memory/CPU/cache congestion might eat up the parallel performance improvement. MIPs can be very hard... $\endgroup$ – mattmilten Dec 18 '20 at 10:21
  • $\begingroup$ I guess I cannot use ConcurrentSettings since it requires at least two machines in a distributed theme. Nor I have a license for the distributed optimization. $\endgroup$ – Mohammad Namakshenas Dec 18 '20 at 10:40
  • $\begingroup$ However, the main question is that why the solver cannot exploit more than 32 cores. $\endgroup$ – Mohammad Namakshenas Dec 18 '20 at 10:50
7
$\begingroup$

Modern CPUs are very complex and have at least two features that limit their scaling capability. The first one is a turbo feature that increases the clock speed when not all cores are utilized. The second one is that all cores share the same memory bus and the same L2 and L3 cache. If you solve the same problem in parallel (so start Python twice and let each solve the same problem), you will notice that it takes longer than solving just one problem, even though in both cases a single problem is solved by 32 dedicated cores.

The second issue is algorithmic. Since you mention a scheduling problem, I assume there are binary variables, so there are many continuous subproblems. Solving one subproblem can be paralellized. For the simplex method, this article by Bixby and Martin (Bixby co-founded CPLEX and Gurobi, he is the 'bi' in 'Gurobi') shows good scaling up to 4 cores. The barrier method uses a sparse Cholesky factorization, which can also be parallelized (I cannot find a reference for how CPLEX/Gurobi do this, although with certain structure you can do better than CPLEX/Gurobi). This article from 2012 (free preprint here) shows in Section 7.1 how well the barrier algorithms of CPLEX and Gurobi scale. Figure 5 shows that there is hardly any gain going from 16 to 32 cores (the efficiency drops by almost 50%), which is also commented on in the text (search for "16 threads"). In CPLEX, only the barrier method supports parallelization:

Linear programming models (LPs) are solved by default with the dual simplex algorithm. The dual simplex algorithm does not use multiple threads. In order to benefit from parallel execution for LP, you need to invoke the barrier or concurrent optimizers explicitly.

For branch&bound, the simplex method is typically preferrable because it is much better at warm starting.

So, the real question is how CPLEX and Gurobi perform branch&bound on a multicore machine. Do they solve nodes in parallel, or they solve one node at a time. For the latter, there is hardly any gain going above 16 cores, whereas for the former there is a trade-off between solving a few nodes quickly and pruning the branch&bound tree, and solving many nodes with the single threaded simplex or barrier method. Prior to CPLEX 11 you could actually control this behavior with the MipThreads and BarThreads parameters, but now there is no such option anymore. I suspect that it defaults to solving CPX_PARAM_THREADS nodes, each with a single threaded instance of dual simplex. Cplex then waits until all nodes are finished to continue. In the node log you can how much time is spent waiting. You can change this behavior by changing CPX_PARAM_PARALLELMODE to -1 (CPX_PARALLEL_OPPORTUNISTIC).

My suspicicion is that 64 instances of dual simplex do not run as fast as 32 instances, even though you have 64 cores, due to what I described in the first paragraph. You could test that experimentally. On top of that, it is possible that most of the work done by the extra cores is wasted because those nodes would be pruned otherwise. By inspecting the node log you could verify how many extra nodes were solved.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your answer is quite informative. Thanks. It seems that the algorithmic capacity of these solvers is not quite developed to use e.g. hundreds of cores at the same time. $\endgroup$ – Mohammad Namakshenas Dec 27 '20 at 18:48
2
$\begingroup$

Your screenshot here indicates to me that you have 32 physical cores, 64 threads, and 64 vCPUs. You observed that Gurobi and CPLEX are not making use of more than 32 cores, but you have not shown us anything indicating that your machine has ever successfully used more than 32 cores for any calculation that doesn't use hyperthreading. If you try other software (such as MATLAB, or even just a few lines of code written by yourself only for the purpose of testing), you may find that there's nothing special here about Gurobi or CPLEX, as no other program is able to use more than 32 cores either, as long as hyperthreading is turned off.

You can also check this by checking the name of your CPU. If it says "Intel" anywhere then it does not have more than 32 physical cores unless it's a Xeon Phi in the x200 series, for which it is very well-known that the speed-up is not linear with the number of cores and does not resemble the physical cores of standard CPUs. If the name of your CPU does not contain "AMD RYZEN" or "AMD EPYC" anywhere, then your CPU is very unlikely to have more than 32 physical cores. I highly recommend you tell us the name of your CPU next time, as the highest-voted answer also suspected the same thing as me (and they turned out to be right). As the other answer says: "Modern CPUs are very complex" so when asking a question about high-performance computing, it's always very important to tell us not only the name and version of your operating system, but also the name and version of your hardware (i.e. CPU, GPU, etc.).

Improve this answer
$\endgroup$
9
  • $\begingroup$ For your first answer, I executed this script lscpu --all --extended for getting the list of all physical and logical cores. Here is the result: imgur.com/vox0woT. It indeed says that the machine has 64 physical core. $\endgroup$ – Mohammad Namakshenas Dec 27 '20 at 7:37
  • 1
    $\begingroup$ @MohammadNamakshenas you are using a virtual machine (KVM) that masks the actual hardware properties. Your cpu only has 20 cores. $\endgroup$ – LinAlg Dec 27 '20 at 15:21
  • 1
    $\begingroup$ @MohammadNamakshenas no, there is no computer with 64 processors with 20 cores each. Try running cplex with 20 threads and with 32 threads, you will find that 20 threads is faster. $\endgroup$ – LinAlg Dec 27 '20 at 18:28
  • 1
    $\begingroup$ @MohammadNamakshenas there is no reference, it's about the hardware. You have 20 cores, so you will not get a speed-up when you go above that. You actually lose performance due to overhead. $\endgroup$ – LinAlg Dec 27 '20 at 18:40
  • 3
    $\begingroup$ @Mohammad no. You cannot ask someone for a reference for every single thing like that. Try it yourself. If you find that they are right, that's more powerful than any third party reference that you can't necessarily trust. If you find they are wrong, then you can notify them with your evidence. But don't ask for a reference. $\endgroup$ – Nike Dattani Dec 27 '20 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.