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
    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