|
In a distributed processing system with the application
task partitioned into a set of program modules, assignment of
those modules to processors is an important aspect of study.
We investigate the problem of finding an optimal assignment of
task modules, whose structure can be expressed as acyclic graph
and thus has precedence relationship, over processors in a
distributed system. The purpose of finding an optimal
assignment is to minimize the task turnaround time, that is, to
minimize the bottleneck-processor utilization, so that the
system resources could be fully utilized. All the existing
methods focus on this topic sometimes can not get the really
optimal value because intermodule communications can either be
in their assumption or be accomplished by those processors
that is not directly connected. We eliminate this constraint
called "valid check" and take full advantage of the processors
and links to carry the module communication so that a really
optimal assignment can be captured. The communicating
modules assigned to different processors can send the
message by way of other idle processors and links. The state
space technique is applied to search the optimal solution.
Further more, we use underestimate values (METU, ATU) and a
simple but effective rule to reduce the state space nodes for
sake of saving time and space. Because the intermodule
communicationsare fully taken into consideration, the state
space grows dramatically. We also refine the underestimate value
in some special case to improve the state space technique. Many
examples are simulated to illustrate that our method is
correctand suitable.
|