Assignment THREAD BASED IMPLEMENTATION

Short answer type questions:-

Ques. 1:
In case of User-Level Thread implementation the schedulable entity is:
a) Program
b) Process
c) Thread
d) (b) & (c) both
Answer:
(b)
(Because kernel is not aware of the threading activity being carried out within the program.)


Ques. 2:
User-Level Threads (ULTs) are implemented by means of ______________ & Kernel-Level Threads are implemented through ____________________.
Answer:
Thread Libraries & System calls


Ques. 3:
Which thread implementation should be preferred in case of a server that spawns a new thread for each incoming request (say for 2000-3000 threads) & why?
User-Level Threads/ Fibers
Kernel-Level Threads/ Threads
Sequential Process Approach
Combined ULT + KLT implementation
Answer:
(a)
(Context switching that includes a blocking system call will be too expensive so in such cases Fibers can be helpful)


Ques. 4:
Mention one such operating system that implements the combined ULT + KLT approach to threading?
Answer:
SOLARIS Operating System


Ques. 5:
The routine used to wake up any threads waiting on a given Condition Variable is:
Event-Clear
Event-Post
Event-Signal
Event-Init
Answer:
(b)


Ques. 6:
To ensure that a post does not happen after the condition checking and before the execution of wait call, _____________________ is made use of.
Answer:
Mutex Variable


Ques. 7:
Name an API for multi-threaded programming standardized by IEEE as part of the POSIX standards?
Answer:
Pthread Library defined under standard POSIX 1003.1c.


Ques. 8:
In JAVA the concept of threads is implemented through:
Integrated in language itself
External APIs & Libraries
Operating System
No multithreaded support in JAVA
Answer:
(b)
(JAVA provides in-built support for multithreading through “java.lang” package & “java.lang.Thread” class)



Ques. 9:
The only method that makes up the entire body of the thread and in which the thread behaviour can be implemented is_____________.
Answer:
The run( ) method.


Ques. 10:
What should be done to prevent a method from causing a RACE CONDITION in a program:
Create only one thread at a time
Precede call to that method with ‘synchronized’ keyword
Precede the method definition with ‘synchronized’ keyword
Synchronization primitives not supported by Java, so can’t be prevented
Answer:
C)
(To make an object enter its lock that is implicitly associated with every object we make use ‘synchronized’ keyword with the method that is likely to result into Race Condition.)


Ques. 11:
List down two basic functions performed by the function pthread_cond_wait (cond, mutex).
Answer:
Put thread in queue of waiting threads
Release the aquired lock


Ques. 12:
Consider the following code segment:
public static void main(String a[])
{
mythread th1=new mythread();
mythread th2=new mythread();
th1.start();
th1.suspend();
th2.start();
System.out.println(" Thread ONE is alive True/False: " +th1.isAlive());
System.out.println(" Thread TWO is alive True/False: " +th2.isAlive());
th1.resume();
try
{
th1.join();
th2.join();
}catch(InterruptedException ie)
{
System.out.println("Exception in threads!!!!");
}
System.out.println(" FINISHED !”);
}
}
What is the purpose of join() call in above code?
Answer:
This will wait for both of the threads to finish (complete execution) and to join it and only after that outputs FINISHED.


Ques. 13:
The join() function in java is equivalent to (serves the purpose of) _________________ primitive in Process Model.
Answer:
barrier() primitive.


Ques. 14:
After making a call to suspend() method on an executing thread, what will the isAlive() method return for the same thread?
True
False
Answer:
a)
(Because the thread is just suspended temporarily, to be resumed later it has not yet completed its execution.)


Ques. 15:
What are the methods available in Java to serve the functionality of Condition Variables?
Answer:
wait() and notify()



Long answer type questions:-

Ques. 1:
Describe different ways of implementing threads, with their merits and demerits. Also mention which method is preferred in which situation?
Answer:
There are two broad categories of thread implementation:
User-Level Threads/ Fibers/ LWPs -- Thread Libraries.
ii) Kernel-level Threads/ Threads -- System Calls.

1. USER-LEVEL THREADS (ULT):
This implementation implements threads as a user-level entity that is unknown to the Operating System. In this level, the kernel is not aware of the existence of threads -- All thread management is done by the application by using a thread library.
Thread switching does not require kernel mode privileges (no mode switch)
Scheduling is application specific
Kernel activity for ULTs: The kernel is not aware of thread activity but it is still managing process activity
Thread/process states: When a thread makes a system call, the whole process will be blocked but for the thread library but that thread is still in the running state. So thread states are independent of process states
Threads are actually handled by a Thread Management Module of the process, which assigns the CPU to one of the available process. When the OS timer interrupts, the control is taken by OS to allot the CPU to another process.

Advantages:
à Thread switching does not involve the kernel -- no mode switching
à Scheduling can be application specific -- choose the best algorithm.
à ULTs can run on any OS -- Only needs a thread library

