[原创] 电脑的奥林匹克：Super Prime五项测试的并行算法优化
[ 2008-08-31 23:00:14 ]
引言/提要：某些特定情况下的测试结果，低档次电脑系统反而超越了高档次的电脑。正如奥林匹克竞赛，谁输谁赢并不是早已注定。这是公平竞争，人人都有的机会。
关键词：奥林匹克，并行计算，算法优化，核心技术，核心竞争力
Super Prime超级质数机，是龙之梦工作室自主开发的快速求64位大质数软件，可以用来测试电脑系统的性能。它主要通过算法优化的方式，把现代电脑的性能优势充分发挥出来，从而体现出新的电脑系统比旧电脑快在哪里。
Super Prime由五个不同的测试程序组成，分别侧重与测试电脑系统的不同方面。犹如奥运标志的五环，分别代表地球的不同地区。
从2007年初开始，龙之梦工作室对这个软件进行了并行算法优化，使其在超线程、双核、多核、多CPU等技术下发挥更出色。在多个升级版本中，陆续开放了求64位质数主程序、求32位预备数据的并行优化。
实际测试中，用双核CPU系统验证了并行算法优化对性能起到了实质性的提升作用。主要表现在：
求64位大质数的速度提高77.5％，轻松突破了10秒钟的大关。具体见《百米冲刺，Super Prime求质数突破10秒大关》和《并行计算显神威，Super Prime性能倍增》。
解决了文件写入冲突之后，求所有32位质数的时间，也就是数据准备时间，从接近9个小时，大幅缩短到3小时13分钟。具体见《更快、更高、更强，Super Prime再度升级》和《超级质数机：并发执行中的异步问题处理心得》。
最后完成的节约内存模式下的并行算法优化，解决了共享缓存冲突问题。实际测试结果显示，不但双核CPU系统中的性能大幅提升，就连单核、无超线程CPU系统中也有显著改善。究其原因，一是并行算法提高了磁盘缓存的命中率，减少了读取硬盘的次数，二是多线程状态下，CPU和硬盘能够同时工作，不必互相等待。
后面附上内部测试数据和简要说明，供大家参考。从中也可以看出，某些特定情况下的测试结果，低档次电脑系统反而超越了高档次的电脑。正如奥林匹克竞赛，谁输谁赢并不是早已注定。这是公平竞争，人人都有的机会。
Super Prime超级质数机，是奥林匹克计算机竞赛选手开发的软件，体现了更快、更高、更强的奥林匹克精神。龙之梦工作室将会一如既往地秉承这种宝贵精神，在信息化的领域中发扬光大。
内部测试数据如下：
A机：AMD Athlon XP 2000+系统，单核、无超线程技术，8MB缓存的IDE硬盘，测试程序prime64_f.exe对内存大小不敏感。
prime64_f.exe (group=1, threads=1) >>> Mon Oct 08 18:37:46 2007
//group＝1表示一个一个质数计算，threads＝1表示单个线程运算
18446744073709551557 , 34000 ms ( thread 1 , +34000 ms )
18446744073709551533 , 68781 ms ( thread 1 , +34781 ms )
18446744073709551521 , 104328 ms ( thread 1 , +35547 ms )
18446744073709551437 , 171390 ms ( thread 1 , +67062 ms )
18446744073709551427 , 206047 ms ( thread 1 , +34657 ms )
18446744073709551359 , 240734 ms ( thread 1 , +34687 ms )
18446744073709551337 , 275265 ms ( thread 1 , +34531 ms )
18446744073709551293 , 312000 ms ( thread 1 , +36735 ms )
18446744073709551263 , 346672 ms ( thread 1 , +34672 ms )
//9个质数总耗时346.672秒，平均每个质数38.52秒
prime64_f.exe (group=1, threads=2) >>> Mon Oct 08 10:51:12 2007
//group＝1表示一个一个质数计算，threads＝2表示2个线程并行运算
18446744073709551557 , 44657 ms ( thread 2 , +44657 ms )
18446744073709551427 , 75797 ms ( thread 1 , +31140 ms )
18446744073709551533 , 85078 ms ( thread 2 , +9281 ms )
18446744073709551359 , 115610 ms ( thread 1 , +30532 ms )
18446744073709551521 , 125719 ms ( thread 2 , +10109 ms )
18446744073709551437 , 167250 ms ( thread 2 , +41531 ms )
18446744073709551263 , 168282 ms ( thread 1 , +1032 ms )
18446744073709551191 , 215578 ms ( thread 1 , +47296 ms )
18446744073709551337 , 215641 ms ( thread 2 , +63 ms )
//9个质数总耗时215.641秒，平均每个质数23.96秒
//并行运算比单个线程快了60.8％
B机：AMD Athlon64 X2 3800+系统，双核、无超线程技术，8MB缓存的SATA硬盘，测试程序prime64_f.exe对内存大小不敏感。
prime64_f.exe (group=1, threads=1) >>> Mon Oct 08 10:40:16 2007
//group＝1表示一个一个质数计算，threads＝1表示单个线程运算
18446744073709551557 , 40703 ms ( thread 1 , +40703 ms )
18446744073709551533 , 90719 ms ( thread 1 , +50016 ms )
18446744073709551521 , 138953 ms ( thread 1 , +48234 ms )
18446744073709551437 , 196344 ms ( thread 1 , +57391 ms )
18446744073709551427 , 245687 ms ( thread 1 , +49343 ms )
18446744073709551359 , 295515 ms ( thread 1 , +49828 ms )
18446744073709551337 , 344109 ms ( thread 1 , +48594 ms )
18446744073709551293 , 392875 ms ( thread 1 , +48766 ms )
18446744073709551263 , 441547 ms ( thread 1 , +48672 ms )
//9个质数总耗时441.547秒，平均每个质数49.06秒
//单线程运算，比档次更低的A机还要慢21.5％（主要原因估计是硬盘子系统NCQ工作原理的差异）
prime64_f.exe (group=1, threads=2) >>> Mon Oct 08 10:57:45 2007
//group＝1表示一个一个质数计算，threads＝2表示2个线程并行运算
18446744073709551557 , 17422 ms ( thread 2 , +17422 ms )
18446744073709551427 , 33813 ms ( thread 1 , +16391 ms )
18446744073709551533 , 35969 ms ( thread 2 , +2156 ms )
18446744073709551359 , 53203 ms ( thread 1 , +17234 ms )
18446744073709551521 , 54547 ms ( thread 2 , +1344 ms )
18446744073709551437 , 73078 ms ( thread 2 , +18531 ms )
18446744073709551263 , 74031 ms ( thread 1 , +953 ms )
18446744073709551337 , 92531 ms ( thread 2 , +18500 ms )
18446744073709551191 , 93063 ms ( thread 1 , +532 ms )
//9个质数总耗时93.063秒，平均每个质数10.34秒
//并行运算比单个线程快了374.5％——惊人的提升
//与A机的并行运算相比，也快了131.7％——作为双核系统，这个差距还算是正常
|
|
[2014-10-16]
人次