Discovery Guides Areas


Grid Computation: the Fastest Supercomputer in the World
(Released November 2006)

  by Chao-Hsu Yao  


Key Citations

Web Sites




♦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)

diagram of how a computer handles multiple tasks

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 = {v1, v2, ..., vn}
To perform addition for 2 vectors X and Y, we will need to do
X + Y = {x1, x2, ..., xn} + {y1, y2, ..., yn} = {x1+y1, x2+y2, ..., xn+yn}
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)
charts of number sequences

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.

sequence of altering numbers
♦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 web-based 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 in-house at CSA