ParallelMergeXplain: A Speculative Parallel Variant of MergeXplain for Multi-Conflict Detection in Constraint-Based Systems

In de digitale wereld zijn complexe systemen gebouwd op regels. Of het nu gaat om een softwareconfiguratie die moet werken met specifieke hardware, een spreadsheet die een budget berekent, of een productconfigurator die een klant helpt bij het bouwen van een aangepaste auto, deze systemen vertrouwen op een reeks beperkingen. Een beperking is simpelweg een regel die zegt wat wel en wat niet is toegestaan. Wanneer een gebruiker probeert een systeem op te zetten dat deze regels overtreedt, moet de computer uitzoeken welke regels precies met elkaar in strijd zijn. Dit wordt het vinden van een "conflict" genoemd. Stel je een puzzel voor waarbij je honderd stukjes hebt, maar slechts een paar daarvan zijn daadwerkelijk het probleem. De taak van de computer is om die specifieke stukjes te isoleren zodat de gebruiker ze kan herstellen. Dit proces vormt de basis van modelgebaseerde diagnose, een vakgebied dat ingenieurs en softwareontwikkelaars helpt om defecte systemen automatisch te repareren.

Decennialang hebben onderzoekers algoritmen ontwikkeld om deze conflicten efficiënt te vinden. Een beroemde methode, bekend als QuickXplain, werkt als een detective die een lijst met verdachten inkrimpt. Het splitst een grote groep regels in twee helften, controleert of de eerste helft het probleem is, en zo niet, controleert het de tweede helft. Het herhaalt dit proces, waarbij de lijst steeds weer in tweeën wordt gesplitst, totdat het de kleinste groep regels vindt die de fout veroorzaakt. Dit is snel, maar het vindt slechts één conflict tegelijk. In veel realistische situaties kan een systeem meerdere verschillende problemen tegelijkertijd hebben. Om het hele systeem te herstellen, moet een computer al deze conflicten vinden, en niet slechts één. Een latere methode genaamd MergeXplain werd ontworpen om precies dat te doen: het vindt meerdere conflicten in één enkele run. Echter, naarmate computers sneller zijn geworden en meer processorcores hebben gekregen, zijn de oude manieren om deze algoritmen uit te voeren tegen een muur aangelopen. Ze waren ontworend voor een enkele rijstrook, terwijl moderne computers over veel rijstroken beschikken.

Een team onderzoekers uit Ecuador en Chili heeft nu een nieuwe versie van deze multi-conflictzoeker gebouwd, die ze ParallelMergeXplain noemen. Hun doel was om de bestaande methode te nemen en deze simultaan op meerdere processorcores te laten draaien, zonder de antwoorden die het geeft te veranderen. Ze wilden zien of ze het proces van het vinden van meerdere conflicten konden versnellen door de volledige kracht van moderne computerchips te gebruiken. De onderzoekers werden geconfronteerd met een specifieke uitdaging: het algoritme heeft twee duidelijke onderdelen. Het eerste deel is een boomstructuur waarbij de computer het probleem in twee takken splitst. Het tweede deel is een lus waarin de computer de resultaten van die takken controleert om eventuele resterende fouten op te schonen. Eerdere pogingen om dit te versnellen richtten zich alleen op het eerste deel, door de twee takken tegelijkertijd te laten draaien. De onderzoekers realiseerden zich dat het tweede deel, de schoonmaaklus, nog steeds traag bleef draaien, stap voor stap, ook al kon ook dat versneld worden.

Om dit op te lossen, creëerde het team een algoritme dat beide delen van het probleem tegelijk aanvalt. Ze lieten de twee hoofdvertakkingen van de zoektocht op verschillende processorcores draaien, net als voorheen. Maar ze voegden ook een nieuwe laag snelheid toe aan de schoonmaaklus. Ze gebruikten een techniek genaamd "speculatieve parallellisatie". Dit is een methode waarbij de computer raadt wat hij als volgende nodig zal hebben en alvast begint met die taken voordat hij absoluut zeker weet dat hij ze nodig heeft. Het is als een chef-kok die, terwijl hij groenten snijdt voor het huidige gerecht, alvast de ingrediënten voor het volgende gerecht voorbereidt omdat hij weet dat deze eraan komt. Als de gok juist is, wordt er tijd bespaard. Als de gok fout is, wordt het werk simpelweg weggegooid en gaat de computer verder. In dit nieuwe systeem gebruikt de computer vrije processorcores om de resultaten van toekomstige controles vooraf te berekenen terwijl het hoofdalgoritme nog draait.

