多线程编程起步：矩阵乘法的任务分配

操作系统多线程编程课程设计完工后记

多线程确实是很浪漫的一个话题，不过在我还没有了解到更底层内容的现在，这种需要做性能分析的工作我还是不要尝试用Java这种高深莫测的虚拟机语言吧吧吧吧吧吧。

---

缘起

先贴一下选题及大致要求：

• A类

  1. 线程安全型双向链表
  2. 线程安全型栈
  3. 线程安全型队列

  要求对数据结构进行多线程读写测试数据正确性，读写操作需以模拟指令的形式。对于任务分配策略

  要求采用抢占与固定分配两种策略

  要求列出每个线程起止时间、所处理的命令条数、耗时，再列出总耗时。

• B类

  1. 并行最短路径计算：地图信息存放在map文件中，该地图至少包含2000个结点
  2. 并行排序：需要排序的数字是整数，存放于一个data文件中，大约有100万的数据量。
  3. 并行矩阵乘法：矩阵A和矩阵B都存放于matrix文件中，大小都为1024*1024，写程序计算矩阵A和B的乘积。（1）在你的电脑中运行，几个线程的计算速度最快？给出你的图表和数据分析（2）如何通过优化你的数据结构和计算过程，提高计算效率，缩短计算时间？请以图表的形式给出你每次优化后的程序版本的计算时间，分析计算速度提升的原因。
  4. 图像批量二值化：图像数量≥2000
  5. 页面图像切分
  6. 多线程书法字匹配（这老师就是搞书法字体匹配的）
  7. 多线程爬虫

我不得不吐槽一下这个所谓的操作系统课程设计，题目不是要求实现线程安全的数据结构就是要求实现多线程需求的性能分析，在我看来这完全就是应用层面的东西，完全跟底层实现没有一点关系。在去年我曾留意过操作系统课设的要求，那时候还是要求学生去模拟操作系统的某些调度算法，今年估计是要冲什么业绩，把大纲改得又红又专不说，题目被改成这个样子，指导老师也是一言难尽。但话说回来也没有什么办法，固然有些勇士是敢于等到之后再考虑修这门课，但我不太愿意将本不该有任何课程的学期添上一件可以半年前就搞定的破事，于是便开始了为期2周的多线程编程学习。

弯路

考虑课设要求进行性能分析，所以权衡之下我选择了并行矩阵乘法，毕竟矩阵乘法是早已学过的数学知识，相当于业务需求已经烂熟于心，只需要学好多线程就可以开工。

矩阵乘法是一个非常好理解的模型，在我的设想中，由用户给出矩阵的规模$n$，接着由系统生成两个符合规模的方阵$A$和$B$，然后再由用户设置计算时的线程数，系统通过多线程计算将结果存入结果矩阵$R$，并记录每次计算的相关信息与耗时，且以合适的可视化方案反馈给用户。

在学了个七七八八之后，我开始思考如何让这么多线程去合理地计算几百万个数据，从而得到由100多万个元素组成的结果矩阵，摆在我面前的有两种方案，一是加锁，或许更符合指导老师的本意；二是无锁，追求更好的性能。

由于深受线程同步理念的毒害，我决定给并行矩阵乘法加锁，每个线程每次计算一个元素，多个线程通过抢占的方式共同完成所有的计算任务，通过设置一个共享的自增计数器来判断计算过程是否结束。这看起来非常合理，是一个好办法，非常典型的多线程程序模型对吧，但是我发现一个可能因为我没有深入研究而没有解决的问题：当我将这个计算过程包装在一个循环中以便探寻在不同并发数下的耗时情况时，除了第一次外，其余轮次计算的耗时全部被“优化”成了0ms，我确信我的代码逻辑没有问题，那会不会是循环中的整个计算过程并没有那么完整？于是我将读取数据的方法也添加到循环体中，这一次很幸运，每一次的耗时都是通过真实运行计算出来的，但是每次计算都要从！文！件！去读数据，这是一件很恐怖的事情，对于1024×1024规模的矩阵，还是2个，光是读数据就要耗费七八秒的时间，这为了得到测试数据就要花几天时间，对于期望赶紧速通这个课设的我来说是万万不行的。

