素数查找算法的并行执行会减慢运行时间

Question

所以我在 go 中实现了下面的素数查找算法。

素数 = []
假设所有数字都是质数（空洞地为真）
检查 = 2
如果检查仍被假定为质数，则将其附加到质数后
用小于或等于其最小因子的每个素数乘以检查并从假定素数中消除结果。
将检查增加 1 并重复 4 到 6 直到检查 > 限制。

这是我的串行实现：

package main

import(
    "fmt"
    "time"
)

type numWithMinFactor struct {
    number int
    minfactor int
}

func pow(base int, power int) int{
    result := 1
    for i:=0;i<power;i++{
        result*=base
    }
    return result
}

func process(check numWithMinFactor,primes []int,top int,minFactors []numWithMinFactor){
    var n int
    for i:=0;primes[i]<=check.minfactor;i++{
        n = check.number*primes[i]
        if n>top{
            break;
        }
        minFactors[n] = numWithMinFactor{n,primes[i]}
        if i+1 == len(primes){
            break;
        }
    }
}

func findPrimes(top int) []int{
    primes := []int{}
    minFactors := make([]numWithMinFactor,top+2)
    check := 2
    for power:=1;check <= top;power++{
        if minFactors[check].number == 0{
            primes = append(primes,check)
            minFactors[check] = numWithMinFactor{check,check}
        }
        process(minFactors[check],primes,top,minFactors)
        check++
    }
    return primes
}

func main(){ 
    fmt.Println("Welcome to prime finder!")
    start := time.Now()
    fmt.Println(findPrimes(1000000))
    elapsed := time.Since(start)
    fmt.Println("Finding primes took %s", elapsed)
}

这运行得很好，在我的电脑上，在大约 63 毫秒内生成 <1,000,000 个素数（主要是打印），在 600 毫秒内生成 <10,000,000 个素数。现在我计算 none 的数字检查使得 2^n < check <= 2^(n+1) 有因子 > 2^n 所以我可以为该范围内的每个检查进行所有乘法和消除一旦我有 2 ^ n 个素数，就可以并行。而我的并行实现如下：

package main

import(
    "fmt"
    "time"
    "sync"
)

type numWithMinFactor struct {
    number int
    minfactor int
}

func pow(base int, power int) int{
    result := 1
    for i:=0;i<power;i++{
        result*=base
    }
    return result
}

func process(check numWithMinFactor,primes []int,top int,minFactors []numWithMinFactor, wg *sync.WaitGroup){
    defer wg.Done()
    var n int
    for i:=0;primes[i]<=check.minfactor;i++{
        n = check.number*primes[i]
        if n>top{
            break;
        }
        minFactors[n] = numWithMinFactor{n,primes[i]}
        if i+1 == len(primes){
            break;
        }
    }
}

func findPrimes(top int) []int{
    primes := []int{}
    minFactors := make([]numWithMinFactor,top+2)
    check := 2
    var wg sync.WaitGroup
    for power:=1;check <= top;power++{
        for check <= pow(2,power){
            if minFactors[check].number == 0{
                primes = append(primes,check)
                minFactors[check] = numWithMinFactor{check,check}
            }
            wg.Add(1)
            go process(minFactors[check],primes,top,minFactors,&wg)
            check++
            if check>top{
                break;
            }
        }
        wg.Wait()
    }
    return primes
}

func main(){ 
    fmt.Println("Welcome to prime finder!")
    start := time.Now()
    fmt.Println(findPrimes(1000000))
    elapsed := time.Since(start)
    fmt.Println("Finding primes took %s", elapsed)
}

不幸的是，此实现不仅速度较慢运行在 600 毫秒内高达 1,000,000 次，在 6 秒内高达 1000 万次。我的直觉告诉我，并行性有可能提高性能，但我显然无法实现这一点，并且非常感谢任何关于如何改进运行时的输入，或者更具体地说，任何关于为什么并行解决方案速度较慢的见解.

此外，并行解决方案相对于串行解决方案消耗更多内存，但这是可以预料的；串行解决方案可以在大约 22 秒内将最多 1,000,000,000 个网格化，而并行解决方案在我的系统（32GB ram）上耗尽内存用于相同的目标。但是我在这里问的是运行时而不是内存使用，例如我可以使用 minFactors 数组的零值状态而不是单独的 isPrime []bool true 状态，但我认为它更具可读性。

我试过为 primes []int 传递一个指针，但这似乎没有什么区别，使用通道而不是将 minFactors 数组传递给 process 函数会导致大量内存使用和大量（10 倍左右）性能较慢。我已经重写了这个算法几次，看看我是否可以解决任何问题，但没有运气。任何见解或建议将不胜感激，因为我认为并行性可以使速度更快而不是慢 10 倍！

按照@Volker 的建议，我通过以下修订将进程数量限制为少于我的电脑可用逻辑进程的数量，但是我仍然得到比串行实现慢 10 倍的运行时间。

package main

