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