Scheduling parallelizable imprecise computations on multiprocessors
Albert Yu, Kuo-Yi Lin · International Parallel Processing Symposium · 2002
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.>
Cited by 8 works. doi:10.1109/ipps.1991.153832
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- A new polynomial-time algorithm for linear programming
- Combinatorial Optimization: Algorithms and Complexity.
- Polynomial algorithms in linear programming
- Data Structures and Network Algorithms
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Fast Approximation Algorithms for Knapsack Problems
- The Characteristics of Parallel Algorithms.
- Imprecise results: Utilizing partial computations in real-time systems
- Complexity of Scheduling Parallel Task Systems