SWITCHING MODEL OF PARALLEL COMPARISONS FOR A DATA FLOW RULE BASED SYSTEMS

Abstract

The article is show the reduction of time spent on generating combinations of elements of the set. The elements of the set are formed from samples (left parts) of the production rules. The main task is to build time-efficient schemes (algorithms) for parallel generation of combinations of array elements. With regard to production systems, such schemes are necessary for the activation of a subset of products applicable to character data in the current step. The basis is taken and developed the well-known algorithm of the parallel bubble. The switching circuit "parallel bubble" consists of two alternating variants of switching elements in pairs. These commutations are based on local union into pairs of array elements with adjacent indices. Such a local combination of elements into pairs leads to "small" displacements of elements along the length of the array and the regular nature of the generation of pairs. In each pair, the operation of comparison-exchange of operands is performed. For production systems, the comparison operation is reduced to the search for sample intersections and the formation of a list of conflicting words. The reduction in the generation time of combinations is based on the construction of switching options with distributed combining of elements in pairs with a step equal to 4. The developed switching scheme contains on odd switching steps with a local combination of elements in pairs. In even-numbered steps, a switching accelerator is performed with a distributed combination of elements in pairs. The simulation of the work of the developed switching scheme was carried out on typical tasks of sorting and complete enumeration of pairs of elements. The reduction of time costs compared with the scheme "parallel bubble" by 15-18%. A linear dependence of the sorting time with a slope angle less than 1 was determined. This allows the use of a switching circuit for large-scale production systems. Local and distributed communications in the switching scheme preserve the property of regularity. This feature determines the hardware implementation of the circuit in the form of a parallel switch with natural scaling. This scheme can be used in a specialized production device for decomposing a production system into independent subsets of products.