BARRIER.H AND BARRIER.CPP WHERE IT SAYS "WRITE YOUR CODE HERE"..
ALSO REMEMBER TO IMPLEMENT THE SEMAPHORE PART REFERENCED IN THE
INSTRUCTIONS,
- Please Write All Programs In C Fill Out The Parts In Barrier H And Barrier Cpp Where It Says Write Your Code Here 1 (117.72 KiB) Viewed 20 times
- Please Write All Programs In C Fill Out The Parts In Barrier H And Barrier Cpp Where It Says Write Your Code Here 2 (49.29 KiB) Viewed 20 times
- Please Write All Programs In C Fill Out The Parts In Barrier H And Barrier Cpp Where It Says Write Your Code Here 3 (34.35 KiB) Viewed 20 times
#include <iostream>
#include <thread>
#include <string>
#include <math.h>
#include
"barrier.h"
using namespace std;
int sizeOfInput = 1000;
int numberOfThreads = 8;
int numberOfPhases = 0;
int **data; // An array to store the input array, output array
and intermediate results
std::thread* workers; // An array to store information about
worker threads
synchronization::barrier* rendevousz; // A reusable
barrier for worker threads to synchronize
void doWork( int myid ) { // The function executed by a worker
thread
int sizeOfChunk = sizeOfInput /
numberOfThreads;
// compute the beginning and ending indices of the
chunk
int mystart = myid * sizeOfChunk;
int myfinish = myid == numberOfThreads - 1 ?
sizeOfInput : mystart + sizeOfChunk;
int fixed = 1; // used by the prefix sum
algorithm
for(int i = 0; i < numberOfPhases; ++i)
{
// execute phase i
for(int j = mystart; j < myfinish;
++j)
{ // compute the new values for my
chunk
if (j < fixed)
{
data[i+1][j] =
data[j]; // simply copy the entry
}
else
{ // compute the sum of
two specific entries
data[i+1][j] =
data[j] + data[j-fixed];
}
}
fixed = 2*fixed; // double the value of
fixed
// Wait until all threads have completed
their work before moving to the next phase
rendevousz->arriveAndWait( );
}
return;
}
int main( int argc, char** argv )
{
if (argc < 3) {
cerr << "Too few arguments" <<
endl;
exit( 1 );
}
// Read the size of the input array (n) and the
number of worker threads (p) to use
sizeOfInput = stoi( argv[1] );
numberOfThreads = stoi( argv[2] );
if ( sizeOfInput <= 0 || numberOfThreads <= 0
) {
cerr << "One of the arguments is
invalid" << endl;
exit( 1 );
}
// Calculate the number of phases (m) in the
algorithm, given by ceiling of log2(n)
numberOfPhases = ceil( log2( sizeOfInput ) );
// Allocate space to store pointers to m+1
arrays
// data[0] stores the input array
// data[m] stores the output array
// data[1]...data[m-1] store
intermediate results
// data[i+1] is computed from data
in phase i, where i = 0,...,m-1
data = new int*[numberOfPhases+1];
// Allocate space for each of the m+1 individual
arrays
for(int i = 0; i < numberOfPhases+1; ++i)
{
data = new int[sizeOfInput];
}
// Initialize elements of the input array
(data[0])
for(int j = 0; j < sizeOfInput; ++j)
{
data[0][j] = 1;
}
// Create a barrier object to be used by worker
threads to synchronize movement from one phase to the next
// a thread can advance to phase i+1
only after ALL threads have completed phase i
rendevousz = new synchronization::barrier(
numberOfThreads );
// Create worker threads
// first parameter is the name of the
function each thread has to execute
// second parameter if the identifier
of the worker thread
workers = new std::thread[numberOfThreads];
for(int i = 0; i < numberOfThreads; ++i)
workers = std::thread( doWork, i );
// Wait for all worker threads to terminate
// It is crucial to join to all the
child threads in order to wait for them to complete
// If the main thread terminates
before the child threads, it will force termination all the child
threads
for(int i = 0; i < numberOfThreads; ++i)
workers.join( );
// Print the output array
for(int j = 0; j < sizeOfInput; ++j)
std::cout << "output[" << j
<< "] = " << data[numberOfPhases][j] <<
std::endl;
// Cleanup: deallocate all dynamically allocated
objects
for(int i = 0; i < numberOfThreads; ++i)
{
delete[] workers;
workers = NULL;
}
for(int i = 0; i < numberOfPhases+1; ++i)
{
delete[] data;
data = NULL;
}
delete data;
data = NULL;
delete rendevousz;
rendevousz = NULL;
return 0;
}
Design and implement a barrier using semaphores. Your barrier should support one method, namely arriveAndWait(). A thread invoking the method is blocked until all threads have arrived at the barrier (in other words, invoked the arriveAndWait() method of the barrier) at which point all threads are released from the barrier and can resume their respective executions. The barrier should be reusable, that is, threads can use the same barrier object multiple times to synchronize with each other. Ensure that your design and implementation of a barrier satisfies the following two properties: (a) safety: no thread is released from the barrier prematurely, and (b) liveness: once all threads have arrived at the barrier, all threads are released from the barrier eventually. 1.1 Testing your Barrier To test your barrier, you will be provided with a program that solves the prefix sum problem using Hillis and Steele's parallel algorithm. The algorithm executes in phases. All threads must complete the current phase before any thread can advance to the next phase, which is achieved using a barrier. 1.2 Semaphores Write your program in C/C++. For this project, we will be using POSIX implementation of semaphores. You will need to include the header file semaphore.h in your program. The functions you will need to use in your program are sem_init, sem_wait, sem_post and sem_destroy. You can learn more about these functions by reading their man pages.
#ifndef BARRIER_H #define BARRIER_H #include <semaphore.h> namespace synchronization { // Provides a reusable barrier class barrier { private: // Declare your variables here public: // Constructor barrier(int numberOfThreads ); // Destructor ~barrier(); // Function to wait at the barrier until all threads have reached the barrier void arriveAndWait ( void ); }; } #endif
#include "barrier.h" namespace synchronization { barrier::barrier(int numberOfThreads ) { // Write your code here return; } barrier::~barrier() { } // Write your code here return; } void barrier::arriveAndWait(void) { // Write your code here return;