Der deutsche Philosoph Friedrich Nietzsche sagte einmal: „Unsichtbare Fäden sind die stärksten Bindungen.“ Man könnte sich „unsichtbare Fäden“ vorstellen, die verwandte Objekte miteinander verbinden, wie die Häuser auf der Route eines Lieferfahrers, oder nebulösere Einheiten, wie Transaktionen in einem Finanznetzwerk oder Benutzer in einem sozialen Netzwerk.
Der Informatiker Julian Shun untersucht diese Artwork vielschichtiger, aber oft unsichtbarer Verbindungen mithilfe von Diagrammen, in denen Objekte als Punkte oder Scheitelpunkte dargestellt werden und die Beziehungen zwischen ihnen durch Liniensegmente oder Kanten modelliert werden.
Shun, ein neuer außerordentlicher Professor am Fachbereich Elektrotechnik und Informatik, entwirft Diagrammalgorithmen, mit denen der kürzeste Weg zwischen Häusern auf der Route des Zustellfahrers ermittelt oder betrügerische Transaktionen böswilliger Akteure in einem Finanznetzwerk erkannt werden könnten.
Doch mit zunehmender Datenmenge sind solche Netzwerke auf Milliarden oder sogar Billionen von Objekten und Verbindungen angewachsen. Um effiziente Lösungen zu finden, entwickelt Shun Hochleistungsalgorithmen, die paralleles Rechnen nutzen, um selbst die umfangreichsten Diagramme schnell zu analysieren. Da paralleles Programmieren bekanntermaßen schwierig ist, entwickelt er auch benutzerfreundliche Programmier-Frameworks, die es anderen erleichtern, eigene effiziente Graphalgorithmen zu schreiben.
„Wenn Sie in einer Suchmaschine oder einem sozialen Netzwerk nach etwas suchen, möchten Sie sehr schnell zu Ergebnissen kommen. Wenn Sie versuchen, betrügerische Finanztransaktionen bei einer Financial institution zu identifizieren, möchten Sie dies in Echtzeit tun, um Schäden zu minimieren. Parallele Algorithmen können die Arbeit beschleunigen, indem sie mehr Rechenressourcen verbrauchen“, erklärt Shun, der auch leitender Forscher am Laptop Science and Synthetic Intelligence Laboratory (CSAIL) ist.
Solche Algorithmen werden häufig in On-line-Empfehlungssystemen eingesetzt. Suchen Sie auf einer E-Commerce-Web site nach einem Produkt und die Chancen stehen intestine, dass Sie schnell eine Liste verwandter Artikel sehen, die Sie auch in Ihren Warenkorb legen könnten. Diese Liste wird mithilfe von Diagrammalgorithmen erstellt, die Parallelität nutzen, um verwandte Elemente in einem riesigen Netzwerk von Benutzern und verfügbaren Produkten schnell zu finden.
Campus-Verbindungen
Shuns einzige Erfahrung mit Computern als Teenager struggle ein Excessive-College-Kurs zum Erstellen von Web sites. Er interessierte sich mehr für Mathematik und Naturwissenschaften als für Technik und beabsichtigte, eines dieser Fächer als Hauptfach zu belegen, als er sich als Pupil an der College of California in Berkeley einschrieb.
Doch in seinem ersten Jahr empfahl ihm ein Freund, einen Einführungskurs in die Informatik zu belegen. Obwohl er nicht sicher struggle, was ihn erwarten würde, beschloss er, sich anzumelden.
„Ich habe mich in das Programmieren und Entwerfen von Algorithmen verliebt. Ich bin zur Informatik gewechselt und habe es nie bereut“, erinnert er sich.
Der erste Informatikkurs fand im Selbststudium statt, daher brachte sich Shun den Großteil des Stoffes selbst bei. Ihm gefielen die logischen Aspekte der Algorithmenentwicklung und die kurze Rückkopplungsschleife bei Informatikproblemen. Shun konnte seine Lösungen in den Laptop eingeben und sofort sehen, ob er richtig oder falsch lag. Und die Fehler in den falschen Lösungen würden ihn zur richtigen Antwort führen.
„Ich habe immer gedacht, dass es Spaß macht, Dinge zu bauen, und beim Programmieren baut man Lösungen, die etwas Nützliches bewirken. Das hat mich gereizt“, fügt er hinzu.
Nach seinem Abschluss verbrachte Shun einige Zeit in der Industrie, erkannte jedoch bald, dass er eine akademische Laufbahn einschlagen wollte. Er wusste, dass er an einer Universität die Freiheit haben würde, sich mit Problemen zu befassen, die ihn interessierten.
Einstieg in die Grafik
Er schrieb sich als Doktorand an der Carnegie Mellon College ein, wo er sich in seiner Forschung auf angewandte Algorithmen und paralleles Rechnen konzentrierte.
Als Pupil hatte Shun theoretische Algorithmenkurse und praktische Programmierkurse besucht, aber die beiden Welten passten nicht zusammen. Er wollte Forschung betreiben, die Theorie und Anwendung vereinte. Parallele Algorithmen passten perfekt.
„Beim Parallelrechnen muss man sich um praktische Anwendungen kümmern. Das Ziel des Parallelrechnens besteht darin, die Dinge im wirklichen Leben zu beschleunigen. Wenn Ihre Algorithmen additionally in der Praxis nicht schnell sind, sind sie nicht so nützlich“, sagt er.
An der Carnegie Mellon lernte er Diagrammdatensätze kennen, bei denen Objekte in einem Netzwerk als durch Kanten verbundene Scheitelpunkte modelliert werden. Er fühlte sich von den vielen Anwendungen dieser Artwork von Datensätzen angezogen und von der Herausforderung, effiziente Algorithmen für deren Verarbeitung zu entwickeln.
Nach Abschluss eines Postdoktorandenstipendiums in Berkeley suchte Shun nach einer Fakultätsstelle und entschloss sich, dem MIT beizutreten. Er hatte mit mehreren MIT-Fakultätsmitgliedern an der Parallel-Computing-Forschung zusammengearbeitet und struggle begeistert, einem Institut mit so umfassender Experience beizutreten.
In einem seiner ersten Projekte nach seinem Eintritt am MIT arbeitete Shun mit dem Professor für Elektrotechnik und Informatik und CSAIL-Kollegen Saman Amarasinghe, einem Experten für Programmiersprachen und Compiler, zusammen, um ein Programmierframework für die Graphverarbeitung namens zu entwickeln GraphIt. Das benutzerfreundliche Framework, das aus Excessive-Degree-Spezifikationen effizienten Code generiert, struggle etwa fünfmal schneller als der nächstbeste Ansatz.
„Das struggle eine sehr fruchtbare Zusammenarbeit. Wenn ich alleine gearbeitet hätte, hätte ich keine so leistungsstarke Lösung entwickeln können“, sagt er.
Shun erweiterte seinen Forschungsschwerpunkt auch um Clustering-Algorithmen, die darauf abzielen, verwandte Datenpunkte zu gruppieren. Er und seine Studenten entwickeln parallele Algorithmen und Frameworks zur schnellen Lösung komplexer Clustering-Probleme, die für Anwendungen wie Anomalieerkennung und Group-Erkennung verwendet werden können.
Dynamische Probleme
In letzter Zeit haben er und seine Mitarbeiter sich auf dynamische Probleme konzentriert, bei denen sich Daten in einem Graphennetzwerk im Laufe der Zeit ändern.
Wenn ein Datensatz Milliarden oder Billionen Datenpunkte umfasst, kann es aus rechnerischer Sicht äußerst kostspielig sein, einen Algorithmus von Grund auf auszuführen, um eine kleine Änderung vorzunehmen. Er und seine Studenten entwerfen parallele Algorithmen, die viele Aktualisierungen gleichzeitig verarbeiten und so die Effizienz verbessern und gleichzeitig die Genauigkeit bewahren.
Aber diese dynamischen Probleme stellen auch eine der größten Herausforderungen dar, an deren Bewältigung Shun und sein Group arbeiten müssen. Da nicht viele dynamische Datensätze zum Testen von Algorithmen verfügbar sind, muss das Group häufig synthetische Daten generieren, die möglicherweise nicht realistisch sind und die Leistung ihrer Algorithmen in der realen Welt beeinträchtigen könnten.
Letztendlich ist es sein Ziel, dynamische Graphalgorithmen zu entwickeln, die in der Praxis effizient funktionieren und gleichzeitig theoretischen Garantien standhalten. Das stellt sicher, dass sie in einem breiten Spektrum von Umgebungen anwendbar sind, sagt er.
Shun geht davon aus, dass dynamische parallele Algorithmen in Zukunft einen noch größeren Forschungsschwerpunkt haben werden. Da Datensätze immer größer und komplexer werden und sich immer schneller ändern, müssen Forscher effizientere Algorithmen entwickeln, um mithalten zu können.
Er geht auch davon aus, dass Fortschritte in der Computertechnologie neue Herausforderungen mit sich bringen werden, da Forscher neue Algorithmen entwickeln müssen, um die Eigenschaften neuartiger {Hardware} zu nutzen.
„Das ist das Schöne an der Forschung – ich kann versuchen, Probleme zu lösen, die andere Menschen noch nicht gelöst haben, und so etwas Nützliches für die Gesellschaft beitragen“, sagt er.