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.
References
otechestvennykh superEVM v period do 2020 goda [Problems of ensuring the productivity growth
of domestic supercomputers in the period up to 2020], Informatsionnye tekhnologii i vychislitel'nye
sistemy [Information technologies and computing systems], 2010, No. 3, pp. 15-18.
2. Korneev V.V. Sleduyushchee pokolenie superkomp'yuterov [The next generation of supercomputers],
Otkrytye sistemy [Open systems], 2008, No. 8, pp. 14-19.
3. Guzik V.F., Kalyaev I.A., Levin I.I. Rekonfiguriruemye vychislitel'nye sistemy: ucheb. posobie
[Reconfigurable computing systems: textbook], under the general editorship of I.A. Kalyaeva.
Taganrog: Izd-vo YuFU, 2016, 472 p.
4. Voevodin, V.V., Voevodin Vl.V. Parallel'nye vychisleniya [Parallel computing]. St. Petersburg:
BKhV-Peterburg, 2002, 608 p.
5. Ognev I.V., Borisov V.V., Sutula N.A. Assotsiativnaya pamyat', sredy, sistemy [Associative
memory, environments, and systems]. Moscow: Goryachaya liniya – Telekom, 2016, 416 p.
6. King A. Distributed Parallel Symbolic Execution. B.S., Kansas State University, 2005,
pp. 181-197.
7. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturnoprotsedurnoy
organizatsiey vychisleniy [Modular-stackable multiprocessor systems with structural
and procedural organization of calculations]. Moscow: Izd-vo Yanus-K, 2003, 380 p.
8. Fet Ya.I. Parallel'nye protsessory dlya upravlyayushchikh system [Parallel processors for control
systems]. Moscow: Energoatomizdat, 1981, 160 p.
9. Va B.U., Louray M.B., Li Gotsze. EVM dlya obrabotki simvol'noy informatsii [Computer for
processing symbolic information], TIIER [Proceedings of the Institute of Electrical and Radio
Electronics Engineers], 1989, Vol. 77, No. 4, pp. 5-40.
10. Artamonov D.S., Putrya M.G. Metod optimizatsii vychislitel'nogo protsessa na
rekonfiguriruemykh vychislitel'nykh sredakh [Method of optimization of the computational
process on reconfigurable computing environments], Informatsionnye tekhnologii
vychislitel'nye sistemy [Information Technologies computing systems], 2010, No. 3, pp. 19-26.
11. Putrya F.M. Arkhitekturnye osobennosti protsessorov s bol'shim chislom vychislitel'nykh
yader [Architectural features of processors with a large number of computing cores],
Informatsionnye tekhnologii [Information technologies], 2009, No. 4, pp. 2-7.
12. Burtsev V.S. Parallelizm vychislitel'nykh protsessov i razvitie arkhitektury superEVM [Parallelism
of computing processes and the development of the architecture of supercomputers].
Moscow: TORUS PRESS, 2006, 416 p.
13. Titenko E.A., Evsyukov V.S. Produktsionnye sistemy i teorema o konfliktnykh slovakh
[Productional systems and the theorem on conflict words], Izvestiya Tul'skogo
gosudarstvennogo universitet [Izvestiya Tulskogo gosudarstvennogo universiteta], 2006,
Issue 15, pp. 92-98.
14. Titenko E.A. Obshchaya strukturnaya skhema rekonfiguriruemogo mul'tiprotsessora [General
block diagram of a reconfigurable multiprocessor], Vestnik Voronezhskogo gosudarstvennogo
tekhnicheskogo universiteta [Bulletin of the Voronezh State Technical University], 2011,
Vol. 7, No. 9, pp. 53-57.
15. Titenko E.A. Metod i odnorodnoe vychislitel'noe ustroystvo k-priblizitel'nogo poiska vkhozhdeniy
po obraztsu [A method and a homogeneous computing device for k-approximate search for occurrences
in a sample], Vestnik Voronezhskogo gosudarstvennogo tekhnicheskogo universiteta [Bulletin
of the Voronezh State Technical University], 2011, Vol. 7, No. 7, pp. 70-78.
16. Titenko E.A. Metod parallel'nogo poiska po obraztsu i matrichnoe ustroystvo dlya ego
realizatsii [Method of parallel search by sample and matrix device for its implementation],
Informatsionnye sistemy i tekhnologii [Information systems and technologies], 2011, No. 4
(66), pp. 24-30.
17. Wichert A. Artificial intelligence and a universal quantum computer, AI Communications,
2016, Vol. 29, Issue 4, pp. 537-543.
18. Titenko E.A., Degtyarev S.V. Approximate search in the sample on the basis manber-wu method,
Journal of Fundamental and Applied Sciences, 2017, Vol. 9, No. 2, pp. 914-918.
19. Titenko E.A., Zerin I.S. Ischislitel'naya sistema produktsiy i protsedura raspoznavaniya
konfliktov dannykh [Calculative system of products and the procedure for recognizing data
conflicts], Vestnik komp'yuternykh i informatsionnykh tekhnologiy [Bulletin of Computer and
Information Technologies], 2012, No. 2, pp. 24-29.
20. Lyuger Dzh.F. Iskusstvennyy intellekt: strategii i metody resheniya slozhnykh problem [Artificial
intelligence: strategies and methods for solving complex problems]. Moscow: Izd. dom
«Vil'yams». 2003, 864 p.
21. Titenko E.A., Kripachev, Marukhlenko A.L. Kommutatsionnaya skhema parallel'nykh parnykh
perestanovok dlya spetsializirovannogo produktsionnogo ustroystva [Switching scheme of
parallel pair permutations for a specialized production device], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2018, No. 8 (203), pp. 29-38.
22. Makkonell Dzh. Osnovy sovremennykh algoritmov [Fundamentals of modern algorithms].
2nd ed.: transl. from engl., ed. by S.K. Lando. Moscow: Tekhnosfera, 2004, 386 p.
23. Knut D. Sortirovka i poisk [Sorting and searching]. Vol. 3. Moscow: Vil'yams, 2000, 500 p.
24. Batcher K.E. Sorting Networks and their Applications, Proc. AFIPS Spring Joint Comput.
Conf., 1968, Vol. 32, pp. 307314.
25. Pisarenko I.V., Alekseev K.N., Mel'nikov A.K. Resursonezavisimoe predstavlenie
sortiruyushchikh setey na yazyke programmirovaniya Set@l [Resource-independent representation
of sorting networks in the programming language Set@l], Vestnik komp'yuternykh i
informatsionnykh tekhnologiy [Bulletin of Computer and Information Technologies], 2019,
No. 9, pp. 3-10.
