Application of prediction in parallel processing of chains of predicates in regular-logic expressions

Pekunov Vladimir Viktorovich Doctor of Technical Science Software Engineer, JSC "Informatika" 153000, Russia, Ivanovskaya oblast', g. Ivanovo, ul. Tashkentskaya, 90 pekunov@mail.ru Other publications by this author

Введение

Регулярно-логические выражения представляют собой расширение обычных регулярных Perl-выражений ^[1], которые дополняются логическими микровыражениями – цепочками предикатов, записанных в нотации некоторого обобщенного логического языка. Существует четыре вида таких цепочек: добавление, удаление, проверка и обучение. При этом выделяются следующие классы предикатов: а) стандартные табличные, осуществляющие работу с CSV-таблицей (четкий или нечеткий поиск, добавление или удаление текстовых или числовых значений), б) стандартные нейросетевые, поддерживающие создание и обучение нейросети, классификацию сетью текстовых или числовых значений, а также восстановление сетью некоторых отсутствующих классифицирующих признаков по известному классу, в) произвольные внешние предикаты, подключаемые из динамических библиотек. Микровыражения работают с именованными парами скобок (переменными) и могут иметь (для вида цепочки «проверка») логический результат, обозначающий успешность или неуспех (с откатом) попытки унификации микровыражения по аналогии с любым иным синтаксическим элементом регулярного выражения.

Регулярно-логические выражения используются в индуцирующих классах распознающих моделей в системе порождения и реконструкции программ PGEN++ ^{[2, 3]}. С их помощью реализуются элементы естественно-языкового интерфейса данной системы ^{[4, 5]}, а также макромодуль, решающий такую достаточно актуальную задачу как автоматическое распараллеливание C-программ в Cilk++ стиле ^[4].

Возможно возникновение ситуаций, при которых отдельные регулярно-логические выражения применяются неоднократно (например, при использовании сканирующей схемы индукции ^[4]), причем некоторые из предикатов, работающих с большими таблицами или решающих нейросетевые задачи, имеют высокую трудоемкость. В таком случае актуально повышение производительности обработки микровыражений (цепочек предикатов). Данная цель может быть отчасти достигнута применением параллельной обработки таких микровыражений, например, для случая системы с общей памятью ^[6], к которому относится большинство современных ЭВМ с многоядерными процессорами.

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

Существуют три основных подхода к предикции: а) имитационное моделирование; б) вывод и применение аналитических соотношений; в) применение полуэмпирических соотношений на базе некоторой известной статистики. Следует заметить, что имитационное моделирование ^{[7, 8, 9]} – достаточно тяжеловесный подход, затраты времени на который могут превысить эффект от распараллеливания. Особенно это может быть характерно для подхода с прямым моделированием, основанным на частичном фактическом исполнении исходного кода, упомянутого в работе ^[9]. Тот же самый эффект вполне вероятен для подхода ^[10], моделирующего логику работы кода (в соответствии с графом исполнения) с вычислением длительности счета отдельных фрагментов с помощью имитационной модели. Применение аналитических соотношений ^{[11, 12, 13]} – малозатратный подход, который может быть достаточно совершенным с точки зрения предсказания, но в нашем случае построение таких универсальных моделей времени для произвольных предикатов, в том числе имеющих дело с не всегда упорядоченными данными в CSV-таблицах и нейронными сетями, достаточно затруднительно. Решением может быть применение полуэмпирико-статистических соотношений. Однако такие известные решения ^{[7, 14]} опираются на достаточно простые линейные соотношения и требуют априорно большого числа замеров. Первое говорит об их потенциальной неточности, второе - об их потенциальной неэффективности по времени, что может быть особенно характерно для рассматриваемого нами общего случая, когда некоторые микровыражения имеют вычислительную трудоемкость, меньшую трудоемкости такой предикции. Достаточно интересен подход, изложенный в работах ^{[15, 16]}, основанный на сборе статистики, классифицируемой по значениям параметров решаемой задачи, и ее применении в линейных моделях времени исполнения. Схожий принцип использован в работе ^[17]. Одним из недостатков этого подхода является потенциально большой объем хранимой и используемой в вычислениях статистики. Более того, при таком подходе сомнения вызывают даже эффективность и гладкость параметризации решаемой нами задачи, учитывая, что большинство ее переменных связаны с поиском по полям постоянно модифицируемых CSV-таблиц. В таких условиях параметризация, скорее, неэффективна и можно полагаться лишь на часть последних по времени замеров, что говорит о возможности применения авторегрессионных моделей. Приходим к выводу, что для рассматриваемой задачи актуален поиск нового полуэмпирико-статистического подхода, отличающегося минимальным количеством замеров времени и применением потенциально более точных моделей (линейных авторегрессионных и квадратичных моделей времени исполнения). Такой подход предлагается в данной работе.

