Snabbt mönstermatchning är ett krav för många problem, speciellt för bioinformatiksekvensanalys som korta läsmappningsprogram. Detta arbete presenterar en variation av FM-indexmetoden, betecknad n-steg FM-index, som tillämpas i exakt matchgenomsökning. Vi föreslår en alternativ tvådimensionell FM-indexstruktur som tillåter bakåtsökt navigering som ger steg av n symboler åt gången. De viktigaste fördelarna med detta arrangemang är minskningen av beräkningsarbetet, men viktigast av allt, minskningen genom n av kedjan av beroende dataåtkomst, och ökningen av tidslokaliseringen av dataåtkomstmönstret. Denna förmån sker på bekostnad av en ökning av den totala mängden uppgifter som krävs för indexet. Vi presenterar en djupgående prestandaanalys av en flerkärnig implementering av algoritmen med hjälp av stora referenser (upp till 1,5G). Vi identifierar minne latens som den viktigaste prestandabegränsaren för enkeltrådig exekvering och minnesbandbredd för flertrådig exekvering. Vårt förslag ger speedups från 1,4× till 2,4×, när det inte finns någon begränsning på DRAM kapacitet. Vi analyserar också kompromissen med att komprimera den föreslagna datastrukturen för att minska kraven på minneskapacitet, nu på bekostnad av ökad genomförandetid. En extra 33% av DRAM utrymme tillåter vårt förslag att förbättra prestanda med 1,2×, medan dubblering DRAM storlek möjliggör en ytterligare 1,5×. Vårt förslag om n-steg algoritm ger ett alternativ för pseudo-random minnesåtkomst algoritmer att omformas till skala i nuvarande och framtida datorsystem.
Den n-steg FM-index metod som presenteras av Chacón et al. REF uppnådde speedups från 1,4× till 2,4× med avseende på deras ursprungliga FM-index sökalgoritm.
n-step FM-Index for Faster Pattern Matching
{'venue': 'ICCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}