并行计算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”队列

master-worker 计算


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
    • 控制或约束资源的分配
    • 自动负载平衡

使用Java 7.0的 Fork/Join框架进行并发编程

 


 

 

MapReduce

  • Google paper 2004
  • Fork/Join的变种
  • 前期要非动态地将功能Work切分。
  • 通常是分布式的
  • 适合大规模数据分析筛选折腾。

MapReduce产品

  • Hadoop (OSS), used @ Yahoo
  • Amazon Elastic MapReduce
  • 许多NOSQL使用其作为searching/querying引擎。

map/reduce


 

理解Map/Reduce

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操作代码

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讨论