18308045-谷正阳-并行与分布式计算作业4-v11

【文章标题】：Foster并行程序设计方法在1000x1000矩阵与1000x1向量乘法中的应用 【文章摘要】：本文详细介绍了如何利用Foster并行程序设计方法来计算1000x1000矩阵与1000x1向量的乘积，包括并行计算的四个关键步骤：数据分区（Partitioning）、通信（Communication）、聚合（Agglomeration）和映射（Mapping）。同时，通过实验结果验证了这种方法的有效性。 【正文】： 在并行计算领域，Foster并行程序设计方法是一种常见的策略，它强调通过数据并行性、管道并行性和任务调度来优化计算效率。在这个作业中，谷正阳同学采用该方法解决了一个具体的计算问题：1000x1000矩阵与1000x1向量的乘积。以下是详细的过程： 1. 数据分区（Partitioning） 为了并行化计算，矩阵被划分为独立的部分，每行作为一个任务。由于矩阵乘法的性质，每一行可以独立计算，没有数据依赖。因此，可以并行处理这些行，充分挖掘数据并行性。 2. 管道并行性（Pipeline Parallelism） 在乘法运算之后，需要对结果进行求和。为了进一步提高效率，采用管道并行，同时进行多个乘法运算和求和操作。例如，当计算第k行时，可以在计算第k行的同时计算第k+1行，以减少等待时间。 3. 通信（Communication） 在并行计算中，不同任务间的数据交换是必要的。在这里，局部通信（Local communication）用于将每个线程计算的中间结果（t(k)）累加到总和（sum），然后更新矩阵C。通过任务通道图（Task-channel graph）清晰地表示了这个过程。 4. 聚合（Agglomeration） 聚合操作将相邻的任务组合在一起，减少了通信开销。例如，将100个连续的任务合并，减少100次通信为一次。这提高了计算效率，因为更少的通信意味着更快的总体执行速度。 5. 映射（Mapping） 在这个例子中，采用了静态的任务映射，根据处理器数量创建相应数量的任务。使用线程（thread）来并行执行矩阵乘法函数（mat_mul），并确保每个处理器处理一定范围的行。在主程序中，通过控制每个线程处理的行数，实现了并行计算的调度。 实验结果显示，对于全1的矩阵A和矩阵B，预期的矩阵C的每个元素值应为row_col。通过编写`verify()`函数，可以验证计算结果是否正确。通过这种并行化方法，不仅实现了高效计算，还确保了结果的准确性。 总结来说，Foster并行程序设计方法在处理大型矩阵运算时具有显著优势，通过合理地分解任务、优化通信和聚合，以及适配硬件资源，可以大大提高计算速度。这个案例展示了并行计算在解决大规模计算问题时的强大能力，为其他类似问题提供了参考。