主页 / unix / 问题 / 564051
Accepted
jesse_b
Asked: 2020-01-26 07:03:56 +0800 CST

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

  • 772

我出于无聊创建了这个脚本，其唯一目的是使用/测试 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
bash parallelism

3 个回答

  1. 我不会提到优化is_prime迭代到 (n) 的 squrare_root。

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

    您将不得不调整您的脚本以降低和增加。

    例如安排并行运行（如果你有 5 个内核）。

    ./script    0 1000 &
./script 1000 1000 &
./script 2000 1000 &
./script 3000 1000 &
./script 4000 1000 &
    • 1
  2. Best Answer

    GNU Parallel 每个作业花费 2-10 毫秒的开销。可以通过使用降低一点-u，但这意味着您可能会从不同的工作中获得混合输出。

    如果您的工作在 ms 范围内并且运行时很重要，那么 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
    • 1

  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
    • 0

相关问题