НАУКА и ОБРАЗОВАНИЕ

Файл статьи: Kudr141.pdf (385.11Кб)

Статья посвящена методам оценки времени выполнения параллельных вычислительных процессов. Цель работы – разработать и обосновать алгоритм, позволяющий находить минимальное время работы параллельного процесса, заданного как последовательность операций, время выполнения которых известно. Основная идея заключается в разложении операций на микрооперации с временем выполнения 1. Это приводит к состоящему из микроопераций параллельному процессу, время выполнения которого будет равно высоте нормальной формы Фоаты соответствующего элемента некоторого свободного частично коммутативного моноида.

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

В данной работе асинхронные системы рассматриваются как пунктированные множества с действием моноидов трасс. Это позволяет ввести морфизмы асинхронных систем, у которых отображения соответствующих моноидов трасс могут быть произвольными гомоморфизмами. Эти морфизмы асинхронных систем обобщают все рассмотренные ранее морфизмы и называются гомоморфизмами.

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

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

Основной результат данной статьи имеет прикладное значение – получен и подробно описан новый алгоритм нахождения времени выполнения параллельного процесса, заданного с помощью трассы в асинхронной системе с функцией времени.  Обоснование этого алгоритма дано в Теореме 1, в которой описаны условия, достаточные для того, чтобы гомоморфизм сохранял минимальное время выполнения трассы. Если к трассе применить гомоморфизм, удовлетворяющий этим условиям, то получится трасса, высота нормальной формы которой равна времени выполнения исходной трассы.

Особенно интересен случай,  когда трасса описывает итерационный параллельный процесс, который описывается некоторой сетью Петри.  Всякая сеть Петри может рассматриваться как асинхронная система. Отсюда вытекает, что параллельные процессы, моделируемые с помощью сетей Петри, допускают оценку времени выполнения, полученного этим способом. Проведен ряд экспериментов, подтверждающих правильность разработанного алгоритма для итерационных параллельных процессов, заданных с помощью сетей Петри. Эксперименты проведены для псевдо-конвейеров  и  для волновых систем. Подробно описано программное обеспечение, на основе которого проведены эксперименты. Оно состоит из потоков, соответствующих переходам сетей Петри. Синхронизация работы потоков осуществляется с помощью событий. Теоретические расчеты приводят к аналитическим формулам для нахождения времени выполнения процесса от числа элементов входных данных. График зависимости времени обработки от объема входных данных показывает, что экспериментальные расчеты почти не отличаются от теоретических.

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

Таким образом, алгоритм обоснован теоретически и подтвержден экспериментально. Рассмотренные примеры применения алгоритма приводят к формулам для нахождения зависимости времени выполнения параллельного процесса от объема входных данных. Хотелось бы иметь способ получения аналогичных формул для общего случая, когда параллельный процесс задан с помощью итерации некоторой трассы. В перспективе также исследование и другие приложения гомоморфизмов асинхронных систем, введенных в данной работе.

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

1. Bednarczyk M. Categories of Asynchronous Systems. Brighton: University of Sussex, 1987. 230 p.
2. Winskel G., Nielsen M. Models for Concurrency // Handbook of Logic in Computer Science. Vol. 4. Semantic Modelling / Abramsky S., Gabbay D.M., Maibaum T.S.E. (eds.). Oxford University Press, 1995.  P. 1-148.
3. Bednarczyk M.A., Bernardinello L., Caillaud B., Pawlowski W., Pomello L. Modular System Development with Pullbacks // Applications and Theory of Petri Nets 2003. Berlin: Springer-Verlag, 2003. P. 140-160. DOI: 10.1007/3-540-44919-1_12    (Ser. Lecture Notes in Computer Science; vol. 2679).
4. Husainov A. On the homology of small categories and asynchronous transition systems // Homology, Homotopy and Applications. 2004. Vol. 6, no.1. P. 439-471. Available at: http://projecteuclid.org/euclid.hha/1139839561 (accessed 01.12.2013).
5. Хусаинов А.А., Кудряшова Е.С. Модель для временных оценок параллельных вычислительных систем // Информационные технологии XXI века: материалы международной научной конференции (Хабаровск, 20-24 мая 2013 г.). Хабаровск: Изд-во Тихоокеан. гос. ун-та, 2013. С. 203 - 207.
6. Cartier P., Foata D. Problemes combinatories de commutation et rearrangements. Berlin: Springer-Verlag, 1969. 88 p. (Ser. Lecture Notes in Math.; vol. 85.).
7. Diekert V. Combinatorics on Traces. Berlin: Springer-Verlag, 1990. 169 p. DOI: 10.1007/3-540-53031-2         (Ser. Lecture Notes in Computer Science; vol. 454.).
8. Diekert V., Metivier Y. Partial Commutation and Traces // Handbook of Formal Languages. Vol. 3. Beyond Words. New York: Springer-Verlag, 1997. P. 457-533. DOI: 10.1007/978-3-642-59126-6_8
9. Mazurkiewicz A. Trace theory // Petri Nets: Applications and Relationships to Other Models of Concurrency. Berlin: Springer-Verlag, 1987. P. 278-324. DOI: 10.1007/3-540-17906-2_30         (Ser. Lecture Notes in Computer Science; vol. 255.).
10. Хусаинов А. Исследование параллельных систем методами теории категорий. Саарбрюкен: LAP LAMBERT Academic Publishing, , 2012. 152 c.
11. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Санкт-Петербург: БХВ-Петербург, 2002. 602 c.
12. Карпов В.Е. Введение в распараллеливание алгоритмов и программ // Компьютерные исследования и моделирование. 2010. Т. 2, № 3. С. 231-272. Режим доступа: http://crm.ics.org.ru/journal/article/1725/ (дата обращения 01.12.2013).
13. Трещев И.А. Методы построения систем автоматизированного распараллеливания приложений для архитектур с симметрично-адресуемой памятью // Ученые записки Комсомольского-на-Амуре государственного технического университета. Сер. «Науки о природе и технике». 2011. Т. 5, № I-1. С. 29-32. Режим доступа: http://www.uzknastu.ru/files/pdf/I-1(5)2011/29-32.pdf (дата обращения 01.12.2013).
14. Герценбергер К.В., Чепин Е.В. Аналитическая модель оценки производительности многопроцессорной обработки данных для набора параллельных алгоритмических структур // Бизнес-информатика. 2011. № 4. С. 24-30. Режим доступа: http://bijournal.hse.ru/2011--4%20(18)/44322998.html (дата обращения 01.12.2013).
15. Goubault E. Durations for truly-concurrent transitions // Programming Languages and Systems — ESOP '96. Berlin: Springer-Verlag, 1996. P. 173-187. DOI: 10.1007/3-540-61055-3_36 (Ser. Lecture Notes in Computer Science; vol. 1058).