Optimal Scheduling for Real-Time Parallel Tasks(Algorithm Theory)
スポンサーリンク
概要
- 論文の詳細を見る
We propose an optimal algorithm for the real-time scheduling of parallel tasks on multiprocessors, where the tasks have the properties of flexible preemption, linear speedup, bounded parallelism, and arbitrary deadline. The proposed algorithm is optimal in the sense that it always finds out a feasible schedule if one exists. Furthermore, the algorithm delivers the best schedule consuming the fewest processors among feasible schedules. In this letter, we prove the optimality of the proposed algorithm. Also, we show that the time complexity of the algorithm is O(M^2・N^2) in the worst case, where M and N are the number of tasks and the number of processors, respectively.
- 社団法人電子情報通信学会の論文
- 2006-06-01
著者
-
Lee Wan
Hallym Univ. Kor
-
Lee Wan
Department Of Computer Engineering Hallym University
-
LEE Heejo
Department of Computer Science and Engineering, Korea University
-
Lee Heejo
Korea Univ. Seoul Kor
-
Lee Heejo
Department Of Computer Science And Engineering Korea University
-
Lee Wan
Department Of Biochemistry College Of Medicine Dongguk University
関連論文
- Optimal Scheduling for Real-Time Parallel Tasks(Algorithm Theory)
- AdaFF : Adaptive Failure-Handling Framework for Composite Web Services
- Dynamic Two-Tier Cell Structure for Bandwidth Reservation of Handoffs in Cellular Networks
- Processor-Minimum Scheduling of Real-Time Parallel Tasks
- Maximizing Total QoS-Provisioning of Image Streams with Limited Energy Budget
- Enhancing Resiliency of Networks : Evolving Strategy vs. Multihoming
- Energy-Aware Error Correction for QoS-Provisioning Real-Time Communications in Wireless Networks
- Error Bound of Collision Probability Estimation in Non-saturated IEEE802.11 WLANs(Terrestrial Radio Communications)
- On the Cross-Layer Impact of TCP ACK Thinning on IEEE802.11 Wireless MAC Dynamics(Wireless Communication Technologies)
- Boosting VoIP Capacity of Wireless Mesh Networks through Lazy Frame Aggregation(Terrestrial Radio Communications)
- Detecting Unknown Worms Using Randomness Check(Internet)
- Expression of E- and N-cadherin and clinicopathology in hepatocellular carcinoma
- Involvement of Vesicular H^+-ATPase in Insulin-Stimulated Glucose Transport in 3T3-F442A Adipocytes
- Evaluation of Two Load-Balancing Primary-Backup Process Allocation Schemes
- Changes in renal function after nephron-sparing surgery in patients with a normal contralateral kidney
- Resiliency of Network Topologies under Path-Based Attacks(Internet)
- Fabrication of W_2NiB_2-Ni Borides Cermets
- Characteristics and prognosis of chromophobe non-metastatic renal cell carcinoma : A multicenter study
- Pressure Effect on the Formation of Ferroelectric SrBi_2Ta_2O_9 Thin Films
- SLA-Based Scheduling of Bag-of-Tasks Applications on Power-Aware Cluster Systems
- Performance Evaluation of Concurrent System Using Formal Model : Simulation Speedup(Concurrent System Technology)
- Epigenetic methylation and expression of caspase 8 and survivin in hepatocellular carcinoma
- Performance Evaluation of Concurrent System Using Formal Model : Simulation Speedup
- Umbilical laparoendoscopic single site surgery versus inguinal varicocelectomy for bilateral varicocele : A comparative study
- Stochastic Power Minimization of Real-Time Tasks with Probabilistic Computations under Discrete Clock Frequencies
- Minimum-Energy Semi-Static Scheduling of a Periodic Real-Time Task on DVFS-Enabled Multi-Core Processors
- An Optimal Resource Sharing in Hierarchical Virtual Organizations in the Grid