The UNIX and Linux Forums  

Go Back   The UNIX and Linux Forums > Top Forums > High Level Programming
Google UNIX.COM


High Level Programming Post questions about C, C++, Java, SQL, and other programming languages here.

More UNIX and Linux Forum Topics You Might Find Helpful
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

Reply
 
Submit Tools LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 04-01-2008
Registered User
 

Join Date: May 2007
Location: Glasgow, Scotland
Posts: 59
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Reddit! Stumble this Post!Spurl this Post!
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 );
Where per_thread_bounds is defined as:

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

}
This works fine for n (or total_thr) < 11, for the given range 1..100. However when i choose 11 worker threads over the range 1..100, the numbers are divided up as per 10 worker threads, leaving a spare worker thread (#11) which is allocated a range 101..100!

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
Reply With Quote
Forum Sponsor
  #2 (permalink)  
Old 04-02-2008
Registered User
 

Join Date: May 2007
Location: Glasgow, Scotland
Posts: 59
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Reddit! Stumble this Post!Spurl this Post!
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;
By choosing to do the arithmetic in float's, then truncate to an int at the very last minute is the way to go -

Code:
partition_size = ((float)(global_bounds->upper - global_bounds->lower)/(float)total_cpus)+0.5;
The subtle ones are always the best! :-)

-c
Reply With Quote
  #3 (permalink)  
Old 04-02-2008
Registered User
 

Join Date: Oct 2003
Posts: 69
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Reddit! Stumble this Post!Spurl this Post!
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.
Reply With Quote
Google UNIX.COM
Reply

Thread Tools
Display Modes


The 50 most popular UNIX and Linux searches.
Google Search Cloud for The UNIX and Linux Forums
"inappropriate ioctl for device" 421 service not available, remote server has closed connection ^m automate ftp autosys awk trim bash eval bash exec bash for loop command copy/move folder in unix couldn't set locale correctly curses.h cut command in unix export command in unix find grep find mtime find null character in a unix file grep multiple lines grep or grep recursive hp-ux ifconfig inaddr_any inappropriate ioctl for device lynx javascript mailx attachment mget mtime ping port remove first character from string in k shell replace space by comma , perl script scp recursive segmentation fault(coredump) sftp script snoop unix stale nfs file handle syn_sent tar exclude tar extract to folder test: argument expected unix unix .profile unix forum unix forums unix interview questions unix simulator unix.com vi select all vi substitute vi+substitute+end+of+line+character while loop within while loop shell script


All times are GMT -7. The time now is 04:37 AM.


Powered by: vBulletin, Copyright ©2000 - 2006, Jelsoft Enterprises Limited.
The UNIX and Linux Forums Content Copyright ©1993-2008 The CEP Blog All Rights Reserved -Ad Management by RedTyger Visit The Global Fact Book

Content Relevant URLs by vBSEO 3.2.0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101