Replicated module allocation to capacitated multiprocessors in network-based concurrent processing systems
Chin-Yuan Ho · 1992
Allocation of modules, with possible replication, on the task control flow graph (TCFG) of a software to capacitated processors on a network-based concurrent processing system is studied. The TCFG is a directed multigraph, consisting of sequential, OR- fork/join, AND-fork/join, subroutine call, and loop arcs. We establish general equations of flow conservation in both the logical level (i.e., in the TCFG), and the physical level (i.e., in the interconnection network). We also develop the methods for estimating intermodule communication cost and module invocation rates that are associated with subroutine calls and pretest loops. Due to the fact that module replication is allowed, we have to address the following questions: (1) how many copies of each module should be maintained; (2) how to allocate module copies over processors; and (3) how to distribute invocations of each module across its copies on different processors. The objective is to minimize the total interprocessor communication (IPC) cost and total module execution cost subject to hardware capacity constraints and constraints associated with equations of flow conservation. We show that when module replication is allowed, the uncapacitated module allocation problem (MAP) can be modeled as a continuous linear program which is in Class-P. With capacity constraints, MAP becomes a mixed 0/1 integer program, which is NP-hard. We develop an $\epsilon$-optimal approximation algorithm for the replicated-and-capacitated module allocation model using the primal decomposition technique. We also develop a primal heuristic to obtain a good feasible solution that can be used in the $\epsilon$-optimal algorithm as an initial incumbent solution. The effectiveness of these solution procedures is compared with that of the LP-based branch-and-bound method. Computational results are reported over a variety of problem instances.