Модель выполнения программы в ядре

При выполнении программы в вычислительной системе протекают параллельно следующие процессы:

читаются и подготавливаются к выполнению команды;

работает кэш-память первого уровня;

работает кэш-память второго уровня;

работает кэш-память третьего уровня;

работают функциональные устройства в каждом ядре;

работает оперативная память.

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

Однако, времена выполнения ряда процессов невозможно предсказать. В частности, не зная точной структуры выполняемой программы (какие команды за какими следуют, какие команды зависят от результатов предшествующих команд, сколько условных переходов, какое количество команд каждого вида и т.п.) нельзя предсказать времена выполнения команд в функциональных устройствах.

Общее время выполнения программы будет не меньше времени выполнения самогого длительного этапа из параллельно выполняемых.

Ядро с некоторой интенсивностью (среднее значение интервала между соседними запросами ) при выполнении команд обращения в память обращается в кэш-память первого уровня. При удачном обращении с вероятностью запрос обслуживается за время и команда завершается. В случае неудачи в кэш-памяти первого уровня с вероятностью генерируется запрос к кэш-памяти второго уровня. При удачном обращении с вероятностью запрос обслуживается кэш-памятью второго уровня за время и команда завершается.

В случае неудачи в кэш-памяти второго уровня с вероятностью генерируется запрос к кэш-памяти третьего уровня. Если буфер заявок в кэш-память третьего уровня заполнен, то ядро блокируется (прекращает генерировать заявки).

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

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

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

При отсутствии заявок во входных буферах кэш-память третьего уровня простаивает.

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

При отсутствии заявок во входных буферах коммутатор 2 простаивает.

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

При отсутствии заявок во входном буфере оперативная память (или контроллер внешних связей) простаивает.

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

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

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

Примем, что известно:

в конкретной программе количество команд обращения в память ;

времена обслуживания на каждом уровне кэш-памяти;

время обслуживания в оперативной памяти;

времена обслуживания коммутаторов;

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

Обозначим общее время выполнения программы в ядре через .

Времена занятости соответствующих уровней составят:

- время занятости кэш-памяти первого уровня;

- время занятости кэш-памяти второго уровня;

- время занятости кэш-памяти третьего уровня;

- время занятости коммутатора;

- время занятости канала оперативной памяти.

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

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

Определим коэффициент использования (нагрузки) кэш-памяти первого уровня следующим образом

.

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

Интенсивность генерации заявок одним ядром к:

кэш-памяти первого уровня

;

кэш-памяти второго уровня

.

коммутатору 1 и, соответственно, кэш-памяти третьего уровня

;

;

коммутатору 2

;

каналу оперативной памяти

;

Коэффициенты нагрузки общих ресурсов МВС ядрами будут:

коммутатора 1

;

кэш-памяти третьего уровня

;

коммутатора 2

;

канала оперативной памяти

;

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

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

все ядра (потоки) одного процессора (микросхемы) используют общую кэш-память третьего уровня;

несколько потоков ядра используют один канал оперативной памяти. При программировании задач в МВС с использованием технологии OpenMP подразумевается, что все ядра выполняют одинаковую программу над различными данными. Соответственно, считаем, что операционная система разумно распределяет оперативную память для всех потоков (ядер) одного процессора;

коммуникационная подсистема между ядрами и кэш-памятью третьего уровня реализована в виде коммутатора с одновременной передачей данных в/из кэш-памяти третьего уровня;

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

канал оперативной памяти также устройство комбинационного типа. Новая заявка может быть выполнена только после завершения предыдущей заявки.

МВС односокетная.