单线程计算矩阵相乘
开发一个单线程的程序，分别计算不同规模矩阵的乘积，并记录矩阵相乘花费的时间；
从文件中读取矩阵的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static void readMatrix(double[][] matrix, String fileName) {
String pathName = "./mx/" + fileName + ".txt";
try (FileReader fr = new FileReader(pathName); BufferedReader br = new BufferedReader(fr)) {
String line;
int cntLine = 0;
while ((line = br.readLine()) != null) {
String[] nums = line.split(" ");
for (int i = 0; i < nums.length; i++) {
matrix[cntLine][i] = Double.valueOf(nums[i]).doubleValue();
}
cntLine++;
}
} catch (IOException e) {
e.printStackTrace();
}
}
|
两矩阵相乘的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static double[][] multiple(double[][] matrixA, double[][] matrixB) {
int rows = matrixA.length;
int cols = matrixA[0].length;
double[][] res = new double[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
for (int k = 0; k < cols; k++) {
res[i][j] += matrixA[i][k] * matrixB[k][j];
}
}
}
return res;
}
|
main函数
- 根据不同的规格读取矩阵文件
- 进行矩阵乘法计算
- 输出计算的耗时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static void main(String[] args) {
int[] sizes = {64,128,512,1024};
Date start,end;
double[][] matrixA= new double[size][size];;
double[][] matrixB= new double[size][size];;
for(int i = 0;i<sizes.length;i++){
size = sizes[i];
matrixA = new double[size][size];
matrixB = new double[size][size];
start = new Date();
readMatrix(matrixA, "M" + size + "A");
readMatrix(matrixB, "M" + size + "B");
double[][] ans = multiple(matrixA, matrixB);
end = new Date();
System.out.println("单线程串行计算" + size + "x" + size + "矩阵乘法耗时：" + (end.getTime() - start.getTime()) + "ms");
}
}
|
运行结果
结果分析
算法复杂度分析
矩阵相乘的时间复杂度为O(N³)
64x64矩阵相乘大约需要运算260 000次=2.6x10^5^
128x128矩阵相乘大约需要运算2 100 000次=2.1x10^6^
512x512矩阵相乘大约需要运算130 000 000次=1.3x10^8^
1024x1024矩阵相乘大约需要运算1 070 000 000次=1.07x10^9^
运行环境分析
笔记本CPU i5-8250U 四核八线程 主频1.6GHz = 每秒计算上限为1.6x10^9^
由于当前是单线程运行，所以理论上限应该是每秒运算2x10^8^次
加上笔记本CPU会自动降频以减少能耗，所以实际的运算速度会比理论上限低
运行结果分析
各规格矩阵相乘耗时 基本和 理论计算值÷理论计算速度 吻合
四线程计算矩阵相乘
开发一个 4 线程的程序，分别计算 16x16 128x128 512x512 矩阵的乘积，并记录矩阵相乘花费的时间；
定义运算线程类
- 每个线程需要被分配各自的任务来实现多线程矩阵计算
- 比如新建2个线程，一个矩阵应该负责1,3,5…列的计算，另一个矩阵负责2,4,6…列的计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class MatrixThread implements Runnable {
private int start;
private double[][] A;
private double[][] B;
private double[][] C;
public MatrixThread(int start, double[][] A, double[][] B, double[][] C) {
this.start = start;
this.A = A;
this.B = B;
this.C = C;
}
@Override
public void run() {
for (int i = start; i < MatrixMultiple.size; i += MatrixMultiple.totalThreads) {
for (int j = 0; j < MatrixMultiple.size; j++) {
for (int k = 0; k < MatrixMultiple.size; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
}
}
|
使用所定义的线程计算矩阵
- 建立线程数组
- 初始化每个线程
- 启动每个线程
- 在线程运行完之后终止线程
- 检验多线程计算的矩阵结果和单线程计算的结果是否相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| public static void main(String[] args) {
int[] sizes = { 64, 128, 512, 1024 };
Date start, end;
double[][] matrixA = new double[size][size];
double[][] matrixB = new double[size][size];
for (int k = 0; k < sizes.length; k++) {
size = sizes[k];
matrixA = new double[size][size];
matrixB = new double[size][size];
start = new Date();
readMatrix(matrixA, "M" + size + "A");
readMatrix(matrixB, "M" + size + "B");
double[][] ans = multiple(matrixA, matrixB);
end = new Date();
long time1 = end.getTime() - start.getTime();
System.out.println("单线程串行计算" + size + "x" + size + "矩阵乘法耗时：" + time1 + "ms");
Thread[] threads = new Thread[totalThreads];
double[][] matrixC = new double[size][size];
for (int i = 0; i < totalThreads; i++) {
threads[i] = new Thread(new MatrixThread(i, matrixA, matrixB, matrixC));
}
start = new Date();
for (int i = 0; i < totalThreads; i++) {
threads[i].start();
}
for (int i = 0; i < totalThreads; i++) {
try {
threads[i].join();
} catch (Exception e) {
e.printStackTrace();
}
}
end = new Date();
long time2 = end.getTime() - start.getTime();
System.out.println(
totalThreads + "线程并行计算" + size + "x" + size + "矩阵乘法耗时：" + time2 + "ms");
double rate = 1.0*(time1-time2)/time1;
System.out.printf(
totalThreads + "线程并行计算" + size + "x" + size + "矩阵乘法的节约时间比例为%.2f\n", rate);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (ans[i][j] != matrixC[i][j]) {
System.out.println("第" + i + "行" + "第" + j + "列不相等");
}
}
}
System.out.println();
}
}
|
运行结果
当前耗时只考虑多线程计算的时间，没有把创建线程和初始化线程的时间算进去
结果分析
- 可以看到由于CPU最大支持8线程，所以在4线程的情况下是能做到并行的
- 4线程并行情况下运算耗时大约为单线程情况下的四分之一
- 矩阵规模越大，节约比例越接近0.75
- 这里我只用了四个线程进行计算，但是却可以发现这边显示的CPU0-7的利用率都同时提升了
- 按理来说，4个线程应该最多只能在4个核上运行
- 原因是，事实上这个CPU在物理上就是4个内核，只是在逻辑上抽象成了8个逻辑处理器
- 可以理解为我把现在雇佣了四个厨师，每个厨师可以同时两只手做两个菜，即左手做一份菜，右手做一份菜
- 现在我派这四个厨师每人做一份菜
- 他们现在很省力，因为可以左手做半份菜，右手做半份菜
- 这对于他们来说只需要花费50%的力气就足够了
十六线程计算矩阵相乘
- 定义线程类和计算代码类似，在此不再赘述
- 只需要改线程数即可
public static int totalThreads = 16;
运行结果
- 可以在任务管理器中明显看到，在进行多线程计算时，CPU利用率显著提高，甚至直接跑满了
- 利用win10自带的资源监视器也可以很明显地看到了是8个核的利用率都满了
结果分析
- 16线程的理论节约时间比例应该是$15/16 = 0.9375$
- 但是实际上由于CPU只支持最大8线程并行，所以即使创建了16线程，也没有能做到16线程并行
- 所以理论节约时间比例的上限只有$7/8 = 0.875$
- 可以看到这次运行时间节约比例和理论值差的很多
- 16线程（实际是8线程）计算的所花的时间甚至比4线程计算的时间还要长
- 个人理解是JVM在线程调度的时候开销增加，导致16进程计算矩阵相乘的时候浪费了大量时间进行线程方面的操作
- 当然由于本身系统环境本身也不是不变的，所以也有可能是其他进程对该程序的影响。
- 在这个情况下，这四个厨子（四个物理核心）
- 我让他们每人做两份菜
- 他们每人左手做一份，右手做一份（每个核心抽象成两个逻辑处理器）
- 因此他们已经达到了自己的极限
线程学习总结
- 合理利用多线程可以有效的增加计算速度
- 相对与单线程来说，多线程的编程会更加复杂
- 过多的线程数并不一定能节省时间，可能会导致计算时间的增加