Из приведенных данных очевидно, что ни строго последовательный, ни строго параллельный режим исполнения не способны гарантировать наименьшее время исполнения во всех случаях (для трудоемких примеров, в которых доля полезной работы заметно выше затрат на распараллеливание, более выгоден параллельный режим, а для «легковесных», где ситуация обратная, - последовательный режим). Более того, было бы крайне затруднительно, если вообще возможно (в общем случае), априорно автоматически выбирать из этих режимов лучший, поскольку такой обоснованный выбор потребует применения достаточно громоздких схем, например, решения задач оптимизации или имитационного моделирования, в том числе с анализом реализующего обработку цепочек кода.
Поэтому, априорно близким к оптимальному решением должна стать предложенная схема с предикцией, которая пытается выбрать лучший режим динамически. Она, обычно, как очевидно из таблицы, не позволяет получить результаты с наименьшим временем (поскольку имеют место дополнительные временные затраты на собственно предикцию, также возможны ошибки в прогнозировании лучшего режима), однако стабильно дает приемлемое время счета, которое несколько не достигает лучшего варианта, но гарантированно лучше, чем худший вариант, который всегда может иметь место при априорном неправильном выборе одного из «чистых» режимов. Это позволяет говорить о достаточной обоснованности предложенных в данной работе подходов.
Выводы
Итак, в данной работе предложена новая методика предикции временных затрат при обработке цепочек предикатов в регулярно-логических выражениях. Данная методика позволяет оперативно выбрать близкий к оптимальному режим исполнения (последовательный или параллельный), который гарантированно дает время исполнения:
а) лучше, чем в худшем случае, который весьма вероятен при априорном выборе любого из «чистых» режимов исполнения;
б) несколько хуже, чем в априорно неизвестном лучшем случае.
Ключевыми новыми элементами предложенной методики являются:
а) частичное восстановление недостающих статистичеких данных (по простым аналитическим соотношениям, без проведения дублирующих экспериментов) ;
б) использование линейного предиктора времени исполнения последовательного режима и квадратичной зависимости для времени исполнения параллельного режима;
в) применение периодической подстройки коэффициентов указанных предикционных выражений путем выполнения одного шага численного решения задачи минимизации квадратичной ошибки.
Серия экспериментов, проведенная для цепочек предикатов различной трудоемкости, подтвердила заявленные оптимальные свойства методики: полученные результаты стабильно лучше худшего случая, хотя и не достигают результатов априорно неизвестного лучшего случая.
Библиография
1. Perlre: [https: //perldoc. perl. org/perlre. html].
2. Пекунов В. В. Новые методы параллельного моделирования распространения загрязнений в окрестности промышленных и муниципальных объектов // Дис. докт. тех. наук. -Иваново, 2009. -274 с.
3. Пекунов В. В. Автоматизация параллельного программирования при моделировании многофазных сред. Оптимальное распараллеливание // Автоматика и телемеханика. -2008. -№7. -С. 170-180.
4. Пекунов В. В. Автоматическое распараллеливание C-программ в Cilk++ стиле. Применение индукции объектно-событийных моделей. -LAP LAMBERT Academic Publishing, 2018. -105 с.
5. Pekunov V. V. An automatic generation of program and a verification of obtained program using reconstruction of model or algorithm // The scientific heritage. -2018. -№26 (26). -Vol. 2. -P. 54-58.
6. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. - СПб. : БХВ-Петербург, 2002. - 608 с.
7. Lei Hu, Ian Gorton. Performance Evaluation for Parallel Systems: A Survey // Technical Report No UNSW-CSE-TR-9707, Department of Computer Systems, School of Computer Science and Engineering, University of NSW, Oct. 1997. - 56 pp.
8. Глинский Б. М., Марченко М. А., Михайленко Б. Г. и др. Отображения параллельных алгоритмов для суперкомпьютеров экзафлопсной производительности на основе имитационного моделирования // Информационные технологии и вычислительные системы. - 2013. - №4. - С. 3-14.
9. Падарян В. А. Оценка времени работы параллельной программы с помощью интерпретатора среды ParJava. - М., 2005. - 38 с. - (Препринт/ Институт Системного Программирования РАН; № 6).
10. Adve V. S., Vernon M. K. Parallel program performance prediction using deterministic task graph analysis // ACM Transactions on Computer Systems (TOCS). - 2004. - Vol. 22. - Iss. 1. - P. 94-136.
11. Muller, O., Baghdadi, A., Jйzйquel, M.. Parallelism Efficiency in Convolutional Turbo Decoding // EURASIP J. Adv. Signal Process. (2010) 2010: 927920. https: //doi. org/10. 1155/2010/927920.
12. Кудряшова Е. С. Модели параллельных систем и их применение для трассировки и расчета времени выполнения параллельных вычислительных процессов // Автореф. дис. канд. физ. -мат. наук. - Комсомольск-на-Амуре, 2015. - 18 с.
13. Дунаев А. В., Ларченко А. В., Бухановский А. В. Моделирование параллельных вычислительных процессов в среде Грид на примере Intel Grid Programming Environment // ПаВТ-2008 - сборник трудов (электронное издание), 2008. - С. 383-389.
14. Tsilker B., Orlov S. Computing parallelization efficiency estimation in the intelligent transportation systems // Proceedings of the 10th International Conference “Reliability and Statistics in Transportation and Communication” (RelStat'10), 20-23 October 2010, Riga, Latvia, p. 218-224.
15. Monteil T. Coupling profile and historical methods to predict execution time of parallel applications. Parallel and Cloud Computing, Dr. Pokkuluri Kiran Sree, 2013, 2 (3), pp. 81-89.
16. Miegemolle B., Monteil T. Hybrid Method to Predict Execution Time of Parallel Applications // Proceedings of the 2008 International Conference on Scientific Computing, CSC 2008, July 14-17, 2008, Las Vegas.
17. Iverson M. A., Ozguner F., Potter L. Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment // IEEE Trans. Comput. - 1999. - Vol. 48 (12), P. 1374-1379.