Disadvantages:
à Most system calls are blocking and the kernel blocks processes -- So all threads within the process will be blocked
à The kernel can only assign processes to processors -- Two threads within the same process cannot run simultaneously on two processors

2. KERNEL-LEVEL THREADS (KLT):
In this level, All thread management is done by kernel. No thread library but an API (system calls) to the kernel thread facility exists. The kernel maintains context information for the process and the threads both, Switching between threads require the kernel.
Scheduling is performed on a thread basis.

Advantages:
à The kernel can simultaneously schedule many threads of the same process on many processors.
à Blocking due to the system calls is also done on a thread level.

Disadvantages:
à Thread switching within the same process involves the kernel, e.g if we have two threads per process and switching between these threads is required quite often after short intervals then kernel has to participate in this switching resulting in a significant slow down of the whole system.

3. COMBINED ULT/KLT APPROACHES:
Sometimes a combined approach for both of the implementations is followed. Solaris is an example of an OS that combines both ULT and KLT.
Under User Space:
à Thread creation.
à Bulk of scheduling and synchronization of threads.
The programmer may adjust the number of KLTs
Process includes the user's address space, stack, and process control block
User-level threads (threads library) invisible to the OS are the interface for application parallelism
Kernel threads the unit that can be dispatched on a processor
Lightweight processes (LWP) each LWP supports one or more ULTs and maps to exactly one KLT .

Suitability:-
Consider the following pseudo code:
main()
{
status=0;
pthread_create(….,proc1,….);
while(status!=0)
…….
}
proc1()
{
…..
v1=1;
…..
}
à The newly created thread is expected to change the value of v1, which the parent thread is waiting for. But in some implementations this may lead the system to hang. If the system follows ULT implementation, then the main thread is apparently doing some serious work and does not yield control to the new thread. Therefore the second thread never gets a chance to run, in order to change the value of v1, which is what main is waiting for. If system followed KLT instead then the problem outlined above cannot occur.
à A case where fibers/ULTs still can be helpful is when the limits of the OS in terms of number of threads per process are reached (for example 2000-3000 threads). In this case context-switching, which includes a system call, is too expensive and fibers can help.
This situation may happen, for example, in a server that spawns a new thread for each incoming request.
•

Ques. 2:
What primitives are available in POSIX Pthread Library for implementing Condition Variables? Explain with an example.
Answer:
Sometimes, there is a need to detect the occurrence of certain events and behave accordingly.
For example: We may want thread T1 to execute certain steps only after some other computation is over by other thread T2. So, T1 is supposed to wait for T2 until it finishes.
For such situations, Pthread library uses the notion of Condition Variables.
A condition variable has two parts:
1. Condition
2. Semaphore
The condition variable mechanism allows threads to suspend execution and relinquish the processor until some condition is true. A condition variable must always be associated with a mutex to avoid a race condition created by one thread preparing to wait and another thread which may signal the condition before the first thread actually waits on it resulting in a deadlock. The thread will be perpetually waiting for a signal that is never sent. Any mutex can be used, there is no explicit link between the mutex and the condition variable.

A condition variable supports four basic operations:
Event-init: It is for initialization of condition variables
ii) Event-wait: It is called when a thread has to wait for the condition to be true.
iii) Event-clear: Used to flag the condition as true.
Event-Post: Used to flag the condition as false. It should also wake up any threads waiting on the variable by calling event-wait.

PRIMITIVES AVAILABLE FOR USING CONDITION VARIABLES ARE:

pthread_cond_init (cond, NULL)
To initialize the condition variable.
cond is a variable of type pthread_cond_t.

pthread_cond_wait (cond, mutex)
Called when a thread has to wait for a condition to become true.
The thread should check for the condition required and only if it is false executes this. Once it is false the event-post routine wakes up all the threads waiting on the variable/condition.
In order to ensure that post does not happen after the condition checking and before the execution of this wait call, a mutex variable is made use of. All operations on condition variable should be done only under this mutex lock.

Posting an event
pthread_cond_broadcast(cond)
Wakes up all threads waiting on the given condition variable.

pthread_cond_signal(cond)
If there are more than one thread waiting then a random one is chosen and woken-up.Else only the thread associated with the condition is woken.

EXAMPLE: The program given below describes the use of condition variables as well as mutex variables.
main()
{
pthread_t thread1, thread2;
int count=0;
pthread_create( &thread1, NULL, &functionCount1, NULL);
pthread_create( &thread2, NULL, &functionCount2, NULL);
exit(0);
}
void *functionCount1()
{
for(;;)
{
pthread_mutex_lock( &condition_mutex );
while( count >= 3 && count <= 6 )
{
pthread_cond_wait( &condition_cond, &condition_mutex );
}
pthread_mutex_unlock( &condition_mutex );

pthread_mutex_lock( &count_mutex );
count++;
printf("Counter value functionCount1: %d\n",count);
pthread_mutex_unlock( &count_mutex );
if(count >= 10) return(NULL);
}
}
void *functionCount2()
{
for(;;)
{
pthread_mutex_lock( &condition_mutex );
if( count <> 6 )
{
pthread_cond_signal( &condition_cond );
}
pthread_mutex_unlock( &condition_mutex );
pthread_mutex_lock( &count_mutex );
count++;
printf("Counter value functionCount2: %d\n",count);
pthread_mutex_unlock( &count_mutex );
if(count >= 10) return(NULL);
}
}

