Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden

Menu
Weltrekordversuch an der FH Graubünden
Pi-Challenge
Der Weltrekord ist gebrochen!
Idee

Idee

Wir wollen aufzeigen, dass wir mit begrenztem Budget, Hardware und personellen Ressourcen die extrem speicherintensive Berechnung von Pi auf 62.8 Billionen Stellen effizient durchführen können. Als Referenz für unser Resultat dient uns der momentane Weltrekord für die höchste Anzahl von Pi-Stellen.

Hintergrund

Hintergrund

Die genauste Berechnung der Kreiszahl Pi ist ein inoffizieller Benchmark (Richtgrösse) im Hochleistungsrechnen. Da die Kenntnis von Billionen von Stellen einer transzendenten Zahl keinen praktischen Nutzen hat, liegt der Sinn auch nicht in der genauen Kenntnis dieser Ziffernfolge, sondern im Weg, diese Ziffernfolge berechnen zu können. Dafür ist nicht nur die passende Hardware nötig, sondern insbesondere auch die Expertise, diese Hardware richtig einzurichten, auf die eingesetzte Software abzustimmen und eine solche Berechnung über Wochen störungsfrei zu betreiben. Dieser Herausforderung stellt sich das Team des Zentrums für Datenanalyse, Visualisierung und Simulation (DAViS) der Fachhochschule Graubünden um IT-Projektleiter Thomas Keller und Zentrumsleiter Prof. Dr. Heiko Rölke.

Im Auftrag des Kantons Graubünden soll am DAViS fachspezifische HPC-Expertise (High-Performance Computing) gebündelt und dafür benötigte Infrastruktur bereitgestellt werden. Mit dem neuen Bachelorstudium Computational und Data Science wird dieser Bereich an der FH Graubünden weiter an Bedeutung gewinnen. Zukünftigen Studierenden wird mit der neu aufgebauten und optimierten HPC-Infrastruktur die Möglichkeit geboten, auf leistungsfähige Hardware zuzugreifen und so ihre theoretischen Kenntnisse aus dem Unterricht in der alltäglichen HPC-Praxis zu vertiefen.

Herausforderung

Herausforderung

FH Graubünden (Herausforderin)

Anzahl Stellen: 62'831'853'071'796
Berechnungstage: Ziel < 140 Tage
Start: 28.04.2021

Timothy Mullican (Rekordhalter)

Anzahl Stellen: 50'000'000'000'000
Berechnungstage: 303 Tage
Start: 01.04.2019

Google (ehemaliger Rekordhalter)

Anzahl Stellen: 31,415,926,535,897
Berechnungstage: 121 Tage
Start: 22.09.2018

Peter Trüb (ehemaliger Rekordhalter)

Anzahl Stellen: 22'459'157'718'361
Berechnungstage: 105 Tage
Start: 11.11.2016

Zwischenstand

Zwischenstand

News

30.08.2021 - Pi Verifikation

Eine Möglichkeit, um das Resultat unserer Pi Berechnung zu überprüfen, funktioniert so, dass mit einem weiteren Algorithmus die letzten Stellen von Pi überprüft werden (siehe erste Abbildung).

Im Vergleich dazu die letzten 32 Stellen aus unserer Chudnovsky Berechnung (zweite Abbildung). Beide Ergebnisse sind in hexadezimaler Schreibweise dargestellt.
Eine weitere Bestätigung unserer Berechnung wurde auf numberworld.org publiziert.

Berechnung der letzten 32 Stellen mithilfe des Bellard BBP Algorithmus.
Letzte 32 Pi-Stellen aus der Chudnvosky Berechnung.

14.08.2021 - Abschluss der Berechnung

Am Samstagmorgen um 9:30, hat unser Hochleistungscomputer die Pi-Berechnung auf genau 62'831'853'071'796 Stellen Präzision erfolgreich abgeschlossen. Daher sind nun zusätzliche 12.8 Billionen Stellen von Pi bekannt. Der Rekord von anhin 50 Billionen Stellen ist somit vom DAViS Team der FH Graubünden gebrochen worden!

Die letzten zehn bekannten Ziffern von Pi lauten: 7817924264

11.08.2021 - Dezimal Version von Pi erstellt

Heute Morgen um ca. 7:30 Uhr hat der Rechner die Konversion der 62.8 Billionen Stellen von hexadezimal nach dezimal abgeschlossen. Die Zahl liegt nun in 63 Dateien aufgeteilt und komprimiert auf dem Rechner.  Als nächstes überprüft die Software ob der Konversionsvorgang korrekt abgeschlossen wurde.

