Математическое моделирование алгоритмов, работающих на разделяемой памяти тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Кудрин, Максим Юрьевич

• Кудрин, Максим Юрьевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Кудрин, Максим Юрьевич

Оглавление.

Введение.

Актуальность темы.

Цель работы, задачи исследования

Научная новизна.

Практическая ценность.

Краткое содержание работы.

Обзор существующих систем.

Динамический анализ

Общие принципы.

Инструменты динамического анализа.

Средства статического анализа.

Основные принципы.

Вычисления при помощи набора состояний.

Анализ части кода.

Использование псевдонимов.

Точность и время работы.

Алгоритмы.

Анализаторы.

Синхронизация в многопоточных алгоритмах.

Архитектуры параллельных систем.

Моделирование и методика анализа.

Алгоритмы анализа.

Постановка задачи для двух потоков.

Представление работы потоков

Построение графа совместного исполнения потоков.

Определение классов эквивалентности.

Построение представителей классов эквивалентности

Оценка числа классов эквивалентности.

Построение редуцированного графа и анализ результатов.

Анализ трех и большего числа потоков.

Ветвления в алгоритмах.

Допустимость перестановки операций одного потока.

Примеры исследования многопоточных алгоритмов.

Задача об изменении значения ячейки в двух потоках

Граф совместного исполнения потоков.

Классы эквивалентности.

Редуцированный граф.

Вычисление результата работы потоков.

Задача о транзакционном изменении двух ячеек памяти

Представление работы потоков.

Граф совместного исполнения потоков.

Классы эквивалентности.

Редуцированный граф.

Вычисление результата работы потоков.

Алгоритм спин-блокировки.

Неблокирующаяся реализация алгоритма очереди.

Алгоритм Петерсона для случая двух потоков.

Список литературы диссертационного исследования кандидат физико-математических наук Кудрин, Максим Юрьевич, 2009 год

1. Serebryany К. Data race test. -(http://c0de.g00gle.c0m/p/data-race-test)

2. Herlihy M., Shavit N. The Art of Multiprocessor Programming. Elsevier, 2008.

3. Rahul V. Patil, George B. Concurrency: Tools And Techniques to Identify Concurrency Issues. MSDN Magazine, June 2008

4. S. Qadeer, D. Wu. KISS: keep it simple and sequential. -PLDI, 2004.

5. E. Bodden, K. Havelund. Racer: effective race detection using Aspectj. ISSTA, 2008.

6. M. Naik, A. Aiken, J. Whaley. Effective Static Race Detection for Java. PLDI, 2008.

7. Robert O'Callahan, Jong-Deok Choi. Hybrid Dynamic Data Race Detection. PPoPP'03, San Diego, California, USA, 2003.

8. Карпов А. Тестирование параллельных программ. (http://www.software-testing.ru/library/testing/functional-testing/5 81 -parallelprogramtesting)

9. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Trans, on Computer Systems, 15(4), 1997.

10. Brian Davies. Whither Mathematics? Notices of the American Mathematical Society, dec. 2005, vol. 52, №11.

11. P. Emanuelsson, U. Nilsson A Comparative Study of Industrial Static Analysis Tools. Elsevier Science Publishers В. V. Amsterdam, The Netherlands, The Netherlands, 2008.

12. A. Deutsch. Interprocedural May-Alias Analysis for Pointers: Beyond k-limiting. In Proe. Programming Language Design and Implementation. ACM Press, 1994.

13. B. Steensgaard. Points-to Analysis in Almost Linear Time. In ACM POPL, 1996.

14. Калугин А. Верификатор программ на языке Си LINT. (http://www. viva64. com/go. php?url=224)

15. Карпов А. Что такое "Parallel Lint"? (http: //software, intel. com/ru-ru/articles/parallel-lint/)

16. Static Source Code Analysis Tools for C. (http://www.spinroot.com/static/)

17. Каличкин С.В. Обзор средств статической отладки. Новосибирск. С.-22. 2004.

18. Christian Terboven. Comparing Intel Thread Checker and Sun Thread Analyze. Center for Computing and Communication RWTH Aachen University, Germany. 2007.

19. Использование Thread Analyzer для поиска конфликтов доступа к данным (http://ru.sun.com/developers/sunstudio/articles/thausingru. html)

20. Anne Dinning and Edith Schonberg. An empirical comparison of monitoring algorithms for access anomaly detection. In Proceedings of the Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 1990. C. 1-10.

21. J. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Proceedings of the 1991 ACM/IEEE conference on Supercomputing, ACM Press, 1991. C. 24-33.

22. D. Perkovic and P. Keleher. Online data-race detection via coherency guarantees. In Proceedings of the 2nd Symposium on Operating Systems Design and Implementation (OSDI'96), 1996. C. 47-57.

23. T. Ball and S. Rajamani. The SLAM project: debugging system software via static analysis. In Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'02), ACM Press, 2002. C. 1-3.

24. M. Das. Unification-based pointer analysis with directional assignments. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI'00), ACM Press, 2000. C. 35-46.

25. David R. Chase, Mark Wegman, and F. Kenneth Zadeck. Analysis of pointers and structures. In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, June 1990. C. 296-310.

26. Mark Orlovich. On flow-insensitive points-to analyses. (http://www.cs.cornell.edu/eourses/es71 l/2005fa/slides/sepl3 .pdf)

27. Кудрин М.Ю., Прокопенко А.С., Тормасов А.Г. Метод нахождения состояний гонки в потоках, работающих на разделяемой памяти // Сборник научных трудов МФТИ. -М.: МФТИ, 2009. № 4. - Том 1. - С. 181-201.

28. Кудрин М.Ю. Выявление состояний гонки с помощью графа совместного исполнения потоков // Материалы международной научно-технической конференции "Компьютерные науки и технологии" Белгород: Изд-во БелГУ, 2009. - С. 45-46.

29. Кудрин М.Ю., Петров В.Н., Прокопенко А.С. Обнаружение состояний гонки в потоках, работающих на разделяемой памяти 11 Модели и методы обработки информации, сборник научных трудов М.: МФТИ, 2009. - С. 93-98.

30. Соколов Е.В., Кудрин М.Ю. Модель организации снимка памяти на основе nk-схемы при наложении ограничения типа темпа доступа // Модели и методы обработкиинформации, сборник научных трудов М.: МФТИ, 2009. - С. 197-205.

31. Кудрин М.Ю., Соколов Е.В. Выявление состояний гонки с помощью аппарата атрибутных грамматик // Научное творчество молодежи. Материалы XIII Всероссийской научно-практической конференции. Кемерово: Кемеровский гос. универ-т, 2009. - С. 112.

32. Соколов Е.В., Кудрин М.Ю. Алгоритмы снэпшота основанные на ограничении темпа доступа к памяти // Научное творчество молодежи. Материалы XIII Всероссийской научно-практической конференции. Кемерово: Кемеровский гос. универ-т, 2009. С. 125.

33. Кудрин М.Ю. Исследование цепочечных объектов // Совр. проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLVII научной конференции. / МФТИ, Долгопрудный, 2004.C. 74.

34. Chris Purcell, Tim Harris, Non-blocking hashtables with open addressing. University of Cambridge, 2005.

35. Intel Architecture Software Developer's Manual. Volume 13.

36. Акишев И. P. Разработка и анализ параллельных поисковых структур данных, нечувствительных к размеру кеша, бакалаврская работа, кафедра компьютерных технологий, СПбГУИТМО, 2008.

37. Philip N. Klein, Hsueh Lu, Robert Netze, Detecting Race Conditions in Parallel Programs that Use Semaphores. -Lecture Notes in Computer Science, Springer Berlin/Heidelberg, 2008.

38. Keir Fraser, Practical lock-freedom. University of Cambridge, 2004.

39. Slonneger K., Kurtz B, Formal syntax and semantics of programming languages. Addison-Wesley, 1995.

40. Серебряков В.А., Галочкин М.П., Гончар Д.P., Фуругян М.Г, Теория и реализация языков программирования. М.: МЗ Пресс, 2006.

41. Herlihy M. Impossibility and Universality Results for Wait-Free Synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, 1988. C. 276-290.

42. Peter M. Hines Symmetries and transitions of bounded Turing machines. CoRR , 1998.

43. Kohtaro Tadaki, Tomoyuki Yamakami, Jack C.H. Lin Theory of One Tape Linear Time Turing Machines Elsevier Science Publishers В. V., 2009.

44. Michiel Ronsse, Koen De Bosschere, Non-Intrusive on-the-Fly Data Race Detection Using Execution Replay, Automated And Algorithmic Debugging: Proceedings. Germany, 2000.

45. Lomet, D.B. Process structuring, synchronization, and recovery using atomic actions, In Proceedings of the ACM Conference on Language Design for Reliable Software . -ACM, NY, 1977. C. 128-137.

46. Shavit, N., Touitou, D. Software transactional memory, In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing. ACM, NY, 1995. - C. 204-213.

47. Herlihy, M., Moss, J.E.B. Transactional memory: Architectural support for lock-free data structures, In Proceedings of the 20th International Symposium on Computer Architecture. ACM, 1993. - C. 289-300.

48. Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal The combined power of conditions and failure detectors to solve asynchronous set agreement, Proceedings of Symposium on Principles of Distributed Computing. ACM, Germany, 2005.

49. G. Kliot, E. Petrank, B. Steensgaard, A lock-free, concurrent, and incremental stack scanning for garbage collectors, Proceedings of the 2009 ACM SIGPLAN/SIGOPSinternational conference on Virtual execution environments. -Washington, DC, USA, 2009.

50. Greg Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures. Velen, Germany, 1993. - C. 261-270.

51. H. Gao , W. H. Hesselink, A general lock-free algorithm using compare-and-swap. — Information and Computation, February, 2007. C. 225-241.

52. M. Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), November, 1993. C. 745-770.

53. E.H. Jensen, G.W. Hagensen, J.M. Broughton, A new approach to exclusive data access in shared memory multiprocessors, Technical Report of Lawrence Livemore National Laboratory, January, 1987.

54. Victor Luchangco , Mark Moir , Nir Shavit, Nonblocking k-compare-single-swap, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, San Diego, California, USA, 2003.

55. Nancy A. Lynch, Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996.

56. John D. Valois, Lock-free linked lists using compare-and-swap, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing. Ontario, Canada, 1995. - C. 214-222.

57. V. Balasundaram , K. Kennedy, Compile-time detection of race conditions in a parallel program, Proceedings of the 3rd international conference on Supercomputing. Crete, Greece, 1989. - C. 175-185.

58. Robert H. B. Netzer , Barton P. Miller, What are race conditions?: Some issues and formalizations. ACM Letters on Programming Languages and Systems (LOPLAS), 1992. -C. 74-88.

59. M. L. Scott. Non-blocking timeout in scalable queue-based spin locks. In PODC '02: Proc. of the Twenty-first Annual Symposium on Principles of Distributed Computing. ACM Press, NY, USA, 2002. - C. 31-40.

60. Карпов А., Рыжков E. Применение технологии статического анализа кода при разработке параллельных программ, (http://www.viva64.com/art-3-l-441110260.html)

61. L. Wang, S. D. Stoller. Run-time analysis for atomicity, Electronic Notes in Theoretical Computer Science, 89(2), 2003.

62. S. V. Adve, K. Gharachorloo. Shared memory consistency models: A tutorial. Computer, 29(12), 1996.

63. Т. Е. Anderson. The performance of spin lock alternatives for sharedmoney multiprocessors, IEEE Transactions on Parallel and Distributed Systems, 1(1):6-16, 1990.

64. N. S. Arora, R. D. Blumofe, and C. G. Plaxton. Thread scheduling for multiprogrammed multiprocessors. In Proc. of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures. ACM Press, USA, 1998. - C. 119-129.

65. H. Gao, J. F. Groote, W. H. Hesselink. Lock-free dynamic hash tables with open addressing, Distributed Computing, 18(1), 2005. C. 21-42.

66. D. Hendler, N. Shavit, L. Yerushalmi. A scalable lock-free stack algorithm. In SPAA '04: Proc. of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. ACM Press, NY, USA, 2004. - C. 206-215.

67. M. Herlihy, Y. Lev, N. Shavit. A lock-free concurrent skiplist with wait-free search. Unpublished Manuscript, Sun Microsystems Laboratories, Burlington, Massachusetts, 2007.

68. M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free data structures. In Proc. of the Twentieth Annual International Symposium on Computer Architecture. ACM Press, San Diego, California, 1993. - C. 289-300.

69. M.Bach. The design of the UNIX operating system. -Prentice Hall, Englewood Cliffs, N.J., 1986.

70. Intel Corporation. Pentium Processor User's Manual. Intel Books, 1993.http://www.intel.com/design/Pentium4/documentation.htm)

71. M. Li, J. Tromp, and P. M. B. Vit'anyi. How to share concurrent wait-free variables. Journal of the ACM, 43(4). -ACM Press, 1996. C. 723-746.

72. P. E. McKenney. Selecting locking primitives for parallel programming. Communications of the ACM, 39(10) ACMPress, 1996. С. 75-82.http://portal.acm.org/citation.cfm?id=236156.236174)

73. M. M. Michael, М. L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proc. of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing. ACM Press, 1996. - C. 267275.

74. M. Raynal. Algorithms for Mutual Exclusion. The MIT Press, Cambridge, MA, 1986.

75. P. Marginean, Lock-Free Queues, Dr. Dobb's Journal, July 2008.

76. Карпов В.E., Коньков К.А. Основы операционных систем. М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий», 2005.

77. Т. Кормен, Ч. Лейзерсон. Р. Ривест Алгоритмы: построение и анализ -М.: Москва, 2004.

78. Н. Sutter, The Trouble With Locks, C/C++ Users Journal, March 2005.

79. Herb Sutter, Lock-Free Code: A False Sense of Security, Dr. Dobb's Journal, 33(9), 2008.