Аннотация.

Дается анализ проблемы планирования периодической обработки цифровой информации в устройствах с перестраиваемой структурой. Основное внимание уделяется разработке формализованных моделей вычислительного процесса с совмещением циклов обработки при ограничениях на число исполнительных ресурсов, исследованию эффективности предложенных алгоритмов. Статья, в силу большого объема, разбита на две части. В первой части дается обзор работ в области построения периодических расписаний, вводится модель и алгоритм совмещения циклов многократного выполнения алгоритма. Во второй части предлагается алгоритм оптимизации закрепления исполнительных блоков за фазами алгоритма, дается расширение задачи на случай комплексов алгоритмов с различными видами параллелизма, рассматриваются вопросы оптимизации структуры вычислителя.

Ключевые слова:

периодические расписания, оптимизация совмещения циклов, процессорный элемент, специализированное вычислительное устройство.

Стр.  62-76.

Полная версия статьи в формате pdf. 

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- 2014-5.pdf (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.