An integrated optimal task assignment policy
Sub Ramakrishnan, Larry A. Dunning, Thomas Nitsch · 1993
Given a set of tasks the task assignment problem ia to determine the processor from a processorset at which a task can reside for its lifetime.Each task has a known execution cost on each of the processors, and may cmnrnunicatc with zero or more other tasks in the task set.'lko ccmrmmicating tasks incur an intmpmceas communication overheadwhen they are assigned to two different processors.We propose an algorithm for task assignment problem which finds optimal solutions.The algorithm has exponential complexity; however, it performs quite well in practice in comparison to previous methods, and can be applied in a practical environment.Our assignment is baaed on Stone's [13] optimti~criteria which is the total cost for execution and interpcess communication.We use the well-known A* tree search algorithm to determine the optimal solution.'he main contribution of this paper is that we integrate the A* approach with a scheme that transforms an n poc-sor assignment problem to equivalent two processor network-flow pcobkms.Moreprecisely,at each nodeof the A* search tree, we solve certain max-tlow problems that enable each processor to "grab" tasks that are "strongly attracted"to it.'l'hisprocedure results in a speed-up of the basic algorithm.We present practical, nrtmericsl examples to show that the new integrated policy helps in reducing size of the search tree.