News Archives

IC-Scheduling: A New Scheduling Paradigm for Task-Hungry Platforms

February 20, 2014

  • Date: Thursday, February 20, 2014
  • Time: 11:00 am - 12:00 pm 
  • Place: Mechanical Engineering 218

Arnold Rosenberg
Northeastern University

Abstract:
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 prioritze 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 aimsto respond to the new challenges of IC. Faced with the impossibility of scheduling to accomodate critical paths in a computation, we seek to schedule in a way that always renders as many tasks as possibleeligible 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.

I begin this talk with the concepts underlying the theory and the algorithms that emerge from them. I then describe several familiar computations and computational paradigms that the nascent theory can schedule optimally. I finally describe simulation experiments whose results suggest that the theory's schedules have a measurable benign effect on "real" Internet-based computing.

Bio:
Arnold L. Rosenberg is a Research Professor of Computer Science at Northeastern University and a Distinguished University Professor Emeritus of Computer Science at the University of Massachusetts (Amherst). After retiring from UMass, Rosenberg held a research professorship at Colorado State University until 2012. Before he joined UMass in 1986, Rosenberg was a Professor of Computer Science at Duke University from 1981 to 1986 and a Research Staff Member at the IBM Watson Research Center from 1965 to 1981. Over the years, Rosenberg held visiting positions at Yale University and the University of Toronto, in addition to part-time positions at the predecessor of Polytechnic University and at New York University. He was a Lady Davis Visiting Professor at the Technion (Israel Institute of Technology) and a Fulbright Senior Research Scholar at the University of Paris-South.

Rosenberg's research program is continuing unabated post-retirement---perhaps even at a higher level of intensity, with no required teaching and committee work. His main research focus is on developing algorithmic models and techniques to deal with the many new modalities of "collaborative computing," the use of many, possibly geographically dispersed, computers to cooperatively solve individual computing problems.

Rosenberg is the (co)author of more than 170 technical papers onmultiple topics in theoretical computer science and discretemathematics (including one in linguistics); these appear in venuesdevoted to computer science, engineering, mathematics, and/or linguistics. In collaboration with Prof. Lenwood S. Heath (Va. Tech), Rosenberg coauthored the book, "Graph Separators, with Applications." He has recently completed a textbook on Computation Theory, "The Pillars of Computation Theory: State, Encoding, Nondeterminism."

  • NO VIDEO FILE AVAILABLE