"基于MPI的埃拉托斯特尼筛法实验报告"

关文聪 2016060601008 分布式并行计算-MPI实验报告1 本次实验的目标是基于 MPI 实现埃拉托斯特尼筛法并进行性能优化。Erathosthenes 素数筛法源自古希腊数学家 Erathosthenes，他采用了一种与众不同的方法来寻找小于等于 N 的素数。具体操作步骤为首先将 2 到 N 的自然数写在纸上，然后将 2 的倍数划去，接着寻找下一个未被划去的数并重复以上步骤直到所有小于等于 N 的自然数都被划去或圈出。这样剩下的所有未被划去的数就是小于等于 N 的素数。 实验原理如下： 1. 首先创建一个自然数 2,3,4,…,n 的列表，其中所有的自然数都没有被标记。 2. 令 k=2，它是列表中第一个未被标记的数。 3. 重复下面的步骤直到k2 > n 为止： （a） 被k2和 n 之间的是 k 倍数的数标记。 （b） 寻找下一个未被标记的数并将其赋值给 k。 MPI (Message Passing Interface) 是一种并行计算编程模型，在本实验中我们利用 MPI 实现了 Erathosthenes 素数筛法。在并行计算的过程中，我们将自然数列表划分成多个区块并分配给不同的处理器进行计算，最终合并得到结果。通过并行计算，可以显著提高计算效率，特别是对于大规模的计算任务。 性能优化是本次实验的重点之一。我们通过优化算法、调整并行计算的策略以及合理配置计算资源来提高程序的性能。通过实验结果的对比分析，我们对比了不同优化策略的性能表现，并且总结出了一些优化方法，对于大规模并行计算问题具有一定的指导意义。 总的来说，本次实验通过 MPI 实现了 Erathosthenes 素数筛法并进行了性能优化，验证了并行计算在大规模计算问题中的有效性。通过本次实验，我们对 MPI 并行计算模型有了进一步的了解，并学习了优化并行计算程序的方法。希望通过不断的实践和探索，能够在并行计算领域取得更多的成果和突破。