Prawa Amdahla i Gustafsona thumbnail|Przykładowy wykres czasu wykonania programu (actual runtime) i jego przyspieszenie (actual speedup) w zależności od liczby procesorów. W pewnym momencie, pomimo zwiększania liczby procesorów, czas obliczeń przestaje maleć (podobnie przyspieszenie przestaje rosnąć). Zaznaczono również optymalny wzrost przyspieszenia (ideal speedup) oraz optymalny spadek czasu obliczeń (ideal runtime). Teoretycznie, przyspieszenie spowodowane zrównolegleniem mogłoby być co najwyżej liniowe – podwojenie liczby jednostek obliczeniowych nie może zmniejszyć czasu obliczeń o więcej niż połowę, jednak w praktyce osiągnięcie optymalnego przyspieszenia nie jest możliwe. Większość realizacji osiąga przyspieszenie bliskie optymalnemu tylko dla małej liczby jednostek obliczeniowych.
Potencjalne przyspieszenie algorytmu na platformie korzystającej z obliczeń równoległych jest określone przez prawo Amdahla sformułowane w latach 60. XX wiekuG. Amdahl, The validity of the single processor approach to achieving large-scale computing capabilities, Materiały konferencyjne AFIPS Spring Joint Computer Conference, s. 483–485, Atlantic City, N.J., kwiecień 1967.