Jak najszybsze znalezienie dwóch największych z pięciu małych liczb całkowitych

Używam odmiany 5-krzyżowego filtra środkowego na danych obrazu w małym systemie osadzonym, tj

    x
  x x x
    x

Algorytm jest naprawdę prosty: odczytaj 5 liczb całkowitych bez znaku, uzyskaj najwyższe 2, wykonaj kilka obliczeń i zapisz wynik na liczbach całkowitych bez znaku.

Ładne jest to, że 5 wartości całkowitych wejściowych mieści się w zakresie 0-20. Obliczona wartość całkowita również mieści się w zakresie 0-20!

Dzięki profilowaniu zorientowałem się, że uzyskanie dwóch największych liczb jest wąskim gardłem, więc chcę przyspieszyć tę część. Jaki jest najszybszy sposób na dokonanie tego wyboru?

Obecny algorytm wykorzystuje maskę 32-bitową z 1 w pozycji podanej przez 5 liczb i obsługiwaną przez HW funkcję CLZ.
Powinienem powiedzieć, że procesor jest zastrzeżony, niedostępny poza moją firmą. Mój kompilator to GCC, ale dostosowany do tego procesora.

Próbowałem dowiedzieć się, czy mogę użyć tabeli odnośników, ale nie udało mi się wygenerować klucza, którego mogę użyć.

Mam kombinacji dla danych wejściowych, ale kolejność nie jest ważna, tzn. Jest taka sama jak .$21^5$[5,0,0,0,5][5,5,0,0,0]

Zdarza się, że funkcja skrótu poniżej tworzy idealny skrót bez kolizji!

def hash(x):
    h = 0
    for i in x:
        h = 33*h+i
    return h

Ale skrót jest ogromny i po prostu nie ma wystarczającej ilości pamięci, aby z niego skorzystać.

Czy istnieje lepszy algorytm, którego mogę użyć? Czy jest możliwe rozwiązanie mojego problemu za pomocą tabeli przeglądowej i wygenerowania klucza?

W mojej drugiej odpowiedzi sugeruję, że skoki warunkowe mogą być główną przeszkodą dla wydajności. W rezultacie przychodzą na myśl sieci sortujące : są one niezależne od danych, to znaczy ta sama sekwencja porównań jest wykonywana bez względu na dane wejściowe, przy czym tylko wymiany są warunkowe.

Oczywiście sortowanie może być zbyt pracochłonne; potrzebujemy tylko dwóch największych liczb. Na szczęście dla nas przebadano również sieci selekcyjne . Knuth mówi nam, że można znaleźć dwie najmniejsze liczby z pięciu² $\hat{U}_2(5) = 6$ porównania [1, 5.3.4 ex 19] (i co najwyżej tyle swapów).

Sieć, którą podaje w rozwiązaniach (przepisana na tablice zerowe) to

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

który implementuje - po dostosowaniu kierunku porównań - w pseudokodzie jako

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Teraz naiwne implementacje nadal mają skoki warunkowe (w całym kodzie wymiany). Jednak w zależności od maszyny można je wymyślić za pomocą instrukcji warunkowych. x86 wydaje się być zwykłym błotnistym ja; ARM wygląda bardziej obiecująco, ponieważ najwyraźniej większość operacji jest uwarunkowana sama w sobie. Jeśli dobrze rozumiem instrukcje , pierwsza zamiana przekłada się na to, zakładając, że nasze wartości tablic zostały załadowane do rejestrów R0poprzez R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

^{Tak, tak, oczywiście możesz używać zamiany XOR z EOR .}

Mam tylko nadzieję, że twój procesor ma to lub coś podobnego. Oczywiście, jeśli zbudujesz coś w tym celu, może uda ci się tam podłączyć sieć?

Jest to prawdopodobnie (możliwe?) Najlepsze, co możesz zrobić w klasycznej dziedzinie, tj. Bez korzystania z ograniczonej domeny i wykonywania nikczemnych magii wewnątrz słowa.

