Flüssiger Parallelrechner

News: Flüssiger Parallelrechner

Es gibt in der Mathematik so manches vermeintlich einfache Problem, dass bei einer größeren Anzahl von Parametern leicht zur harten Nuss werden kann, an der sich selbst Großrechner tagelang die Zähne ausbeißen. Eine derartig vertrackte Aufgabe ist die Suche nach der sogenannten größten Clique - einem System, bei dem die einzelnen Elemente mit jedem anderen in Verbindung stehen. Wissenschaftler haben nun eine recht unkonventionelle aber ungewöhnlich schnelle Methode gefunden, das Problem anzugehen: Sie panschen mit gefärbten Wasser.

Thorsten Krome

Optimierungsaufgaben können so manchen schnellen Rechner ganz schön in die Knie zwingen. Ein Beispiel für eine solche Knacknuss ist das so genannte Problem des Handlungsreisenden oder auch Travelling-Salesman-Problem (TSP). Hier soll der kürzeste Weg gefunden werden, der eine bestimmte Anzahl von Städten miteinander verbindet. Die Länge der einzelnen Teilstrecken ist dabei bekannt. Das TSP ist das Paradebeispiel für eine Klasse von Aufgaben, die Mathematiker und Informatiker NP-vollständig nennen. Und das ist im Prinzip synonym für lange Rechenzeit, denn bislang ist es noch niemandem gelungen, ein Verfahren zu entwickeln, das nicht exponentiell mit der Anzahl der Städte aufwendiger wird.

Nicht genug damit, dass der Handlungsreisende Computer ohnehin schon an ihre Grenzen bringt, es gibt auch einen nahen Verwandten, der es ebenfalls in sich hat: Hier ist aus einem gegebenen Netzwerk zwischen mehreren Städten das größte Unternetzwerk gesucht, bei dem jede Stadt von jeder anderen erreichbar ist. Man spricht auch von der Suche nach der größten Clique oder dem Maximal-Clique-Problem (MCP).

George Whitesides und seine Kollegen an der Harvard University haben nun eine Art Rechner gebaut, der das Problem zu lösen vermag. Allerdings rechnet ihr Gerät nicht mit Elektronen, sondern mit Wasser. So gelingt es den Wissenschaftlern, das Problem parallel anzugehen und vergleichsweise schnell eine Lösung zu erhalten.

Wie sieht der Rechner der Amerikaner aus? Im Wesentlichen handelt es sich um ein kleines System aus Kanälen, die gerade mal einen halben Millimeter dick sind, sowie winzigen Flüssigkeitstanks und mikroskopischen Quellen. All das haben die Wissenschaftler mit einer lithographischen Technik in einzelne Lagen aus Kunststoff gebannt, wobei jede Lage eine Verbindung zwischen zwei Städten repräsentiert. Aus der untersten Lage tropft das Nass aller Quellen schließlich in ein Abwasserbecken.

Die größte Clique ist bei diesem System nun schnell gefunden – es ist die Quelle mit dem größten Durchfluss. Um sie zu erkennen, haben die Forscher dem Wasser ein fluoreszierendes Kontrastmittel hinzugegeben, das leuchtet, wenn es angestrahlt wird. Dabei ist das Leuchten dort am hellsten, wo auch der Fluss am größten ist.

Auf diese Weise haben die Wissenschaftler einen vierlagigen Stapel benutzt, um das Problem mit drei Städten zu lösen, und einen komplexeren 16-lagigen, um die Lösung des Sechs-Städte-Problems zu finden. Bislang lässt sich mit dieser Technik also noch kein Neuland betreten. Denn die Forscher gehen davon aus, dass sich mit ihrem Verfahren und vertretbarem Aufwand maximal ein Vierzig-Städte-Problem lösen lässt, dessen Lösung aber auch auf einem normalen Rechner nur zwanzig Minuten benötigt.

Nichtsdestotrotz werden solche miniaturisierten Netzwerke zunehmend interessant für die Mikrofluidtechnik, bei der ein komplettes Laboratorium auf einem Chip verwirklicht werden soll. Deshalb ist der vielleicht interessanteste Aspekt der Arbeit, dass sich Kontrollmechanismen aus dem Computerbereich auf klitzekleine Flüssigkeit-transportierende Systeme anwenden lassen.