NDLI: Improved approximations for multiprocessor scheduling under uncertainty

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

Utilizing shared data in chip multiprocessors with the Nahalal architecture

What can be approximated locally?: case study: dominating sets in planar graphs

Online multicast with egalitarian cost sharing

Against lock-based semantics for transactional memory

Many random walks are faster than one

Automatic data partitioning in software transactional memories

Operational analysis of processor speed scaling

Fundamental parallel algorithms for private-cache chip multiprocessors

Fast distributed scheduling via primal-dual

Kicking the tires of software transactional memory: why the going gets tough

On obstruction-free transactions

Partial snapshot objects

The adaptive transactional memory test platform: a tool for experimenting with transactional code for rock (poster)

A consistency architecture for hierarchical shared caches

Distributed packing in planar graphs

Trade-offs between the size of advice and broadcasting time in trees

A transactional approach to lock scalability

Improved distributed approximate matching

Checkpoints and continuations instead of nested transactions

A temperature-aware virtual submesh allocation scheme for noc-based manycore chips

Cache-efficient dynamic programming algorithms for multicores

A primal-dual resource augmentation analysis of a constant approximate algorithm for stable coalitions in a cluster

RingSTM: scalable transactions with a single atomic instruction

Practical weak-atomicity semantics for java stm

Communication in wireless networks with directional antennas

Improving software concurrency with hardware-assisted memory snapshot

Combinable memory-block transactions

Polylogarithmic network navigability using compact metrics with small stretch

Cost sharing mechanisms for near-optimal traffic aggregation and network design

RaceTM: detecting data races using transactional memory

Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning

Adaptive transaction scheduling for transactional memory systems

Optimal speedup on a low-degree multi-core parallel architecture (LoPRAM)

Scheduling strategies for optimistic parallel execution of irregular programs

Improved approximations for multiprocessor scheduling under uncertainty

Irrevocable transactions and their applications

Commit phase in timestamp-based stm

Tight competitive ratios for parallel disk prefetching and caching

Distributed voronoi diagram computation in wireless sensor networks

Parallelizing dynamic information flow tracking

On spreading recommendations via social gossip

A first insight into object-aware hardware transactional memory

Finding strongly connected components in parallel using $O(log^{2}n)$ reachability queries

Energy-optimal distributed algorithms for minimum spanning trees

Competitive non-migratory scheduling for flow time and energy

Dreadlocks: efficient deadlock detection

Directed transmission method, a fully asynchronous approach to solve sparse linear systems in parallel

Safe open-nested transactions through ownership

Data replication in p2p environments

Ased: availability, security, and debugging support usingtransactional memory

Leveraging non-blocking collective communication in high-performance applications

Graphical congestion games with linear latencies

Fractal communication in software data dependency graphs

Improved approximations for multiprocessor scheduling under uncertainty

Content Provider	ACM Digital Library
Author	Dzunic, Zoran Scott, Jacob H. Fineman, Jeremy T. Karger, David R. Crutchfield, Christopher Y.
Abstract	This paper presents improved approximation algorithms for the problem of multiprocessor scheduling under uncertainty (SUU), in which the execution of each job may fail probabilistically. This problem is motivated by the increasing use of distributed computing to handle large, computationally intensive tasks. In the SUU problem we are given n unit-length jobs and m machines, a directed acyclic graph G of precedence constraints among jobs, and unrelated failure probabilities $q_{ij}$ for each job j when executed on machine i for a single timestep. Our goal is to find a schedule that minimizes the expected makespan. Lin and Rajaraman gave the first approximations for this NP-hard problem for the special cases of independent jobs, precedence constraints forming disjoint chains, and precedence constraints forming trees. In this paper, we present asymptotically better approximation algorithms. In particular, we improve upon the previously best O(log n)-approximation, giving an O(log log(min {m,n}))-approximation in the case of independent jobs. We also give an O(log(n+m) log log(min{m,n}))-approximation algorithm for precedence constraints that form disjoint chains (improving on the previously best O(log(n)log(m) $^{log(n+m)}$ over log log(n+m)-approximation by a (log n/log log $n)^{2}$ factor when n = m $^{Θ(1)}).$ Our algorithm for precedence constraints forming chains can also be used as a component for precedence constraints forming trees, yielding a similar improvement over the previously best algorithms for trees. Our techniques include reducing SUU to a problem in stochastic scheduling, where machines must process a set of jobs with randomly distributed lengths. We show that our algorithms for (SUU) apply to a standard problem in this setting, giving the first approximation algorithms for preemptive stochastic scheduling on unrelated machines.
Starting Page	246
Ending Page	255
Page Count	10
File Format	PDF
ISBN	9781595939739
DOI	10.1145/1378533.1378579
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-06-01
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Multiprocessor scheduling Scheduling under uncertainty Approximation algorithms Stochastic scheduling
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

Approximation algorithms for multiprocessor scheduling under uncertainty

Improved approximations for multiprocessor scheduling under uncertainty.

Improved Approximations for Multiprocessor Scheduling Under Uncertainty

Improved approximations for multiprocessor scheduling under uncertainty (2008).

Stochastic online scheduling

Approximation Algorithms for Multiprocessor Scheduling under Uncertainty

Approximation Algorithms on Multiprocessor Task Scheduling

Multiprocessor Scheduling with Rejection

Approximation Algorithms for Multiprocessor Scheduling under Uncertainty

Improved approximations for multiprocessor scheduling under uncertainty

Similar Documents

Approximation algorithms for multiprocessor scheduling under uncertainty

Improved approximations for multiprocessor scheduling under uncertainty.

Improved Approximations for Multiprocessor Scheduling Under Uncertainty

Improved approximations for multiprocessor scheduling under uncertainty (2008).

Stochastic online scheduling

Approximation Algorithms for Multiprocessor Scheduling under Uncertainty

Approximation Algorithms on Multiprocessor Task Scheduling

Multiprocessor Scheduling with Rejection

Approximation Algorithms for Multiprocessor Scheduling under Uncertainty

Improved approximations for multiprocessor scheduling under uncertainty