Технология СUDA

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования РФ

Санкт-Петербургский государственный электротехнический

университет «ЛЭТИ»

Кафедра САААПР

Пояснительная записка к курсовой работе

по учебной дисциплине «ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ»

Выполнили: Толстихин А.И.

Иванов В.В.

Группа: 8302

Факультет: КТИ

Санкт-Петербург 2012



Оглавление

графический вычисление архитектура программа

Основные термины

GPU

Отличия от СPU

Общие данные СUDA

Преимущества

Недостатки

Начало работы с CUDA

Создание CUDA проекта

Экспериментальная машина

Код программы суммирование вектора GPU

Технический вывод программы

Код программы суммирование вектора CPU

Код программы расчёта БПФ с использованием библиотеки jCuda

Технический вывод программы

Код программы расчёта числа PI

Технический вывод программы

Расчёт на CPU

Выводы

Приложение 1

Теоретическая часть

Последовательный алгоритм

Параллельный алгоритм

Алгоритм

Вычислительный процессор

Результаты эксперимента

ПРИЛОЖЕНИЕ 1.1

ПРИЛОЖЕНИЕ 1.2

Скриншоты программ

Инструкция пользователя

Программа onethread.exe

Программа multithread.exe

Выводы по лабораторной работе



Основные термины

Тред (Thread) - единица выполнения программы. Имеет свой уникальный идентификатор внутри блока.

Варп (Warp) - 32 последовательно идущих треда, выполняется физически одновременно.

Блок (Block) - объединение потоков, которое выполняется целиком на одном SM. Имеет свой уникальный идентификатор внутри грида.

Грид (Grid) - объединение блоков, которые выполняются на одном устройстве.

Ядро (Kernel) - Параллельная часть алгоритма, выполняется на гриде.

Устройство (Device) - видеокарта, являющаяся сопроцессором к центральному процессору (хосту).

Хост (Host) - центральный процессор, который управляет выполнением программы.



GPU

Графический процессор (англ. graphics processing unit, GPU) -- отдельное устройство персонального компьютера или игровой приставки, выполняющее графический рендеринг. Современные графические процессоры очень эффективно обрабатывают и отображают компьютерную графику. Благодаря специализированной конвейерной архитектуре они намного эффективнее в обработке графической информации, чем типичный центральный процессор. Графический процессор в современных видеоадаптерах применяется в качестве ускорителя трёхмерной графики.

Высокая вычислительная мощность GPU объясняется особенностями архитектуры. Если современные CPU содержат несколько ядер (на большинстве современных систем от 2 до 6, по состоянию на 2012 г.), графический процессор изначально создавался как многоядерная структура, в которой количество ядер может достигать сотен. Разница в архитектуре обусловливает и разницу в принципах работы. Если архитектура CPU предполагает последовательную обработку информации, то GPU исторически предназначался для обработки компьютерной графики, поэтому рассчитан на массивно параллельные вычисления.

Отличия от СPU

Ядра CPU созданы для исполнения одного потока последовательных инструкций с максимальной производительностью, а GPU используются для быстрого исполнения большого числа параллельно выполняемых потоков инструкций. CPU оптимизированы для достижения максимальной производительности отдельного алгоритма, инструкций. У видеочипов работа распараллелена изначально. На входе принимаются полигоны, проводятся необходимые операции, и на выходе получаем пиксели. При чем обработка полигонов никак не связана между собой.

Также отличие GPU от CPU проявляется и в принципе доступа к памяти. То есть, в GPU при записи пикселя в буфер через некоторое время будет записан и соседний с ним пиксель. В следствии такой организации памяти, чипу просто не нужна кэш-память большого размера (до 256 кБ).

Да и сама по себе работа с памятью у GPU и CPU несколько отличается. Так, не все центральные процессоры имеют встроенные контроллеры памяти, а у всех GPU обычно есть по несколько контроллеров, вплоть до восьми 64-битных. Кроме того, на видеокартах применяется более быстрая память, и в результате видеочипам доступна в разы большая пропускная способность памяти.

Также есть и отличия в кэшировании. CPU используют кэш для увеличения производительности за счёт снижения задержек доступа к памяти, а GPU используют кэш для увеличения полосы пропускания. CPU снижают задержки доступа к памяти при помощи кэш-памяти большого размера, а также предсказания ветвлений кода. Эти аппаратные части занимают большую часть площади чипа и потребляют много энергии. Видеочипы обходят проблему задержек доступа к памяти при помощи одновременного исполнения тысяч потоков -- в то время, когда один из потоков ожидает данных из памяти, видеочип может выполнять вычисления другого потока без ожидания и задержек.