现在看来对于矩阵乘法而言事实上没有任何加锁的必要，或者说我设计的加锁模式就存在问题，因为在我设想的矩阵乘法模型中并没有临界资源这一概念，因为即便要对结果矩阵$R$进行写操作，其各个元素之间都是相互独立的，元素运算顺序对最终结果没有任何影响，而对于矩阵$A$和$B$则只有读操作。退一步说，即使要把结果矩阵$R$看成一个整体，由于整个运算的输入输出是严格映射的，因此并发情况下也是对结果矩阵的不同元素进行写操作，不会出现冲突。

但耗时被优化的问题我没有找到原因，猜想是与Java内部的同步机制有关，因为我的设计思想并没有入侵相关源码，出于对未知领域的严谨，有时间我会尝试进一步研究原因。

---

线程任务分配

于是一夜回到解放前，我着手开始考虑无锁方案，一个非常关键的事情是，在【将计算结果的一个元素作为一个子任务】这个前提下，如何安排这一百多万个子任务。这是一个严肃的问题，因为子任务的安排模式将直接决定每个线程需要执行的子任务数量，而其中背负子任务最多的那个苦逼线程就直接决定了本次计算的耗时，因此这个安排模式必须尽力保证每个线程分配到的子任务数量是均匀的，这样就可以保证最累的线程和最轻松的线程所计算的子任务只相差1，换句话说，不管并发线程数怎么变化，各线程执行的最大子任务数只比最小子任务数多1，而对于这个时代的CPU，计算矩阵乘法一个元素的耗时，相较于每个线程计算数万甚至数十万个元素的耗时，几乎可以忽略不计了，所以我们可以认为达到了平均分配任务的目的。

因此，我的最终目标就是：比如说对于4×4规模的方阵，假设有7个线程并发计算矩阵乘法，那么每个线程计算的子任务如下：

Thread-0: [0][0] [1][3] [3][2] 
Thread-1: [0][1] [2][0] [3][3] 
Thread-2: [0][2] [2][1] 
Thread-3: [0][3] [2][2] 
Thread-4: [1][0] [2][3] 
Thread-5: [1][1] [3][0] 
Thread-6: [1][2] [3][1] 

这看起来真的很美妙，把所有的子任务都按列挨个儿分给所有线程，分完整列还剩下的就顺延到下一列，多么直观的逻辑，而它实现起来也是异常简单。

首先我们先定义一个表，我擅自将它命名为任务分配表，aka英文名TAT(Tasks Assignment Table)，TAT能够表达上面这个例子的含义，但形式上需要转变一下，后面会讲到。

光有这个表还不够，我们需要为所有的子任务编号，对于规模为$n×n$的矩阵，计算得到的结果矩阵规模也为$n×n$，包含$n^2$个元素，那么编号就从1到$n^2$，例如对于4×4规模的矩阵，编号就从1到16。

准备工作就到此结束，接下来开始表演。

首先需要确定TAT的规模，确保它能够保存所有的子任务序号，因此通过$n^2\ mod\ nThreads$，即任务数对线程数取余得到余数，如果余数是0，说明能够正好均分，否则说明需要对TAT增加一列存放剩余的子任务。

TAT的每一行的行号代表线程号，这一行中的元素代表本线程需要执行哪些任务，但是作为一个整型的二维数组，TAT很难表达出$[0][0]$这样的含义，于是我们可以借助刚刚的子任务编号构建一个映射，我称之为【子任务序号——TAT映射】，顾名思义，这是把子任务序号映射在TAT上的过程，这样就能够用数字来表示各元素的下标了。

整个过程需要两次遍历矩阵来实现，当然它们之间事实上是存在数学关系的，能够用一次循环来实现，但数学总是不简单的，因此这里我们怎么简单怎么来。第一次遍历是对需要映射的位置进行标记，第二次通过按列遍历TAT来在相应位置上赋值，闲言少叙，直接看代码：

其实这个遍历的方案是我在想到优化手段之后反过来实现的，在我自己的项目中实际上是用了那一层数学关系，在报告中写优化策略时提出了这种基于二次遍历的分配策略。

