Vi presenterar tekniker för att parallellisera medlemstester för Deterministic Finite Automata (DFA). Vår metod söker godtyckliga reguljära uttryck genom att matcha flera byte parallellt med spekulation. Vi partitionerar inmatningssträngen i bitar, matchar bitar parallellt och kombinerar de matchande resultaten. Vår parallella matchande algoritm utnyttjar strukturella DFA egenskaper för att minimera spekulativa overhead. Till skillnad från tidigare tillvägagångssätt är vår spekulation felfri, d.v.s. 1) sekventiella semantik upprätthålls, och (2) hastighetsnedskärningar undviks helt och hållet. På arkitekturer med en SIMD-samling för indexerade minnesbelastningar är vår matchande operation fullt vektoriserad. Det föreslagna systemet för lastbalansering använder ett off-line-profileringssteg för att fastställa varje deltagande processors matchningskapacitet. Baserat på matchningskapacitet är DFA-matcher lastbalanserade på inhomogena parallella arkitekturer som molndatamiljöer. Vi utvärderade vårt spekulativa DFA-medlemskapstest för en representativ uppsättning riktmärken från biblioteket Perl-kompatibel Regular Expression (PCRE) och PROSITE proteindatabasen. Utvärderingen gjordes på en 4 CPU (40 kärnor) delad minnesnod av Intel Academic Program Manycore Testing Lab (Intel MTL), på Intel AVX2 SDE simulator för 8-vägs helt vektoriserad SIMD utförande, och på en 20-node (288 kärnor) kluster på Amazon EC2 computing cloud. Erhållna speedups är på ordningen av O 1 +  skap1  och Q på γ, där  skap betecknar antalet processorer eller SIMD-enheter,  och anger antalet DFA-tillstånd, och 0 < γ ≤ 1 representerar en statiskt beräknad DFA egenskap. För alla observerade fall fann vi att 0,02 < γ < 0,47. Faktiska upphastigheter varierar från 2,3× till 38,8× för upp till 512 DFA-tillstånd för PCRE, och mellan 1,3× och 19,9× för upp till 1,288 DFA-tillstånd för PROSITE på en 40-kärnig MTL-nod. Speedups på EC2 computing cloud varierar från 5,0× till 65,8× för PCRE, och från 5,0× till 138,5× för PROSITE. Int J Parallel Prog (2014) 42:456-489 457 Speedups av vår C-baserade DFA matcher över Perl-baserade ScanProsite scan verktyg sträcker sig från 559.3× till 15079,7× på en 40-kärnig MTL nod. Vi visar skalbarheten av vår strategi för inmatningsstorlekar på upp till 10 GB.
Ett suffix-stängt reguljärt språk har den egenskap som x  på L, L,,,, * : xw, L. Det spekulativa parallella DFA-medlemstest som rapporterats av Ko et al. REF är att parallellisera DFA medlemstester för multicore-, SIMD- och cloud computing-miljöer.
A Speculative Parallel DFA Membership Test for Multicore, SIMD and Cloud Computing Environments
{'venue': 'International Journal of Parallel Programming', 'journal': 'International Journal of Parallel Programming', 'mag_field_of_study': ['Computer Science']}