TY - GEN
T1 - Task partitioning upon memory-constrained multiprocessors
AU - Fisher, Nathan
AU - Anderson, James H.
AU - Baruah, Sanjoy
PY - 2005
Y1 - 2005
N2 - Most prior theoretical research on partitioning algorithms for real-time multiprocessor platforms has focused on ensuring that the cumulative computing requirements of the tasks assigned to each processor does not exceed the processor's processing power. However, many multiprocessor platforms have only limited amounts of local per-processor memory; if the memory limitation of a processor is not respected, thrashing between "main" memory and the processor's local memory may occur during run-time and may result in performance degradation. We formalize the problem of task partitioning in a manner that is cognizant of both memory and processing capacity constraints as the memory constrained multiprocessor partitioning problem, prove that this problem is intractable, and present efficient algorithms for solving it under certain - well-defined - conditions.
AB - Most prior theoretical research on partitioning algorithms for real-time multiprocessor platforms has focused on ensuring that the cumulative computing requirements of the tasks assigned to each processor does not exceed the processor's processing power. However, many multiprocessor platforms have only limited amounts of local per-processor memory; if the memory limitation of a processor is not respected, thrashing between "main" memory and the processor's local memory may occur during run-time and may result in performance degradation. We formalize the problem of task partitioning in a manner that is cognizant of both memory and processing capacity constraints as the memory constrained multiprocessor partitioning problem, prove that this problem is intractable, and present efficient algorithms for solving it under certain - well-defined - conditions.
KW - Memory-constrained systems
KW - Multiprocessor systems
KW - Partitioned scheduling
KW - Utilization-based schedulability tests
UR - https://www.scopus.com/pages/publications/33749053819
U2 - 10.1109/RTCSA.2005.97
DO - 10.1109/RTCSA.2005.97
M3 - Conference contribution
AN - SCOPUS:33749053819
SN - 0769523463
SN - 9780769523460
T3 - Proceedings - 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
SP - 416
EP - 421
BT - Proceedings - 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
T2 - 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
Y2 - 17 August 2005 through 19 August 2005
ER -