Problem
Imagine you're scheduling n jobs. Each job takes one hour. You have m execution threads that you randomly assign jobs to. If two jobs are assigned to the same thread, they run one after the other. What is the average time for the jobs to complete? What's the distribution of completion times look like?
Solution
Consider a simple case. You have 2 jobs and 1 execution thread. There is no way to parallelize them, so they run one after the other and take 2 hours.
Next simplest case...you have 2 jobs and 2 execution threads. The first job will be assigned to a random thread. The second job will then be assigned to a random thread. Calling the threads 1 and 2, there are 4 possibilities: 11, 12, 21, 22
Two of those run in parallel (12 and 21) and two run sequentially (11 and 22). Thus, half the time it will take 1 hour, and half the time it will take 2 hours.
What about 3 jobs and 2 execution threads? Possibilities here are 111, 112, 121, 122, 211, 212, 221, and 222. 25% of jobs are run completely sequentially (111 and 222). The rest all take 2 hours. Thus, 75% of the time it takes 2 hours, and 25% of the time it takes 3 hours.
What if you have more threads than jobs? Start with an easy case...2 jobs and 3 threads. You have 11, 12, 13, 21, 22, 23, 31, 32, and 33 as possibilities.
2 jobs and 4 threads? 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, and 44.
You can keep doing this but I'm tired of typing them...
For the worst case scenario, the math is simple. with n jobs and m threads, there are m^n possibilities. The odds of all getting into the same thread are m*((1/m)^n). Combing those, the chance that all jobs run sequentially is just (1/(m^n)) * m * ((1/m)^n), or 1/(m^(n - 1)). For some examples...
- 2 jobs and 1 thread => 1/(1^1) = 1 => 100% of the time it takes 2 hours
- 2 jobs and 2 threads => 1/(2^1) = 0.5 => 50% of the time it takes 2 hours
- 3 jobs and 2 threads => 1/(2^2) = 0.25 => 25% of the time it takes 3 hours
- 4 jobs and 2 threads => 1/(2^3) = 0.125 => 12.5% of the time it takes 4 hours
- 3 jobs and 3 threads => 11.1% of the time it takes 3 hours
- 4 jobs and 3 threads => 3.7% of the time it takes 4 hours
- 6 jobs and 3 threads => 0.4% of the time it takes 6 hours
- 2 jobs and 3 threads => 33.3% of the time it takes 2 hours
- 2 jobs and 4 threads => 25% of the time it takes 2 hours
- 2 jobs and 8 threads => 12.5% of the time it takes 2 hours
What about cases other than the worst case though? Let's try best case. That is...when number of jobs is less than or equal to number of threads, how often will it run in one hour?
2 jobs and 2 threads? 11, 12, 21, 22 are possibilities, and 12 and 21 run in one hour, so 50% take 1 hour.
2 jobs and 3 threads? 11, 12, 13, 21, 22, 23, 31, 32, and 33 are possibilities, and 6 of the 9 take 1 hour, so 66% take one hour.
2 jobs and 4 threads? 16 possibilities, and 12 of the 16 take 1 hour, so 75% take one hour.
3 jobs and 3 threads? 27 possibilities, and 6 take 1 hour,, so 22.2% take one hour.
There's a general equation here also. Consider the 2 jobs and 2 threads case The chance of getting a unique thread on the first job is 2/2 and on the second is 1/2. For the 2 jobs and 3 threads one, it's 3/3 and 2/3. 2 jobs and 4 threads? 4/4 and 3/4. 3 jobs and 3 threads? 3/3, 2/3, and 1/3. With n as the number of jobs and m as the number of threads, the denominator there when those are multiplied out is m^n again. What's the numerator though?
Thinking back to middle school, it turns out that's the permutation of m choose n, and that equation is m! / (m - n)!. For examples:
- 2 jobs and 2 threads => [2!/1!]/(2^2) = 0.5 => 50% of the time it takes 1 hour
- 2 jobs and 3 threads => [3!/2!]/(3^2) = 0.33 => 33.3% of the time it takes 1 hour
- 2 jobs and 4 threads => [4!/2!]/(4^2) = 0.75 => 75% of the time it takes 1 hour
- 2 jobs and 8 threads => [8!/2!]/(8^2) = 0.875 => 87.5% of the time it takes 1 hour
- 3 jobs and 3 threads => [3!/1!]/(3^3) = 0.222 => 22.2% of the time it takes 1 hour
- 5 jobs and 5 threads => [5!/1!]/(5^5) = 0.038 => 3.8% of the time it takes 1 hour
How do you generalize it though? For example, what's the average time taken for 12 jobs on 9 threads? How often does that situation take 11 hours? This is where I got frustrated and simulated it.
Below is a tool that lets you enter # of threads and # of jobs and get some info back. Just play around with it...
# of Threads
# of Jobs
Slot Cheats Techniques It's a practical option. To bet on slots to increase the chances of having a channel and more opportunities These techniques are even more effective. If you can pick it up and use it in a timely manner, it will be even more encouraging. And it may be a way to make your slots betting successful.
ReplyDelete