4.2.1.3 Efficiency An alternative measure for the performance of a parallel program is the efficiency. The efficiency captures the fraction of time for which a processor is usefully employed by computations that also have to be performed by a sequential program. The definition of the efficiency is based on the cost of a parallel program and can be expressed as: where T (n) is the sequential execution time of the best sequential algorithm and Tp(n) is the parallel execution time on p processors. If no superlinear speedup occurs, then Ep(n) ≤ 1. An ideal speedup Sp(n) = p corresponds to an efficiency of Ep(n) = 1. 4.2.1.4 Amdahl’s Law The parallel execution time of programs cannot be arbitrarily reduced by employing parallel resources. As shown, the number of processors is an upper bound for the speedup that can be obtained. Other restrictions may come from data dependencies within the algorithm to be implemented, which may limit the degree of parallelism. An important restriction comes from program parts that have to be executed sequentially. The effect on the obtainable speedup can be captured quantitatively by Amdahl’s law: When a (constant) fraction f, 0 ≤ f ≤ 1, of a parallel program must be executed sequentially, the parallel execution time of the program is composed of a fraction of the sequential execution time f · T (n) and the execution time of the fraction (1 − f ) · T (n), fully parallelized for p processors, i.e., (1 − f )/p · T (n). The attainable speedup is therefore: This estimation assumes that the best sequential algorithm is used and that the parallel part of the program can be perfectly parallelized. The effect of the sequential computations on the attainable speedup can be demonstrated by considering an example: If 20% of a program must be executed sequentially, then the attainable speedup is limited to 1/ f = 5 according to Amdahl’s law, no matter how many processors are used. Program parts that must be executed sequentially must be taken into account in particular when a large number of processors are employed.

4.2.1.3 Eficiencia Una medida alternativa para el desempeño de un programa paralelo es la eficiencia. La eficiencia captura la fracción de tiempo durante el cual un procesador es empleado de manera útil por cálculos que también deben ser realizados por un programa secuencial. La definición de la eficiencia se basa en el costo de un programa paralelo y se puede expresar como: donde T (n) es el tiempo de ejecución secuencial del mejor algoritmo secuencial y Tp (n) es el tiempo de ejecución paralelo en los procesadores p. Si no se produce una aceleración superlineal, entonces Ep (n) ≤ 1. Una aceleración ideal Sp (n) = p corresponde a una eficiencia de Ep (n) = 1. 4.2.1.4 Ley de Amdahl El tiempo de ejecución paralelo de los programas no puede reducirse arbitrariamente empleando recursos paralelos. Como se muestra, el número de procesadores es un límite superior para la aceleración que se puede obtener. Otras restricciones pueden provenir de dependencias de datos dentro del algoritmo a implementar, lo que puede limitar el grado de paralelismo. Una restricción importante proviene de las partes del programa que deben ejecutarse secuencialmente.El efecto en la aceleración que se puede obtener puede ser capturado cuantitativamente por la ley de Amdahl: Cuando una (constante) fracción f, 0 ≤ f ≤ 1, de un programa paralelo debe ejecutarse secuencialmente, el tiempo de ejecución paralelo del programa se compone de una fracción del tiempo de ejecución secuencial f · T (n) y el tiempo de ejecución de la fracción (1 - f) · T (n), completamente en paralelo para los procesadores p, es decir, (1 - f) / p · T (n). La aceleración alcanzable es por lo tanto: Esta estimación supone que se utiliza el mejor algoritmo secuencial y que la parte paralela del programa se puede paralelizar perfectamente. El efecto de los cálculos secuenciales sobre la aceleración alcanzable se puede demostrar considerando un ejemplo: si el 20% de un programa debe ejecutarse secuencialmente, entonces la aceleración alcanzable se limita a 1 / f = 5 según la ley de Amdahl, sin importar cuántos Se utilizan procesadores. Las partes del programa que deben ejecutarse secuencialmente deben tenerse en cuenta, en particular, cuando se emplea una gran cantidad de procesadores.