МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ
(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)
Вычисление
Последовательности Фибоначчи на CUDA
Студент:Власов Д.Н.
Преподаватель:Семенов С.А.
Москва, 2012 год
Содержание
Постановка задачи ……………………………………………………………….3
Алгоритм………………………………………………………………………….4
Реализация ………………………………………………………………………..6
Сравнение результатов производительности CPU/GPU………………………10
- Характеристика вычислительной системы……………………………...10
- Средства разработки……………………………………………………...10
- Результаты………………………………………………………………...10
Выводы …………………………………………………………………………..12
Список литературы ……………………………………………………………..13
Список сокращений …………………………………………………………….13
Приложения……………………………………………………………………...13
Постановка задачи
Программа
- должна выполняться параллельно
Программа должна делать проверки на ошибки:
- Наличие аппаратной поддержки CUDA
- Открылся ли файл исходных данных
- Правилен ли формат данных?
Программа должна быть скомпилирована с опцией Release и запускаться на Windows 7 CUDA Toolkit 4.2
Программа должна быть скомпилирована CUDA 3.2, 4.2, OpenCl, OpenACC
Программа должна компилироваться. Для этого должен быть приложен vcproj для VS2008, VS2010 либо makefile + .bat
Написать программу для вычисления чисел Фибоначчи с распараллеливанием вычислений.
Алгоритм
Для вычисления чисел Фибоначчи используем следующую формулу:
F(n)=F(L) * F(n-L+1) + F(L-1) * F(n-L), где F(K) – число Фибоначчи с номером K.
Доказательство формулы:
F(n)=F(n-1) * F(n-2)=2* F(n-2) + F(n-3)=F(m+1) * F(n-m) + F(m) * F(n-m-1), где n>1, 0<=m<n
►Формула доказывается легко по индукции. При m = 0 формула верна:
F(n)=F(1) * F(n) + F(0) * F(n-1)=F(n)
Предположим, что формула верна при m = p:
F(n)=F(p+1) * F(n-p) + F(p) * F(n-p-1)
Докажем, что формула верна при m = p + 1:
F(n)=F(p+2)*F(n-p)+F(p+1)*F(n-p-2)=(F(p) +F(p+1))*F(n-p-1)+F(p+1)*F(n-p-2)= F(p)*F(n-p-1)+F(p+1) * F(n-p-1) + F(p+1) * F(n-p-2)=F(p)*F(n-p-1)+F(p+1)*(F(n-p-1)+F(n-p-2))=F(p+1)*F(n-p)+F(p)*F(n-p-1)
-получили такое же выражение, как и для случая m = p, т.е. при m = p + 1 формула остается верной. ◄
Если есть L+1 предыдущих и 2 заранее определенных числа: F(L-1) и F(L). Нам нужно вычислить L последующих элементов Фибоначчи, то L следующих чисел Фибоначчи можно вычислять параллельно. Для работы алгоритма остальные элементы последовательности Фибоначчи не нужны.
Выбор L:
- Если L<n (берем равное числу ядер (решателей)), n – нужное нам число Фибоначчи.
- Если L>=n, то либо берем меньшее L, либо считаем в одноядерном режиме.
Реализация
Требуется 4 двумерных массива размер L* MAXDigit элементов в каждом для вычисления любого числа n в режиме с распараллеливанием на L ядер. Два массива для алгоритма и два для длинной арифметики.
Для 32768 числа Фибоначчи MAXDigit~10^5.
Длинная арифметика:
Длинная арифметика реализована в виде массива чисел int, размером MAXDigit, где каждый элемент – это одна цифра числа(по системе счисления миллиард, т.е элемент массива содержит 10^9 цифр (основание системы счисления 10^9).
Цифры храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы, десятки, сотни, и т.д.).
Все операции выполняются до нулей, т. е простаивающие нули не складываются друг с другом.
Вычисление:
Вначале мы считаем первые L+1 чисел. Эти числа мы записываем в 1 массив M1.
У нас есть L ядер (решателей), в них мы считаем следующие L чисел, параллельно, используя данные из M1, и записываем результат расчета в M2. Копируем M1[L] в M1[0]. Копируем M2 в M1(записывая в M1 со сдвигом на 1 элемент).
И так повторяем, до тех пор, пока не рассчитаем число n.
Для проверки формулы:
F(100)=F(100) * F(1) + F(99) * F(0); F(0)=0; - не используется, т.к. n=L, а требуется n<L.
В качестве примера расчета n = 900 и для L=100:
F(900)=F(100) * F(801) + F(99) * F(800);
В качестве примера расчета n = 1000 и для L=100 ниже приведены формулы для расчета n= 901; 998; 999; 1000:
F(901)=F(100) * F(802) + F(99) * F(801);
F(998)=F(100) * F(899) + F(99) * F(898);
F(999)=F(100) * F(900) + F(99) * F(899);
F(1000)=F(100) * F(901) + F(99) * F(900);
Код ядра CUDA
__global__ void fibonacciKernel(myint *a, myint *b, myint N, int L, myint FL, myint FL1, myint *temp1, myint *temp2)
{
int idx = threadIdx.x;
for ( int i = L; i < N; i = i + L)
{
MultLongShort(a, (idx + 1), FL, MAXDigit, temp1, idx);
MultLongShort(a, idx, FL1, MAXDigit, temp2, idx);
AddLnum(temp1, idx, temp2, idx, MAXDigit, b, idx);
for(int j = 0; j < MAXDigit; j++){
a[0 + j] = a[MAXDigit * (L) + j];
}
for(int j = 0; j < MAXDigit; j++){
a[MAXDigit * (idx + 1) + j] = b[MAXDigit * idx + j];
}
}
}
Сравнение результатов производительности CPU/GPU
Характеристика вычислительной системы
Pentium Dual-Core T4400 2.2GHz, 4Gb(доступно 2,97Gb), Geforce g105m 256Mb.
Средства разработки
Widows7 32, VS2010, CUDA4.2.
Результаты
Для тестирования было написано еще 2 программы для CPU. Первая, вычисляет числа Фибоначчи в лоб по определению:
F(0)=0; F(1)=1; F(n)=F(n-1)+F(n-2).
Вторая, представляет собой мой алгоритм GPU в реализации для CPU(эмуляция 32 нитей CUDA, циклом). Длинная арифметика и функции работают схожим образом. Вычисления на CUDA’е происходили с распараллеливанием на 32/40/44 нити.
Результаты тестирования прикреплены в приложении (два последних графика).
Из результатов тестирования мы можем увидеть, что при увеличении числа процессов с 32 до 40(25%), видим прирост, что прирост составляет порядка 25%. При увеличении с 40 до 44 прирост составляет уже 3 секунды. При увеличении количества процессов вдвое мы можем получить 2-х кратную производительность.
Алгоритм ускоряет вычисление чисел Фибоначчи даже для одного вычислителя(CPU). Потому что, первая видеокарта работает на низкой частоте geforse g105m. Более мощная видеокарта geforse 630 с отрывом обгоняет процессор.
Правда, при увеличении на вычислителей, нам потребуется больше памяти.
Для каждого следующего вычислителя нам требуется хранить 4 больших числа.
Выводы
Реализованный алгоритм хорошо распараллеливается, на огромное количество нитей, бутылочным горлышком в этом случае является память.
При написании программы я столкнулся с очень быстрым ростом вычисляемых чисел. Для этого пришлось реализовать длинную арифметику, а она, как известно, работает, пока не кончится память. В моем случае я смог выделить только 10^5 элементов под число. Максимально в видеокартах пока только 6Gb, на CPU же гораздо больше, поэтому при вычислении с большими числами на GPU надо следить за тем, чтобы не было переполнения.
Список литературы
http://e-maxx.ru/algo/fibonacci_numbers
http://e-maxx.ru/algo/big_integer
Список сокращений
CPU - central processing unit (центральное процессорное устройство),
GPU - graphics processing unit (графический процессор)
CUDA - Compute Unified Device Architecture