SIA: Swarm Intelligence Algorithms
الگوریتم های هوش جمعیSIA: Swarm Intelligence Algorithms
الگوریتم های هوش جمعی
پیاده سازی حل مسئله جمع دوازده عدد به کمک کودا در ویژوال استودیو با چهار سناریو حل
پیاده سازی حل مسئله جمع دوازده عدد به کمک کودا در ویژوال استودیو با چهار سناریو حل
بیان مسئله:
در این مسئله هدف محاسبه حاصل جمع 12 عدد (صفر تا یازده) به کمک پردازش موازی در کودا در محیط ویژوال استودیو است. بدین منظور ابتدا کد سریال آن در محیط ویژوال استودیو سی پلاس پلاس نوشته شده است. پس از آن با چهار سناریو مختلف به شکل موازی مسئله حل شده است. در پایان زمان محاسبه این حاصل جمع برای روش های مختلف مورد مقایسه قرار گرفته است.
|
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
شکل 1: محاسبه مجموع 12 عدد صفر تا یازده
پیاده سازی مسئله به روش سریال به کمک فایل sum12numberserial:
در این روش به صورت ترتیبی مجموع 12 عدد محاسبه شده است که کد آن در ذیل آورده شده است.
مراحل کار در شکل 2 آورده شده است. در آن در هر تکرار یک عدد با مقدار فعلی x جمع می شود.
شکل 2: مجموع دوازده عدد به صورت سریال
## sum12numberserial.cpp
---------------------------------------------------------------------------------------------------------------------
#include "stdio.h"
#include "conio.h"
#include "stdafx.h"
#include "stdafx.h"
#include "iostream"
#include "stdlib.h"
#include "time.h"
#include <stdio.h>
#include "math.h"
#include <cstdio>
#include <memory.h>
#include <stdio.h>
#include <string.h>
#include "stdio.h"
#include "stdio.h"
#include "stdio.h"
#include "conio.h"
#include "stdafx.h"
#include "stdafx.h"
#include "iostream"
#include "stdlib.h"
#include "time.h"
#include <stdio.h>
#include "math.h"
#include <cstdio>
#include <memory.h>
#include <stdio.h>
#include <string.h>
#include "stdio.h"
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <stdio.h>
#include <assert.h>
#include <memory.h>
#include <string.h>
#include <time.h>
#include <windows.h>
#include "stdafx.h"
#include "stdafx.h"
#include "iostream"
#include "stdlib.h"
#include "time.h"
#include <stdio.h>
#include "math.h"
#include <cstdio>
#include <memory.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#include "sum12number.h"
long long milliseconds_now() {
static LARGE_INTEGER s_frequency;
static BOOL s_use_qpc = QueryPerformanceFrequency(&s_frequency);
if (s_use_qpc) {
LARGE_INTEGER now;
QueryPerformanceCounter(&now);
return (1000LL * now.QuadPart) / s_frequency.QuadPart;
}
else {
return GetTickCount();
}
}
int main()
{
long long start = milliseconds_now();
//int a[12];
struct mystruct1
{
int a[12];
int x = 0;
};
//mystruct1 mystruct;
struct mystruct1 mystruct;
for (int i = 0; i < 12; i++)
{
mystruct.a[i] = i;
cout << "\n*a["<<i<<"]=" << mystruct.a[i] << "\n";
}
struct mystruct100 mystruct2;
mystruct2 = sum12number(mystruct.a);
int finalsum;
finalsum=mystruct2.x;
cout << "\n****totalsum="<< finalsum << "\n";
// Somewhere else...
// ...
// ....
long long elapsed = milliseconds_now() - start;
cout << "\n****totalsum=" << elapsed << "\n";
cin.get();
return 0;
}
---------------------------------------------------------------------------------------------------------------------
## sum12numberserial
---------------------------------------------------------------------------------------------------------------------
struct mystruct100
{
int a[12];
int x = 0;
};
struct mystruct100 sum12number(int a[12])
{
struct mystruct100 items;
for (int i = 0; i < 12; i++)
std::cout << "\nitems.a["<<i<<"]=" << a[i] << "\n";
//using namespace std;
//int i, a, b, c, d;
int sum[12] = { 0 };
int x = 0;
for (int i = 0; i < 12; i++)
{
x += a[i];
std::cout << "\nx=" << x << "\n";
}
items.x = x;
return items;
}
---------------------------------------------------------------------------------------------------------------------
پیاده سازی مسئله با روش اول به کمک فایل cudasum12numberby12Thread :
به منظور محاسبه مجموع 12 عدد به صورت موازی در کودا یکی از روش ها این است که با 12 تا نخ در یک بلاک مسئله حل شود. بدین منظور در داخل کد از دستور add << <1, 12 >> >(dev_a); استفاده شده است. در این روش محاسبه به صورت شکل 3 می باشد که در آن ابتدا نخ های زوج با نخ بعدی خود جمع می شوند و حاصل در خود نخ های زوج قرار می گیرد پس از آن نخ های با باقیمانده آنها بر چهار صفر است و ... ادامه می یابد. در نهایت حاصل جمع نهایی در خانه صفرم a[12] قرار خواهد گرفت.
شکل3 : مجموع دوازده عدد به صورت موازی با روش اول
## 1cudasum12numberby12Thread
---------------------------------------------------------------------------------------------------------------------
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#include <cstdio>
#include <memory.h>
#include <string.h>
#include "conio.h"
#include "stdlib.h"
#include <cstdio>
#include "stdio.h"
#include "cuda.h"
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <assert.h>
#include <windows.h>
#include <cuda_gl_interop.h>
#include <cuda_runtime_api.h>
#include "device_launch_parameters.h"
#ifndef __CUDACC__
#endif
#include <device_launch_parameters.h>
#include <device_functions.h>
#include <cuda.h>
#include <cuda_runtime_api.h>
#include <device_launch_parameters.h>
#include <device_functions.h>
#include "cuda_runtime.h"
#include "device_launch_parameters.h"
//for __syncthreads()
#ifndef __CUDACC_RTC__
#define __CUDACC_RTC__
#endif // !(__CUDACC_RTC__)
//for atomicAdd
#ifndef __CUDACC__
#define __CUDACC__
#endif // !__CUDACC__
#include <device_functions.h>
#include <cstdlib>
#include <helper_cuda.h>
#define N 12
using namespace std;
long long milliseconds_now() {
static LARGE_INTEGER s_frequency;
static BOOL s_use_qpc = QueryPerformanceFrequency(&s_frequency);
if (s_use_qpc) {
LARGE_INTEGER now;
QueryPerformanceCounter(&now);
return (1000LL * now.QuadPart) / s_frequency.QuadPart;
}
else {
return GetTickCount();
}
}
__global__ void add(int *a)//, int *b, int *c)
{
int idx = blockIdx.x * blockDim.x + threadIdx.x;
__shared__ int b[12];
b[idx] = a[idx];
printf("\nthreadIdx.x=%d \n", threadIdx.x);
printf("\nieeeeeeeeeeeeeeeedx=%d \n", idx);
if (idx<N&& idx %2==0)
{
b[idx] = b[idx] + b[idx + 1];
printf("\n%d ***2!!!\t ", b[idx], "\n");
}
if (idx<N&& idx % 4 == 0)
{
b[idx] = b[idx] + b[idx + 2];
printf("\n%d ***4!!!\t ", b[idx], "\n");
}
if (idx<N&& idx % 8 == 0)
{
b[idx] = b[idx] + b[idx + 4];
printf("\n%d ***8!!!\t ", b[idx], "\n");
}
if (threadIdx.x == 0)
{
b[0] = b[0] + b[8];
printf("\n%d ***end!!!\t ", b[0], "\n");
}
a[idx] = b[idx];
}
int main()
{
long long start = milliseconds_now();
int a[N];
int *dev_a;
cout << "sizeof int=" << sizeof(int) << "\n";
cout << "\tN*sizeof int=" << N*sizeof(int) << "\n";
cudaMalloc((void **)&dev_a, N*sizeof(int));
cout << "&dev_a=" << &dev_a << "\n";
// Fill Arrays
for (int i = 0; i < N; i++)
a[i] = i;
for (int i = 0; i < N; i++)
cout << "a[" << i << "]=" << a[i] <<"\n";
cudaMemcpy(dev_a, a, N*sizeof(int), cudaMemcpyHostToDevice);
add <<<1, 12 >> >(dev_a);//, dev_b, dev_c);
cudaMemcpy(a, dev_a, N*sizeof(int), cudaMemcpyDeviceToHost);
for (int i = 0; i < N; i++)
printf("%d\n", a[i]);
long long elapsed = milliseconds_now() - start;
cout << "\n****totalsum=" << elapsed << "\n";
cin.get();
return 0;
}
---------------------------------------------------------------------------------------------------------------------
پیاده سازی مسئله با روش دوم به کمک فایل cudasum12numberby12Block :
روش دوم از روش محاسبه روش اول استفاده می کند با این تفاوت که به جای 12 تا نخ در یک بلاک از 12 تا بلاک و یک نخ در هر بلاک استفاده می کند. همانند شکل 4 عمل می نماید.
شکل4: مجموع دوازده عدد به صورت موازی با روش دوم
## 2cudasum12numberby1Blockand12thread
---------------------------------------------------------------------------------------------------------------------
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#include <cstdio>
#include <memory.h>
#include <string.h>
#include "cuda.h"
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <assert.h>
#include <memory.h>
#include <string.h>
#include <windows.h>
#include <cuda_gl_interop.h>
#include <cuda_runtime_api.h>
#include "device_launch_parameters.h"
#ifndef __CUDACC__
#endif
#include <device_launch_parameters.h>
#include <device_functions.h>
#include <cuda.h>
#include <cuda_runtime_api.h>
#include <device_launch_parameters.h>
#include <device_functions.h>
#include "cuda_runtime.h"
#include "device_launch_parameters.h"
//for __syncthreads()
#ifndef __CUDACC_RTC__
#define __CUDACC_RTC__
#endif // !(__CUDACC_RTC__)
//for atomicAdd
#ifndef __CUDACC__
#define __CUDACC__
#endif // !__CUDACC__
#include <device_functions.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <helper_cuda.h>
#define N 12
using namespace std;
long long milliseconds_now() {
static LARGE_INTEGER s_frequency;
static BOOL s_use_qpc = QueryPerformanceFrequency(&s_frequency);
if (s_use_qpc) {
LARGE_INTEGER now;
QueryPerformanceCounter(&now);
return (1000LL * now.QuadPart) / s_frequency.QuadPart;
}
else {
return GetTickCount();
}
}
__global__ void add(int *a)
{
int idx = blockIdx.x * blockDim.x + threadIdx.x;
printf("\nthreadIdx.x=%d \n", threadIdx.x);
printf("\nieeeeeeeeeeeeeeeedx=%d \n", idx);
if (blockIdx.x<N&& blockIdx.x % 2 == 0)
{
a[blockIdx.x] = a[blockIdx.x] + a[blockIdx.x + 1];
printf("sum2num-numB%d:%d \t ", blockIdx.x, a[blockIdx.x], "\t");
}
if (blockIdx.x<N&& blockIdx.x % 4 == 0)
{
a[blockIdx.x] = a[blockIdx.x] + a[blockIdx.x + 2];
printf("\n%d ***4!!!\t ", a[blockIdx.x], "\n");
}
if (blockIdx.x<N&& blockIdx.x % 8 == 0)
{
a[blockIdx.x] = a[blockIdx.x] + a[blockIdx.x + 4];
printf("\n%d ***8!!!\t ", a[blockIdx.x], "\n");
}
if (blockIdx.x == 0)
{
a[0] = a[0] + a[8];
printf("\n%d ***end!!!\t ", a[0], "\n");
}
}
int main()
{
long long start = milliseconds_now();
int a[N];
int *dev_a;
cout << "sizeof int=" << sizeof(int) << "\n";
cout << "\tN*sizeof int=" << N*sizeof(int) << "\n";
cudaMalloc((void **)&dev_a, N*sizeof(int));
cout << "&dev_a=" << &dev_a << "\n";
// Fill Arrays
for (int i = 0; i < N; i++)
a[i] = i;
for (int i = 0; i < N; i++)
cout << "a[" << i << "]=" << a[i] << "\n";
cudaMemcpy(dev_a, a, N*sizeof(int), cudaMemcpyHostToDevice);
add << <12, 1 >> >(dev_a);
cudaMemcpy(a, dev_a, N*sizeof(int), cudaMemcpyDeviceToHost);
for (int i = 0; i < N; i++)
printf("%d\n", a[i]);
long long elapsed = milliseconds_now() - start;
cout << "\n****totalsum=" << elapsed << "\n";
cin.get();
return 0;
}
---------------------------------------------------------------------------------------------------------------------
پیاده سازی مسئله با روش سوم به کمک فایل cudasum12numberby12Thread :
در روش سوم به منظور محاسبه مجموع 12 عدد به صورت موازی در کودا این است که با 12 تا نخ در یک بلاک مسئله حل شود. بدین منظور در داخل کد از دستور add << <1, 12 >> >(dev_a); استفاده شده است. و اما روش حل برخلاف روش اول و دوم در مرحله اول 6 نخ اول محاسبه همانند شکل 5 را انجام می دهند. که در آن نخ صفر با نخ 6 و نخ یک با نخ 7 و ... جمع می شود. مرحله بعد n/4 ، N/8 و ... این عملیات را تکرار می کنند. در نهایت حاصل جمع در نخ صفرم قرار می گیرد.
شکل5: مجموع دوازده عدد به صورت موازی با روش سوم
## 3cudasum12numberby1Blockand12thread
---------------------------------------------------------------------------------------------------------------------
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#include <cstdio>
#include <memory.h>
#include <string.h>
#include "cuda.h"
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <assert.h>
#include <memory.h>
#include <string.h>
#include <windows.h>
#include <cuda_gl_interop.h>
#include <cuda_runtime_api.h>
#include "device_launch_parameters.h"
#ifndef __CUDACC__
//#include "myhack.h"
#endif
#include <device_launch_parameters.h>
#include <device_functions.h>
#include <cuda.h>
#include <cuda_runtime_api.h>
#include <device_launch_parameters.h>
#include <device_functions.h>
#include "cuda_runtime.h"
#include "device_launch_parameters.h"
//for __syncthreads()
#ifndef __CUDACC_RTC__
#define __CUDACC_RTC__
#endif // !(__CUDACC_RTC__)
//for atomicAdd
#ifndef __CUDACC__
#define __CUDACC__
#endif // !__CUDACC__
#include <device_functions.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <helper_cuda.h>
#define N 12
using namespace std;
long long milliseconds_now() {
static LARGE_INTEGER s_frequency;
static BOOL s_use_qpc = QueryPerformanceFrequency(&s_frequency);
if (s_use_qpc) {
LARGE_INTEGER now;
QueryPerformanceCounter(&now);
return (1000LL * now.QuadPart) / s_frequency.QuadPart;
}
else {
return GetTickCount();
}
}
__global__ void add(int *a)//, int *b, int *c)
{
int idx = blockIdx.x * blockDim.x + threadIdx.x;
__shared__ int b[12];
b[idx] = a[idx];
printf("\nthreadIdx.x=%d \n", threadIdx.x);
printf("\nieeeeeeeeeeeeeeeedx=%d \n", idx);
printf("\n%d ***2!!!\t ", b[idx], "\n");
int m = N / 2;
while (idx<m)
{
if (idx < m)
{
b[idx] = b[idx] + b[m + idx];
printf("\n%d ***2!!!\t ", b[idx], "\n");
}
m=m / 2;
}
if (m == 0&&threadIdx.x==0)
{
b[threadIdx.x + 1] = b[threadIdx.x + 2];
b[threadIdx.x] += b[threadIdx.x+1];
printf("\n%d ***2!!!\t ", b[threadIdx.x], "\n");
}
if (threadIdx.x == 0)
printf("\n%d ***end!!!\t ", b[0], "\n");
a[idx] = b[idx];
}
int main()
{
long long start = milliseconds_now();
int a[N];
int *dev_a;
cout << "sizeof int=" << sizeof(int) << "\n";
cout << "\tN*sizeof int=" << N*sizeof(int) << "\n";
cudaMalloc((void **)&dev_a, N*sizeof(int));
cout << "&dev_a=" << &dev_a << "\n";
// Fill Arrays
for (int i = 0; i < N; i++)
a[i] = i;
for (int i = 0; i < N; i++)
cout << "a[" << i << "]=" << a[i] << "\n";
cudaMemcpy(dev_a, a, N*sizeof(int), cudaMemcpyHostToDevice);
add << <1, 12 >> >(dev_a);
cudaMemcpy(a, dev_a, N*sizeof(int), cudaMemcpyDeviceToHost);
for (int i = 0; i < N; i++)
printf("%d\n", a[i]);
long long elapsed = milliseconds_now() - start;
cout << "\n****totalsum=" << elapsed << "\n";
cin.get();
return 0;
}
---------------------------------------------------------------------------------------------------------------------
پیاده سازی مسئله با روش چهارم به کمک فایل cudasum12numberby12Block :
در روش چهارم بدین صورت عمل می شود که همانند شکل 6 از 12 بلاک با 1 نخ در هر بلاک محاسبه انجام می شود. روش محاسبه هم همانند روش سوم می باشد که در آن با استفاده از محاسبه مجموع در ابتدا در N/2وN/4 و ... اول آرایه a[12] قرار می گیرد و در نهایت مجموع در بلاک صفرم محاسبه شده و در خروجی نمایش داده می شود.
شکل6: مجموع دوازده عدد به صورت موازی با روش چهارم
##4cudasum12numberby12Blockand1thread
---------------------------------------------------------------------------------------------------------------------
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#include <cstdio>
#include <memory.h>
#include <string.h>
#include "cuda.h"
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <assert.h>
#include <memory.h>
#include <string.h>
#include <windows.h>
#include <cuda_gl_interop.h>
//#include <cub/cub.cuh>
#include <cuda_runtime_api.h>
#include "device_launch_parameters.h"
#ifndef __CUDACC__
//#include "myhack.h"
#endif
#include <device_launch_parameters.h>
#include <device_functions.h>
#include <cuda.h>
#include <cuda_runtime_api.h>
#include <device_launch_parameters.h>
#include <device_functions.h>
#include "cuda_runtime.h"
#include "device_launch_parameters.h"
//for __syncthreads()
#ifndef __CUDACC_RTC__
#define __CUDACC_RTC__
#endif // !(__CUDACC_RTC__)
//for atomicAdd
#ifndef __CUDACC__
#define __CUDACC__
#endif // !__CUDACC__
#ifdef __CUDACC__
#define cuda_SYNCTHREADS() __syncthreads()
#else
#define cuda_SYNCTHREADS()
#endif
#ifdef __INTELLISENSE___
#define cuda_SYNCTHREADS() __syncthreads()
#else
#define cuda_SYNCTHREADS()
#endif
#include "cuda_runtime.h"
#include "device_launch_parameters.h"
//for __syncthreads()
#ifndef __CUDACC_RTC__
#define __CUDACC_RTC__
#endif // !(__CUDACC_RTC__)
//for atomicAdd
#ifndef __CUDACC__
#define __CUDACC__
#endif // !__CUDACC__
#include <device_functions.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <helper_cuda.h>
#include <device_functions.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <helper_cuda.h>
#define N 12
using namespace std;
long long milliseconds_now() {
static LARGE_INTEGER s_frequency;
static BOOL s_use_qpc = QueryPerformanceFrequency(&s_frequency);
if (s_use_qpc) {
LARGE_INTEGER now;
QueryPerformanceCounter(&now);
return (1000LL * now.QuadPart) / s_frequency.QuadPart;
}
else {
return GetTickCount();
}
}
__global__ void add(int *a)
{
printf("\nthreadIdx.x=%d \n", threadIdx.x);
printf("\nblockIdx.x=%d \n", blockIdx.x);
int m = N / 2;
while (m >0)
{
if (blockIdx.x < m)
{
a[blockIdx.x] = a[blockIdx.x] + a[blockIdx.x + m];
printf("sum2num-numB%d:%d \n ", blockIdx.x, a[blockIdx.x], "\t");
}
m = m / 2;
}
if (blockIdx.x == 0)
{
a[blockIdx.x] = a[blockIdx.x]+a[blockIdx.x + 2];
printf("\n%d ***end!!!\t ", a[blockIdx.x], "\n");
}
}
int main()
{
long long start = milliseconds_now();
int a[N];
int *dev_a;
cout << "sizeof int=" << sizeof(int) << "\n";
cout << "\tN*sizeof int=" << N*sizeof(int) << "\n";
cudaMalloc((void **)&dev_a, N*sizeof(int));
cout << "&dev_a=" << &dev_a << "\n";
// Fill Arrays
for (int i = 0; i < N; i++)
a[i] = i;
for (int i = 0; i < N; i++)
cout << "a[" << i << "]=" << a[i] << "\n";
cudaMemcpy(dev_a, a, N*sizeof(int), cudaMemcpyHostToDevice);
add << <12, 1 >> >(dev_a);
cudaMemcpy(a, dev_a, N*sizeof(int), cudaMemcpyDeviceToHost);
for (int i = 0; i < N; i++)
printf("%d\n", a[i]);
long long elapsed = milliseconds_now() - start;
cout << "\n****totalsum=" << elapsed << "\n";
cin.get();
return 0;
}
---------------------------------------------------------------------------------------------------------------------
مقایسه نتایج:
به منظور مقایسه زمان پردازش از کد ذیل استفاده شده است. نتایج بدست آمده از این مقایسه در جدول 1 آورده شده است.
جدول 1 : مقایسه زمان پردازش روش های مختلف برای حل مسئله جمع 12 عدد
|
مدت زمان محاسبه برای حل مسئله (ثانیه) |
نام روش |
|
0.41 |
سریال |
|
0.685 |
موازی – روش اول |
|
0.699 |
موازی – روش دوم |
|
0.208 |
موازی – روش سوم |
|
0.193 |
موازی – روش چهارم |
کد کودا در ویژوال استودیو C++ این مسئله از لینک زیر قابل دریافت می باشد.
http://cdn.persiangig.com/preview/XRRMaETE86/cudaprogram1.rar
[1]. http://elmavaran.ir/1389.