Учебное пособие Казань 018 удк

часть программы, равна единице. Загруженности остальных устройств 
𝑝
𝑖
=
(1−𝛽)𝑁/𝑠
𝛽𝑁+(𝛽−1)𝑁/𝑠
, 𝑖 = 2, 𝑠
̅̅̅̅
. 
Следовательно, в соответствии с (3.13) 
𝑅 = 1 + ∑
(1 − 𝛽)𝑁/𝑠
𝛽𝑁 + (𝛽 − 1)𝑁/𝑠
=
𝑠
𝛽𝑠 + (1 − 𝛽)
.
𝑠
𝑖=2
Формула Амдала используется для прогноза возможного ускорения. 
Например, 
в 
случае, 
когда 
половина 
операций 
не 
поддаются 
распараллеливанию, 
максимально 
достижимое 
ускорение 
в 
случае 
использования 2 процессоров в соответствии с (3.12) составит около 1,33, для 
10 процессоров - менее 1,82, а для 100 процессоров - около 1,98. В данном 
примере наиболее «узким» местом является сам алгоритм решения задачи, а 
основные усилия должны быть направлены на поиск другой формулировки 
задачи, допускающей более высокую степень параллелизма. 
3.4. Закон Густавсона - Барсиса 
Оценку максимально достижимого ускорения параллельного алгоритма 
можно построить также исходя из имеющейся доли последовательных 
расчетов, задаваемой в виде [3]: 
𝑔 =
𝜏
𝑛
𝜏
𝑛
+𝜏
𝑁−𝑛
/𝑠
.
(3.14) 

---

32 
где 
𝜏
𝑛
и 
𝜏
𝑁−𝑛
- время, необходимое для выполнения последовательной и 
параллельной частей соответственно. 
С учетом введенных обозначений время решения задачи на одном и 
s 
процессорах соответственно 
𝑇
1
= 𝜏
𝑛
+ 𝜏
𝑁−𝑛
, 𝑇
𝑠1
= 𝜏
𝑛
+ 𝜏
𝑁−𝑛
/𝑠
.
(3.15) 
С другой стороны, из соотношения (3.14) для величины 
g
можно 
записать: 
𝜏
𝑛
= 𝑔 (𝜏
𝑛
+
𝜏
𝑁−𝑛
𝑠
) , 𝜏
𝑁−𝑛
= (1 − 𝑔)𝑠(𝜏
𝑛
+
𝜏
𝑁−𝑛
𝑠
)
. 
(3.16) 
С учетом (3.4), (3.15) и (3.16) получаем оценку для ускорения 
𝑅 =
𝑇
1
𝑇
𝑠
=
𝜏
𝑛
+𝜏
𝑁−𝑛
𝜏
𝑛
+𝜏
𝑁−𝑛
/𝑠
=
(𝑔+(1−𝑔)𝑠)(𝜏
𝑛
+
𝜏𝑁−𝑛
𝑠
)
𝜏
𝑛
+𝜏
𝑁−𝑛
/𝑠
= 𝑔 + (1 − 𝑔)𝑠
. 
(3.17) 
Оценку (3.17) называют законом Густавсона - Барсиса. Нетрудно 
заметить, что эту оценку можно также переписать в виде: 
𝑅 =
𝑇
1
𝑇
𝑠
= 𝑠 + (1 − 𝑠)𝑔
.
(3.18)