ОРГАНИЗАЦИЯ ВЫЧИСЛЕНИЙ И ДИАГНОСТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ БОРТОВЫХ ВЫЧИСЛИТЕЛЕЙ РОБОТОТЕХНИЧЕСКИХ КОМПЛЕКСОВ
Аннотация
Целью исследования является повышение эффективности высокоуровнего проектиро-
вания робототехнических комплексов в части организации вычислений и диагностирования
программного обеспечения бортовых вычислителей. Рассматриваются три проблемы: на-
значения, планирования и диагностирования. Первая проблема, задача назначения, определе-
ние необходимых ресурсов и построения назначения программных модулей по процессорам
бортовых вычислителей согласно заданному критерию. В работе дана математическая по-
становка задачи, приведены алгоритмы, показано наличие областей эффективного домини-
рования алгоритмов в зависимости от выбранного критерия. Вторая проблема, задача пла-
нирования, определение последовательности выполнения заданий в многоканальных системах
согласно заданному критерию. Дана математическая постановка задачи, приведены алго-
ритмы и результаты их исследований. Особенностью рассматриваемых алгоритмов плани-
рования является использование единого подхода, а именно понятия отношения доминирова-
ния между процессорами и построение разрешимых классов систем. Третья проблема, диаг-
ностирование программного обеспечения. Сложность проблемы диагностирования вычисли-
тельных систем определяется не только их высокой размерностью, но и множественно-
стью причин возникновения нарушений. Источником нарушений вычислительного процессамогут быть как отказы аппаратуры, так и ошибки в организации вычислений допущенные
разработчиками. В работе используется иерархический подход, в этом случае компоненты
системы, связанные отношением включения, размещаются по уровням сложности так, что
модель компоненты более высокого уровня представляются композицией моделей более
низкого уровня. Для каждого уровня синтезируются свои средства диагностирования,
ориентированные на отказы информационных связей между компонентами предыдущего
уровня. В работе предлагается подход тестового диагностирования с использованием сете-
динамической модели, которая предполагает введение избыточности с целью упрощения
диагностического эксперимента и снижение трудоёмкости его подготовки. Данный подход
позволяет автоматически синтезировать средства диагностирования и обнаруживать на-
рушения в адресации информационных обменов при работе программного обеспечения робо-
тотехнических комплексов по прямому назначению. Апробация рассматриваемых алгорит-
мов проводилась с использованием разработанного автором программного обеспечения на
этапе проектирования бортовых комплексов в АО «Концерн «ЦНИИ «Электроприбор».
Литература
vstraivaemykh vychislitel'nykh sistem [Theoretical and methodological bases of high-level design
of embedded computing systems]. St. Petersburg: Universitet ITMO, 2010, 477 p.
2. Harris D., Harris S. Digital Design and Computer Architecture. 2nd ed. Morgan Kaufman,
2012.
3. Liu J.W.S. Real-Time Systems. Prentice Hall. NJ, 2000, 590 p.
4. Toporkov V.V. Modeli raspredelennykh vychisleniy [Distributed computing models]. Moscow:
Fizmatlit, 2004, 316 p.
5. Edward A. Lee and Sanjit A. Seshia. Introduction to Embedded Systems, A Cyber-Physical
Systems Approach. Second ed. MIT Press, 2017.
6. Kellerer H., Pferschy U., Pisinger U. Knapsack Problems. Springer, Berlin, Germany, 2004, 546 p.
7. Burkard R.E., Dell'Amico M. and Mortello S. Assignment problems. SIAM, Philadelphia, 2009.
8. Gonzalez T.F. Handbook of Approximation Algorithms and Metaheuristics. Second ed. Vol. 2:
Contemporary and Emerging Applications. Ed. Chapman, 2018. Available at: https://doi.org/
10.1201/9781351235426.
9. Jansen K. Parameterized Approximation Scheme for the Multiple Knapsack Problem, SIAM
Journal on Computing, 2010, Vol. 39, No. 4, pp. 1392-1412. Available at: https://doi.org/
10.1137/080731207.
10. Cacchiani V., Iori M., Locatelli A. et. al. Knapsack problems - An overview of recent advances. Part
II: Multiple, multidimensional, and quadratic knapsack problems, Computers & Operations Research,
2022, Vol. 143, pp. 105693. Available at: https://doi.org/10.1016/j.cor.2021.105693.
11. Gruzlikov A.M., Kolesov N.V., Skorodumov Yu.M., Tolmacheva M.V. Grafovyy podkhod k
naznacheniyu zadaniy v raspredelennykh sistemakh real'nogo vremeni [Graph approach to assignment
of tasks in distributed real-time systems], Izvestiya RAN. Teoriya i sistemy
upravleniya [Izvestiya of the RAS. Theory and control systems], 2014, No. 5, pp. 84-94.
12. Cottet F., Kaiser J., Mammeri Z. Scheduling in Real-Time Systems. John Wiley & Sons Ltd,
2002.
13. Brucker P., Knust S. Complex scheduling. Springer-Verlag, Berlin, Heidelberg, 2006.
14. Lazarev A.A. Teoriya raspisaniy. Metody i algoritmy [Schedule theory. Methods and algorithms].
Moscow: IPU RAN, 2019, 408 p.
15. Pinedo M.L. Scheduling. Theory: Algorithms and systems. Springer. Science, 2016, 670 p.
16. Gruzlikov A.M., Kolesov N.V., Skorodumov Yu.M., Tolmacheva M.V. Planirovanie zadaniy v
raspredelennykh sistemakh real'nogo vremeni [Task scheduling in distributed real-time systems],
Izvestiya RAN. Teoriya i sistemy upravleniya [Izvestiya of the RAS. Theory and control
systems], 2017, No. 2, pp. 67-76.
17. Gruzlikov A.M., Kolesov N.V. Ispol'zovanie razreshimykh klassov sistem real'nogo vremeni
dlya planirovaniya s minimizatsiey dzhittera [Using solvable classes of real-time systems for
planning with jitter minimization], Izvestiya RAN. Teoriya i sistemy upravleniya [Izvestiya of
the RAS. Theory and control systems], 2021, No. 6, pp. 43-51.
18. Taillard E. Benchmarks for Basic Scheduling Problems, Europ. J. Operational Research,
1993, Vol. 64, No. 2, pp. 278-285.
19. Zhang X., Guo P., Zhang H., Yao, J. Hybrid Particle Swarm Optimization Algorithm for Process
Planning, Mathematics, 2020, Vol. 8, pp. 1745. Available at: https://doi.org/10.3390/math8101745.
20. Isermann R. Fault Diagnosis Application. Heidelberg: Springer, 2011, 354 p.
21. Zaytoon J., Lafortune S. Overview of Fault Diagnosis Methods for Discrete Event Systems,
Annual Reviews in Control, 2013, Vol. 37, pp. 308-320.
22. Gruzlikov A.M., Kolesov N.V., Lukoyanov E.V. Testovoe diagnostirovanie narusheniy
adresatsii informatsionnykh obmenov v vychislitel'nykh sistemakh s ispol'zovaniem
parallel'noy modeli [Test diagnostics of addressing violations of information exchanges in
computing systems using a parallel model], Izvestiya RAN. Teoriya i sistemy upravleniya
[Izvestiya of the RAS. Theory and control systems], 2018, No. 3, pp. 76-89.
23. Gruzlikov A., Kolesov N., Lukoyanov E., and Tolmacheva M. Test-based diagnosis of distributed
computer system using a time-varying model, 10th IFAC Symposium on Fault Detection,
Supervision and Safety for Technical Processes, SAFEPROCESS – 2018.
24. Gruzlikov A.M., Kolesov N.V. Hierarchical model for testing a distributed computer system,
J. Korbicz et al. (eds.), Advances in Diagnostics of Processes and Systems, Studies in Systems,
Decision and Control 313, 14th International Conference on Diagnostics of Processes and
Systems (DPS), 2021.
