Моделювання DAG-структур робочих навантажень

UKR: Запропоновано конструкційну модель породження DAG-структур робочих навантажень для тестування планувальників кластерів Kubernetes. Модель базується на апараті узагальненого конструктора та спеціалізує його компоненти для предметної області направлених ациклічних графів задач. Формалізовано механізм підстановки як частковий випадок контекстно-вільної графової граматики із заміною вузлів з чотирма типами правил: атрибутування, підстановка підграфа, реплікація та алгоритмічна генерація. Введено систему атрибутів, що розширює ідеї атрибутних граматик Кнута на графові структури. Доведено збереження ацикличності при кожній підстановці та завершимість процесу породження. Конструктор реалізовано мовою Python з декларативним YAML DSL. Експериментально підтверджено практичну придатність моделі на множині з 100 породжених DAG.

ENG: A constructive model for generating DAG structures of workloads for testing Kubernetes cluster schedulers is proposed. The model is based on the generalized constructor formalism and specializes its components for the domain of directed acyclic task graphs. The substitution mechanism is formalized as a special case of node replacement graph grammar with four rule types: attribute assignment, subgraph substitution, replication, and algorithmic generation. An attribute system extending Knuth’s attribute grammars to graph structures is introduced. Preservation of acyclicity under each substitution and termination of the generation process are formally proved. The constructor is implemented in Python with a declarative YAML DSL. Experimental validation on a set of 100 generated DAGs confirms the practical applicability of the model.