NDLI: Profitable scheduling on multiple speed-scalable processors

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

Fast greedy algorithms in mapreduce and streaming

Storage and search in dynamic peer-to-peer networks

Brief announcement: truly parallel burrows-wheeler compression and decompression

IRIS: a robust information system against insider dos-attacks

Coalescing-branching random walks on graphs

Work-efficient matrix inversion in polylogarithmic time

Profitable scheduling on multiple speed-scalable processors

Cloud scheduling with setup cost

Reduced hardware transactions: a new approach to hybrid transactional memory

Broadcasting in logarithmic time for ad hoc network nodes on a line using mimo

Brief announcement: locality in wireless scheduling

SybilCast: broadcast on the open airwaves (extended abstract)

Parallel rotor walks on finite graphs and applications in discrete load balancing

Communication optimal parallel multiplication of sparse random matrices

Nonclairvoyant sleep management and flow-time scheduling on multiple processors

Efficient online scheduling for deadline-sensitive jobs: extended abstract

Recursive design of hardware priority queues

Expected sum and maximum of displacement of random sensors for coverage of a domain: extended abstract

Brief announcement: universally truthful secondary spectrum auctions

On-the-fly pipeline parallelism

Parallel graph decompositions using random shifts

Communication efficient gaussian elimination with partial pivoting using a shape morphing data layout

Reallocation problems in scheduling

Locality-aware task management for unstructured parallelism: a quantitative limit study

Drop the anchor: lightweight memory management for non-blocking data structures

On dynamics in selfish network creation

Brief announcement: online batch scheduling for flow objectives

Reducing contention through priority updates

A constant factor approximation algorithm for the storage allocation problem: extended abstract

Optimal patrolling of fragmented boundaries

Efficient scheduling to minimize calibrations

Balls-into-bins with nearly optimal load distribution

Scalable statistics counters

Brief announcement: set it and forget it - approximating the set once strip cover problem

HEX: scaling honeycombs is easier than scaling clock trees

Non-monetary fair scheduling: a cooperative game theory approach

Brief announcement: between all and nothing - versatile aborts in hardware transactional memory

Brief announcement: towards a fully-articulated pessimistic distributed transactional memory

Brief announcement: a game-theoretic model motivated by the darpa network challenge

Profitable scheduling on multiple speed-scalable processors

Content Provider	ACM Digital Library
Author	Kling, Peter Pietrzyk, Peter
Abstract	We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors. Moreover, we provide a tight analysis of the algorithm's competitiveness. Our results generalize and improve upon work by Chan et al. [10], which considers a single speed-scalable processor. Using significantly different techniques, we can not only extend their model to multiprocessors but also prove an enhanced and tight competitive ratio for our algorithm. In our scheduling problem, jobs arrive over time and are preemptable. They have different workloads, values, and deadlines. The scheduler may decide not to finish a job but instead to suffer a loss equaling the job's value. However, to process a job's workload until its deadline the scheduler must invest a certain amount of energy. The cost of a schedule is the sum of lost values and invested energy. In order to finish a job the scheduler has to determine which processors to use and set their speeds accordingly. A processor's energy consumption is power $P_{α}(s)$ integrated over time, where $P_{α}(s)$ = $s^{α}$ is the power consumption when running at speed s. Since we consider the online variant of the problem, the scheduler has no knowledge about future jobs. This problem was introduced by Chan et al. [10] for the case of a single processor. They presented an online algorithm which is $α^{α}$ +2eα-competitive. We provide an online algorithm for the case of multiple processors with an improved competitive ratio of $α^{α}.$
Starting Page	251
Ending Page	260
Page Count	10
File Format	PDF
ISBN	9781450315722
DOI	10.1145/2486159.2486183
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-07-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Online algorithms Energy Primal-dual Scheduling Convex programming
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

Profitable Scheduling on Multiple Speed-Scalable Processors

Profitable scheduling on multiple speed-scalable processors (2013)

Profitable Scheduling on Multiple Speed-Scalable Processors

Speed scaling on parallel processors

Discrete Min-Energy Scheduling on Restricted Parallel Processors

Primal--Dual Path-Following Algorithms for Semidefinite Programming

A General Primal-Dual Envelope Method for Convex Programming Problems

Fast distributed scheduling via primal-dual

A new primal-dual path-following method for convex quadratic programming

Profitable scheduling on multiple speed-scalable processors

Similar Documents

Profitable Scheduling on Multiple Speed-Scalable Processors

Profitable scheduling on multiple speed-scalable processors (2013)

Profitable Scheduling on Multiple Speed-Scalable Processors

Speed scaling on parallel processors

Discrete Min-Energy Scheduling on Restricted Parallel Processors

Primal--Dual Path-Following Algorithms for Semidefinite Programming

A General Primal-Dual Envelope Method for Convex Programming Problems

Fast distributed scheduling via primal-dual

A new primal-dual path-following method for convex quadratic programming

Profitable scheduling on multiple speed-scalable processors