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

 

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

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

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

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

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

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

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

Иванов В.В.

Группа: 8302

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

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

Оглавление

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

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

Отличия от С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) - центральный процессор, который управляет выполнением программы.

Графический процессор (англ. 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 в неграфических расчётах является распараллеливание алгоритмов на сотни исполнительных блоков, имеющихся в видеочипах.- технология GPGPU, позволяющая реализовывать на С алгоритмы, выполнимые на графических процессорах ускорителей GeForce восьмого поколения и старше. Технология CUDA разработана компанией nVidia. Проще говоря, графическая подсистема компьютера с поддержкой CUDA может быть использована, как вычислительная.To Metal (CTM) - технология GPGPU, использующая низкоуровневое программирование на графических процессорах ATI (AMD Graphics Products Group). CTM является виртуальной машиной, исполняющей ассемблерный код, в то время как CUDA - своеобразное расширение С. Две эти платформы несовместимы между собой.

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

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

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

Рисунок 1

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

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

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

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

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

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

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

Недостатки

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

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

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

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

2. CUDA Toolkit v.2.1

. CUDA SDK v.2.1

. Visual Studio 2008

. 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 ГГц

Gb DDR-3

GeForce GTX 280

ВидеокартыМодельГигафлопсGeForce GTX 690 5622GeForce GTX 5801581.056GeForce GTX 4801344.96GeForce GTX 280933.120GeForce 9800 GTX648GeForce 8800 GTS 640mb346Таблица 1. Сравнение производительности видеокарт

ПроцессорыМодельГигафлопсAMD Phenom II X6 1100T Black Edition 3.3 ГГц60.1Intel Core i7-950 3.03 ГГц53.28Intel Core 2 Quad Q8300 2.5 ГГц40AMD AMD ATHLON II X4 645 3.1 ГГц38.44Intel Core 2 Duo 2.4 ГГц19.02AMD 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)"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]; tid = threadIdx.x; idx = blockIdx.x * blockDim.x + threadIdx.x;

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

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

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

__syncthreads ();

// Суммирование в паралели( int s = blockDim.x / 2; s > 0; s >>= 1 )

{( tid < s ) [tid] += data[tid + s];

__syncthreads ();

}

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

if(tid == 0) _Dst[blockIdx.x] = data[0];

}

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

