В настоящее время широко распространены рабочие станции и персональные компьютеры, содержащие несколько центральных процессоров. Массовые многопроцессорные системы обычно содержат 2, 4 или 8 процессоров, работающих над общей памятью с одинаковым для всех процессоров временем доступа (SMP). Для максимального использования возможностей SMP-систем в вычислительно-интенсивных приложениях необходимо максимально использовать "легковесные" процессы (нити). В этом случае накладные расходы на коммуникацию минимизированы, так как все нити разделяют одно адресное пространство, а синхронизационные операции выполняются проще и быстрее, чем для обычных ("тяжелых") процессов.

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

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

Системы с разделяемой памятью наиболее удобны для программиста параллельных приложений. Более того, часть работы по распараллеливанию последовательного кода может быть выполнена компилятором. Существует много исследований по автоматическому распараллеливанию циклов и рекурсивных процедур на таких системах. Некоторые разработки реализованы в промышленных компиляторах, например, IBM Visual Age C++, Intel C++ Compiler, SGI MIPSPro, REAPAR и других.

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

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

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

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

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

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

Упаковка данных в памяти (data packing) для увеличения количества событий пространственной локальности.

Перестановка процедур, базовых блоков и т.п.

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