当前位置：首页 > 文章列表 > Golang > Go问答 > 执行素数查找算法的并行化会增加运行时间

执行素数查找算法的并行化会增加运行时间

来源：stackoverflow 2024-03-23 10:42:31 0浏览收藏

在尝试并行化素数查找算法时，作者发现并行版本运行时间比串行版本慢。作者尝试通过限制并行进程数量来解决问题，但仍然没有达到预期的性能提升。分析表明，该算法受内存带宽限制，而不是 CPU 限制。

问题内容

因此我在 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。现在我认为没有一个数字检查使得 2^n < 检查 <= 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 内存）上用于相同目标时会耗尽内存。但我在这里询问运行时而不是内存使用，例如，我可以使用 minfactors 数组的零值状态，而不是单独的 isprime []bool true 状态，但我认为它按原样更具可读性。

我尝试过传递 primes []int 的指针，但这似乎没有什么区别，使用通道而不是将 minfactors 数组传递给 process 函数会导致大量的内存使用和很多（10x ish）性能较慢。我已经重写了这个算法几次，看看是否可以解决任何问题，但没有运气。任何见解或建议将不胜感激，因为我认为并行性可以使速度更快而不是慢 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；为什么我的并行实现比串行实现慢，如何使其更快？

par @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)
}

其运行速度与串行实现类似。

正确答案

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

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