Partitioned Scheduling for Real-Time Tasks on Multiprocessor Embedded Systems with Programmable Shared SRAMs

摘要

This work is motivated by the advance of multiprocessor system architecture, in which the allocation of tasks over heterogeneous memory modules has a significant impact on the task execution. By considering two different types of memory modules with different access latencies, this paper explores joint considerations of memory allocation and real-time task scheduling to minimize the maximum utilization of processors of the system. For implicit-deadline sporadic tasks, a two-phase algorithm is developed, where the first phase determines memory allocation to derive a lower bound of the maximum utilization, and the second phase adopts worst-fit partitioning to assign tasks. It is shown that the proposed algorithm leads to a tight (2 -(2/(M+1)))-approximation bound where M is the number of processors. The proposed algorithm is then evaluated with 82 realistic benchmarks from MRTC, Medi-aBench, UTDSP, NetBench and DSPstone, and extensive simulations are further conducted to analyze the proposed algorithm.