Hybride XOR–CNF Boolean satisfiability-problemen native versnellen met in‑memory computing

Waarom sneller problemen oplossen ertoe doet

Veel taken die ons dagelijks leven vormen — van het beveiligen van online communicatie tot het ontwerpen van snellere elektronica — komen neer op een ja‑of‑nee‑vraag voor een computer: bestaat er een combinatie van schakelaars die deze grote logische regel waar maakt? Dat is het Booleaanse satisfiability‑ of SAT‑probleem. SAT is berucht moeilijk en naarmate deze taken in omvang en belang toenemen, worden tijd en energie voor het oplossen ervan een belangrijke bottleneck. Dit artikel onderzoekt een nieuwe manier om SAT‑oplossen te versnellen door zowel de wiskunde als de hardware te herontwerpen zodat ze samen werken binnen een speciaal type geheugenchip.

Verwarrende regels omzetten in eenvoudigere bouwstenen

Traditionele SAT‑oplossers beschrijven problemen meestal met één stijl van logische regels, opgebouwd uit "OF"‑voorwaarden. Maar veel echte industriële problemen — zoals het decoderen van draadloze signalen, het testen van chips op fouten of het aanvallen van bepaalde cryptografische schema’s — mengen van nature "OF" met "exclusive OR" (XOR), een soort pariteitscontrole die omslaat als één invoer verandert. Huidige hulpmiddelen dwingen deze XOR‑regels vaak om te rekenen naar uitsluitend OF, wat de probleemgrootte opblaast en alles vertraagt. De auteurs houden in plaats daarvan beide types regels aan en creëren een hybride beschrijving die dichter bij de manier ligt waarop problemen in de praktijk ontstaan.

Meer bereiken met minder onderdelen

De onderzoekers vergelijken deze hybride representatie zorgvuldig met de traditionele over verschillende benchmark‑families afkomstig uit cryptografie en een klassiek testprobleem dat minimale afwijkingspariteit heet. Door automatisch verborgen XOR‑structuur te reconstrueren en eerst slimme vereenvoudigingen toe te passen, tonen ze aan dat de gemengde representatie het aantal variabelen tot meerdere malen kan verkleinen en het aantal regels ruwweg met een factor vier tot vijf kan verminderen. Met andere woorden: dezelfde logische vraag kan vaak met veel minder bewegende delen worden gesteld wanneer XOR en OF naast elkaar bestaan. Kleinere problemen zijn niet alleen makkelijker voor software, maar ook voor gespecialiseerde hardware die strikte limieten heeft aan hoeveel regels het tegelijk kan opslaan.

Het geheugen de rekentaken laten doen

Om van deze compactere beschrijving te profiteren, ontwerpt het team een speciale "in‑memory computing"‑versneller. In plaats van data heen en weer te vervoeren tussen processor en geheugen, voert dit apparaat veel van de berekeningen uit waar de data staan, binnen rasterarrays van kleine elektronische elementen genaamd memristors. Ze passen een bekende lokale‑zoekstrategie, WalkSAT, aan tot een nieuwe variant WalkSAT‑XNF die native omgaat met de gecombineerde XOR–OF‑regels. Iedere stap van het algoritme — controleren welke regels gebroken zijn, inschatten hoe belangrijk elke schakelaar is, een beetje ruis toevoegen om dode eindes te ontlopen, en de beste kandidaat omslaan — wordt rechtstreeks in analoge schakelingen op de crossbararrays uitgevoerd, met eenvoudige ondersteunende circuits die kiezen welke variabele als volgende wordt omgeslagen.

Aangetoond in het lab en in simulaties

De auteurs bouwen eerst een klein prototype met memristor‑chips om te laten zien dat de analoge hardware clausules betrouwbaar kan evalueren en de zoekprocedure kan sturen, zelfs in aanwezigheid van fabricagevariaties en elektrische ruis. Experimenten op een bescheiden testgeval tonen dat het gedrag van de hardware nauw overeenkomt met ideale simulaties. Vervolgens modelleren ze een geavanceerder 28‑nanometerontwerp en benchmarken dit op families van cryptografische en pariteitsproblemen. Omdat de hybride beschrijving meer informatie in minder clausules propt, heeft de versneller veel minder on‑chip geheugen nodig en verbruikt hij per stap aanzienlijk minder energie dan een versie die beperkt is tot alleen OF‑regels. Over het geheel genomen bereikt de hybride in‑memory‑oplosser ongeveer een tienvoudige snelheidstoename en ongeveer duizendmaal betere energie‑efficiëntie vergeleken met toonaangevende software‑SAT‑oplossers op conventionele CPU’s.

Wat dit betekent voor toekomstige computers

In eenvoudige bewoordingen laat dit werk zien dat we bepaalde berucht moeilijke ja‑of‑nee‑problemen veel sneller en met veel minder vermogen kunnen oplossen door de manier waarop we de logische regels schrijven af te stemmen op hoe een nieuw soort geheugen‑gebaseerde hardware rekent. Door native zowel XOR‑ als OF‑regels binnen de chip te ondersteunen, kan de voorgestelde versneller realistische cryptografische, communicatie‑ en schakeldesign‑taken aan met kleinere, koelere en snellere hardware. Nu computersystemen steeds meer worden beperkt door energie en snelheid, kunnen zulke probleem‑specifieke in‑memory‑benaderingen helpen om kritieke digitale infrastructuur veilig en efficiënt te houden.

Bronvermelding: Im, H., Böhm, F., Pedretti, G. et al. Accelerating hybrid XOR–CNF Boolean satisfiability problems natively with in-memory computing. Nat Commun 17, 2922 (2026). https://doi.org/10.1038/s41467-026-69465-2

Trefwoorden: Booleaanse satisfiability, in‑memory computing, memristor crossbar, hardwareversnellers, cryptografie