Authors E. A. Titenko, A. V. Kripachev, A. L. Marukhlenko
Month, Year 08, 2018 @en
Index UDC 681.3+004.32
DOI 10.23683/2311-3103-2018-8-29-38
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 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 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 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 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 production device for decomposing a production system into independent subsets of products.

Download PDF

Keywords Commutation network; parallel sorting; reconfiguration of connections.
References 1. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturno-protsedurnoy organizatsiey vychisleniy [Modular-scalable multiprocessor system with structural-procedural organization of computing]. Moscow: Izd-vo YAnus-K, 2003, 380 p.
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 systems], 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 [Parallelism 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 Petersburg: 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 systems: textbook]. Saint Petersburg:, 2010, 231 p.
7. Fet Ya.I. Parallel'nye protsessory dlya upravlyayushchikh system [Parallel processors for control 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 [Production systems and the theorem on conflict words], Izvestiya Tul'skogo gosudarstvennogo universitet. Seriya tekhnologicheskaya sistemotekhnika [News of Tula state University. A series 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 method, 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 Vehicles: Organization and Coordination, Proc. of the 24th American Control Conference, Portland, OR., June 2005.
16. Tonetti S., Hehn M., Lupashin S., D'Andrea R. Distributed control of antenna array with formation 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.

Comments are closed.