{<<<BLOCKS, BLOCK_SIZE>>>(d_Dst, d_Src);("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

////////////////////////////////////////////////////////////////////////////////main(int argc, char **argv)

{

//Use command-line specified CUDA device, otherwise use device with highest Gflops/s( cutCheckCmdLineFlag(argc, (const char **)argv, "device") )(argc, argv);( cutGetMaxGflopsDeviceId() );

int *d_Input, *d_Output;* h_Input = new int[VECTOR_SIZE];* h_Output = new int[BLOCKS];

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

{_Input[i] = 1;

}

std::cout << "Size of data: " << VECTOR_SIZE << "\n";::cout << "Blocks: " << BLOCKS << "\n";::cout << "Allocating and initializing CUDA arrays...\n";( cudaMalloc((void **)&d_Input, VECTOR_SIZE * sizeof(int)) );( cudaMalloc((void **)&d_Output, BLOCKS * sizeof(int)) );( cudaMemset(d_Output, 0x00, BLOCKS * sizeof(int)) );( cudaMemcpy(d_Input, h_Input, VECTOR_SIZE * sizeof(int), cudaMemcpyHostToDevice) );::cout << "Running GPU reduction...\n";();(d_Output, d_Input);();

std::cout << "Reading back GPU results...\n";( cudaMemcpy(h_Output, d_Output, BLOCKS * sizeof(int), cudaMemcpyDeviceToHost) );::cout << "Results: \n";::copy(h_Output, h_Output + BLOCKS, std::ostream_iterator<int>(std::cout,", "));( cudaFree(d_Input) );( cudaFree(d_Output) );[] h_Input;[] h_Output;();

cutilExit(argc, argv);}

Технический вывод программыof data: 8192: 16and initializing CUDA arrays...GPU reduction...back GPU results...:

, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512, 512ENTER to exit...

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

#include <iostream>

#include <ctime>

#include <vector>

#include <algorithm>

#include <iterator>show (const std::vector <float> &);main (void)

{int SIZE=5;::vector <float> A;::vector <float> B;::vector <float> REZULT (SIZE);tmp;

// fill vector A(int i=0; i<SIZE; i++) {::cout << "A[" << i <<"]: ";::cin >> tmp;.push_back (tmp); }

// fill vector B(int i=0; i<SIZE; i++) {::cout << "B[" << i <<"]: ";::cin >> tmp;.push_back (tmp); }

// ::vector <float> :: iterator A_=A.begin();::vector <float> :: iterator B_=B.begin();::vector <float> :: iterator REZULT_=REZULT.begin();(REZULT_; REZULT_!=REZULT.end(); REZULT_++, A_++, B_++)

*(REZULT_)=*(A_) + *(B_);= clock() - time;

// output::cout << "Vector A: ";(A);::cout << "Vector B: ";(B);::cout << "Vector REZULT: ";(REZULT);

system ("pause");0;

}

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

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

std::cout << std::endl;

}

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

public class JCufftDemo {static void main(String[] args) {[] fftResults; dataSize = 1<<23;

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

float[] inputData = createRandomData(dataSize)

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

System.out.println();

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

fftResults = jcudaTransformHostMemory(inputData.clone());(fftResults);

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

}

/**

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

*

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

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

*/static float[] createRandomData(int dataSize){random = new Random();data[] = new float[dataSize];(int i = 0; i < dataSize; i++)[i] = random.nextFloat();

return data;

}

/**

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

*

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

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

*/static double[] floatDataToDoubleData(float[] data){ [] doubleData = new double[data.length]; (int i=0; i < data.length; i++) doubleData[i] = data[i];

return doubleData;

}

/**

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

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

*

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

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

*/static double[] jcudaTransformHostMemory(float[] inputData){[] fftResults = new float[inputData.length + 2];

// создание планаplan = new cufftHandle();.cufftPlan1d(plan, inputData.length, cufftType.CUFFT_R2C, 1);

// выполнение БПФtimeStart = new Date().getTime();.cufftExecR2C(plan, inputData, fftResults);.out.println("Время преобразования: " + (new Date().getTime() - timeStart)/1000.0+" сек");

// уничтожение плана.cufftDestroy(plan);

return cudaComplexToDouble(fftResults);

}

/**

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

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

*

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

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

*/static double[] jcudaTransformDeviceMemory(float[] inputData){[] fftResults = new float[inputData.length + 2];

// указатель на устройствоdeviceDataIn = new Pointer();

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

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

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

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

Pointer deviceDataOut = new Pointer();

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

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

// создание планаplan = new cufftHandle();.cufftPlan1d(plan, inputData.length, cufftType.CUFFT_R2C, 1);

/*

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

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

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

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

*/

// выполнение БПФtimeStart = new Date().getTime();.cufftExecR2C(plan, deviceDataIn, deviceDataOut);.out.println("Время преобразования: " + (new Date().getTime() - timeStart)/1000.+" сек")

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

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

// освобождение ресурсов.cufftDestroy(plan);.cudaFree(deviceDataIn);.cudaFree(deviceDataOut);cudaComplexToDouble(fftResults);

}

/**

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

*

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

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

*/static double[] commonsTransform(double[] inputData){fft = new FastFourierTransformer();timeStart = new Date().getTime();[] cmx = fft.transform(inputData);.out.println("Время преобразования: " + (new Date().getTime() - timeStart)/1000.+" сек");[] fftReults = new double[inputData.length/2 + 1];(int i = 0; i < fftReults.length; i++){[i] = cmx[i].abs();

}fftReults;

}

/**

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

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

*

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

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

*/

public static double[] cudaComplexToDouble(float[] complexData){[] result = new double[complexData.length/2];j=0;(int i=0; i < complexData.length-1; i++) { [j++] = Math.sqrt(complexData[i]*complexData[i] + complexData[i+1]*complexData[i+1]);

i++;

}result;

}

/**

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

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

*

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

*/static void printSomeValues(double[] data){ .out.println("[0]: "+data[0]);.out.println("["+(data.length/2)+"]: "+data[data.length/2]);.out.println("["+(data.length-1)+"]: "+data[data.length-1]);

}

}

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

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

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

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

[0]: 4195107.645827353

[2097152]: 1411.8392665442454

[4194304]: 114.60465306043625

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

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

[0]: 4195107.922955976

[2097152]: 1411.791370918522

[4194304]: 114.75

D БПФ 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 floatlong GRID_SIZE=1024;long BLOCK_SIZE=16;

__global__ void pi_kern(CUDA_FLOAT *res)

{n = threadIdx.x + blockIdx.x * BLOCK_SIZE;_FLOAT x0 = n * 1.f / (BLOCK_SIZE * GRID_SIZE); // Началоотрезка интегрирования_FLOAT y0 = sqrtf(1 - x0 * x0);_FLOAT dx = 1.f / (1.f * BLOCK_SIZE * GRID_SIZE); // Шагинтегрирования

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

CUDA_FLOAT x1, y1;= x0 + dx;= sqrtf(1 - x1 * x1);= (y0 + y1) * dx / 2.f;// Площадь трапеции

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

}main(int argc, char** argv)

{_t time;_FLOAT *res_d;// Результаты на устройстве

CUDA_FLOAT res[GRID_SIZE * BLOCK_SIZE];// Результаты в хостовой памяти((void**)&res_d, sizeof(CUDA_FLOAT) * GRID_SIZE *

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

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

dim3 grid(GRID_SIZE);block(BLOCK_SIZE);= clock();_kern<<<grid, block>>>(res_d);// Запуск ядра();// Ожидаем завершения работы ядра(res, res_d, sizeof(CUDA_FLOAT) * GRID_SIZE * BLOCK_SIZE,);// Копируем результаты на хост(res_d);// Освобождаем память на GPU_FLOAT pi = 0;(int i=0; i < GRID_SIZE * BLOCK_SIZE; i++)

{+= res[i];

}*= 4;= clock() - time;("PI = %.12f\n",pi);("%.4f", (double)time/CLOCKS_PER_SEC);

getch();0;

}

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

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

Расчёт на CPU

Потоки, количествоИтерации124816321000006323361000000392313141417100000002681438787888910000000021781120666598680683100000000026665132897395620262586483На 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.

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

Core i7-950

Тактовая частотаЯдраКэш L2Кэш L3TDPРазъём3.07 ГГц44 × 256 КБ8 МБ3 × DDR3-1066LGA 1366Результаты эксперимента

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

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

ПотокиИтерации12481632100000123221100000011,703,002,792,792,291000000011,873,083,083,053,0110000000011,943,273,643,203,19100000000012,013,614,304,264,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_jButton1MouseClickediter = Integer.parseInt(jTextField1.getText());threads = Integer.parseInt(jTextField2.getText());.TimeStart();L = new Listner(iter, threads, 0);t = new Thread(L);.start();{.join();

} catch (InterruptedException ex) {.getLogger(multithread.class.getName()).log(Level.SEVERE, null, ex);

}.insert(Double.toString(Global.F()) + "\n", 0);.TimeStop();.insert(Long.toString(Global.stop - Global.start) + "\n", 0);.Reset();

}//GEN-LAST:event_jButton1MouseClickedclass Listner extends Thread {threads, pos;iter;Listner(long iter, int threads, int pos) {.threads = threads;.iter = iter;.pos = pos;

}

