REPLICATED MODULE ALLOCATION IN LAN-BASED CONCURRENT PROCESSING SYSTEMS

We consider a problem involving the design of a system for concurrent processing of application software using multiple processors on a loca l area network. The task control-flow graph which graphically describe s the software logic is allowed to be an arbitrary directed multigraph . We establish equations of flow conservation which arise in the execu tion of modules on the set of interconnected processors. Incorporating these equations, we develop a mixed integer programming model to find an optimal allocation of program modules, with possible replications, to the set of capacitated processors. The objective is to minimize th e total interprocessor communication cost and module execution cost su bject to the capacity constraints of processors and the broadcast chan nel. The decisions involved are: how many copies of each module should be maintained; how to allocate module copies across processors; and h ow to distribute invocations of each module across its copies on diffe rent processors. We report numerical results from solving the model.