Skip to main content
added 5 characters in body
Source Link
Loki Astari
  • 96.6k
  • 5
  • 125
  • 338
// Sort of pseudo code.
int fact(int n) {

   int partitions = calculateNumberOfPartitions(n);
   int worker     = calculateNumberOfWorkers(n);

   int valuesPerPart = nn+1 / partitions;
   if (partitions * valuesPerPart <= n) {
       ++partitions;++valuesPerPart;
   }

   std::vector<boost::multiprecision::cpp_int>  data(partitions);
   boost::multiprecision::cpp_int               result;

   std::vector<std::function<void()>  jobs;

   // Calculate all factorial for all the partitions.
   for(int loop=0;loop < partitions; loop++) {
       jobs.push_back([&data, loop, n, valuesPerPart](){
             int low  = loop * valuesPerPart;
             int high = low  + valuesPerPart;
             high = high > n ? n+1 : high;

             boost::multiprecision::cpp_int  part = 1;
             for(int val = low; val < high; ++val) {
                 part *= val;
             }
             data[loop] = part;
       });
   }
   // The first (n-1) workers will finish
   // When they do force them to just wait for the last guy.
   std::vector<std::condition_variable>  wait(worker-1);
   for(int loop=0;loop < (worker-1); ++loop) {
       jobs.push_back([&wait, loop](){
           wait[loop].wait();
       });
   }
   // When the last worker finishes.
   // Let him do the reduce job.
   jobs.push_back([&data, &result](){
       for(auto& val: data) {
           result *= val;
       }
   });

   runJobsInParallel(jobs);

   // Now you can release the other workers you put to sleep.
}
// Sort of pseudo code.
int fact(int n) {

   int partitions = calculateNumberOfPartitions(n);
   int worker     = calculateNumberOfWorkers(n);

   int valuesPerPart = n / partitions;
   if (partitions * valuesPerPart <= n) {
       ++partitions;
   }

   std::vector<boost::multiprecision::cpp_int>  data(partitions);
   boost::multiprecision::cpp_int               result;

   std::vector<std::function<void()>  jobs;

   // Calculate all factorial for all the partitions.
   for(int loop=0;loop < partitions; loop++) {
       jobs.push_back([&data, loop, n, valuesPerPart](){
             int low  = loop * valuesPerPart;
             int high = low  + valuesPerPart;
             high = high > n ? n+1 : high;

             boost::multiprecision::cpp_int  part = 1;
             for(int val = low; val < high; ++val) {
                 part *= val;
             }
             data[loop] = part;
       });
   }
   // The first (n-1) workers will finish
   // When they do force them to just wait for the last guy.
   std::vector<std::condition_variable>  wait(worker-1);
   for(int loop=0;loop < (worker-1); ++loop) {
       jobs.push_back([&wait, loop](){
           wait[loop].wait();
       });
   }
   // When the last worker finishes.
   // Let him do the reduce job.
   jobs.push_back([&data, &result](){
       for(auto& val: data) {
           result *= val;
       }
   });

   runJobsInParallel(jobs);

   // Now you can release the other workers you put to sleep.
}
// Sort of pseudo code.
int fact(int n) {

   int partitions = calculateNumberOfPartitions(n);
   int worker     = calculateNumberOfWorkers(n);

   int valuesPerPart = n+1 / partitions;
   if (partitions * valuesPerPart <= n) {
       ++valuesPerPart;
   }

   std::vector<boost::multiprecision::cpp_int>  data(partitions);
   boost::multiprecision::cpp_int               result;

   std::vector<std::function<void()>  jobs;

   // Calculate all factorial for all the partitions.
   for(int loop=0;loop < partitions; loop++) {
       jobs.push_back([&data, loop, n, valuesPerPart](){
             int low  = loop * valuesPerPart;
             int high = low  + valuesPerPart;
             high = high > n ? n+1 : high;

             boost::multiprecision::cpp_int  part = 1;
             for(int val = low; val < high; ++val) {
                 part *= val;
             }
             data[loop] = part;
       });
   }
   // The first (n-1) workers will finish
   // When they do force them to just wait for the last guy.
   std::vector<std::condition_variable>  wait(worker-1);
   for(int loop=0;loop < (worker-1); ++loop) {
       jobs.push_back([&wait, loop](){
           wait[loop].wait();
       });
   }
   // When the last worker finishes.
   // Let him do the reduce job.
   jobs.push_back([&data, &result](){
       for(auto& val: data) {
           result *= val;
       }
   });

   runJobsInParallel(jobs);

   // Now you can release the other workers you put to sleep.
}
added 374 characters in body
Source Link
Loki Astari
  • 96.6k
  • 5
  • 125
  • 338
