What is a Data Race? Why Data Races are undesired? How Data Races can be avoided?

Q. What is a Data Race? Why Data Races are undesired? How Data Races can be prevented? (DEC 18, MAY 18, DEC 17) 10M

Q. Write a short note on Data Race. (MAY 19) 10M

Q. What is a Data Race? (MAY 17) 5M

Ans- Data race

A data race is a situation, in which at least two threads access a shared variable at the same time. At least on thread tries to modify the variable.

Races are typically caused by a human error: failure to follow a locking discipline or overall lack of such. Their exposure depends on non-determinism of the thread scheduler, which can interrupt threads at any time and cause their instructions to be interleaved in unpredictable ways. They can cause unpredictable crashes and data corruption. The worst property of data races is that they are notoriously hard to detect, reproduce, locate, and eliminate, which has earned them the name of Heisenbugs.

The only way to avoid data races is to synchronize access to all mutable data that is shared between threads. There are several ways to achieve this. In Go, you would normally use a channel or a lock. (Lower-lever mechanisms are available in the sync and sync/atomic packages.)

The preferred way to handle concurrent data access in Go is to use a channel to pass the actual data from one goroutine to the next. The motto is: “Don’t communicate by sharing memory; share memory by communicating.”

Explain speedup, efficiency and scalability with suitable example.

Q. Explain speedup, efficiency and scalability with suitable example. (MAY 19, MAY 17) 10M

Ans- 1. Speedup

The speedup is defined as the ratio of the serial runtime of the best sequential algorithm for solving a problem to the time taken by the parallel algorithm to solve the same problem on p processors.

Example Adding n numbers on an n processor hypercube

2. Efficiency

The efficiency is defined as the ratio of speedup to the number of processors. Efficiency measures the fraction of time for which a processor is usefully utilized.

Example Efficiency of adding n numbers on an n‐processor hypercube

3. Scalability

Scalability is a measure of a parallel system’s capacity to increase speedup in proportion to the number of processors.

Example Adding n numbers cost‐optimally

Write a MPI program for prime number generation.

Q. Write a MPI program for prime number generation. (DEC 18, DEC 17) 10M

Ans- MPI program for prime number generation

#include "mpi.h"

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define LIMIT     2500000     /* Increase this to find more primes */

#define FIRST     0           /* Rank of first task */

int isprime(int n) {

int i,squareroot;

if (n>10) {

   squareroot = (int) sqrt(n);

   for (i=3; i<=squareroot; i=i+2)

      if ((n%i)==0)

         return 0;

   return 1;

   }

/* Assume first four primes are counted elsewhere. Forget everything else */

else

   return 0;

}

int main (int argc, char *argv[])

{

int   ntasks,               /* total number of tasks in partitiion */

      rank,                 /* task identifier */

      n,                    /* loop variable */

      pc,                   /* prime counter */

      pcsum,                /* number of primes found by all tasks */

      foundone,             /* most recent prime found */

      maxprime,             /* largest prime found */

      mystart,              /* where to start calculating */

      stride;               /* calculate every nth number */

double start_time,end_time;

MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&rank);

MPI_Comm_size(MPI_COMM_WORLD,&ntasks);

if (((ntasks%2) !=0) || ((LIMIT%ntasks) !=0)) {

   printf("Sorry - this exercise requires an even number of tasks.\n");

   printf("evenly divisible into %d.  Try 4 or 8.\n",LIMIT);

   MPI_Finalize();

   exit(0);

   }

start_time = MPI_Wtime();   /* Initialize start time */

mystart = (rank*2)+1;       /* Find my starting point - must be odd number */

stride = ntasks*2;          /* Determine stride, skipping even numbers */

pc=0;                       /* Initialize prime counter */

foundone = 0;               /* Initialize */

/******************** task with rank 0 does this part ********************/

if (rank == FIRST) {

   printf("Using %d tasks to scan %d numbers\n",ntasks,LIMIT);

   pc = 4;                  /* Assume first four primes are counted here */

   for (n=mystart; n<=LIMIT; n=n+stride) {

      if (isprime(n)) {

         pc++;

         foundone = n;

         /***** Optional: print each prime as it is found

         printf("%d\n",foundone);

         *****/

         }

      }

   MPI_Reduce(&pc,&pcsum,1,MPI_INT,MPI_SUM,FIRST,MPI_COMM_WORLD);

   MPI_Reduce(&foundone,&maxprime,1,MPI_INT,MPI_MAX,FIRST,MPI_COMM_WORLD);

   end_time=MPI_Wtime();

   printf("Done. Largest prime is %d Total primes %d\n",maxprime,pcsum);

   printf("Wallclock time elapsed: %.2lf seconds\n",end_time-start_time);

   }

