Control, the intelligent selection of actions to execute, is critical to the performance of knowledge-based systems such as planners, job shop schedulers, and interpretation systems. This is particularly true for parallel systems in which the controlling agent has the additional goal of maximizing the utilization of multiple resources. This work studies the issues of control in parallel knowledge-based systems.
It is critical to the efficient parallelization of complex programs to understand how concurrent activities can mutually facilitate each other by sharing partial computations or hinder each other through conflicts for shared resources. To this end, we have developed a formal model, called the IDP/UPC, that specifies how interactions between subtasks can be identified from formal models of the problem-solving process and how the strength and frequency of these interactions can be predicted from environmental models. We have verified the accuracy of this model for a class of sophisticated interpretation problem solving architectures. This information can then be used to inform the control process which will schedule concurrent tasks to take advantage of positive interactions and avoid co-executing tasks whose interactions would be detrimental.
The empirical component of this research involves studying the practical issues involved in integrating the information gained from theoretical analysis into the control process. To this end, we have implemented a version of our design-to-time scheduler that schedules parallel task structures; this scheduler exploit information about the expected distribution of task duration and quality, and the interactions patterns among subtasks. This information, together with time deadlines and criteria on acceptable satisfaction for the overall task, is used to generate multiprocessor schedules. As part of this process, the possibility of subtask failure is taken into account so that multiple ways of achieving a task may be incorporated into the parallel schedule in order to have a higher likelihood of meeting the overall task objectives. We have also conducted simulation studies to determine under what conditions rescheduling is effective when task execution does not conform to expectations based on deviation from expected distribution. We have also implemented a problem generator and parallel simulator for constraint satisfaction problems. We are now beginning an empirical study to assess the effect that the distribution of "no-goods" has on the performance of different partitioning of the problem among processors. The goal of this work is to develop a theory of how constraint satisfaction nodes should be partitioned among different processors and what protocol should be used for communication of partial results obtained on each processor so as to maximize effective parallelism.
In summary, the intended result of this research is two-fold: a validation and extension of formal models of how control activities relate to the deep structure of problem-solving process and environment, and the development of parallel control architectures that use these models to schedule activities.
See the following WWW pages for more details: http://dis.cs.umass.edu/research/idp.html and http://dis.cs.umass.edu/research/parallel.html, and the paper Fujita, S. and Lesser, V. R. "Centralized Task Distribution in the Presence of Uncertainty and Time Deadlines." In Proceedings of the Second International Conference on Multi-Agent Systems, California: AAAI Press, pp. 87-94, 1996.