基于vc++实现的矩阵乘优化软件

Barefoot

发布日期: 2020-05-21 10:03:58 浏览量: 428
评分：
star star star star star star star star star star_border
*转载请注明来自write-bug.com

一、实验名称

矩阵乘优化软件

二、实验目的及要求

  • C语言实现矩阵x向量算法

  • 矩阵要求CSR压缩存储格式,测试集选用佛罗里达州立大学测试集 http://www.cise.ufl.edu/research/sparse/matrices//

  • SSE优化，LOOP unrolling，software prefetch软件预取，多线程并行

  • 给出测试界面，运行时间及加速比结果

三、实验环境

  • 操作系统（开发）：Windows 7/Windows XP

  • 编程软件（开发）：Microsoft Visual Studio 2008

  • 操作系统（测试）：Windows 7

  • 硬件环境（测试）：Acer 4741G，i5双核处理器 460M

四、实验内容

根据实验要求，按照路径组合的形式将其分为三类：

  • 读入数据至内存方式：单线程读取文件、多线程读取文件、CSR格式读入

  • 乘法计算：单线程、多线程

  • SSE优化：有SSE优化、无SSE优化

3*2*2=12种 再加上传统算法一共13种算法组合。

五、算法描述及实验步骤

5.1 多线程编程

程序使用WIN32提供的多线程编程的接口（windows.h）函数实现，实验中用到的函数如下:

  1. HANDLE h = CreateThread(NULL,0,MulThread,pParam,0,NULL);//创建多线程
  2. DWORD WINAPI MulThread(LPVOID pParam);//线程函数
  3. WaitForSingleObject(h,INFINITE);//等待线程完成
  4. MulParam * pParam = (MulParam *)HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY,sizeof(MulParam));//为线程分配数据，实现传参
  5. MulParam * p = (MulParam *)pParam;  //线程内读取参数
  6. HeapFree(GetProcessHeap(),0,pParam);//线程内结束后销毁参数
  8. HANDLE hMutex = CreateMutex(NULL,FALSE,NULL);//创建互斥变量
  9. WaitForSingleObject(hMutex,INFINITE);//进入临界区
  10. ReleaseMutex(hMutex);//退出临界区
  12. HANDLE inputSemaphore;  //创建信号量
  13. WaitForSingleObject(inputSemaphore,INFINITE);//查看临界资源是否剩余
  14. ReleaseSemaphore(inputSemaphore,1,NULL);//释放临界资源

5.2 文件预取

使用消费者模型实现文件预取，具体实现是在内存中申请一块区域作为缓存，分别被读写线程共享，读数据与模型中的消费者对应，写数据与模型中的生产者对应。使用信号量机制实现读写同步，读写操作时均要获得读锁或写锁才能操作，以实现互斥访问。具体算法实现如下：

  1. queue<int> input;
  2. queue<int> output;
  3. HANDLE inputMutex = CreateMutex(NULL,FALSE,NULL);
  4. HANDLE outputMutex = CreateMutex(NULL,FALSE,NULL);
  6. /** 缓存数据使用后，将其设为可写状态 */
  7. void PushInput(int _i)
  8. {
  9.     WaitForSingleObject(inputMutex,INFINITE); 
  10.     input.push(_i);
  11.     ReleaseMutex(inputMutex);
  12.     ReleaseSemaphore(inputSemaphore,1,NULL);
  13. }
  15. /** 缓存数据写满后，将其设为可读状态 */
  16. void PushOutput(int _i)
  17. {
  18.     WaitForSingleObject(outputMutex,INFINITE); 
  19.     output.push(_i);
  20.     ReleaseMutex(outputMutex);
  21.     ReleaseSemaphore(outputSemaphore,1,NULL);
  22. }
  24. /** 获缓存写位置 */
  25. int PopInput()
  26. {
  27.     int value;
  28.     WaitForSingleObject(inputSemaphore,INFINITE);
  29.     WaitForSingleObject(inputMutex,INFINITE); 
  30.     value = input.front();
  31.     input.pop();
  32.     ReleaseMutex(inputMutex);
  33.     return value;
  34. }
  36. /** 获取缓存读位置 */
  37. bool isRight = true;
  38. int PopOutput()
  39. {
  40.     int value;
  41.     WaitForSingleObject(outputSemaphore,INFINITE);
  42.     WaitForSingleObject(outputMutex,INFINITE); 
  43.     if(isRight)
  44.     {
  45.         value = output.front();
  46.         output.pop();
  47.         if(fileThreadRunningCount == 0)
  48.         {
  49.             isRight = false;
  50.             ReleaseSemaphore(outputSemaphore,1,NULL);
  51.         }
  52.     }
  53.     else
  54.     {
  55.         value = -1;
  56.         ReleaseSemaphore(outputSemaphore,1,NULL);//TODO 释放所有的阻塞队列
  57.     }
  58.     ReleaseMutex(outputMutex);
  59.     return value;
  60. }

