Pull to refresh

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

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

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

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

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

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

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

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

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

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

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

Прототип


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

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

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

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

Заключение


Сейчас развитие этого прототипа-метаслоя закрыто (я не имею на это времени и давно передал код другому человеку для его экспериментов). Но идея осталась и я попробовал ее здесь изложить, в надежде, что это будет интересно и когда-нибудь ее кто-нибудь самостоятельно разовьет в полноценной форме (как подсистему ОС или полезную библиотеку).
Tags:Программированиеоперационные системыпредсказание
Hubs: Programming Algorithms Concurrent computing
Total votes 5: ↑5 and ↓0+5
Views1.9K

Popular right now