1. Sortowanie i wyszukiwanie według Donalda E. Knutha; The Art of Computer Programming Vol. 3 (wydanie 2, 1998)
2. Zauważ, że pozostawia to dwa wybrane elementy nieuporządkowane. Zamawianie ich wymaga dodatkowego porównania$\hat{W}_2(5) = 7$ wielu łącznie [1, p234 Tabela 1].

Oto algorytm bezpośredni, który znajduje się na stole:

// Sort x1, x2
if x1 < x2
  M1 = x2
  m1 = x1
else
  M1 = x1
  m1 = x2
end

// Sort x3, x4
if x3 < x4
  M2 = x4
  m2 = x3
else
  M2 = x3
  m2 = x4
end

// Pick largest two
if M1 > M2
  M3 = M1
  if m1 > M2
    m3 = m1
  else
    m3 = M2
  end
else
  M3 = M2
  if m2 > M1
    m3 = m2
  else
    m3 = M1
  end
end

// Insert x4
if x4 > M3
  m3 = M3
  M3 = x4
else if x4 > m3
  m3 = x4
end

Dzięki sprytnej implementacji if ... elsemożna pozbyć się pewnych bezwarunkowych skoków, jakie miałoby bezpośrednie tłumaczenie.

To jest brzydkie, ale zajmuje tylko

• pięć lub sześć porównań (tj. skoki warunkowe),
• dziewięć do dziesięciu przypisań (z 11 zmiennymi, wszystkie w rejestrach) i
• brak dodatkowego dostępu do pamięci.

W rzeczywistości sześć porównań jest optymalnych dla tego problemu, jak pokazuje Twierdzenie S w sekcji 5.3.3 [1]; tutaj potrzebujemy$W_2(5)$.

Jednak nie można oczekiwać, że będzie to szybkie na maszynach z potokowaniem; biorąc pod uwagę wysoki odsetek skoków warunkowych, większość czasu prawdopodobnie spędziłaby w przeciągnięciu.

Zauważ, że prostszy wariant - rodzaj x1i x2, a następnie włóż innymi wartościami następnie - trwa od czterech do siedmiu porównań i tylko pięć do sześciu zadań. Ponieważ spodziewam się, że skoki będą tu droższe, utknąłem przy tym.

1. Sortowanie i wyszukiwanie według Donalda E. Knutha; The Art of Computer Programming Vol. 3 (wydanie 2, 1998)

Może to być świetna aplikacja i test dla projektu Souper . Souper to superoptimizer - narzędzie, które pobiera krótką sekwencję kodu jako dane wejściowe i próbuje zoptymalizować go w jak największym stopniu (próbuje znaleźć równoważną sekwencję kodu, która będzie szybsza).

Souper jest open source. Możesz spróbować uruchomić Souper na swoim fragmencie kodu, aby sprawdzić, czy da to coś lepszego.

Zobacz także konkurs Johna Regehra na pisanie szybkiego kodu do sortowania 16 4-bitowych wartości ; możliwe, że niektóre techniki mogą być przydatne.

Możesz użyć $21^3$tabela, która pobiera trzy liczby całkowite i wyświetla dwie największe. Następnie możesz użyć trzech odnośników tabeli:

T[T[T[441*a+21*b+c]*21+d]*21+e]

Podobnie za pomocą $21^4$ tabeli, możesz zredukować ją do dwóch wyszukiwań tabeli, choć nie jest jasne, że byłoby to szybsze.

Jeśli naprawdę chcesz mały stolik, możesz użyć dwóch $21^2$tabele, aby „posortować” dwie liczby, a następnie użyć sieci sortującej. Według Wikipedii wymaga to maksymalnie 18 przeszukiwania tabel (9 komparatorów); możesz być w stanie zrobić mniej, ponieważ (1) chcesz znać tylko dwa największe elementy, i (2) dla niektórych bramek porównawczych, możesz być zainteresowany tylko maksimum.

Możesz także użyć jednego $21^2$stół. Wdrożenie sieci sortującej zużywa mniej pamięci, ale więcej arytmetyki. W ten sposób uzyskuje się maksymalnie 9 odnośników do tabeli.