Programvarans och hårdvarusystemens storlek och komplexitet har ökat betydligt under de senaste åren. Som ett resultat av detta är det svårare att garantera deras rätta beteende. En av de mest framgångsrika metoderna för automatisk verifiering av finita system är modellkontroll. De flesta av de nuvarande modellkontrollsystemen använder binära beslutsdiagram (BDD) för att representera den testade modellen och i verifieringsprocessen av dess egenskaper. Generellt, BDDs tillåter en kanonisk kompakt representation av en booleska funktion (med tanke på en ordning av dess variabler). Ju mer kompakt BDD är, desto bättre prestanda får man från kontrollanten. Att hitta en optimal ordning för en BDD är dock ett NP-komplett problem. Därför har flera heuristiska metoder baserade på expertkunskap utvecklats för variabla beställningar. Vi föreslår ett alternativt tillvägagångssätt där variabel orderalgoritmen får "beställerfarenhet" från utbildningsmodeller och använder den inlärda kunskapen för att hitta bra order. Vår metodik är baserad på offline inlärning av par företräde klassificerare från utbildningsmodeller, det vill säga lära vilken variabel par permutation är mer sannolikt att leda till en bra ordning. För varje träningsmodell utvärderas ett antal träningssekvenser. Varje träningsmodell variabel par permutation är sedan taggad baserat på dess prestanda på de utvärderade beställningarna. De taggade permutationerna skickas sedan genom en funktionsextraktor och ges som exempel till en klassificeringsskapelsealgoritm. Med tanke på en modell för vilken en order begärs konsulterar beställningsalgoritmen varje prioritetsklassificering och konstruerar en parprioritetstabell som används för att skapa ordern. Vår algoritm integrerades med SMV, som är ett av de mest använda verifieringssystemen. Preliminär empirisk utvärdering av vår metod, med hjälp av verkliga referensmodeller, visar prestanda som är bättre än slumpmässig beställning och är konkurrenskraftig med befintliga algoritmer som använder expertkunskap. Vi tror att i underdomäner av modeller (alu, caches, etc.) Vårt system kommer att visa sig ännu mer värdefullt. Detta beror på att det har förmågan att lära sig sub-domän kunskap, något som ingen annan beställning algoritm gör.
REF använder beslutsträd för att lära sig variabel parpermutation vilket är mer sannolikt att leda till en bra ordning.
Learning to Order BDD Variables in Verification
{'venue': 'Journal Of Artificial Intelligence Research, Volume 18, pages 83-116, 2003', 'journal': None, 'mag_field_of_study': ['Computer Science']}