De onderzoekers hebben een volledige, open-source versie van dit nieuwe systeem gebouwd in de programmeertaal Python. Omdat ze in hun testomgeving geen toegang hadden tot standaard commerciële softwaretools, hebben ze hun eigen consistentiecontrole vanaf nul geschreven om te verifiëren dat hun logica klopte. Ze hebben hun nieuwe algoritme getest tegen de oude methode met twee soorten tests. Eerst gebruikten ze synthetische problemen die ze zelf hadden gegenereerd, waarbij ze het exacte antwoord vooraf kenden. Ten tweede gebruikten ze een echte, real-world benchmarkformule uit een publieke bibliotheek van logische problemen, die zij niet zelf hadden gemaakt of aangepast. Deze real-world test was cruciaal omdat het bewees dat het systeem werkte op gegevens die het nog nooit eerder had gezien. Ze voerden deze tests uit op een standaardcomputer met twee processorcores, waarbij ze elke test vele malen herhaalden om er zeker van te zijn dat de resultaten consistent waren en niet slechts een gelukkig toevalstreffer.

De resultaten lieten zien dat de nieuwe methode qua nauwkeurigheid exact even goed werkt als de oude. In elke enkele test vond het nieuwe algoritme exact dezelfde set conflicten als het origineel, wat bewees dat de versnellingstechnieken geen fouten introduceerden. Wat betreft de snelheid was de nieuwe methode sneller, maar de mate van winst hing af van de complexiteit van het probleem. Op de real-world benchmark was het nieuwe systeem ongeveer 1,5 keer sneller dan de oude. Op de synthetische tests was de snelheidswinst bescheidener, met een gemiddelde van ongeveer 1,2 keer sneller. De onderzoekers ontdekten dat de grootste winsten werden behaald wanneer ze beide strategieën combineerden: het parallel draaien van de vertakkingen en het gebruik van de speculatieve blik vooruit in de schoonmaaklus. Ze ontdekten echter ook een limiet. Als ze probeerden te veel taken op de twee beschikbare cores te dwingen, besteedde de computer meer tijd aan het beheren van de taken dan aan het daadwerkelijk oplossen van het probleem, en verdween de snelheidswinst. Dit bevestigde dat het simpelweg toevoegen van meer werkers een klus niet altijd sneller maakt; de werkers moeten worden afgestemd op de omvang van de taak.

Dit werk demonstreert dat het mogelijk is om een complex, sequentieel algoritme aan te passen voor moderne multi-core computers zonder de betrouwbaarheid te verliezen. De onderzoekers hebben bewezen dat ze, door verschillende soorten parallellisme zorgvuldig te combineren, het proces van het vinden van meerdere systeemconflicten aanzienlijk sneller kunnen maken. Hun bevindingen suggereren dat voor systemen met veel beperkingen, het combineren van vertakking-niveau parallellisme en speculatieve blik vooruit de meest effectieve aanpak is. De studie benadrukte ook dat de voordelen van deze technieken variëren afhankelijk van de specifieke aard van het probleem dat wordt opgelost. Hoewel de snelheidswinst niet enorm was op een kleine machine met twee cores, bieden de principes die zij hebben vastgesteld een duidelijk pad voor het versnellen van deze diagnose-systemen op grotere, krachtigere hardware in de toekomst. De code en de data van hun studie zijn publiekelijk beschikbaar, waardoor andere onderzoekers voort kunnen bouwen op deze basis en deze methoden op nog grotere en complexere real-world systemen kunnen testen.