NDLI: Bitwise data parallelism in regular expression matching

Please wait, while we are loading the content...

Internet of mobile things: challenges and opportunities

Virtues and limitations of commodity hardware transactional memory

ATCache: reducing DRAM cache latency via a small SRAM tag cache

What is the cost of weak determinism?

Versatile and scalable parallel histogram construction

Adaptive heterogeneous scheduling for integrated GPUs

Invyswell: a hybrid transactional memory for haswell's restricted transactional memory

PATS: pattern aware scheduling and power gating for GPGPUs

Realm: an event-based low-level runtime for distributed memory architectures

Domain-specific models for innovation in analytics

OpenTuner: an extensible framework for program autotuning

Memory scheduling towards high-throughput cooperative heterogeneous computing

Trading cache hit rate for memory performance

PEMOGEN: automatic adaptive performance modeling during program runtime

$D^{2}MA:$ accelerating coarse-grained data transfer for GPUs

Automatic execution of single-GPU computations across multiple GPUs

An Event-Based Language for Dynamic Binary Translation Frame Works

Cooperative cache scrubbing

SpongeDirectory: flexible sparse directories utilizing multi-level memristors

ILP and TLP in shared memory applications: a limit study

Bitwise data parallelism in regular expression matching

Warp-aware trace scheduling for GPUs

Consolidated conflict detection for hardware transactional memory

Heterogeneous microarchitectures trump voltage scaling for low-power cores

kMAF: automatic kernel-level management of thread and data affinity

Velociraptor: an embedded compiler toolkit for numerical programs targeting CPUs and GPUs

Bounded memory scheduling of dynamic task graphs

Compiler support for selective page migration in NUMA architectures

ArrayTool: a lightweight profiler to guide array regrouping

VAST: the illusion of a large memory space for GPUs

LCA: a memory link and cache-aware co-scheduling approach for CMPs

Improving Performance of Streaming Applications with Filtering and Control Messages

KLA: a new algorithmic paradigm for parallel graph computations

EFetch: optimizing instruction fetch for event-driven webapplications

CAWS: criticality-aware warp scheduling for GPGPU workloads

DeSTM: harnessing determinism in STMs for application development

RCS: runtime resource and core scaling for power-constrained multi-core processors

Shuffling: a framework for lock contention aware thread scheduling for multicore multiprocessor systems

COLORIS: a dynamic cache partitioning system using page coloring

Design for scalability in enterprise SSDs

Automatic optimization of thread-coarsening for graphics processors

A run-time power manager exploiting software parallelism

Stratified Sampling for Even Workload Partitioning

Tiling and optimizing time-iterated computations on periodic domains

XStream: cross-core spatial streaming based MLC prefetchers for parallel applications in CMPs

Graph-based performance accounting for chip multiprocessor memory systems

Design of a Hybrid MPI-CUDA Benchmark Suite for CPU-GPU Clusters

SQRL: hardware accelerator for collecting software data structures

Data Remapping for an Energy Efficient Burst Chop in DRAM Memory Systems

Optimizing stencil code via locality of computation

Data-reuse Optimizations for pipelined Tiling with Parametric Tile Sizes

ADHA: automatic data layout framework for heterogeneous architectures

From Petascale to the Pocket: Adaptively Scaling Parallel Programs for Mobile SoCs

Active learning accelerated automatic heuristic construction for parallel program mapping

Coarrays in GNU Fortran

Preemptive thread block scheduling with online structural runtime prediction for concurrent GPGPU kernels

Locality-Aware Memory Association for Multi-Target Worksharing in OpenMP

Using STT-RAM to enable energy-efficient near-threshold chip multiprocessors

Processing Big Data Graphs on Memory-Restricted Systems

Protection and utilization in shared cache through rationing

Automatic parallelism through macro dataflow in high-level array languages

A runtime support mechanism for fast mode switching of a self-morphing core for power efficiency

Rollback-free value prediction with approximate loads

Measuring flexibility in single-ISA heterogeneous processors

SM-centric transformation: circumventing hardware restrictions for flexible GPU scheduling

Bitwise data parallelism in regular expression matching

Content Provider	ACM Digital Library
Author	Hull, Benjamin R. Shriraman, Arrvindh Lin, Dan Herdy, Kenneth S. Shermer, Thomas C. Cameron, Robert D. Lin, Meng
Abstract	A new parallel algorithm for regular expression matching is developed and applied to the classical grep (global regular expression print) problem. Building on the bitwise data parallelism previously applied to the manual implementation of token scanning in the Parabix XML parser, the new algorithm represents a general solution to the problem of regular expression matching using parallel bit streams. On widely-deployed commodity hardware using 128-bit SSE2 SIMD technology, our algorithm implementations can substantially outperform traditional grep implementations based on NFAs, DFAs or backtracking. 5X or better performance advantage against the best of available competitors is not atypical. The algorithms are also designed to scale with the availability of additional parallel resources such as the wider SIMD facilities (256-bit) of Intel AVX2 or future 512-bit extensions. Our AVX2 implementation showed dramatic reduction in instruction count and significant improvement in speed. Our GPU implementations show further acceleration.
Starting Page	139
Ending Page	150
Page Count	12
File Format	PDF
ISBN	9781450328098
DOI	10.1145/2628071.2628079
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-08-24
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Parallel bit streams Regular expression matching
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in