Моделирование разделяемой памяти двухпроцессорной вычислительной системы

С. П. Сущенко, М. С. Сущенко, Д.В. Биматов

МОДЕЛИРОВАНИЕ РАЗДЕЛЯЕМОЙ ПАМЯТИ ДВУХПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ

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

Современные многопроцессорные вычислительные системы имеют многоуровневую подсистему памяти. Многоуровневая организация памяти позволяет сгладить разрыв между скоростью обработки данных центральным процессором и скоростью доступа к адресуемым объектам в оперативной памяти вычислителя. Эффективность доступа к иерархической памяти определяется не только быстродействием ее отдельных компонент, но и набором архитектурных параметров, важнейшими среди которых являются коэффициент ассоциативности и глубина неблокируемости кэш-памяти. Ассоциативность наряду со стратегией вытеснения кэш-строк при конфликте адресов определяет степень локализации прикладных задач в памяти верхнего уровня [1], а параметр глубины неблокируемости - степень параллелизма выполнения транзакций доступа к памяти различных уровней [2]. Для анализа зависимости операционных характеристик вычислительной системы от глубины небло-кируемости иерархическая память моделируется конвейером с числом фаз, равным количеству уровней подсистемы памяти. Функционирование каждой фазы конвейера описывается марковской СМО с дискретным временем, конечным накопителем и многоэтапным детерминированным обслуживанием. Таким образом, работа конвейера описывается открытой сетью СМО. Длительность дискретного цикла функционирования СМО ґ определяется временем доступа к памяти верхнего уровня и задает время одного этапа обслуживания каждой СМО. Количество этапов обслуживания каждой СМО определяется длительностью обработки транзакции доступа к адресуемым данным на соответствующем уровне иерархической памяти, выраженном в циклах ґ.

Интенсивность входного потока в каждую СМО определяется произведением вероятностей промаха при обработке транзакции в предыдущих уровнях памяти (СМО), вероятностью изменения операциями записи вытесняемого при промахе на соответствующем уровне иерархии блока памяти для кэша с обратной записью и другими параметрами. При исследовании многопроцессорных вычислительных систем с разделяемой общей памятью (БЫР-вычислители) в рассмотренной модели многофазного конвейера необходимо фазу доступа к оперативной памяти вычислителя описывать СМО с неординарным входным потоком. При этом количество поступающих на обработку в данную СМО транзакций определяется вероятностями промаха в кэшах каждого процессора БМР-вычислителя. Поскольку межуровне-вые интерфейсы иерархической памяти имеют ограниченные буферные накопители для хранения запросов к нижележащему уровню памяти при промахе на вышележащем и, кроме того, обслуживание в СМО является многоэтапным, то выходные потоки каждой дискретной СМО не будут марковскими. В силу этого моделирующая сеть СМО не может анализироваться как совокупность независимых марковских дискретных СМО, а должна описываться вложенной цепью Маркова в пространстве с размерностью, равной количеству уровней памяти.

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

Маркова удваивается. В случае же моделирования процесса доступа к иерархической памяти многопроцессорных вычислительных систем с разделяемой оперативной памятью размерность описательного пространства увеличивается кратно количеству процессоров.

МОДЕЛИ ДВУХПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ

Рассмотрим двухпроцессорную вычислительную систему с общей разделяемой оперативной памятью. Будем полагать, что процессорами порождается неограниченный поток обращений к подсистеме двухуровневой памяти. При этом процесс функционирования подсистемы памяти может быть описан работой двухстадийного конвейера. На первой фазе работы конвейера выполняется обращение к кэш-памяти. Длительность этой фазы равна времени доступа к кэшу /. При попадании адресуемого объекта в кэш выполняется следующий запрос к иерархической памяти. В случае промаха одновременно происходит обработка текущего запроса на второй фазе - фазе доступа к оперативной памяти и следующей транзакции - на первой фазе. При глубине неблокируемости N>0 подсистема многоуровневой памяти имеет буфер емкости N для хранения запросов к оперативной памяти, которые последовательно обрабатываются элементами управления памятью на второй фазе конвейера. Если количество транзакций, обрабатываемых в фазе обращения к оперативной памяти, совпадает с коэффициентом неблокируемости N, то кэш-память оказывается заблокированной. В заблокированном состоянии первая стадия конвейера не работает. Разблокирование первой стадии наступает при завершении обработки одной транзакции на второй фазе конвейера.

