Optimal number of threads per core

Question

Let s say I have a 4-core CPU  and I want to run some process in the minimum amount of time  The process is ideally parallelizable  so I can run chunks of it on an infinite number of threads and each thread takes the same amount of time   Since I have 4 cores  I don t expect any speedup by running more threads than cores  since a single core is only capable of running a single thread at a given moment  I don t know much about hardware  so this is only a guess   Is there a benefit to running a parallelizable process on more threads than cores  In other words  will my process finish faster  slower  or in about the same amount of time if I run it using 4000 threads rather than 4 threads

User · Answer

The answer depends on the complexity of the algorithms used in the program. I came up with a method to calculate the optimal number of threads by making two measurements of processing times Tn and Tm for two arbitrary number of threads ‘n’ and ‘m’. For linear algorithms, the optimal number of threads will be N = sqrt ( (mn(Tm*(n-1) – Tn*(m-1)))/(nTn-mTm) ) .

Please read my article regarding calculations of the optimal number for various algorithms: pavelkazenin.wordpress.com

User · Answer

4000 threads at one time is pretty high    The answer is yes and no  If you are doing a lot of blocking I O in each thread  then yes  you could show significant speedups doing up to probably 3 or 4 threads per logical core   If you are not doing a lot of blocking things however  then the extra overhead with threading will just make it slower  So use a profiler and see where the bottlenecks are in each possibly parallel piece  If you are doing heavy computations  then more than 1 thread per CPU won t help  If you are doing a lot of memory transfer  it won t help either  If you are doing a lot of I O though such as for disk access or internet access  then yes multiple threads will help up to a certain extent  or at the least make the application more responsive

User · Answer

The ideal is 1 thread per core  as long as none of the threads will block   One case where this may not be true  there are other threads running on the core  in which case more threads may give your program a bigger slice of the execution time

User · Answer

Benchmark   I d start ramping up the number of threads for an application  starting at 1  and then go to something like 100  run three-five trials for each number of threads  and build yourself a graph of operation speed vs  number of threads   You should that the four thread case is optimal  with slight rises in runtime after that  but maybe not   It may be that your application is bandwidth limited  ie  the dataset you re loading into memory is huge  you re getting lots of cache misses  etc  such that 2 threads are optimal     You can t know until you test

User · Answer

One example of lots of threads   thread pool   vs one per core is that of implementing a web-server in Linux or in Windows   Since sockets are polled in Linux a lot of threads may increase the likelihood of one of them polling the right socket at the right time - but the overall processing cost will be very high   In Windows the server will be implemented using I O Completion Ports - IOCPs - which will make the application event driven  if an I O completes the OS launches a stand-by thread to process it  When the processing has completed  usually with another I O operation as in a request-response pair  the thread returns to the IOCP port  queue  to wait for the next completion   If no I O has completed there is no processing to be done and no thread is launched   Indeed  Microsoft recommends no more than one thread per core in IOCP implementations  Any I O may be attached to the IOCP mechanism  IOCs may also be posted by the application  if necessary

User · Answer

The actual performance will depend on how much voluntary yielding each thread will do   For example  if the threads do NO I O at all and use no system services  i e  they re 100  cpu-bound  then 1 thread per core is the optimal   If the threads do anything that requires waiting  then you ll have to experiment to determine the optimal number of threads   4000 threads would incur significant scheduling overhead  so that s probably not optimal either

User · Answer

speaking from computation and memory bound point of view  scientific computing  4000 threads will make application run really slow   Part of the problem is a very high overhead of context switching and most likely very poor memory locality   But it also depends on your architecture   From where I heard Niagara processors are suppose to be able to handle multiple threads on a single core using some kind of advanced pipelining technique   However I have no experience with those processors

User · Answer

I know this question is rather old  but things have evolved since 2009   There are two things to take into account now  the number of cores  and the number of threads that can run within each core   With Intel processors  the number of threads is defined by the Hyperthreading which is just 2  when available   But Hyperthreading cuts your execution time by two  even when not using 2 threads   i e  1 pipeline shared between two processes -- this is good when you have more processes  not so good otherwise  More cores are definitively better    On other processors you may have 2  4  or even 8 threads  So if you have 8 cores each of which support 8 threads  you could have 64 processes running in parallel without context switching    No context switching  is obviously not true if you run with a standard operating system which will do context switching for all sorts of other things out of your control  But that s the main idea  Some OSes let you allocate processors so only your application has access usage of said processor   From my own experience  if you have a lot of I O  multiple threads is good  If you have very heavy memory intensive work  read source 1  read source 2  fast computation  write  then having more threads doesn t help  Again  this depends on how much data you read write simultaneously  i e  if you use SSE 4 2 and read 256 bits values  that stops all threads in their step    in other words  1 thread is probably a lot easier to implement and probably nearly as speedy if not actually faster  This will depend on your process  amp  memory architecture  some advanced servers manage separate memory ranges for separate cores so separate threads will be faster assuming your data is properly filed    which is why  on some architectures  4 processes will run faster than 1 process with 4 threads

User · Answer

You will find how many threads you can run on your machine by running htop or ps command that returns number of process on your machine   You can use man page about  ps  command   man ps   If you want to calculate number of all users process  you can use one of these commands    ps -aux  wc -l  ps -eLf   wc -l   Calculating number of an user process    ps --User root   wc -l   Also  you can use  htop   Reference    Installing on Ubuntu or Debian   sudo apt-get install htop   Installing on Redhat or CentOS   yum install htop dnf install htop       On Fedora 22  releases    If you want to compile htop from source code  you will find it here

User · Answer

Hope this makes sense  Check the CPU and Memory utilization and put some threshold value  If the threshold value is crossed don t allow to create new thread else allow

User · Answer

If your threads don t do I O  synchronization  etc   and there s nothing else running  1 thread per core will get you the best performance  However that very likely not the case  Adding more threads usually helps  but after some point  they cause some performance degradation   Not long ago  I was doing performance testing on a 2 quad-core machine running an ASP NET application on Mono under a pretty decent load  We played with the minimum and maximum number of threads and in the end we found out that for that particular application in that particular configuration the best throughput was somewhere between 36 and 40 threads  Anything outside those boundaries performed worse  Lesson learned  If I were you  I would test with different number of threads until you find the right number for your application   One thing for sure  4k threads will take longer  That s a lot of context switches

User · Answer

I thought I d add another perspective here  The answer depends on whether the question is assuming weak scaling or strong scaling   From Wikipedia   Weak scaling  how the solution time varies with the number of processors for a fixed problem size per processor   Strong scaling  how the solution time varies with the number of processors for a fixed total problem size   If the question is assuming weak scaling then  Gonzalo s answer suffices  However if the question is assuming strong scaling  there s something more to add  In strong scaling you re assuming a fixed workload size so if you increase the number of threads  the size of the data that each thread needs to work on decreases  On modern CPUs memory accesses are expensive and would be preferable to maintain locality by keeping the data in caches  Therefore  the likely optimal number of threads can be found when the dataset of each thread fits in each core s cache  I m not going into the details of discussing whether it s L1 L2 L3 cache s  of the system    This holds true even when the number of threads exceeds the number of cores  For example assume there s 8 arbitrary unit  or AU  of work in the program which will be executed on a 4 core machine   Case 1  run with four threads where each thread needs to complete 2AU  Each thread takes 10s to complete  with a lot of cache misses   With four cores the total amount of time will be 10s  10s   4 threads   4 cores    Case 2  run with eight threads where each thread needs to complete 1AU  Each thread takes only 2s  instead of 5s because of the reduced amount of cache misses   With four cores the total amount of time will be 4s  2s   8 threads   4 cores    I ve simplified the problem and ignored overheads mentioned in other answers  e g   context switches  but hope you get the point that it might be beneficial to have more number of threads than the available number of cores  depending on the data size you re dealing with

User · Answer

I agree with  Gonzalo s answer  I have a process that doesn t do I O  and here is what I ve found     Note that all threads work on one array but different ranges  two threads do not access the same index   so the results may differ if they ve worked on different arrays   The 1 86 machine is a macbook air with an SSD  The other mac is an iMac with a normal HDD  I think it s 7200 rpm   The windows machine also has a 7200 rpm HDD   In this test  the optimal number was equal to the number of cores in the machine

[parallel-processing] Optimal number of threads per core

Examples related to parallel-processing

Examples related to cpu