NDLI: Combining SIMD and Many/Multi-core Parallelism for Finite State Machines with Enumerative Speculation

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

It's Time for a New Old Language

EffiSha: A Software Framework for Enabling Effficient Preemptive Scheduling of GPU

Checking Concurrent Data Structures Under the C/C++11 Memory Model

Thread Data Sharing in Cache: Theory and Measurement

Simple, Accurate, Analytical Time Modeling and Optimal Tile Size Selection for GPGPU Stencils

Pagoda: Fine-Grained GPU Resource Virtualization for Narrow Tasks

SC-Haskell: Sequential Consistency in Languages That Minimize Mutable Shared Heap

Using Butterfly-Patterned Partial Sums to Draw from Discrete Distributions

Self-Checkpoint: An In-Memory Checkpoint Method Using Less Space and Its Practice on Fault-Tolerant HPL

POSTER: Reuse, don't Recycle: Transforming Algorithms that Throw Away Descriptors

Layout Lock: A Scalable Locking Paradigm for Concurrent Data Layout Modifications

An Efficient Abortable-locking Protocol for Multi-level NUMA Systems

Exploiting Vector and Multicore Parallelism for Recursive, Data- and Task-Parallel Programs

Combining SIMD and Many/Multi-core Parallelism for Finite State Machines with Enumerative Speculation

Groute: An Asynchronous Multi-GPU Programming Model for Irregular Computations

Synchronized-by-Default Concurrency for Shared-Memory Systems

KiWi: A Key-Value Map for Scalable Real-Time Analytics

Silent Data Corruption Resilient Two-sided Matrix Factorizations

POSTER: An Architecture and Programming Model for Accelerating Parallel Commutative Computations via Privatization

Understanding the GPU Microarchitecture to Achieve Bare-Metal Performance Tuning

Contention in Structured Concurrency: Provably Efficient Dynamic Non-Zero Indicators for Nested Parallelism

Isoefficiency in Practice: Configuring and Understanding the Performance of Task-based Applications

S-Caffe: Co-designing MPI Runtimes and Caffe for Scalable Deep Learning on Modern GPU Clusters

Tapir: Embedding Fork-Join Parallelism into LLVM's Intermediate Representation

Function Call Re-Vectorization

Grammar-aware Parallelization for Scalable XPath Querying

POSTER: HythTM: Extending the Applicability of Intel TSX Hardware Transactional Support

Noise Injection Techniques to Expose Subtle and Unintended Message Races

Processor-Oblivious Record and Replay

Model-based Iterative CT Image Reconstruction on GPUs

A Multicore Path to Connectomics-on-Demand

Optimizing the Four-Index Integral Transform Using Data Movement Lower Bounds Analysis

Eunomia: Scaling Concurrent Search Trees under Contention Using HTM

POSTER: Provably Efficient Scheduling of Cache-Oblivious Wavefront Algorithms

POSTER: State Teleportation via Hardware Transactional Memory

POSTER: IOGP: An Incremental Online Graph Partitioning for Large-Scale Distributed Graph Databases

POSTER: Distributed Control: The Benefits of Eliminating Global Synchronization via Effective Scheduling

POSTER: MAPA: An Automatic Memory Access Pattern Analyzer for GPU Applications

POSTER: Cache-Oblivious MPI All-to-All Communications on Many-Core Architectures

POSTER: Automated Load Balancer Selection Based on Application Characteristics

POSTER: A GPU-Friendly Skiplist Algorithm

POSTER: Poor Man's URCU

POSTER: A Wait-Free Queue with Wait-Free Memory Reclamation

POSTER: STAR (Space-Time Adaptive and Reductive) Algorithms for Real-World Space-Time Optimality

POSTER: Recovering Performance for Vector-based Machine Learning on Managed Runtime

POSTER: On the Problem of Consistency Exceptions in the Context of Strong Memory Models

POSTER: An Infrastructure for HPC Knowledge Sharing and Reuse

Combining SIMD and Many/Multi-core Parallelism for Finite State Machines with Enumerative Speculation

Content Provider	ACM Digital Library
Author	Jiang, Peng Agrawal, Gagan
Abstract	Finite State Machine (FSM) is the key kernel behind many popular applications, including regular expression matching, text tokenization, and Huffman decoding. Parallelizing FSMs is extremely difficult because of the strong dependencies and unpredictable memory accesses. Previous efforts have largely focused on multi-core parallelization, and used different approaches, including {\em speculative} and {\em enumerative} execution, both of which have been effective but also have limitations. With increasing width and improving flexibility in SIMD instruction sets, this paper focuses on combining SIMD and multi/many-core parallelism for FSMs. We have developed a novel strategy, called {\em enumerative speculation}. Instead of speculating on a single state as in speculative execution or enumerating all possible states as in enumerative execution, our strategy speculates transitions from several possible states, reducing the prediction overheads of speculation approach and the large amount of redundant work in the enumerative approach. A simple lookback approach produces a set of guessed states to achieve high speculation success rates in our enumerative speculation. We evaluate our method with four popular FSM applications: Huffman decoding, regular expression matching, HTML tokenization, and Div7. We obtain up to 2.5x speedup using SIMD on one core and up to 95x combining SIMD with 60 cores of an Intel Xeon Phi. On a single core, we outperform the best single-state speculative execution version by an average of 1.6x, and in combining SIMD and many-core parallelism, outperform enumerative execution by an average of 2x.
Starting Page	179
Ending Page	191
Page Count	13
File Format	PDF
ISBN	9781450344937
DOI	10.1145/3018743.3018760
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-01-26
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Enumerative speculation Simd Finite state machines
Content Type	Text
Resource Type	Article

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

Chemical Kinetics on Multi-core SIMD Architectures (2009)

Complementing user-level coarse-grain parallelism with implicit speculative parallelism

Multi- and many-core data mining with adaptive sparse grids

A TLP approach for BGP based on local speculation

When polyhedral transformations meet simd code generation.

Exploitation of nested thread-level speculative parallelism on multi-core systems

MicroSpec: Speculation-Centric Fine-Grained Parallelization for FSM Computations

The design and evaluation of hierarchical multilevel parallelisms for h.264 encoder on multi-core architecture.

AA-sort: A new parallel sorting algorithm for multi-core SIMD processors (2007)

Combining SIMD and Many/Multi-core Parallelism for Finite State Machines with Enumerative Speculation

Similar Documents

Chemical Kinetics on Multi-core SIMD Architectures (2009)

Complementing user-level coarse-grain parallelism with implicit speculative parallelism

Multi- and many-core data mining with adaptive sparse grids

A TLP approach for BGP based on local speculation

When polyhedral transformations meet simd code generation.

Exploitation of nested thread-level speculative parallelism on multi-core systems

MicroSpec: Speculation-Centric Fine-Grained Parallelization for FSM Computations

The design and evaluation of hierarchical multilevel parallelisms for h.264 encoder on multi-core architecture.

AA-sort: A new parallel sorting algorithm for multi-core SIMD processors (2007)

Combining SIMD and Many/Multi-core Parallelism for Finite State Machines with Enumerative Speculation