Полагаем, что индивидуальный кэш каждого процессора характеризуется вероятностью промаха Яя 5 = 1, 2 . Время обращения к оперативной памяти считаем равной К интервалам длительности (. Предположим также, что при одновременном обращении двух процессоров к оперативной памяти с вероятностью q обслуживается запрос первого процессора, а с обратной вероятностью (1^) - второго. Тогда фаза доступа к оперативной памяти вычислителя может быть описана СМО с дискретным временем, многоэтапным обслуживанием и конечным накопителем. Функционирование данной СМО в станционарном состоянии задается цепью Маркова в двумерном пространстве (рис. 1). Обозначим через Ру вероятность того, что СМО находится в состоянии (/,_/). Здесь / соответствует количеству этапов обслуживания транзакций доступа к оперативной памяти, поступивших от первого процессора, а у - от второго. Переходные

вероятности Пу из исходного состояния (у) в измененное состояние (1,к) для кэша блокирующего типа (N=1) имеют вид

Л (1-Л2 ), I = 0, у = 0, I = К, к = 0;

1-Л2, I =1К,] = 0,1 = I-1, к = 0;

Л2, / =1^К, у = 0, I = /-1, к = К;

Л2 (1 - Л), / = 0, у = 0, I = 0, к = К;

1 - Къ I = 0, у = 1^К, I = 0, к = у-1;

• / = 0, у =1"К, I = К, к = у-1;

Л^, I = 0, у = 0, I = К, к = К; q, / = К, у = К, I = К-1, к = К;

1-q, / = К, у = К, I = К, к = К-1;

1, / = 1,К -1, у = К, I = /-1, к = К;

1, / = К, у = 1,К -1, I = К, к = у-1.

Рис. 1. Марковская цепь для подсистемы памяти блокирующего типа двухпроцессорной БМР-системы

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

Р = 1^ • Ры .

Ук ,г

Решение системы уравнений равновесия имеет вид

р 0 = Рк 0 (1-Л )К-, I = 1^К-1; Рк 0 = 1 [Л + Л - ЛЛ - Л (1 - Л)К (1 - Л (1 - q))];

Р/К = Рк^ + Рк0(-Л)К-;), ) =1^К-1;

Рj = Рк (1-Л:)К-;, / =1^К-1; Р0 К = 1 [л + Л - ЛЛ - Л (1-Л )К (1 - Л q)];

Рку = Ркк(1-q)+Р0К(1-(1-Л:)К-;), у=1К-1;

РКК = Р00 Л1Л2;

Р00 =1 [(1 -Яг)К +(1-Л2)К -(1-Л:)К (1-Л)К];

z = 2K[ IR2(1 -R1)]I(1 -R)K [1 -KR2 IKR1R2(2-q)]I I(1-R2) [1-Щ IKR1R2 (1I q)]-

-(1 - Rl)K (1 - R2 )K [11KR R2].

Предположим теперь, что индивидуальный кэш каждого процессора является кэшем неблокирующего типа с коэффициентом неблокируемости N=2. Тогда система уравнений равновесия, описывающая фазу доступа к оперативной памяти при K=2, выглядит следующим образом:

P00 = (1 -R1)(1 -R2)[p00 Ip0 IP01] ;

Pw = (1 - Rj)(l - R2)P20 ; Pu = (1 - Rl)(l - R2)Po2 ;

P20 = (1 -R2)P30 IR1(1 -R2)[P00 IP10 IP01] +

I(l - Rj)(l - R2) P21 ;

P02 = (1 -R1)P03 IR2(1 -R1)[P00 Ip0 IP01]I

I(l - Rj)(l - R2) pu;

P21 =(1 - Rl)2(1 - R2) P221 R (l - R2) P02 ;

P2 =(1 -Rl)2(1 -R2)P221R2(l-Rj)P20 ;

P22 = R2P30 IR1P03 I I(1 - R2)p32 I (1 - R1)P23 I

IR1R2 [P00 IP10 I P01] I

IR1 (1 - R2) p2 IR2 (1 - R1) P21 ;

P30 = (1 - R2 )P40 I R1(1 - R2 )P20 ;

P03 = (1 - R1 )P04 IR2 (1 - R1 )P02 ;

P40 = (1 -R2)p4l IR1(1 -R2)P21 ;

P04 = (1 -R1)p4 IR2(1 -R1)p2 ;

P = (J - R2 ) P I Rl(j - R2 ) P .

Ml _ , r42 ^ ~ 22 >

p = d-R,)p IR2(j-Ri)P .

M4_ , , 22 ’

p = (1 R2 ) p I RR p I

r32 _ 2 М^^Л^20 +

I R1 (J - R2 ) P IR p :

^ „ Jr22^JX2 ^40

Р =(1 Л1) р + ККР + Л2(1 Л1) р + КР .

2 24 1 2 02 2 Г2^ЛИ04>

Р42 = Р43 + Л1Л2 Р21 + Л1Р23 + Л2 Р41 ;

Р24 = ^34 + Л1Л2р2 + Л2Р32 + Л1Р14 ;

р = р = Л1Л2 Р22 + Л2 Р42 + Л1Р24 / з^ 2 .

Решение данной системы уравнений равновесия при Л1 = Л2 = Л представимо в виде

p00 = „2

W ; Pjo = p,! =(^W •

R2

2R

p = p = (j - R)2(2 - R) w •

p20 - Po^ 2r w ;

32О

К-1

Р22 = * ; Р30 = Р03 =

Я(1 - Я)3 (2 - Я) 2

* +

(2 - Я)[Я(1- Я)5 + (1-Я)3] (1 - Я)3

-------[------------------+ ----------и ;

Р40 = Р04 =

Я(1 - Я)2 (2 - Я) 2

* + 2

+Я(1 -Я)4(2-Я)у + (1^)2и •

Р32 = Р23 =

* +

Ж +

+ (1 - Я)( - Я 2 + Я + 1) и ;

Р41 = р4 = ЯМ * + Ы и ;

Я2

р42 = р24 = и; Р43 = Р34 =—* + яи.

Здесь введены следующие обозначения:

Ж = Я2(1 - Я)2 (2 - Я2)(-2 Я4 + 6Я3 - 5 Я2 + 2)/В:

* = Я 2(1 - Я)2(2 - Я 2) Г2 Я6-12 Я5 + 24 Я 4-14 Я3-| ¡В ; 1-9Я 2 + 8Я + 2

и=

В =

*------------ -------------1[* +(1-Я)2ж] ;

2 Я14-10 Я13 +11Я12 +12 Я11 +

+8Я10 -120Я9 +112Я8 +148Я7 --330Я6 + 246Я5 -111Я4 +12Я3 +

-ы = - =£У(0 + Рк)+ЕкРк} ;

у=1 У=1

-ь 2 = N2 =£ У Я у + Рк; ) + Хкрк ;

У=1

У=1

Ч1-^); =1[1-»0

- интенсивности потоков, принятых к обслуживанию от первого и второго процессора соответственно. Окончательно для кэша блокирующего типа (И=1) среднее время доступа к объектам, адресуемым 5-м процессором (5 = 1, 2), задается симметричными соотношениями

71 (КДД) = t {1+Р (2К-1)-

К (К -1)Я { + Я2 [1-(1-Я)К ][1- Я! (1-д (1-Я2 )К +}

1+Я2 [1 -(1 - Я1)К ]

Я-1 + д (1 - Я2 )К Я1

Т2

2-^1+Я11-41-

[1-41-Я2 )К ]

1 -1+41- д)(1-я1)к

Я

+36Я2 -16Я + 4

ОПЕРАЦИОННЫЕ ХАРАКТЕРИСТИКИ

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

Среднее время доступа к объектам, адресуемым в 5-м процессоре (5 = 1, 2), определяется соотношением

(— + N

Т5 (К, Я1, Я2 ) = 1 - Я5 + Я5 [-Ь5Г-5

где —Ь5 и —5 - среднее число этапов обслуживания, блокирующих доступ к кэш-памяти 5-го процессора, и среднее количество этапов обработки транзакций обращения 5-го процессора к иерархической памяти в фазе доступа к оперативной памяти соответственно. В случае кэша блокирующего типа эти величины равны друг другу и для различных 5 определяются соотношениями

Рассмотрим соотношение 71

этот показатель преобразуется к известной зависимости для однопроцессорной вычислительной системы: 71 (К, Л1, Л2 )=t (1+КЛ1). В случае постоянных промахов в кэш второго процессора (Я2 =1) средняя задержка доступа к адресуемым объектам первого процессора составит

7 (к , яь Л2 )=

1+Л1 (2К -1)-

к (к-1)л2 [1-(1-л)к+1]

=ґ

2КЯг -1+(1-[1-Щ (1-Л (2 - q))]J

Если при этом постоянные промахи имеют место и в кэш первого процессора (Я1 =1), то задержка досту-

3К -1

па принимает вид 71 (К, 1, 1)=К---. На рис. 2 ил-

2К -1

люстрируется влияние параметра К и вероятностей промаха в кэши процессоров на показатель 71 (К, Я1, Я2) двухпроцессорной вычислительной системы при q= 1/2, N=1. На рис. 3 показана зависимость показателя 71 (К,Я1,Я2) от коэффициента неблоки-руемости N при К=2.

В общем случае вероятность блокировки кэшпамяти 5-го процессора определяется симметричными соотношениями

NKNK Ж Ж

01 (К, р, Я2)=££Ру ; 02(К, Я), Л2)=££р.

г=1 У=0

У=1 г=0

2

2

-Щ

Рис. 2. Среднее время доступа к адресуемым элементам

Т1(К=2, Р1, Р2) / 1

01 (к , Я1, Я2 )=££р =

¿=1 У=0

=1-1 {1+Я2 [1-(1-Я1)К ](Я-1+д(1-Я2 )К |;

К К

Нетрудно видеть, что при Л2 = 0 данный показатель для первого процессора совпадает с пропускной способностью однопроцессорного вычислителя:

1

С1 (К, Я1,0)=

(1 + КЯ1)ґ

В случае Я2 =1 получаем

С (К, Я1, 1)=-

Чиї - Я1)К ] [-1 -і]

'Ф К +(1 - Я! )К [1 - К (1-Я (2 - q))]]'

Набор параметров Я; = 0, Л2 =1 приводит к С1 (К, 0, 1) = 1/1, а для Л1 = Л2 =1 имеем С1 (К, 1, 1) = 1/2К.

Характер зависимости быстродействия подсистемы памяти вычислителя от параметров Я1, Л2 и N

при К=2, q = ^<2 представлен на рис. 4.

Рис. 3. Среднее время доступа к адресуемым элементам подсистемы памяти двухпроцессорного вычислителя

В случае кэша блокирующего типа соотношения для вероятности блокировки кэш-памяти 5-го процессора принимают вид

02 (К, Я1, Я2) = ХХРу =

г=0 у=1

= 1-1 |х +Я1 [1-(1-Я2)К^-1 + (1-q)(1-Я)К|.

Пропускная способность подсистемы памяти для 5-го процессора задается выражением

С (К, Я1, Я2 )=1[1-05 (К, Я1, Я2 )].

--к1

Рис. 4. Пропускная способность подсистемы памяти двухпроцессорной вычислительной системы

ЗАКЛЮЧЕНИЕ

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

эффективности подсистем памяти блокирующего и неблокирующего типа. Из вида зависимостей Т (К, Я1, Л2) и С (К, Я1, Л2), приведенных на рис. 3 и 4, нетрудно видеть, что с ростом вероятности промаха в кэш каждого процессора конкуренция за доступ к общей разделяемой оперативной памяти двухпроцессорной вычислительной системы увеличивается и мешающее воздействие одного процессора на работу другого возрастает. Следствием этого для обоих про-

цессоров является ухудшение индивидуальных операционных характеристик доступа к иерархической памяти для широкой области изменения ее параметров Я1 , Я2 , К. Показано, что с увеличением глубины неблокируемости область значений вероятностей промаха на различных уровнях памяти, для которых уменьшается среднее время доступа к адресуемым объектам, сужается.

ЛИТЕРАТУРА

1. СущенкоМ.С., Сущенко С.П. Анализ эффективности многоуровневой памяти вычислительных систем // Обозрение прикл. и промышл. матем. 2001. Т. 8. Вып. 1. С. 336-337.

2. Сущенко М.С., Сущенко С.П. Модель влияния глубины неблокируемости кэша на быстродействие многоуровневой памяти // Обозрение прикл. и промышл. матем. 2001. Т. 8. Вып. 2. С. 695-696.

Статья представлена кафедрой теоретических основ информатики факультета информатики Томского государственного университета, поступила в научную редакцию 30 апреля 2003 г.