В итоге, основой для эффективного использования мощи GPU в неграфических расчётах является распараллеливание алгоритмов на сотни исполнительных блоков, имеющихся в видеочипах.

CUDA -- технология GPGPU, позволяющая реализовывать на С алгоритмы, выполнимые на графических процессорах ускорителей GeForce восьмого поколения и старше. Технология CUDA разработана компанией nVidia. Проще говоря, графическая подсистема компьютера с поддержкой CUDA может быть использована, как вычислительная.

Close To Metal (CTM) - технология GPGPU, использующая низкоуровневое программирование на графических процессорах ATI (AMD Graphics Products Group). CTM является виртуальной машиной, исполняющей ассемблерный код, в то время как CUDA - своеобразное расширение С. Две эти платформы несовместимы между собой.



Общие данные СUDA

CUDA (англ. Compute Unified Device Architecture) -- программно-аппаратная архитектура параллельных вычислений, которая позволяет существенно увеличить вычислительную производительность благодаря использованию графических процессоров фирмы NVIDIA.

CUDA SDK позволяет программистам реализовывать на специальном упрощённом диалекте языка программирования Си алгоритмы, выполнимые на графических процессорах NVIDIA, и включать специальные функции в текст программы на Cи. Архитектура CUDA даёт разработчику возможность по своему усмотрению организовывать доступ к набору инструкций графического ускорителя и управлять его памятью.

Вычислительную конфигурацию процессов можно представить так:

Рисунок 1



Преимущества

По сравнению с традиционным подходом к организации вычислений общего назначения посредством возможностей графических API, у архитектуры CUDA отмечают следующие преимущества в этой области:

Интерфейс программирования приложений CUDA (CUDA API) основан на стандартном языке программирования Си с некоторыми ограничениями. По мнению разработчиков, это должно упростить и сгладить процесс изучения архитектуры CUDA[2]

Разделяемая между потоками память (shared memory) размером в 16 Кб может быть использована под организованный пользователем кэш с более широкой полосой пропускания, чем при выборке из обычных текстур

Более эффективные транзакции между памятью центрального процессора и видеопамятью

Полная аппаратная поддержка целочисленных и побитовых операций

Поддержка компиляции GPU кода средствами открытого LLVM[3]

Недостатки

Все функции, выполнимые на устройстве, не поддерживают рекурсии (в версии CUDA Toolkit 3.1 поддерживает указатели и рекурсию) и имеют некоторые другие ограничения

Начало работы с CUDA

Что потребуется для работы:

1. Видеокарта из серии nVidia GeForce 8xxx/9xxx или более современная

2. CUDA Toolkit v.2.1

3. CUDA SDK v.2.1

4. Visual Studio 2008

5. CUDA Visual Studio Wizard

Создание CUDA проекта

После установки всего необходимого в VS появиться новый вид проекта для С++ с названием CU-DA WinApp, это именно то, что нам надо. В данном типе проекта доступны дополнительные на-стройки для CUDA, позволяющие настроить параметры компиляции под GPU, например версию Compute Capability в зависимости от типа GPU и т.д.

Обычно я создаю чистый проект (Empty Project), так как Precompiled Headers навряд ли пригодиться для CUDA.

Важно отметить, как собирается CUDA приложение. Файлы с расширением *.cpp обрабатываются компилятором MS C++ (cl.exe), а файлы c расширением *.cu компилятором CUDA (nvcc.exe), который в свою очередь определяет, какой код будет работать на GPU, а какой на CPU. Код из *.cu, работающий на CPU, передается на компиляцию MS C++, эту особенность удобно использовать для написания динамических библиотек, которые будут экспортировать функции, использующие для расчетов GPU.

Далее привожу листинг простой программы на CUDA, который выводит на экран информацию об аппаратных возможностях GPU.

Экспериментальная машина

Мерой производительности вычислительных систем, которая показывает количество операций с плавающей точкой выполняемых за секунду является единица, называемая FLOPS. Ниже в таблицах можно увидеть на сколько различается теоретическая производительность современных видеокарт и современных процессоров при выполнении операций с плавающей точкой.

Машина, на которой я буду производить исследование имеет следующую конфигурацию

Intel Core i7-950 3.03 ГГц

6Gb DDR-3

GeForce GTX 280

