Running Time of a Parallel Program and a Serial Program. What, Why, How?

The Running time of any computer program is depends on the number of steps or lines of codes of the program which is depends upon the algorithm of that code. For solving any real world problem we have to formulate that problem and design the algorithm. While designing the algorithm, it is very important to analyse the algorithm based on its time complexity. The efficient algorithm is fast means its time complexity is less. So to minimise the time complexity the programmer has to design an algorithm with minimum number of steps.

There are two aspects for designing the program. The programmer can design it in serial way or in parallel way. In the serial program the next step is depends on the previous step, so there is the dependency criteria for the design. However,  in parallel program the dependency is less or no. So in parallel program we can easily divided the program into parts and these parts can execute independently and parallel, results in less running time and complexity.

How to Design Parallel Programs? See Here .....


To minimise the time complexity we need to parallelize the program. But, we can not parallelize all the programs. For example, the Fibonaci Series program can not be parallelize, because the next number in the series is depends on the previous number.

If we want to add two matrix then this program can be parallelize, because each element of the matrix will be independently added with the element of other matrix.

The speed of parallel program is again depends on the number of cores in your system. You can create threads to run on these cores independently, with each thread executes the part of the code. For example in matrix addition each thread will add the element of the two matrices.

Lets see an example:
Suppose we have to print hello world 10000 times on the screen. Below is the C code for serial program and using threads which is an OPENMP program.

C Code

#include<stdio.h>
#include<time.h>
void main()
{
clock_t starttime;
clock_t endtime;
   int i;

double timeinterval;
starttime=clock();
for (i = 0; i < 10000; i++) {
      
         printf("Hello World");
      }

endtime=clock();
timeinterval=(double)(endtime-starttime)/CLOCKS_PER_SEC;
printf("\nTime required for execution=%lf Seconds.\n",timeinterval);

}

Output:

OPENMP Code

#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include<time.h>

int main (int argc, char *argv[]) 
{
clock_t starttime;
clock_t endtime;
double timeinterval;
int i;
starttime=clock();  

#pragma omp parallel num_threads(3)
  {
    for (i = 0; i < 10000; i++) {
      
         printf("Hello World");
      }

  }
endtime=clock();
timeinterval=(double)(endtime-starttime)/CLOCKS_PER_SEC;
printf("\nTime required for execution=%lf Seconds.\n",timeinterval);

}

Output:

In OPENMP code we have created 3 threads.
To compile the code use the command gcc -fopenmp hello.c

The running time of C code is 0.001640 Seconds and the OPENMP code is 0.008973 Seconds.

Why this happens?

Hello World is printing one by one, one at a time at the standard output screen. So, the second hello world will not be printed until the first one. So there is the dependency so we can not parallelize the code. If we try to parallelize the code by creating the threads it will take more time because the thread has to wait for printing the hello world of the another thread, so there is time laps between this switching because of dependency.

So we have to parallelize the code or algorithm properly and efficiently then we can use the threads and minimise the time complexity.