并行编程提升性能

### 并行编程提升性能 #### 1. 使用 Incanter 并行处理 Incanter 是一个强大的工具，它使用 Parallel Colt Java 库来处理数据，在使用矩阵、统计或其他函数时能自动在多线程上执行。以下是使用 Incanter 对弗吉尼亚州住房单元普查数据进行线性回归分析的步骤： ##### 1.1 准备工作 - 在 Leiningen 项目的 `project.clj` 文件中添加 Incanter 依赖： ```clojure :dependencies [[org.clojure/clojure "1.5.0"] [incanter "1.3.0"]] ``` - 在 REPL 或脚本中引入相关库： ```clojure (use '(incanter core datasets io optimize charts stats)) ``` - 绑定数据文件名称： ```clojure (def data-file "data/all_160_in_51.P35.csv") ``` ##### 1.2 具体操作 1. 读取数据并将人口和住房单元列提取到各自的矩阵中： ```clojure (def data (to-matrix (sel (read-dataset data-file :header true) :cols [:POP100 :HU100]))) ``` 2. 将人口和住房单元数据绑定到各自的名称： ```clojure (def population (sel data :cols 0)) (def housing-units (sel data :cols 1)) ``` 3. 使用 Incanter 拟合数据： ```clojure (def lm (linear-model housing-units population)) ``` 4. 绘制数据图： ```clojure (def plot (scatter-plot population housing-units :legend true)) (add-lines plot population (:fitted lm)) (view plot) ``` ##### 1.3 工作原理 Incanter 会将数据矩阵分割成块，然后将这些块分布到可用的 CPU 上以加速处理，我们无需担心具体的并行处理细节。 #### 2. 分区蒙特卡罗模拟以提高 pmap 性能 在使用 `pmap` 进行并行处理时，知道何时使用它是比较复杂的。为了让 `pmap` 更高效，我们可以将输入集合分区并对分区组运行 `pmap`。这里我们使用蒙特卡罗方法来近似计算 π，并比较串行版本、简单并行版本和使用并行分区版本的性能。 ##### 2.1 准备工作 - 在 Leiningen 项目的 `project.clj` 文件中添加 Criterium 依赖： ```clojure :dependencies [[org.clojure/clojure "1.5.0"] [criterium "0.3.0"]] ``` - 在脚本或 REPL 中使用这些依赖和 `java.lang.Math` 类： ```clojure (use 'criterium.core) (import [java.lang Math]) ``` ##### 2.2 具体实现 1. 定义模拟所需的函数： ```clojure (defn rand-point [] [(rand) (rand)]) ``` 2. 定义计算点到原点距离的函数： ```clojure (defn center-dist [[x y]] (Math/sqrt (+ (* x x) (* y y)))) ``` 3. 定义计算落在圆内的点数的函数： ```clojure (defn count-in-circle [n] (->> (repeatedly n rand-point) (map center-dist) (filter #(<= % 1.0)) count)) ``` 4. 定义基本（串行）版本： ```clojure (defn mc-pi [n] (* 4.0 (/ (count-in-circle n) n))) ``` 5. 定义简单 `pmap` 版本： ```clojure (defn in-circle-flag [p] (if (<= (center-dist p) 1.0) 1 0)) (defn mc-pi-pmap [n] (let [in-circle (->> (repeatedly n rand-point) (pmap in-circle-flag) (reduce + 0))] (* 4.0 (/ in-circle n)))) ``` 6. 定义分区版本： ```clojure (defn mc-pi-part ([n] (mc-pi-part 512 n)) ([chunk-size n] (let [step (int (Math/floor (float (/ n chunk-size)))) remainder (mod n chunk-size) parts (lazy-seq (cons remainder (repeat step chunk-size))) in-circle (reduce + 0 (pmap count-in-circle parts))] (* 4.0 (/ in-circle n))))) ``` ##### 2.3 性能比较 | Function | Input Size | Chunk Size | Mean | Std Dev. | GC Time | | ---- | ---- | ---- | ---- | ---- | ---- | | mc-pi | 1,000,000 | NA | 634.39ms | 33.22 ms | 4.0% | | mc-pi-pmap | 1,000,000 | NA | 1.92 sec | 888.52 ms | 2.60% | | mc-pi-part | 1,000,000 | 4,096 | 455.94 ms | 4.19 ms | 8.75% | 从表格可以看出，分区版本的性能明显优于串行版本和简单并行版本。 #### 3. 蒙特卡罗模拟原理 蒙特卡罗模拟通过向一个本质上是确定性的问题投掷随机数据来工作，当直接解决该问题在实际中不可行时，这种方法很有用。例如，通过在单位正方形中随机填充点，π/4 大约是落在以 (0, 0) 为中心的圆内的点的比例。使用的随机点越多，近似值就越好。不过，这是一种计算 π 的糟糕方法，它往往比其他方法更慢且更不准确。蒙特卡罗方法在设计隔热罩、模拟污染、光线追踪、金融期权定价等方面有广泛应用。 #### 4. 为 pmap 分区数据的原理 分区可以提高性能的原因是每个线程可以在每个任务上花费更多时间。将工作分布在多个线程上会有性能开销，如上下文切换和线程协调。如果每个任务本身花费的时间不够长，并行的好处就无法弥补这些开销。通过分区输入，为每个线程创建更大的单个任务，从而减少上下文切换和协调的时间。 #### 5. 使用模拟退火算法找到最佳分区大小 在之前的分区蒙特卡罗模拟中，我们大致猜测了一个较好的分区大小，但这仍然是很大程度上的猜测。模拟退火是一种简单的优化算法，它基于分子在温度下降到冰点时进入低能量配置的自然过程。 ##### 5.1 准备工作 使用与分区蒙特卡罗模拟相同的依赖、导入和函数，此外还需要 `mc-pi-part` 函数。 ##### 5.2 具体实现 1. 定义模拟退火函数： ```clojure (defn annealing [initial max-iter max-cost neighbor-fn cost-fn p-fn temp-fn] ```