Sm. Yoo et al., Dynamic scheduling and allocation in two-dimensional mesh-connected multicomputers for real-time tasks, IEICE T INF, E84D(5), 2001, pp. 613-622
Among several multiprocessor topologies, two-dimensional (2D) mesh topology
has become popular due to its simplicity and efficiency. Even though a num
ber of scheduling and processor allocation schemes for 2D meshes have been
proposed in the literature, little study has been done aimed for realtime e
nvironment. In this paper, we propose an on-line scheduling and allocation
scheme for real-time tasks that require the exclusive use of submeshes in 2
D mesh system. By effectively manipulating the information on allocated or
reserved submeshes, the proposed scheme can quickly identify the earliest a
vailable time of a free submesh for a newly arrived task. We employ a limit
ed preemption approach to reduce the complexity of the search for a feasibl
e schedule. Computer simulation reveals that the proposed scheme allows hig
h throughput by decreasing the number of tasks rejected.