Name
Abstract | ||
|---|---|---|
In a real-time application that supports imprecise computation, each task is logically composed of a hard task and a soft task. The hard task must be completed before its deadline. The soft task is an optional task which may not be executed to completion, if insufficient computational resources are available. In the presented model, each task may be parallelized and executed on multiple processors with a multiprocessing overhead which is assumed to be a linear function of the degree of parallelism. It is shown that the problem of time allocation in such a real-time application can be formulated and solved as a linear programming problem. An algorithm is given for constructing a multiprocessor schedule from the linear programming solution. This algorithm guarantees the multiprocessing overhead generated in the multiprocessor schedule not to exceed a linear upper bound. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1109/IPPS.1991.153832 | Anaheim, CA |
Keywords | Field | DocType |
parallel algorithms,scheduling,linear program,multiprocessor scheduling,upper bound,time allocation,linear programming | Parallelizable manifold,Parallel algorithm,Upper and lower bounds,Degree of parallelism,Computer science,Scheduling (computing),Parallel computing,Multiprocessing,Linear programming,Linear function,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-8186-9167-0 | 4 | 0.53 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Albert Chuang-shi Yu | 1 | 177 | 19.38 |
| Kwei-Jay Lin | 2 | 3209 | 376.05 |