NDLI: Fast Scheduling in Distributed Transactional Memory

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

Beyond P vs. NP: Quadratic-Time Hardness for Big Data Problems

Randomized Composable Coresets for Matching and Vertex Cover

Asymptotically Optimal Approximation Algorithms for Coflow Scheduling

Bounding Laconic Proof Systems by Solving CSPs in Parallel

Some Sequential Algorithms are Almost Always Parallel

Distributed Partial Clustering

Is Our Model for Contention Resolution Wrong?: Confronting the Cost of Collisions

Concurrent Data Structures for Near-Memory Computing

Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs

Online Tree Caching

Almost Optimal Streaming Algorithms for Coverage Problems

Online Flexible Job Scheduling for Minimum Span

Matrix Multiplication, a Little Faster

Distributed Detection of Cycles

Optimal Reissue Policies for Reducing Tail Latency

Lower Bounds in the Asymmetric External Memory Model

Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing

Provably Efficient Scheduling of Cache-oblivious Wavefront Algorithms

Bicriteria Distributed Submodular Maximization in a Few Rounds

Minimizing Total Weighted Flow Time with Calibrations

A Communication-Avoiding Parallel Algorithm for the Symmetric Eigenvalue Problem

Distributed Graph Clustering by Load Balancing

Impact of Knowledge on Election Time in Anonymous Networks

Hand-Over-Hand Transactions with Precise Memory Reclamation

Improved Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs

Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers: Extended Abstract

On Energy Conservation in Data Centers

Tight Bounds for Clairvoyant Dynamic Bin Packing

Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource

Fast Scheduling in Distributed Transactional Memory

Swarm-based Incast Congestion Control in Datacenters Serving Web Applications

Optimal Local Buffer Management for Information Gathering with Adversarial Traffic

The Mobile Server Problem

Brief Announcement: Meeting the Challenges of Parallelizing Sequential Programs

Brief Announcement: Scheduling Parallelizable Jobs Online to Maximize Throughput

Brief Announcement: Graph Matching in Massive Datasets

Brief Announcement: Approximation Algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale

Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation

Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack

Brief Announcement: Hazard Eras - Non-Blocking Memory Reclamation

Brief Announcement: A New Improved Bound for Coflow Scheduling

Brief Announcement: Using Multi-Level Parallelism and 2-3 Cuckoo Filters for Set Intersection Queries and Sparse Boolean Matrix Multiplication

Brief Announcement: Towards Fault-Tolerant Bin Packing for Online Cloud Resource Allocation

Brief Announcement: STAR (Space-Time Adaptive and Reductive) Algorithms for Dynamic Programming Recurrences with more than O(1) Dependency

Brief Announcement: Complete Visibility for Oblivious Robots in Linear Time

Brief Announcement: Extending Transactional Memory with Atomic Deferral

Brief Announcement: Hardware Transactional Storage Class Memory

Fast Scheduling in Distributed Transactional Memory

Content Provider	ACM Digital Library
Author	Sharma, Gokarna Popovic, Miroslav Herlihy, Maurice Busch, Costas
Abstract	We investigate scheduling algorithms for distributed transactional memory systems where transactions residing at nodes of a communication graph operate on shared, mobile objects. A transaction requests the objects it needs, executes once those objects have been assembled, and then possibly forwards those objects to other waiting transactions. Minimizing execution time in this model is known to be NP-hard for arbitrary communication graphs, and also hard to approximate within any factor smaller than the size of the graph. Nevertheless, networks on chips, multi-core systems, and clusters are not arbitrary. Here, we explore efficient execution schedules in specialized graphs likely to arise in practice: Clique, Line, Grid, Cluster, Hypercube, Butterfly, and Star. In most cases, when individual transactions request k objects, we obtain solutions close to a factor O(k) from optimal, yielding near-optimal solutions for constant k. These execution times approximate the TSP tour lengths of the objects in the graph. We show that for general networks, even for two objects (k=2), it is impossible to obtain execution time close to the objects' optimal TSP tour lengths, which is why it is useful to consider more realistic network models. To our knowledge, this is the first attempt to obtain provably fast schedules for distributed transactional memory.
Starting Page	173
Ending Page	182
Page Count	10
File Format	PDF
ISBN	9781450345934
DOI	10.1145/3087556.3087565
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-07-24
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Approximation Distributed systems Data-flow model Contention Scheduling Execution time Transactional memory
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

Scheduling support for transactional memory contention management

Impossibility Results for Distributed Transactional Memory

Scheduling Transactions in Replicated Distributed Software Transactional Memory

Conflict Avoidance Scheduling Using Grouping List for Transactional Memory

Adaptive transaction scheduling for transactional memory systems

Transactional contention management as a non-clairvoyant scheduling problem

Scheduling Closed-Nested Transactions in Distributed Transactional Memory

Scheduling Support for Transactional Memory Contention Management

Supporting Transactional Memory in Distributed Systems based on the Data-Flow Model

Fast Scheduling in Distributed Transactional Memory

Similar Documents

Scheduling support for transactional memory contention management

Impossibility Results for Distributed Transactional Memory

Scheduling Transactions in Replicated Distributed Software Transactional Memory

Conflict Avoidance Scheduling Using Grouping List for Transactional Memory

Adaptive transaction scheduling for transactional memory systems

Transactional contention management as a non-clairvoyant scheduling problem

Scheduling Closed-Nested Transactions in Distributed Transactional Memory

Scheduling Support for Transactional Memory Contention Management

Supporting Transactional Memory in Distributed Systems based on the Data-Flow Model

Fast Scheduling in Distributed Transactional Memory