Functional Parallelism

发表于 更新于 本文字数： 519 阅读时长 ≈ 2 分钟

Future Tasks

future tasks

  • tasks with return values

future objects（also known as promise objects

  • a “handle” for accessing a task’s return value

  • 两个主要操作：

    • Assignment，形式如下

      1
      2
      3
      A = future {
          ⟨ task-with-return-value ⟩
      }

      future object 被限制为只能一次赋值（_single assignment_，类似于 final 变量

      future task 完成后 future object 就不能修改了

    • Blocking read

      • A.get() 读操作会等待，直到与 future object 关联的 task 完成，将该任务的返回值作为 A.get() 的值
      • A.get() 之后的任何 statement S 开始执行时与 A 关联的任务已经完成

Creating Future Tasks in Java’s Fork/Join Framework

future tasks 和 regular tasks 的一些关键不同：

  1. future tasks 继承自 FJ 框架的 RecursiveTask 类，regular tasks 继承自 RecursiveAction 类
  2. future task 的 compute() 方法必须有 non-void 的返回值
  3. left.join() 这样的方法调用都会等 left 指向的任务执行，只是 future task 有返回值

Memoization

记录 f(x) 的执行结果，防止重复计算

  1. 创建特定的数据结构，记录

    $$
    {(x_1,y_1=f(x_1)),(x_2,y_2=f(x_2)),…}
    $$

  2. 当出现 f 的调用时先在记录中查找

future task 在这里非常适合，记录的形式变为了

$$
{(x_1,y_1=future(f(x_1))),(x_2,y_2=future(f(x_2))),…}
$$

对于输入 x，如果对应的 future 对象已经创建，则可以调用该对象的 get() 方法

Java Streams

操作集合对象除了for loop还可以利用Java streams提供的 API

下面的例子求注册学生的平均年龄

1
2
3
4
students.stream()
    .filter(s -> s.getStatus() == Student.ACTIVE)
    .mapToInt(a -> a.getAge())
    .average();

Java streams 提供了并行编程的 API

上面代码的 students.stream() 替换为 students.parallelStream() 或者 Stream.of(students).parallel() 就可以了

Determinism and Data Races

functionally deterministic

  • A parallel program is said to be functionally deterministic if it always computes the same answer when given the same input

structurally deterministic

  • It always computes the same computation graph, when given the same input.

没有数据竞争不足以保证确定性

有数据竞争也不意味着程序的不确定性

带有数据竞争的不确定程序，每次产生的结果不同，但是可能每个结果都是可接受的！！e.g., different locations for a search pattern in a target string