Vi presenterar en ny dynamisk partiell orderreduktionsmetod för statslös modellkontroll av samtidiga program. En vanlig metod för att utforska programbeteenden bygger på att räkna upp spåren av programmet, utan att lagra de besökta staterna (även kallad statslös utforskning). Eftersom antalet distinkta spår växer exponentiellt, dynamiska partiell ordning reduktion (DPOR) tekniker har framgångsrikt använts för att dela upp utrymmet för spår i ekvivalens klasser (Mazurkiewicz partitionering), med målet att utforska endast några representativa spår från varje klass. Vi inför en ny likvärdighet på spår under sekventiell konsistens semantik, som vi kallar observationslikvärdighet. Två spår är observationsmässigt likvärdiga om varje läshändelse observerar samma skrivhändelse i båda spåren. Medan den traditionella Mazurkiewicz likvärdighet är kontroll-centrerad, vår nya definition är datacentrisk. Vi visar att vår observation ekvivalens är grövre än Mazurkiewicz ekvivalens, och i många fall även exponentiellt grövre. Vi utformar en DPOR-undersökning av spårrymden, kallad datacentrisk DPOR, baserad på observationslikvärdigheten. (1) För acykliska arkitekturer är vår algoritm garanterad att utforska exakt ett representativt spår från varje observationsklass, samtidigt som vi tillbringar polynomtid per klass. Därför är vår algoritm optimal wrt observation ekvivalens, och i flera fall utforskar exponentiellt färre spår än någon räknande metod baserad på Mazurkiewicz ekvivalens. (2) För cykliska arkitekturer betraktar vi en likvärdighet mellan spår som är finare än observationslikvärdigheten; men grövre än Mazurkiewicz ekvivalens, och i vissa fall är exponentiellt grövre. Vår datacentrerade DPOR-algoritm förblir optimal under denna spåre ekvivalens. Slutligen gör vi en grundläggande experimentell jämförelse mellan den befintliga Mazurkiewicz-baserade DPOR och vår datacentrerade DPOR på en uppsättning akademiska riktmärken. Våra resultat visar en betydande minskning av både körtid och antalet utforskade ekvivalensklasser.
Slutligen presenterar datacentric DPOR (DCDPOR) REF en ny DPOR-algoritm baserad på en annan definition av beroende enligt vilken derivatans ekvivalensklasser baseras på de olika variablerna.
Data-centric dynamic partial order reduction
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}