Modeling of shared memory two-processors computer systems.pdf Современные многопроцессорные вычислительные сис-темы имеют многоуровневую подсистему памяти. Много-уровневая организация памяти позволяет сгладить разрывмежду скоростью обработки данных центральным процес-сором и скоростью доступа к адресуемым объектам в опе-ративной памяти вычислителя. Эффективность доступа киерархической памяти определяется не только быстродей-ствием ее отдельных компонент, но и набором архитектур-ных параметров, важнейшими среди которых являются ко-эффициент ассоциативности и глубина неблокируемостикэш-памяти. Ассоциативность наряду со стратегией вытес-нения кэш-строк при конфликте адресов определяет степеньлокализации прикладных задач в памяти верхнего уровня[1], а параметр глубины неблокируемости - степень парал-лелизма выполнения транзакций доступа к памяти различ-ных уровней [2]. Для анализа зависимости операционныххарактеристик вычислительной системы от глубины небло-кируемости иерархическая память моделируется конвейе-ром с числом фаз, равным количеству уровней подсистемыпамяти. Функционирование каждой фазы конвейера описы-вается марковской СМО с дискретным временем, конечнымнакопителем и многоэтапным детерминированным обслу-живанием. Таким образом, работа конвейера описываетсяоткрытой сетью СМО. Длительность дискретного циклафункционирования СМО t определяется временем доступа кпамяти верхнего уровня и задает время одного этапа обслу-живания каждой СМО. Количество этапов обслуживаниякаждой СМО определяется длительностью обработки тран-закции доступа к адресуемым данным на соответствующемуровне иерархической памяти, выраженном в циклах t.Интенсивность входного потока в каждую СМО опреде-ляется произведением вероятностей промаха при обработкетранзакции в предыдущих уровнях памяти (СМО), вероят-ностью изменения операциями записи вытесняемого припромахе на соответствующем уровне иерархии блока памя-ти для кэша с обратной записью и другими параметрами.При исследовании многопроцессорных вычислительныхсистем с разделяемой общей памятью (SMP-вычислители) врассмотренной модели многофазного конвейера необходи-мо фазу доступа к оперативнойвероятности lkƒij из исходного состояния (i,j) в изме-ненное состояние (l,k) для кэша блокирующего типа(N=1) имеют вид( )( )1 2222 1111 21 , 0, 0, , 0;1 , 1, , 0, 1, 0;, 1, , 0, 1, ;1 , 0, 0, 0, ;1 , 0, 1, , 0, 1;, 0, 1, , , 1;, 0, 0, , ;, , , 1, ;1 , ,lkijR R i j l K kR i K j l i kR i K j l i k KR R i j l k KR i j K l k jR i j K l K k jR R i j l K k Kq i K j K l K k Kq i K j K− = = = =− = = = − == = = − =− = = = =− = = = = −ƒ = = = = = −= = = == = = − =− = = , , 1;1, 1, 1, , 1, ;1, , 1, 1, , 1.l K k Ki K j K l i k Ki K j K l K k j⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪= = − ⎪⎪= − = = − =⎪ = = − = = − ⎪⎩00 10 20 K001020K 1K 2K KKK1K21 1 1111R1R21− R11− R2 1− R2 1− R2 1− R2R1R1R1R2 R2 R21− qq( ) 121 RR⋅ −⋅1− R11− R11− R1............R1 ⋅(1− R2)Рис. 1. Марковская цепь для подсистемы памятиблокирующего типа двухпроцессорной SMP-системыПроцесс доступа к адресуемым объектам двухпро-цессорной вычислительной системы описываетсяследующей системой уравнений равновесия:,ijij kl klk lP P=ƒƒ ⋅ .Решение системы уравнений равновесия имеет вид0 0(1 2)K i, 1, 1;Pi =PK −R − i= K−0 1 2 12 2( 1) ( 1( ))1 1 K1 1 ;K PR R RR R R R qz=⎡⎣+ − − − − − ⎤⎦( ( ) ) 01 1 2K j , 1, 1;PjK=PKKq+PK − −R − j= K−0 0 (1 1)K j, 1, 1;Pj=PK −R − j= K−0 1 2 1 2 1( 2) ( 2 )1 1 K1 ;K PR R RR R R Rqz=⎡⎣ + − − − − ⎤⎦( ) ( ( ) ) 1 0 1 1 1K j , 1, 1;PKj=PKK −q+PK − −R − j= K−PKK =P00R1R2 ;00 ( 1) ( 2) ( 1) ( 2)P 11RK 1RK 1RK1RK;z=⎡⎣− + − − − − ⎤⎦[ ( )] ( ) [ ( )]( ) [ ( )]( ) ( ) [ ]1 2 1 1 2 1 22 1 1 21 2 1 22 1 1 1 21 1 11 1 1 .KKK Kz K R R R R KR KR R qR KR KRR qR R KRR= + − + − − + − ++ − − + + −− − − +Предположим теперь, что индивидуальный кэшкаждого процессора является кэшем неблокирующеготипа с коэффициентом неблокируемости N=2. Тогдасистема уравнений равновесия, описывающая фазудоступа к оперативной памяти при K=2, выглядитследующим образом:P00 = (1−R1)(1−R2 )[P00+P10+P01] ;P10 = (1−R1)(1−R2 )P20 ; P01 =(1−R1)(1−R2 )P02 ;P20 = (1−R2 )P30+R1(1−R2 )[P00+P10+P01]++(1−R1)(1−R2)P21;P02 = (1−R1)P03+R2 (1−R1)[P00+P10+P01]++(1−R1)(1−R2)P12;1 221 22 1 2 02(1 )(1 )(1 )2P R RP R R P− −= + − ;1 212 22 2 1 20(1 )(1 )(1 )2P R RP R R P− −= + − ;P22 =R2P30+R1P03++(1−R2)P32+(1−R1)P23++R1R2 [P00+P10+P01]++R1(1−R2 )P12+R2 (1−R1)P21 ;P30= (1−R2)P40+R1(1−R2)P20;P03= (1−R1)P04+R2(1−R1)P02;P40 = (1−R2 )P41+R1(1−R2 )P21 ;P04= (1−R1)P14+R2(1−R1)P12;2 1 241 42 22(1 ) (1 )2 2P RP R RP− −= + ;1 2 114 24 22(1 ) (1 )2 2P RP R RP− −= + ;232 42 1 2 201 222 2 40(1 )2(1 )2P R P R R PR R P RP−= + +−+ +;1 2 123 24 1 2 02 22 1 04(1 ) (1 )2 2P RP R R P R R P R P− −= + + + ;P42 =P43+R1R2P21+R1P23+R2P41 ;P24 =P34+R1R2P12+R2P32+R1P14 ;1 2 22 2 42 1 2443 34 2P P RRP RP RP+ += = .Решение данной системы уравнений равновесияпри R1=R2=R представимо в виде( )600 21 RP WR−= ; 10 01(2 )2P P RWR−= = ;220 02(1 ) (2 )2P P R RWR− −= = ;P P RZ R RW− − −= = + ;P22 =Z;330 03(1 ) (2 )2P P R R RZ− −= = +(2 ) (1 )5 (1 )32R R R RW+ − ⎡⎣ − + − ⎤⎦ +(1 )32R U−;240 04(1 ) (2 )2P P R R RZ− −= = +(1 )4 (2 )2R R RW− −+ +(1 )22R U−;( 4 3 2 )32 23(1 ) 3 22R R R R RP P Z− − + += = +(1 )2( 5 4 4 5 3 2 2)2R R R R R RW− − + − + ++ +(1 )( 2 1)2R R R U− − + ++ ;41 14(1 ) (1 )2 2P P R RZ RU− −= = + ;P42=P24=U;243 34 2P =P = R Z+RU.Здесь введены следующие обозначения:W=R2(1−R)2(2−R2)(−2R4+6R3−5R2+2) D;6 5 4 32 2 22(1 ) (2 )2 12 24 149 8 2Z R R R R R R R DR R= − − ⎜⎝⎛− −+ ++ − −⎟⎠⎞;( ) ( )6 5 4 3 22 4 4 2 412R R R R RU Z R W− + − − += ⎡⎣+− ⎤⎦;14 13 12 1110 9 8 76 5 4 322 10 11 128 120 112 148330 246 111 1236 16 4R R R RR R R RDR R R RR R⎛ − + + + ⎞⎜ ⎟⎜+ − + + −⎟=⎜ ⎟⎜− + − + +⎟⎜⎝+ − + ⎟⎠.ОПЕРАЦИОННЫЕ ХАРАКТЕРИСТИКИВажнейшими операционными характеристиками,определяющими эффективность работы подсистемыпамяти, являются среднее время доступа к адресуе-мым объектам и пропускная способность подсистемыиерархической памяти.Среднее время доступа к объектам, адресуемым вs-м процессоре (s =1, 2), определяется соотношением( , 1, 2) 1 bs s ,s s ssT K R R R R N N⎛ + ⎞= − + ⎜⎝ ƒ ⎟⎠где Nbs и Ns - среднее число этапов обслуживания,блокирующих доступ к кэш-памяти s-го процессора, исреднее количество этапов обработки транзакций об-ращения s-го процессора к иерархической памяти вфазе доступа к оперативной памяти соответственно. Вслучае кэша блокирующего типа эти величины равныдруг другу и для различных s определяются соотно-шениями( ) 11 1 01 1K Kb j jK Kjj jN N jP P KP−= == =ƒ + +ƒ ;( ) 12 2 01 1K Kb j Kj jKj jN N jP P KP−= == =ƒ + +ƒ ;1 001 1KiiPt =⎛ ⎞ƒ =⎜− ⎟⎝ ⎠ƒ ; 2 001 1KiiPt =⎛ ⎞ƒ =⎜− ⎟⎝ ⎠ƒ- интенсивности потоков, принятых к обслуживаниюот первого и второго процессора соответственно.Окончательно f3для кэша блокирующего типа81-R1T1(K, R1, R2) / tR2=0R2=0.1R2=1K=2K=5Рис. 2. Среднее время доступа к адресуемымэлементам (двухпроцессорная система с кэ-шем блокирующего типа)0,0 0,2 0,4 0,6 0,8 1,01234R2=0R2=0.1R2=1T1(K=2, R1, R2) / t1-R1Рис. 3. Среднее время доступа к адресуемымэлементам подсистемы памяти двухпроцес-сорного вычислителя (пунктирные линии со-ответствуют N=1, сплошные - N=2)В случае кэша блокирующего типа соотношениядля вероятности блокировки кэш-памяти s-го процес-сора принимают вид1( 1 2)1 0, ,K Kiji jQ K R R P= ==ƒƒ =2 ( 1) ( 2)1111R1 1RK 11q1RKz R= − ⎩⎨⎧+ ⎣⎡ − − ⎦⎤⎝⎛⎜ − + − ⎠⎞⎟⎭⎫⎬;2( 1 2)0 1, ,K Kiji jQ K R R P= ==ƒƒ =1 ( 2) ( )( 1)2111R1 1RK 11 1q1RKz R= − ⎧⎩⎨+ ⎡⎣ − − ⎤⎦⎛⎝⎜ − + − − ⎞⎠⎟⎫⎭⎬.Пропускная способность подсистемы памяти дляs-го процессора задается выражением( 1 2) [ ( 1 2)]CsK,R,R 11 QsK,R,Rt= − .Нетрудно видеть, что при R2 = 0 данный показа-тель для первого процессора совпадает с пропускнойспособностью однопроцессорного вычислителя:( )1 1 ( )1, , 0 11C K RKR t=+.В случае R2 =1 получаем( )( ){ ( ) [ ( ( ))]}111 11 11 1 1 1 1, ,12 1 1 1 2KKRC K R Rt K R K R q= +⎡⎣ − − ⎤⎦ ⎛⎜⎝ − ⎞⎟⎠+ − − − −.Набор параметров R1 = 0 , R2 =1 приводит кС1 (K, 0, 1)=1t, а для R1=R2=1 имеемC1 (K, 1, 1)=1 2Kt.Характер зависимости быстродействия подсисте-мы памяти вычислителя от параметров R1 , R2 и Nпри K=2, 1q = 2 представлен на рис. 4.0,0 0,2 0,4 0,6 0,8 1,00,20,30,40,50,60,70,80,91,0R2=1R2=0.1R2=0N=1N=2C1(K=2, R1, R2) / t1-R1Рис. 4. Пропускная способность подсистемыпамяти двухпроцессорной вычислительнойсистемы (пунктирные линии соответствуютслучаям N=1, сплошные - N=2)ЗАКЛЮЧЕНИЕДля изучения зависимости быстродействия под-системы памяти двухпроцессорной вычислительнойсистемы с симметричной архитектурой от ее парамет-ров (емкость неблокирующего буфера, вероятностипромаха в кэши процессоров, время выборки адре-суемого элемента из кэша и оперативной памяти) раз-работана математическая модель влияния глубинынеблокируемости кэша на операционные характери-стики иерархической памяти в виде многоэтапнойсистемы массового обслуживания с поступлениемзаявок (транзакций доступа к основной памяти) втемпе промахов в кэш-память, детерминированнымобслуживанием и дискретным временем. Полученыаналитические соотношения для вероятностно-вре-менных характеристик параллельного процесса обра-ботки транзакций доступа к различным уровням ие-рархической памяти. Проведен сравнительный анализэффективности подсистем памяти блокирующего инеблокирующего типа. Из вида зависимостейT(K,R1,R2) и С(K,R1,R2), приведенных на рис. 3 и 4,нетрудно видеть, что с ростом вероятности промаха вкэш каждого процессора конкуренция за доступ к об-щей разделяемой оперативной памяти двухпроцес-сорной вычислительной системы увеличивается имешающее воздействие одного процессора на работудругого возрастает. Следствием этого для обоих про-цессоров является ухудшение индивидуальных опе-рационных характеристик доступа к иерархическойпамяти для широкой области изменения ее парамет-ров R1 , R2 , K. Показано, что с увеличением глубинынеблокируемости область значений вероятностейпромаха на различных уровнях памяти, для которыхуменьшается среднее время доступа к адресуемымобъектам, сужается.

Скачать электронную версию публикации