Chris@16: // Copyright 2004 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Douglas Gregor
Chris@16: //           Peter Gottschling
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_PARALLEL_DISTRIBUTION_HPP
Chris@16: #define BOOST_PARALLEL_DISTRIBUTION_HPP
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_USE_MPI
Chris@16: #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
Chris@16: #endif
Chris@16: 
Chris@16: #include <cstddef>
Chris@16: #include <vector>
Chris@16: #include <algorithm>
Chris@16: #include <numeric>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/iterator/counting_iterator.hpp>
Chris@16: #include <boost/random/uniform_int.hpp>
Chris@16: #include <boost/shared_ptr.hpp>
Chris@16: #include <typeinfo>
Chris@16: 
Chris@16: namespace boost { namespace parallel {
Chris@16: 
Chris@16: template<typename ProcessGroup, typename SizeType = std::size_t>
Chris@16: class variant_distribution
Chris@16: {
Chris@16: public:
Chris@16:   typedef typename ProcessGroup::process_id_type process_id_type;
Chris@16:   typedef typename ProcessGroup::process_size_type process_size_type;
Chris@16:   typedef SizeType size_type;
Chris@16: 
Chris@16: private:
Chris@16:   struct basic_distribution
Chris@16:   {
Chris@16:     virtual ~basic_distribution() {}
Chris@16:     virtual size_type block_size(process_id_type, size_type) const = 0;
Chris@16:     virtual process_id_type in_process(size_type) const = 0;
Chris@16:     virtual size_type local(size_type) const = 0;
Chris@16:     virtual size_type global(size_type) const = 0;
Chris@16:     virtual size_type global(process_id_type, size_type) const = 0;
Chris@16:     virtual void* address() = 0;
Chris@16:     virtual const void* address() const = 0;
Chris@16:     virtual const std::type_info& type() const = 0;
Chris@16:   };
Chris@16: 
Chris@16:   template<typename Distribution>
Chris@16:   struct poly_distribution : public basic_distribution
Chris@16:   {
Chris@16:     explicit poly_distribution(const Distribution& distribution)
Chris@16:       : distribution_(distribution) { }
Chris@16: 
Chris@16:     virtual size_type block_size(process_id_type id, size_type n) const
Chris@16:     { return distribution_.block_size(id, n); }
Chris@16: 
Chris@16:     virtual process_id_type in_process(size_type i) const
Chris@16:     { return distribution_(i); }
Chris@16: 
Chris@16:     virtual size_type local(size_type i) const
Chris@16:     { return distribution_.local(i); }
Chris@16: 
Chris@16:     virtual size_type global(size_type n) const
Chris@16:     { return distribution_.global(n); }
Chris@16: 
Chris@16:     virtual size_type global(process_id_type id, size_type n) const
Chris@16:     { return distribution_.global(id, n); }
Chris@16: 
Chris@16:     virtual void* address() { return &distribution_; }
Chris@16:     virtual const void* address() const { return &distribution_; }
Chris@16:     virtual const std::type_info& type() const { return typeid(Distribution); }
Chris@16: 
Chris@16:   private:
Chris@16:     Distribution distribution_;
Chris@16:   };
Chris@16: 
Chris@16: public:
Chris@16:   variant_distribution() { }
Chris@16: 
Chris@16:   template<typename Distribution>
Chris@16:   variant_distribution(const Distribution& distribution)
Chris@16:     : distribution_(new poly_distribution<Distribution>(distribution)) { }
Chris@16: 
Chris@16:   size_type block_size(process_id_type id, size_type n) const
Chris@16:   { return distribution_->block_size(id, n); }
Chris@16:   
Chris@16:   process_id_type operator()(size_type i) const
Chris@16:   { return distribution_->in_process(i); }
Chris@16:   
Chris@16:   size_type local(size_type i) const
Chris@16:   { return distribution_->local(i); }
Chris@16:   
Chris@16:   size_type global(size_type n) const
Chris@16:   { return distribution_->global(n); }
Chris@16: 
Chris@16:   size_type global(process_id_type id, size_type n) const
Chris@16:   { return distribution_->global(id, n); }
Chris@16: 
Chris@16:   operator bool() const { return distribution_; }
Chris@16: 
Chris@16:   void clear() { distribution_.reset(); }
Chris@16: 
Chris@16:   template<typename T>
Chris@16:   T* as()
Chris@16:   {
Chris@16:     if (distribution_->type() == typeid(T))
Chris@16:       return static_cast<T*>(distribution_->address());
Chris@16:     else
Chris@16:       return 0;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename T>
Chris@16:   const T* as() const
Chris@16:   {
Chris@16:     if (distribution_->type() == typeid(T))
Chris@16:       return static_cast<T*>(distribution_->address());
Chris@16:     else
Chris@16:       return 0;
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@16:   shared_ptr<basic_distribution> distribution_;
Chris@16: };
Chris@16: 
Chris@16: struct block
Chris@16: {
Chris@16:   template<typename LinearProcessGroup>
Chris@16:   explicit block(const LinearProcessGroup& pg, std::size_t n) 
Chris@16:     : id(process_id(pg)), p(num_processes(pg)), n(n) { }
Chris@16: 
Chris@16:   // If there are n elements in the distributed data structure, returns the number of elements stored locally.
Chris@16:   template<typename SizeType>
Chris@16:   SizeType block_size(SizeType n) const
Chris@16:   { return (n / p) + ((std::size_t)(n % p) > id? 1 : 0); }
Chris@16: 
Chris@16:   // If there are n elements in the distributed data structure, returns the number of elements stored on processor ID
Chris@16:   template<typename SizeType, typename ProcessID>
Chris@16:   SizeType block_size(ProcessID id, SizeType n) const
Chris@16:   { return (n / p) + ((ProcessID)(n % p) > id? 1 : 0); }
Chris@16: 
Chris@16:   // Returns the processor on which element with global index i is stored
Chris@16:   template<typename SizeType>
Chris@16:   SizeType operator()(SizeType i) const
Chris@16:   { 
Chris@16:     SizeType cutoff_processor = n % p;
Chris@16:     SizeType cutoff = cutoff_processor * (n / p + 1);
Chris@16: 
Chris@16:     if (i < cutoff) return i / (n / p + 1);
Chris@16:     else return cutoff_processor + (i - cutoff) / (n / p);
Chris@16:   }
Chris@16: 
Chris@16:   // Find the starting index for processor with the given id
Chris@16:   template<typename ID>
Chris@16:   std::size_t start(ID id) const
Chris@16:   {
Chris@16:     std::size_t estimate = id * (n / p + 1);
Chris@16:     ID cutoff_processor = n % p;
Chris@16:     if (id < cutoff_processor) return estimate;
Chris@16:     else return estimate - (id - cutoff_processor);
Chris@16:   }
Chris@16: 
Chris@16:   // Find the local index for the ith global element
Chris@16:   template<typename SizeType>
Chris@16:   SizeType local(SizeType i) const
Chris@16:   { 
Chris@16:     SizeType owner = (*this)(i);
Chris@16:     return i - start(owner);
Chris@16:   }
Chris@16: 
Chris@16:   // Returns the global index of local element i
Chris@16:   template<typename SizeType>
Chris@16:   SizeType global(SizeType i) const
Chris@16:   { return global(id, i); }
Chris@16: 
Chris@16:   // Returns the global index of the ith local element on processor id
Chris@16:   template<typename ProcessID, typename SizeType>
Chris@16:   SizeType global(ProcessID id, SizeType i) const
Chris@16:   { return i + start(id); }
Chris@16: 
Chris@16:  private:
Chris@16:   std::size_t id; //< The ID number of this processor
Chris@16:   std::size_t p;  //< The number of processors
Chris@16:   std::size_t n;  //< The size of the problem space
Chris@16: };
Chris@16: 
Chris@16: // Block distribution with arbitrary block sizes
Chris@16: struct uneven_block
Chris@16: {
Chris@16:   typedef std::vector<std::size_t>    size_vector;
Chris@16: 
Chris@16:   template<typename LinearProcessGroup>
Chris@16:   explicit uneven_block(const LinearProcessGroup& pg, const std::vector<std::size_t>& local_sizes) 
Chris@16:     : id(process_id(pg)), p(num_processes(pg)), local_sizes(local_sizes)
Chris@16:   { 
Chris@16:     BOOST_ASSERT(local_sizes.size() == p);
Chris@16:     local_starts.resize(p + 1);
Chris@16:     local_starts[0] = 0;
Chris@16:     std::partial_sum(local_sizes.begin(), local_sizes.end(), &local_starts[1]);
Chris@16:     n = local_starts[p];
Chris@16:   }
Chris@16: 
Chris@16:   // To do maybe: enter local size in each process and gather in constructor (much handier)
Chris@16:   // template<typename LinearProcessGroup>
Chris@16:   // explicit uneven_block(const LinearProcessGroup& pg, std::size_t my_local_size) 
Chris@16: 
Chris@16:   // If there are n elements in the distributed data structure, returns the number of elements stored locally.
Chris@16:   template<typename SizeType>
Chris@16:   SizeType block_size(SizeType) const
Chris@16:   { return local_sizes[id]; }
Chris@16: 
Chris@16:   // If there are n elements in the distributed data structure, returns the number of elements stored on processor ID
Chris@16:   template<typename SizeType, typename ProcessID>
Chris@16:   SizeType block_size(ProcessID id, SizeType) const
Chris@16:   { return local_sizes[id]; }
Chris@16: 
Chris@16:   // Returns the processor on which element with global index i is stored
Chris@16:   template<typename SizeType>
Chris@16:   SizeType operator()(SizeType i) const
Chris@16:   {
Chris@16:     BOOST_ASSERT (i >= (SizeType) 0 && i < (SizeType) n); // check for valid range
Chris@16:     size_vector::const_iterator lb = std::lower_bound(local_starts.begin(), local_starts.end(), (std::size_t) i);
Chris@16:     return ((SizeType)(*lb) == i ? lb : --lb) - local_starts.begin();
Chris@16:   }
Chris@16: 
Chris@16:   // Find the starting index for processor with the given id
Chris@16:   template<typename ID>
Chris@16:   std::size_t start(ID id) const 
Chris@16:   {
Chris@16:     return local_starts[id];
Chris@16:   }
Chris@16: 
Chris@16:   // Find the local index for the ith global element
Chris@16:   template<typename SizeType>
Chris@16:   SizeType local(SizeType i) const
Chris@16:   { 
Chris@16:     SizeType owner = (*this)(i);
Chris@16:     return i - start(owner);
Chris@16:   }
Chris@16: 
Chris@16:   // Returns the global index of local element i
Chris@16:   template<typename SizeType>
Chris@16:   SizeType global(SizeType i) const
Chris@16:   { return global(id, i); }
Chris@16: 
Chris@16:   // Returns the global index of the ith local element on processor id
Chris@16:   template<typename ProcessID, typename SizeType>
Chris@16:   SizeType global(ProcessID id, SizeType i) const
Chris@16:   { return i + start(id); }
Chris@16: 
Chris@16:  private:
Chris@16:   std::size_t              id;           //< The ID number of this processor
Chris@16:   std::size_t              p;            //< The number of processors
Chris@16:   std::size_t              n;            //< The size of the problem space
Chris@16:   std::vector<std::size_t> local_sizes;  //< The sizes of all blocks
Chris@16:   std::vector<std::size_t> local_starts; //< Lowest global index of each block
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: struct oned_block_cyclic
Chris@16: {
Chris@16:   template<typename LinearProcessGroup>
Chris@16:   explicit oned_block_cyclic(const LinearProcessGroup& pg, std::size_t size)
Chris@16:     : id(process_id(pg)), p(num_processes(pg)), size(size) { }
Chris@16:       
Chris@16:   template<typename SizeType>
Chris@16:   SizeType block_size(SizeType n) const
Chris@16:   { 
Chris@16:     return block_size(id, n);
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType, typename ProcessID>
Chris@16:   SizeType block_size(ProcessID id, SizeType n) const
Chris@16:   {
Chris@16:     SizeType all_blocks = n / size;
Chris@16:     SizeType extra_elements = n % size;
Chris@16:     SizeType everyone_gets = all_blocks / p;
Chris@16:     SizeType extra_blocks = all_blocks % p;
Chris@16:     SizeType my_blocks = everyone_gets + (p < extra_blocks? 1 : 0);
Chris@16:     SizeType my_elements = my_blocks * size 
Chris@16:                          + (p == extra_blocks? extra_elements : 0);
Chris@16:     return my_elements;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType operator()(SizeType i) const
Chris@16:   { 
Chris@16:     return (i / size) % p;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType local(SizeType i) const
Chris@16:   { 
Chris@16:     return ((i / size) / p) * size + i % size;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType global(SizeType i) const
Chris@16:   { return global(id, i); }
Chris@16: 
Chris@16:   template<typename ProcessID, typename SizeType>
Chris@16:   SizeType global(ProcessID id, SizeType i) const
Chris@16:   { 
Chris@16:     return ((i / size) * p + id) * size + i % size;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   std::size_t id;                   //< The ID number of this processor
Chris@16:   std::size_t p;                    //< The number of processors
Chris@16:   std::size_t size;                 //< Block size
Chris@16: };
Chris@16: 
Chris@16: struct twod_block_cyclic
Chris@16: {
Chris@16:   template<typename LinearProcessGroup>
Chris@16:   explicit twod_block_cyclic(const LinearProcessGroup& pg,
Chris@16:                              std::size_t block_rows, std::size_t block_columns,
Chris@16:                              std::size_t data_columns_per_row)
Chris@16:     : id(process_id(pg)), p(num_processes(pg)), 
Chris@16:       block_rows(block_rows), block_columns(block_columns), 
Chris@16:       data_columns_per_row(data_columns_per_row)
Chris@16:   { }
Chris@16:       
Chris@16:   template<typename SizeType>
Chris@16:   SizeType block_size(SizeType n) const
Chris@16:   { 
Chris@16:     return block_size(id, n);
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType, typename ProcessID>
Chris@16:   SizeType block_size(ProcessID id, SizeType n) const
Chris@16:   {
Chris@16:     // TBD: This is really lame :)
Chris@16:     int result = -1;
Chris@16:     while (n > 0) {
Chris@16:       --n;
Chris@16:       if ((*this)(n) == id && (int)local(n) > result) result = local(n);
Chris@16:     }
Chris@16:     ++result;
Chris@16: 
Chris@16:     //    std::cerr << "Block size of id " << id << " is " << result << std::endl;
Chris@16:     return result;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType operator()(SizeType i) const
Chris@16:   { 
Chris@16:     SizeType result = get_block_num(i) % p;
Chris@16:     //    std::cerr << "Item " << i << " goes on processor " << result << std::endl;
Chris@16:     return result;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType local(SizeType i) const
Chris@16:   { 
Chris@16:     // Compute the start of the block
Chris@16:     std::size_t block_num = get_block_num(i);
Chris@16:     //    std::cerr << "Item " << i << " is in block #" << block_num << std::endl;
Chris@16: 
Chris@16:     std::size_t local_block_num = block_num / p;
Chris@16:     std::size_t block_start = local_block_num * block_rows * block_columns;
Chris@16: 
Chris@16:     // Compute the offset into the block 
Chris@16:     std::size_t data_row = i / data_columns_per_row;
Chris@16:     std::size_t data_col = i % data_columns_per_row;
Chris@16:     std::size_t block_offset = (data_row % block_rows) * block_columns 
Chris@16:                              + (data_col % block_columns);    
Chris@16: 
Chris@16:     //    std::cerr << "Item " << i << " maps to local index " << block_start+block_offset << std::endl;
Chris@16:     return block_start + block_offset;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType global(SizeType i) const
Chris@16:   { 
Chris@16:     // Compute the (global) block in which this element resides
Chris@16:     SizeType local_block_num = i / (block_rows * block_columns);
Chris@16:     SizeType block_offset = i % (block_rows * block_columns);
Chris@16:     SizeType block_num = local_block_num * p + id;
Chris@16: 
Chris@16:     // Compute the position of the start of the block (globally)
Chris@16:     SizeType block_start = block_num * block_rows * block_columns;
Chris@16: 
Chris@16:     std::cerr << "Block " << block_num << " starts at index " << block_start
Chris@16:               << std::endl;
Chris@16: 
Chris@16:     // Compute the row and column of this block
Chris@16:     SizeType block_row = block_num / (data_columns_per_row / block_columns);
Chris@16:     SizeType block_col = block_num % (data_columns_per_row / block_columns);
Chris@16: 
Chris@16:     SizeType row_in_block = block_offset / block_columns;
Chris@16:     SizeType col_in_block = block_offset % block_columns;
Chris@16: 
Chris@16:     std::cerr << "Local index " << i << " is in block at row " << block_row
Chris@16:               << ", column " << block_col << ", in-block row " << row_in_block
Chris@16:               << ", in-block col " << col_in_block << std::endl;
Chris@16: 
Chris@16:     SizeType result = block_row * block_rows + block_col * block_columns
Chris@16:                     + row_in_block * block_rows + col_in_block;
Chris@16: 
Chris@16: 
Chris@16:     std::cerr << "global(" << i << "@" << id << ") = " << result 
Chris@16:               << " =? " << local(result) << std::endl;
Chris@16:     BOOST_ASSERT(i == local(result));
Chris@16:     return result;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   template<typename SizeType>
Chris@16:   std::size_t get_block_num(SizeType i) const
Chris@16:   {
Chris@16:     std::size_t data_row = i / data_columns_per_row;
Chris@16:     std::size_t data_col = i % data_columns_per_row;
Chris@16:     std::size_t block_row = data_row / block_rows;
Chris@16:     std::size_t block_col = data_col / block_columns;
Chris@16:     std::size_t blocks_in_row = data_columns_per_row / block_columns;
Chris@16:     std::size_t block_num = block_col * blocks_in_row + block_row;
Chris@16:     return block_num;
Chris@16:   }
Chris@16: 
Chris@16:   std::size_t id;                   //< The ID number of this processor
Chris@16:   std::size_t p;                    //< The number of processors
Chris@16:   std::size_t block_rows;           //< The # of rows in each block
Chris@16:   std::size_t block_columns;        //< The # of columns in each block
Chris@16:   std::size_t data_columns_per_row; //< The # of columns per row of data
Chris@16: };
Chris@16: 
Chris@16: class twod_random
Chris@16: {
Chris@16:   template<typename RandomNumberGen>
Chris@16:   struct random_int
Chris@16:   {
Chris@16:     explicit random_int(RandomNumberGen& gen) : gen(gen) { }
Chris@16: 
Chris@16:     template<typename T>
Chris@16:     T operator()(T n) const
Chris@16:     {
Chris@16:       uniform_int<T> distrib(0, n-1);
Chris@16:       return distrib(gen);
Chris@16:     }
Chris@16: 
Chris@16:   private:
Chris@16:     RandomNumberGen& gen;
Chris@16:   };
Chris@16:   
Chris@16:  public:
Chris@16:   template<typename LinearProcessGroup, typename RandomNumberGen>
Chris@16:   explicit twod_random(const LinearProcessGroup& pg,
Chris@16:                        std::size_t block_rows, std::size_t block_columns,
Chris@16:                        std::size_t data_columns_per_row,
Chris@16:                        std::size_t n,
Chris@16:                        RandomNumberGen& gen)
Chris@16:     : id(process_id(pg)), p(num_processes(pg)), 
Chris@16:       block_rows(block_rows), block_columns(block_columns), 
Chris@16:       data_columns_per_row(data_columns_per_row),
Chris@16:       global_to_local(n / (block_rows * block_columns))
Chris@16:   { 
Chris@16:     std::copy(make_counting_iterator(std::size_t(0)),
Chris@16:               make_counting_iterator(global_to_local.size()),
Chris@16:               global_to_local.begin());
Chris@16: 
Chris@16:     random_int<RandomNumberGen> rand(gen);
Chris@16:     std::random_shuffle(global_to_local.begin(), global_to_local.end(), rand);
Chris@16:   }
Chris@16:       
Chris@16:   template<typename SizeType>
Chris@16:   SizeType block_size(SizeType n) const
Chris@16:   { 
Chris@16:     return block_size(id, n);
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType, typename ProcessID>
Chris@16:   SizeType block_size(ProcessID id, SizeType n) const
Chris@16:   {
Chris@16:     // TBD: This is really lame :)
Chris@16:     int result = -1;
Chris@16:     while (n > 0) {
Chris@16:       --n;
Chris@16:       if ((*this)(n) == id && (int)local(n) > result) result = local(n);
Chris@16:     }
Chris@16:     ++result;
Chris@16: 
Chris@16:     //    std::cerr << "Block size of id " << id << " is " << result << std::endl;
Chris@16:     return result;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType operator()(SizeType i) const
Chris@16:   { 
Chris@16:     SizeType result = get_block_num(i) % p;
Chris@16:     //    std::cerr << "Item " << i << " goes on processor " << result << std::endl;
Chris@16:     return result;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType local(SizeType i) const
Chris@16:   { 
Chris@16:     // Compute the start of the block
Chris@16:     std::size_t block_num = get_block_num(i);
Chris@16:     //    std::cerr << "Item " << i << " is in block #" << block_num << std::endl;
Chris@16: 
Chris@16:     std::size_t local_block_num = block_num / p;
Chris@16:     std::size_t block_start = local_block_num * block_rows * block_columns;
Chris@16: 
Chris@16:     // Compute the offset into the block 
Chris@16:     std::size_t data_row = i / data_columns_per_row;
Chris@16:     std::size_t data_col = i % data_columns_per_row;
Chris@16:     std::size_t block_offset = (data_row % block_rows) * block_columns 
Chris@16:                              + (data_col % block_columns);    
Chris@16: 
Chris@16:     //    std::cerr << "Item " << i << " maps to local index " << block_start+block_offset << std::endl;
Chris@16:     return block_start + block_offset;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   template<typename SizeType>
Chris@16:   std::size_t get_block_num(SizeType i) const
Chris@16:   {
Chris@16:     std::size_t data_row = i / data_columns_per_row;
Chris@16:     std::size_t data_col = i % data_columns_per_row;
Chris@16:     std::size_t block_row = data_row / block_rows;
Chris@16:     std::size_t block_col = data_col / block_columns;
Chris@16:     std::size_t blocks_in_row = data_columns_per_row / block_columns;
Chris@16:     std::size_t block_num = block_col * blocks_in_row + block_row;
Chris@16:     return global_to_local[block_num];
Chris@16:   }
Chris@16: 
Chris@16:   std::size_t id;                   //< The ID number of this processor
Chris@16:   std::size_t p;                    //< The number of processors
Chris@16:   std::size_t block_rows;           //< The # of rows in each block
Chris@16:   std::size_t block_columns;        //< The # of columns in each block
Chris@16:   std::size_t data_columns_per_row; //< The # of columns per row of data
Chris@16:   std::vector<std::size_t> global_to_local;
Chris@16: };
Chris@16: 
Chris@16: class random_distribution
Chris@16: {
Chris@16:   template<typename RandomNumberGen>
Chris@16:   struct random_int
Chris@16:   {
Chris@16:     explicit random_int(RandomNumberGen& gen) : gen(gen) { }
Chris@16: 
Chris@16:     template<typename T>
Chris@16:     T operator()(T n) const
Chris@16:     {
Chris@16:       uniform_int<T> distrib(0, n-1);
Chris@16:       return distrib(gen);
Chris@16:     }
Chris@16: 
Chris@16:   private:
Chris@16:     RandomNumberGen& gen;
Chris@16:   };
Chris@16:   
Chris@16:  public:
Chris@16:   template<typename LinearProcessGroup, typename RandomNumberGen>
Chris@16:   random_distribution(const LinearProcessGroup& pg, RandomNumberGen& gen,
Chris@16:                       std::size_t n)
Chris@16:     : base(pg, n), local_to_global(n), global_to_local(n)
Chris@16:   {
Chris@16:     std::copy(make_counting_iterator(std::size_t(0)),
Chris@16:               make_counting_iterator(n),
Chris@16:               local_to_global.begin());
Chris@16: 
Chris@16:     random_int<RandomNumberGen> rand(gen);
Chris@16:     std::random_shuffle(local_to_global.begin(), local_to_global.end(), rand);
Chris@16:                         
Chris@16: 
Chris@16:     for (std::vector<std::size_t>::size_type i = 0; i < n; ++i)
Chris@16:       global_to_local[local_to_global[i]] = i;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType block_size(SizeType n) const
Chris@16:   { return base.block_size(n); }
Chris@16: 
Chris@16:   template<typename SizeType, typename ProcessID>
Chris@16:   SizeType block_size(ProcessID id, SizeType n) const
Chris@16:   { return base.block_size(id, n); }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType operator()(SizeType i) const
Chris@16:   {
Chris@16:     return base(global_to_local[i]);
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType local(SizeType i) const
Chris@16:   { 
Chris@16:     return base.local(global_to_local[i]);
Chris@16:   }
Chris@16: 
Chris@16:   template<typename ProcessID, typename SizeType>
Chris@16:   SizeType global(ProcessID p, SizeType i) const
Chris@16:   { 
Chris@16:     return local_to_global[base.global(p, i)];
Chris@16:   }
Chris@16: 
Chris@16:   template<typename SizeType>
Chris@16:   SizeType global(SizeType i) const
Chris@16:   { 
Chris@16:     return local_to_global[base.global(i)];
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   block base;
Chris@16:   std::vector<std::size_t> local_to_global;
Chris@16:   std::vector<std::size_t> global_to_local;
Chris@16: };
Chris@16: 
Chris@16: } } // end namespace boost::parallel
Chris@16: 
Chris@16: #endif // BOOST_PARALLEL_DISTRIBUTION_HPP
Chris@16: