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

• Соколов, Евгений Владимирович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Соколов, Евгений Владимирович

Содержание.

Введение.

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

Цели диссертационной работы.

Методы исследования.

Научная новизна работы.

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

Положения, выносимые на защиту.

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

1 Алгоритмы синхронизации данных.

1.1 Важность синхронизации потоков. Закон Амдала.

1.2 Синхронизация потоков. Критические секции.

1.2.1 Алгоритм Петерсона.

1.2.2 Переупорядочивания операций.

1.2.3 Алгоритм булочной.

1.3 Снимки памяти.

1.4 Неупорядоченный доступ к данным в архитектуре графических процессоров CUDA.

2. Избыточное хранения данных.

2.1 Обзор систем избыточного хранения данных.

2.2 Модель избыточного хранения данных, основанная на (w. А:) -схеме.

2.3 Построение (п, к)-пороговая схемы.

2.4 Алгоритмы (п,к)-пороговой схемы.

3. Математическая модель примитива синхронизации типа «снимок памяти».

4. Вычисления в полях Галуа.

Алгоритмы вычислений в полях Галуа.

Алгоритм Эвклида.

Логарифмическое умножение.

Сведение к вычислениям в подполях.

Таблицы умножения.

5. Способы увеличения скорости преобразований по in, к") -схеме.

5.1 Алгоритмы «упрощенного» преобразования по £) -схеме.

5.2 Алгоритмы умножения в полях Галуа с использованием векторных команд.

5.3 Распараллеливание на несколько потоков.

5.4 Результаты повышения производительности.

Введение диссертации (часть автореферата) на тему «Моделирование синхронизации доступа к данным на основе избыточного хранения»

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

Современные информационные системы обрабатывают всё возрастающие объемы данных, которые требуют как высокой производительности компьютеров, так и места для хранения информации. Для обеспечения сохранности данных применяются различные способы, основанные, в первую очередь, на хранении с избыточностью.

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

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

Цели диссертационной работы

Целью данной работы является разработка математической модели примитива синхронизации типа «снимок памяти» на основе алгоритма избыточного хранения данных. Модель гарантирует целостность данных и позволяет обходиться без блокировки системной шины данных. Кроме этого, работа направлена на ускорение работы алгоритма избыточного хранения данных на процессорах общего назначения как за счет ускорения вычислений в полях Галуа, так и за счет изменения свойств самих алгоритмов.

Методы исследования

В работе использовались методы теории алгоритмов, системного программирования и дискретной математики.

Предложенные модели реализованы в виде комплекса программ. Проведён ряд вычислительных экспериментов с использованием этого комплекса.

Научная новизна работы

1. Предложена математическая модель примитива синхронизации типа «снимок памяти», гарантирующего целостность данных. Модель включает ограничения нового типа, разница между количеством 5 операций читателя и писателя не превышает заданного максимума. Преимуществом модели является то, что её применение позволяет не использовать блокировки, которые обычно используются в реализации примитивов синхронизации.

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

Yl ^ k

--. ч . —— раз, где п-количество частей, на которые п — к)* (к — 1) разбиваются данные, к -количество частей, необходимых для восстановления данных (А: < л?) . Увеличение скорости работы является существенным при сопоставимых значениях параметрах п и к. Например, При п = 5 и к = 3 ускорение составляет 3.75 раза. Алгоритмы основываются на преобразованиях матрицы Вандермонда к упрощенному виду. При этом основное свойство матрицы - любые пш к строк являются линейно независимыми и могут образовывать базис в к-мерном пространстве - остается неизменным.

3. Разработан алгоритм умножения нескольких элементов поля Галуа GF(24) с использованием векторных команд процессора. Алгоритм позволяет параллельно производить серию умножений вида (а0,аг.ар) & Ъ = (cQr)cx.c, где а,Ь,с - элементы поля GF(24), используя последовательность векторных операций процессора общего назначения архитектуры х86 (SIMD-команды). В отличие от известных алгоритмов количество необходимых процессорных инструкций не зависит от количества умножаемых элементов, что позволяет значительно увеличить производительность (т?, к) -схемы.

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

Предложенные модели и алгоритмы могут быть использованы на практике. Модель типа «снимок памяти» обеспечивает решение проблемы «противоречивой информации» без использования блокировок и сокращение времени простоя процессора.

Полученные в диссертационной работе результаты позволяют существенно ускорить работу систем хранения данных, основанных на in, к) - схеме.

Результаты исследования были реализованы в продуктах компании Acronis.

Положения, выносимые на защиту

1. Математическая модель примитива синхронизации типа «снимок памяти» на основе избыточного хранения данных, гарантирующего целостность данных при накладывании ограничения на темп доступа к памяти.

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

3. Эффективный алгоритм параллельного умножения чисел в поле Галуа GF(24) с использованием векторных команд.

Краткое содержание диссертации

Структура о объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка использованных источников,

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Соколов, Евгений Владимирович

Приведем в заключение основные результаты и выводы работы:

1. Разработана математическая модель примитива синхронизации типа «снимок памяти» на основе избыточного хранения данных, гарантирующего целостность данных при накладывании ограничения на темп доступа к памяти.

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

3. Предложен эффективный алгоритм параллельного умножения чисел в поле Галуа GF(24) с использованием векторных команд.

Список литературы диссертационного исследования кандидат физико-математических наук Соколов, Евгений Владимирович, 2009 год

1. D. Patterson, G. Gibson, R. Katz. A Case for Redundant Arrays of Inexpensive Disks (RAID). /University of California. Berkeley 1987. —26 p.

2. Б. Ван дер Варден. Алгебра. — М.: Наука. 1979. — 648 с.

3. Е. Win, A. Bosselaers, S. Vanderberghe, P. Gersem, J. Vandewalle. A Fast Software Implementation for Arithmetic Operations in GF(2n). / Katholieke Universiteit Leuven. 1997. — 12 p.

4. Intel 64 and IA-32 architecture software developer's manual, vol. ЗА: system programming guide, part 1.http://www.intel.com/design/processor/manuals/253668.pdf

5. A. Stailings. Data and Computer Communications. Sixth Edition.

6. New Jersey: Prentice Hall. 1999. — 810 p.

7. J. Adamek. Foundations of Coding. — Wiley: Interscience. 1991.336 p.

8. А. Курош. Курс высшей алгебры. — M.: Наука. 1975. — 431 с.

9. V. Hamann. Making Internet Servers Fault-Tolerant A Comprehensive Overview. / Материалы конференции "Interner-Россия 96". — 7 p.

10. H. Kameda, J. Li, C. Kim, Y. Zhang. Optimal Load Balancing in Distributed Computer Systems (Telecommunication Networks and Computer Systems). — Berlin: Springer Verlag. 1996. — 251 p.

11. W. Richard Stevens. TCP/IP Illustrated vol. 1-3. — Addison: Wesley Pub Co. 1994. — 2078 p.

12. D. Libertone, M. Brain. Windows NT Cluster Server Guidebook. — New Jersey: Prentice Hall. 1998. — 280 p.

13. A. Shamir. How to share a secret. Communications of the ACM // vol. 24. 1979. — pp. 612 - 613.

14. G. Blakley. Safeguarding cryptographic keys. Proceeding of AFIPS // vol. 48. 1979. — pp. 313 - 317.

15. E. Brickell, D. Devenport, On the classification of ideal secret schemes, Journal of Cryptology, vol. 4, pp. 123-134, 1991.

16. G. Simmons, An introduction to shared secret and/or shared control schemes and their applications, Contemporary Cryptology, IEEE Press, Piscataway, NY, pp.441-497, 1992.

17. E.D. Mastrovito, "VLSI Architectures for Computation in Galois Fields," PhD thesis, Dept. of Electrical Eng., Linkoping Univ., Linkoping, Sweden, 1991.

18. Peter J. Braam, The Coda Distributed File System, Carnegie Mellon University, html. (http://www.coda.cs.cmu.edu/lipaper/li.html).

19. Peter J. Braam, Coda Authentication and Protection, html. (http://www.coda.cs.cmu.edu/doc/html/sec.htmiy

20. A. Tanenbaum, Distributed Operation Systems, M: Prentice Hall, 1995.

21. Ван Стеен Маартен Распределенные системы. Принципы и парадигмы М: Питер, 2003. - 880 с.

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

23. Кудрявцев Л.Д. Курс математического анализа М. Наука, 1981, т.1,2.

24. Laszlo Lovasz, Computation Complexity. pdf. (http://www.cs.bu.edu/~gacs/papers/lovasz-notes.pdf).

25. Пименов В.М., Соколов Е.В., Кобец A.JI. Способы увеличения производительности алгоритмов для отказоустойчивых систем хранения данных // Вестник НГУ. Серия: Информационные технологии -2007. Т. 5, вып. 1. С. 32-39.

26. Кобец A.JL, Луковников В.В., Пименов В.М., Соколов Е. В. Оценка точности группового наложенного управления ресурсами операционной системы для дискового ввода / вывода. //Вестник НГУ. Серия: Информационные технологии -2007, Т. 5, вып. 1-С. 28-31.

27. Соколов Е.В., Кудрин М.Ю. Применение (п, к)-схемы для реализации алгоритмов енэпшота памяти. // XXXV Гагаринские чтения. Научные труды Международной молодежной научной конференции в 8-ми томах. Москва, 2009.-Т. 4-С. 155.

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

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

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

31. Тормасов А.Г., Хасин М.А., Пахомов Ю.И. Модель распределенного хранения данных с регулируемой избыточностью // Электронный журнал «Исследовано в России». 2001. т. 4. С. 355-364. http://zhurnaLape.relarn.ru/articles/2001/035.pdf

32. Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of shared memory // Journal of the ACM (JACM). 1993. Issue 4. P. 873 890. 1993.

33. Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup Lock-free Dynamically Resizable Arrays Texas A&M University http://www.research.att.com/~bs/lock-free-vector.pdf

34. Herlihy, Maurice; Shavit, Nir. The art of Multiprocessor Programming 2008. 508 p. Morgan Kaufmann ISBN-13: 9780123705914

35. Б. Ван дер Варден, Алгебра, М. Наука, 1979.

36. Hans-J. Boehm. Memory model for Multithreaded С++ // HP Labshttp://www.hpl.hp.com/personal/Hans Boehm/c++mm/mmissues.pdf

37. Danny Dolev, Nir Shavit. Bounded concurrent time-stamping. // Society for Industrial and Applied Mathematics. Vol. 26, No. 2, pp. 418-455, April 1997

38. Paar C. Efficient VLSI Architectures for Bit-Parallel Computation in Galois Fields. PhD thesis (English translation). Inst, for Experimental Math., Univ. of Essen. Essen, 1994.

39. Пименов В. M., Сметанин А. Г. Использование программируемых графических процессоров в задачах хранения данных // Проблемы вычислительной математики,математического моделирования и информатики. М.: МЗ Пресс, 2006. С. 138-157.

40. А. Тормасов, М. Хасин, Ю. Пахомов, Обеспечение отказоустойчивости в распределенных средах// журнал "Программирование" N 5 сс. 26-34 2001.

41. М. Хасин, Применение (N,k)-noporoBbix схем для обеспечения доступности Интернет-серверов, научные труды ДГТУ, выпуск 29, серия: Проблемы моделирования и автоматизации проектирования динамических систем, сс. 285291 ,Севастополь-ВЕБЕР, 2001.

42. М. Хасин, Методики хранения информации с регулируемой избыточностью/ Моделирование моделирование обработки информации и процессов управления, сс. 23-34, Москва, 2001.

43. Петров В.А. "Моделирование переноса и поиска данных в децентрализованной распределенной системе, использующей N-k-схему хранения информации", кандидатская диссертация, кафедра информатики, 2008

44. Хасин М.А. "Модель распределенного хранилища в глобальной сети", кандидатская диссертация, кафедра информатики, 2001

45. Reed, I. and Solomon, G., Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics. v8. 300-304.

46. James S. Plank, A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems, Software—Practice & Experience, v.27 n.9, p.995-1012, Sept. 1997

47. Ling Zhuo , Viktor K. Prasanna, High Performance Linear Algebra Operations on Reconfigurable Systems, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.2, November 12-18, 2005

48. R. E. Blahut. Theory and Practive of Error Control Codes. Reading, MA: Addison-Wesley, 1984.

49. F.J.Mac Williams and N.J. Sloane, The Theary of Error-Correcting Codes. Amsterdam: North-Holland, 1986.

50. H.C.A. van Tilborg, An Introduction to Cryptology, Boston: Kluwer Academic Publ., 1988

51. B. Benjauthrit, I.S. Reed, Galois Switching functions and their Applications, IEEE Trans. Comput., Vol. C-25, pp. 78-86, January 1976.

52. I.S. Reed, Т.К. Thuong, The Use of Finite Fields to Compute Convolutions, IEEE Trans. Inform. Theory, vol. IT-21, No.2, pp.208-213, March 1975.

53. J. H. McClellan, С. M. Rader, Number Theory in Digital Signal Processing, Englewood Cliffs: Prentice-Hall, 1979.

54. W. Diffie, M. E. Hellman, New directions in Cryptography, IEEE Trans. Inform. Threory, IT-22, pp.644-654, 1976.

55. A. M. Odlyzko, Discrete Logarihms in Finite Fields and their Cryptographic Significance, Adv. Cryptol., Proc. Eurocypt '84, Paris, France, pp. 224-314, April 1984.

56. В. Smeets, Some results on Linear Recurring Sequences, PhD Dissertation LUTEDX/(TEDD-1007)/1-129 (1987), Lund University, Lund, March 1987.

57. С. C. Wang, D. Pei, A VLSI Design for Computing Exponentiations in GF(2m) and Its Application to Generate Pseoderandom Number Sequences, IEEE Trans. On Comput., Vol. C-39, No. 2. Pp. 258-262, February 1990.

58. NVIDIA CUDA Compute Unified Device Architecture, Programming Guide, version 1.0. NVIDIA Corporation, 2007.

59. Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985

60. Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v. 13 n.l, p.124-149, Jan. 1991

61. J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26(1):80—113, 2007.

62. Phuong Hoai Ha , Philippas Tsigas , Otto J. Anshus, Non-blocking programming on multi-core graphics processors: (extended asbtract), ACM SIGARCH Computer Architecture News, v.36 n.5, December 2008

63. Philippas Tsigas , Yi Zhang, Integrating non-blocking synchronisation in parallel applications: performance advantages and methodologies, Proceedings of the 3rd international workshop on Software and performance, July 24-26, 2002, Rome, Italy

64. Tushar Chandra , Vassos Hadzilacos , Prasad Jayanti , Sam Toueg, Generalized Irreducibility of Consensus and the Equivalence of t-Resilient and Wait-Free Implementations of Consensus, SIAM Journal on Computing, v.34 n.2, p.333-357, 2005

65. Э. M. Габидулин, В. А. Обернихин. Коды в F-метрике Вандермонда и их применение, Пробл. передачи информ., 39:2 (2003), 3-14

66. Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming1.nguages and Systems (TOPLAS), v. 15 n.5, p.745-770, Nov. 1993

67. Arjan J. C. van Gemund, The importance of synchronization structure in parallel program optimization, Proceedings of the 11 th international conference on Supercomputing, p. 164-171, July 0711, 1997, Vienna, Austria

68. А. Г. Тормасов. Основы аппаратного обеспечения выполнения параллельных программ на разделяемой памяти. Учебное пособие. Москва, Долгопрудный, 2009.

69. М. Dubois , С. Scheurich , F. Briggs, Memory access buffering in multiprocessors, ACM SIGARCH Computer Architecture News, v. 14 n.2, p.434-442, June 1986

70. A. E. Умнов. Аналитическая геометрия и линейная алгебра. Серия «Лекции кафедры высшей математики МФТИ», 2002

71. Eshrat Arjomandi, William O'Farrell, Concurrency issues in С"14", Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada

72. N. H. Gehani, Capsules: A Shared Memory Access Mechanism for Concurrent C/C++, IEEE Transactions on Parallel and Distributed Systems, v.4 n.7, p.795-811, July 1993

73. Tony P. Ng, Using histories to implement atomic objects, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.360-393, Nov. 1989

74. M. Dubois, Throughput Analysis of Cache-Based Multiprocessors with Multiple Buses, IEEE Transactions on Computers, v.37 n.l, p.58-70, January 1988

75. Zhiyuan Li , Walid Abu-Sufah, A technique for reducing synchronization overhead in large scale multiprocessors, ACM SIGARCH Computer Architecture News, v.13 n.3, p.284-291, June 1985

76. A. Silberschatz, "Communication and synchronization in distributed programs." IEEE Trans. Softw. Eng. SE-5, 6 (Nov. 1979), 542-546.

77. John Reif , Paul Spirakis, Unbounded speed variability in distributed communication systems, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.46-56, January 25-27, 1982, Albuquerque, Mexico

78. D. B. Lomet, Process structuring, synchronization, and recovery using atomic actions, Proceedings of an ACM conference on Language design for reliable software, p. 128-137, March 28-30, 1977, Raleigh, North Carolina

79. P. E. Lauer , M. W. Shields, Abstract specification of resource accessing disciplines: adequacy, starvation, priority and interrupts, ACM SIGPLAN Notices, v. 13 n.12, p.41-59, December 1978

80. Butler W. Lampson, Atomic Transactions, Distributed Systems -Architecture and Implementation, An Advanced Course, p.246-265, January 1981

81. David Gelernter , Arthur J. Bernstein, Distributed communication via global buffer, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p. 10-18, August 18-20, 1982, Ottawa, Canada

82. P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with "readers" and "writers", Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971

83. CONWAY, M.E. "A multiprocessor system design." In Proc. AFIPS Fall Jt. Computer Conf. (Las Vegas, Nev., Nov., 1963), vol. 24. Spartan Books, Baltimore, Maryland, pp. 139-146. (b)

84. Per Brinch Hansen, Concurrent Programming Concepts, ACM Computing Surveys (CSUR), v.5 n.4, p.223-245, Dec. 1973

85. Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v. 13 n.2, p. 185-221, June 1981

86. M. Ben-Ari, Principles of concurrent and distributed programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990

87. Gregory R. Andrews, Synchronizing Resources, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.405-430, Oct. 1981

88. Bard Bloom, Constructing two-writer atomic registers, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.249-259, August 10-12, 1987, Vancouver, British Columbia, Canada

89. James E. Burns , Gary L. Peterson, Constructing multi-reader atomic values from non-atomic values, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.222-231, August 10-12, 1987, Vancouver, British Columbia, Canada

90. Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.l, p.77-97, Jan. 1987

91. Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988

92. Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985

93. Ray Ford , Jim Calhoun, Concurrency control mechanisms and the serializability of concurrent tree algorithms, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada

94. M.P. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1): 124—149, January 1991

95. Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems,

96. Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.59-70, August 1985, Minaki, Ontario, Canada