Видеокарты
Модель	Гигафлопс
GeForce GTX 690	5622
GeForce GTX 580	1581.056
GeForce GTX 480	1344.96
GeForce GTX 280	933.120
GeForce 9800 GTX	648
GeForce 8800 GTS 640mb	346

Таблица 1. Сравнение производительности видеокарт

Процессоры
Модель	Гигафлопс
AMD Phenom II X6 1100T Black Edition 3.3 ГГц	60.1
Intel Core i7-950 3.03 ГГц	53.28
Intel Core 2 Quad Q8300 2.5 ГГц	40
AMD AMD ATHLON II X4 645 3.1 ГГц	38.44
Intel Core 2 Duo 2.4 ГГц	19.02
AMD Athlon 64 X2 4200+ 2.2 ГГц	13.02

Таблица 2. Сравнение производительности процессоров

Как видно из таблиц, теоретическая производительность моей видеокарты в 17 раз превосходит производительность моего процессора.

Для реализации своей программы я использовал Visual Studio 2010, и написал консольное приложение.

Код программы суммирование вектора GPU

#ifndef _COMMON_H

#define _COMMON_H

#define VECTOR_SIZE 8192

#define BLOCK_SIZE 512

#define BLOCKS (VECTOR_SIZE / BLOCK_SIZE)

extern "C" void reductionGPU(int *d_Dst, int *d_Src);

#endif

#include <cutil_inline.h>

#include "common.h"

__global__ void reductionKernel(int *d_Dst, int *d_Src)

{

__shared__ int data[BLOCK_SIZE];

int tid = threadIdx.x;

int idx = blockIdx.x * blockDim.x + threadIdx.x;

// Копируем из глобальной в локальную блоками

data[tid] = (idx < VECTOR_SIZE) ? d_Src[idx] : 0;

// Ждём пока каждый поток в блоке скопирует данные

__syncthreads ();

// Суммирование в паралели

for ( int s = blockDim.x / 2; s > 0; s >>= 1 )

{

if ( tid < s )

data[tid] += data[tid + s];

__syncthreads ();

}

// Первый поток в блоке записывает результат суммирования

if(tid == 0)

d_Dst[blockIdx.x] = data[0];

}

extern "C" void reductionGPU(int *d_Dst, int *d_Src)

{

reductionKernel<<<BLOCKS, BLOCK_SIZE>>>(d_Dst, d_Src);

cutilCheckMsg("convolutionRowsKernel() execution failed\n");

}

#include <stdlib.h>

#include <iostream>

#include <algorithm>

#include <iterator>

#include <string.h>

#include <cutil_inline.h>

#include "common.h"

////////////////////////////////////////////////////////////////////////////////

// Main program

////////////////////////////////////////////////////////////////////////////////

int main(int argc, char **argv)

{

//Use command-line specified CUDA device, otherwise use device with highest Gflops/s

if ( cutCheckCmdLineFlag(argc, (const char **)argv, "device") )

cutilDeviceInit(argc, argv);

else

cudaSetDevice( cutGetMaxGflopsDeviceId() );

int *d_Input, *d_Output;

int* h_Input = new int[VECTOR_SIZE];

int* h_Output = new int[BLOCKS];

for(int i = 0; i < VECTOR_SIZE; ++i)

{

h_Input[i] = 1;

}

std::cout << "Size of data: " << VECTOR_SIZE << "\n";

std::cout << "Blocks: " << BLOCKS << "\n";

std::cout << "Allocating and initializing CUDA arrays...\n";

cutilSafeCall( cudaMalloc((void **)&d_Input, VECTOR_SIZE * sizeof(int)) );

cutilSafeCall( cudaMalloc((void **)&d_Output, BLOCKS * sizeof(int)) );

cutilSafeCall( cudaMemset(d_Output, 0x00, BLOCKS * sizeof(int)) );

cutilSafeCall( cudaMemcpy(d_Input, h_Input, VECTOR_SIZE * sizeof(int), cudaMemcpyHostToDevice) );

std::cout << "Running GPU reduction...\n";

cudaThreadSynchronize();

reductionGPU(d_Output, d_Input);

cudaThreadSynchronize();

std::cout << "Reading back GPU results...\n";

cutilSafeCall( cudaMemcpy(h_Output, d_Output, BLOCKS * sizeof(int), cudaMemcpyDeviceToHost) );

std::cout << "Results: \n";

std::copy(h_Output, h_Output + BLOCKS, std::ostream_iterator<int>(std::cout,", "));

cutilSafeCall( cudaFree(d_Input) );

cutilSafeCall( cudaFree(d_Output) );

delete[] h_Input;

delete[] h_Output;

cudaThreadExit();

cutilExit(argc, argv);}

