Algo to partition a range over workers in C Post: 302180889

Sponsored Content

Top Forums Programming Algo to partition a range over workers in C Post 302180889 by craigp84 on Tuesday 1st of April 2008 11:33:25 AM

04-01-2008

Registered User

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

craigp84

View Public Profile for craigp84

Find all posts by craigp84

6 More Discussions You Might Find Interesting

1. UNIX for Dummies Questions & Answers

understanding logical partition, physical partition

hi, 1) is logical partition the same as physical partition except that one is physical and the other is logical? 2) then it must a one to one ratio?

2. UNIX for Dummies Questions & Answers

I've created a partition with GNU Parted, how do I mount the partition?

I've created a partition with GNU Parted, how do I mount the partition? The manual information at http://www.gnu.org/software/parted/manual/parted.html is good, but I am sure about how I mount the partition afterwards. Thanks, --Todd

3. Shell Programming and Scripting

print range between two patterns if it contains a pattern within the range

I want to print between the range two patterns if a particular pattern is present in between the two patterns. I am new to Unix. Any help would be greatly appreciated. e.g. Pattern1 Bombay Calcutta Delhi Pattern2 Pattern1 Patna Madras Gwalior Delhi Pattern2 Pattern1...

4. Solaris

Partition overlaps another partition while creating new parition in solaris

hi all while formatting hard disk i am getting following error. Partition 1 ends at 266338338 It must be between 34 and 143374704. label error: EFI Labels do not support overlapping partitions Partition 8 overlaps partition 1. Warning: error writing EFI. Label failed. I have formatted the...

5. Filesystems, Disks and Memory

Ask concept soft partition vs hard partition

Hi Experts I would like to know different between soft partition concept and hard partition concept on solaris. Here is little explanation between soft partition concept and hard partition concept on solaris. Soft Partition: 1TB total space available in storage in all mapped to the OS to...

6. Red Hat

Shrink LVM partition & create new Linux Primary partition

Hello All, I have a Red Hat Linux 5.9 Server installed with one hard disk & 2 Partitions created on it as follows, /boot - Linux Partition & another is LVM - One VG & under that 5-6 Logical volumes(var,opt,home etc). Here my requirement is to take out 1GB of space from LVM ( Any logical...

LEARN ABOUT HPUX

pthread_set_nice_np

pthread_get_nice_np(3T) 												   pthread_get_nice_np(3T)

NAME

       pthread_get_nice_np(), pthread_set_nice_np() - get or set the nice value of a thread

SYNOPSIS

PARAMETERS

	      thread	The thread whose nice value is to be set/retrieved.

	      nice_val	Value  of  nice  to  be  applied to the target thread is returned (get function) or it specifies the new value of nice for
			thread (set function).

DESCRIPTION

       These functions are used to set and retrieve the nice value of an individual thread.

       returns the current nice value setting of the target thread and stores it in nice_val.  adds the value of  nice_val  to	the  current  nice
       value of the target thread.

       A  thread's  nice  value is a non-negative number.  The system imposes a minimum nice value of 0 and a maximum of 39 with lower nice values
       providing more favorable scheduling.  If calling results in a nice value outside the range of 0 to 39, the value will be set to the nearest
       limit.	A  process must have appropriate privileges to lower a thread's nice value.  The function allows individual threads in the process
       to have different nice values.

       returns the current nice value less 20 and will be in the range -20 to +19.

       The nice value of only system scope threads can be changed.  An attempt to change the nice value of a process-scope thread will result in a
       return  value  of  Calling on a thread that has a scheduling policy other than will have an effect only when the thread's scheduling policy
       changes to If a thread calls the system call to create a new process, the new process inherits the process-level nice  value.   Calling	to
       create a new thread will result in the new thread inheriting the creating thread's nice value.

   Note
       If  the	nice value of the entire process is changed through or all the threads in the process will have their nice values reset to the new
       process-level nice value.  The new process's nice value setting overwrites the old thread's setting.  Thus its possible that a thread whose
       nice value had been set higher than the process-level nice value have its nice value lowered as a result of the process-level re-nicing.

RETURN VALUE

       Upon successful completion, and return zero.

       Otherwise, an error number is returned to indicate the error (the variable is not set).

ERRORS

       If any of the following occur, the and functions return the corresponding error:

	      A process-scope thread was specified.

	      The caller does not have permission to lower the nice
			     value specified in nice_val.

	      No thread could be found corresponding to
			     thread.

AUTHOR

       and were developed by HP.

SEE ALSO

       fork(2), nice(2), setpriority(2), pthread_attr_getschedpolicy(3T), pthread_setschedparam(3T).

								  Pthread Library					   pthread_get_nice_np(3T)