High performance peer-to-peer desktop grid computing : architecture, methods, applications

Abstract

Although today’s largest Desktop Grid harvests idle cycles from only 0.46‰ of the Personal Computers (PC) deployed world-wide, it is way ahead of the currently fastest supercomputer with respect to raw computing performance. If it were possible to attract roughly 7% of the world’s PC owners to donate their resources, the resulting virtual supercomputer would right now punch through the exascale barrier expected to be broken by supercomputers not until around the year 2020.

However, the full potential of Desktop Grid Computing has not yet been unleashed in another respect: application support. Due to their centralized interaction model Desktop Grids are currently limited to embarrassingly parallel applications. By complementing the foundations of Desktop Grid Computing systems with Peer-to-Peer concepts and methods, their scope can be extended to non-trivial applications from the field of High-Performance Computing, like parallel search problems – including discrete optimization, constraint satisfaction, and satisfiability solving –, Raytracing, or N-Body simulations. These applications are all instances of a special class of parallel applications called Irregularly Structured Problems (ISP). Their computation and interaction patterns are input-dependent, unstructured, and evolving.

The incorporation of Peer-to-Peer methods has impact on many aspects of Desktop Grid Computing systems: Their architecture has to be retrofitted to support decentralized operation by multiple authorities in a secure and safe environment. The plethora of algorithmic alternatives available beyond Client/Server interaction requires the system to be designed for extensibility from the ground up. Solving task-parallel ISPs requires much more sophisticated platform support in the form of a distributed task pool that is able to perform dynamic decomposition, load balancing, and termination detection in a decentralized and fault-tolerant way. To support this decentralized execution model the underlying network substrate must provide efficient Peer-to-Peer unicast and multicast primitives and the ability to rapidly report available resources and their vanishing, both without seriously impairing scalability.

Cohesion, the next generation Desktop Grid Computing platform described in this thesis, is an amalgamation of novel approaches designed to tackle these challenges. It’s capacity to efficiently execute task-parallel ISPs in volatile and heterogeneous Desktop Grids is demonstrated by means of Satciety, a state-of-the-art distributed SAT solver build on top of Cohesion.

Obwohl das derzeit größte Desktop Grid der Welt nur etwa 0.46‰ der Ressourcen der weltweit vorhandenen Personal Computer (PC) nutzt, ist es bezüglich der reinen Rechenkraft dennoch deutlich leistungsfähiger als die zurzeit schnellsten Supercomputer. Gelänge es nur 7% der weltweiten PC Eigentümer zu überzeugen die Ressourcen ihrer Rechner einem Desktop Grid zur Verfügung zu stellen, durchstöße der entstehende virtuelle Supercomputer bereits heute die Exascale-Schwelle, die von konventionellen Supercomputern voraussichtlich erst um das Jahr 2020 erreicht werden wird.

Das volle Potential des Desktop Grid Computing wird bislang aber auch bezüglich der Anwendungsunterstützung noch nicht realisiert. Aufgrund ihres zentralisierten Aufbaus eignen sich aktuelle Desktop Grids lediglich für sehr einfache parallele Anwendungen. Durch die Nutzung von Konzepten aus dem Peer-to-Peer Computing könnte die Anwendbarkeit des Ansatzes auf nicht-triviale Anwendungen aus dem Hochleistungsrechnen ausgeweitet werden. Dazu gehören Suchprobleme, wie die diskrete Optimierung, das Bedingungserfüllungsproblem, und das Erfüllbarkeitsproblem, aber auch Raytracing und N-Körper-Simulationen. Alle diese Anwendungen gehören zur Klasse der Irregulär-Strukturierten Probleme (ISP). Sie zeichnen sich durch stark eingabeabhängige, unstrukturierte und sich über die Zeit verändernde Verarbeitungs- und Interaktionsmuster aus.

Der Einsatz von Peer-to-Peer Mechanismen hat Einfluss auf zahlreiche Aspekte einer Desktop Grid Computing Plattform: Die Architektur muss dezentralisiert werden und eine sichere Ausführung von Anwendungen in einem Umfeld erlauben, das nicht von einer einzigen vertrauenswürdigen Authorität kontrolliert wird. Die Plattform muss außerdem auf Erweiterbarkeit ausgelegt sein, um die Vielzahl unterschiedlicher spezialisierter verteilter Algorithmen jenseits des Client/Server Paradigmas zu unterstützen. Um die effiziente Ausführung task-paralleler ISPs zu gewährleisten, muss die Plattform einen verteilten Taskpool bereitstellen, der es erlaubt Probleme dynamisch zur Laufzeit zu zerlegen, die Teilprobleme innerhalb des Desktop Grids zu verteilen, im Fehlerfall verlorene Tasks wiederherzustellen und schließlich das Ende der verteilten Berechnung zu erkennen. Dazu ist auf Ebene des Netzwerksubstrates die Verfügbarkeit effizienter Mechanismen für die Punkt-zu-Punkt und die Gruppenkommunikation von entscheidender Bedeutung. Außerdem muss der Status von Ressourcen bezüglich ihrer Verfügbarkeit effizient und zeitnah kommuniziert werden. All dies ohne die Skalierbarkeit der Plattform zu beeinträchtigen.

Cohesion, die in dieser Arbeit beschriebene Desktop Grid Computing Plattform der nächsten Generation, löst diese Herausforderungen durch den kombinierten Einsatz neuer und bewährter Methoden. Das Potential der Plattform zur Ausführung nicht-trivialer Anwendungen wird anhand eines verteilen Solvers für das Erfüllbarkeitsproblem namens Satciety demonstriert.