int nTasks = length * length;

// build tasksTable[][]
int[][] tasksTable;

// initialize tasksTable size
if (nTasks % nThreads == 0) {
    tasksTable = new int[nThreads][nTasks / nThreads];
} else {
    tasksTable = new int[nThreads][nTasks / nThreads + 1];
}

// load all tasks to tasksTable[][]
// 将所有子任务序号映射到任务分配表
int nTask = 1; // 设定子任务序号遍历初始值为1
// 按列遍历任务分配表中与子任务数量相同的元素数量
for (int j = 0; j < tasksTable[0].length; j++) {
    for (int i = 0; i < tasksTable.length; i++) {
        // 当子任务序号小于等于子任务数量时将当前元素置1
        if (nTask <= nTasks) {
            tasksTable[i][j] = 1; // 进行置1操作
            nTask++; // 子任务序号递增
        }
    }
}
nTask = 1; // 重置子任务序号遍历初始值为1
// 按行遍历任务分配表，对其中所有置1的元素赋值子任务序号
for (int j = 0; j < tasksTable[0].length; j++) {
    for (int i = 0; i < tasksTable.length; i++) {
        if (tasksTable[i][j] == 1) {
            tasksTable[i][j] = nTask;
            nTask++;
        }
    }
}

---

线程内部运算

下一步操作是线程内部的运算过程。我们假设子任务的编号是按矩阵横向遍历顺序递增的，于是这个编号与矩阵的元素下标之间也是存在数学关系的，可以找出规律：
$$
i=\lfloor\frac{nTask-1}{matrix.length}\rfloor
$$

$$
j=(nTask-1)\ mod\ matrix.length
$$

这样就能根据编号$nTask$计算出要求的元素下标$matrix[i][j]$。

public void multiplyAssignedElements(int[] tasksGroup) {
    // 遍历接收到的子任务组中所有元素
    for (int nTask : tasksGroup) {
        // 由于子任务组中可能存在0，需要将其忽略
        if (nTask != 0) {
            // 将子任务序号映射为结果矩阵的元素下标[i][j]
            int i = (nTask - 1) / result.length;
            int j = (nTask - 1) % result.length;
            // 计算矩阵A的第i行与矩阵B的第j列进行矩阵乘法运算得到结果C[i][j]
            for (int k = 0; k < result.length; k++) {
                result[i][j] += matrixA[i][k] * matrixB[k][j];
            }
        }
    }
}

---

优化

为了方便理解任务分配的过程，使子任务竖着排队无疑是最直观的方案，但性能却不是最高的，要解释这个问题需要了解一些底层知识。

首先，在编译器的眼中没有多维数组的概念，所有多维数组都被横向拉长成一行放在内存中，但由于数组元素可以通过下标直接访问，编译器会根据下标直接计算出数组元素的实际地址，因此访问数据元素的不同方式没有明显的性能差距。

接下来需要了解一下局部性原理：在现代计算机的存储体系中，存在多个寄存器以及多级高速缓存，CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。这时候联系一下上一条可以发现，如果现在CPU读取的元素是$[0][0]$，寄存器中很有可能缓存了$[0][1]$而不太可能缓存了$[1][0]$，因此，由于按列分配的模式会导致TAT的行元素之间相互割裂，局部性原理难以发挥作用。

但有意思的是，在上述这种分配策略下，只需要互换28与29行就可以实现按行分配子任务了，分配效果就像这样：

Thread-0: [0][0] [0][1] [0][2] 
Thread-1: [0][3] [1][0] [1][1] 
Thread-2: [1][2] [1][3] 
Thread-3: [2][0] [2][1] 
Thread-4: [2][2] [2][3] 
Thread-5: [3][0] [3][1] 
Thread-6: [3][2] [3][3] 

如果你已经明白了上述的简单策略，那么恭喜你，你已经有了多线程编程的思想钢印，只要了解一下你喜欢的语言中多线程的语法，就可以尝试慢慢搭建整个项目了。

---

如果你也想试试

最后来回答一下开头我为什么说不要用Java可能会更好。