Output: Compile: cc -lpthread cond1.c
Run: ./a.out
Results:
Counter value functionCount1: 1
Counter value functionCount1: 2
Counter value functionCount1: 3
Counter value functionCount2: 4
Counter value functionCount2: 5
Counter value functionCount2: 6
Counter value functionCount2: 7
Counter value functionCount1: 8
Counter value functionCount1: 9
Counter value functionCount1: 10
Counter value functionCount2: 11



Ques. 3:
Write down the steps for creating threads in JAVA?
OR
What are the alternative methods of creating threads in JAVA? Explain.
Answer:
A unique property of Java is its support for multithreading. That is, java enables us to use multiple flows of control in developing programs.
Each flow of control may be thought of as a separate tiny program (or module) known as a thread that runs in parallel to others. A program that contains multiple flows of control is known as multithreaded program.
A new thread can be created in two ways:
By creating a thread class
By converting a class to a thread
The approach to be used depends on what the class that we are creating requires. If it requires to extend another class, then we have to implement the Runnable interface (as Java does not support more than one superclasses so multiple inheritance is achieved through interfaces in Java).


I) METHOD #1: EXTENDING THE THREAD CLASS
For both the methods we need to extend the class java.lang.Thread which gives us access to all the thread methods directly. The steps involved are:

Step 1: Declare the class as extending the Thread class.

class MyThread extends Thread
{ - - - - - - - - -
- - - - - - - - -
}
This creates a new thread of type ‘MyThread’

Step 2: Implement the run ( ) method that is responsible for executing the sequence of code that the thread will execute.
The run ( ) method has been inherited by the class MyThread. We need to override this method in order to implement the code to be executed by our thread. When we start the new thread, Java calls the thread’s run ( ) method, so it is the run ( ) where all the action takes place.

public void run( )
{
- - - - - - - - - - -
- - - - - - - - - (Statements for implementing thread)
- - - - - - - - - - -
}

Step 3: Create a thread object and call the start ( ) method to initiate the thread execution. To actually create and run the instance of our thread class we must write the following:

MyThread th1 = new MyThread ( );
// This will put the thread th1 in a newborn state.
th1.start( );
// Thread th1 is now put into Runnable state


à Now the Java runtime will schedule the thread to run by invoking its run ( ) method implicitly. Now, the thread is said to be in the running state.
à The start ( ) method returns back to the main thread immediately after invoking the run ( ) method, thus allowing the main thread to start some another thread.

II) METHOD #2: IMPLEMENTING THE ‘Runnable’ INTERFACE
To create threads in those situations where the class needs to have more than one super classes we must use the practice of implementing the ‘Runnable’ interface. It involves the following steps:

Step 1: Declare the class as implementing the Runnable interface.
class mythread implements Runnable
{
…………
…………
}

Step 2: Implement the run ( ) method. It is important to understand that run ( ) can call other methods, use other classes, and declare variables just like the main thread can.

Step 3: After creating the class, next we will instantiate an object of type Thread from within that ‘runnable’ class as the target of the thread. For this very purpose the Thread class defines several constructors. One such simple constructor that can be used is:

Thread(Runnable threadOb, String threadname);


Object of the class Name given to the
that implemented new thread(optional)
Runnable interface

Thread th = mythread ( this, “demo Thread”);

Step 4: Call the thread’s start ( ) method that executes a call to the run ( ) method to run the thread.
th.start ( );











Ques. 4:
What is meant by mutual exclusion? What are the primitives available in JAVA and Pthread library for synchronizing access to shared variables and resources?
Answer:
One of the major issues in thread programming is controlling access to shared resources. Mutual exclusion is used to prevent data inconsistencies due to race conditions. A race condition often occurs when two or more threads need to perform operations on the same memory area, but the results of computations depends on the order in which these operations are performed.
Mutual exclusion primitives are used for serializing shared resources. Anytime a global resource is accessed by more than one thread the resource should have some kind of lock associated with it. One can apply a lock to protect a segment of memory ("critical region") from other threads.

Mutual Exclusion In JAVA:
Locking management is well integrated into JAVA language. Conceptually, we can view Java’s synchronization system as associating a lock with every object created. In other words, methods can be declared as ‘synchronized’.
With every object an implicit monitor is associated with. To make an object enter its monitor that is implicitly associated with every object we make use ‘synchronized’ keyword with the method that is likely to result into Race Condition.
(Race Condition is the condition where nothing exists to stop all the threads in the program from calling the same method, on the same object, at the same time.)
All other threads even ‘synchronized threads’ can’t enter or call that thread. To exit monitor and relinquish control of object, owner of monitor simply returns from synchronized method.
Example:
The concept explained above can better be depicted through an example code:

