Метаслой: идеи о применении предсказания для оптимизации программирования и распределения ресурсов в ОС

    Здравствуйте, уважаемые читатели.

    Сейчас много говорят о «больших данных», обработка которых должна дать нам множество новых возможностей в самых различных сферах. В этой публикации я хотел бы немного рассказать об одной своей уже давней работе, которая, вообще говоря, предполагает полезную обработку некоторых «больших данных», естественным образом возникающих в процессе работы конечной программы или даже операционной системы. Если кратко, то речь идет, по меньшей мере, о временных профилях выполнения кода и о его различных внутренних характеристиках/переменных — это могут быть универсальные (например, размеры запрашиваемых у ОС блоков памяти) или локальные (внутренние переменные программы) значения. Я думаю, что несомненный интерес представляют:

    а) параметризация временных характеристик выполнения отдельных фрагментов кода, то есть поиск зависимости времени его выполнения от значений его внутренних переменных;

    б) поиск логических и приближенных математических зависимостей одних внутренних переменных программы от других.

    Для чего нужна первая идея, наверно, вполне очевидно: для оптимизации исполнения программы, то есть для проектирования высокоэффективных алгоритмов. Например, если наша программа содержит несколько вычислительных блоков, выполняемых в параллельном режиме, то для наиболее эффективного распределения нагрузки (балансировки) может потребоваться умение предсказывать приблизительное время исполнения этих блоков. Это может быть очень нетривиальной задачей, если рабочие алгоритмы блоков сложны. Тогда нам помогла бы специальная подсистема, которая сперва старательно собирала бы значения переменных и времени исполнения блоков, затем пыталась бы определить приближенную зависимость времени от этих переменных и предоставить (динамически построить) некую оценочную функцию, пользуясь которой, Ваша программа уже смогла бы тщательно планировать и распределять нагрузку для параллельной обработки.

    Вторая идея может показаться странной, но у нее есть не менее двух полезных применений:

    1. Одной из внутренних переменных может быть объем очередного выделяемого блока памяти. Если операционной системе требуется, например, предсказать размер следующего выделяемого программе блока и момент его выделения (для оптимизации распределения памяти), то ей тоже была бы полезна подсистема, которой программа сообщала бы значения некоторых переменных (на свое усмотрение) X и размер блока N, а подсистема регистрировала бы еще и время запроса T, после чего строила бы зависимости N(X), T(X) и активно пользовалась бы ими для оптимизации выделения ресурсов, предсказания необходимости задействования файла подкачки, и в прочих нужных ей целях. Аналогично ОС может прогнозировать выделение и возврат многих других ресурсов: дескрипторов файлов, графики и т.п.

    2. Существуют алгоритмы, например, из области численных методов (скажем, интегрирование уравнений аэродинамики), в которых иногда очень важно получить хотя бы грубые приблизительные результаты (для начала), опираясь на которые, можно запустить основные алгоритмы, а уже потом, когда будут готовы точные результаты, внести, например, поправки. Здесь и используются модели зависимостей переменных от переменных. Так, например, можно реализовать один из подходов к параллельному решению аэродинамической задачи с декомпозицией рабочей области по пространству, блоками.

    Итак, мы предположили, что заявленная идея, по меньшей мере, небесполезна. Как можно ее реализовать?

    Предположим, что в ОС появится подсистема предсказания, которая будт оперативно использовать часто простаивающие ядра ЦПУ и, например, видеокарты, для решения поставленной задачи, то есть для моделирования временных и прочих характеристик исполнения программ в зависимости от предоставленных ими для ОС данных об их внутреннем состоянии (о значениях важных переменных в различные моменты времени).

    Прототип


    В свое время я разрабатывал прототип такой подсистемы («метаслоя»), которая решала поставленную задачу, строя сложные модели времени исполнения и данных. Поскольку изначально предполагалось, что модели будут очень нетривиальными, я понял, что далеко не всегда предоставляемые программой данные будут полны и желательно дополнительно иметь некоторую трассу ее исполнения (со значениями предоставленных метаслою переменных), по которой подсистема восстановит некоторую часть логики исполнения, определив часть недостающих данных (например, псевдосчетчики внутренних вложенных циклов for/while/do). Эта задача решалась анализом больших таблиц значений переменных по ходу исполнения, с поиском циклов, переходов и условий циклов/переходов. Полученные переменные (вспомогательные счетчики внутренних циклов в совокупности с непосредственно представленными программой переменными) использовались уже непосредственно для поиска функций зависимости времени/данных от этих переменных. Это делалось с помощью метода группового учета аргументов (МГУА).

    Получение метаслоем данных оформлялось вызовом его функций, в которые передавались идентификаторы «меток» программы и значения определенных внутренних переменных. По этим данным метаслой строил совмещенную модель переходов/функциональных зависимостей в виде тела специальной функции (на C++), компилировал ее внешним компилятором в динамическую библиотеку (DLL) и подключал к программе, которая, таким образом получала требуемые инструменты предсказания.

    Такой подход был опробован на нескольких тестовых задачах:

    • выбора наиболее оптимального числа потоков для параллельной обработки в цикле сложных данных — использовались динамически построенные в метаслое модели временных характеристик;
    • построения алгоритмической модели «секретного» файла данных, который нельзя хранить непосредственно — использовалась построенная в метаслое модель данных, читаемых программой из файла.

    Заключение


    Сейчас развитие этого прототипа-метаслоя закрыто (я не имею на это времени и давно передал код другому человеку для его экспериментов). Но идея осталась и я попробовал ее здесь изложить, в надежде, что это будет интересно и когда-нибудь ее кто-нибудь самостоятельно разовьет в полноценной форме (как подсистему ОС или полезную библиотеку).
    Поделиться публикацией

    Комментарии 10

      +1
      выбора наиболее оптимального числа потоков для параллельной обработки в цикле сложных данных — использовались динамически построенные в метаслое модели временных характеристик;

      Зачем проделывать такую работу, когда можно было получить это число эмпирически?

        0
        Особенно если учесть, что создатель задачи априори обладает существенно большей информацией о её потребностях. В том числе и о будущих, которые зачастую невозможно предсказать по текущим. Да и задача сама вполне способна (при правильном подходе) динамически подстраивать свои потребности под доступные ресурсы. Единственное, что для этого требуется — возможность простого получения реалистичной информации об этих самых ресурсах (без учёта эмуляций и виртуализаций)
          0
          Если программа будет работать только на одной конкретной ЭВМ, то, конечно, можно и эмпирически. Но если ЭВМ заранее неизвестна, то все уже не так просто. Но это даже не главное. Объём вычислений в цикле может очень сильно зависеть от входных данных, соответственно и оптимальное число потоков может от них сильно зависеть. Если входные данные постоянно меняются, то единого эмпирического оптимального числа потоков просто нет. Вот тогда и может пригодиться построенная модель.
            0
            А не проще взять несколько репрезентативных наборов данных разного объема и прогнать программу на 2, 4, 8, 16, 32, 64,… потоках. Построить [график](https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BA%D0%BE%D0%BD_%D0%90%D0%BC%D0%B4%D0%B0%D0%BB%D0%B0#/media/File:AmdahlsLaw.svg) и выбрать подходящее значение.
            Тут мы можем упереться в количество ядер, закон Амдала.
              0
              Если таких наборов данных — один или два, то можно и по графикам. А если их пять-десять-больше, то я предпочту что-то вроде того, что предлагается в публикации. Потому в начале и было написано про потенциально «большие данные», где подход может оправдать себя.
                +1
                А если их пять-десять-больше

                Их все равно придется делать, что бы протестировать код.


                про потенциально «большие данные», где подход может оправдать себя.

                А там это нужно? Люди собирают кластер, с безумно большим количеством ресурсов, и не парятся.

            0
            Оптимальное число потоков равно числу ядер. Если же нет, то нужно оптимизировать код, а не число потоков.
              0
              Дело не в оптимизации кода, а в свойствах реализуемого алгоритма. Там есть определенная доля нераспараллеливаемой работы, которая просто неподвластна оптимизации. Если эта доля растёт с увеличением числа потоков, то на определенном этапе попытка увеличить число потоков приведёт только к замедлению работы программы. В-общем, один землекоп копает яму за час, два землекопа — за полчаса, а сто землекопов только будут мешать друг другу и проработают два часа (если вообще не передерутся).
            0
            Представляю такую ОС будущего.

            Пришёл с работы, поиграл часок в пасьянс, потратил 0,2 кВт⋅ч электроэнергии, лёг спать.
            А система всю ночь обсчитывает модели и трассы этого пасьянса, задействуя все (неиспользуемые ночью) ядра и видеокарты, и к утру нажгёт 5 кВт⋅ч.
              0
              :) Да, конечно, до такого лучше не доводить. А если серьезно, то для такой ОС целесообразно ввести простое ранжирование приложений по требуемому уровню обслуживания (пасьянсу — нулевой).

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.