@Overridevoid run() {start = 1;delta = iter / threads;[] t = new Thread[threads];(pos == 0) {[] f = new First[threads];(int i = 0; i < threads; i++) {[i] = new First(start, start + delta);[i] = new Thread(f[i], "Thread " + Integer.toString(i));[i].start();= start + delta;

}

}(pos == 1) {[] f = new Second[threads];(int i = 0; i < threads; i++) {[i] = new Second(start, start + delta);[i] = new Thread(f[i], "Thread " + Integer.toString(i));[i].start();= start + delta;

}

}

for (int i = 0; i < threads; i++) {{[i].join();

} catch (InterruptedException ex) {.getLogger(Listner.class.getName()).log(Level.SEVERE, null, ex);

}

}

}

}class First extends Thread {start, stop;First(long start, long stop) {.start =start;.stop = stop;

}

@Overridevoid run() {summ = 0;(int i = (int)start; i < stop; i++) {+= 1 / Math.pow(i, 2);

}.plus(summ);

}

}

public class Global

private static double SumF = 0, SumS = 1;static long start, stop;static synchronized void plus(double d) {+= d;

}static synchronized void mul(double d) {*= d;

}static synchronized double F() {Math.sqrt(6 * SumF);

}static synchronized double S() {SumS * 2;

}static synchronized void TimeStart() {= System.currentTimeMillis();

}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.

Министерство образования РФ Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» Кафедра САААПР

Больше работ по теме: