THE COMMUTATION SHEME OF THE PARALLEL COMPANION TRANSFORMATIONS FOR SPECIALIZED COMPUTING DEVICE
Abstract
The article shows 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 ar-ray 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 well-known algorithm of the parallel bubble is taken as the basis and developed. 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 distrib-uted combining of elements in pairs with a step equal to 4. The developed switching scheme con-tains 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 developed switching scheme performance has been carried out on typical tasks of sorting and complete enumeration of pairs of elements. The time costs compared with the scheme "parallel bubble" are reduced by 15–18 %. A linear dependence of the sorting time with a slope angle less than 1 has been 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 pro-duction device for decomposing a production system into independent subsets of products.
References
2. Levin I.I., Dordopulo A.I., Mel'nikov A.K., Gudkov V.A. Metody i sredstva arkhitekturno-nezavisimogo programmirovaniya vysokoproizvoditel'nykh vychislitel'nykh sistem [Methods and means of architecture-independent programming of high-performance computing sys-tems], Desyataya Vserossiyskaya mul'tikonferentsiya po problemam upravleniya (MKPU-2017) [Tenth all-Russian multiconference on control problems (ICPD-2017)]. Rostov-on-Don – Taganrog: Izd-vo YuFU, 2017, pp. 145-147.
3. Burtsev V.S. Parallelizm vychislitel'nykh protsessov i razvitie arkhitektury superEVM [Paral-lelism of computing processes and development of supercomputer architecture]. Moscow: TORUS PRESS, 2006, 416 p.
4. Voevodin V.V., Voevodin Vl.V. Parallel'nye vychisleniya [Parallel computation]. Saint Peters-burg: BKHV-Peterburg, 2002, 608 p.
5. Kravets O.Ya., Podval'nyy E.S., Titov V.S., Yastrebov A.S. Arkhitektura vychislitel'nykh sistem s elementami konveyernoy obrabotki: ucheb. Posobie [Architecture of computer systems with elements of conveyor processing: tutorial]. Saint Petersburg: Politekhnika, 2009, 152 p.
6. Sergeev S.L. Arkhitektury vychislitel'nykh sistem: uchebnik [Architectures of computing sys-tems: textbook]. Saint Petersburg:, 2010, 231 p.
7. Fet Ya.I. Parallel'nye protsessory dlya upravlyayushchikh system [Parallel processors for con-trol systems]. Moscow: Energoatomizdat, 1981, 160 p.
8. Va B.U. Louray M.B., Gotsze Li. 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.
9. Titenko E.A. Obshchaya strukturnaya skhema rekonfiguriruemogo mul'tiprotsessora [General block diagram of reconfigurable multiprocessor], Vestnik Voronezhskogo gosudarstvennogo tekhnicheskogo universiteta [Bulletin of Voronezh state technical University], 2011, Vol. 7, No. 9, pp. 53-57.
10. Dovgal' V.M., Titov V.S., Titenko E.A. Strategii bystrykh simvol'nykh vychisleniy dlya ischislitel'noy produktsionnoy sistemy [Strategies of fast symbolic calculations for the calculus production system], Izvestiya vysshikh uchebnykh zavedeniy. Priborostroenie [Journal of Instrument Engineering], 2008, Vol. 51, No. 2, pp. 44-47.
11. Titenko E.A., Evsyukov V.S. Produktsionnye sistemy i teorema o konfliktnykh slovakh [Pro-duction systems and the theorem on conflict words], Izvestiya Tul'skogo gosudarstvennogo universitet. Seriya tekhnologicheskaya sistemotekhnika [News of Tula state University. A se-ries of technological systems engineering], 2006, Issue 15, pp. 92-98.
12. Titenko E.A., Degtyarev S.V. Approximate search in the sample on the basis manber-wu meth-od, Journal of Fundamental and Applied Sciences, 2017, Vol. 9, No. 2, pp. 914-918.
13. Titenko E.A., Evsyukov V.S. Produktsionnye sistemy i teorema o konfliktnykh slovakh [The method and homogeneous computing device of k-approximate search of occurrences on a sample], Izvestiya Tul'skogo gosudarstvennogo universitet. Seriya tekhnologicheskaya sistemotekhnika [Bulletin of Voronezh state technical University], 2006, Issue 15, pp. 92-98.
14. Casbeer D.W. Forest fire monitoring with multiple small UAVs, Proceedings of the 2005 American Control Conference, 2005, pp. 3530-3535.
15. Spry S.C., Girard A.R., Hedrick J.K. Convoy Protection using Multiple Unmanned Aerial Ve-hicles: Organization and Coordination, Proc. of the 24th American Control Conference, Port-land, OR., June 2005.
16. Tonetti S., Hehn M., Lupashin S., D'Andrea R. Distributed control of antenna array with for-mation of UAVs, In World Congress, 2011, August, Vol. 18, No. 1, pp. 7848-7853.
17. Chung J. Cooperative Control of UAVs Using a Single Master Subsystem for Multi-task Multi-target Operations, Advances in Intelligent Systems and Computing, 2015, Vol. 345, pp. 193-212.
18. Korneev V.V., Kiselev A.V. Sovremennye mikroprotsessory [Modern microprocessor]. Saint Petersburg: BHV-SPb. 2003, 448 p.
19. King A. Distributed Parallel Symbolic Execution. B.S., Kansas State University, 2005.
20. Hwang K., Briggs F.A. Computer Architecture and Parallel Processing, 1984, pp. 32-40.