/******************** all other tasks do this part ***********************/

if (rank > FIRST) {

   for (n=mystart; n<=LIMIT; n=n+stride) {

      if (isprime(n)) {

         pc++;

         foundone = n;

         /***** Optional: print each prime as it is found

         printf("%d\n",foundone);

         *****/

         }

      }

   MPI_Reduce(&pc,&pcsum,1,MPI_INT,MPI_SUM,FIRST,MPI_COMM_WORLD);

   MPI_Reduce(&foundone,&maxprime,1,MPI_INT,MPI_MAX,FIRST,MPI_COMM_WORLD);

   }

MPI_Finalize();

}

Write a MPI program to find factorial of given number.

Q. Write a MPI program to find factorial of given number. (MAY 18) 10M

Ans- MPI program to find factorial of a given number

#include <stdio.h>

#include "mpi.h"

int main(int argc, char *argv[]){

    int myRank;

    int size;

    int fact;

    int lower,upper;

    int i;

    double local_result = 1.0;

    double total;

    /* initialize MPI */

    MPI_Init(&argc,&argv);

    /* get my rank and the size of the communicator */

    MPI_Comm_rank(MPI_COMM_WORLD, &myRank);

    MPI_Comm_size(MPI_COMM_WORLD, &size);

    /* get the input. (only if i have rank 0) */

    if(myRank==0){

        printf("Enter a number:");

        scanf("%d",&fact);

    }

    /* since only the process with rank 0 has the input,

     * we must pass it to all the other processes. */

    MPI_Bcast(&fact, /* in/out parameter */

              1,     /* count */

              MPI_INT, /* datatype */

              0,       /* root */

              MPI_COMM_WORLD); /* communicator */

    /* calculate the upper and lower boundaries

     * for each process

     */

    if(myRank==0){

        lower = 1;

    }else

        lower = myRank * (fact / size) + 1;

    if(myRank==(size-1))

        upper = fact;

    else

        upper = (myRank + 1) * (fact / size);

    /* now that we know upper and lower, do the

     * multiplication in our local area

     */

    for(i=lower;i<=upper;i++){

        local_result = local_result * (double)i;

    }

    /* combine all the local results by multiplying them 

     * together

     */

    MPI_Reduce(&local_result, /* operand */

               &total,        /* result */

               1,             /* count */

               MPI_DOUBLE,    /* datatype */

               MPI_PROD,      /* operator */

               0,             /* root rank */

               MPI_COMM_WORLD); /* communicator */

    /* give the output to the user */

    if(myRank==0){

        printf("The factorial of %d is %lf, and was calculated using %d processes\n",fact,total,size);

    }

    /* shut down MPI */

    MPI_Finalize();

    return 0;

}

Write a MPI program to find sum of N numbers.

Q. Write a MPI program to find sum of N numbers. (MAY 19) 10M

Ans-  MPI program to find sum of N numbers

#include <bits/stdc++.h>

#include "mpi.h"

using namespace std;

int main(int argc, char ** argv)

{

int myrank,res,p,dst = 0,tag = 0,ar[100],i;

for(int i=0;i<100;i++)

ar[i] = i;

MPI_Status status;

MPI_Init (&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &myrank);

MPI_Comm_size(MPI_COMM_WORLD, &p);

if(myrank != 0)

{

int interval = 100/(p-1),x,y;

x = interval*(myrank-1);

y = interval*(myrank)-1;

res = 0;

for(i=x;i<=y;i++)

res+=ar[i];

// cout<<"sum "<<res <<"\n";

MPI_Send(&res, sizeof(res), MPI_INT, 0, 0, MPI_COMM_WORLD);

}

else

{

int sum = 0;

for(int src= 1; src< p; src++)

{

MPI_Recv(&res, sizeof(res), MPI_INT, src, 0, MPI_COMM_WORLD, &status);

printf("sum recieved from the process: %d is %d\n",src, res);

sum = sum + res;

}

printf("the total sum is %d\n",sum);

}

 

MPI_Finalize();

}

Explain in brief Quantum Computers.

Q. Explain in brief Quantum Computers. (MAY 19, DEC 18, DEC 17) 10M

Q. Write a short note on Quantum Computers. (MAY 18) 5M

Ans- A quantum computer is a type of computer that uses quantum mechanics so that it can perform certain kinds of computation more efficiently than a regular computer can. A quantum computer does not use bits to store information. Instead, it uses something called qubits.

What is a qubit? 

Today's computers use bits—a stream of electrical or optical pulses representing 1s or 0s. Everything from your tweets and e-mails to your iTunes songs and YouTube videos are essentially long strings of these binary digits.

