Thread: handling array or list in parallel

I have a bunch of numbers in an array, lets say 1,2,3,4,5,6,etc... and assign these to different threads.
processor 0: arraypart = 1,2
processor 1: arraypart = 3,4
etc...
Each processor is going to delete some of the assigned numbers.

Is there a 'standard' technique for merging the arrayparts at the end of the parallel section (in pthreads)? If there are a neater way of doing this with lists Im also interested in that.

Example: After parallel section array is 1,3,6,etc

I'd suggest having just one array, in shared memory. Each thread works with the array as you would without using threads, except instead of each thread getting a pointer to the base of the array, and a size, now each thread will will get a pointer to the base + offset to the lowest index it will be working with in the array, along with the number of offset + range of indices it will be working with, instead of the full size of the data.

i.e.: Say I want to sort a huge array, using 4 threads, and the array is 1 million in size, total.

thread
#1 gets the arrayName, as the address to array[0] (as normally it would be done w/o threads), and 250,000
#2 gets the &arrayName[250,000], and 500,000 //base is index 250,000. Top index it works with is 499,999
#3 gets the &arrayName[500,000] and 750,000 //etc.
#4 gets the &arrayName[750,000] and 1,000,000.

Each thread works from the base to it's top range of indices - 1, that have been passed to it, the way C naturally does it.

No taking apart or putting the array back together again .

Maybe i was unclear... Each thread is deleting entries in the assigned array interval. Well lets say Im interested in what to do after the code you posted.
I think ill go with memcpy. Ill monitor how many undeleted elements each thread puts into the local array so that i know how much to copy into the global array. Hmm, yea something like that would probably work...

Originally Posted by überfuzz

Maybe i was unclear... Each thread is deleting entries in the assigned array interval. Well lets say Im interested in what to do after the code you posted.
I think ill go with memcpy. Ill monitor how many undeleted elements each thread puts into the local array so that i know how much to copy into the global array. Hmm, yea something like that would probably work...

OK, You have a "master" array of 12 numbers: master[12].

1,2,3,4,5,6,7,8,9,10,11,12

Each of 4 threads, will work with 3 numbers.

#1 thread will delete even numbers 1-3
#2 thread will delete odd numbers 4-6
#3 thread will delete the lowest number 7-9
#4 thread will delete the highest number 10-12

Final master[] now has:
1,3,4,6,8,9,10,11.

The only question is how to deal with the "deleted" numbers.

One way:
#define NIL -999 (some totally impossible value for your data). Replace the deleted numbers, with NIL, and set up your later functions to ignore NIL values - don't do computations or display them. Just adds one line to your print loop, for instance.

Code:

for(i=0;i<12;i++) {
   if(master[i] != NIL)
      printf("%d \n",master[i]);
}

Another way to do it:
Copy all the non-NIL values, to another array.

Another way:
Move the remaining numbers down to overwrite the deleted numbers, then work with only the 8 remaining numbers master[0] through master[7], in the case above.

This could be done inside the same loop that deletes numbers (just adds one extra variable to the loop to record the correct next [index] that will be over-written. It could also be done in a later loop (simpler but less effecient).