Abstract.

The analysis of a problem of planning of periodic digital information processing in devices with tunable structure is given. The main attention is paid to development of the formalized models of calculating process with combination of operation cycles with restrictions on number of the executive resources, to a research of offered algorithms efficiency. Article, owing to large volume, is broken into two parts. In the first part the review of operations in plot area of the work in constructing periodic schedules is given, the model and an algorithm of combination of cycles of repeated algorithm execution is entered. In the second part the algorithm of optimization of fixing of the executive units to algorithm phases is offered, extension of the task on a case of complexes of the algorithms responding to different types of parallelism is given questions of calculator structure optimization are considered.

Keywords:

periodic schedules, optimization of combination of cycles, processor element, specialized computing device.

PP. 62-76.

REFERENCES

1. Artamonov, E.I., Sh-M.A.Ismailov, O.G.Kokaev, and V.M. Khachumov, 1993. Specializirovannye algoritmy i ustrojstva obrabotki massivov dannyh [Specialized algorithms and devices for processing array data]. Mahachkala: Dagestanskoe knizhnoe izdatel'stvo [Makhachkala, Dagestan book publishing house]. 304 p.
2. Gilman, A.L., and Ja.G. Hait, 1970. Raspisanija v zadachah organizacii periodicheskoj obrabotki informacii, 1970. [Schedules the tasks of the organization of the periodic information processing]. Izv. AN SSSR. Tehnicheskaja kibernetika [Proceedings of the USSR Academy of Sciences. Technical Cybernetics]. 3:125-130.
3. Bejlin, A.M., and A.L. Gilman. 1973. Planirovanie periodicheskoj obrabotki informacii v sisteme, rabotajushhej bez preryvanij [The scheduling information processing in the system running without interruption]. Izv. AN SSSR. Tehnicheskaja kibernetika [Proceedings of the USSR Academy of Sciences. Technical Cybernetics]. 3:113-116.
4. Leung, J.Y-T., and M.L. Merril. 1980. A note on preemptive scheduling of periodic real-time tasks. Information processing letters. 11(3):115–118.
5. Lui, С.L., and J.W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the Association for Computing Machinery. 20(1):46–61. Available at:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.5086&rep=rep1&type=pdf (accessed February 15, 2017).
6. Lawler, E.L., and C.U. Martel. 1981. Scheduling periodically occurring tasks on multiple processors. Information processing letters. 12(1):9–12. Available at: http://www.sciencedirect.com/science/article/pii/0020019081900661 (accessed February 15, 2017).
7. Lawler, E.L., and J. Labetoulle. 1978. On preemptive scheduling of unrelated parallel processors by linear programming. Journal of the ACM. 25(4):612–619. Available at: http://www.columbia.edu/~cs2035/courses/ieor6400.F07/ll.pdf (accessed February 15, 2017).
8. Gonzalez, T., and S. Sahni. 1976. Open shop scheduling to minimize finish time. Journal of the ACM (JACM). 23(4):665–679. Available at:: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394.1507&rep=rep1&type=pdf (accessed February 15, 2017).
9. Shurajc, Ju.M. 1979. Optimizacija issledovanija resursov pri mnogokratnom vypolnenii kompleksa rabot. Dis... kand.tehn.nauk. [Optimization studies with multiple resources performing the work. Thesis of candidate of technical Sciences]. Moscow, 166 p.
10. Gudman, S., and S. Hidetniemi. 1981. Vvedenie v razrabotku i analiz algoritmov [Introduction to the design and analysis of algorithms]. Moscow: Mir, 366 p.
11. Konvej, R.V., V.A. Maksvell, and L.B. Miller. 1975. Teorija raspisanij [The scheduling theory]. Moscow: Nauka, 360 p.
12. Ajzenshtat, B.C. 1963. Sovmeshhenie primitivnyh ciklicheskih processov [The combination of primitive cyclic processes]// Doklady AN BSSR [Reports of Academy of Sciences of the Byelorussian SSR]. VII. 3: 148-151.
13. Ajzenshtat, B.C. 1963. Mnogooperatornye ciklicheskie process [Multi-statement cyclic processes]. Doklady AN BSSR [Reports of Academy of Sciences of the Byelorussian SSR]. VII. 4: 224-227.
14. Metelskij, A.S. 1963. O nekotoryh periodicheskih processah [Some periodic processes]. Doklady AN BSSR [Reports of Academy of Sciences of the Byelorussian SSR]. VII. 9: 584-587.
15. Metelskij, A.S. 1963. K sisteme periodicheskih processov [To the system of periodic processes]. Doklady AN BSSR [Reports of Academy of Sciences of the Byelorussian SSR]. VII. 11: 724-728.
16. Metelskij, A.S. 1965. Periodicheskie processy [Periodic processes]. Doklady AN BSSR [Reports of Academy of Sciences of the Byelorussian SSR]. IX. 12: 788-790.
17. Bronshtejn, I.I., Je. A., Trahtengerc, and Ju. M. Shurajc. 1975. Opredelenie optimal'nogo plana realizacii algoritma na mnogoprocessornoj vychislitel'noj mashine [Determining the optimal plan for the implementation of the algorithm on a multiprocessor computer]. Avtomatika i telemehanika [Automation and remote control]. 4:122-127.
18. Shurajc, Ju.M. 1977. Optimalnoe raspredelenie resursov pri mnogokratnom vypolnenii kompleksa rabot [Optimal resource allocation in case of multiple execution of complex of works]. Aktualnye voprosy teorii i praktiki upravlenija [Relevant issues of the theory and practice of control]. Moscow: Nauka: 122-125.
19. Dzhonson, S.M. 1966. Optimal'nye dvuh- i trehoperacionnye kalendarnye plany proizvodstva s uchetom podgotovitel'nozakljuchitel'nogo vremeni. Kalendarnoe planirovanie [Optimal two - and trihomonatidne calendar plans of production, given the preparatory-final time. Scheduling]. Moscow: Progress: 33-41.
20. Layland, J.W. 1975. Development of real-time hardware/software systems. The deep space network progress report. 42-28:57–66.
21. Tanaev, B.C., and V.B. Shkurba. 1975. Vvedenie v teoriju raspisanij [Introduction to scheduling theory]. Moscow: Nauka. 256 p.
22. Fedorovich, O.E., and V.I. Gorlova. 1980. Perechislenie vozmozhnyh variantov sostava modul'nyh struktur s uchetom faz obrabotki informacii. Teorija avtomatizirovannogo proektirovanija [Enumeration of the possible variants of modular structures, taking into account the phases of information processing. Theory of computer-aided design]. Mezhvuz. temat. sbornik nauchn. Trudov [Interuniversity theme. collection of scientific works]. Kharkov. 2:92-97.
23. Reiter, R. 1968. Sheduling parallel computations. Journal of the Association for Computing Machinery. 15(4):590–599.
24. Solih, R. 1973. Zadacha kalendarnogo planirovanija dlja ciklicheski povtorjajushhegosja proizvodstva [Task scheduling for cyclic production]. Zhurnal vychislitel'noj matematiki i matematicheskoj fiziki [Computational mathematics and mathematical physics]. 13(2):326-342.
25. Tret'jakov, A. 2012. Avtomatizacija postroenija raspisanij dlja periodicheskih sistem real'nogo vremeni [Automation of scheduling for periodic real-time systems]. Trudy Instituta sistemnogo programmirovanija RAN [Proceedings of Institute of system programming of RAS]. 22:375-400. Available at:
http://www.ispras.ru/proceedings/docs/2012/22/isp_22_2012_375.pdf (accessed February 15, 2017).
26. Brucker, P., and T. Kampmeyer. 2005. Tabu search algorithms for cyclic machine scheduling problems. Journal of Scheduling. 8:303–322.
27. Brucker, P., and T. Kampmeyer. 2008. A general model for cyclic machine scheduling problems. Discrete Applied Mathematics. 156(13):2561–2572.
28. Furugjan, M.G. 2013. Postroenie periodicheskih raspisanij v mnogoprocessornyh sistemah real'nogo vremeni [The construction of periodic schedules in multiprocessor real-time automation]. Materialy 7 mezhdunarodnoj konferencii «Upravlenie razvitiem krupnomasshtabnyh sistem» [The materials of the 7 international conference "Managing the development of large-scale systems"]. IPU RAN, Moskva [Institute of control problems of RAS, Moscow]. 444-446.
29. Furugjan, M.G. 2000. Postroenie periodicheskih raspisanij v mnogoprocessornyh ASU realnogo vremeni [The construction of periodic schedules in multiprocessor real-time automation]. Avtomatika i telemehanika [Automation and remote control]. 9:169-172. Available at: http://www.mathnet.ru/links/8e4787617aa0bc93619b6f743ac90985/at364.pdf (accessed February
15, 2017).
30. Hanzalek, Z., and C. Hanen. 2015. The impact of core precedences in a cyclic RCPSP with precedence delays. Journal of Scheduling. 18(3):275–284. Available at: http://link.springer.com/article/10.1007/s10951-014-0399-4 (accessed February 15, 2017).
31. Dkhil, A., Do X.K., P. Dubrulle, S. Louise, and C. Rochange. 2014. Self-timed periodic scheduling for cyclo-static dataflow model. In: Workshop on Architecture, Languages, Compilation and Hardware support for Emerging ManYcore systems. ALCHEMY 2014, 10 June 2014 – 12 June 2014 (Cairns, Australia). 18 p. Available at: http://oatao.univtoulouse. fr/12956/1/Dkhil_12956.pdf (accessed February 15, 2017).
32. Tendulkar, P., P. Poplavko, and O. Maler. 2014. Strictly periodic scheduling of acyclic synchronous dataflow graphs using SMT solvers. Verimag Research Report no TR-2014-5 01-May-2014. Available at: http://www-verimag.imag.fr/TR/TR (accessed February 15, 2017).
33. Periodic Scheduling – CMSC 451: Design and Analysis of Algorithms Spring 2015. Available at:
http://www.cs.umd.edu/class/spring2015/cmsc451/periodicsch.pdf (accessed February 15, 2017).
34. Khachumov, V.M. 2003. Periodicheskie raspisanija s sovmeshheniem ciklov obrabotki dannyh [Periodic schedules with combining cycles of data processing]. Trudy Pervoj Vserossijskoj nauchnoj konferencii «Metody i sredstva obrabotki informacii» [Proceedings of the First all-Russian scientific conference "Methods and means of information processing"]. Moscow: MGU. 522-527.
35. Khachumov, V.M., and M.G. Jumagulov. 1983. Metod analiza i sinteza optimal'nyh struktur vychislitel'nyh ustrojstv dlja sistem upravlenija [The method of analysis and optimal synthesis of structures of computing devices for control systems].
V sb.: Avtomatizacija proektirovanija i konstruirovanija. Tezisy dokladov II Vsesojuznogo soveshhanija. Chast' 2 [In proceedings: automation of design and construction. Abstracts of the II all-Union meeting. Part 2]. Moscow: Institute of control problems, RAS. 106-109.
36. Khachumov, V.M., and M.G. Jumagulov. 1984. Ob optimizacii metoda sovmeshhenija vychislitel'nyh processov v specializirovannyh ustrojstvah [About optimization of the method of combining computational processes in specialized devices].
V kn.: Upravlenie v slozhnyh nelinejnyh sistemah [In the book: Management in complex nonlinear systems]. Moscow: Nauka. 148-152.
37. Khachumov, V.M. 2009. Modeli konvejernogo medicinskogo tehnologicheskogo processa [Conveyor model of medical technological process]. Iskusstvennyj intellekt i prinjatie reshenij [Artificial intelligence and decision making]. 3: 25-32.