Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I highly doubt any of these tags fit. I'm not sure which tags do fit, though. –  Asaf Karagila Jun 18 '11 at 8:35

2 Answers 2

up vote 5 down vote accepted
$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
share|improve this answer
    
That is so much more simple than I had thought, I guess I was over thinking it some. Thanks! –  BHare Jun 18 '11 at 10:54

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.

share|improve this answer
    
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 true –  BHare Jun 18 '11 at 2:38
    
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$. –  Jack Henahan Jun 18 '11 at 2:45
    
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. –  Ross Millikan Jun 18 '11 at 2:47
    
That's a good point, @Ross. I should have considered that. I'll edit it into the answer. –  Jack Henahan Jun 18 '11 at 2:49
    
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. –  Jack Henahan Jun 18 '11 at 6:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.