Технический вывод программы

Size of data: 8192

Blocks: 16

Allocating and initializing CUDA arrays...

Running GPU reduction...

Reading back GPU results...

Results:

512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512

Press ENTER to exit...

Код программы суммирование вектора CPU

#include <iostream>

#include <ctime>

#include <vector>

#include <algorithm>

#include <iterator>

void show (const std::vector <float> &);

int main (void)

{

const int SIZE=5;

std::vector <float> A;

std::vector <float> B;

std::vector <float> REZULT (SIZE);

float tmp;

// fill vector A

for (int i=0; i<SIZE; i++) {

std::cout << "A[" << i <<"]: ";

std::cin >> tmp;

A.push_back (tmp); }

// fill vector B

for (int i=0; i<SIZE; i++) {

std::cout << "B[" << i <<"]: ";

std::cin >> tmp;

B.push_back (tmp); }

//

std::vector <float> :: iterator A_=A.begin();

std::vector <float> :: iterator B_=B.begin();

std::vector <float> :: iterator REZULT_=REZULT.begin();

for (REZULT_; REZULT_!=REZULT.end(); REZULT_++, A_++, B_++)

*(REZULT_)=*(A_) + *(B_);

time = clock() - time;

// output

std::cout << "Vector A: ";

show (A);

std::cout << "Vector B: ";

show (B);

std::cout << "Vector REZULT: ";

show (REZULT);

system ("pause");

return 0;

}

void show (const std::vector <float> &vec)

{

std::copy (vec.begin(), vec.end(), std::ostream_iterator <int> (std::cout, " "));

std::cout << std::endl;

}

Код программы расчёта БПФ с использованием библиотеки jCuda