class Callme
{
void call(String msg)
{
System.out.print("[ " +msg);
System.out.println(" ]");
}
}
class caller implements Runnable
{
String msg;
Callme cme;
Thread t;
public caller(Callme c, String s)
{
cme=c;
msg=s;
t = new Thread(this);
/* Create a new thread. 'this' refers to the object of the class that implemented the RUNNABLE interface. In this case it can be any of th1, th2, th3 or th4.
*/
t.start();
}
public void run()
{
cme.call(msg);
} }
class mutual
{
public static void main(String a[])
{
Callme cme1 = new Callme();
caller th1 = new caller ( cme1, "Example");
caller th2 = new caller ( cme1, "Of");
caller th3 = new caller ( cme1, "Mutual");
caller th4 = new caller ( cme1, "Exclusion");
}
}

Output:
[Example][of Mutual]Exclusion][
or
[Example[[of Mutual [Exclusion]]]]
or
Any sort of distorted or overlapped output.

The problem with the above program is that all of the four threads are calling the same method call() at same time, so that’s why we are not able to get the desired output. There is a need to synchronize access to this method which can be simply done as follows:
synchronized void call(String msg)
Now, the desired output will be:
[Example]
[of]
[Mutual]
[Exclusion]



Mutual Exclusion In POSIX:
The threads library provides three synchronization mechanisms:
mutexes - Mutual exclusion lock: Block access to variables by other threads. This enforces exclusive access by a thread to a variable or set of variables.
joins - Make a thread wait till others are complete (terminated).
condition variables - data type pthread_cond_t.

Example:
One such example code that depicts the use of both mutex variables and joins that can be implemented in a program to achieve mutual exclusion features is as follows:

int counter = 0;
main()
{
int rc1, rc2;
pthread_t thread1, thread2;
/* Create independent threads each of which will execute functionC */
if( (rc1=pthread_create( &thread1, NULL, &functionC, NULL)) )
{
printf("Thread creation failed: %d\n", rc1);
}
if( (rc2=pthread_create( &thread2, NULL, &functionC, NULL)) )
{
printf("Thread creation failed: %d\n", rc2);
}
/* Wait till threads are complete before main continues. */
pthread_join( thread1, NULL);
pthread_join( thread2, NULL);
}
void *functionC()
{
pthread_mutex_lock( &mutex1 );
counter++;
printf("Counter value: %d\n",counter);
pthread_mutex_unlock( &mutex1 );
}

OUTPUT:
Compile: cc -lpthread mutex1.c
Run: ./a.out
Results:
Counter value: 1
Counter value: 2

Content Credit: Prabhjot Kaur

Read full story

ASSIGNMENT APPLICATIONS OF PARALLEL COMPUTING

APPLICATIONS OF PARALLEL COMPUTING IN PHYSICS, CHEMISTRY, MATHEMATICS & COMPUTER SCIENCE

OBJECTIVE QUESTIONS

1) Which among the following is done by solving partial differential equations:
A. Visualization
B. Animation
C. Data mining
D. Weather forecasting

Which of the following application requires very high computing speed:
E. Weather forecasting
F. Visualization and animation
G. Predicting the motion of astronical bodies
H. All the above

In an N-body problem, if there are n-bodies then forces required to calculate for each body will be:
A. N
B. N-1
C. N+1
D. N*N

In order to calculate molecular properties lots of calculations are required, to reduce there time the program used in chemistry field is:
Artificial intelligence
Animations
GAMESS
None of the above

Which among these is a program which draw a contour plot of total electron density of a molecule:
A. Molplt
B. Dendif
C. Animation
D. Visualization

Which of the below is included in source code distribution of GAMESS:
A. Animation
B. Data mining
C. Dendif
D. None of the above

Molplt is a program that
A. Draw ball and stick molecular figures
B. Included in source code of GAMESS
C. Analyze data in large databases
D. None of the above


The problem complexity of data mining can be expressed by PC=
A. S*P*N
B. S*N
C. P*P
D. S*P

in which among the following the result of the computations are to be realistically rendered on high resolution terminal:
A. Visualization and animation
B. Data mining
C. GAMESS
D. Weather forecasting

Applications where parallel programming is used in computer science are:
A. Sorting algorithms
B. Numerical algorithms
C. Image processing applications
D. All the above

The fast fourier transfer algorithm used in:
A. Image enhancement
B. Image restoration
C. Image compression
D. All the above

In Visualization and animation time needed to process a pixel is:
1/(60*G*R)
1/(30*G*R)
1/(G*R)
None of the above


ANSWERS
D
D
B
C
B
C
A
A
9. A
10. D
11. D
12. A

