On the run-time optimization of the Boolean logic of a program

摘要

The problem considered here is the optimal scheduling of a Boolean expression on a single-processor system. We consider a Boolean expression in which each Boolean variable represents the binary outcome (or return code) of a program module. The result of the expression may be known without executing all modules (e.g. an OR-operation is terminated as soon as one of the operands returns the value 1), so that the order in which the modules are executed influences the cost involved in finding the result. The optimisation discussed here consists in finding the operand arrangement that minimizes the average execution cost. The cost of each module represents the consumption of resources such as CPU time, elapsed time, number of input-outputs, etc. The assumptions regarding the modules are: (i) No module execution is the pre-requisite for the execution of another module. (ii) At each execution, the return code and the cost of a module do not depend on the sequence of execution. (iii) Over a number of executions, the return code and the cost of a module may be statistically dependent or a deterministic function of return codes and costs of other modules.A prototype scheduler is presented, that implements a sub-optimal strategy. It stores the Boolean expression in tabular form, passes control to a module at a time, as needed for the Boolean computation, measures the cost of execution and decides empirically what operand arrangement is more advantageous.