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

This work is motivated by the advance of multiprocessor sys-tem architecture, in which the allocation of tasks over heteroge-neous memory modules has a significant impact on the task ex-ecution. By considering two different types of memory modules with different access latencies, this paper explores joint consider-ations of memory allocation and real-time task scheduling to min-imize the maximum utilization of processors of the system. For implicit-deadline sporadic tasks, a two-phase algorithm is devel-oped, 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 pro-posed 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 simula-tions are further conducted to analyze the proposed algorithm