Question

Write a parallel program using Pthread based on given sequential solution. Please set the thread number as 10 in your code.

Given Sequential Solution:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX 10240

int total = 0;
int n1,n2;
char *s1,*s2;
FILE *fp;

int readf(FILE *fp)
{
        if((fp=fopen("strings.txt", "r"))==NULL){
                printf("ERROR: can't open string.txt!\n");
                return 0;
        }
        s1=(char *)malloc(sizeof(char)*MAX);
        if(s1==NULL){
                printf("ERROR: Out of memory!\n");
                return -1;
        }
        s2=(char *)malloc(sizeof(char)*MAX);
        if(s2==NULL){
                printf("ERROR: Out of memory\n");
                return -1;
        }
        /*read s1 s2 from the file*/
        s1=fgets(s1, MAX, fp);
        s2=fgets(s2, MAX, fp);
        n1=strlen(s1);  /*length of s1*/
        n2=strlen(s2)-1; /*length of s2*/

        if(s1==NULL || s2==NULL || n1<n2)  /*when error exit*/
                return -1;
        return 0;
}

int num_substring(void)
{
        int i,j,k;
        int count;

        for (i = 0; i <= (n1-n2); i++){   
                count=0;
                for(j = i,k = 0; k < n2; j++,k++){  /*search for the next string of size of n2*/  
                        if (*(s1+j)!=*(s2+k)){
                                break;
                        }else{
                                count++;
                        }

                        if(count==n2){  
                                total++;                /*find a substring in this step*/   
                        }                       
                }
        }
        return total;
}

int main(int argc, char *argv[])
{
        int count;
 
        readf(fp);
        count = num_substring();
        printf("The number of substrings is: %d\n", count);
        return 1;
}

strings.txt file:

Thss is an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. This is an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss ss. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That is a kiwi fruit. This is an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. This is a banana. This is a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ssss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. This is a banana. This is a berry. That is cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. This is a banana. This is a berry. This is cherry. That ss a haw. Thss ss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ssss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. This is a banana. This is a berry. This is cherry. That is a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss ss an avocado. There ss a peach on the tree. This is a banana. This is a berry. This is cherry. This is a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree This is a banana. This is a berry. This is cherry. This is a haw. Thss is a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. This is a banana. This is a berry. This is cherry. This is a haw. This is a lemon. There ss a hickory on the tree. Thss ss an apple. That ss a pear. That ss an orange. That ss a kiwi fruit. Thss ss an avocado. There ss a peach on the tree. Thss ss a banana. That ss a berry. That ss cherry. That ss a haw. Thss ss a lemon. There ss a hickory on the
is

Given Template for program using 10 threads:

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX 10240
#define NUM_THREADS  10

int n1,n2;
char *s1,*s2;
FILE *fp;
int countArray[NUM_THREADS]={0};


//read input file and generate string s1/s2 and length n1/n2
int readf(FILE *fp)
{
        if((fp=fopen("strings.txt", "r"))==NULL){
                printf("ERROR: can't open string.txt!\n");
                return 0;
        }
        s1=(char *)malloc(sizeof(char)*MAX);
        if(s1==NULL){
                printf("ERROR: Out of memory!\n");
                return -1;
        }
        s2=(char *)malloc(sizeof(char)*MAX);
        if(s1==NULL){
                printf("ERROR: Out of memory\n");
                return -1;
        }
        /*read s1 s2 from the file*/
        s1=fgets(s1, MAX, fp);
        s2=fgets(s2, MAX, fp);
        n1=strlen(s1);  /*length of s1*/
        n2=strlen(s2)-1; /*length of s2*/

        if(s1==NULL || s2==NULL || n1<n2)  /*when error exit*/
                return -1;
        return 0;
}

int num_substring(int t)
{
//add your logic here
//1, how to distribute different parts of string s1 into different threads
//2, how to sum up the total number of substring from all threads
        
    return 0;
}

void *calSubStringThread(void *threadid){
    long tid = (long)threadid;
    printf("This is thread %ld, ", tid);
    int num = num_substring(tid);
    printf("find num of is: %d\n", num);
    pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
    pthread_t threads[NUM_THREADS];
    int t, rc;
    int totalNum = 0;

        readf(fp);

        for(t=0; t<NUM_THREADS; t++){
        rc = pthread_create(&threads[t], NULL, calSubStringThread, (void *) (size_t)t);
        if (rc){
            printf("ERROR; return code from pthread_create() is %d\n", rc);
            exit(-1);
        }
    }

    for(t=0; t<NUM_THREADS; t++){
        pthread_join(threads[t], NULL);
    }

        printf("The number of substrings is: %d\n", totalNum);
        return 1;
}

Answer 1

Working code implemented in C and appropriate comments provided for better understanding.

Source Code:

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX 10240
#define NUM_THREADS 10

int n1,n2;
char *s1,*s2;
FILE *fp;
int countArray[NUM_THREADS]={0};
int total;

//read input file and generate string s1/s2 and length n1/n2
int readf(FILE *fp)
{
if((fp=fopen("strings.txt", "r"))==NULL){
printf("ERROR: can't open string.txt!\n");
return 0;
}
s1=(char *)malloc(sizeof(char)*MAX);
if(s1==NULL){
printf("ERROR: Out of memory!\n");
return -1;
}
s2=(char *)malloc(sizeof(char)*MAX);
if(s2==NULL){
printf("ERROR: Out of memory\n");
return -1;
}
/*read s1 s2 from the file*/
s1=fgets(s1, MAX, fp);
s2=fgets(s2, MAX, fp);
n1=strlen(s1); /*length of s1*/
n2=strlen(s2)-1; /*length of s2*/

if(s1==NULL || s2==NULL || n1<n2) /*when error exit*/
return -1;
return 0;
}

void num_substring(int t)
{
//add your logic here
//1, how to distribute different parts of string s1 into different threads
//2, how to sum up the total number of substring from all threads

int i,j,k;
int count;

long tid = (long)t;
printf("id is %ld\n", tid);

for (i = ((n1/10) * tid); i < (n1/10); i++)
{
count =0;
for(j = i, k = 0; k < n2; j++, k++)
{
if (*(s1 + j) != *(s2 + k))
{
break;
}
else
{
count++;
}
if(count == n2)
{
countArray[tid] = countArray[tid] + 1;
}
}
}
for(int i = 0; i < 10; i++)
{
total = total + countArray[i];
}

}

void *calSubStringThread(void *threadid){
long tid = (long)threadid;
printf("This is thread %ld\n", tid);
num_substring(tid);
pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
pthread_t threads[NUM_THREADS];
int t, rc;
int totalNum;

readf(fp);

rc = pthread_create(&threads[0], NULL, calSubStringThread, (void *) (size_t)t);
sleep(1);

for(t=1; t<NUM_THREADS; t++){
rc = pthread_create(&threads[t], NULL, calSubStringThread, (void *) (size_t)t);
if (rc){
printf("ERROR; return code from pthread_create() is %d\n", rc);
exit(-1);
}
}

for(t=0; t<NUM_THREADS; t++){
pthread_join(threads[t], NULL);
}

printf("The number of substrings is: %d\n", total);
pthread_exit(NULL);

return 1;
}
  

Sample Output Screenshots: