Baumsuchalgorithmen eignen sich aufgrund der feingranularen Parallelität sehr gut zur Parallelisierung - selbst auf massiv parallelen Systemen mit mehr als eintausend Prozessoren. Die Schwierigkeit dabei liegt jedoch in der Lastverteilung. Der Baum kann beliebig in Teilbäume zerlegt werden, welche unabhängig voneinander durchsucht werden können. Bei der Aufteilung des Suchbaumes unter den Prozessoren ist die Größe der sich dabei ergebenen Teilbäume jedoch nicht a priori bekannt. Aus diesem Grund ist eine effiziente dynamische Lastverteilungsstrategie notwendig, um die Prozessoren während der Suche möglichst gleichmäßig auszulasten.
Ein weiteres Problem stellt die initiale Lastverteilung in einem massiv parallelen System dar. Bei Verfahren, die auf einem Stack-Splitting Ansatz basieren [10][2], beginnt ein Prozessor mit der Suche und baut dabei einen Stack mit unbearbeiteten Knoten auf. Falls dieser Stack eine bestimmte Tiefe erreicht hat, wird er geteilt, d.h. dieser Prozessor gibt einen oder mehrere Knoten an jeden seiner Nachbarn ab, die nach dem gleichen Verfahren wiederum Arbeit für ihre Nachbarprozessoren erzeugen. Dieses Verfahren setzt sich während der gesamten Suche fort. Ein Prozessor, der seinen erhaltenen Stack abgearbeitet hat, stellt wieder eine Arbeitsanfrage an einen seiner Nachbarn (Task-Attraction Scheme).
In einem massiv parallelen System führt dieser Ansatz dazu, daßdie Prozessoren mit einem größeren Abstand zum Startprozessor durch das rekursive Aufsplitten des Stacks nur sehr kleine Lastpakete erhalten und somit viele Anfragen stellen müssen [7].
Ein anderer Parallelisierungsansatz ist die parallele Fenstersuche [6]. Hier beginnen alle Prozessoren ihre Suche an der Wurzel des Suchbaumes, jedoch mit unterschiedlichen Kostenschranken. Dieses Verfahren ist für die Parallelisierung auf einem massiv parallelen System nicht geeignet, außerdem kann die Optimalität einer gefundenen Lösung nicht garantiert werden.