import(
    "fmt"
    "time"
    "sync"
)

type numWithMinFactor struct {
    number int
    minfactor int
}

func pow(base int, power int) int{
    result := 1
    for i:=0;i<power;i++{
        result*=base
    }
    return result
}

func process(check numWithMinFactor,primes []int,top int,minFactors []numWithMinFactor, wg *sync.WaitGroup){
    defer wg.Done()
    var n int
    for i:=0;primes[i]<=check.minfactor;i++{
        n = check.number*primes[i]
        if n>top{
            break;
        }
        minFactors[n] = numWithMinFactor{n,primes[i]}
        if i+1 == len(primes){
            break;
        }
    }
}

func findPrimes(top int) []int{
    primes := []int{}
    minFactors := make([]numWithMinFactor,top+2)
    check := 2
    nlogicalProcessors := 20
    var wg sync.WaitGroup
    var twoPow int
    for power:=1;check <= top;power++{
        twoPow = pow(2,power)
        for check <= twoPow{
            for nLogicalProcessorsInUse := 0 ; nLogicalProcessorsInUse < nlogicalProcessors; nLogicalProcessorsInUse++{
                if minFactors[check].number == 0{
                    primes = append(primes,check)
                    minFactors[check] = numWithMinFactor{check,check}
                }
                wg.Add(1)
                go process(minFactors[check],primes,top,minFactors,&wg)
                check++
                if check>top{
                    break;
                }
                if check>twoPow{
                    break;
                }
            }           
            wg.Wait()
            if check>top{
                break;
            }
        }
    }
    return primes
}

func main(){ 
    fmt.Println("Welcome to prime finder!")
    start := time.Now()
    fmt.Println(findPrimes(10000000))
    elapsed := time.Since(start)
    fmt.Println("Finding primes took %s", elapsed)
}

tldr；为什么我的并行实现比串行实现慢我如何让它更快？

比起@mh-cbon，我为并行处理做了更大的工作，从而产生了以下代码。

package main

import(
    "fmt"
    "time"
    "sync"
)

func pow(base int, power int) int{
    result := 1
    for i:=0;i<power;i++{
        result*=base
    }
    return result
}

func process(check int,primes []int,top int,minFactors []int){
    var n int
    for i:=0;primes[i]<=minFactors[check];i++{
        n = check*primes[i]
        if n>top{
            break;
        }
        minFactors[n] = primes[i]
        if i+1 == len(primes){
            break;
        }
    }
}

func processRange(start int,end int,primes []int,top int,minFactors []int, wg *sync.WaitGroup){
    defer wg.Done()
    for start <= end{
        process(start,primes,top,minFactors)
        start++
    }
}


func findPrimes(top int) []int{
    primes := []int{}
    minFactors := make([]int,top+2)
    check := 2
    nlogicalProcessors := 10
    var wg sync.WaitGroup
    var twoPow int
    var start int
    var end int
    var stepSize int
    var stepsTaken int
    for power:=1;check <= top;power++{
        twoPow = pow(2,power)
        stepSize = (twoPow-start)/nlogicalProcessors
        stepsTaken = 0
        stepSize = (twoPow/2)/nlogicalProcessors
        for check <= twoPow{                
            start = check
            end = check+stepSize
            if stepSize == 0{
                end = twoPow
            }
            if stepsTaken == nlogicalProcessors-1{
                end = twoPow
            }
            if end>top {
                end = top
            }
            for check<=end {            
                if minFactors[check] == 0{
                    primes = append(primes,check)
                    minFactors[check] = check
                }
                check++
            }
            wg.Add(1)
            go processRange(start,end,primes,top,minFactors,&wg)
            if check>top{
                break;
            }
            if check>twoPow{
                break;
            }
            stepsTaken++
            
        }
        wg.Wait()
        if check>top{
            break;
        }
    }
    return primes
}

func main(){ 
    fmt.Println("Welcome to prime finder!")
    start := time.Now()
    fmt.Println(findPrimes(1000000))
    elapsed := time.Since(start)
    fmt.Println("Finding primes took %s", elapsed)
}

这与串行实现的运行速度相似。

Answer 1

所以我最终确实得到了代码的并行版本运行比串行版本稍微快一点。遵循@mh-cbon 的建议（见上文）。然而，相对于串行实现，此实现并没有带来巨大的改进（50 毫秒到 1000 万，而串行为 75 毫秒）考虑到分配和写入 []int 0:10000000 需要 25 毫秒，我对这些结果并不感到失望。正如@Volker 所说，“这些东西通常不受 CPU 的限制，而是受内存带宽的限制。”我相信这里就是这种情况。

我仍然希望看到任何其他改进，但是我对我在这里获得的东西感到有些满意。

序列码运行宁达20亿19.4秒
并行代码运行宁达20亿11.1秒
正在初始化 []int{0:2Billion} 4.5 秒

素数查找算法的并行执行会减慢运行时间

Parallel execution of prime finding algorithm slows runtime

parallel-processing

primes

go