Preview

Информатика

Расширенный поиск

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

https://doi.org/10.37661/1816-0301-2022-19-1-72-87

Полный текст:

Аннотация

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

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

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

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

Об авторах

В. М. Демиденко
http://www.bseu.by/hm/
Белорусский государственный экономический университет
Беларусь

Демиденко Виталий Михайлович - доктор физико-математических наук, профессор.

пр. Партизанский, 26, Минск, 220070.



В. И. Бенедиктович
https://www.im.bas-net.by
Институт математики НАН Беларуси
Беларусь

Бенедиктович Владимир Иванович - кандидат физико-математических наук, ведущий научный сотрудник.

ул. Сурганова, 11, Минск, 220072.



Список литературы

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.


Дополнительные файлы

Рецензия

Для цитирования:


Демиденко В.М., Бенедиктович В.И. Векторизация итерационных вычислительных процессов и оценки временного ускорения. Информатика. 2022;19(1):72-87. https://doi.org/10.37661/1816-0301-2022-19-1-72-87

For citation:


Demidenko V.M., Benediktovich V.I. A vectorization of iterative computational processes and time acceleration estimates. Informatics. 2022;19(1):72-87. (In Russ.) https://doi.org/10.37661/1816-0301-2022-19-1-72-87

Просмотров: 83


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)