Quantum computers, on the other hand, use qubits, which are typically subatomic particles such as electrons or photons. Generating and managing qubits is a scientific and engineering challenge. Some companies, such as IBM, Google, and Rigetti Computing, use superconducting circuits cooled to temperatures colder than deep space. Others, like IonQ, trap individual atoms in electromagnetic fields on a silicon chip in ultra-high-vacuum chambers. In both cases, the goal is to isolate the qubits in a controlled quantum state.

Qubits have some quirky quantum properties that mean a connected group of them can provide way more processing power than the same number of binary bits. One of those properties is known as superposition and another is called entanglement. 

What is superposition? 

Qubits can represent numerous possible combinations of 1 and 0 at the same time. This ability to simultaneously be in multiple states is called superposition. To put qubits into superposition, researchers manipulate them using precision lasers or microwave beams.

Thanks to this counterintuitive phenomenon, a quantum computer with several qubits in superposition can crunch through a vast number of potential outcomes simultaneously. The final result of a calculation emerges only once the qubits are measured, which immediately causes their quantum state to “collapse” to either 1 or 0. 

What is entanglement? 

Researchers can generate pairs of qubits that are “entangled,” which means the two members of a pair exist in a single quantum state. Changing the state of one of the qubits will instantaneously change the state of the other one in a predictable way. This happens even if they are separated by very long distances.

Nobody really knows quite how or why entanglement works. It even baffled Einstein, who famously described it as “spooky action at a distance.” But it’s key to the power of quantum computers. In a conventional computer, doubling the number of bits doubles its processing power. But thanks to entanglement, adding extra qubits to a quantum machine produces an exponential increase in its number-crunching ability.

Quantum computers harness entangled qubits in a kind of quantum daisy chain to work their magic. The machines’ ability to speed up calculations using specially designed quantum algorithms is why there’s so much buzz about their potential.

That’s the good news. The bad news is that quantum machines are way more error-prone than classical computers because of decoherence. 

What is decoherence? 

The interaction of qubits with their environment in ways that cause their quantum behavior to decay and ultimately disappear is called decoherence. Their quantum state is extremely fragile. The slightest vibration or change in temperature—disturbances known as “noise” in quantum-speak—can cause them to tumble out of superposition before their job has been properly done. That’s why researchers do their best to protect qubits from the outside world in those supercooled fridges and vacuum chambers.

But despite their efforts, noise still causes lots of errors to creep into calculations. Smart quantum algorithms can compensate for some of these, and adding more qubits also helps. However, it will likely take thousands of standard qubits to create a single, highly reliable one, known as a “logical” qubit. This will sap a lot of a quantum computer’s computational capacity.

And there’s the rub: so far, researchers haven’t been able to generate more than 128 standard qubits (see our qubit counter here). So we’re still many years away from getting quantum computers that will be broadly useful.

That hasn’t dented pioneers’ hopes of being the first to demonstrate “quantum supremacy.”

What is quantum supremacy?

It’s the point at which a quantum computer can complete a mathematical calculation that is demonstrably beyond the reach of even the most powerful supercomputer.

It’s still unclear exactly how many qubits will be needed to achieve this because researchers keep finding new algorithms to boost the performance of classical machines, and supercomputing hardware keeps getting better. But researchers and companies are working hard to claim the title, running tests against some of the world’s most powerful supercomputers.

There’s plenty of debate in the research world about just how significant achieving this milestone will be. Rather than wait for supremacy to be declared, companies are already starting to experiment with quantum computers made by companies like IBM, Rigetti, and D-Wave, a Canadian firm. Chinese firms like Alibaba are also offering access to quantum machines. Some businesses are buying quantum computers, while others are using ones made available through cloud computing services.

Define MPI. Explain in detail principles of Message Passing Programming.

Q. Define MPI. Explain in detail principles of Message Passing Programming. (MAY 19) 10M

Q. What are the principles of Message Passing Programming. (DEC 18, MAY 17) 10M

Q.What is Message Passing Interface? What are the principles of Message Passing Programming. (DEC 17) 10M

Ans- Message Passing Interface 

Message Passing Interface (MPI) is a standardized and portable message-passing standard designed by a group of researchers from academia and industry to function on a wide variety of parallel computing architectures.

Principles of Message Passing Programming

• There are two key attributes that characterize the message-passing programming paradigm.

1. the first is that it assumes a partitioned address space
2. the second is that it supports only explicit parallelization.

• There are two immediate implications of a partitioned address space.