LONG QUESTIONS

1) EXPLAIN ONE OF THE PROGRAM THAT IS USED BY THE RESEARCHERS TO REDUCE CALCULATION TIME IN CHEMISTRY
ANS:
Computational chemists solve problems on quantum mechanics, polymer chemistry and crystal by using super computers. In order to calculate the molecular properties are
Electronic wave function
Bond distance and bond functions
Electronic energy and nuclear repulsions etc

A lot of calculations are required; in order to reduce this calculation time the program that is used by researchers in chemistry field is GAMESS.

GAMESS:::: GAMESS is a general quantum chemistry package. Gamess is a program that can compute SCP wave functions ranging from simple dipole moments to frequency dependent hyperpolarizabilites may be computed. Several graphics programs are available for viewing of the final results. Some of them with their o/p are;
1) DENDIF::::::: this program will draw a contour plot of the total electron density of a molecule. It is included in source code distribution of games.
2) MOLPLT::::::: this program draws ball and stick molecular figures automatically centering the molecule, once drawn on a X terminal almost everything about the picture can be changed interactively. The change includes rotation of the molecule code, size, and rescaling of normal mode.

2) EXPLAIN SOME OF THE APPLICATIONS OF PARALLEL COMPUTING THAT HAS VERY HIGH COMPUTING SPEED?
ANS:
There are many applications that use very high computing speed. Some of them are discussed below
WEATHER FORECASTING:
Weather forecasting is a widely quoted example of that requires very powerful computing. The objective of numerical weather modeling is to predict the status of the atmosphere at a particular region at a specified future time based on the current and past observations of the values of the atmosphere. It is done by solving the partial differential equation.

DATA MINING:
A technique used by the organization to analyze data in large databases to discover some pattern or rules. In general, the idea is to hypothesize a rule relating data elements and test it by retrieving these data elements from archieve.the problem complexity (PC) of this may be expressed by the formula:
PC=s*p*n where s-> size of databases, p-> no. Of instances to executed to check a rule, n->no of rules to be checked.

GAMESS::::
GAMESS is a general quantum chemistry package. Gamess is a program that can compute SCP wave functions ranging from simple dipole moments to frequency dependent hyperpolarizabilites may be computed. Several graphics programs are available for viewing of the final results. Some of them with their o/p are;
DENDIF::::::: this program will draw a contour plot of the total electron density of a molecule. It is included in source code distribution of games.

MOLPLT::::::: this program draws ball and stick molecular figures automatically centering the molecule, once drawn on a X terminal almost everything about the picture can be changed interactively. The change includes rotation of the molecule code, size, and rescaling of normal mode.
VISUALIZATION AND ANIMATION:

In visualization and animation the results of computation are to be realistically rendered on a high-resolution terminal. In this case the no. Of area elements where the picture to be rendered is represented by G.The no. Of picture elements to be processed in each area element is represented by R and time to process a pixel by T. the computation should be repeated at least 60 times a second for animation. Thus GR pixels should be processed in 1/60 sec.time to process a pixel= 1/(60*G*R). For G=10*10*10*10*10 and R=10*10*10*10.a pixel should be processed within few seconds. Computation complexity in this case is G*R*P*N, where P -> no of repetitions/sec


3) EXPLAIN APPLICATIONS OF PARALLEL PROGRAMIING IN COMPUTER SCIENCE??

ANS:

There are many applications in computer science where parallel programming is used. Some of them are discussed below
MATRIX MULTIPICATION:

