Name
Abstract | ||
|---|---|---|
A "pebble game驴 is developed to model the process of scheduling computation-dags for Internet-based computing (IC, for short). Strategies are derived for scheduling three common, significant families of such dags for IC: reduction-meshes, which represent (the intertask dependencies of) computations that can be performed by "up-sweeps驴 of meshes; reduction-trees, which represent "accumulative驴 computations that can be performed by "up-sweeps驴 of trees; and FFT (Fast Fourier Transform) dags, which represent a large variety of convolutional computations. Two criteria are used to assess the quality of a schedule: its memory requirements and its rate of producing tasks that are eligible for allocation to remote clients. These criteria are important because of, respectively, the typically enormous sizes of IC computations and the typical temporal unpredictability of remote clients in IC. In particular, a high production rate of eligible tasks decreases a computation's vulnerability to the gridlock that can occur when a computation stalls pending the return of intermediate results by remote clients. Under idealized assumptions, the schedules derived are optimal in the rate of producing eligible tasks and are either exactly or approximately optimal in memory requirements. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/TC.2005.65 | Computers, IEEE Transactions |
Keywords | Field | DocType |
Internet,fast Fourier transforms,grid computing,mesh generation,scheduling,tree data structures,Internet-based computing,Web computing,convolutional computation,fast fourier transform,global computing,grid computing,memory requirement,mesh-structured computation,reduction computation,tree-structured computation,Index Terms- Internet-based computing,Web computing,convolutional computations,global computing,grid computing,mesh-structured computations,reduction computations,scheduling,tree-structured computations. | Grid computing,Computer science,Scheduling (computing),Parallel computing,Tree (data structure),Fast Fourier transform,Schedule,Mesh generation,Distributed computing,Computation,The Internet | Journal |
Volume | Issue | ISSN |
54 | 4 | 0018-9340 |
Citations | PageRank | References |
28 | 1.30 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arnold L. Rosenberg | 1 | 2107 | 640.21 |
| Matthew Yurkewych | 2 | 28 | 1.30 |