Accession Number : ADA257433


Title :   Allocation of Periodic Tasks with Precedences on Transputer-Based Systems


Descriptive Note : Master's thesis


Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA


Personal Author(s) : Falcao, Marco A


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a257433.pdf


Report Date : Sep 1992


Pagination or Media Count : 197


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 to the same processor. The remaining tasks are allocated according to a heuristic function that considers task precedences, task execution times, and relative due 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.


Descriptors :   *DISTRIBUTED DATA PROCESSING , *PARALLEL PROCESSING , *ALLOCATIONS , *MULTIPROCESSORS , *ADA PROGRAMMING LANGUAGE , *COMPUTER NETWORKS , COMPUTERIZED SIMULATION , REAL TIME , ROUTING , FAULT TOLERANT COMPUTING , UTILIZATION , MAPPING , HEURISTIC METHODS , COSTS , NODES , THESES , OPTIMIZATION


Subject Categories : Computer Programming and Software
      Computer Hardware
      Computer Systems


Distribution Statement : APPROVED FOR PUBLIC RELEASE