The product of an L*M matrix A and an M*N matrix B is an L*N matrix C whose elements are defined by
C ij = A ik B kJ
A sequential algorithm implements matrix multiplication as follows:
For (I=0;I<1;I++)
{
For (j=0;j
{
C [I][j]=0.0;
For (k=0;k
C [I][j] +=a [I][k]+b [k][j];
}
}
PARALLEL QUICK SORT

Quick sort is a divide and conquer algorithm that easily yields itself to parallelisation.the following steps describe the algorithm to sort data in ascending order:
The array is portioned into two parts using a pivot element, such that all elements in the left partition are smaller than the pivot element and the elements to the right are larger.
The pivot element is inserted in between the two partitions and hence in the sorted position after partitioning.
Step 1 is applied recursively on each partition if the size of the partition is larger than one element.
To parallelise this algo, we first create a set of processes. The extents of the array to be sorted are placed on a stack to indicate the presence of the work to be done. The first process to fetch the work partitions the array and places the extents of the resulting two partitions on the stack and as per the above algorithm create new partitions. These are added to the stack.

PARALLEL TREE-SORT ALGORITHMS

Here a binary tree data structure with (2n-1) nodes is used to sort n numbers. The tree has n leaves and initially one number is stored in each leaf. Sorting is done by selecting the minimum of n numbers then the minimum of the remaining (n-1) numbers and so on
The binary tress is used to find the minimum by iteratively comparing the numbers in the two sibling nodes and moving the smaller number to the parent node. The algo can be parallelised by considering a set of (2n-1) processors interconnected to form a binary tree. By starting with one number at each leaf processor, the minimum can be transferred to the root of the trees in log n steps. At each step, a parent receives a minimum of its child nodes, if any. Once the first element is extracted the subsequent list can be removed in (n-1) steps. Thus the sorting is completed in log n+n steps or O (n) time.

ODD-EVEN TRANSPOSITION SORT::

The serial odd-even transposition sort is a variation of the basic bubble sort, with a total of n phases, each of which requires n/2 comparisions.odd and even phases alternate. During the odd phase, the odd numbered elements are compared with their right adjacent neighbours.during the even phase the even numbered phase, the even numbers are compared with their right adjacent neighbours.to totally sort the sequence a total of n phases are required.
The algorithm can be trivially parallelised since the comparisons within the phase are independent. Consider n linearly connected processors and label them p1, p2, p3, ------, pn. Assume that the links are bi-directional that pi can communicate with pi-1 and pi+1.also assume that initially Xi resides in pi for I=1,2,3, ------n. To sort the elements in parallel, let p1, p3, p5 be active during the odd time and execute in the odd phase of the serial odd even transposition sort in parallel. An analogous step is done in parallel on the even numbered processors with the even phase.
Note that a single comparison exchange requires two transfers. Thus, the parallel odd-even transposition algorithm sort n numbers with n processors in n parallel comparisons and 2n transfers.

Content Credit: Reema Pahuja

Read full story

ASSIGNMENT DATA DEPENDENCY ANALYSIS

Subjective Questions

Q1. Explain data dependency analysis and its primary sources.
Ans. Some programs code segments cannot be run in parallel due to dependency where the results of execution of some part of the code affects the execution of some other part. For example, the average of a set of numbers is required for the computation of the standard deviation of the set. Data dependency analysis deals with the study of the nature of such dependencies.
Automatic detection of parallism in the existence code requires the need for compilers that can identify what can be done in parallel and what cannot be. This is not an easy task. There are a numbers of factors affecting this task, including the choice of language used.
Some are hard dependencies which cannot be circumvented at all. For example, if a routine outputs the contents of an array in order, it has to be executed sequentially. Without destroying the order, it is difficult to envisage a parallelization. In some other cases, the code may appear to require a sequential order, but suitable remodeling can convert the code to run in parallel. In the best case, find the code segments that are independent and hence can be directly scheduled for running in parallel.

Primary sources of dependencies:
Dependency among program segments arises from primarily three sources:
Control dependence.
Resource dependence.
Data dependence.
Control dependence:
This is imposed by the language construct like if then, case, etc. though the code segment corresponding to different branches are independent, there is no use of executing them I parallel because only one of the results should be visible , which depends on the conditions being tested.
Resource Dependence:
The need to share resources among instructions causes resource dependency. E.g. if 2 instructions require the use of a floating point processor and only one such floating point unit is available in CPU, then these 2 instructions can not be executed in parallel.
Data dependence:
It is the most important source of dependency. It arises when 2 segments of code accesses or updates the common piece of data. E.g. consider 2 statements:
A=A+1;
B=A+1;
Let initial value be A=0, B=0
Result of sequential execution will be A=1, B=2
Result of parallel execution would depend on the order in which statements would be executed & therefore, will be different every time. This is because statement 2 is referring to a variable being used by statement 1.


Q2. Explain various types of dependencies.
Ans : DEF & USE set of statements are used to identify the type of dependency that exists in a given code of segment.
DEF: It is a set of variables modified by the statement.
USE: It is a set of variables accessed/used by the statement.
Example: let there be a statement, A=5.2
By definition, DEF(A)={A}
& USE (A)={ } (as no variable is used by statement)
let another statement be: A=B+C-2.4
By definition, DEF(A)={A}
& USE(A)={B,C}
DEF and USE are used to formalized the notion of dependence.

Types of dependence:

1. TRUE/FLOW DEPENDENCE: it arises when
DEF (S1) intersection USE (S2)! = { }
· It is the most common & most difficult to avoid.
· It arises because a value computed by S1 is used in S2 for some processing.
· When a program is solved in a sequence of steps then intermediate or partial results are computed for further use.
Example: Let S1: A=B+C
S2: D=2*A
DEF (S1) = {A}
USE (S2) = {A}
According to definition,
DEF (S1) intersection USE (S2) = {A}
Therefore, Flow dependence arises in these statements.
2. ANTI-DEPENDENCE: It arises when
DEF (S2) intersection USE (S1)! = { }
· It is opposite of flow dependence.
· It arises when we reuse variable names.
· A variable whose value is used in S1 is redefined in S2.
· It is to be ensured that the old value of variable is used in S1.
· If we execute S1 & S2 in parallel, it might be possible that S2 gets executed first, which results in a new value being used in S1.
Example: Let S1: A=B+C; B is used in S1 & is redefined in S2
S2: B=0;
USE (S1) = {B, C}
DEF (S2) = {B}
And DEF (S2) intersection USE (S1) = {B}
Therefore, Anti-dependence arises.
OUTPUT DEPENDENCE: It arises when
DEF (S1) intersection DEF (S2)! = { }
It arises because of 2 reasons:
a. Reuse of variable names for convenience.
b. Incremental computation of a variable.
Example: Let S1: A=B+C;
S2: A=A-D;
DEF (S1) = {A}
DEF (S2) = {A}
And DEF (S1) intersection DEF (S2) = {A}
Therefore, Output dependence arises.

INPUT DEPENDENCE: It arises when
USE (S1) intersection USE (S2)! = { }
c. There is no threat to parallelism as a commonly accessed or used variable is present.
d. Since accessing a value by a process does not change its value, therefore, any number of processes accessing the value simultaneously is acceptable.
Example: Let S1: A=B+C; No harm in executing S1 & S2 in parallel
S2: D=B+5;
USE (S1) = {B, C}
USE (S2) = {B}
And USE (S1) intersection USE (S2) = {B}
Among all 4 types of dependencies, FLOW Dependence is real & is unavoidable because it is inherent in the style of computation. It is bound to occur even irrespective of the programming paradigm being used.


Q3.a How can we avoid various types of dependencies?
Ans. Flow dependence is real and it is unavoidable.

Avoiding Output dependence:
It can be avoided by suitable use of variable names. Consider the following statements, these have output dependence.
A= B+C;
A= C-D;
The dependence can be avoided by rewriting the statements
A1= B+C;
A= C-D;
Change all occurrences of A from the statement to the second statement to A1.
The expression can be combined as
A= B+C-D.

Avoiding Anti-Dependence:
It can also be avoided by suitable use of variable names. The following segment
A= B+C
B= 0
Has anti-dependence.
It can be avoided by rewriting
A= B+C
B1 =0
All occurrences of B below these statements must be changed to B1. However, such simple transformation is not always possible as in for loop statement.

Q3b. Explain “Dependence is not Transitive”.
Ans: Dependence relation is not transitive. By this we mean, if there are 3 sets of statements S1, S2 & S3, then if S1 & S2 are dependent and S2 & S3 are dependent then it does not imply that S1 & S3 are also dependent.
Let us prove it with an example.
Let S1: A=B+C;
S2: A=C-D;
S3: D=0;
DEF & USE sets of S1, S2 & S3 are:
DEF (S1) = {A} USE (S1) = {B, C}
(1)
DEF (S2) = {A} USE (S2) = {C, D} (2)
DEF (S3) = {D} USE (S3) = { } (3)

Now we know that, Output Dependence arises if:
DEF (S1) intersection DEF (S2)! = { } (A)
From (1) & (2),
DEF (S1) intersection DEF (S2) = {A}
Therefore, Output dependence exists between S1 & S2

Also, Anti- Dependence arises if:
DEF (S2) intersection Use (S1)! = { } (B)
From (2) & (3),
DEF (S3) intersection USE (S2) = {D}
Therefore, Anti-dependence exists between S2 & S3

Now, Flow dependence arises if:
DEF (S1) intersection USE (S2)! = { } (C)
But from (1) & (3)
None of the conditions ((A), (B), (C)) holds true
Therefore, there is no dependence between S1 & S3
Hence dependence is not transitive.

Fill in the blanks/ multiple choice questions with answers

1. Dependence arise from the need to share resources among instructions is
.
2. Primary sources of dependency are

3. set is a set of variables modified by the statement.

4 set of a statement is the set of variables accessed by the statement.
True dependence also known as .
Identify the type of dependence
S1: A= B+C;
S2: D= 2*A;
a) Anti-dependence b) Flow/ true dependence
c) Output dependence d) Input dependence
Anti- dependence arises when which of the following set of intersection is non-empty
a) DEF(S1) and USE(S2) b) DEF(S2) and USE(S1)
b) DEF(S1) and DEF(S2) d) USE(S1) and USE(S2)
Anti - dependence is the opposite of
a) Input dependence b) Flow/ true dependence
c) Output dependence d) none of these
9. Which of the following is the most common type of dependence and most difficult
to avoid?
a) Anti-dependence b) Flow/ true dependence
c) Output dependence d) Input dependence
10. dependence is real and unavoidable.
11. How can we avoid this dependence?
A= B+C
A= C-D and also identify the type of dependence also.


