In scientic visualization, use is made of multiprocessor computers. 1.1. Amajori

ID: 3764038 • Letter: I

Question

In scientic visualization, use is made of multiprocessor computers.

1.1. Amajorissuewithmultiprocessorcomputersistheamountofspeedup that can be achieved compared to a uniprocessor computer. There are two laws covering speedup: Amdahl and Gustafson.

1.1.1. Do either of these have a formal proof? If so, present the formal proof and explain what it means (i.e., do not just use formalism, also use ordinary English sentences).

1.1.2. Do either of these have a basis in data? If so, explain the data and explain how the data is used to justify the law.

1.1.3. Which of these laws are more likely to be applicable to most problems in scientic visualization? Explain your answer with some examples.

1.2. Explain the various steps (or functionalities) in scientic visualization. Which steps are most easily implemented on a multiprocessor machine? Why?

1.3. In most cases, are truly parallel algorithms implemented for scientic visualization at the present epoch? If not, how is parallelization actually implemented? (Hint: consider the implementation of Paraview and how one does scientic visualization within Paraview.)

Explanation / Answer

Amdahl law describes the parallelizing the load in general is in vain without driving up the accompanying sequential processing rates. It deals with irregularities in real-world problem sets would degrade parallel performance.

It is a set of mathematical relationships that became known as Amdahl's Law, which quantifies the theoretical speedup that can be obtained by parallelizing a computational load among a set number of processors

Amdahl shows that increasing the parallelism of the computing environment by some number N an never increase performance by a factor of N. The two main factors contribute to this limitation are the presence of the inherently serial portion of the computational load and the overhead associated with parallelization.

That overhead consists of such factors as creating and destroying threads, locking data to prevent multiple threads from manipulating it simultaneously, and synchronizing the computations performed among various threads to obtain a coordinated result.

Gustafson, work helped to refine Amdahl's model by adjusting some of its underlying assumptions to more accurately reflect the course of his work. Gustafson argues that, as processor power increases, the size of the problem set also tends to increase

cores

Computation

Speedup

Efficiency
(speedup / # cores)

.1 + 2 ( 1 - .1)

1.9x

95.00%

.1 + 4 ( 1 - .1)

3.7x

92.50%

.1 + 32 ( 1 - .1)

28.9x

90.31%

1024

.1 + 1024 ( 1 - .1)

921.7x

90.01%

Speedup, Efficiency, and Scalability

Two important metrics related to performance and parallelism are speedup and efficiency. Speedup (Equation 1) compares the latency for solving the identical computational problem on one hardware unit ("worker") versus on P hardware units:

Equation 1.

where T1 is the latency of the program with one worker and TP is the latency on P workers.

Equation 2.

Efficiency measures return on hardware investment. Ideal efficiency is 1 (often reported as 100%), which corresponds to a linear speedup, but many factors can reduce efficiency below this ideal.

Amdahl argued that the execution time T1 of a program falls into two categories:

Time spent doing non-parallelizable serial work

Time spent doing parallelizable work

Call these Wser and Wpar, respectively. Given P workers available to do the parallelizable work, the times for sequential execution and parallel execution are:

Equation 5.

The bound on TP assumes no superlinear speedup, and is an exact equality only if the parallelizable work can be perfectly parallelized. Plugging these relations into the definition of speedup yields Amdahl's Law:

Equation 6.

Figure 1 visualizes this bound. Amdahl's Law has an important corollary. Let f be the non-parallelizable serial fraction of the total work. Then the following equalities hold:

Equation 7.

Substitute these into Equation 7 and simplify to get: