0

im trying to distribute the rows of a matrix as evenly as possible between a certain amount of processes to do a certain task, the thing is that given the fact that the division might not be exact i cannot figure out how to distribute these rows, even tho its pretty easy to do it when we assume the division is equal. So the problem would be something like this:

(assuming exact division):

//code...

work = rows / numprocs;

//leftover = rows % numprocs; /* what to do with this !! */

for(i = my_id * work; i < (my_id * work + work); i ++){
// do things...

//more code

thanks in advance.

ysap
  • 7,723
  • 7
  • 59
  • 122
Delachiesa
  • 15
  • 4
  • There are several different ways to do this and outlining different methods is likely too broad a topic for SO. – wolfPack88 May 06 '15 at 18:52
  • sounds like http://stackoverflow.com/questions/15658145/how-to-share-work-roughly-evenly-between-processes-in-mpi-despite-the-array-size/19322881#19322881 ? – Rob Latham May 08 '15 at 20:05
  • Actually thats a very interesting thread, thanks for the info. – Delachiesa May 09 '15 at 16:21

1 Answers1

1

Obviously, some of the processes will contain more rows than the others. Just spread the remaining N rows ("leftovers") across the first N processes.

Update:

For example:

M = 22 rows
P = 5 processes
Q = M / P = 22 / 5 = 4
N = M - Q * P = 22 % 5 = 2

proc #0 - 5 rows
proc #1 - 5 rows
proc #2 - 4 rows
proc #3 - 4 rows
proc #4 - 4 rows

Update 2:

A function that gets number of rows, start row in a process:

// my_id = 0 -> (P-1)
R = (my_id < N) ? (M / P + 1) : (M / P);
S = (my_id < N) ? (my_id * R) : (my_id * R + N);
ysap
  • 7,723
  • 7
  • 59
  • 122
  • Exactly, some of them will at most have 1 more row than the others, the problem is that the rows i give to them have to be consecutive so i have to give them all the work at once. – Delachiesa May 06 '15 at 18:54
  • So, procs 1 to N get (Q+1) rows and procs (N+1) to M get Q rows (where M: total number of procs; Q: the integral part of the division of rows by M). – ysap May 06 '15 at 19:06
  • For example, 22 rows and 5 processes: M = 22; Q = 22 / 5 = 4; N = 22 % 5 = 2; Rows = {5, 5, 4, 4, 4} – ysap May 06 '15 at 19:09
  • Ok, i undestand that now thanks, but i might be missapproaching it... lets say process 0 ends in Q+1, process 1 will start in my_id + Q so how do i deal with that? i might be going nuts... what im trying to figure out now is the structure of the code to deal with that... – Delachiesa May 06 '15 at 19:21
  • each process has an id to indetify them i just call it my_id, sorry im pretty new at this (programming + posting here) – Delachiesa May 06 '15 at 19:45
  • Because the number of rows in each process is not a constant, you need to change the start and end row indices in your `for` loop according to the non-equal division. You could, for example, use an array to store the pre-calculated start and end rows, and index this array with `my_id`. Or, you can try to parametrize the start and end rows inline. – ysap May 06 '15 at 19:54
  • Can you come up with a simple function for the number of rows per `my_id`? – ysap May 06 '15 at 19:57
  • I think i might, im not sure tho, i've beeng thinking about it for a while and nothing came up, if you could put an example i would be more than gratefull – Delachiesa May 06 '15 at 19:59
  • Since it is your 1st post in SE, please make sure you read the FAQ, and if an answer helps you solve your problem, it is usually a good practice to upvote and/or accept it. – ysap May 06 '15 at 20:00