Tune-up for the Dead-Zone algorithm

Jorma Tarhio; Bruce Watson

Tune-up for the Dead-Zone algorithm

Jorma Tarhio
, Bruce Watson

Tietotekniikan laitos

Stellenbosch University

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

Abstrakti

We present a number of performance tuning techniques as applied to the Dead-Zone algorithm for exact single (keyword) pattern matching in strings in sequential processing. The tuning techniques presented here are focused on the algorithm skeleton as well as how the shifters are used, and include: removal of some redundant computation, and shifting using 2-grams, among others. Benchmarking results are given for the C implementation in a modern processor without penalties for misaligned memory access.

Alkuperäiskieli	Englanti
Otsikko	Proceedings of the Prague Stringology Conference 2020
Toimittajat	Jan Holub, Jan Zdarek
Julkaisupaikka	Prague
Kustantaja	Czech Technical University in Prague
Sivut	160-167
Sivumäärä	8
ISBN (painettu)	978-80-01-06749-9
Tila	Julkaistu - 2020
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisussa
Tapahtuma	Prague Stringology Conference - Prague, Tshekki Kesto: 31 elok. 2020 → 2 syysk. 2020

Conference

Conference	Prague Stringology Conference
Lyhennettä	PSC
Maa/Alue	Tshekki
Kaupunki	Prague
Ajanjakso	31/08/2020 → 02/09/2020

Pääsy asiakirjaan

http://www.stringology.org/event/2020/p14.html

Siteeraa tätä

@inproceedings{74e2b50c93114715b500dbf8c1003dea,

title = "Tune-up for the Dead-Zone algorithm",

abstract = "We present a number of performance tuning techniques as applied to the Dead-Zone algorithm for exact single (keyword) pattern matching in strings in sequential processing. The tuning techniques presented here are focused on the algorithm skeleton as well as how the shifters are used, and include: removal of some redundant computation, and shifting using 2-grams, among others. Benchmarking results are given for the C implementation in a modern processor without penalties for misaligned memory access.",

author = "Jorma Tarhio and Bruce Watson",

year = "2020",

language = "English",

isbn = "978-80-01-06749-9",

pages = "160--167",

editor = "Jan Holub and Jan Zdarek",

booktitle = "Proceedings of the Prague Stringology Conference 2020",

publisher = "Czech Technical University in Prague",

address = "Czech Republic",

note = "Prague Stringology Conference, PSC ; Conference date: 31-08-2020 Through 02-09-2020",

}

TY - GEN

T1 - Tune-up for the Dead-Zone algorithm

AU - Tarhio, Jorma

AU - Watson, Bruce

PY - 2020

Y1 - 2020

N2 - We present a number of performance tuning techniques as applied to the Dead-Zone algorithm for exact single (keyword) pattern matching in strings in sequential processing. The tuning techniques presented here are focused on the algorithm skeleton as well as how the shifters are used, and include: removal of some redundant computation, and shifting using 2-grams, among others. Benchmarking results are given for the C implementation in a modern processor without penalties for misaligned memory access.

AB - We present a number of performance tuning techniques as applied to the Dead-Zone algorithm for exact single (keyword) pattern matching in strings in sequential processing. The tuning techniques presented here are focused on the algorithm skeleton as well as how the shifters are used, and include: removal of some redundant computation, and shifting using 2-grams, among others. Benchmarking results are given for the C implementation in a modern processor without penalties for misaligned memory access.

M3 - Conference article in proceedings

SN - 978-80-01-06749-9

SP - 160

EP - 167

BT - Proceedings of the Prague Stringology Conference 2020

A2 - Holub, Jan

A2 - Zdarek, Jan

PB - Czech Technical University in Prague

CY - Prague

T2 - Prague Stringology Conference

Y2 - 31 August 2020 through 2 September 2020

ER -

Tune-up for the Dead-Zone algorithm

Abstrakti

Conference

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä