NDLI: Stochastic prediction of execution time for dynamic bulk synchronous computations

Content Provider	IEEE Xplore Digital Library
Author	Xu, C.-Z. Wang, L.Y. Fong, N.-T.
Copyright Year	2001
Description	Author affiliation: Dept. of Electr. & Comput. Eng., Wayne State Univ., Detroit, MI, USA (Xu, C.-Z.)
Abstract	We consider the problem of execution time prediction for non-deterministic bulk synchronous computations on multiprocessors. We formulate the evolution of the execution time of a processor as two random workload change models: additive and multiplicative. These two models reflect parallel commutations in which the workload change of a processor is independent of its workload and proportional to its workload, respectively. We take advantage of their salient features and show that approaches based a central limiting theorem in statistics are viable to approximate the execution time after a certain transient time interval. By an elegant coordination of some results from order statistics and convergence rates in the central limiting theorem, we derive explicit bounds on the execution time under some mild assumptions on distributions. The accuracy of the prediction is analyzed rigorously and verified by simulations.
Sponsorship	IEEE Comput. Soc. Tech. Committee on Parallel Process.
File Size	156759
File Format	PDF
ISBN	0769509908
ISSN	15302075
DOI	10.1109/IPDPS.2001.924982
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2000-04-23
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Stochastic processes Statistical distributions Computational modeling Yield estimation Random variables Phase estimation Upper bound Convergence Accuracy Analytical models
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

Stochastic bounds on execution times of parallel computations

Bayesian Analysis For Simulation Input And Output

Statistical Analysis of Output Processes

Statistical analysis of simulation output

Execution Time Estimation for Workflow Scheduling

Optimal remapping in dynamic bulk synchronous computations via a stochastic control approach

An Analytical Bound for Probabilistic Deadlines

Bandits with budgets

Modeling marked point processes using bivariate mixture transition distribution models

Stochastic prediction of execution time for dynamic bulk synchronous computations

Similar Documents

Stochastic bounds on execution times of parallel computations

Bayesian Analysis For Simulation Input And Output

Statistical Analysis of Output Processes

Statistical analysis of simulation output

Execution Time Estimation for Workflow Scheduling

Optimal remapping in dynamic bulk synchronous computations via a stochastic control approach

An Analytical Bound for Probabilistic Deadlines

Bandits with budgets

Modeling marked point processes using bivariate mixture transition distribution models

Stochastic prediction of execution time for dynamic bulk synchronous computations