________________________________________________________

Descriptions for Implementation of Pthreads Programs

________________________________________________________

Example 1: Description for implementation of Pthreads program to print Hello World

• Objective : Write a Pthreads program to print "Hello World".
• Description:
  This is a very simple program to get the feel of threads and to get a view of how threads actually work. The implementation is as follows: The main thread creates two child threads. These threads print the words "Hello" and "World!" individually. Though there is no actual parallelism involved, this is just to demonstrate the working of threads. It is to be however noted that depending on the system load and the implementation of Pthreads Standard, the message may not always be "Hello World!". It can be "World! Hello" depending on which thread is scheduled to execute first. This also demonstrates the use of "Pthread_join".
• Input : None
• Ouput : Hello World! or World! Hello
  

Example 2 : Description for implementation of Pthreads program to find Sum of first n Natural Numbers.

• Objective: Write a Pthreads program to find sum of first n natural numbers.
• Description:
  This program prints the sum of first n natural numbers. This introduces the concept of a MutEx or a "Mutual Exclusion". Each thread adds its assigned number to a global variable. When all the threads are done, the global variable will contain the result. It uses a mutex variable to make sure that only one thread is updating the variable at any given time.
• Input: Number of Threads.
• Output: Sum of first n natural numbers, n is the number of threads specified.

Example 3 : Description for implementation of Pthreads program to compute the value of PI function by Numerical Integration

• Objective: Write a Pthreads program to compute the value of PI function by numerical integration of a function f(x) = 4/(1+x ² ) between the limits 0 and 1.
• Description:
  This program computes the value of PI over a given interval using Numerical integration. The main thread distributes the given interval uniformly over the number of threads. Each thread calculates its part of the interval and finally adds it up to the result variable. Each thread locks a mutex before doing the same to guarantee the atomicity of the operation.
• Input: Number of Threads.
• Output: Calculated Value of PI

Example 4 : Description for implementation of Pthreads program to compute the dot product of two vectors using block striped partitioning with uniform data distribution

• Objective: To write a Pthreads program to compute the vector-vector multiplication with Pthreads using block striped partitioning for uniform data distribution . Assume that the vectors are of size n and p is number of processors used and n is a multiple of p.
• Description:
  This is an implementation of Vector-Vector multiplication using the block striped partitioning algorithm. Each thread multiplies the corresponding elements and writes the product into the result vector. A Mutex is used on the result vector to guarantee atomicity. The thread accesses the elements based on its id which is allocated by the main thread in the order of their creation. As the number of threads and the number of elements is known, the corresponding elements to be accessed can easily be computed.
• Input: Vector Size and Number Threads. Number of threads should be a factor of Vector size.
• Output: Dot Product of the given vectors.

Example 5 : Description for implementation of Pthreads program to compute Infinity Norm of the Matrix using block striped partitioning with row wise data distribution

• Objective: Write a Pthreads program to calculate Infinity norm of a matrix using row wise block striped partitioning .
• Description:

  Infinity Norm of a Matrix: The Row-Wise infinity norm of a matrix is defined to be the maximum of sums of absolute  values of elements in a row, over all rows.

  In the row wise distribution, each thread finds the sum of the elements of that row and compares it with the result variable which is initialized to zero. If the sum is greater than the current value of the result, it updates the result variable to reflect the new result. A Mutex is used on the result variable. Distribution of rows is done knowing the id of each thread assigned by the main thread in the order of their creation and the total number of threads.

• Input: Number of Threads and the input file. Number of threads must be a factor of number of rows.
• Output: Infinity Norm of the given Matrix.
• Input file
  A sample input file for the matrix A (8 x 8) is given below : 
  8  8 
  -1.0   2.0     3.0     4.0       5.0      6.0      7.0      8.0 
  2.0     3.0     4.0      5.0      6.0      7.0      8.0      9.0 
  3.0     4.0     5.0      6.0      7.0      8.0      9.0    10.0 
  4.0     5.0     6.0      7.0      8.0      9.0    10.0    11.0 
  5.0     6.0     7.0      8.0      9.0    10.0    11.0    12.0 
  6.0     7.0     8.0      9.0    10.0    11.0    12.0    13.0 
  7.0     8.0     8.0    10.0    11.0    12.0    13.0    14.0 
  8.0   -9.0   10.0    11.0    12.0    13.0    14.0    15.0 

