Início / unix / Perguntas / 564051
Accepted
jesse_b
Asked: 2020-01-26 07:03:56 +0800 CST

Como otimizar o GNU paralelo para este uso?

  • 772

Eu criei este script por tédio com o único propósito de usar/testar o GNU paralelo, então sei que não é particularmente útil ou otimizado, mas tenho um script que calculará todos os números primos até 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

Quando executado com o loop:

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

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

Eu esperaria que a substituição do loop for pelo GNU paralelo fizesse com que isso fosse executado significativamente mais rápido, mas essa não foi minha experiência. Em média, é apenas cerca de 1 segundo mais rápido:

#!/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 {}

Executar com paralelo:

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

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

Eu não estou realmente interessado em otimizar a isprime()função, só estou querendo saber se há algo que eu possa fazer para otimizar o GNU paralelo?

No meu teste, seqna verdade, é mais rápido do que for ((i=1...)), então, não acho que tenha muito a ver com o tempo de execução

Curiosamente, se eu modificar o loop for para:

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

Ele roda ainda mais rápido:

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

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

3 respostas

  1. Não vou mencionar otimizar is_primeiterar para squrare_root de (n).

    Desconfio que a versão com paralelo, esteja gastando uma quantidade significativa de tempo iniciando processos. Portanto, divida-o em pedaços maiores. por exemplo, n/Number_of_cpus deve ser o mais rápido (se cada pedaço levar o mesmo tempo). Experimente alguns tamanhos de pedaços, veja o que acontece.

    Você terá que adaptar seu script para diminuir e incrementar.

    por exemplo, organize a execução paralela (se você tiver 5 núcleos).

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

    GNU Parallel gasta 2-10 ms de sobrecarga por trabalho. Ele pode ser reduzido um pouco usando -u, mas isso significa que você pode obter saída de diferentes trabalhos misturados.

    O GNU Parallel não é ideal se seus trabalhos estiverem na faixa de ms e o tempo de execução for importante: a sobrecarga geralmente será muito grande.

    Você pode distribuir a sobrecarga para vários núcleos executando vários GNU Parallels:

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

    Você ainda paga a sobrecarga, mas agora pelo menos tem mais núcleos para pagar.

    Uma maneira melhor seria mudar isprimepara que seja necessário várias entradas e, portanto, demore mais para ser executado:

    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. Alterando o loop for principal:

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

    ele corre um pouco mais rápido

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

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

    do que sem &:

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

    ou apenas com chamadas em segundo plano &:

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

    Então, enquanto o e comercial levava você de 28s para 5s, eu fui de 5s para 3s.

    Eu também tentei 2 com e comercial e 1 sem, mas isso já está ficando mais lento.

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

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

    Desaceleração dramática (veja o ^C) se o e comercial estiver apenas na segunda chamada:

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

    Isso parece um pouco confuso.

    Usando os números primos encontrados apenas como divisores, você pode acelerar pelo fator 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

    Isto dá:

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

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

    E a mesma coisa em perl:

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

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

    (a primeira linha se parece com *** 3, então wca saída é normal)

    Mas este algoritmo é mais difícil de paralelizar: isprime()tem que ter acesso à lista (crescente) de números primos (até sqrt).

    Talvez factor(um comando lutando contra a seção 6 :) seria útil como uma unidade funcional padrão. Então você pode alimentá-lo com diferentes "pedaços".

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

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

    O sedexclui linhas com mais de um espaço (ou seja, mais de um fator).

    Mas, novamente, é muito rápido para ser ajudado:

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

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

relate perguntas