A New Scheduling Paradigm for Internet-Based Computing
1:04:25
-
3 years ago
Technological and economic developments have made the Internet a viable platform for a new, “collaborative,” modality of Internet-based computing (IC, for short). Within this modality, the owner of a large, typically compute-intensive, computation enlists remote clients to “collaborate” in performing the computation. When the computation comprises only independent tasks, the temporal unpredictability of IC — communication is over the Internet; computing is by clients who arrive at unpredictable times and who are typically not dedicated to the computation — is at worst an annoying source of slowdown. But, when the computation’s tasks have interdependencies that prioritize their execution, then the temporal unpredictability can confute attempts to benefit from “parallel” execution of tasks and can lead to a form of gridlock wherein no new tasks can be allocated to remote clients pending completion of already allocated tasks.
In recent papers, we have proposed a new scheduling paradigm that aims to respond to the new challenges of IC. Faced with the impossibility (due to temporal unpredictability) of scheduling to accommodate “critical paths” in a computation, we seek to schedule in a way that always renders as many tasks as possible eligible for allocation (to remote clients). This has the dual goal of maximizing the utilization of available clients and minimizing the likelihood of gridlock. We have formalized this scheduling problem and, under idealized assumptions, have developed the rudiments of an algorithmic theory of how to schedule complex computations for IC.
We begin this talk with the concepts underlying the theory and the algorithms that emerge from them. We then describe several familiar computations and omputational paradigms that the nascent theory can schedule optimally. We finally describe simulation experiments whose results suggest that the theory’s schedules have a measurable benign effect on “real” Internet-based computing.
The “IC-scheduling team” is codirected by Greg Malewicz (Google) and includes Gennaro Cordasco (Salerno) regarding theoretical development, and Rob Hall and Arun Venkataramani (UMass) regarding experimental studies.Technological and economic developments have made the Internet a viable platform for a new, “collaborative,” modality of Internet-based ...all »Technological and economic developments have made the Internet a viable platform for a new, “collaborative,” modality of Internet-based computing (IC, for short). Within this modality, the owner of a large, typically compute-intensive, computation enlists remote clients to “collaborate” in performing the computation. When the computation comprises only independent tasks, the temporal unpredictability of IC — communication is over the Internet; computing is by clients who arrive at unpredictable times and who are typically not dedicated to the computation — is at worst an annoying source of slowdown. But, when the computation’s tasks have interdependencies that prioritize their execution, then the temporal unpredictability can confute attempts to benefit from “parallel” execution of tasks and can lead to a form of gridlock wherein no new tasks can be allocated to remote clients pending completion of already allocated tasks.
In recent papers, we have proposed a new scheduling paradigm that aims to respond to the new challenges of IC. Faced with the impossibility (due to temporal unpredictability) of scheduling to accommodate “critical paths” in a computation, we seek to schedule in a way that always renders as many tasks as possible eligible for allocation (to remote clients). This has the dual goal of maximizing the utilization of available clients and minimizing the likelihood of gridlock. We have formalized this scheduling problem and, under idealized assumptions, have developed the rudiments of an algorithmic theory of how to schedule complex computations for IC.
We begin this talk with the concepts underlying the theory and the algorithms that emerge from them. We then describe several familiar computations and omputational paradigms that the nascent theory can schedule optimally. We finally describe simulation experiments whose results suggest that the theory’s schedules have a measurable benign effect on “real” Internet-based computing.
The “IC-scheduling team” is codirected by Greg Malewicz (Google) and includes Gennaro Cordasco (Salerno) regarding theoretical development, and Rob Hall and Arun Venkataramani (UMass) regarding experimental studies.«
Download is starting. Save file to your computer. If the download does not start automatically, right-click this link and choose "Save As". How to get videos onto the iPod or PSP.
