Multiprocessor optimizations: |interconnection and task assignment

Abstract

Effective spreading of the use of muLtiprocessors, -or distributed processing in general-, and achieving the potential advantages of this new design option require various hardware and software-related probLems to be solved. This study is a research on two basic probLem areas, namely the Interconnection and the Task Assignment in Multiprocessors. Any multiprocessor system that employs more than one processor for a singLe job must be designed to allow efficient communication between processors, so that the advantages of multiprocessing is not negated by inefficient communication. As the number of processors grows, the interconnection design becomes more cruciaL as crossbar or fully-connected schemes become impractical. Thus, from a realizability point of view a partially-connected structure is desirable, which, however, in turn, introduces the problem of variable interprocessor distances, complicating the task assignment process. In the first part of this study, PON (Processor Omega Network), a partially- connected, multistage processor network with desirabLe implementation and communication properties is proposed and evaluated. In any distributed processing environment, except for identical processors forming a fully-connected network of uniform interprocessor distances, optimal assignment of software modules comprising a task to processors of the network is essential for minimum-time completion of the task and this can be achieved by balancing two conflicting factors; minimization of interprocessor communication and maximization of load balance of processors. In addition to the complexities of the previously studied resource limited task-assignment environments, partially-connectedness introduces the new interrelated problems of indirect data transfers, availability of intermediate processors, and data routing when more than one path is available between non-adjacent pairs. Two different performance measures are proposed for the two operation environments considered. The minimum port-to-port time (PTP) criterion produces optimal assignments in single-run environments, whereas the optimum performance in a multi-run operation mode is achieved by minimizing the least re-initiation period (LIP), which is equivalent to maximizing the overlap between successive task executions. The characteristics of the objective functions, the number of constraints, and the precedence reLations dictated an aLgorithmic solution to the assignment problem. An analytical model is developed to describe the task assignment environment considered in this study, and based on the model components and the proposed objectives, the optimization problems for both environments are formulated. Some possible methods for storage-and-processing efficient representations of hardware and software are investigated and the task assignment algorithm for partially-connected networks (PCTAA) is presented and the methods and modifications to reduce its computational complexity -related to the structure of networks and tasks- are discussed in order to extend its use to analysis of larger systems.