1. First, each data element must belong to one of the partitions of the space; hence, data must be explicitly partitioned and placed. This adds complexity to programming, but encourages locality of access that is critical for achieving high performance on non-UMA architecture, since a processor can access its local data much faster than non-local data on such architectures.
2. The second implication is that all interactions (read-only or read/write) require cooperation of two processes (the process that has the data and the process that wants to access the data). This requirement for cooperation adds a great deal of complexity for a number of reasons.

• The process that has the data must participate in the interaction even if it has no logical connection to the events at the requesting process. In certain circumstances, this requirement leads to unnatural programs. In particular, for dynamic and/or unstructured interactions the complexity of the code written for this type of paradigm can be very high for this reason.
• However, a primary advantage of explicit two-way interactions is that the programmer is fully aware of all the costs of non-local interactions, and is more likely to think about algorithms (and mappings) that minimize interactions.
• Another major advantage of this type of programming paradigm is that it can be efficiently implemented on a wide variety of architectures.
• The programmer is responsible for analyzing the underlying serial algorithm/application and identifying ways by which he or she can decompose the computations and extract concurrency.
• As a result, programming using the message-passing paradigm tends to be hard and intellectually demanding. However, on the other hand, properly written message-passing programs can often achieve very high performance and scale to a very large number of processes.

Discuss in detail SISD, SIMD, MISD, MIMD, SIMT, SPMD, MPMD.

Q. Discuss in detail SISD, SIMD, MISD, MIMD, SIMT, SPMD, MPMD. (MAY 19) 10M

Q. Explain SIMD, MIMD, SIMT. (DEC 18) 10M

Ans- 1. Single-instruction, single-data (SISD) –

A SISD computing system is a uniprocessor machine which is capable of executing a single instruction, operating on a single data stream. In SISD, machine instructions are processed in a sequential manner and computers adopting this model are popularly called sequential computers. Most conventional computers have SISD architecture. All the instructions and data to be processed have to be stored in primary memory. The speed of the processing element in the SISD model is limited(dependent) by the rate at which the computer can transfer information internally. Dominant representative SISD systems are IBM PC, workstations.

2. Single-instruction, multiple-data (SIMD) –

A SIMD system is a multiprocessor machine capable of executing the same instruction on all the CPUs but operating on different data streams. Machines based on a SIMD model are well suited to scientific computing since they involve lots of vector and matrix operations. So that the information can be passed to all the processing elements (PEs) organized data elements of vectors can be divided into multiple sets (N-sets for N PE systems) and each PE can process one data set. Dominant representative SIMD systems is Cray’s vector processing machine.

3. Multiple-instruction, single-data (MISD) –

A MISD computing system is a multiprocessor machine capable of executing different instructions on different PEs but all of them operating on the same dataset.

Example Z = sin(x)+cos(x)+tan(x)

The system performs different operations on the same data set. Machines built using the MISD model are not useful in most of the application, a few machines are built, but none of them are available commercially.

4. Multiple-instruction, multiple-data (MIMD) –

A MIMD system is a multiprocessor machine which is capable of executing multiple instructions on multiple data sets. Each PE in the MIMD model has separate instruction and data streams; therefore, machines built using this model are capable to any kind of application. Unlike SIMD and MISD machines, PEs in MIMD machines work asynchronously. MIMD machines are broadly categorized into shared-memory MIMD and distributed-memory MIMD based on the way PEs are coupled to the main memory.

5. Single-instruction, multiple-data (SIMD) –

A SIMT is an execution model used in parallel computing where single-instruction, multiple data is combined with multithreading. The processors, say a number p of them, seem to execute many more than p tasks. This is achieved by each processor having multiple threads, which execute in lock-step, and are analogous to SIMD lanes. The SIMT execution model has been implemented on several GPUs and is relevant for general-purpose computing on graphics processing units (GPGPU), e.g. some supercomputers combine CPUs with GPUs. SIMT was introduced by Nvidia.

6. Single-program, multiple-data (SIMD) –

SPMD is actually a “high level” programming model that can be built upon any combination of the previously mentioned parallel programming models. A single program is executed by all tasks simultaneously. At any moment of time, tasks can be executing the same or different instructions within the same program. SPMD programs usually have the necessary logic programmed into them to allow different tasks to branch or conditionally execute only those parts of the program they are designed to execute. That is, tasks do not necessarily have to execute the entire program – perhaps only a portion of it. All tasks may use different data.

7. Multiple-program, multiple-data (SIMD) –

Like SPMD, MPMD is actually a “high level” programming model that can be built upon any combination of the previously mentioned parallel programming models. MPMD applications typically have multiple executable object files (programs). While the application is being run in parallel, each task can be executing the same or different program as other tasks. All tasks may use different data.