y-cruncher - A Multi-Threaded Pi-Program
From a high-school project that went a little too far...
By Alexander J. Yee
(Last updated: March 22, 2015)
The first scalable multi-threaded Pi-benchmark for multi-core systems...
How fast can your computer compute Pi?
y-cruncher is a program that can compute Pi and other constants to trillions of digits.
It is the first of its kind that is multi-threaded and scalable to multi-core systems. Ever since its launch in 2009, it has become a common benchmarking and stress-testing application for overclockers and hardware enthusiasts.
y-cruncher has been used to set several world records for the most digits of Pi ever computed.
Windows: Version 0.6.8 Build 9460 (Released: March 17, 2015)
Linux : Version 0.6.8 Build 9460 (Released: March 17, 2015)
Official Xtremesystems Forums thread.
Version v0.6.8 Patched: (March 17, 2015)
I totally knew this would happen... The moment I rush a release (for Pi Day), something breaks.
It turns out there was a very large (up to 5%) performance regression on Haswell processors that scales inversely with the memory bandwidth of the system. Normally, such large regressions are caught long before they can be released. But since my primary test machine has 4 channels of overclocked DDR4, I never noticed the regression at all. It was only after Shigeru Kondo reported this did I test it on a different Haswell machine which did reproduce the regression.
This screw-up involved a cache optimization that was designed into the algorithm from the very beginning rather than being added later as a result of profiling. Being a premature optimization, it backfired for small computations and had no noticeable effect for large ones on my machine. Therefore I disabled it sometime between v0.6.7 and v0.6.8. Not a big deal, I expect some of these premature micro-optimizations to backfire.
Well... It turns out that the premature optimization wasn't really that premature after all. On large computations, it reduces the demand on memory bandwidth. If the processor is bandwidth-starved (such as mainstream Haswell), it translates to an increase in performance. Therefore, this patch re-enables the optimization on all processors except for AMD Bulldozer - which takes a 10% performance hit for some unknown reason.
The sad part is that, back in 2012, I did this optimization because I predicted that it would reduce the demand on memory bandwidth. But it wasn't until 2015 did the hardware and software become fast enough for it to actually make a difference. During those 3 years, I completely forgot about the optimization and left it in the "on" position until a recent refactoring touched it. That prompted me to re-evaluate it and (erroneously) disable it for the Pi day v0.6.8 release.
Pi Day of the Century: (March 14, 2015)
Surprise! There was no way I could possibly pass this day up right?
y-cruncher v0.6.8 is out with some new features:
y-cruncher has been used to set a number world record size computations.
Blue: Current World Record
Green: Former World Record
Red: Unverified computation. Does not qualify as a world record until verified using an alternate formula.
|Date Announced||Date Completed:||Source:||Who:||Constant:||Decimal Digits:||Time:||Computer:|
|March 21, 2015||March 19, 2015||Andreas Stiller||Lemniscate||40,000,000,000||
|4 x Xeon E7-4890 v2 @ 2.8 GHz
(2 nodes only - 60 vCPUs)
256 GB DDR3
|February 9, 2015||February 9, 2015||Randy Ready||Lemniscate||15,000,000,000||Amazon Web Services
2 x Xeon E5-2670 v2 @ 2.5 GHz
(32 Logical Cores only)
240 GB DDR3
|October 8, 2014||October 7, 2014||"houkouonchi"||Pi||13,300,000,000,000||
|2 x Xeon E5-4650L @ 2.6 GHz
192 GB DDR3 @ 1333 MHz
24 x 4 TB + 30 x 3 TB
|March 24, 2014||March 10, 2014||Shigeru Kondo||Log(10)||200,000,000,050||
|2 x Xeon E5-2690 @ 3.3 GHz
256 GB DDR3 @ 1600 MHz
12 x 3 TB
|February 28, 2014||Shigeru Kondo||Log(2)||200,000,000,050||
|2 x Xeon E5-2690 @ 3.3 GHz
256 GB DDR3 @ 1600 MHz
12 x 3 TB
|December 28, 2013||December 28, 2013||Source||Shigeru Kondo||Pi||12,100,000,000,050||2 x Xeon E5-2690 @ 2.9 GHz
128 GB DDR3 @ 1600 MHz
24 x 3 TB
|December 22, 2013||December 22, 2013||Alexander Yee||Euler-Mascheroni Constant||119,377,958,182||
2 x Intel Xeon X5482 @ 3.2 GHz
64 GB DDR2 FB-DIMM
64 GB SSD (Boot) + 2 TB (Data)
8 x 2 TB (Computation)
|September 13, 2013||September 13, 2013||Source||Setti Financial LLC||Zeta(3) - Apery's Constant||200,000,001,000||
Compute: ~5 months
|Intel Core i5-3570S @ 3.1 GHz
|April 8, 2013||April 8, 2013||Source||Setti Financial LLC||Catalan's Constant||100,000,000,000||
Compute: ~4 months
|2 x Intel Xeon X5460 @ 3.16 GHz
16 GB DDR2
|February 9, 2012||February 9, 2012||Alexander Yee||Square Root of 2||2,000,000,000,050||2 x Xeon X5482 @ 3.2 GHz - 64 GB
8 x 2 TB
Core i7 2600K @ 4.4 GHz - 16 GB
5 x 1 TB + 5 x 2 TB
|September 17, 2010||September 17, 2010||Source||Alexander Yee||Zeta(3) - Apery's Constant||100,000,001,000||"Nagisa" + "Ushio"|
|July 8, 2010||July 8, 2010||Source||Alexander Yee||Golden Ratio||1,000,000,000,000||
*Not a continuous run.
2 x Intel Xeon X5482 @ 3.2 GHz
64 GB DDR2 FB-DIMM
1.5 TB (Boot + Output)
4 x 1 TB (2 x 2 RAID0) + 6 x 2 TB
|July 5, 2010||July 5, 2010||Source||Shigeru Kondo||e||1,000,000,000,000||Intel Core i7 980X @ 3.33 GHz
12 GB DDR3
2 TB (Boot + Output)
8 x 1 TB (Computation)
|April 16, 2009||April 16, 2009||Source||Alexander Yee &
Compute: 178 hours
Verify: 221 hours
See the complete list.
Aside from computing Pi and other constants, y-cruncher is great for stress testing 64-bit systems with lots of ram.
Latest Release: (March 17, 2015)
- Windows Vista or later.
- You may need to install: Microsoft Visual C++ 2013 Redistributable Package
- Privilege elevation is needed to run y-cruncher. So this may result in UAC prompts.
See the FAQ for why y-cruncher needs privilege elevation.
- 64-bit Linux is required. There is no support for 32-bit.
- You may need to enable execute permissions. This can be done by running the following command on the y-cruncher directory: "chmod -R 777 *.out"
- An x86 or x64 processor with SSE3 instructions. This shouldn't be a problem since nearly all PCs since 2006 has them.
Main Page: y-cruncher - Version History
Other Downloads (for C++ programmers):
Comparison Chart: (Last updated: February 24, 2015)
Computations of Pi to various sizes. All times in seconds. All times include the time needed to convert the digits to decimal representation.
|Processor(s):||Core 2 Quad Q6600||Core i7 920||Core i7 3630QM||FX-8350||Core i7 4770K||Core i7 5960X|
|Generation:||Intel Core||Intel Nehalem||Intel Ivy Bridge||AMD Piledriver||Intel Haswell||Intel Haswell|
|Processor Speed:||2.4 GHz||3.5 GHz (OC)||2.4 GHz (3.2 GHz turbo)||4.0 GHz (4.2 GHz turbo)||4.0 GHz (OC)||4.0 GHz (OC)|
|Memory:||6 GB - 800 MHz||12 GB - 1333 MHz||8 GB - 1600 MHz||16 GB - 1333 MHz||32 GB - 1866 MHz||64 GB - 2666 MHz|
|Version:||v0.6.3 - SSE3||v0.6.3 - SSE4.1||v0.6.7 - AVX||v0.6.7 - XOP||v0.6.7 - AVX2||v0.6.7 - AVX2|
|Processor(s):||2 x Xeon X5482||2 x Xeon E5-2690*|
|Generation:||Intel Penryn||Intel Sandy Bridge|
|Processor Speed:||3.2 GHz||3.5 GHz|
|Memory:||64 GB - 800 MHz||256 GB - ???|
|Version:||v0.6.3 - SSE4.1||v0.6.2/3 - AVX|
*Credit to Shigeru Kondo.
The full chart of rankings for each size can be found here:
These fastest times may include unreleased betas.
Got a faster time? Let me know: firstname.lastname@example.org
If you're interested in what formulas and algorithms y-cruncher uses:
Main Page: y-cruncher - Language and Algorithms
Q: Is there a version that can use the GPU?
A: No. As of 2015, GPUs are no better than CPUs for large number arithmetic.
- GPUs are optimized for single-precision performance. Their double-precision and 64-bit integer throughput is far from impressive.
As of 2015, every single large integer multiplication algorithm uses either double-precision, 64-bit integer multiply, or carry-propagation. All of these operations are inefficient on current GPUs. And no, single-precision cannot be used because it imposes size limits that make the algorithms useless.
Device Frequency Double-Precision Throughput Price Nvidia GeForce GTX Titan X 1 GHz 192 GFlops $1000 Intel Core i7 5960X 3 GHz 384 GFlops $1000
- GPUs require massive vectorization. Large number arithmetic is difficult to vectorize due to carry-propagation. The speedups that are currently achieved with CPU vectorization (SSE, AVX) are only modest at best.
- Large computations of Pi and other constants are not limited by computing power. The bottleneck is in the data communication. (memory bandwidth, disk I/O, etc...) So throwing GPUs at the problem (even if they could be utilized) would not help much.
Fundamental issues aside, the biggest practical barrier would be the need to rewrite the entire program using GPU programming paradigms.
It is worth mentioning the Xeon Phi co-processor line. Programming for these do not require a change of programming paradigm. Furthermore, the ISA convergence to AVX512 between Skylake and Knights Landing makes Xeon Phi even more attractive. But regardless of how awesome this may be, it's still limited by PCIe bandwidth and disk I/O. For something that I have absolutely no other use for, Xeon Phi is far too expensive.
Q: Why can't you use distributed computing to set records?
A: No for more or less the same reasons that GPUs aren't useful.
- Just as with GPUs, computational power is not the bottleneck. It is the data communication. For this to be feasible as of 2015, everyone would need to have an internet connection speed of more than 1 GB/s. Anything slower than that and it's faster to do it on a single computer.
- Computing a lot of digits requires a lot of memory which would need to be distributed among all the participants. But there is no tolerance for data loss and distributed computing means that participants can freely join or leave the network at any time. Therefore, a tremendous amount of redundancy will be needed to ensure that no data is lost when participants leave.
Q: Is there a distributed version that performs better on NUMA and HPC clusters?
A: Not specifically. y-cruncher is still a shared memory program, so it inherently will not scale well into large networks.
As far as tweaks go, y-cruncher is known to be more sensitive to memory bandwidth than latency. So some performance can be gained by interleaving memory so that the bandwidth from all nodes are utilized. On Linux this can be done using: numactl --interleave=all "./y-cruncher.out"
Q: Is there a publicly available library for the multi-threaded arithmetic that y-cruncher uses?
A: This was something I tried back in 2012, but it didn't work out. The problem is that the interface changes far too quickly for it to be maintainable.
That said it is still possible to make this happen. The easy way is to fork out a static version of the library. But this means that it will never get updated with future optimizations. The harder approach is to build a compatibility layer to a static interface. But this will be increasingly difficult to do efficiently as the static interface falls further and further behind the internal interface. In some cases, it may not even be possible when a newer version completely removes an old feature. (This will happen in v0.6.8 when the concept of "threads" will be replaced with "task decomposition".)
Q: What's the deal with the privilege elevation? Why does y-cruncher need administrator privileges in Windows?
A: Privilege elevation is needed to work-around a security feature that would otherwise hurt performance.
In Swap Mode, y-cruncher creates large files and writes to them non-sequentially. When you create a new file and write to offset X, the OS will zero the file from the start to X. This zeroing is done for security reasons to prevent the program from reading data that has been leftover from files that have been deleted.
The problem is that this zeroing incurs a huge performance hit - especially when these swap files could be terabytes large. The only way to avoid this zeroing is to use the SetFileValidData() function which requires privilege elevation.
Linux doesn't have this problem since it implicitly uses sparse files.
Q: Why is the performance so poor for small computations? The program only gets xx% CPU utilization on my xx core machine for small sizes!!!
A: For small computations, there isn't much that can be parallelized. In fact, spawning N threads for an N core machine may actually take longer than the computation itself! In these cases, the program will decide not to use all available cores. Therefore, parallelism is really only helpful when there is a lot of work to be done.
As an additional note, y-cruncher has never been particularly efficient with the way it uses threads. Historically it always spawns new threads for tasks and then kills them when the task is done. While this works fine for large computations, it has a lot of overhead for small ones. This is partially being addressed in v0.6.8 with a revamp of the threading framework.
Q: Is y-cruncher open-sourced?
A: In short no. But roughly 5% of the code (mostly involving the Digit Viewer) is open sourced.
Here's some interesting sites dedicated to the computation of Pi and other constants:
Contact me via e-mail. I'm pretty good with responding unless it gets caught in my school's junk mail filter.