В статье излагаются результаты исследования, направленного на расширение теоретической базы в области вычислений в реальном времени. К числу рассматриваемых вопросов относятся: определение показателей вычислительной сложности в реальном времени, методология их количественной оценки, выявление способов достижения вычислимости алгоритмов в реальном времени, формализация подходов к оптимальной технической реализации вычислительных систем реального времени. Проведенные исследования опираются на существующие представления теории алгоритмов и теории вычислений, в том числе, вычислений в реальном времени. К числу значимых новых научных результатов проведенного исследования относятся: введение, наряду с известными показателями временной и пространственной вычислительной сложности, дополнительного показателя конфигурационной вычислительной сложности, необходимого для оценки вычислительной сложности в реальном времени; констатация возможности управления временной, пространственной и конфигурационной сложностью в рамках заданного функционала алгоритма исключительно за счет изменения числа потоков исполнения вычислений; теоретическое обоснование возможности снижения времени выполнения алгоритма конфигурирования с экспоненциального до полиномиального или даже линейного за счет конденсации исходного графа алгоритма с образованием из сильно связанных компонент совокупности функций-акторов и получения в результате ациклического ориентированного графа, топологическая сортировка которого выполнима за линейное время; определение подходов к оптимальной технической реализации алгоритма с заданной конфигурацией, в том числе, в виде интегральной схемы с разводкой, оптимизируемой на основе решения прямоугольной задачи Штейнера.
The article presents the results of a study aimed at expanding the theoretical basis in the field of real-time computing. The issues considered include: defining indicators of computational complexity in real time, a methodology for their quantitative assessment, identifying ways to achieve the computability of algorithms in real time, and formalizing approaches to the optimal technical implementation of real-time computing systems. The research is based on existing concepts in algorithm theory and computation theory, including real-time computation. Significant new scientific results of the research include: the introduction, along with the known indicators of temporal and spatial computational complexity, of an additional indicator of configuration computational complexity, necessary for assessing computational complexity in real time; the confirmation of the possibility of controlling temporal, spatial, and configuration complexity within the framework of a given algorithm functional solely by changing the number of computation execution threads; theoretical justification of the possibility of reducing the execution time of the configuration algorithm from exponential to polynomial or even linear by condensing the initial graph of the algorithm with the formation of strongly connected components of a set of actor functions and obtaining as a result an acyclic directed graph, whose topological sorting can be performed in linear time; determination of approaches to the optimal technical implementation of the algorithm with a given configuration, including in the form of an integrated circuit with wiring optimized based on the solution of Steiner's rectangular problem.
The authors declare that there are no conflicts of interest present.