ASSIGNMENT 1. Assignment 1.1 Вычисление числа pi методом Монте-Карло: – Каждый поток генерирует n случайных точек (x,y) (x,y) в интервале (0, 1)x(0, 1) - презентация

1 ASSIGNMENT 1

2 Assignment 1.1 Вычисление числа pi методом Монте-Карло: – Каждый поток генерирует n случайных точек (x,y) (x,y) в интервале (0, 1)x(0, 1) – Считает сколько точек m лежит в единичном круге (m N) – Все потоки внутри блока складывают Mi = m Параллельная редукция – Один поток на блок записывает результат в глобальную память – Второй проход вычисляет общее количество M = Mi точек попавших в круг – Pi = (M / N) * 4, где N = n

3 Assignment 1.1 Генерация псевдослучайного числа – Задать seed, например, сгенерировав 1 случайное число на блок на cpu – След. код генерирует число в интервале [-1, 1] float noise(int x) { x = (x

4 Assignment 1.2 Построение K-D дерева для 2D точек – Генерация N случайных точек P[] (x, y) – Узел дерева: struct S_KdNode { union { float position; int count; }; union { int start; struct { int right : 30; int axis : 2; }; }; - Вычислить ограничивающий прямоугольник

5 Assignment 1.2 Построение дерева: продолжать пока в узле точек > K – Если точек K, добавить Лист в дерево.start := адрес первой точки в листе.count := кол-во точек в листе.axis := 3 // мнемонический код листа Выбрать след. ось (изначально X) – Отсортировать все точки поддерева вдоль текущей оси – Из отсортированного массива выбрать точку посередине X: 1, 7, 8, 2, 6, 3, 4, 5 X: 1, 7, 8, 2, 6, 3, 4,

6 Assignment 1.2 Добавить в дерево вершину S_KdNode: – Поле position := значение из отсортированного массива – Поле axis := индекс текущей оси (X == 0, Y == 1, Лист == 3) – В левое поддерево поместить все точки, лежащие левее выбранной плоскости, все остальные поместить в правое поддерево X: 1, 7, 8, 2, 6, 3, 4, 5 X: 1, 7, 8, 2, 6, 3, 4, Tree: (position, axis, right) - P[6].x, X, ??? Tree: (position, axis, right) - P[6].x, X, ???

7 Assignment 1.2 Повторить процедуру для левого поддерева, потом для правого – При рекурсивном вызове ось меняется X Y X Y … X: 1, 7, 8, 2, 6, 3, 4, 5 Y left: 8, 1, 2, 7 Y right: 6, 3, 4, 5 X: 1, 7, 8, 2, 6, 3, 4, 5 Y left: 8, 1, 2, 7 Y right: 6, 3, 4, Tree: (position, axis, right) - P[6].x, X, ??? - P[1].y, Y, ??? - P[3].y, Y, ??? Tree: (position, axis, right) - P[6].x, X, ??? - P[1].y, Y, ??? - P[3].y, Y, ???

8 Assignment 1.2 Дерево в памяти располагается так: – Левое поддерево всегда находится по следующему адресу после корня поддерева –.right в структуре указывает на правое поддерево – Необходимо полностью построить левое поддерево прежде, чем станет известно значение.right Root L L R R RR RL LL LR Root, L, LL, LR, R, RL, RR Расположение узлов в памяти:Вид дерева:

9

10 Общие правила по оформлению программ Если сдаете по – ДОЛЖЕН быть с темой CUDA ASSIGNEMENT 2011.N (N - номер задания)

11 Общие правила по оформлению прорамм – Программа должна делать проверки на ошибки: Наличие девайса? Выделилась память? И т.д. – Программа должна компилироваться CUDA Toolkit 3.2 Если писали на windows то vcproj для VS2005 / VS2008 либо (makefile +.bat) Если писали на *nix то make

12 Общие правила по оформлению программ Если вы используете любые другие инклюды кроме стандартных – не расчитывайте, что они прописаны на проверяющей машине. Пример того, чего не будет на машине: – cutil.h (требует установки CUDA SDK) Пример того, что будет на машине: – cudart.h (ставиться вместе с CUDA toolkit) – stdio.h (стандартная C библиотека) – thrust – cufft

13 Вопросы