Narrow Results

Let A and B be two groups of up to n elements distributed on the first row of an n × n reconfigurable mesh, and C_A,B a subset of the cartesian product A × B satisfying some unknown condition C. Only one broadcasting step is needed in order to compute C_A,B's elements. However, the problem of moving C_A,B's elements to the first row in optimal time (so that they can be further processed) is not trivial. The conditional cartesian product (CCP) problem is to move C_A,B's elements to the first row in steps. This requires optimizing the cartesian product operation such that C_A,B's elements will be optimally scattered in the mesh, so that O(n) elements can be retrieved in a single step as opposed to elements needed if the cartesian product is not optimized). We give a deterministic algorithm that for any A, B, C solves this problem in steps, and an "adaptive" randomized algorithm whose optimality is verified by experimental results. Note that the CCP is a case where we overcome the inherent limitation of the reconfigurable mesh, namely, the inability to perform fast routing of packets located in a small area.

We also present the model of production systems, in which computation is realized by executing cartesian productions of subsets in a common element space. Production systems are useful for database applications, expert systems, and can even be used as a general parallel programming language. Solving the CCP problem allows us to devise an efficient implementation for production systems on the reconfigurable mesh. In this way the reconfigurable mesh is shown to be an attractive architecture for database machines and for parallel programming as well.

The objects of pattern recognition have in the past been primarily physical in nature, describable in terms of some physical units of measurement. The patterns of interest in this paper are conceptual or logical. They are to be representative of structures known to be operative in the human mind. A hybrid technique is proposed, involving the use of structural prototypes from pattern recognition combined with production systems from artificial intelligence. The purpose is to enable the computer interface to observe, detect, identify and anticipate conceptual structures. As a result, the interface system should have a more comprehensive “perspective” on what the user is doing and likely to do next. It should therefore be better prepared to provide him/her with adaptive assistance.

Much effort has been expended on developing special architectures dedicated to the efficient execution of problems in artificial intelligence (AI), especially production systems. While artificial neural networks (ANNs) offer the promise of solving various problems in pattern recognition and classification, we demonstrate here that the ANN approach can be applied to the AI production system paradigm. Among various types of neural networks, the three-layers of ring-structured feedback network is considered in this paper to suit the problem domain under investigation. Characteristics of the production system paradigm are identified. Various aspects of the use of feedback neural networks in mapping production systems are discussed. Two types of representation techniques are studied: local and hierarchical representations. A hierarchical representation derives features from patterns in production systems and constructs a 3-dimensional space called feature space, where a pattern can be uniquely defined by a vector. To demonstrate the efficient use of the neural network approach, a mapping of the generic production system is detailed throughout the paper. The results of a deterministic simulation demonstrate that the three layers of ring-structured feedback neural network architecture can be an efficient processing mechanism for the AI production system paradigm.

The importance of production systems in artificial intelligence (AI) has been repeatedly demonstrated by a large number of expert systems. As the number and size of expert systems grow, there has however been an emerging obstacle in such AI applications: the large processing time. The need for faster execution of production systems has spurred research in both the software and hardware domains, including connectionist architectures. This paper surveys various aspects of parallel distributed processing of production systems. Approaches taken to date to solve the problems associated with production systems are classified here into three levels: the algorithmic level, the parallel implementation level, and the connectionist level. Several pattern matchers and multiple rule firing principles are presented to demonstrate the algorithm level improvement. Several parallel implementation efforts are surveyed along with experimental results on real machines or with simulators. The presentation of three different types of connectionist production systems (local, distributed, and hierarchical representation) completes this survey. Finally, we explore some potential avenues towards the implementation of a true asynchronous parallel production system.

RETE match for production systems and Arc Consistency (AC) filtering are two efficient AI algorithms that are designed for particular constraint satisfaction problems (CSP). Interestingly, it is possible to integrate the two within a common framework, and provide RETE with the lookahead advantages of AC. Unfortunately, the resulting quadratic dependence of AC on working memory (WM) size precludes the application of AC to RETE, since RETE responds to incremental changes in WM. Recent results in AC graph factorization, however, reduce the quadratic dependence to just linear for certain classes of problems, including RETE.

In this paper, we present RETE and AC within the unified framework of Call-Graph Caching (CGC) evaluation. We describe factored arc consistency (FAC) and its use in an integrated FAC/RETE algorithm that provides RETE match with AC lookahead. We discuss our implementations, promising initial empirical results, and explore FAC/RETE’s applicability conditions and extensions. We conclude that incorporating factored AC into RETE match is an interesting and potentially useful application of arc consistency methods to the RETE CSP.

This paper introduces a transaction model for parallel production systems, where rules can be fired in a completely asynchronous parallel manner. A model is developed to describe two properties of a serial production system execution, namely, conditional dependence (a rule firing removes another from the conflict set) and prioritization (by the conflict resolution mechanism). These are used as the basis to define the correctness criteria for parallel production execution, namely, conditional serializability, prioritized serializability, and prioritized conditional serializability. A graph model is used to represent production system execution which provides a means of expressing correctness as graph acyclicity, which in turn is used as a basis to develop practical schedulers that manage the concurrent asynchronous production execution and ensure correctness. Two practical schedulers, namely, conditional strict two-phase locking and priority queue scheduler are developed for conditional serializability and prioritized serializability, respectively. They are combined for prioritized conditional serializability.

Parallel-rule firing approaches have been proposed to improve the performance of production systems. However, few models have been developed to measure the performance of parallel-rule firing approaches. There are three approaches to evaluating system performance, namely, analytical modeling, simulation, and system prototyping or implementation. Analytical modeling has its advantage in being cost effective and providing a powerful tool for studying various aspects of system performance by varying system parameters. Since analytical modeling has been very successfully used in evaluating database system performance, we develop such a model for parallel production systems, where rule firing is modeled as a transaction. Both resource contention and data contention are modeled in detail and the performance of locking, timestamp and optimistic approaches is analyzed. We show that significant speedup can be gained in parallel rule execution. Our main contribution is in the insights into parallel-rule firing provided by parametric modeling.

The study of production systems taxonomy not only provides a good description of organization dominant groups but also provides the ground for more specialized studies such as a study of performance, the proper form of production decisions in each group, and the theorizing in it. In some taxonomic studies, due to high speed and ease of implementation, K-means cluster analysis was used to analyze data but the convergence took place in local optimum. For this reason, Hybrid Clustering Algorithms were used for the clustering of manufacturing companies. The clustering results of these methods were compared using validation indicators. According to the results of the comparisons, the best clustering algorithm was chosen, based on which cluster naming was done. Then, using the results of Discriminant Analysis, the distinctive dimensions of clusters were identified and the results showed that the manufacturing systems in Iran can be introduced in two dimensions of green production planning and resource capacity.