Example 6 : Description for implementation of Pthreads program to compute Infinity Norm of the Matrix using block striped partitioning with column wise distribution

• Objective: Write a Pthreads program to calculates Row-Wise infinity norm of a matrix using column wise block striped partitioning .
• Description:
  In this method, the total columns are distributed among the child threads. Each thread adds the value to the corresponding element in a vector whose length is equal to the number of rows of the matrix. Each element of the vector that holds the row-wise sum of the matrix is protected by a mutex to guarantee granularity of the operation. When all the threads are done, the vector holds the sum of each row of the matrix. The main thread now picks the maximum of the sums and prints it as the Infinity Norm.
• Input: Number of Threads and the input file. Number of threads must be a factor of number of columns.
• Output: Infinity Norm of the given Matrix.
• Input file
  A sample input file for the matrix A (8 x 8) is given below : 
  8  8 
  -1.0   2.0     3.0     4.0       5.0      6.0      7.0      8.0 
  2.0     3.0     4.0      5.0      6.0      7.0      8.0      9.0 
  3.0     4.0     5.0      6.0      7.0      8.0      9.0    10.0 
  4.0     5.0     6.0      7.0      8.0      9.0    10.0    11.0 
  5.0     6.0     7.0      8.0      9.0    10.0    11.0    12.0 
  6.0     7.0     8.0      9.0    10.0    11.0    12.0    13.0 
  7.0     8.0     8.0    10.0    11.0    12.0    13.0    14.0 
  8.0   -9.0   10.0    11.0    12.0    13.0    14.0    15.0 

Example 7 : Description for implementation of Pthreads program to compute Matrix-Vector Multiplication using self scheduling algorithm

• Objective: To write a Pthreads program, for computing the matrix-vector multiplication with 'p' threads using self scheduling algorithm.
• Description:
  In self scheduling algorithm, a master distributes the rows of the matrix to worker  threads. The worker threads calculate the dot product of the given row and the vector. When all the workers finish their part of the work, the resultant vector is the product of the given matrix and the vector.

  In this implementation, the role of a master is emulated using a variable to distribute the work to the worker threads. This variable will maintain the current row that needs to be operated upon. A mutex is used on this variable to ensure granularity of the operations. Each thread when free checks this variable for the row to use and increments the value to reflect the change. The result is placed in the corresponding cell based on the element used.

• Input: Number of Rows, Columns of the matrix and number of Threads. Number of threads is a factor of  the number of rows..
• Output: Product of Matrix Vector Multiplication.

Example 8 : Description for implementation of Pthreads program to compute Matrix-Matrix Multiplication using self scheduling algorithm

• Objective: To write a Pthreads program, for computing the matrix-matrix multiplication with p threads using self scheduling algorithm.
• Description:
  There is no master to distribute the work as that would lead to a complicated program. But, the role of the master is emulated using a variable that indicates the row that is to be operated upon when a thread becomes free. Each thread, as soon as it is created, checks the variable to know which row to operate up on and then increments the variable value to reflect the change. This is repeated till the entire matrix has been processed. The result is placed in the corresponding cell based on the row and column operated. A mutex is used on the variable maintaining the current row to ensure granularity of the operations.
• Input: Number of Rows, Columns of matrix and the number of Threads.
• Output: Product of Matrix-Matrix Multiplication..

Example 9 : Description for implementation of Pthreads program to compute Matrix-Matrix Multiplication using checkerboard partitioning

• Objective: To write a Pthreads program for computing the matrix-vector multiplication using checkerboard partitioning of the matrices.
  Assume that p= q*q and the size of square matrices A and B is evenly divisible by q where p is number of threads.
• Description:
  This is an implementation of Matrix Vector multiplication using checkerboard partitioning. The main thread checks is the given number of threads is a perfect square. And then it splits the matrix over the number of threads. Each thread calculates the partial sum of the resultant vector and adds it up to the existing value in the resultant vector. Each cell of the resultant vector is protected by a Mutex to guarantee the atomicity of the operation.
• Input: Number of Rows, Columns of the matrix and the number of Threads.
• Output: Resultant Matrix.