Používání bloků
Pro maximální možné zvýšení rychlosti aplikace lze použít dělení do bloků.Dělení do bloků rozděluje vlákna do rovnoměrných obdélníkových podmnožin nazývaných bloky.Použití vhodné velikosti bloku a algoritmu, který bloky využívá, umožňuje získat ještě větší zrychlení kódu C++ AMP.Základní komponenty dělení do bloků jsou tyto:
Proměnné tile_static.Hlavní výhodou dělení do bloku je zvýšení výkonu díky přístupu k proměnným tile_static.Přístup k datům v paměti tile_static může být výrazně rychlejší než přístup k datům v globálním prostoru (objekty array nebo array_view).Instance proměnné tile_static je vytvořena pro každou dlaždici a všechna vlákna v dlaždici mají k této proměnné přístup.V typickém algoritmu využívajícím bloky jsou data jednou zkopírována do paměti tile_static z globální paměti a poté je k nim mnohokrát přistupováno v paměti tile_static.
tile_barrier::wait – metoda.Volání funkce tile_barrier::wait pozastaví provádění aktuálního vlákna, dokud všechna vlákna ve stejném bloku nedosáhnou k volání funkce tile_barrier::wait.Nelze zaručit pořadí, ve kterém budou vlákna spuštěna, pouze že žádné vlákno v bloku nebude provádět příkazy po volání funkce tile_barrier::wait, dokud všechna vlákna nedosáhnout tohoto volání.To znamená, že pomocí metody tile_barrier::wait lze provádět úkoly spíše blok po bloku než vlákno po vlákně.Typický algoritmus využívající dlaždice má kód inicializující paměť tile_static pro celou dlaždici následovanou voláním funkce tile_barrer::wait.Kód následující tile_barrier::wait obsahuje výpočty, které vyžadují přístup ke všem hodnotám tile_static.
Místní a globální indexování.Lze přistoupit k indexu vlákna relativnímu k celým objektům array_view nebo array a indexu relativnímu k bloku.Použití místního indexu může vézt ke snazšímu čtení a ladění kódu.Obvykle je místní indexování používáno pro přístup k proměnným tile_static a globální indexování pro přístup k proměnným array a array_view.
tiled_extent – třída a tiled_index – třída.Při volání algoritmu parallel_for_each je používán místo objektu extent objekt tiled_extent.Při volání algoritmu parallel_for_each je používán místo objektu index objekt tiled_index.
Pro využití dělení do bloku musí algoritmus rozdělit výpočetní doménu do bloků a poté pro rychlejší přístup data bloku zkopírovat do proměnných tile_static.
Příklad globálních, blokových a místních indexů
Následující diagram reprezentuje matici dat velikosti 8x9 uspořádanou do bloků velikosti 2x3.
.png "matice 8 9 rozdělena na 2 3 dlaždice")
Následující příklad ukazuje globální, blokové a místní indexy této blokové matice.Je vytvořen objekt array_view za použití prvků typu Description.Description udržuje globální, blokové a místní indexy prvků matice.Kód ve volání algoritmu parallel_for_each nastaví hodnotu globálního, blokového a místního indexu každého prvku.Výstup zobrazuje hodnoty struktur Description.
#include <iostream>
#include <iomanip>
#include <Windows.h>
#include <amp.h>
using namespace concurrency;
const int ROWS = 8;
const int COLS = 9;
// tileRow and tileColumn specify the tile that each thread is in.
// globalRow and globalColumn specify the location of the thread in the array_view.
// localRow and localColumn specify the location of the thread relative to the tile.
struct Description {
int value;
int tileRow;
int tileColumn;
int globalRow;
int globalColumn;
int localRow;
int localColumn;
};
// A helper function for formatting the output.
void SetConsoleColor(int color) {
int colorValue = (color == 0) ? 4 : 2;
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), colorValue);
}
// A helper function for formatting the output.
void SetConsoleSize(int height, int width) {
COORD coord; coord.X = width; coord.Y = height;
SetConsoleScreenBufferSize(GetStdHandle(STD_OUTPUT_HANDLE), coord);
SMALL_RECT* rect = new SMALL_RECT();
rect->Left = 0; rect->Top = 0; rect->Right = width; rect->Bottom = height;
SetConsoleWindowInfo(GetStdHandle(STD_OUTPUT_HANDLE), true, rect);
}
// This method creates an 8x9 matrix of Description structures. In the call to parallel_for_each, the structure is updated
// with tile, global, and local indices.
void TilingDescription() {
// Create 72 (8x9) Description structures.
std::vector<Description> descs;
for (int i = 0; i < ROWS * COLS; i++) {
Description d = {i, 0, 0, 0, 0, 0, 0};
descs.push_back(d);
}
// Create an array_view from the Description structures.
extent<2> matrix(ROWS, COLS);
array_view<Description, 2> descriptions(matrix, descs);
// Update each Description with the tile, global, and local indices.
parallel_for_each(descriptions.extent.tile< 2, 3>(),
[=] (tiled_index< 2, 3> t_idx) restrict(amp)
{
descriptions[t_idx].globalRow = t_idx.global[0];
descriptions[t_idx].globalColumn = t_idx.global[1];
descriptions[t_idx].tileRow = t_idx.tile[0];
descriptions[t_idx].tileColumn = t_idx.tile[1];
descriptions[t_idx].localRow = t_idx.local[0];
descriptions[t_idx].localColumn= t_idx.local[1];
});
// Print out the Description structure for each element in the matrix.
// Tiles are displayed in red and green to distinguish them from each other.
SetConsoleSize(100, 150);
for (int row = 0; row < ROWS; row++) {
for (int column = 0; column < COLS; column++) {
SetConsoleColor((descriptions(row, column).tileRow + descriptions(row, column).tileColumn) % 2);
std::cout << "Value: " << std::setw(2) << descriptions(row, column).value << " ";
}
std::cout << "\n";
for (int column = 0; column < COLS; column++) {
SetConsoleColor((descriptions(row, column).tileRow + descriptions(row, column).tileColumn) % 2);
std::cout << "Tile: " << "(" << descriptions(row, column).tileRow << "," << descriptions(row, column).tileColumn << ") ";
}
std::cout << "\n";
for (int column = 0; column < COLS; column++) {
SetConsoleColor((descriptions(row, column).tileRow + descriptions(row, column).tileColumn) % 2);
std::cout << "Global: " << "(" << descriptions(row, column).globalRow << "," << descriptions(row, column).globalColumn << ") ";
}
std::cout << "\n";
for (int column = 0; column < COLS; column++) {
SetConsoleColor((descriptions(row, column).tileRow + descriptions(row, column).tileColumn) % 2);
std::cout << "Local: " << "(" << descriptions(row, column).localRow << "," << descriptions(row, column).localColumn << ") ";
}
std::cout << "\n";
std::cout << "\n";
}
}
void main() {
TilingDescription();
char wait;
std::cin >> wait;
}
Hlavní práce ukázky spočívá v definici objektu array_view a ve volání algoritmu parallel_for_each.
Vektor struktur Description je zkopírován do objektu array_view o velikosti 8x9.
Metoda parallel_for_each je volána s objektem tiled_extent jako výpočetní doménou.Objekt tiled_extent je vytvořen voláním metody extent::tile() proměnné descriptions.Typové parametry volání funkce extent::tile(), <2,3> určují, že budou vytvořeny bloky velikosti 2x3.Matice velikosti 8x9 je tedy rozdělena do 12 bloků, čtyři řádky a tři sloupce.
Metoda parallel_for_each je volána za použití objektu tiled_index<2,3> (t_idx) představujícího index.Typové parametry indexu (t_idx) musí odpovídat typovým parametrům výpočetní domény (descriptions.extent.tile< 2, 3>()).
Při spuštění každého vlákna vrací index t_idx informace o tom, ve kterém bloku se vlákno nachází (vlastnost tiled_index::tile), a o umístění vlákna v bloku (vlastnost tiled_index::local).
Synchronizace bloků – tile_static a tile_barrier::wait
Předchozí příklad ilustruje rozložení bloků a indexů, ale sám o sobě není příliš užitečný. Dělení do bloků se stává užitečným, jsou-li bloky nedílnou součástí algoritmu a využívají proměnných tile_static.Jelikož všechna vlákna bloku mají přístup k proměnným tile_static, volání funkce tile_barrier::wait se používají k synchronizaci přístupu k těmto proměnným tile_static.Ačkoli všechna vlákna bloku mají přístup k proměnným tile_static, není nikterak zaručeno pořadí, v němž jsou vlákna v bloku spuštěna.Následující příklad ukazuje, jak použít proměnné tile_static a metodu tile_barrier::wait pro výpočet průměrné hodnoty každého bloku.Zde jsou klíčové údaje pro pochopení tohoto příkladu:
Objekt rawData je uložen v matici velikosti 8x8.
Velikost bloku je 2x2.To vytvoří mřížku bloků velikosti 4x4 a průměry mohou být uloženy do matice velikosti 4x4 použitím objektu array.Existuje pouze omezený počet typů, které lze zachytit odkazem ve funkci určené pro AMP.Třída array je jedním z nich.
Velikost matice a velikost vzorku jsou definovány pomocí příkazů #define, protože typové parametry objektů array, array_view, extent a tiled_index musí být konstantní hodnoty.Lze také použít deklarace const int static.Další výhodou je, že je jednoduché změnit velikost vzorku tak, aby počítal průměr nad bloky velikosti 4x4.
Pro každou dlaždici je deklarováno pole hodnot tile_static s plovoucí desetinnou čárkou o velikosti 2x2.Ačkoli je deklarace pro každé vlákno v cestě kódu, je pro každý blok v matici vytvořeno pouze jedno pole.
Jeden z řádků kódu slouží ke kopírování hodnot v každém bloku do pole tile_static.Pro každé vlákno platí, že po zkopírování hodnoty do pole je spuštění vlákna pozastaveno kvůli volání funkce tile_barrier::wait.
Jakmile všechna vlákna bloku dosáhnou této bariéry, lze vypočítat průměr.Jelikož se kód spouští v každém vlákně, je zde příkaz if zajišťující výpočet průměru pouze v jednom vlákně.Průměr je uložen v proměnné averages.Bariéra v podstatě představuje konstrukci, která řídí výpočty po blocích obdobným způsobem, jako by se dala použít smyčka for.
Data v proměnné averages musí být zkopírována zpět k hostiteli, protože jde o objekt array.Tento příklad používá operátor převodu vektoru.
V úplném příkladu lze změnit hodnotu SAMPLESIZE na 4 a kód se provede správně bez jakýchkoliv jiných změn.
#include <iostream>
#include <amp.h>
using namespace concurrency;
#define SAMPLESIZE 2
#define MATRIXSIZE 8
void SamplingExample() {
// Create data and array_view for the matrix.
std::vector<float> rawData;
for (int i = 0; i < MATRIXSIZE * MATRIXSIZE; i++) {
rawData.push_back((float)i);
}
extent<2> dataExtent(MATRIXSIZE, MATRIXSIZE);
array_view<float, 2> matrix(dataExtent, rawData);
// Create the array for the averages.
// There is one element in the output for each tile in the data.
std::vector<float> outputData;
int outputSize = MATRIXSIZE / SAMPLESIZE;
for (int j = 0; j < outputSize * outputSize; j++) {
outputData.push_back((float)0);
}
extent<2> outputExtent(MATRIXSIZE / SAMPLESIZE, MATRIXSIZE / SAMPLESIZE);
array<float, 2> averages(outputExtent, outputData.begin(), outputData.end());
// Use tiles that are SAMPLESIZE x SAMPLESIZE.
// Find the average of the values in each tile.
// The only reference-type variable you can pass into the parallel_for_each call
// is a concurrency::array.
parallel_for_each(matrix.extent.tile<SAMPLESIZE, SAMPLESIZE>(),
[=, &averages] (tiled_index<SAMPLESIZE, SAMPLESIZE> t_idx) restrict(amp)
{
// Copy the values of the tile into a tile-sized array.
tile_static float tileValues[SAMPLESIZE][SAMPLESIZE];
tileValues[t_idx.local[0]][t_idx.local[1]] = matrix[t_idx];
// Wait for the tile-sized array to load before you calculate the average.
t_idx.barrier.wait();
// If you remove the if statement, then the calculation executes for every
// thread in the tile, and makes the same assignment to averages each time.
if (t_idx.local[0] == 0 && t_idx.local[1] == 0) {
for (int trow = 0; trow < SAMPLESIZE; trow++) {
for (int tcol = 0; tcol < SAMPLESIZE; tcol++) {
averages(t_idx.tile[0],t_idx.tile[1]) += tileValues[trow][tcol];
}
}
averages(t_idx.tile[0],t_idx.tile[1]) /= (float) (SAMPLESIZE * SAMPLESIZE);
}
});
// Print out the results.
// You cannot access the values in averages directly. You must copy them
// back to a CPU variable.
outputData = averages;
for (int row = 0; row < outputSize; row++) {
for (int col = 0; col < outputSize; col++) {
std::cout << outputData[row*outputSize + col] << " ";
}
std::cout << "\n";
}
// Output for SAMPLESSIZE = 2 is:
// 4.5 6.5 8.5 10.5
// 20.5 22.5 24.5 26.5
// 36.5 38.5 40.5 42.5
// 52.5 54.5 56.5 58.5
// Output for SAMPLESIZE = 4 is:
// 13.5 17.5
// 45.5 49.5
}
int main() {
SamplingExample();
}
Konflikty časování
Může být lákavé vytvořit proměnnou tile_static pojmenovanou total a zvyšovat ji pro každé vlákno následujícím způsobem:
// Do not do this.
tile_static float total;
total += matrix[t_idx];
t_idx.barrier.wait();
averages(t_idx.tile[0],t_idx.tile[1]) /= (float) (SAMPLESIZE * SAMPLESIZE);
Prvním problémem tohoto přístupu je, že proměnné tile_static nemohou mít inicializátory.Druhý problém je, že u přiřazování k proměnné total dochází ke konfliktům časování, protože všechna vlákna bloku mají k této proměnné přístup bez určitého pořadí.Lze naprogramovat algoritmus tak, aby umožnil přístup k hodnotě celkem u každé bariéry pouze jednomu vláknu, jak je ukázáno dále.Toto řešení však není rozšiřitelné.
// Do not do this.
tile_static float total;
if (t_idx.local[0] == 0 && t_idx.local[1] == 0) {
total = matrix[t_idx];
}
t_idx.barrier.wait();
if (t_idx.local[0] == 0 && t_idx.local[1] == 1) {
total += matrix[t_idx];
}
t_idx.barrier.wait();
// etc.
Ohrazení paměti
Existují dva typy přístupů k paměti, které musí být synchronizovány – přístup ke globální paměti a přístup k paměti tile_static.Objekt concurrency::array alokuje pouze globální paměť.Objekt concurrency::array_view může odkazovat do globální paměti, do paměti tile_static nebo do obou v závislosti na způsobu jeho vytvoření. Existují dva druhy paměti, které je zapotřebí synchronizovat:
globální paměť
tile_static
Ohrazení paměti zajišťuje, že jsou přístupy k paměti dostupné ostatním vláknům v bloku vláken a že přístupy k paměti jsou provedeny ve shodě s pořadím programu.Aby toto bylo zajištěno, kompilátory a procesory nemění pořadí čtení a zápisu napříč ohrazením.V knihovně C++ AMP je ohrazení paměti vytvořeno voláním jedné z těchto metod:
tile_barrier::wait – metoda: Vytvoří ohrazení kolem globální paměti i paměti tile_static.
tile_barrier::wait_with_all_memory_fence – metoda: Vytvoří ohrazení kolem globální paměti i paměti tile_static.
tile_barrier::wait_with_global_memory_fence – metoda: Vytvoří ohrazení pouze kolem globální paměti.
tile_barrier::wait_with_tile_static_memory_fence – metoda: Vytvoří ohrazení pouze kolem paměti tile_static.
Volání určitého požadovaného ohrazení může zvýšit výkon aplikace.Typ bariéry ovlivňuje způsob, jakým kompilátor a hardware mění pořadí příkazů.Například ohrazení globální paměti platí pouze pro přístupy ke globální paměti, tudíž kompilátor a hardware mohou změnit pořadí čtení a zápisů proměnných tile_static na obou stranách ohrazení.
V následujícím příkladu bariéra synchronizuje zápisy do proměnné tileValues, tile_static.V tomto příkladu je namísto funkce tile_barrier::wait volána funkce tile_barrier::wait_with_tile_static_memory_fence.
// Using a tile_static memory fence.
parallel_for_each(matrix.extent.tile<SAMPLESIZE, SAMPLESIZE>(),
[=, &averages] (tiled_index<SAMPLESIZE, SAMPLESIZE> t_idx) restrict(amp)
{
// Copy the values of the tile into a tile-sized array.
tile_static float tileValues[SAMPLESIZE][SAMPLESIZE];
tileValues[t_idx.local[0]][t_idx.local[1]] = matrix[t_idx];
// Wait for the tile-sized array to load before calculating the average.
t_idx.barrier.wait_with_tile_static_memory_fence();
// If you remove the if statement, then the calculation executes for every
// thread in the tile, and makes the same assignment to averages each time.
if (t_idx.local[0] == 0 && t_idx.local[1] == 0) {
for (int trow = 0; trow < SAMPLESIZE; trow++) {
for (int tcol = 0; tcol < SAMPLESIZE; tcol++) {
averages(t_idx.tile[0],t_idx.tile[1]) += tileValues[trow][tcol];
}
}
averages(t_idx.tile[0],t_idx.tile[1]) /= (float) (SAMPLESIZE * SAMPLESIZE);
}
});