NDLI: Brief Announcement: A QPTAS for Non-preemptive Speed-scaling

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

Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation)

On Computational Thinking, Inferential Thinking and Data Science

Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers

RUBIC: Online Parallelism Tuning for Co-located Transactional Memory Applications

Cache-Adaptive Analysis

General Profit Scheduling and the Power of Migration on Heterogeneous Machines

A Multicore Path to Connectomics-on-Demand

Robust and Probabilistic Failure-Aware Placement

Just Join for Parallel Ordered Sets

Universal Shape Formation for Programmable Matter

Lock-free Transactions without Rollbacks for Linked Data Structures

The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets

The Cost of Unknown Diameter in Dynamic Networks

Parallel Shortest Paths Using Radius Stepping

Parallel Algorithms for Summing Floating-Point Numbers

A Practical Solution to the Cactus Stack Problem

Extending TM Primitives using Low Level Semantics

Parallel Algorithms for Asymmetric Read-Write Costs

The Power of Migration in Online Machine Minimization

Brief Announcement: Flexible Resource Allocation for Clouds and All-Optical Networks

Parallel Equivalence Class Sorting: Algorithms, Lower Bounds, and Distribution-Based Analysis

Asymptotically Optimal Gathering on a Grid

Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free

Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph?

Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration

Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity

Latency-Hiding Work Stealing: Scheduling Interacting Parallel Computations with Work Stealing

Investigating the Performance of Hardware Transactions on a Multi-Socket Machine

Brief Announcement: Preserving Happens-before in Persistent Memory

Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines

Clairvoyant Dynamic Bin Packing for Job Scheduling with Minimum Server Usage Time

Parallel Approaches to the String Matching Problem on the GPU

Better Bounds for Coalescing-Branching Random Walks

Fast and Robust Memory Reclamation for Concurrent Data Structures

Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures

Fast Distributed Algorithms for Connectivity and MST in Large Graphs

Parallelism in Randomized Incremental Algorithms

Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications

Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs

Brief Announcement: Transactional Data Structure Libraries

Brief Announcement: Approximating the I/O Complexity of One-Shot Red-Blue Pebbling

Scheduling Parallelizable Jobs Online to Minimize the Maximum Flow Time

Brief Announcement: Improved Approximation Algorithms for Scheduling Co-Flows

Brief Announcement: MIC++: Accelerating Maximal Information Coefficient Calculation with GPUs and FPGAs

Brief Announcement: Benchmarking Concurrent Priority Queues:

Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond

Brief Announcement: A Tight Distributed Algorithm for All Pairs Shortest Paths and Applications

Brief Announcement: Dynamic Determinacy Race Detection for Task Parallelism with Futures

Brief Announcement: A QPTAS for Non-preemptive Speed-scaling

Online Packet Scheduling for CIOQ and Buffered Crossbar Switches

Brief Announcement: Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables

Brief Announcement: Relaxed Byzantine Vector Consensus

Brief Announcement: Energy Optimization of Memory Intensive Parallel Workloads

Brief Announcement: A QPTAS for Non-preemptive Speed-scaling

Content Provider	ACM Digital Library
Author	Shadloo, Maryam Im, Sungjin
Abstract	Modern processors typically allow dynamic speed-scaling offering an effective trade-off between high throughput and energy efficiency. In a classical model, a processor/machine runs at speed s when consuming power $s^{α}$ where α >1 is a constant. Yao et al. [FOCS 1995] studied the problem of completing all jobs before their deadlines on a single machine with the minimum energy in their seminal work and gave a nice polynomial time algorithm. The influential work has been extended to various settings. In particular, the problem has been extensively studied in the presence of multiple machines as multi-core processors have become dominant computing units. However, when jobs must be scheduled non-preemptively, our understanding of the problem remains fairly unsatisfactory. Often, preempting a job is prohibited since it could be very costly. Previously, a $O((w_{max}$ $w_{min})^{α})-approximation$ was known for the non-preemptive setting where $w_{max}$ and $w_{min}$ denote the maximum and minimum job sizes, respectively. Even when there is only one machine, the best known approximation factor had a dependency on α. In this paper, for any fixed α >1 and ε >0, we give the first (1+ε)-approximation for this problem on multiple machines which runs in nO(polylog (n)) time where n is the number of jobs to be scheduled.
Starting Page	207
Ending Page	209
Page Count	3
File Format	PDF
ISBN	9781450342100
DOI	10.1145/2935764.2935824
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-11
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Job deadline Parallel machines Scheduling Energy minimization
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