Ćwiczenia
Napisz stałoprzecinkową implementację generatora Mandelbrota.
a.
Zauważysz, że wydajność jest niespójna pomiędzy różnymi pikselami i różnymi klatkami. Dlaczego tak się dzieje?
b.
Jaka jest intensywność arytmetyczna najbardziej wewnętrznej pętli, w operacjach na bajt dostępny z pamięci? Jaka jest odpowiednia granica wydajności dla Twojego procesora ARM? Jak to się ma do zaobserwowanej wydajności?
c.
Pomiar następujących metryk wydajności dla ciała pętli wewnętrznej:
▪
instrukcje na iterację
▪
instrukcje na operację
▪
CPI
▪
częstotliwość pominięć pamięci podręcznej
d.
Użyj złożenia inline do implementacji ciała najbardziej wewnętrznej pętli i zmierz wpływ wydajności w odniesieniu do metryk z części c. Jaki jest wzrost prędkości w porównaniu z kodem wygenerowanym przez kompilator?
Paralelizuj generator zbioru Mandelbrota za pomocą OpenMP. Zastosuj dyrektywę parallel-for do najbardziej zewnętrznej pętli (wierszowej).
a.
Zmierz średnią liczbę cykli wymaganych dla każdej iteracji najbardziej wewnętrznej pętli (do obliczenia wielomianu) dla jednego wątku i dwóch wątków dla początkowej ramki. Użyj tych pomiarów, aby obliczyć wzrost prędkości, w pikselach na sekundę, dwóch wątków w stosunku do jednego wątku.
b.
Zmierz czas obliczania wszystkich pikseli w pierwszej ramce, gdy używany jest harmonogram dynamiczny w porównaniu do harmonogramu statycznego.
Co utrudnia zastosowanie operacji SIMD dla generatora zbioru Mandelbrota? Jaka jest najbardziej efektywna metoda zastosowania operacji SIMD dla generatora zbioru Mandelbrota?
Pomiar efektywnej przepustowości zapisu dla bufora ramek systemu Linux. Czy jest ona równoważna przepustowości zapisu dla tablicy pamięci alokowanej ze sterty?
Oblicz intensywność arytmetyczną programu przekształcającego obraz w operacjach na piksel. Jaka jest jego granica wydajności biorąc pod uwagę efektywną przepustowość pamięci Twojego procesora ARM? Jak to się ma do zaobserwowanej wydajności?
Użyj OpenMP, aby dodać obsługę wielordzeniową do programu przekształcającego obraz stałoprzecinkowy. Aby to zrobić, zastosuj pragmę parallel for do najbardziej zewnętrznej pętli (wierszowej).
Pomierz jego wydajność na czterordzeniowym procesorze ARM. Jak skaluje się jego wydajność, gdy jest wykonywany z jednym, dwoma, trzema i czterema wątkami?
Użyj intrinsics, aby dodać obsługę NEON SIMD do stałoprzecinkowej wersji programu przekształcającego obraz. Użyj operacji czterokierunkowych do wykonania następujących obliczeń dla grupy czterech pikseli: lokalizacja piksela źródłowego, ekstrakcja frakcji i obliczenie wagi. W jakim stopniu poprawia to wydajność?
Nie możemy łatwo zoptymalizować programu generatora Mandelbrota za pomocą instrukcji SIMD, ponieważ sąsiednie piksele mogą wymagać różnej liczby ocen wielomianu, a każda iteracja wielomianu jest zależna od poprzedniej oceny. Alternatywnym podejściem jest zaimplementowanie pętli w asemblerze inline, rozwinięcie jej o co najmniej cztery, a następnie użycie programowego pipeliningu do poprawienia CPI pętli. W tym przypadku powinniśmy unikać rozgałęzień warunkowych wewnątrz rozwijanej pętli. Ponieważ rozbieżne wartości c będą nadal rozbieżne z kolejnymi obliczeniami, możemy poczekać na sprawdzenie warunku zakończenia pętli po każdej grupie czterech iteracji. Jednak wykonanie dodatkowych obliczeń wielomianu po tym, jak Pc() potencjalnie wykracza poza okrąg o promieniu 2, będzie wymagało od nas uwzględnienia dodatkowych wymagań dotyczących zakresu dla naszego formatu stałoprzecinkowego. Przelicz wymagania dotyczące zakresu dla formatu stałoprzecinkowego dla tej optymalizacji i określ, w jakim stopniu zmniejszy to maksymalny poziom powiększenia.
Głównymi zaletami formatu stałoprzecinkowego jest zmniejszenie opóźnienia operacji i możliwość uniknięcia konwersji typów w pewnych typach kodów graficznych. W rozdziale 2 zwrócono uwagę na przykładowy program, którego wydajność jest wrażliwa na opóźnienie operacji – metodę Hornera. Zakładając, że możemy tolerować ograniczenia zakresu metody stałoprzecinkowej w naszym kodzie metody Hornera, czy przekonwertowanie go na stałoprzecinkowy poprawiłoby wydajność? Wyjaśnij swoją odpowiedź.
W sekcji 3.6.5 pokazano dwie różne implementacje uogólnionego makra preprocesora dodawania stałoprzecinkowego. Pierwsza z nich została wygenerowana przez gcc przy maksymalnej optymalizacji, druga została zakodowana ręcznie przy użyciu języka asemblerowego. Obie implementacje wymagały mniej więcej takiej samej liczby instrukcji.
a.
Pokaż zależności danych read-after-write w obu implementacjach. Zakładając, że procesor używa pojedynczych instrukcji, w kolejności wydawania, oraz zakładając, że opóźnienie wszystkich operacji arytmetycznych na liczbach całkowitych wynosi cztery cykle, ile porównaj liczbę cykli przeciągnięć danych potrzebnych w obu implementacjach.
b.
Przepisz wersję makra dodawania stałoprzecinkowego w języku inline assembly tak, aby rozplanować instrukcje w taki sposób, aby zależne instrukcje były maksymalnie rozdzielone. W jakim stopniu są zredukowane przeciągnięcia, zakładając opóźnienie podane w części a?
c.
Napisz kod, który zademonstruje, jak wszystkie trzy implementacje (generowana przez kompilator, montowana liniowo i montowana liniowo) mogą być scharakteryzowane pod względem wydajności.
W tym pytaniu badamy implementację w asemblerze inline uogólnionego mnożenia stałoprzecinkowego opisaną w punkcie 3.6.6.
a.
Jak wypada, pod względem liczby instrukcji i wydajności runtime, w porównaniu z równoważnym kodem wygenerowanym przez kompilator dla:
res = (((long long)op1 * (long long)op2) >> (rp1>rp2?rp1:rp2)) +(rp1>rp2 ? ((((long long)op1 * (long long)op2) >> (rp1-1))&1) :
((((long long)op1 * (long long long)op2) >> (rp2-1))&1));
Pewnie użyj przełączników „-O3” i „-marm” podczas kompilacji z gcc.
b.
Zaplanuj instrukcje makra multiply w wersji inline assembly tak, aby zminimalizować zacięcia związane z zależnościami danych. Zmierz jego wydajność w stosunku do wersji podanej w sekcji 3.6.6.
c.
Dla implementacji w asemblerze inline, o ile więcej można osiągnąć, jeśli zostanie zmieniona tak, że pozycje punktów radix są stałe zamiast zmiennych, jak w kodzie? Dla tego pytania, użyj zarówno liczby instrukcji, jak i rzeczywistego zachowania runtime.
Obliczanie wartości pikseli dla zbioru Mandelbrota wymaga funkcji do konwersji liczby iteracji na kanały kolorów R, G i B. Ustawienie wszystkich trzech kanałów na tę samą wartość wygeneruje szary obraz, więc nachylenie każdej funkcji kanału koloru powinno być unikalne, a to, które nachylenie jest największe, określi odcień obrazu.
Jak opisano w sekcji 3.8.1, liczba ocen wielomianu może przekroczyć wartość, która przekracza zakres kanału koloru. Aby uniknąć potencjalnego przepełnienia, należy użyć arytmetyki nasycającej podczas obliczania wartości każdego piksela. W ten sposób, jeśli obliczona wartość przekroczy maksymalną dozwoloną wartość, ustaw ją na wartość maksymalną.
Napisz makro w języku C, które wykonuje 8-bitowe, niepodpisane mnożenie nasycające. Funkcja pobiera dwa 8-bitowe operandy i wytwarza 8-bitowy iloczyn ustawiony na 255, jeśli iloczyn przekracza 255. Makro nie może zawierać instrukcji rozgałęzienia i być zaplanowane pod kątem zależności od danych.
W tym ćwiczeniu zbadamy zwiększenie precyzji typów stałoprzecinkowych dla generatora Mandelbrota do 64-bitów.
a.
Używając współczynnika powiększenia 1.5zoom, do jakiego poziomu można powiększyć ramkę przed przekroczeniem tej precyzji?
b.
Zdefiniuj makro w języku C do dodawania dwóch (64,56) wartości stałoprzecinkowych. Makro może wykonywać 128-bitowe dodawanie przy użyciu czterech 32-bitowych dodawań i używać flagi przenoszenia do implementacji przenoszenia z każdej 32-bitowej grupy do następnej najbardziej znaczącej 32-bitowej grupy.
c.
Zdefiniuj makro w języku C do mnożenia dwóch (64,56) wartości stałoprzecinkowych. Zbuduj to makro na wierzchu 64-bitowego makra dodawania z części b.
Jak pokazano na rysunku 3.6, prostym sposobem wykonania 64-bitowego mnożenia jest wykonanie serii czterech 32-bitowych operacji mnożenia/shiftu/akumulacji, z których każda daje 64-bitowy wynik.
Rysunek 3.6. Mnożnik 8-bitowy zaimplementowany za pomocą mnożników 4-bitowych.
Na rysunku dwie 4-bitowe wartości A i B przechowujące wartości 1110 i 1410 są rozdzielone na dwie 2-bitowe porcje górną i dolną, nazwane A1, A0 oraz B1 i B0. Zakładając, że produkty są 4-bitowe, 8-bitowy produkt jest obliczany jako (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Aby zastosować to do 64-bitowego mnożenia, każda z dwóch 64-bitowych wartości musi być przechowywana w dwóch 32-bitowych rejestrach. Każde mnożenie generuje 64-bitowy wynik, co pozwala uzyskać 128-bitowy produkt końcowy.
d.
Zastosowując te makra, zaimplementuj 64-bitowy generator zbioru Mandelbrota i zmierz różnicę w jego wydajności.
e.
Zaimplementuj oba makra w języku asemblerowym inline i zmierz przyspieszenie działania generatora Mandelbrota w porównaniu z tym z części d.
.