<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Aptos;
panose-1:2 11 0 4 2 2 2 2 2 4;}
@font-face
{font-family:"Segoe UI";
panose-1:2 11 6 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:10.0pt;
font-family:"Aptos",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
mso-ligatures:none;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style>
</head>
<body lang="en-TR" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt">Hi Sascha,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt">Many thanks for your detailed response! I will definitely experiment with allocating a fraction of the cores for the runs.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt">Best wishes,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<div>
<div>
<p class="MsoNormal"><b><span lang="TR" style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:#333333">Selin Bayramoglu<o:p></o:p></span></b></p>
<p class="MsoNormal"><span lang="TR" style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:#333333">Ph.D. Student<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:#333333">H. Milton Stewart School of Industrial and Systems Engineering</span></b><span style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:black"><br>
</span><span style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:#333333">Georgia Institute of Technology</span><span style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:black"><o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><a href="mailto:sbayramoglu3@gatech.edu"><span lang="TR" style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:#0563C1">sbayramoglu3@gatech.edu</span></a><span style="font-size:11.0pt"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal" style="mso-margin-top-alt:0cm;margin-right:0cm;margin-bottom:12.0pt;margin-left:36.0pt">
<b><span style="font-size:12.0pt;color:black">From: </span></b><span style="font-size:12.0pt;color:black">s schnug <sascha.schnug@gmail.com><br>
<b>Date: </b>Tuesday, 26 November 2024 at 18:04<br>
<b>To: </b>Bayramoglu, Selin <sbayramoglu3@gatech.edu><br>
<b>Cc: </b>scip@zib.de <scip@zib.de><br>
<b>Subject: </b>Re: [SCIP] About variances in solving time<o:p></o:p></span></p>
</div>
<table class="MsoNormalTable" border="0" cellspacing="0" cellpadding="0" align="left" width="100%" style="width:100.0%;background:revert!important;border:revert!important;bottom:revert!important;color:revert!important;direction:revert!important;display:revert!important;font-size:revert!important;height:revert!important;letter-spacing:revert!important;line-height:revert!important;margin:revert!important;opacity:revert!important;order:revert!important;outline:revert!important;overflow:revert!important;padding:revert!important;position:revert!important;tab-size:revert!important;table-layout:revert!important;text-align:revert!important;text-indent:revert!important;text-orientation:revert!important;text-overflow:revert!important;text-transform:revert!important;top:revert!important;vertical-align:revert!important;visibility:revert!important;white-space:revert!important;width:revert!important;word-break:revert!important;word-spacing:revert!important;writing-mode:revert!important;zoom:revert!important;border:0!important;display:table!important;width:100%!important;table-layout:fixed!important;border-collapse:seperate!important;float:none!important;border-spacing:0px 0px!important">
<tbody>
<tr style="background:revert!important;border:revert!important;bottom:revert!important;color:revert!important;direction:revert!important;display:revert!important;font-size:revert!important;height:revert!important;letter-spacing:revert!important;line-height:revert!important;margin:revert!important;opacity:revert!important;order:revert!important;outline:revert!important;overflow:revert!important;padding:revert!important;position:revert!important;tab-size:revert!important;table-layout:revert!important;text-align:revert!important;text-indent:revert!important;text-orientation:revert!important;text-overflow:revert!important;text-transform:revert!important;top:revert!important;vertical-align:revert!important;visibility:revert!important;white-space:revert!important;width:revert!important;word-break:revert!important;word-spacing:revert!important;writing-mode:revert!important;zoom:revert!important">
<td style="background:#A6A6A6;padding:0cm 0cm 0cm 0cm;background:revert!important;border:revert!important;bottom:revert!important;color:revert!important;direction:revert!important;display:revert!important;font-size:revert!important;height:revert!important;letter-spacing:revert!important;line-height:revert!important;margin:revert!important;opacity:revert!important;order:revert!important;outline:revert!important;overflow:revert!important;padding:revert!important;position:revert!important;tab-size:revert!important;table-layout:revert!important;text-align:revert!important;text-indent:revert!important;text-orientation:revert!important;text-overflow:revert!important;text-transform:revert!important;top:revert!important;vertical-align:revert!important;visibility:revert!important;white-space:revert!important;width:revert!important;word-break:revert!important;word-spacing:revert!important;writing-mode:revert!important;zoom:revert!important;padding:2px!important;background-color:#A6A6A6!important;width:0px!important">
</td>
<td width="99%" style="width:99.88%;background:#EAEAEA;padding:0cm 0cm 0cm 0cm;background:revert!important;border:revert!important;bottom:revert!important;color:revert!important;direction:revert!important;display:revert!important;font-size:revert!important;height:revert!important;letter-spacing:revert!important;line-height:revert!important;margin:revert!important;opacity:revert!important;order:revert!important;outline:revert!important;overflow:revert!important;padding:revert!important;position:revert!important;tab-size:revert!important;table-layout:revert!important;text-align:revert!important;text-indent:revert!important;text-orientation:revert!important;text-overflow:revert!important;text-transform:revert!important;top:revert!important;vertical-align:revert!important;visibility:revert!important;white-space:revert!important;width:revert!important;word-break:revert!important;word-spacing:revert!important;writing-mode:revert!important;zoom:revert!important;width:100%!important;background-color:#EAEAEA!important;padding:15px!important;font-size:12px!important;font-weight:normal!important;color:#212121!important;text-align:left!important;word-wrap:break-word!important">
<div>
<p class="MsoNormal" style="mso-element:frame;mso-element-frame-hspace:2.25pt;mso-element-wrap:around;mso-element-anchor-vertical:paragraph;mso-element-anchor-horizontal:column;mso-height-rule:exactly">
<span style="font-size:12.0pt;font-family:"Segoe UI",sans-serif;color:black">You don't often get email from sascha.schnug@gmail.com.
</span><span style="color:black"><a href="https://aka.ms/LearnAboutSenderIdentification"><span style="font-size:12.0pt;font-family:"Segoe UI",sans-serif">Learn why this is important</span></a></span><span style="font-size:12.0pt;font-family:"Segoe UI",sans-serif;color:black">
</span><span style="font-size:12.0pt;font-family:"Segoe UI",sans-serif"><o:p></o:p></span></p>
</div>
</td>
<td style="background:#EAEAEA;padding:0cm 0cm 0cm 0cm;background:revert!important;border:revert!important;bottom:revert!important;color:revert!important;direction:revert!important;display:revert!important;font-size:revert!important;height:revert!important;letter-spacing:revert!important;line-height:revert!important;margin:revert!important;opacity:revert!important;order:revert!important;outline:revert!important;overflow:revert!important;padding:revert!important;position:revert!important;tab-size:revert!important;table-layout:revert!important;text-align:revert!important;text-indent:revert!important;text-orientation:revert!important;text-overflow:revert!important;text-transform:revert!important;top:revert!important;vertical-align:revert!important;visibility:revert!important;white-space:revert!important;width:revert!important;word-break:revert!important;word-spacing:revert!important;writing-mode:revert!important;zoom:revert!important;width:75px!important;background-color:#EAEAEA!important;padding:5px!important;font-size:12px!important;font-weight:normal!important;color:#212121!important;text-align:left!important;word-wrap:break-word!important">
</td>
</tr>
</tbody>
</table>
<div>
<div>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:12.0pt">Hi,<br>
<br>
i think this a very complex multi-dimensional question.<br>
<br>
Some of those questions and my personal opinions (i'm no SCIP-dev):<br>
<br>
1: What influences solving-time with "deterministic tasks" (here meaning: same decisions/path -> but potentially earlier/later finishing)<br>
- 1a: Thread starvation (e.g. overcommitment of cpu-cores)<br>
- 1b: memory-limit (leading to memory-trashing)<br>
- 1c: memory-bandwith limit<br>
- 1d: cache invalidation<br>
- 1e: IO-bottleneck<br>
<br>
1a is related to question 3<br>
1b should be easy to estimate / check -> care has to be taken as memory-trashing is catastrophic in regards to solving-time (probably not your issue as it's usually worse than only a 70% slow-down)<br>
1c can be a real issue (imho) with many LP/MILP solvers running concurrently as some subroutines (e.g. simplex) are quite memory-bandwith hungry -> tuning recommended (see "recommendation")<br>
1d not much one can do without removing concurrent workers / noisy neighbors -> hopefully not that important as mostly a L3-cache issue (which is slow anyway) until threads are highly overcommitted (many context-switches)<br>
1e only relevant when all your 48 tasks read their input the same time -> not sure if relevant: but easy to solve if needed => add a randomized sleep before doing IO which is not counting towards solving-time<br>
<br>
Conclusion: 1a would be a real problem (see 3); 1b should be analyzed and 1c might need tuning. 1d we ignore and 1e might be analyzed and approaches if nothing else works.<br>
<br>
2: "Determinism" (again: decisions/path)<br>
- 2a: Slow-down while using a different solver-path (different decisions)<br>
- 2b: Slow-down while not using a different solver-path (same path, but faster or slower)<br>
<br>
Non-deterministic throughput (OS-scheduling and all topics above) is bad itself but it's probably even worse when the algorithm is working in a time-dependent manner. In this case, 2a, any bad effect can become much much worse.<br>
<br>
I'm somewhat afraid <u>and <b>this is a question for SCIP-devs</b></u> that SCIP is not (opposed to some other solvers based on cooperative-scheduling / task-interleaving) necessarily following the same path before being cut-off by some time-limit (or terminating
with a solution). I interpret the source-code like "#define DEFAULT_HEURTIMELIMIT 60.0 /**< time limit for a single heuristic run */" as indication, that effects/influences from 1 can make two solver-runs "diverge" in their decisions (run A can work with
heuristic success solution; run B cannot) => the bad thing here is that decisions can have exponentially bad influence on solving-time (compare with "performance variability in mixed-integer programming").<br>
<br>
Conclusion : Probably not much one can do except for reducing the effects of 1.<br>
<br>
3: "CPU-core overcommitment (self-scheduled + "noisy neighbors" = other peoples scheduled tasks):<br>
- 3a: Scheduling 100 tasks on 48 cores leads to <= 48 tasks running concurrently (bounded pool)<br>
- 3b: Scheduling 100 tasks on 48 cores leads to 49 or more tasks running concurrently (unbounded pool)<br>
<br>
Related to 1a:<br>
<br>
Conclusion: 3b is bad in any case, but even worse when other peoples tasks are not controlled by the scheduler. I assume 3a is the case.
<u>If not, it's not a good environment/setup for benchmarking.</u><br>
<br>
4: Single-core performance variability<br>
- 4a: Turbo-boosted CPUs<br>
- 4b: More "stable" CPUs<br>
<br>
Especially desktop CPUs are hard to use for benchmarks due to turbo-boosting and co. Some libraries like "google benchmark" even tries to detect this and outputs strong warnings.<br>
There are similar (inverse) topics related to noisy-neighbors (AVX512 instruction-counting based cpu-clock throttling).<br>
<br>
Terrible situation for everyone doing benchmarks. BUT hopefully your VM is a classic server-like setup where turbo-boosting and co. is not there and things are much more symmetric.
<o:p></o:p></span></p>
<div>
<p class="MsoNormal" style="margin-left:36.0pt"><u><span style="font-size:12.0pt">If not: again... bad environment/setup.</span></u><span style="font-size:12.0pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:12.0pt">The AVX512 topic can hurt a lot (~30% less clock-speed) but pretty much no software is using it. I guess this includes simplex-based MILP solvers (especially SCIP). Not so sure about
IPMs though.<br>
<br>
-----<br>
<br>
Long story short:<br>
<br>
Assuming that it's a server-like environment ("stable CPU cores" + high memory-bandwith) i have only one real recommendation:<br>
<br>
- Don't let the scheduler run with a pool-size of N=cpu-cores=48 but M<<N<br>
- Tune M by doing experiments: M converging to 0 should make performance-variability converge to 0 (~ your serial experiments) and you should decide for yourself if 1%, 5% or 10% deviation is ok (when 70% is not) -> pick M achieving the % desired<br>
- This should help with all topics in 1, 2, and 3<br>
<br>
***** Hopyfully, you have some kind of control of the scheduler to do this! (maybe there is an admin to contact and talk to) *****<br>
Best-case: M includes other peoples tasks (probably a strong no by your admin due to economic factors)<br>
Maybe okay: M includes only your tasks (for which we now are very cpu/memory-bandwith hungry)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:12.0pt">(Without control there might be some merrit in scheduling dummy-tasks; we control; limiting negative impact. But in most cases this assumes something about the scheduler-decisions
and is a rather hacky endavour)<br>
<br>
Greetings,<br>
Sascha<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:12.0pt">PS: There is, of course, also statistics. Maybe it makes sense to replace serial runs with
<u>doing parallel runs multiple times (each) and smooth the results</u> (including analysis of variance). <o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<div>
<div>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:12.0pt">Am Di., 26. Nov. 2024 um 21:48 Uhr schrieb Bayramoglu, Selin <</span><a href="mailto:sbayramoglu3@gatech.edu"><span style="font-size:12.0pt">sbayramoglu3@gatech.edu</span></a><span style="font-size:12.0pt">>:<o:p></o:p></span></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt">Hello,</span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt"> </span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt">I have a question regarding the timing of algorithms. I am recording the solving times of SCIP on 100 problems. My end goal is to compare SCIP under different configurations. I am running my experiments on a dedicated
48-core virtual machine. I have run these problems in two settings:</span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt"> </span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span style="font-size:11.0pt">1. </span><span lang="EN-US" style="font-size:11.0pt">Submit a single job which solves the problems sequentially on a single core. I did not submit any other job, but the machine has regular processes going on in the background.</span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span style="font-size:11.0pt">2. </span><span lang="EN-US" style="font-size:11.0pt">Submit 100 jobs and use all cores of the machine. The jobs get assigned to different cores of the machine and run in parallel. </span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt"> </span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt">I use HTCondor for scheduling jobs. I observed that the solving time can go up by up to 70% in case 2 compared to case 1. In addition, running case 1 several times gives very consistent runtimes, but the runtimes
vary a lot more in case 2. </span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt"> </span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt">I was wondering if there are certain measures to take so that timing values are stable (one can guarantee to get the a similar solving time for every run on the same problem) and are short. Even though the results
from case 1 are satisfactory, it is highly time consuming to run all jobs on a single core and keep the remaining 47 cores idle.</span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt"> </span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt">I would be happy to take any suggestions on this matter.</span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt"> </span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt">Thanks.</span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="EN-US" style="font-size:11.0pt"> </span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<b><span lang="TR" style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:#333333">Selin Bayramoglu</span></b><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<span lang="TR" style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:#333333">Ph.D. Student</span><span style="font-size:12.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<b><span style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:#333333">H. Milton Stewart School of Industrial and Systems Engineering</span></b><span style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:black"><br>
</span><span style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:#333333">Georgia Institute of Technology</span><span style="font-size:12.0pt"><o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
<a href="mailto:sbayramoglu3@gatech.edu" target="_blank"><span lang="TR" style="font-size:12.0pt;font-family:"Calibri",sans-serif;color:#0563C1">sbayramoglu3@gatech.edu</span></a><span style="font-size:12.0pt"><o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:12.0pt">_______________________________________________<br>
Scip mailing list<br>
</span><a href="mailto:Scip@zib.de" target="_blank"><span style="font-size:12.0pt">Scip@zib.de</span></a><span style="font-size:12.0pt"><br>
</span><a href="https://listserv.zib.de/mailman/listinfo/scip" target="_blank"><span style="font-size:12.0pt">https://listserv.zib.de/mailman/listinfo/scip</span></a><span style="font-size:12.0pt"><o:p></o:p></span></p>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>