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

• Автор: Воеводин, Вадим Владимирович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 144 с. : ил.

Оглавление
ВведениеЗ

Глава 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. Шаблоны профилей и свойства локальности.
Заключение
Список литературы


Регистры, кэшпамять разных уровней, оперативная память, TLB буфер, аппаратный префетчер - каждый из этих компонентов подсистемы памяти обладает целым набором аппаратных свойств, которые необходимо учитывать для организации эффективной работы с памятью. Не менее остро стоит проблема эффективного использования заложенного в аппаратуре параллелизма. Для того чтобы иметь возможность максимально распараллеливать выполнение операций, необходимо учитывать большое число различных свойств аппаратуры. Например, в случае кластерной системы, эго топология сети, строение узлов кластера, латентность и пропускная способность сети, число различных функциональных устройств, число портов для доступа к этим устройствам, скорость выполнения операций и т. Помимо этого, также могут оказывать влияние различные программные факторы, такие как, например, свойства выбранной технологии программирования или компилятора. Данная работа преследует две цели. Первая цель - провести комплексное исследование всех этапов процесса отображения структуры программ и алгоритмов на архитектуру вычислительных систем. Вторая цель заключается в том, чтобы выделить и описать основные характеристики работы программ с памятью. Достижение указанных двух целей позволит снять целое множество вопросов, связанных с разработкой эффективного программного обеспечения для современных вычислительных систем. Для того чтобы учитывать сложности, описанные в предыдущем разделе, и получить эффективную реализацию алгоритма на некоторой аппаратной платформе, необходимо исследовать всю задачу отображения, от начала и до конца. Задача отображения - это задача выбора наилучшей реализации выбранного алгоритма на выбранной платформе. Часть процесса отображения, в основном связанная со свойствами алгоритма, не зависит от выбираемой аппаратуры, и соответствующая часть исследования задачи отображения машинно-независима. С этой точки зрения такое исследование позволит решать не только задачи эффективного использования выбранной аппаратуры, но и более общие задачи эффективности, не связанные с определенной аппаратной платформой. Подобных задач много. К таким задачам относится, например, задача подбора наилучшей аппаратной платформы для определенного алгоритма. Предположим, необходимо решить задачу N тел, на какой платформе она будет решаться быстрее всего - на обычной х платформе, на графическом процессоре или ПЛИС? И все указывает на то, что и далее этот процесс продолжится. Конечно, зачастую создаются различные средства автоматизированного и даже автоматического переноса, которые помогают, например, преобразовать MPI-программы, написанные на C++ для обычных х процессоров, в CUDA-программы для графических процессоров. Однако в подавляющем большинстве случаев эффективность таких перенесенных программ крайне невысока, поскольку нужно создавать не просто синтаксически правильно написанную программу, но и учитывать кардинальные изменения в архитектуре целевой вычислительной системы, соответствующим образом преобразуя семантику программы. Сделать это автоматически в большинстве случаев очень непросто. Основной идеей предлагаемого подхода решения данной задачи является детая ьное описание трех основных частей всего процесса отображения - алгоритма, программы и аппаратуры - с помощью набора свойств, оценивая которые, можно оценивать эффективность самого процесса отображения. Основные этапы процесса отображения представлены на рис. Для решения данной задачи необходимо на каждом этапе выделить те ключевые свойства каждого этапа, которые могут влиять на эффективность отображения, и затем определить степень их влияния и взаимосвязь. Анализируя найденные свойства, можно будет понять, что послужило причиной снижения эффективности в каждом конкретном случае. Выбранная технология программирования РоЛгезэ. СЬаре! Х, СиОА. Рис. Идеи решения задачи отображения, безусловно, появлялись и раньше. Одним из первых, кто еще в -х годах заговорил о необходимости исследования задачи отображения алгоритмов на аппаратные платформы, был академик Марчук Г. И. [Марчук ]. Также исследованиями в данной области в течение длительного времени занимался академик Воеводин В.