☰

이 목적을 위해 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

나는 for 루프를 GNU 병렬 처리로 대체하면 작업 속도가 훨씬 빨라질 것이라고 기대했지만, 내 경험은 그렇지 않았습니다. 평균적으로 약 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

관련 정보