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

Barefoot

发布日期: 2020-05-21 10:03:58 浏览量: 100
评分:
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);//线程内结束后销毁参数
  7. HANDLE hMutex = CreateMutex(NULL,FALSE,NULL);//创建互斥变量
  8. WaitForSingleObject(hMutex,INFINITE);//进入临界区
  9. ReleaseMutex(hMutex);//退出临界区
  10. HANDLE inputSemaphore; //创建信号量
  11. WaitForSingleObject(inputSemaphore,INFINITE);//查看临界资源是否剩余
  12. 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);
  5. /** 缓存数据使用后,将其设为可写状态 */
  6. void PushInput(int _i)
  7. {
  8. WaitForSingleObject(inputMutex,INFINITE);
  9. input.push(_i);
  10. ReleaseMutex(inputMutex);
  11. ReleaseSemaphore(inputSemaphore,1,NULL);
  12. }
  13. /** 缓存数据写满后,将其设为可读状态 */
  14. void PushOutput(int _i)
  15. {
  16. WaitForSingleObject(outputMutex,INFINITE);
  17. output.push(_i);
  18. ReleaseMutex(outputMutex);
  19. ReleaseSemaphore(outputSemaphore,1,NULL);
  20. }
  21. /** 获缓存写位置 */
  22. int PopInput()
  23. {
  24. int value;
  25. WaitForSingleObject(inputSemaphore,INFINITE);
  26. WaitForSingleObject(inputMutex,INFINITE);
  27. value = input.front();
  28. input.pop();
  29. ReleaseMutex(inputMutex);
  30. return value;
  31. }
  32. /** 获取缓存读位置 */
  33. bool isRight = true;
  34. int PopOutput()
  35. {
  36. int value;
  37. WaitForSingleObject(outputSemaphore,INFINITE);
  38. WaitForSingleObject(outputMutex,INFINITE);
  39. if(isRight)
  40. {
  41. value = output.front();
  42. output.pop();
  43. if(fileThreadRunningCount == 0)
  44. {
  45. isRight = false;
  46. ReleaseSemaphore(outputSemaphore,1,NULL);
  47. }
  48. }
  49. else
  50. {
  51. value = -1;
  52. ReleaseSemaphore(outputSemaphore,1,NULL);//TODO 释放所有的阻塞队列
  53. }
  54. ReleaseMutex(outputMutex);
  55. return value;
  56. }

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 下载需要13点积分

发送私信

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

10
文章数
21
评论数
最近文章
eject