![]() |
|
|
|
|
|||||||
| High Level Programming Post questions about C, C++, Java, SQL, and other programming languages here. |
|
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Sed Range Issue | Wrathe | Shell Programming and Scripting | 2 | 06-17-2008 12:54 PM |
| Algo Trading on Your BlackBerry? | iBot | Complex Event Processing RSS News | 0 | 06-05-2008 06:20 AM |
| Getting 'out of range' when partitioning | pmichner | UNIX for Dummies Questions & Answers | 1 | 09-29-2006 10:51 PM |
| I've created a partition with GNU Parted, how do I mount the partition? | jtp51 | UNIX for Dummies Questions & Answers | 1 | 09-18-2006 08:01 AM |
| understanding logical partition, physical partition | yls177 | UNIX for Dummies Questions & Answers | 3 | 11-15-2002 06:49 AM |
|
|
Submit Tools | LinkBack | Thread Tools | Display Modes |
|
|||
|
Algo to partition a range over workers in C
Hi all,
I'm struggling with an algorithm i've attempted in C. The idea of the algorithm is to take a given range of numbers, say 1..100, and divide it into n equal chunks, with the final chunk absorbing any remainders. This a really common algorithm, but i don't know it's name to look up a reference implentation. Here's my attempt thus far: 1. Identify a range the process should work on 2. Partition that range into equal chunks, so that the chunks can be allocated to worker threads 3. Fire each chunk out to a thread for processing Code:
/* Upper and lower bounds of the partition, packed for easy passing into a thread */
struct bounds_s {
int upper;
int lower;
};
typedef struct bounds_s bounds_t;
...
bounds_t global_bounds = { 100, 1 }; /* This would normally come from command line opts */
...
/* This lives in a for loop.
curr_thr iterates between 0 and total_thr-1.
global_bounds is the entire partition this process will work on
thread_bounds is to be populated with the boundaries of this thread's subdivision of the partition */
per_thread_bounds( curr_thr, total_thr, &global_bounds, &thread_bounds );
Code:
/* Work out how many subparitions to partition the global domain into,
and what the bounds of this thread should be */
void per_thread_bounds( int curr_thr, int total_thr, bounds_t const *global_bounds, bounds_t *thread_bounds ) {
/* How big is the total range we're dealing with? Divide it by the total number of threads
to find out how big a partition to assign to each worker thread */
int partition_size;
partition_size = (int)((global_bounds->upper - global_bounds->lower)/total_thr)+1;
/* Assign a partition's worth of range in the first instance, and tweak for
special cases thereafter */
thread_bounds->lower = global_bounds->lower;
thread_bounds->upper = global_bounds->lower + ( partition_size - 1 );
/* Special case: This is not the first CPU (i.e. not the first partition of range to assign
and is not the last CPU -- so don't need to soak up the remainders to the end of the range */
if( curr_thr > 0 ) {
thread_bounds->lower += curr_thr * partition_size;
thread_bounds->upper += curr_thr * partition_size;
}
/* Special case: This is the last thread, should soak up the rest of the partition */
if( curr_thr == (total_thr-1) ) {
thread_bounds->upper = global_bounds->upper;
}
}
Not what i intended :-) So i guess it's todo with my rounding, and generally poor algorithm for partitioning a range. How do i improve it? Many thanks in advance, -c |
| Forum Sponsor | ||
|
|
|
|||
|
Ok so it was my rounding all along! :-)
Specifically it's this line which was iffy - Code:
partition_size = (int)((global_bounds->upper - global_bounds->lower)/total_thr)+1; Code:
partition_size = ((float)(global_bounds->upper - global_bounds->lower)/(float)total_cpus)+0.5; -c |
|
|||
|
You could also spawn off a number of threads and have each one pull the next item off the entire range. I.E. have a "next range item" variable and a mutex that protects it.
Each thread (in a loop until all values in the range are processed) locks the mutex, take the current value, increments it, unlock the mutex, and computes on the current value. This does create a hot spot at the mutex, but if the computation takes significantly long then I don't see that being a big deal. |
|||
| Google UNIX.COM |
| Thread Tools | |
| Display Modes | |
|
|