Timeline for Parallelization problem in LinearSolve and Minimize
Current License: CC BY-SA 3.0
55 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 28, 2012 at 13:29 | comment | added | mak maak |
Oleksandr R., Thanks again for your help. When we replace Log[Exp[-x] + Exp[+x]] with a function including absolute value, like what you suggested, our target function becomes non-smooth, because of the absolute value, and, as far as I know, minimization of a non-smooth function is much more difficult. I need to find values which make the function zero, and this function absolutely has got such an answer.
|
|
| Sep 27, 2012 at 18:22 | comment | added | Oleksandr R. |
Just FYI, such a function is (-(Abs[x]*(-1 + Tanh[8 - 4*Abs[x]])) + ((3*(25 + 4*Abs[x]^2 - 375/(15 + 4*Abs[x]^2)))/64 + Log[2])*(1 + Tanh[8 - 4*Abs[x]]))/2. This deviates from Log[Exp[-x] + Exp[+x]] by less than 1% and should suffice as a replacement. If you also scale your variables then we may be in business. By the way, do you need to find the minimum or will a value close to the minimum suffice? The problem is, I'm not sure if it's possible to do the former (or, if you do, to prove that you succeeded). The latter is difficult in a 5000-dimensional problem but not impossible.
|
|
| Sep 27, 2012 at 13:43 | comment | added | Oleksandr R. |
As regards making your function more stable, you might start by replacing your many instances of Log[Exp[-x] + Exp[+x]] with a function that returns the same value without generating intermediate values that vary by hundreds of thousands of orders of magnitude. It will be highly preferable if you can keep all intermediates within the range limitations of machine precision numbers.
|
|
| Sep 27, 2012 at 13:38 | comment | added | Oleksandr R. |
I don't have a lot of time to answer questions at the moment as I'm trying to finish a PhD thesis, so I apologize if I can't keep up with all of your queries. On second thought, don't use my Nelder-Mead code for this; there are some minor issues for your function and anyway I don't think it will be as beneficial for this problem as it is in other cases. With regard to LinearSolve--honestly, you should split this question into several on the different (unrelated) topics you bring up--the timing difference is due to parallelization of the RandomReal calls which otherwise are single-threaded.
|
|
| Sep 27, 2012 at 4:19 | comment | added | mak maak | @Oleksandr R., Could you please also have a look at Edit 5 in my question. Based on what you mentioned regarding LinearSolve, how we can explain these examples? Thanx. | |
| Sep 27, 2012 at 4:15 | history | edited | mak maak | CC BY-SA 3.0 |
added 2547 characters in body
|
| Sep 26, 2012 at 20:54 | answer | added | KAI | timeline score: 9 | |
| Sep 26, 2012 at 15:16 | comment | added | mak maak | @Oleksandr R., I don't know why I cannot use your Nelder-Mead code to minimize my function. | |
| Sep 26, 2012 at 12:45 | comment | added | mak maak | @Oleksandr R., Thank you for your comments. Could you please have a look at edit 4. I agree with what you said regarding instability, but I am wondering how I can make this function stable. Moreover, even if we make it stable, I think it is better to implement NMinimize for the large stable function in Mathematica using more capacity of the CPU. | |
| Sep 26, 2012 at 3:05 | history | edited | Mr.Wizard | CC BY-SA 3.0 |
added 1140 characters in body
|
| Sep 25, 2012 at 21:02 | answer | added | Simon Woods | timeline score: 3 | |
| Sep 25, 2012 at 14:13 | history | edited | mak maak | CC BY-SA 3.0 |
deleted 1080 characters in body
|
| Sep 25, 2012 at 13:54 | history | edited | mak maak | CC BY-SA 3.0 |
added 1084 characters in body
|
| Sep 24, 2012 at 18:55 | comment | added | Oleksandr R. |
At least part of the problem appears to be related to the fact that the numeric values in your function as well as the optimum values of your parameters are all very small. This leads to severe numerical instability, especially since FindMinimum and NMinimize start with an initial guess of 1 for the value of each parameter: you are working with huge numbers whose logs are about 1 million and looking for small differences between these, which is unlikely to work out for obvious reasons. Perhaps you will have better luck if you first improve the stability characteristics of your function.
|
|
| Sep 24, 2012 at 16:16 | comment | added | Oleksandr R. |
And as I already mentioned, if you don't provide a concrete example of your problem but just allude to it, it's very difficult to see where the real issues lie! I assume you are not typing in a 5000-dimensional function by hand. If you can't supply the function directly (75-dimensional, or whatever is the smallest that gives you difficulty), can you provide the code to generate it? Otherwise, use CopyToClipboard@InputForm[expr] to copy it.
|
|
| Sep 24, 2012 at 15:29 | comment | added | mak maak | @Oleksandr R., As I already mentioned, the problem arises when the number of variables increases! 75 is the minimum number (I mentioned 75 just to make my question not very complicated), it is usually about 5000 or more, but the general shape of the function is like what I edited. I didn't know how to copy the whole function from Mathematica notebook to this page, so just typed some terms from the beginning. | |
| Sep 24, 2012 at 15:09 | comment | added | Oleksandr R. |
Differential evolution is inherently parallelizable because each stage of the algorithm is quite simple and can be applied to the complete dataset in one step with no synchronization or dependency propagation necessary. This is not to say that NMinimize offers a parallel implementation of differential evolution--it doesn't, but it can be done. Could you please edit a full 75- (or more) dimensional example into your question? The 12-dimensional excerpt you supplied so far does not give any difficulties to FindMinimum, so it is difficult to determine where exactly your problems arise.
|
|
| Sep 24, 2012 at 15:00 | comment | added | Oleksandr R. | I should add that none of those options is a solution to your parallelization question, but I feel it's more important to discuss how to attack the problem before considering parallelization. An inefficient algorithm may take days to run in parallel while an efficient one (suited to the problem) might not even need to be parallelized at all to return a solution in reasonable time. | |
| Sep 24, 2012 at 14:57 | comment | added | mak maak | @Oleksandr R., I think it is the third case, unfortunately! Could you please explain more what do you mean by parallelizable differential evolution method?? Thanx. | |
| Sep 24, 2012 at 14:43 | comment | added | Oleksandr R. |
Thanks for the extra information. Well, a 75-dimensional function is not a serious problem, but a 5000-dimensional one might be. Is this a convex function? If so, you can most likely use FindMinimum with the "ConjugateGradient" or "QuasiNewton" (L-BFGS) methods. If it's only slightly non-convex, try my Nelder-Mead code (not the implementation offered by NMinimize, which is much slower). If it's severely non-convex and/or possesses many local minima, you might have serious problems; differential evolution is one possible (parallelizable) option, but the algorithm is not very efficient.
|
|
| Sep 24, 2012 at 14:25 | comment | added | mak maak | @Oleksandr R., Thank you for your help, please have a look at edit 3 in the question. | |
| Sep 24, 2012 at 14:21 | history | edited | mak maak | CC BY-SA 3.0 |
added 2046 characters in body
|
| Sep 24, 2012 at 13:05 | comment | added | user21 |
@OleksandrR., I was refering to MKL related stuff only. In V8.0.3 The MKL version is <= 10.3.5. Intel it self suggests switching HT off for MKL (BLAS) related operations (see here and here Also, to the best of my knowledge automatic selection is only available on windows here - So IMHO optimal LinearSolve optimal performance is by not using HT and (maybe) setting thread affinity.
|
|
| Sep 24, 2012 at 12:17 | comment | added | Oleksandr R. | ... tabulating primes, and instead focus on the performance of the minimization without getting distracted by the specific value reported for CPU usage, it will be much easier to contemplate giving you a practical answer. Please describe the actual function in as much detail as possible (or post it in its entirety) because without that information anything that can be said is pure speculation. | |
| Sep 24, 2012 at 12:15 | comment | added | Oleksandr R. |
Yes, that's exactly what I mean. Please read Jon Stokes's article, which explains how SMT works and why this is the case. I'm sorry if this is confusing but this is a fairly technical subject and it will be difficult to understand until you have some quite detailed knowledge about the design of modern CPUs, which it isn't practical to review here. Anyway, please let's focus on the actual problem and actual performance: a 75-dimensional function is really not that large a problem, and should not take very long to minimize. If you can remove irrelevant material about LinearSolve and ...
|
|
| Sep 24, 2012 at 11:23 | comment | added | mak maak | @Oleksandr R., I am not sure, but maybe you mean for LinearSolve 50% usage of CPU means using all CPU resources and CPU usage less than 50% means not using all CPU resources, which still sounds confusing to me! | |
| Sep 24, 2012 at 11:20 | comment | added | mak maak | @Oleksandr R., But I am still confused about what you mentioned for LinearSolve. You said I am actually using all CPU's resources, even though the CPU monitor claims 50% usage. But as you can see in the first example of Edit2 in my question, increasing CPU usage results in shorter computation time, so when increasing CPU usage from 12% in case1 to 50% in case4 can decrease computation time from 203 to 89, I wonder why we cannot decrease computation time more by making CPU usage 100% (if it is possible)?? | |
| Sep 24, 2012 at 11:14 | comment | added | mak maak | @Oleksandr R., Thank you for your comments. The function I am trying to minimize using NMinimize is a very large function of 75 (or more variables) including quadratics terms and exponential terms. One more thing is that I have same problem with FinRoot command in Mathematica. I mean I can do my optimization using NMinimize (or Minimize) to find the minimum of my big function OR solve a large system of non-linear equations including 75 (or more) non-linear equations and 75 (or more variables), but in FindRoot I have same problem and cannot make CPU usage 100%. | |
| Sep 24, 2012 at 10:02 | history | edited | mak maak | CC BY-SA 3.0 |
added 11 characters in body
|
| Sep 24, 2012 at 8:16 | comment | added | Oleksandr R. |
@chris it's complicated... basically Prime is stateful; it matters which arguments have been passed already. You can get improved performance by blocking, either using ParallelSubmit or the Method -> "CoarsestGrained" option of ParallelTable. More on Prime here.
|
|
| Sep 24, 2012 at 8:11 | comment | added | Oleksandr R. | @ruebenko MKL has its own thread scheduler, which is pretty good at making the optimal choices. I agree with what you wrote, but for non-MKL code you might like to reconsider switching HT off. In practice the situation is a lot more complicated than whether all the execution resources are used (for almost all code--even most HPC-like floating point workloads--they aren't). The HT implementation in recent CPUs is much improved versus a decade ago, and you'll now find only rare cases for which HT actually reduces performance. Very little code comes anywhere close to MKL in terms of optimization. | |
| Sep 24, 2012 at 7:48 | comment | added | chris | @OleksandrR. do you understand why ParallelTable performs more poorly than ParallelSubmit for the primes? | |
| Sep 24, 2012 at 7:21 | comment | added | Oleksandr R. |
... you're using in this case. As you saw from the link above, I've implemented an improved version of the Nelder-Mead algorithm, which (the algorithm itself, I mean) is not inherently parallel as it stands but can be adapted to benefit from parallelism. The other algorithms are inherently parallel (which means you can write a parallel implementation, not that NMinimize itself is parallelizable) but may or may not be appropriate for any given problem. Essentially the one thing that will really help here is more detail about the function you are actually minimizing.
|
|
| Sep 24, 2012 at 7:17 | comment | added | Oleksandr R. |
... in that case, one can load up the CPU to 100% of its front end/scheduler capacity and see a performance gain by doing so. To understand this you need to know how and why SMT works, which is quite a technical topic. Jon Stokes has given a very good introduction that I would suggest as a starting point. Focusing on your actual problem, i.e. NMinimize, basically the current implementation is serial only, but the algorithms it uses are parallelizable in principle to some extent, which is why I asked which of the algorithms ...
|
|
| Sep 24, 2012 at 7:13 | comment | added | Oleksandr R. |
Thanks for the update. Okay, things are getting complicated now, so let me try to clarify. First thing to note is that these workloads (LinearSolve, NMinimize, and tabulating primes) have very different performance characteristics, so your conclusions in each case are not transferable to the others. For LinearSolve, you actually are using all of your CPU's resources, even though the CPU monitor claims 50% usage. Tabulating primes is "embarrassingly parallel" and can benefit from SMT (Hyper-threading), so ...
|
|
| Sep 24, 2012 at 6:52 | comment | added | mak maak | @chris, Please have a look at edit 2 I made for my question. It looks that the performance of the method you suggested is completely different from what I used and computation time increases too much if we use what you mentioned. You can check it on your laptop. | |
| Sep 24, 2012 at 6:50 | comment | added | mak maak | @Oleksandr R., Please have a look at edit 2 I made for my question. It looks that "CPU usage" reported by the system monitor is not very inconsistent with actual performance. What I am looking for is just to make sure that I am using all capacity of my CPU to make computation time as short as possible. | |
| Sep 24, 2012 at 6:44 | history | edited | mak maak | CC BY-SA 3.0 |
added 7285 characters in body
|
| Sep 24, 2012 at 2:43 | comment | added | user21 |
@makmaak, the fact that you only see 4 CPUs active in LinearSolve may be because the MKL detects that HT is on and does not use it. In my experiance HT may be beneficial if the tasks done use different part of the CPU, which is not the case for numerics. Since I do a lot of numerics, I usually switch HT off altogether. Concerning NMinimize it would be good to see the problem at hand, perhaps something can be done.
|
|
| Sep 23, 2012 at 19:45 | comment | added | chris |
@mak maak just for your information you can do t = AbsoluteTime[]; primelist = ParallelTable[Prime[k], {k, 1, 20000000}]; time2 = AbsoluteTime[] - t in one command so to speak. It does it in 60 sec on my laptop.
|
|
| Sep 23, 2012 at 18:05 | comment | added | Oleksandr R. | Also, what minimization method are you using? Not all methods are particularly amenable to parallelization, even in principle. In those cases you are basically stuck with domain decomposition as suggested by Sjoerd. | |
| Sep 23, 2012 at 17:51 | comment | added | Oleksandr R. |
4 cores plus SMT is still 4 cores, so you'll only suffer by running 8 threads of LinearSolve on a 4-core CPU. For other types of workload that aren't as well optimized it isn't always so clear, but you can try SetSystemOptions["ParallelOptions" -> "ParallelThreadNumber" -> 8], which I found gave a boost of about 20% in this question, which also relates to NMinimize. Don't expect miracles from SMT; "CPU usage" as reported by the system monitor usually does not correspond in any direct way to actual performance.
|
|
| Sep 23, 2012 at 15:46 | comment | added | mak maak | @Sjoerd C. de Vries, unfortunately my problem is an Unconstrained Optimization case | |
| Sep 23, 2012 at 15:30 | comment | added | mak maak | @chris, please have a look at edit 1 for my question to see result of explicit analysis. If NMinimize cannot be parallelized, so how I can use all capacity of my CPU to minimize this large function??! | |
| Sep 23, 2012 at 15:26 | history | edited | mak maak | CC BY-SA 3.0 |
added 1005 characters in body
|
| Sep 23, 2012 at 15:05 | comment | added | Sjoerd C. de Vries |
Can you divide the area over which you want to minimize in 8 parts? If so, you could try ParallelTable to start parallel evaluations in all those areas. Pick the lowest result from the table returned.
|
|
| Sep 23, 2012 at 14:58 | comment | added | mak maak | @ruebenko, I am not sure but I think It is 4 cores plus hyperthreading. If it is the case so how I can use the capacity of my CPU to solve the problems I mentioned??! My problem for NMinimize is a large function with 75 variables, and I want to find the minimum of this function. Mathematica can minimize this function and give me the result but it takes too much time, because just uses one core (CPU usage=12%). So I am trying to employ 8 cores to make computation time as short as possible. It sounds very wierd to me if it is not possible in a software like Mathematica! | |
| Sep 23, 2012 at 14:26 | comment | added | user21 | @makmaak, do you have 8 cores or 4 plus hyperthreading? If that is the case the MKL will not only use the true number of cores for performance reasons. | |
| Sep 23, 2012 at 13:11 | comment | added | chris |
NMinimize might not be parallelized depending on the problem you are trying to solve. Have you tried explicitly something like ParallelTable to see what load you get then? For instance (rather surprizingly) ParallelTable[Pause[20], {i, 8}] yields a load of 87 % on my 2.5 Ghz i7
|
|
| Sep 23, 2012 at 11:42 | comment | added | mak maak | When I check from Evaluation\Parallel Kernel Configuration\Parallel; The limit by license availability is 16. | |
| Sep 23, 2012 at 11:00 | history | edited | mak maak | CC BY-SA 3.0 |
edited title
|
| Sep 23, 2012 at 7:29 | comment | added | b.gates.you.know.what | 4 cores rather than 8 might be a license limitation. | |
| Sep 23, 2012 at 6:08 | history | tweeted | twitter.com/#!/StackMma/status/249751979897802752 | ||
| Sep 23, 2012 at 3:35 | review | First posts | |||
| Sep 23, 2012 at 15:05 | |||||
| Sep 23, 2012 at 3:35 | history | asked | mak maak | CC BY-SA 3.0 |