Формальная постановка задачи

Пусть имеется цепочка предикатов (микровыражение), которая многократно вычисляется в ходе унификации регулярно-логического выражения, причем время исполнения цепочки априорно неизвестно. Часть предикатов цепочки зависимы по данным от некоторых предыдущих ее предикатов. В последовательном режиме цепочка вычисляется строго слева направо. В параллельном режиме можно совместить во времени исполнение независимых друг от друга предикатов, при этом можно организовать обработку по типу «портфель задач» ^[18], где одна задача соответствует одному предикату A и имеет в качестве предусловия выполнения завершение обработки всех предикатов, от которых зависит A.

Остается решить задачу выбора режима исполнения. Предположим, что существует подход, позволяющий вычислить предполагаемое время исполнения в последовательном режиме t₁ и в параллельном режиме t_N. Тогда, при t₁ ≤ t_N выбирается последовательный режим, иначе – параллельный.

Предикция времени исполнения

Очевидным решением проблемы предикции, теоретически, могло бы стать, например, построение двух независимых экстраполяторов (первый – для t₁, второй – для t_N) по некоторой собираемой статистике, которую целесообразно периодически «сбрасывать» и собирать заново, для повышения валидности предикции. Однако такой подход не вполне эффективен, поскольку построение статистики для двух независимых экстраполяторов требует проведения двойной серии вычислений цепочки (одной в последовательном и одной в параллельном режиме), что, скорее всего, даст негативный эффект по времени исполнения.

Данная проблема разрешима:

1. После каждого очередного сброса статистики можно ограничиться лишь одной небольшой серией из K вычислений цепочки (попеременно, в последовательном и параллельном режимах – с вариацией, например, через 1÷2 шага), в результате чего имеем серию замеров (при единичном шаге вариации)

по которой можно интерполировать (в простейшем случае – путем линейной интерполяции) недостающие значения

и

.

2. Учитывая очевидное существование связи между t₁ и t_N, можно ограничиваться построением одного линейного предиктора только для t₁:

,

где S – номер замера времени, a – вектор коэффициентов предиктора, легко вычисляемый по серии из K предыдущих замеров, K > 3. Что же касается вычисления t_N, то можно ограничиться гипотетическим соотношением (полученным, исходя из известных соотношений ^[6]):

,

где α – доля работы, не поддающейся распараллеливанию, β – коэффициент накладных расходов на распараллеливание. Введя предположения о линейной зависимости α и β от t₁, получаем

,

где m, p, q – неизвестные коэффициенты, которые можно вычислить по серии из K замеров t₁ и t_N, воспользовавшись методом наименьших квадратов ^[19]. Важно отметить, что последнее соотношение также позволяет вычислить t₁ по известному значению t_N, найдя максимальный из вещественных корней соответствующего квадратного уравнения (если вещественных корней нет, можно, с известной погрешностью, брать предыдущее значение t₁).

3. После получения указанных в пункте 1 серий из K значений, можно вычислить (см. пункт 2) все неизвестные коэффициенты, связанные с предикцией: a, m, p, q.

