Podaj przykład ponadliniowego przyśpieszenia obliczeń i wyjaśnij możliwe przyczyny

Przyspieszenie ponadliniowe możemy zaobserwować dla:

• Sekwencyjnego (skalarnego) mnożenia macierzy

    Wejście: 
        C ∈ IRm×n
        A ∈ IRm×k
        B ∈ IRk×n
        α, β ∈ IR
    Wyjście: 
        C = βC + αAB
  
    1: for j = 1 to n do
    2: for i = 1 to m do
    3: t ← 0
    4: for l = 1 to k do
    5: t ← t + ailblj
    6: end for
    7: cij ← βcij + αt
    8: end for
    9: end for
  

Taką sytuację obserwuje się często, gdy w przypadku obliczeń równoległych, dane przetwarzane przez poszczególne procesory (rdzenie) lepiej wykorzystują pamięć podręczną

• problemy z pamięcią:
  • np. aplikacja potrzebuje dużo pamięci, która musi być załadowana/przeładowana z/na dysk jednego z procesorów (?)
    • to zwalnia obliczenia na tym procesorze
    • z drugiej strony część danych przypisana do procesorów w rozruchu równoległym dopasowują się do pamięci i nie potrzeba robić żadnych przeładowań, więc nie ma błędów stronnicowania
• procesowanie niespodziewanych strumieni danych:
  • jeżeli przychodzi wiele (więcej niż jest procesorów) strumieni danych to niektóre dają rozwiązania szybciej niż inne
• jeden procesor może przetwarzać dane tylko z jednego strumienia i nie jest w stanie przewidzieć które z nich będą najlepsze
• wiele procesorów przetwarza wszystkie strumienie równolegle