
♦What kind of processes can be done in parallel?
To solve a problem using grid computation, the process must be divisible into several subprocesses, and each subprocess should be independent. For example, using an editorial company with 10 employees, if we would like to calculate the average production number per employee per day, we may have 10 CPUs to calculate each employee's average daily production number in one month, separately, at the same time, and use one CPU to calculate the 10 employees' average daily production number. It only takes two steps to finish the job, while it takes 11 steps using a single CPU. (See Fig. 1)

However, if the process cannot be divided into several subprocesses, the parallel computation won't be performable. If some of the subprocesses are dependent on previous ones, the parallel computation will still be performed, but won't greatly speed up the outcome. For the above example, the red arrow stage (averaging 10 employees' daily production numbers in one month) cannot be started, until all blue stages (averaging each employee's daily production numbers) have been completed.
Vector computation is one of the most popular parallel computations, and has long been used in solving scientific problem. A vector V containing n elements is normally expressed as
V = {v_{1}, v_{2}, ..., v_{n}}
To perform addition for 2 vectors X and Y, we will need to do
X + Y = {x_{1}, x_{2}, ..., x_{n}} + {y_{1}, y_{2}, ..., y_{n}} = {x_{1}+y_{1}, x_{2}+y_{2}, ..., x_{n}+y_{n}}
Doing this sequentially, it takes n steps to complete the job. However, using an n CPUs machine to perform parallel computation, it only takes one step to complete the job.
The Bitonic Sorting Algorithm is a very fast sorting method using parallel computation to sort bitonic sequences. A bitonic sequence is a series of numbers, for which
 the sequence is monotonically increasing and is monotonically decreasing; or
 there exists a cyclic shift of indicies such that the above is satisfied. (See Fig. 2)
For example, to sort 8 bitonic numbers using 4 CPU's, in the first step we compare the 1st and 5th, 2nd and 6th, 3rd and 7th, and 4th and 8th numbers and switch them if they are not in order. In the second step, we compare the 1st and 3rd, 2nd and 4th, 5th and 7th, and 6th and 8th numbers and switch them if they are not in order. In the 3rd step, we compare 1st and 2nd, 3rd and 4th, 5th and 6th, and 7th and 8th numbers, and switch them if they are not in order. The total parallel process can be shown in Fig. 3. It only takes 3 steps while sequential comparison using a single CPU could takes up to 12 steps to complete the job.

♦How can computer resources be shared on line using internet connections?
Unlike most companies and academic institutions, which run computers in a Local Area Network (LAN) environment, grid computation runs processes under an internet (global) environment. Therefore, a specific domain must be set up to restrict resource sharing to those with authorized access. This domain is called virtual organization (VO, aka the Grid), which is outside the LAN environment.
People who join a VO will be able to share some (but not all)
of their computer's resources (storage drive, memory, or CPU
. . .) with others in the same VO. Normally a webbased interface
is designed for users to perform their requests.
When a computer joins the VO, it will start running a subprocess
after receiving the request online from another computer. The
benefit of grid computation is that when users log in to the
internet, they may not use their computers' CPUs all the time.
For instance, when they are reading news on a website, it may
take them 10 minutes to finish reading an article, while the
CPU stays idle. Other users will try their best to utilize this
computer's CPU to run the subprocess in parallel while it's
idle. Imagine how many computers there are running parallel
processing in a VO. Even if most of them provide only a few
resources, a proper design could speed up the whole process.
Go To Applications
© Copyright 2006, All Rights Reserved, CSA
All figures
developed inhouse at CSA

