The Fork-Join program consisting of K parallel tasks is a useful model for a large number of computing applications. When the parallel processor has multi-channels, later tasks may finish execution earlier than their ...The Fork-Join program consisting of K parallel tasks is a useful model for a large number of computing applications. When the parallel processor has multi-channels, later tasks may finish execution earlier than their earlier tasks and may join with tasks from other programs. This phenomenon is called exchangeable join (EJ), which introduces correlation to the task’s service time. In this work, we investigate the response time of multiprocessor systems with EJ with a new approach. We analyze two aspects of this kind of systems: exchangeable join (EJ) and the capacity constraint (CC). We prove that the system response time can be effectively reduced by EJ, while the reduced amount is constrained by the capacity of the multiprocessor. An upper bound model is constructed based on this analysis and a quick estimation algorithm is proposed. The approximation formula is verified by extensive simulation results, which show that the relative error of approximation is less than 5%.展开更多
Real-time task scheduling is of primary significance in multiprocessor systems.Meeting deadlines and achieving high system utilization are the two main objectives of task scheduling in such systems.In this paper,we re...Real-time task scheduling is of primary significance in multiprocessor systems.Meeting deadlines and achieving high system utilization are the two main objectives of task scheduling in such systems.In this paper,we represent those two goals as the minimization of the average response time and the average task laxity.To achieve this,we propose a genetic-based algorithm with problem-specific and efficient genetic operators.Adaptive control parameters are also employed in our work to improve the genetic algorithms' efficiency.The simulation results show that our proposed algorithm outperforms its counterpart considerably by up to 36% and 35% in terms of the average response time and the average task laxity,respectively.展开更多
基金Project supported by the National Natural Science Foundation of0 China (Nos. 60274011 and 60574067), and the Program for NewCentury Excellent Talents in University (No. NCET-04-0094), China
文摘The Fork-Join program consisting of K parallel tasks is a useful model for a large number of computing applications. When the parallel processor has multi-channels, later tasks may finish execution earlier than their earlier tasks and may join with tasks from other programs. This phenomenon is called exchangeable join (EJ), which introduces correlation to the task’s service time. In this work, we investigate the response time of multiprocessor systems with EJ with a new approach. We analyze two aspects of this kind of systems: exchangeable join (EJ) and the capacity constraint (CC). We prove that the system response time can be effectively reduced by EJ, while the reduced amount is constrained by the capacity of the multiprocessor. An upper bound model is constructed based on this analysis and a quick estimation algorithm is proposed. The approximation formula is verified by extensive simulation results, which show that the relative error of approximation is less than 5%.
文摘Real-time task scheduling is of primary significance in multiprocessor systems.Meeting deadlines and achieving high system utilization are the two main objectives of task scheduling in such systems.In this paper,we represent those two goals as the minimization of the average response time and the average task laxity.To achieve this,we propose a genetic-based algorithm with problem-specific and efficient genetic operators.Adaptive control parameters are also employed in our work to improve the genetic algorithms' efficiency.The simulation results show that our proposed algorithm outperforms its counterpart considerably by up to 36% and 35% in terms of the average response time and the average task laxity,respectively.