主要是在做性能分析的时候，第一步自然是计算耗时 —— 就是在启动计算之前记录一下时间，计算完毕后再记录一下时间，二者相减就得到了计算耗时，当然也可以更细致地记录各线程的运行时间，只是当时我觉得没必要，而且也并没有因为这一点被要求改进或者影响成绩。

事实上在中期答辩上看到了一些项目被要求记录各线程耗时，一方面我觉得这种要求很抽象，另一方面，对于这个项目来说，记录下各线程耗时并不会对性能分析产生任何帮助，因为从任务分配策略上就做到了最大限度的均匀分配，不存在任务抢占，自然也就不存在线程获取的任务数量不均导致出现部分线程耗时极短或极长的问题，并且当时我的开发进度已经过半，正在设计UI及相关逻辑，而这样的改动也会对整个数据分析模块的设计产生很大的影响，所以还是勇了一把而没有去做。

但是在测试过程中，发现数据的变化规律并不足够稳定，也就是说重复执行设计的测试方案，发现每次的耗时曲线都有些许差异，而且是在我已经禁用睿频的前提下，这意味着风扇几乎不会满载，电脑也几乎不会发热。

我不禁有些诧异，思来想去认为是JVM —— 或者说别的VM可能也一样 —— 可能并没有直接与操作系统和CPU交互来得准确，而我不可能真的把频率限制到1GHz的水平来更细致地观察，那样又会大大拉长测试的时间，最后我也只能是在测试出比较合理的曲线时及时采用。

所以如果有朋友看到也想实现一下这个项目的话，可以用C/C++/Go/Rust等等这类编译型语言来尝试一下，对于Windows平台也可以用C#来实现，而Python、Java、JavaScript/Node这类包含VM的解释型语言在性能分析方面或许会存在一些不准确的因素。

注：以上内容只是我的猜测，我不排除这些不稳定现象与我的代码质量和运行环境存在一定关系，而很遗憾我只对Java有些许了解，所以在未来我也可能会尝试用别的语言实现，各位有兴趣也可以试试。

---

后记

我可以理解多线程爬虫需要设计UI来展示信息，也可以理解最短路径可以用真正意义上的地图来呈现，但是我理解不了非强制性的UI实现最后却连线程安全型数据结构都要求设计界面来展示信息。

为了要求的UI界面，必须要展示更多信息，展示更多信息就要写更多代码，况且UI线程占用系统资源的能力并不逊于多线程编程自身。虽然相较于写后端逻辑我更喜欢前端的那种表现力，但是我也对为这玩意儿开发UI感到厌恶。即便我在学习多线程的时候发现自己对多线程还比较感兴趣，但明明是关于底层设计的课设被改成提升应用层不说，更甚的是UI的加入彻底地将其变成了一个独立的应用程序，把这个课设的核心完全移出操作系统这个范围了，根本就不属于操作系统的项目。

我感兴趣的方向好像是两个极端，一是完全地与用户互动，二是彻底地与开发者交互。在我刚开始Hello World的时候，我首先想知道的就是怎么实现输入，因为实现了输入就意味着我可以控制程序运行的方向，这个程序的控制权在我的手中，慢慢地就不再仅仅乐于在命令行里折腾，想去实现真正的界面，那种灵动的布局、流畅的动效和严谨的适配，真是浪漫的美学与严肃的工程的完美结合，所以去做大前端，去用图形界面与屏幕前的你开展无声的交流，这是我能想到的代码与人类之间最友好的沟通方式。

对我来说，写多了代码很不幸地激发了我对“程序是怎样产生的”这样一个话题有了好奇，不过即便是在编译原理课上学习了词法分析&语法分析&一点点语义分析，没有写过一行相关代码的我也感受不到这就能把我写的代码变成一个 .o、.class或者 .exe，所以还是很好奇这个编译的过程。在无意间翻了几十篇网刊文章后算是找到了一些有关底层原理的系列文章，希望自己有时间去跟随这些牛人，在未来有这样的可能去为框架、工具链、编译器贡献一行自己的代码。

---

附录

其实没有采用这么高级的算法，只是放在这里，也许未来有时间会研究。

并行矩阵乘法——Cannon算法的原理实现以及性能评测