弗洛伊德算法

大纲

• 全对最短路径问题
• 动态二维数组
• 并行算法设计
• 点对点通信
• 块行矩阵 I/O
• 分析和基准测试

埃拉托斯特尼筛法

串行算法

1. 列出 2 以后的所有序列：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2. 标出序列中的第一个质数，也就是 2，序列变成：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3. 将剩下序列中，划摽 2 的倍数（用红色标出），序列变成：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
4. 如果现在这个序列中最大数小于等于最后一个标出的素数的平方，那么剩下的序列中所有的数都是质数，否则回到第二步。

时间复杂度：（nlnlnn)

消息传递编程

进程

• 启动时指定数量
• 在整个程序执行过程中保持不变
• 都执行相同的程序
• 每个都有唯一的 ID 号
• 交替执行计算和通信

第四章 性能

指标（加速比和效率）

• 运行时间（执行时间）
• 加速
• 效率
• 可扩展性
• 便携性、编程能力等等

第三章 并行程序设计

Foster 方法

划分、通信：处理与机器无关的问题，影响并发性和可扩展性
聚合、映射：处理与机器有关的问题，影响局部性和其他性能问题

划分

将要执行的指令和数据按计算部分拆分成多个小任务。关键在于识别出可以并行执行的任务

通信

确定划分的任务之间需要执行哪些通信

第一章 Architecture

大纲（outline）

• 冯诺依曼模型的修改
• 分布式硬件
  • 弗林分类法
  • 共享内存系统和分布式存储系统
  • 内存层次结构和缓存一致性
  • 互联网络
• 分布式软件
• 输入输出