Будь ласка, використовуйте цей ідентифікатор, щоб цитувати або посилатися на цей матеріал:
http://elartu.tntu.edu.ua/handle/lib/31748| Назва: | Дослідження оптимального алгоритму та використання методів розпаралелювання для задач сингулярно-спектрального розкладу |
| Інші назви: | Study of an optimal algorithm and parallelizing methods use for the problems of singular-spectrum analysis |
| Автори: | Свистун, Ігор Володимирович Svystun, Ihor |
| Приналежність: | ТНТУ ім. І. Пулюя, Факультет комп’ютерно-інформаційних систем і програмної інженерії, Кафедра комп’ютерних наук, м.Тернопіль, Україна |
| Бібліографічний опис: | Свистун І. В. Дослідження оптимального алгоритму та використання методів розпаралелювання для задач сингулярно-спектрального розкладу : дипломна робота магістра за спеціальністю „122 — комп’ютерні науки“ / І. В. Свистун. — Тернопіль: ТНТУ, 2020. — 122 с. Svystun Ihor. Study of an optimal algorithm and parallelizing methods use for the problems of singular-spectrum analysis |
| Дата публікації: | 28-тра-2020 |
| Дата подання: | 25-тра-2020 |
| Дата внесення: | 2-чер-2020 |
| Країна (код): | UA |
| Місце видання, проведення: | ТНТУ ім. І.Пулюя, ФІС, м. Тернопіль, Україна |
| Науковий керівник: | Приймак, Микола Володимирович |
| Члени комітету: | Марценюк, Василь Петрович |
| УДК: | 004.73 |
| Теми: | 122 комп’ютерні науки паралелізм задач task based parallelizm сингулярно-спектральний аналіз SSA стратегія strategy MRRR спектральний розклад матриці OPENMP INTEL TBB INTEL TBB QUARK PLASMA |
| Короткий огляд (реферат): | Дипломна робота присвячена дослідженню методів реалізації паралельних алгоритмів для задачі сингулярно-спектрального розкладу на базі паралельних бібліотек. Метою роботи є вибір оптимального алгоритму та стратегії його розпаралелювання для задачі сингулярно-спектрального розкладу. |
| Опис: | Thesis is devoted to the research of methods of realization of parallel algorithms for the problem of singular-spectral decomposition on the basis of parallel libraries. The aim of the work is to choose the optimal algorithm and strategy of its parallelization for the problem of singular-spectral decomposition. |
| Зміст: | ЗМІСТ Вступ ... 13 1 Дослідження сучасних методів реалізації сингулярного розкладу матриці 15 1.1 Опис чисельного методу сингулярно-спектрального аналізу для аналізу часових рядів ...15 1.2 Огляд алгоритму MRRR та його дерево представлення ...21 1.3 Методи оптимізації програми ...25 1.4 Висновки до першого розділу ...26 2 Методи та технології паралельних обчислень ...28 2.1 Типи паралелізму ...28 2.2 Огляд кросплатформенної бібліотеки шаблонів TBB...29 2.3 Модель програмування OpenMP ...31 2.4 Бібліотека для роботи з системами зі спільною пам’яттю QUARK .. 32 2.5 Порівняння Intel TBB, OpenMP та QUARK ...37 2.6 Висновки до другого розділу ...40 3 Реалізація паралельного методу сингулярного розкладу...42 3.1 Адаптація алгоритму SVD для паралельного виконання ...42 3.2 Стратегія паралелізму алгоритму SVD на базі парадигми «розділяй і владарюй» ...46 3.3 Стратегія паралелізму для алгоритму MRRR ...53 3.4 Порівняння алгоритмів MRRR і DС ...64 3.5 Висновки до третього розділу ...65 4 Обчислювальний експеримент та результати використання паралельного методу ...66 4.1 Проведення обчислювального експерименту ...66 4.2 Висновки до четвертого розділу ...71 5 Спеціальна частина ...72 5.1 Орієнтований ациклічний граф ...72 5.2 Застосування орієнтованого ациклічного графа ...74 5.3 Висновки до п’ятого розділу ...79 6 Обгрунтування економічної ефективності ...80 6.1 Визначення стадій технологічного процесу та загальної тривалості проведення НДР ...80 6.2 Визначення витрат на оплату праці та відрахувань на соціальні заходи ...81 6.3 Розрахунок матеріальних витрат ...84 6.4 Розрахунок витрат на електроенергію ...85 6.5 Розрахунок суми амортизаційних відрахувань ...85 6.6 Обчислення накладних витрат ...87 6.7 Складання кошторису витрат та визначення собівартості НДР ...87 6.8 Розрахунок ціни дослідження ...88 6.9 Визначення економічної ефективності і терміну окупності капітальних вкладень ...89 6.10 Висновки до шостого розділу ...90 7 Охорона праці та безпека в надзвичайних ситуаціях ...91 7.1 Охорона праці ...91 7.1.2 Вимоги до природного та штучного освітлення робочих місць користувачів ПК ...91 7.1.2 Шкідливі фактори при роботі з комп’ютерною технікою ...94 7.2 Безпека в надзвичайних ситуаціях ...98 7.2.1 Основні принципи і способи забезпечення життєдіяльності ...98 7.2.2 Освітлення виробничих приміщень для роботи з ВДТ та локальній комп’ютерній мережі...102 7.3 Висновки до сьомого розділу ...105 8 Екологія ...106 8.1 Методика дослідження джерел забруднення промислових підприємств... 106 8.2 Статистична оцінка техногенних впливів ...109 8.3 Висновки до сьомого розділу ...114 Висновки ...115 Перелік використаних джерел ...116 |
| URI (Уніфікований ідентифікатор ресурсу): | http://elartu.tntu.edu.ua/handle/lib/31748 |
| Власник авторського права: | © Свистун Ігор Володимирович, 2020 |
| Перелік літератури: | 1. Algorithm 880: A Testing Infrastructure for Symmetric Tridiagonals Eigensolver / J. Demmel, O. Marques, B. Parlett, C. Vömel. // ACM TOMS., 2008. – vol. 30, no. 1.– C. 1508–1526. 2. An Implementation of the Tile QR Factorization for a GPU and Multiple CPUs / Kurzak J., Nath R., Du P., Dongarr J. // PARA'10: State of the Art in Scientific and Parallel Computing / – Reykjavík: Springer, 2012. – С. 248–257. 3. Arbenz P. On the spectral decomposition of hermitian matrices modified by flow rankpertubations / P. Arbenz, G. H. Golub – SIAM J. Matrix Anal Appl., 1988. – vol. 9, no. 1. – С. 172-191. 4. Bashe, C. J. The Architecture of IBM’s Early Computers [Electronic resource] / [C. J. Bashe, W. Buchholz, G. V. Hawkins та ін. ] // IBM Journal of System Development, 1981 – Mode of access: URL: http://web.ece.ucdavis.edu/~vojin/CLASSES/EEC272/S2005/Papers/IBM-Architecture-Bashe_sep81.pdf. – c 5. Bentley Jon Writing Efficient Programs / Jon Bentley – Prentice Hall Ptr, 1982. – 170 c.– ISBN 978-0139702440. 6. Bientinesi P. A Parallel Eigensolver for Dense Symmetric Matrices Based on MRRR / P. Bientinesi, I. Dhillon, R. van der Geijn. // SIAM J. SCI. COMP., 2005. – vol. 21. – C. 43-66. 7. Chapman B. Using OpenMP – Portable Shared Memory Parallel Programming / Barbara Chapman, Gabriele Jost, Ruud van der Pas – The MIT Press, 2007. – 384 c. – ISBN 978-0262533027. 8. Chen D. Taming Hardware Event Samples for FDO Compilation // Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization / [Dehao Chen, Neil Vachharajani, Robert Hundt та ін.]., 2010 – C. 42-52. 117 9. Cilk: An Efficient Multithreaded Runtime System / [R. Blumofe, C. Joerg, B. Kuszmaul та ін.] // Journal of Parallel and Distributed Computing, 1996. – vol. 37, no. 1 – С. 55–69. 10. Cooper Keith D., Engineering a Compiler/ 2-nd Edition / Keith D. Cooper, Linda Torczon. – Morgan Kaufmann, 2011. – 404 c. – ISBN 1-55860- 699-8. 11. Cuppen J. J. M. A divide and conquer method for the symmetric tridiagonal eigenproblem / J. J. M. Cuppen. // Numerische Mathematik, 1980. – vol. 36, no. 2. – С. 177-195. 12. Demmel J. W. Applied Numerical Linear Algebra / J. W. Demmel. – Philadelphia: SIAM, 1997. – 184 c. 13. Demmel James W. On the correctness of some bisection-like parallel eigenvalue algorithms in floating point arithmetic / James W. Demmel, Dhillon Inderj.it, Ren Huan // Electronic Trans. Num. Anal, 1995. – vol. 3. – C. 116-149 14. Dhillon I. Orthogonal Eigenvectors and Relative Gaps / I. Dhillon, B. Parlett –SIAM J. Matrix Anal, 2004. – vol. 25. – C. 858-899. 15. Dhillon I. Relative Robust Representations of Symmetric Tridiagonal Linear Algebra / I. Dhillon, B. Parlett // Linear Algebra and its Applications, 2000. – vol. 309, no. 1-3. – C. 121-151. 16. Dhillona Inderjit S. Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices / Inderjit S. Dhillona, Beresford N. Parlettb // Linear Algebra and its Applications, 2004. – vol. 387. – C. 1-28. 17. Divide and Conquer Symmetric Tridiagonal Eigensolver for Multicore Architectures // Parallel and Distributed Processing Symposium / [G. Pichon, A. Haidar, M. Faverge та ін.]. – Hyderabad, 2015. – С. 51–60. 18. Dongarra J. A. Quark user’ guide: Queuing and runtime for kernels / J. Dongarra, J. Kurzak, A. YarKhan // Innovative Computing Laboratory University of Tennessee, Technical Report, 2011. 118 19. Francis J. G. F. The QR Transformation A Unitary Analogue to the LR Transformation – Part 1 / J. G. F. Francis // Computer Journal, 1961. – vol. 4, no. 3 – С. 256-271. 20. Frost R. Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars. // 10th International Workshop on Parsing Technologies / Richard Frost, Hafiz Rahmatullah, Paul Callaghan. – Prague , ACL-SIGPARSE, 2007. – C. 109-120. 21. Golub G. H. Some modified matrix eigenvalue problems / G. H. Golub // SIAM Review, 1973. – vol. 15, no. 2. – C. 318-334. 22. Gu Ming A Divide-and-Conquer Algorithm for the Symmetric Tridiagonal Eigenproblem / Ming Gu, Stanley C. Eisenstat // SIAM. J. Matrix Anal. Appl., 1995. – vol. 16, no. 1. – C.172-191. 23. Guand M. A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem / M. Guand, S. C. Eisenstat // SIAM J. Matrix Anal. Appl., 1995. – vol. 16, no. 1. – С. 172-191. 24. Hennessy John L Computer Organization and Design. The Hardware/Software Interface. 5th Edition / John L. Hennessy, David A. Patterson – Morgan Kaufmann Publishers, 2013. – ISBN 978-0124077263. 25. Hyde Randall The Art of Assembly Language. 2nd Edition / Randall Hyde – No Starch Press, 2010. – ISBN 978-1593272074. 26. Isard Michael Distributed Data-Parallel Programs from Sequential Building Blocks // European Conference on Computer Systems (EuroSys) / [Michael Isard, Mihai Budiu, Yuan Yu та ін.]. – Lisbon, Portugal, 2007. – vol. 41, no. 3. – С. 59-72. – ISBN 978-1-59593-636-3. 27. Knuth D. The Art of Computer Programming, Volume 1: Fundamental Algorithms / Donald Knuth - Addison-Wesley, 2011. – 672 c. – ISBN 978-0201896831. 119 28. Kublanovskaya V. N. On some algorithms for the solution of the complete eigenvalue problem / V. N. Kublanovskaya. // USSR Computational Mathematics and Mathematical Physics, 1961. – vol. 1, no. 3. – С. 555-572. 29. LAPACK Users’ Guide. / [E. Anderson, Z. Bai, C. Bischof та ін.]. – Philadelphia,: SIAM, 2001. – 258 c. 30. Lessig C. An Implementation of the Tile QR Factorization for a GPU and Multiple CPUs // PPAM 2009: 8th Intern. Conf. on Parallel Processing and Applied Math. – Poland, Wroclaw, 2009. – С. 369–402. 31. Nakatsukasa Yuji A Divide-and-Conquer Algorithm for the Symmetric Tridiagonal Eigenproblem / Yuji Nakatsukasa, Nicholas J. Higham // SIAM. J. Sci. Comput., 2013 – vol. 35, no. 3. – C. A1325-A1349. 32. OpenMP Application Program Interface Version 3.0 [Electronic resource] – Mode of access: URL: http://www.openmp.org/mp-documents/spec30.pdf. – Last access: 10.05.2015. – Title from the screen. 33. OpenMP Application Program Interface, Version 4.0 [Electronic resource] – Mode of access: URL: http://www.openmp.org/mp-documents/OpenMP4.0.0.pdf – Last access: 11.05.2015 – Title from the screen. 34. Parallel solution of partial symmetric eigenvalue problems from electronic structure calculations / [T. Auckenthaler, V. Blum, H. Bungartz та ін.]. // Parallel Comput., 2011 – vol. 36, no. 12. – С. 783 –794. 35. Parallel Tiled QR Factorization for Multicore Architectures / A Buttari, J Langou, J Kurzak, J Dongarra // Concurrency and Computation: Practice and Experience, 2008. – vol. 35, no. 1. – C. 31573-1590. 36. Parlett B. An implementation of the DQDS Algorithm / B. Parlett, O. Marques // Linear Algebra and its Applications, 2000. – vol. 309, no. 1-3. – C. 217-259. 37. Perez J. A dependency-aware task-based programming environment for multi-core architectures / J. Perez, R. Badia, J. Labarta. //Cluster Computing, 2008 120 IEEE International Conference on, 2008. – C. 142-151. – ISBN 978-1-4244-2639-3. 38. Performance and accuracy of lapack’s symmetric tridiagonal eigensolvers [Electronic resource] / J.Demmel, O. Marques, B. Parlett, C. Vomel // SIAM J. Scientific Computing, 2008 – vol. 30, no. 3. – С. 1508-1526. – Mode of access: URL: http://dblp.unitrier.e/db/journals/siamsc/siamsc30.html#DemmelMPV08. – Last access: 23.10.2015. – Title from the screen. 39. Performance and Accurancy of LAPACK’s Symmetric Tridiagonal Eigensolvers / J. Demmel, O. Marques, B. Parlett, O. Voemel //SIAM J. SCI COMP., 2008. – vol. 30. – C. 1-28. 40. Pichon P. Divide and Conquer Symmetric Tridiagonal Eigensolver for Multicore Architectures / [G. Pichon, A. Haidar, M. Faverge та ін.]. // Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International – IEEE, 2015. – C. 51-60. 41. Plasma users’ guide: Parallel linear algebra software for multicore architectures [Electronic resource] / [E. Agullo, J. Dongarra, B. Hadri та ін.]. // Technical report, University of Tennessee, Innovative Computing Laboratory, 2010. – Mode of access: URL: http://icl.cs.utk.edu/projectsfiles/plasma/pdf/users_guide20091104.pdf. – Last access: 03.05.2015. – Title from the screen. 42. Programming Matrix Algorithm-by-Blocks for Thread-Level Parallelism / [G. Quintana-Ort, E. S. Quintana-Ort, U. Jaume та ін.]. // ACM Trans. Math. Soft., 2009. – vol. 36, no. 3. – 28 c. 43. Reinders J. Intel Threading Building Blocks: Outfitting C++ for multi-core processor parallelism / James Reinders. – Sebastopol: O'Reilly Media, 2007. – 336 с. – ISBN 978-0596514808. 121 44. Reinders James Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism / James Reinders – Sebastopol: O'Reilly Media, 2007 – 336 c. – ISBN 978-0-596-51480-8. 45. ScaLAPACK USER’s Guide / [L. S. Blackford, J. D. Crus, I. Duff та ін.] // Philadelphia: SIAM, 1997. 46. Sedgewick Robert Algorithms / Robert Sedgewick – Addison-Wesley Pub, 1988. – c. 657. – ISBN 978-0201066739. 47. StarPU: A unied platform for task scheduling on heterogeneous multicore architectures / C.Augonnet, S. Thibault, R. Namyst, P. Wacrenier // Euro-Par ’09: In Proceedings of the 15th International Euro-Par Conference on Parallel Processing – Heidelberg: Springer-Verlag, 2009. – С. 863–874. 48. Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide / [Z. Bai, J. Demmel, J. Dongarra та ін.]. – Philadelphia: SIAM, 2000. – 440 с. 49. Tisseur F. Parallizing The devide and conquer algorithm for the symmetric tridiagonal eigenvalue problem on distributed memory architechtures / F. Tisseur, J. Dongarra // SIAM J. SCI. COMPUT, 1998. – vol. 20. – C. 2223-2236. 50. Wescott Bob The Every Computer Performance Book / Bob Wescott – CreateSpace, 2013. – 222 c. – ISBN 1482657759. 51. Wilkinson J. The Calculation of the Eigenvectors of Codiagonal Matrices / J. H. Wilkinson. // Computer Journal, 1958. – vol. 2, no. 2. – С. 90–96. 52. Willems P. On MR3-type Algorithms for the Tridiagonal Symmetric Eigenproblem and Bidiagonal SVD / P. Willems – Disertation, University of Wuppertal, 2010. 53. Бобок С.А. Чрезвычайные ситуации: защита населения и территорий / С.А. Бобок, В.И. Юртушкин – М.: «Издательство ГНОМ и Д», 2000. 122 54. Закон України «Про оплату праці». Верховна Рада України. Закон від 24.03.1995 № 108/95-ВР, чинний, поточна редакція – Редакція від 01.01.2015. – К.: Відомості Верховної Ради України, 1995, № 17, ст. 121. 55. (Цушко) Максимець О. В. Дослідження методів реалізації паралельних алгоритмів для задачі сингулярно-спектрального розкладу на базі паралельних бібліотек : дипломна робота магістра / О.В. (Цушко) Максимець — Тернопіль: ТНТУ, 2015. – 103 с. 56. Назаревич О. Б. Інформаційна технологія моніторингу газоспоживання міста : автореф. дис. на здобуття наук. ступеня канд. техн. наук: 05.13.06 «Інформаційні технології» / О. Б. Назаревич. – Тернопіль, 2015. – 24 с. 57. Приймак М. Дослідження особливостей енергоспоживання в умовах ритміки методом гістограмного аналізу / М.В. Приймак, О.В. Мацюк, О.Б. Назаревич, Г.В. Шимчук // Міжнародна науково-технічна конференція "Фундаментальні та прикладні проблеми сучасних технологій" (присвячена 50-річчю заснування ТНТУ та 165- річчю з дня народження Івана Пулюя, 19-21 травня)., 2010 – Тернопіль: ТНТУ. – 301 с. 58. Основи охорони праці. В. Ц. Жидецький, В. С. Джигирей, О. В. Мельников — Вид. 2е, стериотипне. — Львів: Афіша, 2000. — 348 с. 59. Катренко П.А., Кіт Ю.В., Пістун І.П. Охорона праці. Курс лекцій. Практикум: Навчальний посібник.- Суми: ВТД “Університетська книга”, 2003. — 496с. 60. https://studfile.net/preview/5211197/page:3/ 61. Тарасова В.В. «Екологічна статистика», 2008, - 392с. |
| Тип вмісту: | Master Thesis |
| Розташовується у зібраннях: | 122 — комп’ютерні науки |
Файли цього матеріалу:
| Файл | Опис | Розмір | Формат | |
|---|---|---|---|---|
| dyplom_Svystun.pdf | 5,45 MB | Adobe PDF | Переглянути/відкрити |
Усі матеріали в архіві електронних ресурсів захищені авторським правом, всі права збережені.
Інструменти адміністратора