NDLI: Speculative thread decomposition through empirical optimization

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

On using connection-oriented vs. connection-less transport for performance and scalability of collective and one-sided operations: trade-offs and impact

Open nesting in software transactional memory

Automatic mapping of nested loops to FPGAS

Self-adaptive applications on the grid

Alert-on-update: a communication aid for shared memory multiprocessors

Reordering constraints for pthread-style locks

Tight analysis of the performance potential of thread speculation using spec CPU 2006

The Z-polyhedral model

X10: concurrent programming for modern architectures

Disens: scalable distributed sensor network simulation

Implicit parallelism with ordered transactions

Featherweight transactions: decoupling threads and atomic blocks

May-happen-in-parallel analysis of X10 programs

Methods of inference and learning for performance modeling of parallel applications

Transactional programming in a multi-core environment

Efficient nonblocking software transactional memory

Barrier matching for programs with textually unaligned barriers

Using fine grain multithreading for energy efficient computing

Conservative vs. optimistic parallelization of stateful network intrusion detection

Adaptive structured parallelism for computational grids

Fault detection in multi-threaded c++ server applications

MCSTL: the multi-core standard template library

Optimized lock assignment and allocation: a method for exploiting concurrency among critical sections

Performance evaluation of the cray XT3 configured with dual core opteron processors

Locality-aware connection management and rank assignment for wide-area MPI

Speculations: providing fault-tolerance and improving performance of parallel applications

Promised messages: recovering from inconsistent global states

Supporting fault-tolerance in streaming grid applications

A study of tracing overhead on a high-performance linux cluster

Speculative thread decomposition through empirical optimization

Content Provider	ACM Digital Library
Author	Vijaykumar, T. N. Johnson, Troy A. Eigenmann, Rudolf
Abstract	Chip multiprocessors (CMPs), or multi-core processors, have become a common way of reducing chip complexity and power consumption while maintaining high performance. Speculative CMPs use hardware to enforce dependence, allowing a parallelizing compiler to generate multithreaded code without needing to prove independence. In these systems, a sequential program is decomposed into threads to be executed in parallel; dependent threads cause performance degradation, but do not affect correctness. Thread decomposition attempts to reduce the run-time overheads of data dependence, thread misprediction, and load imbalance. Because these overheads depend on the runtimes of the threads that are being created by the decomposition, reducing the overheads while creating the threads is a circular problem. Static compile-time decomposition handles this problem by estimating the run times of the candidate threads, but is limited by the estimates' inaccuracy. Dynamic execution-time decomposition in hardware has better run-time information, but is limited by the decomposition hardware's complexity and run-time overhead. We propose a third approach where a compiler instruments a profile run of the application to search through candidate threads and pick the best threads as the profile run executes. The resultant decomposition is compiled into the application so that a production run of the application has no instrumentation and does not incurany decomposition overhead. We avoid static decomposition's estimation accuracy problem by using actual profile-run execution times to pick threads, and we avoid dynamic decomposition's overhead by performing the decomposition at profile time. Because we allow candidate threads to span arbitrary sections of the application's call graph and loop nests, an exhaustive search of the decomposition space is prohibitive, even in profile runs. To address this issue, we make the key observation that the run-time overhead of a thread depends, to the first order, only on threads that overlap with the thread inexecution (e.g., in a four-core CMP, a given thread can overlap with at most three preceding and three following threads). This observation implies that a given thread affects only a few other threads, allowing pruning of the space. Using a CMP simulator, we achieve an average speedup of 3.51 on four cores for five of the SPEC CFP2000 benchmarks, which compares favorably to recent static techniques. We also discuss experiments with CINT2000.
Starting Page	205
Ending Page	214
Page Count	10
File Format	PDF
ISBN	9781595936028
DOI	10.1145/1229428.1229474
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-03-14
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Empirical search Chip multiprocessor Multi-core Thread-level speculation Decomposition
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

Position-aware thread-level speculative parallelization for large-scale chip-multiprocessor

Min-cut program decomposition for thread-level speculation

Module-level speculative execution techniques on chip multiprocessors.

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

Abstract Data Speculation Support for a Chip Multiprocessor

Loop-level speculative parallelism in embedded applications.

Software and Hardware for Exploiting Speculative Parallelism with a Multiprocessor (1997)

Limits on thread-level speculative parallelism in embedded applications.

Abstract data speculation support for a chip multiprocessor.

Speculative thread decomposition through empirical optimization

Similar Documents

Position-aware thread-level speculative parallelization for large-scale chip-multiprocessor

Min-cut program decomposition for thread-level speculation

Module-level speculative execution techniques on chip multiprocessors.

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

Abstract Data Speculation Support for a Chip Multiprocessor

Loop-level speculative parallelism in embedded applications.

Software and Hardware for Exploiting Speculative Parallelism with a Multiprocessor (1997)

Limits on thread-level speculative parallelism in embedded applications.

Abstract data speculation support for a chip multiprocessor.

Speculative thread decomposition through empirical optimization