☰

如何为此用途优化 GNU 并行？

tag-icon • tag-icon bash parallelism gnu-parallel
如何为此用途优化 GNU 并行？

我出于无聊而创建了这个脚本，唯一的目的是使用/测试 GNU 并行，所以我知道它不是特别有用或优化，但我有一个脚本可以计算 n 以内的所有素数：

#!/usr/bin/env bash

isprime () {
    local n=$1
    ((n==1)) && return 1
    for ((i=2;i<n;i++)); do
        if ((n%i==0)); then
            return 1
        fi
    done
    printf '%d\n' "$n"
}

for ((f=1;f<=$1;f++)); do
    isprime "$f"
done

当使用循环运行时：

$ time ./script.sh 5000 >/dev/null

real    0m28.875s
user    0m38.818s
sys     0m29.628s

我预计用 GNU 并行替换 for 循环将使运行速度显着加快，但这不是我的经验。平均而言，只快了 1 秒左右：

#!/usr/bin/env bash

isprime () {
    local n=$1
    ((n==1)) && return 1
    for ((i=2;i<n;i++)); do
        if ((n%i==0)); then
            return 1
        fi
    done
    printf '%d\n' "$n"
}

export -f isprime

seq 1 $1 | parallel -j 20 -N 1 isprime {}

并行运行：

$ time ./script.sh 5000 >/dev/null

real    0m27.655s
user    0m38.145s
sys     0m28.774s

我对优化该函数并不是很感兴趣isprime()，我只是想知道是否可以做一些事情来优化 GNU 并行？

在我的测试中seq，实际上运行速度比for ((i=1...))所以我认为这与运行时没有太大关系

有趣的是，如果我将 for 循环修改为：

for ((f=1;f<=$1;f++)); do
    isprime "$f" &
done | sort -n

它运行得更快：

$ time ./script.sh 5000 >/dev/null

real    0m5.995s
user    0m33.229s
sys     0m6.382s

答案1

GNU Parallel 每个作业花费 2-10 毫秒的开销。使用 可以稍微降低它-u，但这意味着您可能会混合不同作业的输出。

如果您的作业在毫秒范围内并且运行时很重要，那么 GNU Parallel 并不理想：开销通常太大。

您可以通过运行多个 GNU Parallels 将开销分散到多个内核：

seq 5000 | parallel --pipe --round-robin -N100 parallel isprime

您仍然需要支付开销，但现在您至少有更多的核心需要支付。

更好的方法是进行更改isprime，使其需要多个输入，从而需要更长的时间来运行：

isprime() {
  _isprime () {
      local n=$1
      ((n==1)) && return 1
      for ((i=2;i<n;i++)); do
          if ((n%i==0)); then
              return 1
          fi
      done
      printf '%d\n' "$n"
  }
  for t in "$@"; do
    _isprime $t
  done
}
export -f isprime

seq 5000 | parallel -X isprime
# If you do not care about order, this is faster because higher numbers always take more time
seq 5000 | parallel --shuf -X isprime

答案2

我不会提及优化is_prime对 (n) 的 sqrare_root 的迭代。

我怀疑并行版本花费了大量时间来启动进程。因此，将其分成更大的块。例如，n/Number_of_cpus 应该是最快的（如果每个块花费相同的时间）。尝试一些块大小，看看会发生什么。

您将必须调整脚本以降低和增加。

例如，安排并行运行（如果您有 5 个核心）。

./script    0 1000 &
./script 1000 1000 &
./script 2000 1000 &
./script 3000 1000 &
./script 4000 1000 &

答案3

通过更改主 for 循环：

for ((f=1;f<=$1;f+=2)); do
    isprime $f &
    isprime $((f+1))
done

它跑得快一点

]# time ./jj.sh 5000 |wc
    669     669    3148

real    0m2.537s
user    0m8.109s
sys     0m1.374s

比没有&：

real    0m5.758s
user    0m5.761s
sys     0m0.007s

或仅使用后台调用&：

real    0m3.298s
user    0m10.743s
sys     0m1.869s

因此，当 & 符号将您从 28 变为 5 时，我则从 5 变为 3。

我还尝试了 2 个带 & 符号和 1 个不带 & 符号，但这已经变得越来越慢。

]# time ./jj.sh 5000 |wc
^C

real    0m17.668s
user    0m17.576s
sys     0m1.344s

如果 & 符号仅出现在第二次调用上，则会显着减慢速度（请参阅 ^C）：

for ((f=1;f<=$1;f+=2)); do
    isprime $f
    isprime $((f+1)) &
done

这似乎有点令人困惑。

通过仅使用找到的素数作为除数，您可以将速度提高 20 倍：

max=5000
max2=75
primes=('3')
echo '2'; echo '3'

for ((n=5; n<max; n+=2))
do  size=${#primes[@]}
    for ((pi=0; pi<=$size; pi++))
    do  p=${primes[$pi]}
        if (( $n % $p == 0 ))
        then break
        fi
        if (( $p * $p > $n ))
        then echo $n
             (( $n < $max2 )) && primes+=("$n")
             break
        fi
    done
done

这给出：

]# time . prim.sh |wc
    669     669    3148

real    0m0.126s
user    0m0.142s
sys     0m0.001s

Perl 中也有同样的事情：

]# time perl prim.pl | wc
    668    1336    6486

real    0m0.008s
user    0m0.009s
sys     0m0.001s

（第一行看起来像*** 3，所以wc输出正常）

但该算法更难以并行化：isprime()必须访问（不断增长的）素数列表（最多 sqrt）。

也许factor（针对第 6 节的命令:) 作为标准功能单元会很有用。然后你可以用不同的“块”喂它。

]# time seq 2 5000 |factor |sed '/ .* /d' |cut -f1 -d':' |wc 
    669     669    3148

real    0m0.008s
user    0m0.014s
sys     0m0.005s

删除sed具有多个空格（即多个因素）的行。

但话又说回来，速度太快了，无能为力：

]# time seq 900000000002 900000005000 | factor  |wc
   4999   26848  163457

real    0m0.031s
user    0m0.035s
sys     0m0.003s

相关内容