Guile Scheme 并行形式加速
Guile Scheme parallel forms speedup
我正在试验 Guile Scheme 的并行形式，我有以下代码：
(use-modules (srfi srfi-1)
(ice-9 pretty-print)
(ice-9 receive))
(define (busy-work limit)
(if (> limit 0)
(begin (sqrt (+ (expt limit limit) 1))
(busy-work (- limit 1)))
'done))
(define (busy-work-2 lst)
(cond [(null? lst) 'done]
[else
(expt (car lst) (car lst))
(busy-work-2 (cdr lst))]))
(define (time thunk)
(define starting-time (current-time))
(define res (thunk))
(define ending-time (current-time))
(display "elapsed time: ")
(display (- ending-time starting-time))
(display "s")
(newline)
res)
(define (partition-4 numbers)
(define (loop numbers rc0 rc1 rc2 rc3)
(cond [(null? numbers) (list (reverse rc0)
(reverse rc1)
(reverse rc2)
(reverse rc3))]
[else
(let* ([number (car numbers)]
[residue (remainder number 4)])
(cond [(= residue 0) (loop (cdr numbers)
(cons number rc0)
rc1
rc2
rc3)]
[(= residue 1) (loop (cdr numbers)
rc0
(cons number rc1)
rc2
rc3)]
[(= residue 2) (loop (cdr numbers)
rc0
rc1
(cons number rc2)
rc3)]
[(= residue 3) (loop (cdr numbers)
rc0
rc1
rc2
(cons number rc3))]))]))
(loop numbers '() '() '() '()))
（或在我位于 https://github.com/ZelphirKaltstahl/guile-scheme-tutorials/blob/5321470f8f3cbbdb7f64d4ed60e4b1eaf8d8f444/parallellism/utils.scm 的实验存储库中）
据我所知，busy-work 和 busy-work-2 这两个过程是纯粹的数字运算，带有数字列表，其中没有计算依赖于另一个。我知道时间测量可能不完全准确。
但是，我一直没有通过使用更多线程（核心，正如我在 CPU 指标中的核心使用情况中看到的那样）获得预期的加速。
这里有一些例子，我希望 2 个线程完成任务的速度是 1 个内核的两倍，4 个内核的速度是 2 个内核的两倍。至少或多或少，因为我正在以某种方式拆分列表，这应该或多或少地平均分配工作。
使用 4 个核心和 parallel
(let ([residue-classes (partition-4 (iota 30000))])
(time
(lambda ()
(parallel (busy-work-2 (car residue-classes))
(busy-work-2 (cadr residue-classes))
(busy-work-2 (caddr residue-classes))
(busy-work-2 (cadddr residue-classes))))))
这在我的机器上大约在 10 秒内完成。有时 9s 有时 10s.
Using par-map 使用 4 个线程（内核）
(let ([residue-classes (partition-4 (iota 30000))])
(time
(lambda ()
(par-map busy-work-2
residue-classes))))
这在我的机器上大约在 10 秒内完成。有时是 9 有时是 10。就像 parallel.
使用 n-par-map 和 4 个线程（在我的机器上）
(let ([residue-classes (partition-4 (iota 30000))])
(time
(lambda ()
(n-par-map (current-processor-count)
busy-work-2
residue-classes))))
也是10s。这里的手册（https://www.gnu.org/software/guile/manual/html_node/Parallel-Forms.html）说：
Unlike those above, the functions described below take a number of threads as an argument. This makes them inherently non-portable since the specified number of threads may differ from the number of available CPU cores as returned by current-processor-count (see Processes). In addition, these functions create the specified number of threads when they are called and terminate them upon completion, which makes them quite expensive.
Therefore, they should be avoided.
虽然我发现这个解释并没有 100% 的意义（为什么 n-par-map 不使用与 parallel 相同的预创建线程，如果这些线程足够的话？喜欢4 就像在我的机器上一样？），我没有看到任何很大的开销，我再次看到它大约在 10 秒内完成。我的猜测是，线程创建花费的时间太少，与数字运算时的所有计算相比，它根本没有被注意到。
使用 n-par-map 2 个线程（内核）
(let ([residue-classes (partition-4 (iota 30000))])
(time
(lambda ()
(n-par-map 2
busy-work-2
residue-classes))))
预期：可能会在 20 秒内完成。
结果：这在 12 秒内完成。
现在我当然在想：“那么在 4 核的运行中肯定有一些巨大的开销！”。
问题：但是，当我进行没有任何结果相互依赖的纯数字运算时，这些开销从何而来？它是否使用一些共享内存以致内存访问成为瓶颈？
您可能正在使用具有两个超线程物理内核的机器，因此报告了 4 个 CPU。它显示的是此工作负载不适合超线程。
我在具有两个超线程物理内核的机器上得到了类似的结果。但是，对于具有 4 个物理内核的机器，我使用所有 4 个内核获得 9 秒，仅使用 2 个内核获得 16 秒，这更符合您的预期。
我正在试验 Guile Scheme 的并行形式，我有以下代码：
(use-modules (srfi srfi-1)
(ice-9 pretty-print)
(ice-9 receive))
(define (busy-work limit)
(if (> limit 0)
(begin (sqrt (+ (expt limit limit) 1))
(busy-work (- limit 1)))
'done))
(define (busy-work-2 lst)
(cond [(null? lst) 'done]
[else
(expt (car lst) (car lst))
(busy-work-2 (cdr lst))]))
(define (time thunk)
(define starting-time (current-time))
(define res (thunk))
(define ending-time (current-time))
(display "elapsed time: ")
(display (- ending-time starting-time))
(display "s")
(newline)
res)
(define (partition-4 numbers)
(define (loop numbers rc0 rc1 rc2 rc3)
(cond [(null? numbers) (list (reverse rc0)
(reverse rc1)
(reverse rc2)
(reverse rc3))]
[else
(let* ([number (car numbers)]
[residue (remainder number 4)])
(cond [(= residue 0) (loop (cdr numbers)
(cons number rc0)
rc1
rc2
rc3)]
[(= residue 1) (loop (cdr numbers)
rc0
(cons number rc1)
rc2
rc3)]
[(= residue 2) (loop (cdr numbers)
rc0
rc1
(cons number rc2)
rc3)]
[(= residue 3) (loop (cdr numbers)
rc0
rc1
rc2
(cons number rc3))]))]))
(loop numbers '() '() '() '()))
（或在我位于 https://github.com/ZelphirKaltstahl/guile-scheme-tutorials/blob/5321470f8f3cbbdb7f64d4ed60e4b1eaf8d8f444/parallellism/utils.scm 的实验存储库中）
据我所知，busy-work 和 busy-work-2 这两个过程是纯粹的数字运算，带有数字列表，其中没有计算依赖于另一个。我知道时间测量可能不完全准确。
但是，我一直没有通过使用更多线程（核心，正如我在 CPU 指标中的核心使用情况中看到的那样）获得预期的加速。
这里有一些例子，我希望 2 个线程完成任务的速度是 1 个内核的两倍，4 个内核的速度是 2 个内核的两倍。至少或多或少，因为我正在以某种方式拆分列表，这应该或多或少地平均分配工作。
使用 4 个核心和 parallel
(let ([residue-classes (partition-4 (iota 30000))])
(time
(lambda ()
(parallel (busy-work-2 (car residue-classes))
(busy-work-2 (cadr residue-classes))
(busy-work-2 (caddr residue-classes))
(busy-work-2 (cadddr residue-classes))))))
这在我的机器上大约在 10 秒内完成。有时 9s 有时 10s.
Using par-map 使用 4 个线程（内核）
(let ([residue-classes (partition-4 (iota 30000))])
(time
(lambda ()
(par-map busy-work-2
residue-classes))))
这在我的机器上大约在 10 秒内完成。有时是 9 有时是 10。就像 parallel.
使用 n-par-map 和 4 个线程（在我的机器上）
(let ([residue-classes (partition-4 (iota 30000))])
(time
(lambda ()
(n-par-map (current-processor-count)
busy-work-2
residue-classes))))
也是10s。这里的手册（https://www.gnu.org/software/guile/manual/html_node/Parallel-Forms.html）说：
Unlike those above, the functions described below take a number of threads as an argument. This makes them inherently non-portable since the specified number of threads may differ from the number of available CPU cores as returned by current-processor-count (see Processes). In addition, these functions create the specified number of threads when they are called and terminate them upon completion, which makes them quite expensive.
Therefore, they should be avoided.
虽然我发现这个解释并没有 100% 的意义（为什么 n-par-map 不使用与 parallel 相同的预创建线程，如果这些线程足够的话？喜欢4 就像在我的机器上一样？），我没有看到任何很大的开销，我再次看到它大约在 10 秒内完成。我的猜测是，线程创建花费的时间太少，与数字运算时的所有计算相比，它根本没有被注意到。
使用 n-par-map 2 个线程（内核）
(let ([residue-classes (partition-4 (iota 30000))])
(time
(lambda ()
(n-par-map 2
busy-work-2
residue-classes))))
预期：可能会在 20 秒内完成。
结果：这在 12 秒内完成。
现在我当然在想：“那么在 4 核的运行中肯定有一些巨大的开销！”。
问题：但是，当我进行没有任何结果相互依赖的纯数字运算时，这些开销从何而来？它是否使用一些共享内存以致内存访问成为瓶颈？
您可能正在使用具有两个超线程物理内核的机器，因此报告了 4 个 CPU。它显示的是此工作负载不适合超线程。
我在具有两个超线程物理内核的机器上得到了类似的结果。但是，对于具有 4 个物理内核的机器，我使用所有 4 个内核获得 9 秒，仅使用 2 个内核获得 16 秒，这更符合您的预期。