NDLI: Versatile and scalable parallel histogram construction

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

Versatile and scalable parallel histogram construction

Content Provider	ACM Digital Library
Author	Park, Jongsoo Jung, Wookeun Lee, Jaejin
Abstract	Histograms are used in various fields to quickly profile the distribution of a large amount of data. However, it is challenging to efficiently utilize abundant parallel resources in modern processors for histogram construction. To make matters worse, the most efficient implementation varies depending on input parameters (e.g., input distribution, number of bins, and data type) or architecture parameters (e.g., cache capacity and SIMD width). This paper presents versatile histogram methods that achieve competitive performance across a wide range of input types and target architectures. Our open source implementations are highly optimized for various cases and are scalable for more threads and wider SIMD units. We also show that histogram construction can be significantly accelerated by Intel Xeon Phi coprocessors for common input data sets because of their compute power from many cores and instructions for efficient vectorization, such as gather-scatter. For histograms with 256 fixed-width bins, a dual-socket 8-core Intel® Xeon® E5-2690 achieves 13 billion bin updates per second (GUPS), while a 60-core Intel® Xeon Phi™ 5110P coprocessor achieves 18 GUPS for a skewed input. For histograms with 256 variable-width bins, the Xeon processor achieves 4.7 GUPS, while the Xeon Phi coprocessor achieves 9.7 GUPS for a skewed input. For text histogram, or word count, the Xeon processor achieves 342.4 million words per seconds (MWPS). This is 4.12X, 3.46X faster than Phoenix and TBB. The Xeon phi processor achieves 401.4 MWPS, which is 1.17X faster than the Xeon processor. Since histogram construction captures essential characteristics of more general reduction-heavy operations, our approach can be extended to other settings.
Starting Page	127
Ending Page	138
Page Count	12
File Format	PDF
ISBN	9781450328098
DOI	10.1145/2628071.2628108
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-08-24
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Histogram Algorithms Multi-core Simd Performance
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