Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: dynamic number of threads based on CPU utilization

by BrowserUk (Pope)
on Sep 26, 2012 at 15:44 UTC ( #995800=note: print w/ replies, xml ) Need Help??


in reply to dynamic number of threads based on CPU utilization

In addition to trying to figure out why the CPU utilization is not staying constant, I would like to find a way to dynamically add threads based on CPU utilization such that more work can be done when the CPU load falls below a certain threshold (arbitrarily, let's say 25%).

Forget the idea of throwing more threads at the problem in order to increase your cpu utilisation.

  • If twice as many cpu-bound (no IO) threads as you have cores is not sufficient to fully utilise your cpu capacity, then the problem is something to do with the design of your code.

    And throwing more threads at the problem will likely slow it down rather than speed it up.

  • Whatever tool or system call you use to measure cpu utilisation, the figure you get will be an instantaneous value.

    And even on the most cpu bound system, it will not be a smooth, roughly constant figure, but will fluctuate wildly between 0% in one instance and 100% in the next. This is normal, but completely useless for basing decisions on.

    Even if you apply some smoothing algorithm over time, the effects of feedback will mean that you will simply overload your memory until no thread can run until another thread has been swapped out; with the consequence that all your cpu time is spent switching threads and performing swapping IO. your system will simply grind to a halt.

  • So please, ignore any suggestions to measure cpu and employ busy loops and wait loops to control cpu utilisation.

    They might succeed in consuming 100% of your cpu, BUT THEY WILL NOT IMPROVE YOUR WORK RATE OR CUT YOUR PROGRAMS RUNTIME.

trying to figure out why the CPU utilization is not staying constant ...

In the first half of your program, less than 100% utilisation is to be expected as a) you are doing disk IO, reading the XML files from disk; b) writing to your shared %similar hash which will involve locking -- whether you are doing it; which you do not show -- or just using the implicit locking that perl does internally for its own protection.

In the second half of your program, you are a) iterating over that same shared hash, which means that internal locking comes into play. (But that's probably not a big problem for that part of your program).

Much worse is that each of your second pool of threads is performing the same bi-gramming process on each of the keys of the shared hash, for each work item it receives. AND EACH OF THOSE WORK ITEMS IS ITSELF, ONE OF THE KEYS OF THAT HASH!

That means you are doing a O(n^2) process of comparing each key against each key, and bi-graming both keys again every time. That is monumentally wasteful.

If you fix that algorithm -- ie. bi-gram each of the keys in the hash once first -- and then compare them each against the next, a single thread will probably finish much faster than your current mechanism. At which point, all the talk of dynamically spawning threads according to cpu load becomes moot.

Once you've you have made your similarity algorithm implementation efficient -- single-threaded -- it might then be worth considering whether if can be sped up using threading. But for now, ditch your second thread pool, use a single threaded loop to construct bi-gram arrays for each of your keys; and then use a second loop to compare one against the other.


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

RIP Neil Armstrong


Comment on Re: dynamic number of threads based on CPU utilization
Download Code
Re^2: dynamic number of threads based on CPU utilization
by mabossert (Beadle) on Sep 26, 2012 at 16:31 UTC

    Thanks for the feedback with the bi-gramming. It turns out, I can simply store the bi-gram array directly as part of the hash...I will give that a shot later today and see how it does.

      it turns out, I can simply store the bi-gram array directly as part of the hash..

      That will work, but be aware that accessing the data in a shared data structure is significantly slower than accessing non-shared memory. This is due to the need for internal locking amongst other things.

      So if you run a second pool of threads, each accessing that shared hash containing shared arrays, the lock contention between the threads will likely slow your processing to a crawl. (A simple fact of life with perl's shared data structures).

      Try the version I posted and see how you get on.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

      RIP Neil Armstrong

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://995800]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (5)
As of 2014-08-02 10:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Who would be the most fun to work for?















    Results (55 votes), past polls