Authors Ya.E. Romm, D.A. Chabanyuk
Month, Year 07, 2014 @en
Index UDC 681.3:007
Abstract Was described method of comparing words numeric and string type using the vertical processing. The method is constructed on the basis of the discharge parallelization of algebraic addition of binary numbers and applied to sorting algorithms, as well as the merger of strings as an information search step. Presented by the original method was bit by bit parallel addition without calculating transfer in bit code of the sign modification for by bit parallel comparison of numbers and strings. To perform algebraic addition without calculating a reverse transfer binary negative numbers and given additional code modification, eliminating the calculation of transfer. When comparing string elements all word characters encoded binary numbers in ASCII-code set of binary characters per word is interpreted as a binary number in a positional number system. When comparing by algebraic addition of the numbers they are aligned to the senior class. Inclusion in the method of comparing parallel algorithms for sorting and merging increases the maximum depth parallel to the ideal level parallelism comparisons of words and at the same time based on the level of operations. The method of allocation was the senior non-zero sign bit in the word, the resulting comparison. The method includes algorithmic and schematics, providing maximum bit parallelization. Additionally there was the problem of occurrence of a substring in a string. Was synthesized parallel search algorithm for the maximum occurrence of a substring in a string. Estimates are given for the time complexity, in particular the maximum parallelism occurrence of a substring in search string characterized by the time complexity O(1), regardless of the number of characters per string. Examples are algorithms and schemes implementation of the proposed method.

Download PDF

Keywords Bit by bit-parallel addition without calculating transfer; bit code of the sign; Bit by bit-parallel comparison of numbers and strings; parallel sorting and searching; time complexity.
References 1. Virt N. Algoritmy i struktury dannykh [Algorithms and data structures]. Moscow: DMK Press, 2010, 272 p.
2. Knut D. Iskusstvo programmirovaniya dlya EhVM. T. 3. Sortirovka i poisk [The art of computer programming. Vol. 3. Sorting and searching]. Moscow: Vilyams, 2007, 832 p.
3. Romm Ya.E. Metod vertikalnoy obrabotki potoka celochislennykh gruppovykh dannykh. I. Gruppovye arifmeticheskie operacii [The method of vertical flow of integral group data. I. Group arithmetic operations], Kibernetika i sistemnihy analiz [Cybernetics and Systems Analysis], 1998, No. 3, pp. 123-151.
4. Romm Ya.E. Metod vertikalnoy obrabotki potoka tselochislennykh gruppovykh dannykh. II. Prilozhenie k binarnym arifmeticheskim operatsiyam [The method of vertical flow of integral group data. II. The Annex to the binary arithmetic operations], Kibernetika i sistemnyy analiz [Cybernetics and Systems Analysis], 1998, No. 6, pp. 146-162.
5. Romm Ya.E., Chabanyuk D.A. Primenenie metoda vertikalnoy obrabotki informatsii k operatsiyam sravneniya i poiska [Application of the method of vertical processing of information for comparisons and searches]. Taganrog: TGPI, 2013, 32 p. Dep. v VINITI 20.05.13, № 141 – V 2013.
6. Romm Ya.E., Ivanova A.S. Vertikalnoe gruppovoe algebraicheskoe summirovanie primenitelno k sortirovke so sliyaniem i parallelnomu poisku [The vertical group of the algebraic summation with respect to merge sort and parallel search]. Taganrog: TGPI., 2012, 44 p. Dep. v VINITI 03.09.2012, № 362 – V 2012.
7. Romm Ya.E., Chabanyuk D.A. Vertikalnye gruppovye arifmeticheskie operatsii nad tselochislennymi dannymi bez vychisleniya perenosa [The vertical group arithmetic integer data without calculation of transfer], Fundamentalnye issledovaniya [Fundamental Research], 2012, No. 11, pp. 960-964.
8. Romm Ya.E., Chabanyuk D.A. Sravnenie slov s edinichnoy vremennoy slozhnostyu [Compared with single time complexity]. Taganrog: TGPI, 2013, 30 p. Dep. v VINITI 30.10.13, № 306 – V 2013.
9. Charras C., Lecroq T. Handbook of Exact String Matching Algorithms. College Publications. 2004, 256 p.
10. Ivanova A.S. Rasshirenie diapazona dannykh dlya vertikalnoy obrabotki primenitelno k sortirovke so sliyaniem i poisku: Avtoref. dis. … kand. tekhn. nauk [The expansion of the range of data for vertical processing applied to the merge sort and search. Cand. of eng. sc. abstract of thesis]. Taganrog: YuFU, 2013, 22 p.

Comments are closed.