• yoyo@home: Veröffentlichung zu Harmonious Trees und Odd Weird Search

    Eine neue Veröffentlichung von Wenjie Fang beschäftigt sich am Beispiel der beiden ehemaligen yoyo@home-Subprojekte Harmonious Trees und Odd Weird Search damit, wie bestimmte Fragestellungen, die nicht von Haus aus einfach parallelisierbar sind, dennoch effizient von Volunteer-Computing-Projekten bearbeitet werden können.

    Eine Veröffentlichung zu Harmonious Trees und Odd Weird Search
    Ja, es gab lange Zeit keine Neuigkeiten über die Ergebnisse der Subprojekte Harmonious Trees oder Odd Weird Search. Wir wussten nur, dass wir nichts gefunden haben, die Vermutungen nicht widerlegt und sogar gestärkt wurden. Das klingt etwas enttäuschend.

    Aber nein! In dieser Zeit haben wir fleißig an etwas gearbeitet. Es ist, um genau zu sein, ein Forschungsartikel, der beschreibt, was wir getan haben, um beide Projekte zu ermöglichen, was wir beobachtet haben und was wir tun können, um es zu verbessern (wenn aus einem ähnlichen Problem ein Volunteer-Computing-Projekt entstehen soll). Und schließlich, nach vielem Schreiben und Bearbeiten zwischen langen Zeiträumen der Prokrastination (ja, ich habe zwischendurch einen Doktorgrad in Mathematik erlangt und yoyo musste natürlich neben seiner Arbeit das Projekt unterhalten), wurde er heute endlich veröffentlicht!

    Unter dem Titel Parallel Tree Search in Volunteer Computing: a Case Study (engl., Parallele Baumsuche mit Volunteer Computing: eine Fallstudie) kann der Artikel hier gefunden werden:
    https://link.springer.com/article/10...723-017-9411-5 (engl.)

    Der Zugang ist frei, sodass es jeder kostenlos herunterladen und anschauen kann. Danke an die TU Graz (ich bin dort Postdoktorand), den FWF (der österreichische Wissenschaftsfonds) und die Bibliothek der TU Graz, dass sie eine Open-Access-Vereinbarung mit Springer haben. Andernfalls müssen die Autoren in der Regel tausende Dollar für die Open-Access-Option bezahlen. Also, viel Spaß damit, wenn es euch interessiert!

    Hier ist eine Kurzfassung des Artikels:

    Während sich Volunteer Computing, als ein eingeschränktes Modell parallelen Rechnens, als ein erfolgreiches Paradigma für wissenschaftliches Rechnen mit exzellenten Vorteilen bei der Kosteneffizienz und Öffentlichkeitsarbeit erwiesen hat, sind die meisten Probleme, die auf diesem Weg gelöst werden, intrinsisch hochparallel. Viele effiziente Algorithmen, darunter Rücksetzverfahren, nehmen jedoch die Form einer Baumsuche in einem extrem ungleichmäßigen Baum an, welche für das Volunteer-Computing-Paradigma nicht auf einfache Weise effizient parallelisierbar sind. Wir erforschen in diesem Artikel, wie solche Suchen effizient als Volunteer-Computing-Projekte durchgeführt werden können. Wir schlagen ein paralleles Suchbaum-Schema vor und beschreiben zwei reale Anwendungsbeispiele, Harmonious Tree und Odd Weird Search, welche beide beim Volunteer-Computing-Projekt yoyo@home durchgeführt wurden. Um die beobachtete Effizienz unseres Schemas zu bestätigen, nehmen wir eine mathematische Analyse vor, welche beweist, dass unser Schema unter vernünftigen Annahmen, die mit experimentellen Beobachtungen übereinstimmen, nur einen konstanten Faktor von perfekter Parallelität entfernt ist. Einzelheiten zur Verbesserung der Gesamtleistung werden ebenfalls diskutiert.
    24.10.2017

    Originaltext:
    Zitat Zitat von https://www.rechenkraft.net/yoyo/
    A publication on Harmonious Trees and Odd Weird Search
    It has been a long time, we know, that there was no news whatsoever the results of Harmonious Trees, or Odd Weird Search. All we knew was that we found nothing, the conjectures remained safe, and even taking on more credence. It sounds a bit anti-climatic.

    But no! In this interval, we have been busy working on something. It is a research article, to be precise, that describes what we did to make both projects possible, what we observed, and what we can do to make it better (if there is a similar problem to be made into a volunteer computing project). And finally, after a lot of writing and editing in between great periods of procrastination (yes, I did a PhD in math in between, and yoyo of course needs to maintain the project alongside his work), today it is finally published!

    Titled Parallel Tree Search in Volunteer Computing: a Case Study, the article can be found here:
    https://link.springer.com/article/10...723-017-9411-5

    It is open access, meaning that everyone can download it and have a look freely. Thanks to TU Graz (I am a postdoc there), FWF (the Austria founding agency) and the library of TU Graz for having an open access arrangement with Springer. Otherwise, the authors generally have to pay thousands of dollars for the open access option. So, enjoy if you are interested!

    Here is an abstract of the article:

    While volunteer computing, as a restricted model of parallel computing, has proved itself to be a successful paradigm of scientific computing with excellent benefit on cost efficiency and public outreach, many problems it solves are intrinsically highly parallel. However, many efficient algorithms, including backtracking search, take the form of a tree search on an extremely uneven tree that cannot be easily parallelized efficiently in the volunteer computing paradigm. We explore in this article how to perform such searches efficiently on volunteer computing projects. We propose a parallel tree search scheme, and we describe two examples of its real-world implementation, Harmonious Tree and Odd Weird Search, both carried out at the volunteer computing project yoyo@home. To confirm the observed efficiency of our scheme, we perform a mathematical analysis, which proves that, under reasonable assumption that agrees with experimental observation, our scheme is only a constant multiplicative factor away from perfect parallelism. Details on improving the overall performance are also discussed.
    24 Oct 2017
    Ursprünglich wurde dieser Artikel in diesem Thema veröffentlicht: Cafe yoyo (News, Begrüßungen, SmallTalk zum Projekt & ...) - Erstellt von: RealSanta Original-Beitrag anzeigen
Single Sign On provided by vBSSO