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