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.