Search

Search Results

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

  E.A. Titenko, E.V. Taldykin

  2021-02-25

  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.