4
$\begingroup$

I asked this question at stackoverflow and instead of addressing the math required in the problem, they wanted to talk about why setting up 5 threads is no good, or question my intentions. I just want the math solved.

Lets say you want 5 threads to process data simultaneous. Also assume, you have 89 tasks to process.

Off the bat you know 89 / 5 = 17 with a remainder of 4. The best way to split up tasks would be to have 4 (the remainder) threads process 18 (17+1) tasks each and then have 1 (# threads - remainder) thread to process 17.

This will eliminate the remainder. Just to verify:

Thread 1: Tasks  1-18  (18 tasks)
Thread 2: Tasks 19-36  (18 tasks)
Thread 3: Tasks 37-54  (18 tasks)
Thread 4: Tasks 55-72  (18 tasks)
Thread 5: Tasks 73-89  (17 tasks)

Giving you a total of 89 tasks completed.

I need a way of getting the start and ending range of each thread mathematically/programmability; where the following should print the exact thing I have listed above:

$NumTasks = 89
$NumThreads = 5
$Remainder = $NumTasks % $NumThreads 
$DefaultNumTasksAssigned = floor($NumTasks / $NumThreads)

For $i = 1 To $NumThreads
    if $i <= $Remainder Then
        $NumTasksAssigned = $DefaultNumTasksAssigned + 1
    else
        $NumTasksAssigned = $DefaultNumTasksAssigned
    endif
    $Start = ??????????
    $End = ??????????
    print Thread $i: Tasks $Start-$End ($NumTasksAssigned tasks)
Next

This should also work for any number of $NumTasks.

Note: Please stick to answering the math at hand and avoid suggesting or assuming the situation.

  • 0
    I highly doubt any of these tags fit. I'm not sure which tags do fit, though.2011-06-18

2 Answers 2

5
$NumTasks = 89
$NumThreads = 5
$Remainder = $NumTasks % $NumThreads 
$DefaultNumTasksAssigned = floor($NumTasks / $NumThreads)
$End = 0

For $i = 1 To $NumThreads
    if $i <= $Remainder Then
        $NumTasksAssigned = $DefaultNumTasksAssigned + 1
    else
        $NumTasksAssigned = $DefaultNumTasksAssigned
    endif
    $Start = $End + 1
    $End = $End + $NumTasksAssigned
    print Thread $i: Tasks $Start-$End ($NumTasksAssigned tasks)
Next
  • 0
    That is so much more simple than I had thought, I guess I was over thinking it some. Thanks!2011-06-18
2

Dividing the number of jobs ($j$) by the number of threads ($n$) yields the length of a block of tasks ($\frac{j}{n} = l$). The first block is obviously $\{1,2,\ldots l\}$. The second block is $\{l + 1, l + 2,\ldots 2l\}$, and so on up to $\{\ldots (nl-2), (nl-1), nl\}$. Using a loop, you should be able to automate this distribution, and the distribution of the remainder gained from your mod calculation.

It's not elegant, but it should do what you're asking.

  • 0
    I am not sure I follow you fully. The length of a block of tasks is represented by `$NumTasksAssigned`. In your answer `l` is the number of jobs (89) / threads (5) which is always 17.8 -- This concludes that your first block `{1,2,...l}` is not true2011-06-18
  • 0
    Edited the answer to be more clear... you must take the integral part. My answer doesn't have a specific number built into it. By iterating over the set $\{l, 2l,\ldots nl\}$ (remember that $l$ is determined by $\frac{j}{n}$), you find the upper bound of each block of tasks. You can then find the lower bound of, say the third block, by taking $2l + 1$ or $(3l + 1) - l$.2011-06-18
  • 0
    Jack is right but you need to worry about rounding. $l=\lceil\frac{j}{n}\rceil$ does the trick. Then each block except the last is $\{kl+1,kl+2, \ldots k(l+1)\}$ for $k=0,1,2,\ldots ,n-1$ and the last ends with the last task.2011-06-18
  • 0
    That's a good point, @Ross. I should have considered that. I'll edit it into the answer.2011-06-18
  • 0
    On second thought, rolled back to the first version, and I'll let your comment speak for itself. I composed the edit on my way out the door, and it didn't really gel properly when done so hurriedly.2011-06-18