Abstract
In this paper, we study a new model for dynamic processor allocation in multicomputer systems. The model, originally proposed in [3] for hypercube systems, uses Boolean functions to represent free processors and allocates processors by applying Boolean operations on the functions. With the model, existing techniques for handling Boolean functions, such as binary decision diagram (BOD), can be applied directly. This paper extends previous results in several ways. First, a technique called lazy combining is introduced, which uses the current free processor composition as much as possible - changes on/y when an incoming request fails to find a match. Second, when recombining of the free processors is necessary, a comprehensive literal reordering technique for BDD is presented to identify matching free subcubes. Third, we eztend the new model to general k-ary n-cube mesh or torus systems. Due to the generality of our model, the extension is straightforward as long as some restrictions are observed. Finally, complexities and performance evaluation of the algorithms are presented.