4. После серии начальных замеров включаем рабочий режим (на некоторое количество P вычислений цепочки, после которого делаем сброс статистики с переходом к пункту 1), при котором для p-го вычисления цепочки (p > K) делается прогноз значения t_1,p, по которому вычисляется прогноз t_N,p. Если t_1,p ≤ t_N,p, то p-й запуск проходит в последовательном режиме (при этом получаем реальное значение t₁, по которому восстанавливаем предполагаемое t_N), иначе – в параллельном режиме (при этом получаем реальное значение t_N, по которому восстанавливаем предполагаемое t₁). Полученные значения t₁ и t_N сохраняются. На протяжении рабочего режима эти значения могут использоваться для периодического пересчета коэффициентов предиктора, а также для небольшой постоянной коррекции этих коэффициентов, например, с помощью одного шага градиентного метода ^[19], исходя из принципа минимизации соответствующего функционала квадратичной ошибки

` `

или

.

Апробация

Предложенная методика выбора режима исполнения была опробована на двух характерных примерах:

а) трудоемкой цепочке из 6 предикатов (как табличных, так и нейросетевых) с зависимостями, вызываемой 32 раза;

б) «легковесной» цепочке из 40 независимых табличных предикатов, вызываемой 64 раза.

Каждый пример исполнялся в двух сериях, в каждой из которых испытывались три режима исполнения (последовательный, параллельный, с предикцией). Полученные результаты сведены в таблицу.

Таблица. Результаты проведенных экспериментов (замеры времени, мс)

Из приведенных данных очевидно, что ни строго последовательный, ни строго параллельный режим исполнения не способны гарантировать наименьшее время исполнения во всех случаях (для трудоемких примеров, в которых доля полезной работы заметно выше затрат на распараллеливание, более выгоден параллельный режим, а для «легковесных», где ситуация обратная, – последовательный режим). Более того, было бы крайне затруднительно, если вообще возможно (в общем случае), априорно автоматически выбирать из этих режимов лучший, поскольку такой обоснованный выбор потребует применения достаточно громоздких схем, например, решения задач оптимизации или имитационного моделирования, в том числе с анализом реализующего обработку цепочек кода.

Поэтому, априорно близким к оптимальному решением должна стать предложенная схема с предикцией, которая пытается выбрать лучший режим динамически. Она, обычно, как очевидно из таблицы, не позволяет получить результаты с наименьшим временем (поскольку имеют место дополнительные временные затраты на собственно предикцию, также возможны ошибки в прогнозировании лучшего режима), однако стабильно дает приемлемое время счета, которое несколько не достигает лучшего варианта, но гарантированно лучше, чем худший вариант, который всегда может иметь место при априорном неправильном выборе одного из «чистых» режимов. Это позволяет говорить о достаточной обоснованности предложенных в данной работе подходов.

Выводы

Итак, в данной работе предложена новая методика предикции временных затрат при обработке цепочек предикатов в регулярно-логических выражениях. Данная методика позволяет оперативно выбрать близкий к оптимальному режим исполнения (последовательный или параллельный), который гарантированно дает время исполнения:

а) лучше, чем в худшем случае, который весьма вероятен при априорном выборе любого из «чистых» режимов исполнения;

б) несколько хуже, чем в априорно неизвестном лучшем случае.

Ключевыми новыми элементами предложенной методики являются:

а) частичное восстановление недостающих статистичеких данных (по простым аналитическим соотношениям, без проведения дублирующих экспериментов);

б) использование линейного предиктора времени исполнения последовательного режима и квадратичной зависимости для времени исполнения параллельного режима;

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

Серия экспериментов, проведенная для цепочек предикатов различной трудоемкости, подтвердила заявленные оптимальные свойства методики: полученные результаты стабильно лучше худшего случая, хотя и не достигают результатов априорно неизвестного лучшего случая.