Allocation of periodic tasks with precedences on transputer-based systems

Abstract

Task allocation is an important component of the process of mapping modules of application programs to multicomputers. A scheme for static allocation of periodic tasks with precedences to processors is developed considering task execution times, communication costs, and utilization level of each processor. It has the main goal of minimizing the application response time with a minimum number of processors. A network of transputers is employed as a platform to experimentally evaluate the allocation approach constructed with this work. An existing communication layer in the language ADA is improved to provide an efficient support for task flow simulations on transputer networks. The first phase of the allocation scheme is a constructive assignment heuristic that allocates the cluster of tasks composed of all tasks in the critical path in the same processor. The remaining tasks are allocated according to a heuristic function that considers task precedences, task execution times, and relative sizes of intertask messages. The initial allocation is improved in the second phase by using an iterative pairwise interchange of tasks that considers interprocessor communication distances. The overall scheme of task allocation was successfully tested and analyzed through simulation of several applications on a transputer network providing a near optimal solution.