Skocz do: nawigacji, wyszukiwania

Opracowanie sposobów dystrybucji obliczeń wybranych algorytmów typu stencil w architekturach masywnie wielordzeniowych Intel Xeon Phi -Raport

Opracowanie sposobów dystrybucji obliczeń wybranych algorytmów typu stencil w architekturach masywnie wielordzeniowych Intel Xeon Phi

Kamil Halbiniak, Politechnika Częstochowska



Abstract
Streszczenie...


Algortmy typu stencil

Algorytmy typu stencil stanowią grupę obliczeń stosowaną w szerokiej gamie obliczeń naukowych. Znajdują one zastosowanie między innymi w obliczeniach numerycznych stosowanych do różnego rodzaju symulacji, w tym numerycznego modelowania pogody Są one również wykorzystywane w równaniach różniczkowych cząstkowych oraz obliczeniach elektromagnetycznych i wielu innych.


Algorytmy typu stencil definiowane są jako obliczenia polegające na wyznaczaniu elementów na podstawie elementu o tym samym, jak i sąsiednich indeksach w macierzy. Oznacza to, że wartość danego elementu macierzy wyjściowej obliczana jest na podstawie odpowiadającego mu elementu znajdującego się w macierzy bądź macierzach wejściowych oraz jego sąsiadów. Algorytmy te wykonują obliczenia przy użyciu kilku n-wymiarowych tablic (najczęściej dwu lub trój wymiarowych).


Mianem n-elementowego stencila określa się punkt oraz n-1 otaczających go sąsiadów. Zgodnie z ta definicją wyróżnia się wiele rodzai stencili, począwszy od prostych 3-punktowych, aż do bardzo złożonych 27-punktowych. Graficzna reprezentacja stencila została zaprezentowana na Rysunku 1.


Stencils.png
Rysunek 1. Graficzna reprezentacja stencila: a) 5-punktowy stencil, b) 7-punktowy stencil


Algorytmy typu stencil zazwyczaj cechuje niska wydajność obliczeń. Program, w ramach którego wykonywane są obliczenia typu stencili na ogół nie osiąga maksymalnej wydajności jaką oferuje dana architektura. Głównym ograniczeniem dla tego rodzaju obliczeń jest zbyt niska wydajność podsystemu pamięci, w którym przepustowość danych stanowi wąskie gardło dla danej platformy. Problem ten wynika z faktu, iż tego typu obliczenia wymagają wykonania większej liczby operacji na pamięci aniżeli operacji arytmetycznych. W związku z tym, dużą cześć czasu wykonywanej aplikacji jest przeznaczana na transfer danych. Uzyskanie wysokiej wydajności obliczeń wykonywanych z wykorzystaniem algorytmów typu stencil wymaga zastosowania wyszukanych metod optymalizacji często dedykowanych dla konkretnej platformy.