Conway’s Game of Life中看C++SSE2并行化计算
2018-06-18 04:09:50来源:未知 阅读 ()
一、Conway’s Game of Life描述
康威生命游戏(英语:Conway's Game of Life),又称康威生命棋,是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。
1、规则
生命游戏中,对于任意细胞,规则如下。每个细胞有两种状态:存活或死亡,每个细胞与以自身为中心的周围八格细胞产生互动。
- 当前细胞为存活状态时,当周围低于2个(不包含2个)存活细胞时, 该细胞变成死亡状态。(模拟生命数量稀少)
- 当前细胞为存活状态时,当周围有2个或3个存活细胞时, 该细胞保持原样。
- 当前细胞为存活状态时,当周围有3个以上的存活细胞时,该细胞变成死亡状态。(模拟生命数量过多)
- 当前细胞为死亡状态时,当周围有3个存活细胞时,该细胞变成存活状态。 (模拟繁殖)
可以把最初的细胞结构定义为种子,当所有在种子中的细胞同时被以上规则处理后, 可以得到第一代细胞图。按规则继续处理当前的细胞图,可以得到下一代的细胞图,周而复始。随题给出了一个细胞图的不断演变过程,见Gospers_glider_gun.gif。
二、实现思路
2.1基本实现思路
- 输入数据格式
- 数据结构及实现思路
- 输入输出的问题
三、串行java实现
-
Conway2D
1 import java.io.*; 2 3 /** 4 * Java class for simulation of Conway's Game of Life. 5 */ 6 7 class Conway2D { 8 private final int width; 9 private final int height; 10 private final int size; 11 private byte[] data; 12 13 /** 14 * @param width 15 * @param height 16 */ 17 Conway2D(int width, int height) { 18 this.width = width; 19 this.height = height; 20 this.size = width * height; 21 data = new byte[size]; 22 } 23 24 25 /** 26 * 生命游戏迭代一次 27 */ 28 void iterate() { 29 byte[] prev = new byte[size]; 30 System.arraycopy(data, 0, prev, 0, size); 31 byte[] next = new byte[size]; 32 for (int i = 0; i < width; i++) { 33 for (int j = 0; j < height; j++) { 34 if (isAlive(i, j, prev)) { 35 next[j * width + i] = 49; 36 } else { 37 next[j * width + i] = 48; 38 } 39 } 40 } 41 System.arraycopy(next, 0, data, 0, size); 42 } 43 44 45 /** 46 * 检查cell是否存活 47 * 48 * @param x The x position 49 * @param y The y position 50 * @param d The grid data. 51 * @return 52 */ 53 54 private boolean isAlive(int x, int y, byte[] d) { 55 int count = 0; 56 int pos1 = y * width + x; 57 //循环该cell的周围,累计周围活细胞个数 58 for (int i = x - 1; i <= x + 1; i++) { 59 for (int j = y - 1; j <= y + 1; j++) { 60 int pos = j * width + i; 61 if (pos >= 0 && pos < size - 1 && pos != pos1) //如果点在圈内 并且 不是自己 62 { 63 if (d[pos] == 49) { 64 count++; 65 } 66 } 67 } 68 } 69 //如果该细胞死亡 70 if (d[pos1] == 48) { 71 return count == 3; 72 } else {//如果该细胞活着 73 return !(count < 2 || count > 3); 74 } 75 } 76 77 78 /** 79 * 读取文件中的数据 80 * 注意byte的不同,空格和换行在byte中的表示不同 81 * 82 * @param file 83 */ 84 void readData(String file) throws IOException { 85 BufferedInputStream in = new BufferedInputStream(new FileInputStream(file)); 86 ByteArrayOutputStream out = new ByteArrayOutputStream(1); 87 88 byte[] temp = new byte[1]; 89 int size; 90 while ((size = in.read(temp)) != -1) { 91 if (temp[0] != 32 && temp[0] != 10) { 92 out.write(temp, 0, size); 93 } 94 } 95 in.close(); 96 data = out.toByteArray(); 97 } 98 99 100 void writeToFile(String file) throws IOException { 101 FileOutputStream fos =new FileOutputStream(file); 102 BufferedInputStream bis = new BufferedInputStream(new ByteArrayInputStream(data)); 103 byte[] tmp = new byte[100]; 104 int size; 105 while((size = bis.read(tmp)) != -1){ 106 fos.write(tmp); 107 fos.write(new byte[]{10}); 108 } 109 } 110 }
- main
1 import java.io.IOException; 2 3 /** 4 * Created by anyuan on 2017/1/4. 5 */ 6 public class Main { 7 public static final int MAXTIMES = 50000; 8 9 public static void main(String[] args) { 10 Conway2D conway2D = new Conway2D(100, 50); 11 try { 12 conway2D.readData("C:\\Users\\anyuan\\IdeaProjects\\操作系统实验\\LifeGame\\input_50x100"); 13 double start = System.currentTimeMillis(); 14 for (int i = 0; i < MAXTIMES; i++) { 15 conway2D.iterate(); 16 } 17 double end = System.currentTimeMillis(); 18 System.out.println("运行时间:" + (end - start)/1000 + "秒");//应该是end - start 19 conway2D.writeToFile("output_java串行"); 20 } catch (IOException e) { 21 e.printStackTrace(); 22 } 23 } 24 }
四、C++串行和并行实现
- 读入数据//去空格读取
- 数据转换49to1//将48转换为0,49转换为1。
- 迭代50000次//思路为将第一遍历,一次性读入八个数据到__m128i寄存器,然后对该寄存器的数据周边八个数值进行相加。作为count以判断是否该存活。所以实际上只需要迭代50000/8次。
- 数据转换1to49//1转换成49,0转换成48
- 输出数据
Header.h
1 #pragma once 2 #include <algorithm> 3 #include <fstream> 4 #include <iostream> 5 #include <string> 6 #define D_SCL_SECURE_NO_WARNINGS 7 8 #define WIDTH 100 9 #define HEIGHT 50 10 #define MAXSIZE 50*100 11 12 class Conway2D 13 { 14 const int width; 15 const int height; 16 const int size; 17 int data[MAXSIZE]; 18 19 20 public: 21 Conway2D() : width(100), height(50), size(width * height) 22 { 23 } 24 25 Conway2D(int width, int height) 26 : width(width), 27 height(height), 28 size(width * height) 29 { 30 } 31 32 void iterate() 33 { 34 int prev[MAXSIZE]; 35 std::copy(data, data + size, prev); 36 int next[MAXSIZE]; 37 for (int i = 0; i < width; i++) 38 { 39 for (int j = 0; j < height; j++) 40 { 41 if (isAlive(i, j, prev)) 42 { 43 next[j * width + i] = 49; 44 } 45 else 46 { 47 next[j * width + i] = 48; 48 } 49 } 50 } 51 std::copy(next, next + size, data); 52 } 53 54 bool isAlive(int x, int y, int d[]) const 55 { 56 int count = 0; 57 int pos1 = y * width + x; 58 //循环该cell的周围,累计周围活细胞个数 59 for (int i = x - 1; i <= x + 1; i++) 60 { 61 for (int j = y - 1; j <= y + 1; j++) 62 { 63 int pos = j * width + i; 64 if (pos >= 0 && pos < size - 1 && pos != pos1) //如果点在圈内 并且 不是自己 65 if (d[pos] == 49) 66 ++count; 67 } 68 } 69 //如果该细胞死亡 70 if (d[pos1] == 48) 71 { 72 return count == 3; 73 } 74 //如果该细胞活着 75 return !(count < 2 || count > 3); 76 } 77 78 void readData(std::string file) 79 { 80 std::ifstream f1(file); 81 if (!f1) 82 std::cout << "文件打开失败" << std::endl; 83 char tmp[1]; 84 int count = 0; 85 while (count < MAXSIZE) 86 { 87 f1.read(tmp, 1); 88 if (tmp[0] == '1' || tmp[0] == '0') 89 { 90 data[count] = static_cast<int>(tmp[0]); 91 ++count; 92 } 93 } 94 } 95 96 void writeToFile(std::string file) 97 { 98 std::ofstream f1(file); 99 if (!f1) 100 std::cout << "文件创建失败" << std::endl; 101 char tmp[WIDTH]; 102 for (int i = 0; i < HEIGHT; ++i) 103 { 104 std::copy(data + i*WIDTH, data + (i + 1)*WIDTH, tmp); 105 f1.write(tmp,WIDTH); 106 f1.write("\n",1); 107 } 108 } 109 }; 110 111 112
Header_simd_2.h
1 #pragma once 2 #include <fstream> 3 #include <iostream> 4 #include <emmintrin.h>//sse2 5 #define D_SCL_SECURE_NO_WARNINGS 6 #define WIDTH 100 7 #define HEIGHT 50 8 #define MAXSIZE 50*100 9 10 class Conway2D_simd_2 11 { 12 const __int16 width; 13 const __int16 height; 14 const __int16 size; 15 __int16 data_s[MAXSIZE + 2 * WIDTH + 2];//这样就可以考虑边界cell的四周的cell了 16 __int16* data = &data_s[WIDTH + 1];//从data_s的WIDTH+1开始,到MAXSIZE+WIDTH+1结束 17 //之后要使用的8个寄存器 18 __m128i _m128_1; 19 __m128i _m128_2; 20 __m128i _m128_r; 21 __m128i _m128_s; 22 23 public: 24 25 Conway2D_simd_2(__int16 width, __int16 height) 26 : width(width), 27 height(height), 28 size(width * height) 29 { 30 for (int i = 0; i < MAXSIZE + 2 * WIDTH + 2; ++i) 31 { 32 data_s[i] = 48; 33 } 34 // data = &data_s[WIDTH + 1]; 35 } 36 37 void iterate() 38 { 39 __int16 prev[MAXSIZE]; 40 // std::copy(data, data + size, prev); 41 __int16 pos_s = 0; 42 for (; pos_s < MAXSIZE; pos_s += 8) 43 { 44 _m128_1 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s - WIDTH - 1])); 45 _m128_2 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s - WIDTH])); 46 _m128_r = _mm_add_epi16(_m128_1, _m128_2); 47 _m128_1 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s - WIDTH + 1])); 48 _m128_2 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s - 1])); 49 _m128_s = _mm_add_epi16(_m128_1, _m128_2); 50 _m128_r = _mm_add_epi16(_m128_r, _m128_s); 51 _m128_1 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s + 1])); 52 _m128_2 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s + WIDTH - 1])); 53 _m128_s = _mm_add_epi16(_m128_1, _m128_2); 54 _m128_r = _mm_add_epi16(_m128_r, _m128_s); 55 _m128_1 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s + WIDTH])); 56 _m128_2 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s + WIDTH + 1])); 57 _m128_s = _mm_add_epi16(_m128_1, _m128_2); 58 _m128_r = _mm_add_epi16(_m128_r, _m128_s); 59 for (int i = 0; i < 8; ++i) 60 { 61 //如果该细胞死亡 62 if (data[pos_s+i] == 0) 63 { 64 // if (_m128_r.m128i_i16[i] == 3) 65 // { 66 // _m128_r.m128i_i16[i] = 1; 67 // } 68 // else 69 // { 70 // _m128_r.m128i_i16[i] = 0; 71 // } 72 _m128_r.m128i_i16[i] = (_m128_r.m128i_i16[i] == 3); 73 } 74 else 75 { 76 //如果该细胞活着 77 // if(_m128_r.m128i_i16[i] == 2 || _m128_r.m128i_i16[i] == 3) 78 // { 79 // _m128_r.m128i_i16[i] = 1; 80 // } 81 // else 82 // { 83 // _m128_r.m128i_i16[i] = 0; 84 // 85 // } 86 _m128_r.m128i_i16[i] = (!(_m128_r.m128i_i16[i] < 2 || _m128_r.m128i_i16[i] > 3)); 87 } 88 } 89 _mm_storeu_si128(reinterpret_cast<__m128i *>(&prev[pos_s]), _m128_r); 90 } 91 std::copy(prev, prev + size, data); 92 } 93 94 95 void readData(std::string file) const 96 { 97 std::ifstream f1(file); 98 if (!f1) 99 std::cout << "文件打开失败" << std::endl; 100 char tmp[1]; 101 __int16 count = 0; 102 while (count < MAXSIZE) 103 { 104 f1.read(tmp, 1); 105 if (tmp[0] == '1' || tmp[0] == '0') 106 { 107 data[count] = static_cast<int>(tmp[0]); 108 ++count; 109 } 110 } 111 } 112 113 void writeToFile(std::string file) const 114 { 115 std::ofstream f1(file); 116 if (!f1) 117 std::cout << "文件创建失败" << std::endl; 118 char tmp[WIDTH]; 119 for (__int16 i = 0; i < HEIGHT; ++i) 120 { 121 std::copy(data + i * WIDTH, data + (i + 1) * WIDTH, tmp); 122 f1.write(tmp, WIDTH); 123 f1.write("\n", 1); 124 } 125 } 126 127 void dataFrom1to49() 128 { 129 for (int i = 0; i < MAXSIZE + 2 * WIDTH + 2; ++i) 130 { 131 if (data_s[i] == 1) 132 { 133 data_s[i] = 49; 134 } 135 else 136 { 137 data_s[i] = 48; 138 } 139 } 140 } 141 142 void dataFrom49to1() 143 { 144 for (int i = 0; i < MAXSIZE + 2 * WIDTH + 2; ++i) 145 { 146 if (data_s[i] == 49) 147 { 148 data_s[i] = 1; 149 } 150 else 151 { 152 data_s[i] = 0; 153 } 154 } 155 } 156 };
Source.cpp
1 #include "Header.h" 2 #include <time.h> 3 //#include "Header_simd.h" 4 #include "Header_simd_2.h" 5 #define MAXTIMES 50000 6 void main() 7 { 8 //串行 9 Conway2D conway2_d = Conway2D(100, 50); 10 conway2_d.readData("input_50x100"); 11 clock_t start_time = clock(); 12 for (int i = 0; i < MAXTIMES; ++i) 13 { 14 conway2_d.iterate(); 15 } 16 clock_t end_time = clock(); 17 std::cout << "串行 Runing time is:" << static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC << "s" << std::endl; 18 conway2_d.writeToFile("output_Cpp串行"); 19 20 // //并行 21 // Conway2D_simd conway2_d_simd = Conway2D_simd(100, 50); 22 // conway2_d_simd.readData("input_50x100"); 23 // clock_t start_time_simd = clock(); 24 // for (int i = 0; i < MAXTIMES; ++i) 25 // { 26 // conway2_d_simd.iterate(); 27 // } 28 // clock_t end_time_simd = clock(); 29 // std::cout << "Runing time is:" << static_cast<double>(end_time_simd - start_time_simd) / CLOCKS_PER_SEC << "s" << std::endl; 30 // conway2_d_simd.writeToFile("output_Cpp并行"); 31 32 //并行2 33 Conway2D_simd_2 conway2_d_simd_2 = Conway2D_simd_2(100, 50); 34 conway2_d_simd_2.readData("input_50x100"); 35 conway2_d_simd_2.dataFrom49to1(); 36 clock_t start_time_simd_2 = clock(); 37 for (int i = 0; i < MAXTIMES; ++i) 38 { 39 conway2_d_simd_2.iterate(); 40 } 41 clock_t end_time_simd_2 = clock(); 42 std::cout << "并行2 Runing time is:" << static_cast<double>(end_time_simd_2 - start_time_simd_2) / CLOCKS_PER_SEC << "s" << std::endl; 43 conway2_d_simd_2.dataFrom1to49(); 44 conway2_d_simd_2.writeToFile("output_Cpp并行_2"); 45 system("pause"); 46 }
五、SIMD介绍和C++并行思路
SIMD简要介绍
SIMD intrinsics有一些类似于C语言中的函数,可以被其它代码直接调用,可以像其它函数一样给它传递参数,Intel C++编译器支持SIMD intrinsics(VS2005/2010也支持,GCC也支持),并且可以针对函数进行内联等优化。需要包含的头文件:
#include //MMX #include //SSE (include mmintrin.h) #include //SSE2 (include xmmintrin.h) #include //SSE3 (include emmintrin.h)
这些头文件定了一些数据类型对应于那些SIMD指令要适应的浮点数和整数。
这些数据类型名以两个下划线开始:
__m64用于表示一个MMX寄存器的内容,用于64bi的MMX整数指令,可以封装正8个8bit,4个16bit,2个32bit和一个64bit的整数。
__m128用于SSE,表示封装了四个32bit的单精度浮点数的SSE寄存器。
__m128d可以封装2个64bit的双精度浮点数
__m128i用于表示支持128bi的内存变量,位于16B的边界。声明为__m64的内存变量位于8B的边界。
SSE(一种SIMD指令集)基本操作
SSE的基本命令有以下几种:
- load系列命令(读取连续的内存内容到寄存器中)
- set系列命令(读取内存内容到寄存器中,与load的区别在于不要连续,可以传入多个参数)
- 算数逻辑系列命令(这些命令和汇编比较类似,执行一些简单的算数和逻辑操作)
- store系列命令(把寄存器内容存储到内存中)
SSE基本操作流程:
- load/set指令把内存数据读取到寄存器中。
- 算数指令对寄存器进行相应的操作。
- store指令将操作结果存回到内存中。
SSE指令格式
SSE另外要注意的事项
#include <intrin.h> __declspec(align(16)) float op1[4] = {1.0, 2.0, 3.0, 4.0};
本例中使用的寄存器和数据类型
typedef union __declspec(intrin_type) __declspec(align(16)) __m128i { __int8 m128i_i8[16]; __int16 m128i_i16[8]; __int32 m128i_i32[4]; __int64 m128i_i64[2]; unsigned __int8 m128i_u8[16]; unsigned __int16 m128i_u16[8]; unsigned __int32 m128i_u32[4]; unsigned __int64 m128i_u64[2]; } __m128i;
本例用__m128i存8个__int16数据。
一次迭代的操作
void iterate() { __int16 prev[MAXSIZE]; // std::copy(data, data + size, prev); __int16 pos_s = 0; for (; pos_s < MAXSIZE; pos_s += 8) { _m128_1 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s - WIDTH - 1])); _m128_2 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s - WIDTH])); _m128_r = _mm_add_epi16(_m128_1, _m128_2); _m128_1 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s - WIDTH + 1])); _m128_2 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s - 1])); _m128_s = _mm_add_epi16(_m128_1, _m128_2); _m128_r = _mm_add_epi16(_m128_r, _m128_s); _m128_1 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s + 1])); _m128_2 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s + WIDTH - 1])); _m128_s = _mm_add_epi16(_m128_1, _m128_2); _m128_r = _mm_add_epi16(_m128_r, _m128_s); _m128_1 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s + WIDTH])); _m128_2 = _mm_loadu_si128(reinterpret_cast<__m128i const*>(&data[pos_s + WIDTH + 1])); _m128_s = _mm_add_epi16(_m128_1, _m128_2); _m128_r = _mm_add_epi16(_m128_r, _m128_s); for (int i = 0; i < 8; ++i) { //如果该细胞死亡 if (data[pos_s+i] == 0) { // if (_m128_r.m128i_i16[i] == 3) // { // _m128_r.m128i_i16[i] = 1; // } // else // { // _m128_r.m128i_i16[i] = 0; // } _m128_r.m128i_i16[i] = (_m128_r.m128i_i16[i] == 3); } else { //如果该细胞活着 // if(_m128_r.m128i_i16[i] == 2 || _m128_r.m128i_i16[i] == 3) // { // _m128_r.m128i_i16[i] = 1; // } // else // { // _m128_r.m128i_i16[i] = 0; // // } _m128_r.m128i_i16[i] = (!(_m128_r.m128i_i16[i] < 2 || _m128_r.m128i_i16[i] > 3)); } } _mm_storeu_si128(reinterpret_cast<__m128i *>(&prev[pos_s]), _m128_r); } std::copy(prev, prev + size, data); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:【帕斯卡三角形(杨辉三角)】
下一篇:深究标准IO的缓存
- CF1215DTicketGame——(博弈) 2020-04-25
- AtCoder agc007_d Shik and Game 2020-02-08
- 《游戏引擎构架Game Engine Architecture》略读笔记 2019-09-23
- FZU - 2295 Human life (最大权闭合子图) 2019-08-16
- kuangbin专题 专题一 简单搜索 Fire Game FZU - 2150 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash