Векторизация итерационных вычислительных процессов и оценки временного ускорения

Ц е л и . Решается задача эффективной организации выполнения последовательных вычислительных процессов в векторном режиме с учетом возможностей современных высокопроизводительных векторно-конвейерных ЭВМ. Актуальность рассматриваемой задачи обусловлена тем, что такие процессы, возникающие при циклической обработке данных и в итерационных алгоритмах, являются наиболее сложными для распараллеливания. При решении задачи ставились три цели: построение математической модели,  учитывающей основные  архитектурные  и  вычислительные особенности  современных  векторно-конвейерных ЭВМ; расчет оптимального суммарного времени выполнения векторных операций; оценка временного выигрыша по сравнению с последовательным режимом обработки данных.

М е т о д ы . Для реализации поставленных целей и доказательства основных и вспомогательных утверждений применялся оригинальный метод, включающий установление справедливости индуктивных предположений в рассматриваемых случаях, а также иллюстративный метод теории расписаний, использующий диаграммы Ганта.

Р е з у л ь т а т ы . Предложена векторная модель реализации последовательных вычислений, учитывающая основные особенности векторно-конвейерных ЭВМ. Определено оптимальное суммарное время выполнения последовательных вычислений в векторном режиме и получена нижняя оценка временного выигрыша по сравнению с последовательным режимом их выполнения.

З а к л ю ч е н и е . Установлено, что при обработке в последовательном режиме скалярных входных данных векторными операциями с длиной конвейера k возможно ускорение не менее чем в nN (nk+N) раз, где N – размер входа, n – число векторных и соответствующих им скалярных операций. Оценка временного ускорения при векторизации вычислений приводится в сравнении с последовательным режимом их выполнения.

1. Векторизация программ: теория, методы, реализация : сб. ст. / под ред. Г. Д. Чинина. – М. : Мир, 1991. – 271 с.

2. Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. – СПб. : БХВ-Петербург, 2002. – 608 с.

3. Топорков, В. В. Модели распределенных вычислений / В. В. Топорков. – М. : Физматлит, 2004. – 320 с.

4. Миллер, Р. Последовательные и параллельные алгоритмы: общий подход / Р. Миллер, Л. Боксер ; пер. с англ. М. : БИНОМ. Лаборатория знаний, 2009. 406 с.

5. Pllana, S. Programming multi core and many core computing system / S. Pllana, F. Xhafa. – John Wiley & Sons, 2017. – 528 p.

6. Демиденко, В. М. Библиотека базовых программных модулей решения комбинаторных задач упорядочения для векторно-конвейерной ЭВМ / В. М Демиденко, П. С. Кляус, Н. С. Коваленко // Проблемы создания суперЭВМ, суперсистем и эффективность их применения : тез. докл. Первой Всесоюз. конф., Минск, 15–17 сент. 1987. Минск, 1987. – Ч. 2. С. 31-32.

7. Демиденко, В. М. О возможности эффективной конвейеризации одного комбинаторного алгоритма / В. М. Демиденко, П. С. Кляус // Вопросы кибернетики. Разработка и использование суперЭВМ : сб. науч. тр. М. : Институт проблем кибернетики, 1987. Вып. 7. С. 96-104.

8. Демиденко, В. М. Базовые процедуры в алгоритмах лексикографической цифровой сортировки и их реализации на векторно-конвейерной ЭВМ / В. М. Демиденко, Л. И. Шевченко // Проблемы создания суперЭВМ, суперсистем и эффективность их применения : тез. докл. Первой Всесоюз. конф., Минск, 15–17 сент. 1987. Минск, 1987. – Ч. 2. С. 33-35.