Безпосередня та пряма адресації
Розглянемо два приклади.
11.Закони Амдала та Густафсона.
DOP (Degree Of Parallelism)
Ступінь паралелізму програми – D(t) – число процесорів, що у виконанні рограммы у час t
DOP залежить від алгоритму програми, ефективності компіляції та доступних ресурсів під час виконання
Графік D(t) – профіль паралелізму програми
T(n) – час виконання програми на n процесорах
T(n) T(1), якщо накладні витрати (витрати) реалізації паралельної версії алгоритму надмірно великі
Прискорення за рахунок паралельного виконання
Ефективність системи з n процесорів
Випадок S(n)=n – лінійне прискорення – масштабованість (Scalability) алгоритму (можливість прискорення обчислень пропорційно числу процесорів)
Випадок S(n)>n – суперлінійне прискорення (наприклад, через більший коефіцієнт кеш-попадань)
Gene Amdahl (1967)
f – частка послідовної частини програми
1-f – частка частини, що розпалюється.
Практичні обмеження прискорення
Джин Амдал сформулював закон у 1967 році, виявивши просте по суті, але непереборне за змістом обмеження зростання продуктивності при розпаралелювання обчислень:
«У разі, коли завдання поділяється на кілька частин, сумарний час її виконання на паралельній системі не може бути меншим за час виконання найдовшого фрагмента». Якщо частина коду f, що розділяється, може бути рівномірно формально розподілена по n процесорам, то закономірність може бути записана, як представлено на рис. 1.
Закон визначає теоретично можливий верхній кордон, але на практиці справа ще гірша – частинаресурсів кожного процесора йде на забезпечення колаборативної роботи, а шини мають кінцеву пропускну здатність.
Єдина відома гіпотеза про можливість подолання описаних обмежень була висловлена в 1988 Джоном Густафсоном, але вона не поширюється на підмножину фіксованих завдань. На підставі отриманого досвіду Густафсон дійшов висновку, що при побудові потужніших систем користувачі прагнуть не скоротити час роботи поточної версії завдання, а перейти до нової версії, яка забезпечує більш високу якість рішення:
S(P)= P – l(P – 1), де P – число процесорів, S – прискорення, l – частина коду, що не піддається розпаралелювання.
Закон масштабованого прискорення (Scaled Speedup):
Припустимо, деяку конструкцію можна розрахувати методом кінцевих елементів, і в такому разі, чим меншим береться розмір елемента, тим точніше буде. Сьогодні ідеї Густафсона, пов'язані з удосконаленням методів комунікації між вузлами, реалізуються у компанії Massively Parallel Technologies (MPT), де, до речі, працює і сам Амдал. Припустимо сказати, що це методи дозволяють подолати обмеження закону, названого його ім'ям, але побічно.
Принцип заміни простих завдань складнішими, запропонований Густафсоном, скоріше екзотика, ніж повсякденна практика, у масових додатках, куди розраховуються багатоядерні процесори, діє закон Амдала.