Миграция данных: различия между версиями

Специальный случай задачи миграции данных изучали Андерсон и др. [1] и Холл и др. [5]. Они предположили, что имеется граф переносов данных, вершины которого соответствуют дискам, а ориентированные ребра – каждой обозначенной операции перемещения (создание новых копий элементов данных не допускается). Вычисление графика перемещения данных в точности соответствует задаче раскраски ребер графа переноса. Теперь можно применить алгоритмы раскраски ребер мультиграфов для расчета графика миграции, поскольку каждый класс цветов представляет сопоставление в графе, которое можно спланировать одновременно. Вычисление решения с минимальным количеством этапов является NP-полной задачей, однако для раскраски ребер разработано несколько эффективных алгоритмов аппроксимации. Задача становится сложнее при наличии ограничений на пространство диска. Холл и др. [5] показали, что в предположении, что на каждом диске имеется один свободный элемент памяти, можно очень разработать эффективные аппроксимации с константным коэффициентом. Такие алгоритмы используют не более <math>4 \lceil \Delta / 4 \rceil \;</math> цветов и не более n/3 обходных вершин, либо не более <math>6 \lceil \Delta / 4 \rceil \;</math> цветов – без обходных вершин.