执行素数查找算法的并行化会增加运行时间
来源:stackoverflow
时间:2024-03-23 10:42:31 361浏览 收藏
在尝试并行化素数查找算法时,作者发现并行版本运行时间比串行版本慢。作者尝试通过限制并行进程数量来解决问题,但仍然没有达到预期的性能提升。分析表明,该算法受内存带宽限制,而不是 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;itop{ 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;itop{ 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;itop{ 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;itop{ 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 限制,而是受内存带宽限制。”我相信这里就是这种情况。
我仍然希望看到任何额外的改进,但我对在这里获得的东西有些满意。
- 串行代码运行时间高达 20 亿次,耗时 19.4 秒
- 并行代码运行时间高达 20 亿次,耗时 11.1 秒
- 初始化 []int{0:2Billion} 4.5 秒
理论要掌握,实操不能落!以上关于《执行素数查找算法的并行化会增加运行时间》的详细介绍,大家都掌握了吧!如果想要继续提升自己的能力,那么就来关注golang学习网公众号吧!
-
502 收藏
-
502 收藏
-
501 收藏
-
501 收藏
-
501 收藏
-
139 收藏
-
204 收藏
-
325 收藏
-
477 收藏
-
486 收藏
-
439 收藏
-
357 收藏
-
352 收藏
-
101 收藏
-
440 收藏
-
212 收藏
-
143 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 立即学习 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 立即学习 508次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 立即学习 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 立即学习 484次学习