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
Old 04-01-2008
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
 

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? (3 Replies)
Discussion started by: yls177
3 Replies

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 (1 Reply)
Discussion started by: jtp51
1 Replies

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... (2 Replies)
Discussion started by: joyan321
2 Replies

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... (2 Replies)
Discussion started by: nikhil kasar
2 Replies

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... (2 Replies)
Discussion started by: edydsuranta
2 Replies

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... (5 Replies)
Discussion started by: gr8_usk
5 Replies
iv_work(3)						    ivykis programmer's manual							iv_work(3)

NAME
IV_WORK_POOL_INIT, iv_work_pool_create, iv_work_pool_put, IV_WORK_ITEM_INIT, iv_work_pool_submit_work - ivykis worker thread management SYNOPSIS
#include <iv_work.h> struct iv_work_pool { int max_threads; void *cookie; void (*thread_start)(void *cookie); void (*thread_stop)(void *cookie); }; struct iv_work_item { void *cookie; void (*work)(void *cookie); void (*completion)(void *cookie); }; void IV_WORK_POOL_INIT(struct iv_work_pool *this); int iv_work_pool_create(struct iv_work_pool *this); int iv_work_pool_put(struct iv_work_pool *this); void IV_WORK_ITEM_INIT(struct iv_work_item *work); int iv_work_pool_submit_work(struct iv_work_pool *this, struct iv_work_item *work); DESCRIPTION
Calling iv_work_pool_create on a struct iv_work_pool object previously initialised by IV_WORK_POOL_INIT creates a pool of worker threads that can be used to offload CPU intensive tasks to, so as to prevent negatively influencing event handling latency in the calling thread, and to enable the use of multiple host CPUs for CPU intensive tasks. iv_work dynamically adjusts the number of threads in the pool to the amount of work there is to do. The ->max_threads member of struct iv_work_pool specifies the maximum number of threads that will be created in this pool. Calling iv_work_pool_submit_work on a struct iv_work_item object previously initialised by IV_WORK_ITEM_INIT submits a work item to a pool. The ->work member of struct iv_work_item specifies the function that will be called in one of the worker threads in the pool specified by ->this, with ->cookie as its sole argument. When the work function has completed, iv_work will call the ->completion callback to indicate this, also with ->cookie as its sole argument, in the thread that iv_work_pool_create was called in for this pool object. As a special case, calling iv_work_pool_submit_work with a NULL work pool pointer will cause the work item to be processed in the local thread, from an iv_task(3) callback. If the ->thread_start function pointer specified in struct iv_work_pool is not NULL, it will be called upon creation of a new worker thread, in the context of the created worker thread, with ->cookie as its sole argument. Calls to ->thread_start are not explicitly seri- alised, which should be kept in mind when manipulating state shared between threads from within that callback function. Similarly, if iv_work decides to terminate a worker thread, for example due to inactivity, ->thread_stop will be called in the context of the terminating thread, with ->cookie as its sole argument. Calls to ->thread_stop are also not explicitly serialised. iv_work_pool_submit_work can only be called from the thread that iv_work_pool_create for this pool object was called in. There is no way to cancel submitted work items. There is no guaranteed order, FIFO or otherwise, between different work items submitted to the same worker thread pool. When the user has no more work items to submit to the pool, its reference to the pool can be dropped by calling iv_work_pool_put. If there are still pending or running work items assigned to this pool when iv_work_pool_put is called, those work items will not be can- celed, but will be allowed to run to completion, and their ->completion callbacks will be called as usual. A similar thing holds for the ->thread_start and ->thread_stop callbacks -- they can also still be called after iv_work_pool_put returns. Even so, the memory corre- sponding to the struct iv_work_pool can immediately be freed or reused by the user upon return of the iv_work_pool_put call. Internally, iv_work uses iv_thread(3) for its thread management. SEE ALSO
ivykis(3), iv_thread(3) ivykis 2010-09-14 iv_work(3)
All times are GMT -4. The time now is 07:48 AM.
Unix & Linux Forums Content Copyright 1993-2022. All Rights Reserved.
Privacy Policy