A Performance Measure for the Scheduling of Typed Task Systems with Communication Costs
スポンサーリンク
概要
- 論文の詳細を見る
To provide a constant measure of the performance of scheduling heuristics, the development of a sharp lower bound on the execution time for varous task system models is indispensable in the theory of scheduling. This paper presents a lower bound on the time needed to execute task systems that include various types of task and have communication costs. The main result describes a methodology for buiding a parallel execution abstraction called a monotypic task graph [set], which shows naturally inherent parallelism among tasks of identical type for a given typed task system that has communication costs. By applying a formulation to it, we can derive a lower bound on the completion time of the task set. The new lower bound is sharper than the known values.
- 一般社団法人情報処理学会の論文
- 1994-08-15
著者
-
Ishii Naohiro
Department Of Intelligence And Computer Science Nagoya Institute Of Technology
-
Li Dingchao
Department Of Electrical Engineering And Computer Science Nagoya Institute Of Technology
-
Sowa Masahiro
The University Of Electro-communications
-
Ishii Naohiro
Department Of Electrical Engineering And Computer Science Nagoya Institute Of Technology
関連論文
- The Completeness of Order-Sorted Term Rewriting Systems Is Preserved by Currying
- An Energy-Efficient Initialization Protocol for Wireless Sensor Networks with No Collision Detection
- Termination of Order-Sorted Rewriting with Non-minimal Signatures
- Accuracy of the Minimum Time Estimate for Programs on Heterogeneous Machines
- A Lookahead Heuristic for Heterogeneous Multiprocessor Scheduling with Communication Costs (Special Issue on Parallel and Distributed Supercomputing)
- An Improved Increase over the Minimum Execution Time of a Parallel Program
- An Efficient Method for Computing All Reducts
- A Hybrid Method of Feature Subset Selection
- Improving Performance of the k-Nearest Neighbor Classifier by Combining Feature Selection with Feature Weighting
- Speeding up String Searching Algorithms for Nonuniform Texts
- On Relationships between Decomposable Programs and Rule Commutative Programs
- Efficient Evaluation of One-directional Cycle-recursive Formulas
- A Performance Measure for the Scheduling of Typed Task Systems with Communication Costs
- Decomposable Programs Revised
- Dynamic Fast Issue(DFI) Mechanism for Dynamic Scheduled Processors (Special Section on VLSI Design and CAD Algorithms)
- Determining Feature Weight of Pattern Classification by Using Rough Genetic Algorithm and Fuzzy Similarity Measure
- Fast On-line String Searching
- Reliability of a Mobile Communication System with Network Congestion
- Optimizing Linear Recursive Formulas by Detaching Isolated Variables
- An FPGA-Based Information Detection Hardware System Employing Multi-Match Content Addressable Memory