Abstrakt. Detta dokument presenterar en ny BDD-baserad distribuerad algoritm för åtkomlighetsanalys som är helt asynkron. Tidigare BDD-baserade distribuerade system är synkrona: de består av interleaved rundor av beräkning och kommunikation, där den snabbaste maskinen (eller en som är lätt laddad) måste vänta på den långsammaste i slutet av varje runda. Vi ger två viktiga bidrag. För det första utför algoritmen bildberäkning och meddelandeöverföring samtidigt, med icke-blockerande protokoll i flera lager av kommunikationen och beräkningsinfrastrukturen. Som ett resultat, oavsett skala och typ av den underliggande plattformen, kan den maximala mängden resurser användas effektivt. För det andra innehåller algoritmen en adaptiv mekanism som delar arbetsbelastningen, med beaktande av tillgången till fri beräkningskraft. På detta sätt kan beräkningen gå snabbare eftersom, när fler processorer är tillgängliga för att gå med i beräkningen, mindre arbete tilldelas till var och en av dem. Mindre belastning innebär ytterligare viktiga fördelar, såsom bättre lokalisering av referens, mindre overhead i komprimeringsverksamhet (såsom omordning), och snabbare och bättre arbetsbörda uppdelning. Vi implementerade det nya tillvägagångssättet genom att utöka en symbolisk modellkontroll från Intel. Det resulterande systemets effektivitet visas på ett antal stora industriella konstruktioner och offentliga referenskretsar, som alla är kända för att vara svåra att nå fram till. Våra resultat visar att asynkron algoritm möjliggör effektivt utnyttjande av högre nivåer av parallellism. Höga hastigheter rapporteras, upp till en storleksordning, för datortillgänglighet för modeller med högre minneskrav än vad som tidigare varit möjligt.
För att övervinna synkroniseringen nackdel, Grumberg et al. REF införde en asynkron version av den vertikala skärmetoden som inte bara utför bildberäkning och meddelande som passerar samtidigt, utan också innehåller en adaptiv mekanism som tar hänsyn till tillgängligheten av fri beräkningskraft för att dela arbetsbelastningen.
Achieving speedups in distributed symbolic reachability analysis through asynchronous computation
{'venue': 'In CHARME', 'journal': None, 'mag_field_of_study': ['Computer Science']}