Метаслою: ідеї про застосування передбачення для оптимізації програмування та розподілу ресурсів в ОЗ
Технології
Вітаю, шановні читачі.
Зараз багато говорять про «великі дані», обробка яких повинна дати нам безліч нових можливостей у різних сферах. У цій публікації я хотів би трохи розповісти про одну свою вже давню роботу, яка, взагалі кажучи, передбачає корисну обробку деяких «великих даних», що природним чином виникають у процесі роботи кінцевої програми або навіть операційної системи. Якщо коротко, то мова йде, щонайменше, про часові профілі виконання коду і про його різні внутрішні характеристики/змінні - це можуть бути універсальні (наприклад, розміри запитуваних у ОС блоків пам'яті) або локальні (внутрішні змінні програми) значення. Я думаю, що безсумнівний інтерес представляють:
а) параметризація часових характеристик виконання окремих фрагментів коду, тобто пошук залежності часу його виконання від значень його внутрішніх змінних;
б) пошук логічних і наближених математичних залежностей одних внутрішніх змінних програми від інших.
Для чого потрібна перша ідея, напевно, цілком очевидно: для оптимізації виконання програми, тобто для проектування високоефективних алгоритмів. Наприклад, якщо наша програма містить декілька обчислювальних блоків, що виконуються в паралельному режимі, то для найбільш ефективного розподілу навантаження (балансування) може знадобитися вміння передбачати приблизний час виконання цих блоків. Це може бути дуже нетривіальним завданням, якщо робочі алгоритми блоків складні. Тоді нам допомогла б спеціальна підсистема, яка спершу старанно збирала б значення змінних і часу виконання блоків, потім намагалася б визначити наближену залежність часу від цих змінних і надати (динамічно побудувати) якусь оціночну функцію, користуючись якою, Ваша програма вже змогла б ретельно планувати і розподіляти навантаження для паралельної обробки.
Друга ідея може здатися дивною, але у неї є не менше двох корисних застосувань:
1. Однією з внутрішніх змінних може бути обсяг чергового виділеного блоку пам'яті. Якщо операційній системі потрібно, наприклад, передбачити розмір наступного вибраного блока і момент його виділення (для оптимізації розподілу пам'яті), то їй теж була б корисна підсистема, якою програма повідомляла б значення деяких змінних (на свій розсуд) X і розмір блоку N, а підсистема реєструвала б ще й час запиту T, після чого будувала б залежності N(X), T (X) і активно користувалася б ними для оптимізації виділення ресурсів, передбачення необхідності задіяння файлу підкачки, та в інших потрібних їй цілях. Аналогічно ОС може прогнозувати виділення і повернення багатьох інших ресурсів: дескрипторів файлів, графіки тощо.
2. Існують алгоритми, наприклад, з області численних методів (скажімо, інтегрування рівнянь аеродинаміки), в яких іноді дуже важливо отримати хоча б грубі приблизні результати (для початку), спираючись на які, можна запустити основні алгоритми, а вже потім, коли будуть готові точні результати, внести, наприклад, поправки. Тут і використовуються моделі залежностей змінних від змінних. Так, наприклад, можна реалізувати один з підходів до паралельного вирішення аеродинамічного завдання з декомпозицією робочої області по простору, блоками.
Отже, ми припустили, що заявлена ідея, щонайменше, небесполезна. Як можна її реалізувати?
Припустимо, що в ГР з'явиться підсистема передбачення, яка будт оперативно використовувати часто простоюючі ядра ЦПУ і, наприклад, відеокарти, для вирішення поставленого завдання, тобто для моделювання часових та інших характеристик виконання програм залежно від наданих ними для ОС даних про їх внутрішній стан (про значення важливих змінних у різні моменти часу).
Прототип
Свого часу я розробляв прототип такої підсистеми («метаслоя»), яка вирішувала поставлене завдання, будуючи складні моделі часу виконання і даних. Оскільки спочатку передбачалося, що моделі будуть дуже нетривіальними, я зрозумів, що далеко не завжди надані програмою дані будуть повні і бажано додатково мати деяку трасу її виконання (зі значеннями наданих метаслою змінних), за якою підсистема відновить деяку частину логіки виконання, визначивши частину відсутніх даних (наприклад, псевдолічильники внутрішніх вкладених циклів for/while/do). Це завдання вирішувалося аналізом великих таблиць значень змінних по ходу виконання, з пошуком циклів, переходів і умов циклів/переходів. Отримані змінні (допоміжні лічильники внутрішніх циклів у сукупності з безпосередньо представленими програмою змінними) використовувалися вже безпосередньо для пошуку функцій залежності часу/даних від цих змінних. Це робилося за допомогою методу групового обліку аргументів (МГУА).
Отримання метаслоєм даних оформлялося викликом його функцій, в які передавалися ідентифікатори «міток» програми і значення певних внутрішніх змінних. За цими даними метаслою будував поєднану модель переходів/функціональних залежностей у вигляді тіла спеціальної функції (на C++), компілював її зовнішнім компілятором в динамічну бібліотеку (DLL) і підключав до програми, яка, таким чином отримувала необхідні інструменти передбачення.
Такий підхід був випробуваний на декількох тестових завданнях:
- вибору найбільш оптимального числа потоків для паралельної обробки в циклі складних даних - використовувалися динамічно побудовані в метасле моделі часових характеристик;
- побудови алгоритмічної моделі «секретного» файлу даних, який не можна зберігати безпосередньо - використовувалася побудована в метасле модель даних, що читаються програмою з файлу.
Ув'язнення
Зараз розвиток цього прототипу-метаслоя закрито (я не маю на це часу і давно передав код іншій людині для її експериментів). Але ідея залишилася і я спробував її тут викласти, в надії, що це буде цікаво і коли-небудь її хто-небудь самостійно розвине в повноцінній формі (як підсистему ОС або корисну бібліотеку).