Розробка програмно-математичного забезпечення для паралельної обробки розріджених матриць за допомогою технологи OpenMP

О. В. Минько, К. Е. Золотько

Анотація


Робота присвячена паралельному обчисленню розріджених матриць. В ході роботи були спроектовані і оптимізовані за допомогою мови програмування С алгоритми для роботи з розрідженими матрицями для наступних операцій: транспонування, множення розріджених матриць, множення розрідженій матриці на щільний вектор, додавання розріджених матриць. Для зберігання даних розроблений гнучкий алгоритм, який застосовує найбільш оптимальної варіант збереження для конкретного типу операцій. Були застосовані процедури виділення щільних підматриць в розріджених матрицях. Для прискорення роботи програми використовується технологія паралельного обчислення OpenMP, яка дає можливість на апаратному рівні мінімізувати ресурси і час виконання.


Ключові слова


розріджені матриці; формат crs; операції над розрідженими матрицями; паралельна реалізація; openmp

Повний текст:

PDF (Русский)

Посилання


Pissanetski, S. (1988). Sparse matrix technology. Moscow: Mir, 410.

George, A., Liu, J. (1984). Numerical solution of large sparse systems of equations. Moscow: Mir, 333.

Tewarson, R. (1977). Sparse matrix. Moscow: Mir, 191.

Horton, I. (2011). Visual C++ 2010: full course. Dialektika, 1216.

Antonov, A. S. (2009). Paralelne programming using technology OpenMP. Moscow: MGY, 77.

Golub, J., Van Loan, C. (1999). Matrix calculations. Moscow: Mir, 548.

Potemkin, V. G. Guide to the MATLAB, 164. Available at: http://ui-engineers.ddns.net/_ld/1/143___Matlab.pdf

Kaspersky, K. (2003). Technique optimization programs. Efficient use of memory. Saint Petersburg: BHV-Petersburg, 464.

Horton, I. (2007). Visual C++ 2005: full course. Williams, 1152.

Demmel, J. W. (1997). Applied Numerical Linear Algebra. SIAM, 431.

Demmel J. U.C. (2014). Applications of Parallel Computers. Available at: https://people.eecs.berkeley.edu/~demmel/cs267_Spr14/

Tewarson, R. P. (1973). Sparse Matrices. Academic Press, 160

Buttari, A., Langou, J., Kurzak, J., Dongarra, J. (2007). A Classof Parallel Tiled Linear Algebra Algorithms for Multicore Architectures. University of Tennessee, 191.

Kernighan, B., Ritchie, D. (2009). The C Programming Language. Williams, 304.

Gerber, R., Bik, A. J. C., Smith, K. B., Tian, X. (2010). The Software Optimization Cookbook. Saint Petersburg: Piter, 352

Bik, A. J. C. (2006). The Software Vectorization Handbook: Applying Multimedia Extensions for Maximum Performance. Intel Press, 236.

Vorontsov, K. V. Mathematical methods of training on precedents (machine learning theory), 141. Available at: http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf

Deacons, A. (2010). The data analysis, training on precedents, logic games, WEKA system, RapidMiner and MatLab. MAKSPress, 278.

Zhuravlev, Y. (1998). Selected scientific works. Moscow: Magistr, 420.

Zhuravlev, Y. (1978). Correct algebras over sets incorrect (heuristic) algorithms. Cybernetics, 2, 35−43.

Rudakov, K. (1989). On the algebraic theory of universal and local constraints for classification problems. Recognition, classification, prognosis, 1, 176−201.

Rudakov, K. (1987). Completeness and universal constraints in the problem of correction heuristic algorithms cal classification. Cybernetics, 3, 106−109.

Petrov, S. O., Marchenko, I. O., Dibrov, B. O. (2015). The use of convolution operators in the tasks of edge detection. Eastern-European Journal of Enterprise Technologies, 6(4(78)), 27−31. doi:10.15587/1729-4061.2015.56548


Пристатейна бібліографія ГОСТ


1. Писсанецкы, С. Технология разреженных матриц [Текст] / С. Писсанецкы. − Москва: Мир, 1988. − 410 с.

2. Джордж, А. Численное решение больших разреженных систем уравнений [Текст] / А. Джордж, Дж. Лю. − Москва: Мир, 1984. − 333 c.

3. Тьюарсон, Р. Разреженные матрицы [Текст] / Р. Тьюарсон. − Москва: Мир, 1977. – 191 c.

4. Хортон, А. Visual C++ 2010: полный курс [Текст] / А. Хортон. – Диалектика, 2011. – 1216 с.

5. Антонов, А. С. Паралельне программирования с использованием технологии OpenMP [Текст]: учебное пособие / А. С. Антонов. − Москва: МГУ, 2009. – 77 с.

6. Голуб, Дж. Матричные вычисления [Текст] / Дж. Голуб, Ч. Ван Лоун. − Москва: Мир, 1999. − 548 c.

7. Потемкин, В. Г. Справочник по MATLAB [Электронный ресурс] / В. Г. Потемкин. – 164 с. – Режим доступа: \www/URL: http://ui-engineers.ddns.net/_ld/1/143___Matlab.pdf

8. Касперски, К. Техника оптимизации программ. Эффективное использование памяти [Текст] / К. Касперски. − Санкт-Петербург: БХВ-Петербург, 2003. – 464 с.

9. Хортон, А. Visual C++ 2005: базовый курс [Текст] / А. Хортон. – Вильямс, 2007. – 1152 с.

10. Demmel, J. W. Applied Numerical Linear Algebra [Text] / J. W. Demmel. − SIAM, 1997. − 431 p.

11. Demmel, J. U. C. Applications of Parallel Computers [Electronic resource] / J. U. C Demmel. – Spring, 2014. − Available at: \www/URL: https://people.eecs.berkeley.edu/~demmel/cs267_Spr14/

12. Tewarson, R. P. Sparse Matrices [Text] / R. P. Tewarson. − Academic Press, 1973. – 160 p.

13. Buttari, A. A Class of Parallel Tiled Linear Algebra Algorithms for Multicore Architectures [Text]: technical report / A. Buttari, J., Langou, J., Kurzak, J. Dongarra. − University of Tennessee, 2007. – 191 p.

14. Керниган, Б. Язык программирования C [Текст] / Б. Керниган, Д. Ритчи. − Вильямс, 2009. – 304 с.

15. Гербер, Р. Оптимизация ПО. Сборник рецептов [Текст] / Р. Гербер, А. Бик, К. Смит, К. Тиан. – Санкт Петербург: Питер, 2010. – 352 с.

16. Bik, A. J. C. The Software Vectorization Handbook: Applying Multimedia Extensions for Maximum Performance [Text] / A. J. C. Bik. − Intel Press, 2006. – 236 p.

17. Воронцов, К. В. Математические методы обучения по прецедентам (теория обучения машин) [Электронный ресурс]: курс лекций / К. В. Воронцов. – 141 с. – Режим доступа: \www/URL: http://www.machinelearning.ru/wiki/images/6 /6d/Voron-ML-1.pdf

18. Дьяконов, A. Г. Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab [Текст] / A. Г. Дьяконов. – МАКСПресс, 2010. – 278 с.

19. Журавлёв, Ю. И. Избранные научные труды [Текст] / Ю. И. Журавлёв. − Москва: Магистр, 1998. – 420 с.

20. Журавлёв, Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов [Текст] / Ю. И. Журавлёв // Кибернетика. − 1978. − № 2. − С. 35–43.

21. Рудаков, К. В. Об алгебраической теории универсальных и локальных ограничений для задач классификации [Текст] / К. В. Рудаков // Распознавание, классификация, прогноз. – 1989. – № 1. – C. 176−201.

22. Рудаков, К. В. Полнота и универсальные ограничения в проблеме коррекции эвристичских алгоритмов классификации [Текст] / К. В. Рудаков // Кибернетика. − 1987. − № 3. − C. 106−109.

23. Петров, С. О. Дослідження застосування операторів згортки в задачах виділення границь на зображенні [Текст] / С. О. Петров, І. О. Марченко, Б. О. Дібров // Східно-Європейський журнал передових технологій. – 2015. − № 6/4 (78). – C. 27−31. doi:10.15587/1729-4061.2015.56548



Посилання

  • Поки немає зовнішніх посилань.




Copyright (c) 2016 О. В. Минько, К. Е. Золотько

Creative Commons License
Ця робота ліцензована Creative Commons Attribution 4.0 International License.

ISSN 2411-2828 (Online), ISSN 2411-2798 (Print)