A HARDWARE-ORIENTED METHOD OF ACCELERATED SEARCH BY TEMPLATE BASED ON STRUCTURAL-PROCEDURAL COMPUTING

Abstract

The operation of searching for occurrences of a pattern in a text is generally significant in modern
computing tools for solving problem-searching tasks. Of greatest interest are hardware and software solutions
that have a homogeneous structure and regular connections between computing blocks. The aim of
the work is to reduce the time costs for searching for occurrences based on the use of parallel search in
associative memory and the method of parallelization by iterations. The proposed method uses associative
memory for parallel search for occurrences and dynamic reconfiguration of the structure of the original
string from a one-dimensional form to a matrix form. The method is critical to such resources as the number
of memory access channels, the volume of block memory for creating and parallel operation of an
array of associative cells. Involvement of all elements in the reconfiguration entails excessive costs of the
internal block memory for sequential viewing of partial entries by one set of starting positions multiples of
the sample length (the second symbolic operand). Instead, an approach is proposed to combine in time the
search for partial entries by two sets of substrings multiples of the sample length, with a simultaneous
proportional reduction in the elements of the bit slice of the associative memory for each set, which allows
processing several sample symbols at the current search step. Quantitative estimates of search time are
determined by the number of comparison and substring writing operations in the overall work cycle, as
well as the proportions of the time of these operations. It is shown that for samples of more than 10 elements,
the time gain is approximately 1.8-2 times. This effect is obtained by eliminating the steps of sequential
shift with transitions between the boundary elements of the strings. The developed method provides
pipeline processing of a stream of string operands with a combination of viewing at the current
search step of a non-unit set of characters of the processed string. The search time is re duced by introducing
a pipeline, the number of stages of which depends on the reduction coefficient of the bit slice size,
which allows hardware implementation of the structural-procedural approach used in reconfigurable
computing systems