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

• Воеводин, Вадим Владимирович
• кандидат физико-математических наук
• 2011

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

Введение.

Глава 1. Вычислительные системы и эффективность выполнения программ.

1.1 Проблемы разработки параллельного программного обеспечения.

1.2 Отображение алгоритмов на архитектуру параллельных вычислительных систем.

1.3 Средства исследования и повышения эффективности выполнения программ.

1.4 Направление исследований и постановка задачи.

Глава 2. Исследование процесса отображения алгоритмов на вычислительные платформы.

2.1 Общее описание подхода.

2.2 Характеристики алгоритма.

2.3. Характеристики программы.

2.4 Характеристики вычислительных систем.

Глава 3. Взаимодействие с памятью и эффективность выполнения программ.

3.1 Формальное описание характеристик работы с памятью.

3.2 Общие характеристики работы с памятью.

3.3 Тонкие характеристики работы программ с памятью.

3.4. Визуализация взаимодействия программ с памятью.

Глава 4. Исследование структуры программ и алгоритмов.

4.1 Характеристики алгоритма для типовых алгоритмических структур.

4.2 Характеристики работы с памятью для типовых алгоритмических структур.

4.3. Шаблоны профилей и свойства локальности.

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

Развитие высокопроизводительной вычислительной техники, постоянно происходившее все последние годы, сопровождается целым набором важных особенностей. Определить их не сложно, для чего можно воспользоваться различными средствами, например, аккуратно проанализировать список Тор500 самых мощных компьютеров мира. Анализ вышедших редакций списка сразу указывает на невероятно устойчивый рост производительности суперкомпьютеров. Каждые 10-12 лет их производительность увеличивается на три порядка, что верно как для систем с рекордной производительностью из первой десятки, так и для аутсайдеров списка.

Вместе с этим, обратной стороной медали постоянного роста производительности суперкомпьютерных систем является резкое снижение эффективности выполнения параллельных программ. Даже на оптимизированном тесте Ыпраск с хорошо известной структурой, являющегося основой для составления списка Тор500, эффективность многих вычислительных систем не превышает 50%, поэтому и эффективность в 3-5% у многих реальных приложений не вызывает большого удивления. Компьютеры теоретически могут многое, но достичь максимальных показателей на практике крайне сложно, а зачастую просто невозможно.

Проблема низкой эффективности приложений была замечена давно, но в последние годы разница между пиковыми и реальными показателями производительности стала особенно заметной. Причин этому несколько, одна из них - это стремительный рост степени параллелизма в архитектуре современных вычислительных систем. На перспективу эта тенденция явно будет продолжаться, и ожидается, что экзафлопсные вычислительные системы будут объединять в своем составе сотни миллионов независимо работающих ядер. Важно и то, что идеи параллельной обработки з распространяются по всем уровням их архитектуры. Векторная обработка, суперскалярность, конвейерность, У1Л\¥-архитектура, гипертрейдинг, многоядерность, распределенная обработка - все это, как и многое другое, используется в современных суперкомпьютерах, являясь проявлением различных сторон параллелизма. Другой не - менее серьезной причиной снижения эффективности программ является сложная структура подсистем памяти в современных компьютерах. Давно подмечено, что скорость работы процессора намного превышает скорость работы оперативной памяти, из-за чего при выполнении операций чтения/записи процессор вынужден простаивать в ожидании завершения работы с данными.

Что происходит в реальных программах? Вопрос крайне важный, но далеко не однозначный. Многое определяется использованным для решения исходной задачи методом, алгоритмом, конкретной технологией программирования, стилем написания программ. В конечном итоге, все определяется тем, насколько хорошо соответствуют свойства программ и алгоритмов особенностям архитектуры вычислительных систем. Еще в конце 80-х годов прошлого столетия академик Г.И.Марчук сформулировал задачу отображения структуры программ и алгоритмов на архитектуру компьютеров, являющейся первичной при исследовании эффективности. Многие известные российские и зарубежные ученые внесли вклад в решение задачи отображения. Но, несмотря на значительный возраст самой проблемы, в настоящее время можно с уверенностью говорить не о найденном решении задачи отображения, а о решении множества более частных задач.

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

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

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

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

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

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

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

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

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

В заключении сформулированы основные результаты диссертационной работы.

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

Заключение

В заключение сформулируем основные результаты, полученные в диссертационной работе.

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

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

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

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

1. Воеводин 2009. Воеводин В.В. Доклад в рамках Всероссийской школы "Суперкомпьютерные технологии" 31 октября 2010 г. http://www.intuit.ru/video/70/

2. IESP 2011. Текущая версия документа, описывающего выполняемые в рамках проекта IESP работы.http://www.exascale.Org/mediawiki/images/2/20/IESP-roadmap.pdf

3. EESI. Описание Инициативы EESI. www.eesi-project.eu/

4. Марчук 1979. Марчук Г.И., Котов В.Е. Проблемы вычислительной техники и фундаментальные исследования // Автом. и вычисл. техн. 1979. №2. 3-14.

5. Воеводин 1991. Воеводин В.В. Математические основы параллельных вычислений// М., Изд-во МГУ, 1991, 345 с.

6. Воеводин 1997. Воеводин В.В. Информационная структура алгоритмов // М., Изд-во Моск. ун-та, 1997, 139 с.

7. Воеводин 2000. Воеводин В.В. Отображение проблем вычислительной математики на архитектуру вычислительных систем. // Тр. меж дун. конфер. "Выч. мат. и мат. моделир."ИВМ РАН, т.1, 2000. 14 стр.

8. Ершов 1973. Ершов А.П. Современное состояние теории схем программ //В сб.: Проблемы кибернетики, №27. 1973. С. 193-204.

9. Moldovan 1983. Moldovan D.I. On the design of algorithm for VLSI systolic arrays III IEEE Proc. 1983.

10. Воеводин 2002. Воеводин B.B., Воеводин Вл.В. Параллельные вычисления // СПб., БХВ-Петербург, 2002, 608 с.

11. Воеводин 2006. Воеводин В.В. Вычислительная математика и структура алгоритмов // М.: Изд-во МГУ, 2006.-112 с.

12. Asanovic 2008. Asanovic К. et al. The Parallel Computing Laboratory at UC Berkeley: A Research Agenda Based on the Berkeley View // UC Berkeley Electrical Engineering and Computer Sciences, Department Technical Report UCB/EEECS-2008-23, March 2008.

13. Asanovic 2006. Asanovic, K. et al. The Landscape of Parallel Computing Research: A View from Berkeley // UCB/EECS-2006-183, University of California, Berkeley, Dec. 18, 2006.

14. Colella 2004. P. Colella, "Defining Software Requirements for Scientific Computing," presentation, 2004.

15. Luco 1991. Lucco, S. and O. Sharp (1991). "Parallel programming with coordination structures." Annual Symposium on Principles of Programming Languages, 1991.

16. Gelernter 1992. Gelernter, D. andN. Carriero (1992). "Coordination languages and their significance" Commun. ACM 35(2): 97-107.

17. Linpack 1979. LINPACK Users Guide, J. Dongarra, J. Bunch, C. Moler and G. W. Stewart, SIAM, Philadelphia, PA, 1979.

18. Dongarra 1989. Performance of Various Computers Using Standard Linear Equations Software, J. Dongarra, Technical Report CS-89-85, University of Tennessee, 1989.

19. Top500. Список Top500 самых высокопроизводительных систем в мире [Электронный доступ]: http://www.top500.org/

20. НРСС. Набор тестов НРС Challenge [Электронный доступ]: http://icl.cs.utk.edu/hpcc/

21. Graph500. Список Graph500 самых высокопроизводительных систем в мире [Электронный доступ]: http://www.graph500.org/

22. NPB. Набор тестов NAS Parallel Benchmarks [Электронный доступ]: http://www.nas.nasa.gov/Resources/Software/npb.html

23. Deep Blue. Описание компьютера Deep Blue. http://www.research.ibm.eom/deepblue/meet/html/d.3.shtml

24. Deep Crack. Описание компьютера Deep Crack. http://en.wikipedia.org/wiki/DeepCrack

25. MDGrape-3. Описание компьютера MDGrape-3. http://mdgrape.gsc.riken.ip/modules/mdgrape3/index.php

26. QPACE. Описание компьютера QPACE. http://www-zeuthen.desy.de/technischesseminar/texte/cellprocessor.pdf

27. Bailey 2010. Bailey D. H., Lucas R.F., Williams S. Performance tuning of scientific applications // CRC Press, 2010. 399 p.

28. Wulf 1995. W.A. Wulf and S.A. McKee, "Hitting the Memory Wall: Implications of the Obvious," Computer Architecture News, vol. 23, no. 1, Mar. 1995, pp. 20-24.

29. PAPI. Документация по библиотеке PAPI. http://icl.cs.utk.edu/projects/papi/wiki/MainPage

30. Intel Compiler. Описание компилятора Intel Compiler. http://software.intel.com/sites/products/documentation/hpc/compileфro/en-us/cpp/lin/compilerc/index.htm

31. Optimization 1. Описание различных способов оптимизации при компиляции.http ://www. eetimes. com/electronics-products/embedded-tools/4086427/Advanced-Compiler-Qptimization-Techniques

32. Optimization2. Приемы оптимизации компиляции для AIX.3 6. http: / / publib .boulder Jbmxom/mfocenter/aix/v6rl/index.isp?topic=/com.ibm.aix.prftungd/doc/prftungd/comp opttech.htm

33. HyperThreading. Описание технологии HyperThreading. http://www.intel.com/cd/corporate/techtrends/emea/rus/platform-technology/hyper-threading/3 69646. htm

34. Two Strong Threads. Описание технологии Two Strong Threads. http://www.thg.ru/cpu/amdbulldozerbobcat/index.html

35. Blelloch. Классификация языков программирования. http://www.cs.cmu.edu/~scandal/parallel-lang.html

36. БПФ с прореживанием. Описание БПФ с прореживанием по времени -http://dsplib.ru/content/thintime/thintime.html42. рекурсивный БПФ. Описание рекурсивной реализации БПФ -http://www.engineeringproductivitytools.com/stuff/T0001/PTQ4.HTM