ИСТИНА

Эффективность использования подсистемы памяти является одной из самых главных причин, влияющих на общую эффективность выполнения программ. Связанная с этим проблема получила название «стены памяти»: в течение уже многих лет скорость работы процессоров растет значительно быстрее скорости работы памяти. Чтобы сгладить это несоответствие, используют сложные способы организации подсистем памяти, что делает ее эффективное использование непростой задачей. Один из способов исследования эффективности взаимодействия программ с памятью – это изучение локальности работы с памятью на основе анализа последовательности обращений. При этом на практике оказывается, что многие задачи обладают схожими потоками обращений, и, значит, похожими свойствами работы с памятью. Это позволяет говорить о возможности выделения шаблонов обращений программ в память, отображающих свойства взаимодействия с памятью целого класса задач. Задача проекта – изучение свойств локальности обращений в память, разработка оценок для анализа данной локальности, а также определение и изучение понятия шаблона и выделение набора шаблонов для конкретных классов задач. Знание свойств шаблонов позволит как оценивать работу с памятью для всех задач из того же класса, так и оценивать эффективность взаимодействия с памятью произвольных программ.

В рамках данного проекта были получены следующие результаты. Разработан инструментарий для получения профилей обращений в память, основанный на замене типа исследуемой структуры данных в программе. С помощью данного инструментария были получены и затем проанализированы профили для множества различных программ и бенчмарков. Разработана новая машинно-независимая оценка локальности (cvg) на основе предложенного метода покрытий, которая определяется как пространственной, так и временной локальностью. Данная оценка позволяет с достаточной точностью определять степень локальности программ, при этом она удовлетворяет предъявленным требованиям и является машинно-независимой, при этом достаточно простой в понимании. Также была разработана машинно-зависимая оценка daps, определяющая реальную производительность работы с памятью. Данная оценка дополняет разработанную машинно-независимую оценку, что позволяет с разных сторон оценить качество взаимодействия программ с памятью. Было выполнено исследование потенциала метода покрытий для разработки других оценок, а также альтернативных методов анализа локальности, которые позволили бы повысить точность оценки. В частности, была проанализирована применимость модификаций оценки cvg. Выполненный анализ показал, что оценка cvg обладает наибольшей точностью из изученных машинно-независимых оценок. Была выполнена модификация разработанных методов для оценки работы с памятью на случай параллельных программ. Новый метод позволяет оценивать локальность и производительность программ, написанных с применением технологий OpenMP. Показана апробация предложенных оценок на нескольких многопоточных программах. На основе разработанных методов был предложен и апробирован стандарт описания локальности и взаимодействия с памятью в целом для различных программ. Данный стандарт совмещает качественную оценку на основе анализа визуального представления профиля обращений и количественного анализа с помощью предложенных оценок cvg и daps. Предложен метод определения классов программ на основе ранжирования с использованием оценки локальности cvg; при этом шаблонами классов являются типовые программы с хорошо изученной локальностью. Приведено описание этих классов, а также рассмотрена принадлежность изученных программ и тестов к выделенным классам. Составлен банк шаблонов, которые являются типовыми представителями текущего набора классов. Для каждого шаблона составлено описание свойств работы с памятью, а также влияние этих свойств на локальность шаблона. Данные описания составлены на основе изучения профиля обращений в память. На основе исследованных программ были выделены типовые фрагменты обращений в память. Типовые фрагменты представляют собой группу профилей обращений, обладающих определенным характерным поведением, которое встречается в реальных программах. Анализ локальности данных профилей, выполненный один раз, позволяет лучше понять структуру множества профилей обращений в память, в которых он был найден. Было выделено 4 группы типовых фрагментов, в зависимости от их строения – фрагменты с модификациями последовательного перебора, циклической структурой, вариантами случайного доступа и другие. Приведены примеры оптимизации взаимодействия программ с памятью на основе разработанных методов оценки локальности. Для каждой программы было рассмотрено несколько вариантов, полученных путем эквивалентных преобразований, и для этих вариантов были получены оценки работы с памятью. На основе анализа полученных оценок и профилей обращений в память в каждом случае сделан вывод относительно того, какой из рассмотренных вариантов является наилучшим.