Answers
1. Resource dependence
2. Control, data and resource
3. DEF
4. USE
5. Flow dependence
6. b)
7. b)
8. b)
9. b)
10. Flow dependence
11. Output dependence and can be avoided by rewriting as
A1= B+C A= C-D
Or
A= B+C-D

Content Credit : RUPINDER KAHLON

Read full story

Assignment Parallel Processing

Ques.1 Which of the computer use a single processor?
Personal Computer
Parallel Computer
Cray Computer

Ques.2 Travel Agents access this computer system when receiving flights.
Super Computer
Personal Computer
Mainframe Computers

Ques.3 Which of the computers used in the weather forecasting system?
Notebook Computer
Super Computer
Jon Von Neumann Computer

Ques.4 Which computers are connected to many terminals and can multitask?
PC running MS Dos
Minicomputers
Leo /Computers

Ques.5 How many number of users can work on a minicomputer?
No Limit
200 Users
1000 users

Ques.6 _________ is used as a measure of computer’s performance especially in the field of scientific computing that makes use of heavy floating point calculations.
FLOPS
G Hertz
Terabytes

Ques.7 ___________computer's abilities are defined by their massive internal memory, large, high-capacity external storage, fast high-throughput I/O, high-quality internal engineering and expensive but high-quality technical support.
Mainframe
Super Computers
Laptops
Personal Computer

