tailieunhanh - Algorithms and Data Structures in C part 10

If an algorithm can be completely decomposed into n parallelizable units without loss of efficiency then the Speedup obtained | If an algorithm can be completely decomposed into n parallelizable units without loss of efficiency then the Speedup obtained is If however only a fraction f of the algorithm is parallelizable then the speedup obtained is which yields This is known as Amdahl s Law. The ratio shows that even with an infinite amount of computing power an algorithm with a sequential component can only achieve the speedup in Eq. . If an algorithm is 50 sequential then the maximum speedup achievable is 2. While this may be a strong argument against the merits of parallel processing there are many important problems which have almost no sequential components. Definition The efficiency of an algorithm executing on n processors is defined as the ratio of the speedup to the number of processors Using Amdahl s law with Pipelining Pipelining is a means to achieve speedup for an algorithm by dividing the algorithm into stages. Each stage is to be executed in the same amount of time. The flow is divided into k distinct stages. The output of the jth stage becomes the input to the j 1 th stage. Pipelining is illustrated in Figure . As seen in the figure the first output is ready after four time steps Each subsequent output is ready after one additional time step. Pipelining becomes efficient when more than one output is required. For many algorithms it may not be possible to subdivide the task into k equal stages to create the pipeline. When this is the case a performance hit will be taken in generating the first output as illustrated in Figure . Figure A Four Stage Pipeline Figure Pipelining In the figure TSEQ is the time for the algorithm to execute sequentially. TPS is the time for each pipeline stage to execute. TPIPE is the time to flow through the pipe. The calculation of the time complexity sequence to process n inputs yields for a -stage pipe. It follows that TPIPE n TSEQ n when The speedup for pipelining is Example Order which yields In some .