Modelling of hierarchical memory of non-blocking computer systems.pdf Важнейшим элементом вычислительных систем является подсистема многоуровневой памяти. Разрыв скорости обработки данных в центральном процессоре и скорости доступа к адресуемым операндам в оперативной памяти современных компьютеров составляет 2-3 порядка. Высокое быстродействие вычислительной системы в значительной мере определяется организацией ее многоуровневой памяти. Одним из параметров подсистемы памяти, определяющих ее операционные характеристики, является глубина неблокируемости кэша. Этот параметр задает потенциально достижимую степень параллелизма выполнения совокупности транзакций доступа к различным уровням иерархической памяти. Принципы функционирования и модель кэша неблокирующего типа Рассмотрим двухуровневую память, имеющую кэш неблокирующего типа с обратной записью [1,2]. Будем полагать, что процессором порождается неограниченный поток обращений к подсистеме памяти. Функционирование многоуровневой памяти с кэшем неблокирующего типа может быть описано работой двухстадийного конвейера. На первой фазе конвейера выполняется обращение к кэш-памяти. Полагаем, что обращения происходят к различным блокам кэш-памяти. Длительность этой фазы равна времени t доступа к кэшу. При попадании адресуемого объекта в кэш выполняется следующий запрос к иерархической памяти. В случае промаха одновременно происходит обработка текущего запроса на второй фазе (доступ к оперативной памяти) и следующей транзакции - на первой фазе. Факт обработки транзакции доступа к иерархической памяти на второй фазе является случайным событием. Время обработки транзакции на второй фазе Т в К>2 раз превышает время обращения к кэш-памяти t. При глубине неблокируемости N>1 подсистема многоуровневой памяти имеет буфер емкости N для хранения запросов к оперативной памяти, которые последовательно обрабатываются элементами управления памятью на второй фазе конвейера. Если количество таранзакций, обрабатываемых в фазе обращения к оперативной памяти, совпадает с N, то кэш-память оказывается заблокированной. В заблокированном состоянии первая стадия конвейера не работает. Разблокирование первой фазы наступает при завершении обработки одной транзакции на второй фазе конвейера. Для описания процесса обработки запросов к двухуровневой памяти с глубиной блокировки, равной N, смоделируем стадию доступа к оперативной памяти Марковской системой масового обслуживания (СМО) с дискретным временем и К-этапным обслуживающим прибором [3] с детерминированным временем обслуживания. Длительность цикла дискретной СМО составляет время t. Время между поступлениями заявок (транзакций обращения к оперативной памяти) кратно t и имеет геометрическое распределение с параметром, равным вероятности промаха R. Считаем, что доступ к многоуровневой памяти выполняется только на чтение или только на запись. Будем полагать, что в каждом такте выполняется обращение к кэш-памяти (при незаблокированной первой фазе конвейера) и с вероятностью промаха R в СМО поступает заявка с временем обработки Т, равным трудоемкости выполнения К этапов СМО длительности t. Обработка различных запросов к оперативной и кэш-памяти выполняется параллельно и цепь Маркова, описывающая динамику количества этапов обработки совокупности заявок на доступ к оперативной памяти, будет содержать KN состояний. Номер состояния цепи Маркова соответствует количеству этапов обслуживания транзакций доступа к оперативной памяти, накопленных в СМО. Вероятность того, что в стационарном режиме система находится в состоянии к обозначим через Рк ,к=0,NK-1. Заблокированным соответствует множество состояний i =К (N-1)+1, KN-1, в которых СМО содержит N транзакций. Переходные вероятности цепи Маркова имеют вид: |R,i=0, j=K; П i = R,i=1,K (N-1), j^+К-1; 1-R,i=1,K (N-1)j=i-1; 1,i=K (N -1)+1,KN-1, j=i-1. Система уравнений равновесия для вероятностей состояний Р t ,i=0,NK-1, стационарного режима функционирования дискретной СМО, описывающей процесс доступа к иерархической памяти, для произвольной конечной глубины неблокируемости N > 2 и целочисленного отношения времен обращения к оперативной памяти и кэш-памяти К > 2 записывается следующим образом: РоR=P(1-R); _ Р =РМ(1-К)^=1,К-1; (1) Рк =Рк+1 +(Ро +P)R,N=2; Рк =Рк+1(1^)+(Ро +^)R,N >2; Р =Р+, (1-R)+^-K+1 R,i=K+1,( N-1) К -1; Р =Р+1 +Р-к+1 R,i=( N-1)К ,NK-2; Р =Р R 1 NK-1 1 (N-1) К+1iu Для неограниченного N данная система уравнений переписывается в виде: \РаR=P(1-R); _ Р =P+1(1-R),i=1,K-1; Рк =Рк+i(1-R)+(P0 +Р) R; Р =p+i(1-R)-p.-K+R,i>K+1. Для кэш-памяти блокирующего типа (N=1) уравнения равновесия принимают вид: \Ро R=P; (2) Р =P+J=1K-1; Рк =RP,. Важнейшими операционными характеристиками иерархической памяти являются вероятность блокировки кэш-памяти, среднее время доступа и пропускная способность. Вероятность блокировки определяется суммой вероятностей состояний, в которых на фазе доступа к оперативной памяти (в СМО) выполняется обработка N транзакций: NK-1 Q(N,K)= ХР . (3) i=( N-1) K+1 Среднее время доступа к адресуемым объектам складывается из времени разблокирования кэш-памяти, времени обращения к кэшу и времени обращения к оперативной памяти (при промахе в кэш): Т (N ,K )=rT 5+(1-R) t+RTii. (4) Здесь Тр и Тт - условное среднее время разблокирования и обращения к оперативной памяти соответственно, определяемые по формуле Литтла [3]: _ NK-1 _ NK-1 Т, К'-( N-1) к) Pi Тр =Х-1 XiPi , =( N-1 ) K+1 =1 Я = KR( 1 - К)) - принятый (протащенный) поток Вероятностно-временные характеристики Найдем аналитический вид решения системы уравнений равновесия и показателей быстродействия многоуровневой памяти. Для кэш-памяти блокирующего типа (N=1) найденные из (2) вероятности состояний второй фазы конвейера записываются как Р =_1_Р 0 ' J i , i=1,K, а операционные характе- 1+KR 1+KR ристики определяются зависимостями: KR - K (1+K) Q (1,K (1,K )=t+tR (1+R)---. 1+KR 2 (1+KR) Из этих соотношений нетрудно видеть, что с ростом K при R>0 вероятность блокировки стремится к 1. Среднее время выборки адресуемых объектов растет от T(1,K)=t при R=0 до Т (1,K )=t (1+K) при R=1. При N=2 и конечном K>2 решение системы уравнений равновесия (1) с учетом условия нормировки вероятностей Р ,i=0,2K -1 принимает вид: R Р =Р 1 i 1 0 ■i=1,K; (1-R )i R 2 K-i-1 pk+ =Ро~~~к S(1-R)' ,i=1,k-1; (1-R) (1-R )J Ро =- 1+R2 X( K-y-1)(1-R) ^ J=0 Вероятность блокировки (3) при этом определяется зависимостью: Q (2,к )=- R2 к к - j )(1-R у-1 J=1_ 1+R2 § K-1- j )(1-R)" J=0 Т (2,2 )=t Т (2,3 )=t Среднее время доступа к адресуемым объектам (4) при K=2 и K=3 соответственно составит: 1+R (1+3 R) 1+R3(3+13 R-4 R2 ) С дальнейшим увеличением K сложность аналитического вида соотношения (4) стремительно возрастает. Для K=2 и конечной глубины неблокируемости N>2 решением (1) являются соотношения R 1-R Р =Ро -; Р =Ро R =2,2(N-1). 0 (1-R) В случае неограниченного N стационарное состояние существует при R>1/2, и решение системы уравнений равновесия принимает вид: R R -1 Р0 =1-2R, Р =(1-2R)-, Р =(1-2R)--, i>2. 0 1 1-R ' (1-R)' Операционные показатели для N=ro описываются соотношениями: Q (2 решение (1) имеет вид: R Р =Р 0 Р0 R2 -1 ■Z(1-R )J Р3 к - i " i=1,K-1; (1-R )2 кТ~0 P0 =(1-R )2 , i =1,K; (1-R У Р =Р0 R [1-(1-R)к-1 (1+R (i -K -1)) ], i=K+1,2 K; (1-R У 1-(1-R)к х x(1+R (K -1- j))_ х (1-R)K +R X(1-R)K =0 x[1-(1-R)K-1 (1+iR)+ +R2 S K -i )(1-R) i-1x [x[1-(1-R)K-1(1+( K -i) R )]J Для глубины неблокируемости N=4 и произвольном K>2 решение (1) записывается следующим образом: R Р =Р 0 -i =1,к; (1-R У R _ Р =P^7T^7[1-(1-R)K-1 (1+R (i-K-1)) ],i =K+1, 2 K; (1-R) R Р =Р0 ., i=1,K; - 0 (1-R у 1-(1-R) К-1 [1+R (i-K-1)+ +(i-2 K) R (1-R) '(1-R)' 1+R 2 i=2 K +1,3 K; P0 R2 р 4 K(1-R )3 K 1-( 1-R)K -1 (1+ +R (2 K-j-1))+( K-j )x K - 7-1 1+R xR (1-R )2( K-1) 2 Вероятность P0 находится из условия нормировки. Влияние частоты изменений данных на операционные характеристики Для учета влияния на операционные характеристики иерархической памяти интенсивности изменений данных (операций записи) введем вероятность г того, что вытесняемая при промахе строка кэш-памяти с обратной записью изменена. Будем полагать, что неизмененная вытесняемая строка требует К1 интервалов длительности t для замещения новым блоком памяти, востребованным вычислителем, а измененная - требует сохранения вытесняемого блока в оперативной памяти и загрузки в кэш новой строки с общим временем выполнения транзакции, равным K2t. Очевидно, что К1 - P(1,к2 )=p(1,0) Rr _1 X(1-R)' м,к 1 -1; (1-R) 1 1=0 1 г I(1-R)l P(K, ,j)=P(0,1) P(0,j)=P(0,1)R ,j=1,K2; Rr K2+,\ P (0,K 2 + j )=P (0,1) (1-R) 2 -1 1=0 7=1, K 2 -1; R (1-r) K 2 r £(1-R)l ,j=1,K 2 -1; (1-R) 2 -1 1=0 Г K 2 -2 R11-Rr ^(1-R)l -r (1-R)K 2 -1 P (1,0 )=P (0,0)к 2 -к 1 -1 (1-R) \ 1-Rr К 1-R)l [ l=0 Г k 2 -3 Rr \ R ^(1-R)l +(1-R)K -K -1 P (0,1)=P (0,0)- K -K -1 1-Rr ^(1-R)l Вероятность состояния (0,0) определяется из условия нормировки. Для набора параметров Kj=2, K2=3 вероятность P(0,0) записывается следующим образом: (1-R )2 (1-Rr) P(0,0)= (1-R)2 (1-Rr )+R (2-r) а для Kj=2, K2=4 принимает вид: (1-R)2 [1-Rr (2-R)] P(0,0)= (1-R)2 [1-Rr (2-R)]+2R(1+r) Предварительный анализ показывает, что при заданной вероятности промаха в кэш-памяти пропущенный по системной шине поток транзакций доступа к адресуемым объектам оперативной памяти растет с увеличением глубины неблокируемости, а среднее время выборки операндов и команд из иерархической памяти - падает. Заключение Для изучения зависимости быстродействия подсистемы памяти от ее параметров (емкость неблокирующего буфера, коэффициент ассоциативности и объем кэш-памяти, относительные взаимные емкости памятей различных уровней, размер межуровневого интерфейсного блока, распределение приложений в оперативной памяти, вероятность сквозной записи вытесняемой строки кэша в основную память при промахе, тактовая частота системной шины, количество процессоров в системе) предложена математическая модель в виде многоэтапной СМО с поступлением заявок (транзакций доступа к основной памяти) в темпе промахов в кэш-память, детерминированным обслуживанием и дискретным временем. При этом время между поступлениями заявок распределено по геометрическому закону с интегральным параметром, определяемым вероятностью промаха в кэше процессора вычислительной системы и вероятностью порождения обменов «память - внешнее устройство». Получены аналитические соотношения для вероятностно-временных характеристик параллельного процесса обработки транзакций доступа к различным уровням иерархической памяти. В дальнейшем планируется всестороннее исследование операционных показателей многоуровневой памяти и изучение вероятностно-временных характеристик протоколов обеспечения когерентности кэшпамяти многопроцессорных вычислительных систем с сильной и слабой связью на основе механизмов следящей шины и распределенных директорий.

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