04.08.2021 - Hexadezimal Version von Pi berechnet

Nach etwas mehr als 92 Tagen Rechenzeit  hat Y-cruncher heute morgen, die hexadezimale Version von Pi auf die Festplatten unseres Rechners geschrieben. Die Zahl ist komprimiert und belegt daher nur etwa 24 TB Speicherplatz (anstatt 48 TB in unkomprimierter Form). Momentan konvertiert der Rechner die berechnete Zahl Pi in das dezimale Zahlensystem.

01.08.2021 - Berechnung «Inverse Square Root»

01.08.2021: Da y-cruncher nun das Herzstück des Chudnovsky Algorithmus am 25.7 fertig berechnet hat (in der untenstehenden Formel grün umrandet), berechnet die Software momentan den sogenannten «Inverse Square Root»* des Algorithmus. Das heisst, dass nun die unten dargestellte Berechnung ausgeführt wird. 

Beim Nenner dieses Bruches, handelt es sich um eine gigantisch grosse Zahl (Billionen von Stellen). Wir rechnen mit ca. 5-6 Tagen für diesen Berechnungsabschnitt

* Warum der Programmierer von Y-cruncher diesen Abschnitt als «Kehrwert einer Quadratwurzel» bezeichnet, ist uns nicht bekannt. Wir gehen jedoch davon aus, dass er die Multiplikation des Kehrwerts einer Division vorzieht, da sich diese Operation gemäss ihm schneller berechnen lässt. 

26.07.2021 - Backup und Berechnung zweiter Teil des Pi-Algorithmus

Das Backup der Berechnung ist nun abgeschlossen und seit einigen Stunden läuft die nächste Etappe, in der, der letzte Teil der Formel berechnet wird. Danach wird Y-cruncher eine Basiskonversion von Hexadezimal nach Dezimal vornehmen und die berechneten Stellen verifizieren. Wir schätzen mit ca. 3 - 4 Wochen bis zum Ende der Berechnung.

25.07.2021- Berechnung Chudnovsky Serie abgeschlossen

Unser Computer hat die Berechnung der Chudnovsky Reihe, innerhalb von 88 Tagen und 14 h, abgeschlossen! Die reine Rechenzeit (ohne Downtime) liegt bei 83 Tagen und 20 h. Als Nächstes starten wir ein Backup unserer berechneten Daten (ca. 51 TB). Für das Backup müssen wir die Berchnung jeweils unterbrechen.

Statistik

Pi-Berechnung abgeschlossen: 100 %
Pi-Verifikation abgeschlossen: 0 %
Downtime (Backup oder Wartung): 18.57h (Backup) / 27.55h (Backup) / 41.64h (Backup) / 25.51h (Backup) / 26.47h (Backup) - 139.74h (Total Downtime)

Hardware

Hardware

Für die Berechnung von Pi im Billionenstellen-Bereich sind enorm hohe Speichermengen (RAM und Auslagerungsspeicher) und tiefe Speicherzugriffszeiten wichtig. Die Prozessorenleistung ist bei dieser Art von Berechnung jedoch zweitrangig.

Prozessoren
2 AMD EPYC 7542 CPUs mit je 32 Kernen

Arbeitsspeicher
1 TB

Festplattenplatz
510 TB brutto

HDDs
38 Festplatten à 7'200 rpm und je 16 TB Speicherplatz. Davon werden 34 für das Swapping benutzt und 4 Festplatten für die Pi Speicherung verwendet

SSDs
2 SSDs für die Installation des Betriebssystems

Obwohl unser RAM im Vergleich zu einem Desktop-PC sehr gross bemessen ist, würde er nur für eine Berechnung von einigen 100 Milliarden Stellen ausreichen. Daher speichert das Berechnungsprogramm y-Cruncher einen grossen Teil des RAM auf der Festplatte. Diese Technik wird auch «Swapping» (Auslagern) genannt und kommt hier genauso wie auf einem regulären PC mit Windows oder Mac zum Einsatz. Aus Performance-Gründen wären SSDs (sehr schnelle Harddisks auf Basis von Halbleitertechnologien) bei dieser Art von Berechnung von grossem Vorteil. Jedoch erwarten wir bei der Pi-Berechnung und zukünftigen Berechnungen ein grosses Mass an Schreibzyklen, was bei SSDs einen hohen Verschleiss zur Folge hat. Da die Speicherpreise bei SSDs zusätzlich um den Faktor fünf bis zehn höher liegen als bei herkömmlichen HDDs, haben wir uns im Designprozess für HDDs entschieden. Dies betrifft jedoch nur den Speicherplatz für die Berechnungen. SSDs setzen wir für die Installation des Betriebssystems ein, da hier weniger Schreibzyklen anfallen und der Speicherplatzbedarf im Bereich von wenigen GB liegt.