Ques.8 Mainframe computers are multi-tasking and generally used in areas where large __________ are maintained.
databases
Multiple Threads
Serialized Classes
Ques.9 _______ are used for interacting with mainframe systems remotely.
Dumb terminals
Personal Computers
Handhelds
Notebook

Ques.10 The _____________ large number of processors, enormous disk storage, and substantial memory greatly increase the power and speed of the machine.
A . Supercomputer's
B . Mainframe ‘s
C . Embeded Computer’s


Subjective Questions


Ques.1 How can High speed Computing be achieved?

Ans. High speed computing can be achieved by High Performance computing technique which is employed as a branch of computer science that concentrates on developing supercomputers and software to run on supercomputers. A main area of this discipline is developing parallel processing algorithms and software: programs that can be divided into little pieces so that each piece can be executed simultaneously by separate processors.
Ques.2 What are High Performance Computing Clusters?

Ans. High Performance Computing Cluster (HPCC) combines multiple Symmetric Multi-Processor (SMP) computer systems together with high-speed interconnects to achieve the raw-computing power of classic "big-iron" supercomputers. These systems work in tandem to complete a single request by dividing the work among the server nodes, reassemble the results and present them to the client as if a single-system did the work.
The HPC clusters are used for solving the most challenging and rigorous engineering tasks facing the present era. The parallel applications running on HPC are both numeric and data intensive and require medium to high-end industry standard computing resources to fulfill today's computational needs. Since HPC has such a strong implementation, the demand for it is growing at a tremendous speed and is becoming highly popular in all aspects.

Ques.3 Write Down the applications of Supercomputers?

Ans. Supercomputers are so powerful that they can provide researchers with insight into phenomena that are too small, too big, too fast, or too slow to observe in laboratories. For example, astrophysicists use supercomputers as "time machines" to explore the past and the future of our universe. A supercomputer simulation was created in 2000 that depicted the collision of two galaxies: our own Milky Way and Andromeda. Although this collision is not expected to happen for another three billion years, the simulation allowed scientists to run the experiment and see the results now. This particular simulation was performed on Blue Horizon, a parallel supercomputer at the San Diego Supercomputer Center. Using 256 of Blue Horizon's 1,152 processors, the simulation demonstrated what will happen to millions of stars when these two galaxies collide. This would have been impossible to do in a laboratory.
Another example of supercomputers at work is molecular dynamics (the way molecules interact with each other). Supercomputer simulations allow scientists to dock two molecules together to study their interaction. Researchers can determine the shape of a molecule's surface and generate an atom-by-atom picture of the molecular geometry. Molecular characterization at this level is extremely difficult, if not impossible, to perform in a laboratory environment. However, supercomputers allow scientists to simulate such behavior easily.
Beside this supercomputers are also used in weather forecasting. To estimate the weather in the coming days/weeks.

Ques.4 Write down the configuration of an existing mainframe computer?

Ans. IBM Mainframe Computer S/390 Parallel Enterprise Server
Hardware

Processor technology Air-cooled S/390 CMOS

Architecture IBM S/390

Number of processors 9672-R11:1
9672-R21:2
9672-R31:3
9672-R41:4
9672-R51:5
9672-R61:6
Channels
Minimum 3
Maximum 48
Increments Channels are available in increment of 3
General Parallel Channel, ESCON and ESCON XDF
(Extended Distance Feature) are available

Processor Storage
Minimum 128 MB
Maximum 2048 MB
Options 256 MB
512 MB
1024 MB
2048 MB
Physical configuration

Minimum 1 Frame
Weight: 540 Kgs.
Footprint: 1.0 M ²
Service Clearance: 2.5 M ²
Input Power: 1.4 KVA
Heat Output: 1.3 kW

Maximum 2 Frame
Weight: 1040 Kgs.
Footprint: 1.8 M ²
Service Clearance: 4.8 M ²
Input Power: 2.3 KVA
Heat Output: 2.1 kW

Read full story