NDLI: Offline Scheduling of Multi-threaded Request Streams on a Caching Server

Content Provider	IEEE Xplore Digital Library
Author	Rehn-Sonigo, V. Trystram, D. Wagner, F. Haifeng Xu Guochuan Zhang
Copyright Year	2011
Abstract	In this work, we are interested in the problem of satisfying multiple concurrent requests submitted to a computing server. Informally, there are users each sending a sequence of requests to the server. The requests consist of tasks linked by precedence constraints. Tasks may occur several times in the same sequence as well as in a request sequence of another user. The computing server has to execute tasks with variable processing times. The server owns a cache of limited size where intermediate results of the processing may be stored. If an intermediate result for a task is stored into the cache, no processing cost has to be paid and the result can directly be fetched from the cache. The goal of this work is to determine a schedule of the tasks such that an optimization function is minimized (the only objective studied up to now is the make span). This problem is a variant of caching which considers only one sequence of requests. We then extend the study to the minimization of the mean completion time of the request sequences. Two models are considered. In the first model, caching is forced whereas in the second model caching is optional and one can choose whether an intermediate result is stored in the cache or not. All combinations turn out to be NP-hard for fixed cache sizes and we provide a formulation as dynamic program as well as bounds for in approximation. We propose polynomial time approximation algorithms for some variants and analyze their approximation ratios. Finally, we also devise some heuristics and present experimental results. Tasks may occur several times in the same sequence as well as in a request sequence of another user. The computing server has to execute tasks with variable processing times. The server owns a cache of limited size where intermediate results of the processing may be stored. If an intermediate result for a task is stored into the cache, no processing cost has to be paid and the result can directly be fetched from the cache. The goal of this work is to determine a schedule of the tasks such that an optimization function is minimized (the only objective studied up to now is the make span). This problem is a variant of caching which considers only one sequence of requests. We then extend the study to the minimization of the mean completion time of the request sequences. Two models are considered. In the first model, caching is forced whereas in the second model caching is optional and one can choose whether an intermediate result is stored in the cache or not. All combinations turn out to be NP-hard for fixed cache sizes and we provide a formulation as dynamic program as well as bounds for in approximation. We propose polynomial time approximation algorithms for some variants and analyze their approximation ratios. Finally, we also devise some heuristics and present experimental results.
Starting Page	1167
Ending Page	1176
File Size	888016
Page Count	10
File Format	PDF
ISBN	9781612843728
ISSN	15302075
DOI	10.1109/IPDPS.2011.111
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-05-16
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Optimized production technology Servers Approximation algorithms Approximation methods Dynamic programming Schedules Heuristic algorithms
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

On the Worst Case of Scheduling with Task Replication on Computational Grids

Fuzzy dynamic programming for optimized scheduling of repetitive construction projects

A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems

Effective algorithms for scheduling problems under non-availability constraints (Invited paper)

Scheduling jobs with dwindling resource requirements in clouds

Buffer minimization in pipelined SDF scheduling on multi-core platforms

A dynamic priority scheduling algorithm on service request scheduling in cloud computing

A unified approach for the scheduling problem with rejection

Optimal top-K queries processing: Sampling and dynamic scheduling approach

Offline Scheduling of Multi-threaded Request Streams on a Caching Server

Similar Documents

On the Worst Case of Scheduling with Task Replication on Computational Grids

Fuzzy dynamic programming for optimized scheduling of repetitive construction projects

A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems

Effective algorithms for scheduling problems under non-availability constraints (Invited paper)

Scheduling jobs with dwindling resource requirements in clouds

Buffer minimization in pipelined SDF scheduling on multi-core platforms

A dynamic priority scheduling algorithm on service request scheduling in cloud computing

A unified approach for the scheduling problem with rejection

Optimal top-K queries processing: Sampling and dynamic scheduling approach

Offline Scheduling of Multi-threaded Request Streams on a Caching Server