Um den Geschwindigkeitsnachteil gegenüber SSDs etwas kompensieren zu können, haben wir y-Cruncher so konfiguriert, dass der Zugriff auf den Swap-Speicherplatz parallelisiert ausgeführt wird. Dies erlaubt uns eine aggregierte Read/Write-Geschwindigkeit auf die Daten im Swap von ca. 8.5 GB/s mithilfe von 34 HDDs. Dieselben Zugriffszeiten könnte man mit dem Einsatz von nur drei SSDs erreichen. Damit hätten wir aber den benötigten Speicherplatz von ca. 310 TB für den Swapspace bei weitem nicht erreichen können.

Alleine das Speichern des Ergebnisses von Pi benötigt 63 Terabyte Speicherplatz. Die Zwischenspeicherungen der Berechnung verschlingen nochmals bis zu 91 TB Festplattenplatz. Für das Swapping benötigen wir 310 TB Speicherplatz sowie knapp 180 TB Speicherplatz für das Backup der Zwischenspeicherungsdaten.

Das System für die Pi-Berechnung besteht aus zwei Einheiten:

Das System ist in einem Serverrack (Einbauschrank für Rechner) mit Kühlung und Notstromversorgung untergebracht, da bei einer Berechnung unter Volllast konstante Luftkühlung benötigt wird, um die Komponenten nicht zu überhitzen.

Energieverbrauch

Energieverbrauch

Die Recheneinheit mit CPUs, Memory und SSDs benötigt ca. 300 Watt Leistung. Das JBOD mit den 38 HDDs ca. 430 Watt.

Da der Rechner und die Disks im laufenden Betrieb sehr heiss werden können, (die CPU Kerne werden kurzfristig bis zu 80° C heiss, die Disks bis zu 40° C) muss diese Wärme mit einer Luftkühlung abgeführt werden. Gemäss American Power Conversion müssen wir zusätzlich geschätzte 950 Watt Kühlleistung aufwenden. Im Total brauchen wir für die Berechnung also ca. 1'700 Watt Leistung. Grob geschätzt würde dies einer Leistung von 1.75 GFlops/Watt entsprechen.

Zum Vergleich:

Software

Software

Die Berechnung von Pi wird mit der Software y-Cruncher durchgeführt. Diese Software kam auch bei bisherigen Weltrekordberechnungen zum Einsatz und zeichnet sich dadurch aus, dass sie moderne Hardwareeigenschaften des Prozessors nutzen kann. y-Cruncher wurde vom amerikanischen Entwickler Alexander Yee erstellt und kann auch auf einem handelsüblichen PC mit Windows oder Linux zur Berechnung von Konstanten wie Pi oder e benutzt werden.

Auf dem Rechner haben wir ein Linux-Betriebssystem (Ubuntu 20.04) installiert. Dieses System erlaubt vielfältige Eingriffsmöglichkeiten, um die Berechnungsgeschwindigkeit von Pi zu erhöhen. Unter anderem haben wir folgende Einstellungen vorgenommen, um die Ausführungsgeschwindigkeit zu verbessern:

  • Abschaltung von diversen Sicherheitsfunktionen
  • Aktivierung eines auf die Berechnung optimierten I/O Schedulers
  • Abschaltung von Stromspareinstellungen
  • Wechsel auf ein schnelleres Filesystem
  • Optimierungen am BIOS

Einige dieser Optimierungen haben oft auch schwerwiegende Nachteile zur Folge. Zum Beispiel können diese Änderungen eine tiefere Ausfallsicherheit oder höheren Stromverbrauch mit sich bringen. Andere Änderungen führen nur zu einem Zeitvorteil für eine spezifische Software oder Berechnungsart.

Algorithmus

Algorithmus

Bei der Zahl Pi handelt es sich um eine irrationale und transzendente Zahl. Dies bedeutet, dass die Zahl Pi weder als Bruch (irrational) noch als Polynom (transzendent) dargestellt werden kann.

1988 entwickelten die Brüder Chudnovsky den folgenden Algorithmus zur Berechnung der Zahl Pi:

Auffällig ist, dass die Summe (Sigma-Zeichen) bis unendlich (liegende Acht) geht. Dies ist darauf zurückzuführen, dass es sich bei Pi um eine irrationale Zahl handelt, welche konvergiert, aber nie mit endgültiger Präzision dargestellt werden kann. Daher kann der Algorithmus, der durch die zur Verfügung stehende Berechnungszeit limitiert wird, immer nur eine Annäherung der Zahl liefern. Der Algorithmus zählt zu den hypergeometrischen Reihen und braucht für die Berechnung hauptsächlich Ganzzahlen (Integers). Mithilfe dieser Ganzzahlen kann der Computer jeden Berechnungsschritt ohne Rundungen oder Approximierungen durchführen. Somit werden Rundungsfehler vermieden, welche zu Präzisionsfehlern führen können. Solche Rundungsfehler haben in der Vergangenheit bereits zu spektakulären Fehlern geführt.

Aktuell handelt es sich bei der Chudnovsky-Formel noch immer um die effizienteste Methode, um Pi auf eine beliebige Anzahl Stellen zu berechnen. Mithilfe dieser Methode wird die Zahl Pi mit einer Präzision von durchschnittlich 14.81 Stellen pro Iteration berechnet. Alle Weltrekorde der letzten Jahre  wurden mit diesem Verfahren berechnet. Dieser Algorithmus wurde in Y-Cruncher mit Hilfe von C/C++ implementiert und wird von uns genauso verwendet wie etwa von Timothy Mullican oder Google bei ihren jeweiligen Weltrekordversuchen.

Verifikation

Verifikation

Um die neu berechneten Stellen auf deren Richtigkeit zu überprüfen, gibt es zwei Möglichkeiten: Einerseits könnte man mit einem weiteren Algorithmus (zum Beispiel mit dem Gauss-Legendre-Algorithmus) die Anzahl Stellen nachrechnen. Dies würde jedoch nochmals mindestens so viel Zeit in Anspruch nehmen wie die ursprüngliche Berechnung. Glücklicherweise wurde 1995 durch Simon Plouffe die Bailey-Borwein-Plouffe-Formel entdeckt. Mit dieser kann eine beliebige Stelle der Zahl Pi ermittelt werden. Zum Beispiel die 10'581. Stelle, ohne Berechnung aller vorangehenden Stellen. Das Berechnen einer einzelnen Stelle von Pi ist jedoch sehr rechenintensiv (exponentielle Komplexität) und daher werden jeweils nur einige der letzten Ziffern von Pi verifiziert.  

Der französische Mathematiker Fabrice Bellard hat zwei Jahre später eine weitere und schnellere Möglichkeit gefunden, um zufällige Stellen von Pi zu berechnen. Diese wird auch von y-Cruncher benutzt, um die errechnete Zahl zu verifizieren.

Anwendungsgebiete

Anwendungsgebiete

High-Performance Computing (HPC), wie es zur Berechnung von mathematischen Konstanten nötig ist, wird heute in vielen Bereichen der angewandten Forschung und Entwicklung eingesetzt. Immer grösser werdende Datenmengen benötigen laufend leistungsfähigere Hardware und Software. HPC kommt daher auch bei der DNA-Sequenzanalyse oder beim maschinellen Lernen zum Einsatz.

Das DAViS bietet daher unter anderem Rechenleistung für das Projekt Translaturia (maschinelles Lernen) oder unterstützt die Allergie- und Asthmaforschung des SIAF (DNA-Sequenzanalyse) in Davos.

Team

Team

DAViS ist ein regionales Kompetenzzentrum für Forschung, Industrie und Lehre in den Bereichen Datenanalyse und wissenschaftlichem Rechnen. Dieses arbeitet mit dem von der ETH Zürich betriebenen, nationalen Hochleistungs-Rechenzentrum (CSCS) in Lugano zusammen und kooperiert mit dem Schweizerischen Institut für Allergie- und Asthmaforschung (SIAF) der Universität Zürich.

Da das DAViS Teil der FH Graubünden ist, können wir auf ein breites Spektrum an fachspezifischem Wissen und auf eine fortschrittliche IT-Infrastruktur zurückgreifen. Im Falle des Weltrekordversuchs haben wir beim Hardwareaufbau und der Inbetriebnahme des neuen Servers eng mit den Informatikdiensten der Fachhochschule zusammengearbeitet. 

Für Inputs und Fragen bezüglich Pi-Weltrekordversuch wenden Sie sich bitte an Thomas Keller oder Heiko Rölke

Weitere Teammitglieder

Swiss Institute of Allergy and Astma Research (SIAF)
PD, Ph.D. Katja Bärenfaller
+41 81 410 08 49
katja.baerenfaller@siaf.uzh.ch