5.3 SSE优化

调用CPU提供的128位寄存器，试验中将4个浮点数一次性压入寄存器，调用乘法指令，计算完后将会把结果写在对应的寄存器中，再将其读出即可，具体算法如下：

  1. __m128 r1,res;
  2. ........
  3. r1.m128_f32[0]=node->matrix[j];
  4. r1.m128_f32[1]=node->matrix[j+1];
  5. r1.m128_f32[2]=node->matrix[j+2];
  6. r1.m128_f32[3]=node->matrix[j+3];
  7. res = _mm_mul_ps(_mm_set_ps(node->v[node->xj[j+3]], node->v[node->xj[j+2]], node->v[node->xj[j+1]], node->v[node->xj[j]]), r1);            
  8. result[i]=result[i]+res.m128_f32[0]+res.m128_f32[1]+res.m128_f32[2]+res.m128_f32[3];

5.4 生成CSR格式

矩阵文件存储格式：

  • 第一个数字：矩阵的列数

  • 第二个数字：矩阵的行数

  • 第三个数字：下面有效的行数

  • 行数据：列号 行号 值

例如：

表示矩阵：

向量文件存储格式：

  • 第一个数字：向量矩阵的行数

  • 下面表示向量矩阵各行的值

例如：

表示矩阵：

按照文件存储格式，将其转化成CSR存储格式，存放在内存，其具体实现如下：

  1. int sum=0;
  2. int current=0;
  3. for(i=0;i<node->row;i++)
  4. {
  5.     for(j=0;j<node->xr[i];j++)
  6.     {
  7.         node->matrix[sum]=coo[current].value;            
  8.         node->xj[sum]=coo[current].col-1;
  9.         sum++;
  10.         current++;
  11.     }
  12.     int t=4-node->xr[i]%4;
  13.     while(t%4)
  14.     {
  15.         node->matrix[sum]=0;
  16.         node->xr[i]++;
  17.         node->xj[sum]=0;
  18.         t--;
  19.         sum++;
  20.     }
  21.     //原先node->xr每个数据表示该行的数据数目，现在修改后表示每行第一个数的位置
  22.     if(i)
  23.     {
  24.         node->xr[i]=node->xr[i]+node->xr[i-1];
  25.     }
  26. }

六、调试过程及实验结果

本程序对各个算法的运算加速比进行统计，并用网页形式表现出来，如下图（并行乘法线程数为3，文件预取线程数为3）：

  • 由图中2-5、6-9、10-13，可以看出实现文件读取策略的选择是关键，以CSR格式提取数据效率最低，主要是由于其转化成CSR格式而须做数据排序算法，耗时较大；非预取是以单线程读取文件，由于其读入缓存即可使用，相比CSR方式效率有所提高；而预取使用多个线程读取文件，相比单线程读取文件效率又有相当大的提升

  • 由图中2-3、4-5、…、12-13，可以看出多线程计算乘法，反而效率略有所下降，这主要是CPU直接从内存及缓存访问数据效率极高，但是多个线程之间的不断切换反而不利于提高效率

  • 由图中2和4、3和5、…、11和13，看不出SSE优化得效果，可能是高速处理器计算效率极高，由于访存速度跟不上而导致瓶颈

综上所述，对SSE的优化几乎无影响，对乘法实现多线程效率反而有所下降，而对读取文件的优化，即软件预取是提升最大。

七、总结

在这次短学期中，我们学会了很多，在一开始什么都不知道的情况下，我们查看了很多资料，学会CSR压缩存储，学会用SSE优化，学会用多线程预取文件，并行运算出结果，在这个过程中解决并行时的冲突和同步问题，但是这个过程中还有点不足的事，我们一开始没有想好全局设计，使的后来的交接部分一而再再而三的改动，不过吃一堑，长一智，经验总是在坎坷后的。

八、附录

  • 算法实现和分工

    • A：CSR压缩 SSE优化
    • B： 并行运算 预取技术

  • 项目说明

    • 文件夹Matrix为程序用C++实现的全部算法，为了更好的分析实验数据，文件夹VIEW_RESULT是用C#实现的结果展现页面
上传的附件 cloud_download 基于vc++实现的矩阵乘优化软件.7z ( 2.61mb, 2次下载 )
error_outline 下载需要11点积分

keyboard_arrow_left上一篇 : 基于JAVA的记事本 基于WinPcap的网络包截获和分析系统 : 下一篇keyboard_arrow_right

comment 1
Barefoot
2020-05-21 10:02:30
基于vc++实现的矩阵乘优化软件
mode_comment 评论(0)

Barefoot

发送私信

任何值得做的，就把它做好

10
文章数
21
评论数
最近文章
highlight comment

Copyright @2020-WRITE-BUG.COM 技术支持 - YCY科技 - 备案/许可证编号：京ICP备16025663号-5

eject