// Sort of pseudo code.
int fact(int n) { 

   int partitions = calculateNumberOfPartitions(n);
   int worker     = calculateNumberOfWorkers(n);

   int valuesPerPart = n / partitions;
   if (partitions * valuesPerPart <= n) {
       ++partitions;
   }

   std::vector<boost::multiprecision::cpp_int>  data(partitions);
   boost::multiprecision::cpp_int               result;

   std::vector<std::function<void()>  jobs;

   // Calculate all factorial for all the partitions.
   for(int loop=0;loop < partitions; loop++) {
       jobs.push_back([&data, loop, n]n, valuesPerPart](){
           // Calculate factorialint low  = loop * valuesPerPart;
             int high = low  + valuesPerPart;
             high = high > n ? n+1 : high;

             boost::multiprecision::cpp_int  part = 1;
             for(int val = low; val < high; ++val) {
           // The range indicated by loop. part *= val;
           // place it}
 in            data[loop] = part;
       });
   }
   // The first (n-1) workers will finish
   // When they do force them to just wait for the last guy.
   std::vector<std::condition_variable>  wait(worker-1);
   for(int loop=0;loop < (worker-1); ++loop) {
       jobs.push_back([&wait, loop](){
           wait[loop].wait();
       });
   }
   // When the last worker finishes.
   // Let him do the reduce job.
   jobs.push_back([&data, &result](){
       for(auto& val: data) {
           result *= val;
       }
   });

   runJobsInParallel(jobs);

   // Now you can release the other workers you put to sleep.
}
// Sort of pseudo code.
int fact(int n) {
   int partitions = calculateNumberOfPartitions(n);
   int worker     = calculateNumberOfWorkers(n);

   std::vector<boost::multiprecision::cpp_int>  data(partitions);
   boost::multiprecision::cpp_int               result;

   std::vector<std::function<void()>  jobs;

   // Calculate all factorial for all the partitions.
   for(int loop=0;loop < partitions; loop++) {
       jobs.push_back([&data, loop, n](){
           // Calculate factorial for 
           // The range indicated by loop.
           // place it in data[loop]
       });
   }
   // The first (n-1) workers will finish
   // When they do force them to just wait for the last guy.
   std::vector<std::condition_variable>  wait(worker-1);
   for(int loop=0;loop < (worker-1); ++loop) {
       jobs.push_back([&wait, loop](){
           wait[loop].wait();
       });
   }
   // When the last worker finishes.
   // Let him do the reduce job.
   jobs.push_back([&data, &result](){
       for(auto& val: data) {
           result *= val;
       }
   });

   runJobsInParallel(jobs);

   // Now you can release the other workers you put to sleep.
}
// Sort of pseudo code.
int fact(int n) { 

   int partitions = calculateNumberOfPartitions(n);
   int worker     = calculateNumberOfWorkers(n);

   int valuesPerPart = n / partitions;
   if (partitions * valuesPerPart <= n) {
       ++partitions;
   }

   std::vector<boost::multiprecision::cpp_int>  data(partitions);
   boost::multiprecision::cpp_int               result;

   std::vector<std::function<void()>  jobs;

   // Calculate all factorial for all the partitions.
   for(int loop=0;loop < partitions; loop++) {
       jobs.push_back([&data, loop, n, valuesPerPart](){
             int low  = loop * valuesPerPart;
             int high = low  + valuesPerPart;
             high = high > n ? n+1 : high;

             boost::multiprecision::cpp_int  part = 1;
             for(int val = low; val < high; ++val) {
                 part *= val;
             }
             data[loop] = part;
       });
   }
   // The first (n-1) workers will finish
   // When they do force them to just wait for the last guy.
   std::vector<std::condition_variable>  wait(worker-1);
   for(int loop=0;loop < (worker-1); ++loop) {
       jobs.push_back([&wait, loop](){
           wait[loop].wait();
       });
   }
   // When the last worker finishes.
   // Let him do the reduce job.
   jobs.push_back([&data, &result](){
       for(auto& val: data) {
           result *= val;
       }
   });

   runJobsInParallel(jobs);

   // Now you can release the other workers you put to sleep.
}
Source Link
Loki Astari
  • 96.6k
  • 5
  • 125
  • 338

I would change this to a map/reduce problem.

1) Have a set of `N` mappers.
   Each mapper calculates the value for a range.
   Then saves the value for use by the reducer.

2) Reducer waits for all mappers to finish
   Then calculates a result based on the value generated
   by the mappers.

Using this technique you don't need any data locks. You just need a way to know when all the mappers have finished working.

// Sort of pseudo code.
int fact(int n) {
   int partitions = calculateNumberOfPartitions(n);
   int worker     = calculateNumberOfWorkers(n);

   std::vector<boost::multiprecision::cpp_int>  data(partitions);
   boost::multiprecision::cpp_int               result;

   std::vector<std::function<void()>  jobs;

   // Calculate all factorial for all the partitions.
   for(int loop=0;loop < partitions; loop++) {
       jobs.push_back([&data, loop, n](){
           // Calculate factorial for 
           // The range indicated by loop.
           // place it in data[loop]
       });
   }
   // The first (n-1) workers will finish
   // When they do force them to just wait for the last guy.
   std::vector<std::condition_variable>  wait(worker-1);
   for(int loop=0;loop < (worker-1); ++loop) {
       jobs.push_back([&wait, loop](){
           wait[loop].wait();
       });
   }
   // When the last worker finishes.
   // Let him do the reduce job.
   jobs.push_back([&data, &result](){
       for(auto& val: data) {
           result *= val;
       }
   });

   runJobsInParallel(jobs);

   // Now you can release the other workers you put to sleep.
}