public class JCufftDemo {

public static void main(String[] args) {

double[] fftResults;

int dataSize = 1<<23;

System.out.println("Генерация входных данных размером "+dataSize+" значений...\n");

float[] inputData = createRandomData(dataSize)

System.out.println("1D БПФ с использованием apache commons math...");

fftResults = commonsTransform(floatDataToDoubleData(inputData.clone()));

printSomeValues(fftResults);

System.out.println();

System.out.println("1D БПФ JCufft (данные в оперативной памяти)...");

fftResults = jcudaTransformHostMemory(inputData.clone());

printSomeValues(fftResults);

System.out.println();

System.out.println("1D БПФ JCufft (данные в памяти видеокарты)...");

fftResults = jcudaTransformDeviceMemory(inputData.clone());

printSomeValues(fftResults);

}

/**

* Генерирует массив случайных чисел

*

* @param dataSize - размер генерируемого массива

* @return массив случайных чисел

*/

public static float[] createRandomData(int dataSize){

Random random = new Random();

float data[] = new float[dataSize];

for (int i = 0; i < dataSize; i++)

data[i] = random.nextFloat();

return data;

}

/**

* Конвертирует массив значений типа float в массив значений double

*

* @param data - массив который нужно конвертировать

* @return - сконвертированный массив

*/

public static double[] floatDataToDoubleData(float[] data){

double[] doubleData = new double[data.length];

for(int i=0; i < data.length; i++) doubleData[i] = data[i];

return doubleData;

}

/**

* Выполняет БПФ массива значений с помощью CUDA, осуществляя

* операции с данными в оперативной памяти

*

* @param inputData - массив входных значений

* @return массив с результатами БПФ

*/

public static double[] jcudaTransformHostMemory(float[] inputData){

float[] fftResults = new float[inputData.length + 2];

// создание плана

cufftHandle plan = new cufftHandle();

JCufft.cufftPlan1d(plan, inputData.length, cufftType.CUFFT_R2C, 1);

// выполнение БПФ

long timeStart = new Date().getTime();

JCufft.cufftExecR2C(plan, inputData, fftResults);

System.out.println("Время преобразования: " + (new Date().getTime() - timeStart)/1000.0+" сек");

// уничтожение плана

JCufft.cufftDestroy(plan);

return cudaComplexToDouble(fftResults);

}

/**

* Выполняет БПФ массива значений с помощью CUDA, осуществляя

* операции с данными в памяти видеокарты

*

* @param inputData - массив входных значений

* @return массив с результатами БПФ

*/

public static double[] jcudaTransformDeviceMemory(float[] inputData){

float[] fftResults = new float[inputData.length + 2];

// указатель на устройство

Pointer deviceDataIn = new Pointer();

// выделение памяти на видеокарте для входных данных

JCuda.cudaMalloc(deviceDataIn, inputData.length * 4);

// копирование входных данных в память видеокарты

JCuda.cudaMemcpy(deviceDataIn, Pointer.to(inputData), inputData.length * 4,

cudaMemcpyKind.cudaMemcpyHostToDevice);

Pointer deviceDataOut = new Pointer();

// выделение памяти на видеокарте для результатов преобразования

JCuda.cudaMalloc(deviceDataOut, fftResults.length * 4);

// создание плана

cufftHandle plan = new cufftHandle();

JCufft.cufftPlan1d(plan, inputData.length, cufftType.CUFFT_R2C, 1);

/*

*plan - указатель на план

*inputDataSize - количество входных значений; если входные данные являются *вещественными, то этот параметр равняется длине входного массива, а если *входные данные это массив комплексных чисел, то значение параметра равно *половине длины входного массива, т.к. одно комплексное число представлено *двумя элементами массива

*cufftType.CUFFT_R2C - тип преобразования

*1 - количество подобных преобразований

*/

// выполнение БПФ

long timeStart = new Date().getTime();

JCufft.cufftExecR2C(plan, deviceDataIn, deviceDataOut);

System.out.println("Время преобразования: " + (new Date().getTime() - timeStart)/1000.+" сек")

// копирование результатов из памяти видеокарты в оперативную память

JCuda.cudaMemcpy(Pointer.to(fftResults), deviceDataOut, fftResults.length * 4,

cudaMemcpyKind.cudaMemcpyDeviceToHost);

// освобождение ресурсов

JCufft.cufftDestroy(plan);

JCuda.cudaFree(deviceDataIn);

JCuda.cudaFree(deviceDataOut);

return cudaComplexToDouble(fftResults);

}

/**

* Выполняет БПФ массива значений с помощью Apache Commons Math

*

* @param inputData - массив входных значений

* @return массив с результатами БПФ

*/

public static double[] commonsTransform(double[] inputData){

FastFourierTransformer fft = new FastFourierTransformer();

long timeStart = new Date().getTime();

Complex[] cmx = fft.transform(inputData);

System.out.println("Время преобразования: " + (new Date().getTime() - timeStart)/1000.+" сек");

double[] fftReults = new double[inputData.length/2 + 1];

for(int i = 0; i < fftReults.length; i++){

fftReults[i] = cmx[i].abs();

}

return fftReults;

}

/**

* Метод осуществляет преобразование массива комплексных чисел в

* массив, содержащий их модули

*

* @param complexData - массив комплексных чисел

* @return массив модулей комплексных чисел

*/

public static double[] cudaComplexToDouble(float[] complexData){

double[] result = new double[complexData.length/2];

int j=0;

for(int i=0; i < complexData.length-1; i++) {

result[j++] = Math.sqrt(complexData[i]*complexData[i] + complexData[i+1]*complexData[i+1]);

i++;

}

return result;

}

/**

* Выводит на стандартный вывод первое, среднее

* и последнее значения массива

*

* @param data - массив, значения которого необходимо вывести

*/

public static void printSomeValues(double[] data){

System.out.println("[0]: "+data[0]);

System.out.println("["+(data.length/2)+"]: "+data[data.length/2]);

System.out.println("["+(data.length-1)+"]: "+data[data.length-1]);

}

}

Технический вывод программы

Генерация входных данных размером 8388608 значений...

1D БПФ с использованием apache commons math...

Время преобразования: 92.851 сек

[0]: 4195107.645827353

[2097152]: 1411.8392665442454

[4194304]: 114.60465306043625

1D БПФ JCufft (данные в оперативной памяти)...

Время преобразования: 0.085 сек

[0]: 4195107.922955976

[2097152]: 1411.791370918522

[4194304]: 114.75

1D БПФ JCufft (данные в памяти видеокарты)...

Время преобразования: 0.0 сек

[0]: 4195107.922955976

[2097152]: 1411.791370918522

[4194304]: 114.75

Код программы расчёта числа PI

#include "cuda_runtime.h"

#include "device_launch_parameters.h"

#include <stdio.h>

#include <conio.h>

#include <time.h>

#include <cuda.h>

#include <math.h>

#include <Windows.h>

#define CUDA_FLOAT float

const long GRID_SIZE=1024;

const long BLOCK_SIZE=16;

__global__ void pi_kern(CUDA_FLOAT *res)

{

int n = threadIdx.x + blockIdx.x * BLOCK_SIZE;

CUDA_FLOAT x0 = n * 1.f / (BLOCK_SIZE * GRID_SIZE); // Началоотрезка интегрирования

CUDA_FLOAT y0 = sqrtf(1 - x0 * x0);

CUDA_FLOAT dx = 1.f / (1.f * BLOCK_SIZE * GRID_SIZE); // Шагинтегрирования

CUDA_FLOAT s = 0; // Значение интеграла по отрезку, данномутекущему треду

CUDA_FLOAT x1, y1;

x1 = x0 + dx;

y1 = sqrtf(1 - x1 * x1);

s = (y0 + y1) * dx / 2.f;// Площадь трапеции

res[n] = s;// Запись результата в глобальную память

}

int main(int argc, char** argv)

{

clock_t time;

CUDA_FLOAT *res_d;// Результаты на устройстве

CUDA_FLOAT res[GRID_SIZE * BLOCK_SIZE];// Результаты в хостовой памяти

cudaMalloc((void**)&res_d, sizeof(CUDA_FLOAT) * GRID_SIZE *

BLOCK_SIZE);// Выделение памяти на CPUл

// Рамеры грида и блока на GPU

dim3 grid(GRID_SIZE);

dim3 block(BLOCK_SIZE);

time = clock();

pi_kern<<<grid, block>>>(res_d);// Запуск ядра

cudaThreadSynchronize();// Ожидаем завершения работы ядра

cudaMemcpy(res, res_d, sizeof(CUDA_FLOAT) * GRID_SIZE * BLOCK_SIZE,

cudaMemcpyDeviceToHost);// Копируем результаты на хост

cudaFree(res_d);// Освобождаем память на GPU

CUDA_FLOAT pi = 0;

for (int i=0; i < GRID_SIZE * BLOCK_SIZE; i++)

{

pi += res[i];

}

pi *= 4;

time = clock() - time;

printf("PI = %.12f\n",pi);

printf("%.4f", (double)time/CLOCKS_PER_SEC);

getch();

return 0;

}

Технический вывод программы

Расчёты проводились 10 раз. 100 000 000 Слагаемых для решения числа PI, время работы программы 35~37 секунд

Расчёт на CPU

	Потоки, количество
Итерации	1	2	4	8	16	32
100000	6	3	2	3	3	6
1000000	39	23	13	14	14	17
10000000	268	143	87	87	88	89
100000000	2178	1120	666	598	680	683
1000000000	26665	13289	7395	6202	6258	6483

На CPU 100 000 000 итераций занимает 598 секунд.



Выводы

При расчете числа Пи на CPU по результатам проделанной работы стало известно, что чем больше количество итераций, тем эффективнее работает параллельный алгоритм.

Самое эффективное - количество потоков = количеству ядер процессора.

На не больших количествах итераций система hyper-t не дает преимущества, за счет того, что потоки слишком быстро заканчивают свое действие. Но при более больших объемах вычислений, hyper-t позволяет и дальше увеличивать производительность поточного программирования, за счет удвоения числа реально работающих в параллельном режиме потоков, примерно на 20%.

На более высоких значениях количества итераций максимальное ускорение достигается на 8 потоках, из-за того, что данный процессор поддерживает технологию HyperThreading.

В процессорах с использованием этой технологии каждый физический процессор может хранить состояние сразу двух потоков, что для операционной системы выглядит как наличие двух логических процессоров (англ. Logical processor). Физически у каждого из логических процессоров есть свой набор регистров и контроллер прерываний (APIC), а остальные элементы процессора являются общими. Когда при исполнении потока одним из логических процессоров возникает пауза (в результате кэш-промаха, ошибки предсказания ветвлений, ожидания результата предыдущей инструкции), то управление передаётся потоку в другом логическом процессоре. Таким образом, пока один процесс ждёт, например, данные из памяти, вычислительные ресурсы физического процессора используются для обработки другого процесса.

Параллельные вычисления в целом более эффективнее, чем последовательные, из-за того, они используют всю вычислительную мощь процессора.

Расчёты на GPU быстрее в 17 раз, чем на CPU.

Высокая вычислительная мощность GPU объясняется особенностями архитектуры. Если современные CPU содержат несколько ядер (на большинстве современных систем от 2 до 6, по состоянию на 2012 г.), графический процессор изначально создавался как многоядерная структура, в которой количество ядер может достигать сотен. Разница в архитектуре обусловливает и разницу в принципах работы. Если архитектура CPU предполагает последовательную обработку информации, то GPU исторически предназначался для обработки компьютерной графики, поэтому рассчитан на массивно параллельные вычисления.



Приложение 1

Теоретическая часть

-- иррациональное число, то есть его значение не может быть точно выражено в виде дроби m/n, где m и n -- целые числа. Следовательно, его десятичное представление никогда не заканчивается и не является периодическим

В своей лабораторной работе я использовал два алгоритма расчета числа Пи .

Формула Леонарда Эйлера:

И Формулу Валлеса:



Последовательный алгоритм.

Схема 1.

Код программы представлен в приложении 1.



Параллельный алгоритм

Узким местом параллельного алгоритма является сохранение промежуточных сумм и произведений в один класс данных.

Чтобы этого избежать я сделал специальный поток в программе, который распределяет нагрузку между потоками, которые считают промежуточные суммы и произведения. А затем, после окончания расчета, отправляют данные в один глобальный класс, который защищен мьютексом, чтобы только один поток, в одно время мог записывать данные в переменную.

После поступления всех данных в общий глобальный класс, поток который распределял нагрузку между потоками, начинает считать сумму или произведение, в зависимости от алгоритма.

Такое распределение нагрузки позволило избежать постоянных задержек в ожидании записи данных.

См. схема 2, код представлен в приложении 2.

Алгоритм

Алгоритм расчёта чиста PI.

Вычислительный процессор

Intel Core i7-950

Тактовая частота	Ядра	Кэш L2	Кэш L3	TDP	Разъём
3.07 ГГц	4	4 Ч 256 КБ	8 МБ	3 Ч DDR3-1066	LGA 1366

Результаты эксперимента

	Потоки, количество
Итерации	1	2	4	8	16	32
100000	6	3	2	3	3	6
1000000	39	23	13	14	14	17
10000000	268	143	87	87	88	89
100000000	2178	1120	666	598	680	683
1000000000	26665	13289	7395	6202	6258	6483

Таблица 1. Таблица зависимости времени выполнения, от количества итераций и потоков

Минимальное время в миллисекундах выделено серым цветом.

	Потоки
Итерации	1	2	4	8	16	32
100000	1	2	3	2	2	1
1000000	1	1,70	3,00	2,79	2,79	2,29
10000000	1	1,87	3,08	3,08	3,05	3,01
100000000	1	1,94	3,27	3,64	3,20	3,19
1000000000	1	2,01	3,61	4,30	4,26	4,11

Таблица 2. Таблица зависимости ускорения, от количества итераций и потоков

Максимальное ускорение выделено серым цветом.

Рисунок 0. График зависимости ускорения, от количества итераций и потоков.

ПРИЛОЖЕНИЕ 1.1

Рис.1 Хронология загрузки ЦП 1 000 000 000 итераций, 1 процесс

Рис.2 Хронология загрузки ЦП 1 000 000 000 итераций, 2 процесса

Рис.3 Хронология загрузки ЦП 1 000 000 000 итераций, 4 процесса

Рис.4 Хронология загрузки ЦП 1 000 000 000 итераций, 8 процессов

Рис.5 Хронология загрузки ЦП 1 000 000 000 итераций, 16 процессов

Рис.6 Хронология загрузки ЦП 1 000 000 000 итераций, 32 процесса

ПРИЛОЖЕНИЕ 1.2

private void jButton1MouseClicked(java.awt.event.MouseEvent evt) {//GEN-FIRST:event_jButton1MouseClicked

int iter = Integer.parseInt(jTextField1.getText());

int threads = Integer.parseInt(jTextField2.getText());

Global.TimeStart();

Listner L = new Listner(iter, threads, 0);

Thread t = new Thread(L);

t.start();

try {

t.join();

} catch (InterruptedException ex) {

Logger.getLogger(multithread.class.getName()).log(Level.SEVERE, null, ex);

}

jTextArea2.insert(Double.toString(Global.F()) + "\n", 0);

Global.TimeStop();

jTextArea3.insert(Long.toString(Global.stop - Global.start) + "\n", 0);

Global.Reset();

}//GEN-LAST:event_jButton1MouseClicked

