Средства разработки приложений


Разбиение программ на нити и повышение локальности - часть 2


Предложено несколько подходов, таких, как управление выполнением нитей (thread-level speculation) [6], коммутативный анализ, динамическое распределение задач на нити (dynamic task scheduling) [5], автоматическое разделение на нити на этапе компиляции. Часть предложенных алгоритмов проверена авторами на эмуляторах, часть реализована в существующих исследовательских компиляторах, например, в компиляторе SUIF Стенфордского университета [7].

Формализация понятия локальности проведена в [8]. Рассматривается два вида событий локальности:

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

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

  1. Группировка инструкций, использующих одни и те же данные (locality grouping), для увеличения количества событий временной локальности.
  2. Упаковка данных в памяти (data packing) для увеличения количества событий пространственной локальности.
  3. Перестановка процедур, базовых блоков и т.п.

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




Начало  Назад  Вперед