Parametric Combinatorial Computing and a Problem of Program Module Distribution

Abstract

In parametnc computing some parts of a problem description are given as funcuons of one or more parameters which vary over a range of values Any fgxed values of the parameters specify a problem instance, and the goal of parametric computing ~s to solve all such problem instances efficiently as a funcUon of the parameter values. The output ~s either a partition of the parameter space into regions such that all instances m the same region have the same solution, or some other compact output permitting rapid solution to any given problem instance. A general parametnc computing method that works well for a large class of combinatorial problems ts presented The method is related to one for solving ratio optim~aUon problems developed by Megiddo The parametric method is illustrated by solvmg a problem of dmnbutmg modules of a computer program between two processors. Associated with each module are processing costs on each processor, and assocmted with each pair of modules is a communication cost recurred by d~stributing the modules on d~fferent processors The problem is to distribute the modules to mmunize the total cost of computauon. Stone has solved this problem for fixed costs, and for costs of one processor varying as a function of a single parameter representing the varying load on one processor. The general parametnc computing method is applied to solve the problem efficiently for costs of both processors varying as a funcuon of two independent parameters.