public class Listner extends Thread {

int threads, pos;

long iter;

public Listner(long iter, int threads, int pos) {

this.threads = threads;

this.iter = iter;

this.pos = pos;

}

@Override

public void run() {

long start = 1;

long delta = iter / threads;

Thread[] t = new Thread[threads];

if (pos == 0) {

First[] f = new First[threads];

for (int i = 0; i < threads; i++) {

f[i] = new First(start, start + delta);

t[i] = new Thread(f[i], "Thread " + Integer.toString(i));

t[i].start();

start = start + delta;

}

}

if (pos == 1) {

Second[] f = new Second[threads];

for (int i = 0; i < threads; i++) {

f[i] = new Second(start, start + delta);

t[i] = new Thread(f[i], "Thread " + Integer.toString(i));

t[i].start();

start = start + delta;

}

}

for (int i = 0; i < threads; i++) {

try {

t[i].join();

} catch (InterruptedException ex) {

Logger.getLogger(Listner.class.getName()).log(Level.SEVERE, null, ex);

}

}

}

}

public class First extends Thread {

long start, stop;

public First(long start, long stop) {

this.start =start;

this.stop = stop;

}

@Override

public void run() {

double summ = 0;

for (int i = (int)start; i < stop; i++) {

summ += 1 / Math.pow(i, 2);

}

Global.plus(summ);

}

}

public class Global

private static double SumF = 0, SumS = 1;

public static long start, stop;

public static synchronized void plus(double d) {

SumF += d;

}

public static synchronized void mul(double d) {

SumS *= d;

}

public static synchronized double F() {

return Math.sqrt(6 * SumF);

}

public static synchronized double S() {

return SumS * 2;

}

public static synchronized void TimeStart() {

start = System.currentTimeMillis();

}

public static synchronized void TimeStop() {

stop = System.currentTimeMillis();

}

Скриншоты программ

Инструкция пользователя

Программы имеют графический интерфейс, и различаются иконками.

Программа использующая последовательный алгоритм расчета пи имеет иконку: (onethread.exe), а параллельный : (multithread.exe)

Программа onethread.exe

Программа имеет 3 кнопки

«Первый» -- нажимая эту кнопку вы запускаете первый алгоритм(алгоритм Эйлера)

«Второй» -- нажимая эту кнопку вы запускаете второй алгоритм (алгоритм Валлеса)

««clear()» -- очистка полей

В поле «количество итераций» вводится количество итераций от 1 до 100 000 000 000

В поле «количество прогонов» вводится количество повторений алгоритма, для более точного значения.

В левом поле выводится число Пи, в правом время работы алгоритма.

Программа multithread.exe

Программа имеет 2 кнопки

«Первый» -- нажимая эту кнопку вы запускаете первый алгоритм(алгоритм Эйлера)

«Второй» -- нажимая эту кнопку вы запускаете второй алгоритм (алгоритм Валлеса)

В поле «количество итераций» вводится количество итераций от 1 до 100 000 000 000

В поле «количество потоков» вводится количество повторений алгоритма, для более точного значения.

В левом поле выводится число Пи, в правом время работы алгоритма.

Выводы по лабораторной работе

При расчете числа Пи на CPU по результатам проделанной работы стало известно, что чем больше количество итераций, тем эффективнее работает параллельный алгоритм.

Самое эффективное - количество потоков = количеству ядер процессора.

На не больших количествах итераций система hyper-t не дает преимущества, за счет того, что потоки слишком быстро заканчивают свое действие. Но при более больших объемах вычислений, hyper-t позволяет и дальше увеличивать производительность поточного программирования, за счет удвоения числа реально работающих в параллельном режиме потоков, примерно на 20%.

На более высоких значениях количества итераций максимальное ускорение достигается на 8 потоках, из-за того, что данный процессор поддерживает технологию HyperThreading.

В процессорах с использованием этой технологии каждый физический процессор может хранить состояние сразу двух потоков, что для операционной системы выглядит как наличие двух логических процессоров (англ. Logical processor). Физически у каждого из логических процессоров есть свой набор регистров и контроллер прерываний (APIC), а остальные элементы процессора являются общими. Когда при исполнении потока одним из логических процессоров возникает пауза (в результате кэш-промаха, ошибки предсказания ветвлений, ожидания результата предыдущей инструкции), то управление передаётся потоку в другом логическом процессоре. Таким образом, пока один процесс ждёт, например, данные из памяти, вычислительные ресурсы физического процессора используются для обработки другого процесса.

Параллельные вычисления в целом более эффективнее, чем последовательные, из-за того, они используют всю вычислительную мощь процессора.

1. Размещено на www.allbest.ru