并行计算Parallel Computing
并行计算几种模式
- SPMD Pattern
- Master/Worker Pattern主/从
- Loop Parallelism Pattern循环并行
- Fork/Join Pattern
- MapReduce Pattern
SPMD 模式
- SPMD 简称:Single Program Multiple Data
单程序多数据。 多线程
- UE: Unit of Execution 执行单元
• Process • Thread • Coroutine• Actor
用单个程序为所有UEs运行或服务。
用UE’s ID为程序执行选择不同路径
UE之间保持交互共享或通讯。
Master/Worker主从
- 好的可伸缩性 自动负载平衡
- 如何检测断点?(1)任务包是空的 (2)毒丸
- 如果瓶颈在Queue上怎么办? 使用多个队列,或Work stealing
- 容错性如何解决?使用“in-progress”队列
Loop Parallelism循环并行
- 操作流程
1.找出造成瓶颈的loops循环。
2.消除循环中遍历的耦合,解耦。
3.将循环进行并行运行。
- 如果遍历次数少,通过合并循环 嵌套循环加重它。
任务并行的两种方式
- 将循环loops语法实现并行计算 (Loop Parallelism)。
- 将这些任务放入一个工作队列中,表面上的串行计算 (Master/Worker)。
- 如果上面方式都不奏效,使用: Fork/Join
Fork/Join
- 当任务之间的关系比较简单,可使用。
- 适合递归式的数据处理
- work-stealing:
1. Fork: 任务将动态被创建
2. Join: 任务然后会被中断,数据被聚合合并。
Fork/Join两种实现方式
- 直接的task/UE 映射
• 在Task/UE之间实现1:1映射
• 问题: 动态UE创建是消耗很大
- 间接 task/UE 映射
• 将UE进行池化pool
• 控制或约束资源的分配
• 自动负载平衡
MapReduce
- Google paper 2004
- Fork/Join的变种
- 前期要非动态地将功能Work切分。
- 通常是分布式的
- 适合大规模数据分析筛选折腾。
MapReduce产品
- Hadoop (OSS), used @ Yahoo
- Amazon Elastic MapReduce
- 许多NOSQL使用其作为searching/querying引擎。
理解Map/Reduce
用新的converCurrency:
共同点
- 创建一个输出集合list,
- 从输入集合中遍历每个元素,再调用相应转换方法,然后把转换结果保存到另外一个输出集合中。
- 返回这个输出集合list.
- 这是我们经常干的事情。
Map操作定义
- 调用某个方法someMethod(T):
- 输入参数T是输入集合list<T>的元素
- 方法将返回另外一个同样大小的集合list<T>。
- apply a method on each element of a collection
- oogle Guava 的 Iterables 类 提供Map操作
注意下面代码方法参数是函数。
Map操作代码
Fold/Reduce操作
- 类似Map操作,但是sum += amount; 统计总和,返回的不是集合,而是总和结果。
- Fold是这样一个方法someMethod(T),方法内部有一个的可变状态。
反复调用输入集合中每一个元素,直至到最后,我们得到fold操作的结果。
- Fold适合计算总和, 逻辑上 AND 和 OR, List.add() or List.addAll(), StringBuilder.append(), 取最大值或最小值等 etc.. Fold 类似 SQL语句中聚合功能.
Apache Commons Collection Closure 接口 模拟Fold:
// the closure interface with same input/output type
public interface Closure<T> {
T execute(T value);
}
// an example of a concrete closure
public class SummingClosure implements Closure<Double> {
private double sum = 0;
public Double execute(Double amount) {
sum += amount; // apply '+=' operator
return sum; // return current accumulated value
}
}
// the poor man Fold operator
public final static <T> T foreach(Iterable<T> list, Closure<T> closure) {
T result = null;
for (T t : list) {
result = closure.execute(t);
}
return result;
}
@Test // example of use
public void testFold() throws Exception {
SummingClosure closure = new SummingClosure();
List<Double> exVat = Arrays.asList(new Double[] { 99., 127., 35. });
Double result = foreach(exVat, closure);
System.out.println(result); // print 261.0
}
并行计算的产品
- MPI
- OpenMP
- JSR166 Fork/Join
- java.util.concurrent
• ExecutorService, BlockingQueue etc.
- ProActive Parallel Suite
- CommonJ WorkManager (JEE)
Java并发专题
并发与并行
首页
云计算
更多伸缩性scalable讨论