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

Презентация:



Advertisements
Похожие презентации
ASSIGNMENT 4. Assignment 4.1 Задача – Аппроксимировать изображение набором полупрозрачных многоугольников.
Advertisements

ASSIGNMENT 2. Assignment 2.1 Масштабирование звука – Синусоида – противный «пищащий» звук – Частота дискретизации – Khz – 44Khz == 44 тысячи раз сигнал.
ASSIGNMENT Assignment 3.1 Растеризация на CUDA – Загрузить 3d модель (stanford bunny, dragon или buddha)stanford bunny, dragon или buddha – Преобразовать.
CUDA Assignment #1 Работа с глобальной и разделяемой памятью.
Задание бинарных деревьев с помощью массивов Обходы деревьев.
Вероятностные модели Построение информационной модели с использованием метода Монте-Карло.
СОРТИРОВКА ДЕРЕВОМ Выполнил: ст-т гр. ХХХХ.
Линейная функция (7класс) y = k x + b где k и b – заданные числа. Например, y = -2 x + 3, y=5 x, y = 3 x-7, y = 8.
Максимова СН Определение координат тела, находящегося в покое. Системы отсчета.
1 Метод Монте-КарлоМонте-Карло Метод приближенного нахождения площадей фигур А.Г. Гейн, и др. Информатика. Учебник для 8-9 классов. Москва, «Просвещение»,
Линейная функция Выполнено: Дроздовой А.Д. План Замечание. Информация на каждом слайде появляется после щелчка мыши. Щелкаем несколько раз.
Двоичные деревья поиска. Очередь с приоритетами Федор Царев Спецкурс «Олимпиадное программирование» Лекция , Санкт-Петербург, Гимназия.
ГОУ СОШ 504 г. Санкт-Петербург Учитель Миронова В.И.
Системы линейных уравнений. Обобщающий урок.. Определения: Линейным уравнением с двумя переменными называется уравнение вида ax+by=c, где х и у – переменные,
Метод используется для расчета корней уравнения вида f(x)=0. С помощью метода половинного деления всегда можно получить приближённые значения максимума.
Построение графиков функций.. Записать следующие выражения, учитывая, что значение х находится в ячейке А1 а) б) в) Ответы: а) (1 + А1)/(4*А1^2); б) –
Что такое функция? Функциональная зависимость, или функция, - это такая зависимость между двумя переменными, при которой каждому значению независимой переменной.
Основы информатики Лекция. Функции Заикин Олег Сергеевич
Исполнитель Чертежник. Работа в среде Алгоритмика 1 7 класс Яблоновская СОШ 3, Тахтамукайский район, Республика Адыгея Учитель информатики Нигматуллин.
Лекция 8 Красно-черные деревья План лекции 1.Определение красно-черного дерева и его высота. 2.Вращения 3.Вставка элемента, восстановление структуры дерева.
Транксрипт:

ASSIGNMENT 1

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

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

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; }; }; - Вычислить ограничивающий прямоугольник

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,

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, ???

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, ???

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

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

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

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

Вопросы