Л.П. Фельдман, Т.В. Михайлова - Вероятностная модель блочной памяти

Аннотация

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

Введение

Для реализации основной памяти используют объединение нескольких интегральных микросхем (ИМС). Совокупность микросхем называют модулем памяти. Один или несколько модулей образуют банк памяти.

В общем случае основная память вычислительного модуля практически всегда имеет блочную структуру, то есть содержит несколько банков.

При использовании блочной памяти, состоящей из В банков, адрес ячейки А преобразуется в пару (b, w), где b – номер банка, w – адрес ячейки внутри банка [1].

Cхемы распределения разрядов адреса А между b и w:
– блочная (номер банка b определяет старшие разряды адреса);
– циклическая (b = A mod В; w = A div В);
– блочно-циклическая (комбинация двух предыдущих схем).

Типовая структура памяти, организованная в соответствии с блочной структурой, показана на рис. 1.

Рисунок 1 – Структура основной памяти на основе блочной схемы

Выбор банка обеспечивается либо с помощью дешифратора номера банка памяти, либо путем мультиплексирования информации. Емкость ОП равна суммарной емкости составляющих, а быстродействие – быстродействию отдельного банка [1].

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

В блочно-циклической схеме расслоения памяти каждый банк состоит из нескольких модулей, адресуемых по круговой схеме. Адреса между банками распределены по блочной схеме [1].

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

Вероятностная модель блочной памяти с одним входным потоком заявок

Основные предположения о функционировании блочной памяти, отражающие организацию работы ОП:

1. Все модули ОП работают синхронно так, что за один такт (цикл обращения) каждый модуль может обслужить не более одной заявки, а все модули не более N заявок одновременно.

2. В каждом такте работы число заявок во входном потоке не меньше числа банков системы, т.к. максимальная производительность всех существующих мультипроцессорных вычислительных систем достигается при вычислениях, производимых над регулярно организованными массивами информации. Число обращения к ОП за командами мало по сравнению с обращением за операндами. Потоки в рассматриваемой модели – это потоки обращения к ОП за считыванием или записью векторов, каждый из которых содержит элементов не менее, чем число банков ОП. Каждая заявка с равными вероятностями 1/N требует обслуживания каждым из банков ОП.

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

4. Распределение заявок по банкам памяти происходит в порядке очередности этих заявок во входном потоке, из которого на обслуживание заявки поступают до тех пор, пока не появится первая заявка с запросом на обслуживание занятым банком. Это значит, что если какая-либо заявка не может быть обслужена в данном такте из-за занятости соответствующего банка, то она блокирует поступления к банкам ОП всех последующих заявок.

Интервал времени распределения и обслуживания заявок назовем тактом работы системы. Обозначим n число заявок входного потока, выбранных на обслуживание в одном такте, которое примем за состояние системы. Вероятность того, что первая заявка из входного потока поступит на обслуживание, равна 1, так как она застает свободными все N модулей. Вероятность р₁ того, что из входного потока на обслуживание поступит точно одна заявка, может быть вычислена как произведение вероятности того, что первая заявка поступит на обслуживание в один из N свободных банков, и вероятности того, что вторая заявка требует обслуживания тем же банком, т.е. р_l = 1/N.

Вероятность того, что из входного потока на обслуживание поступит ровно две заявки, равна произведению вероятности поступления двух первых заявок на свободные модули и вероятности того, что третья заявка требует обслуживания одним из двух уже занятых банков, т.е. Р₂ = ((N – 1)/N) x (2/N). Рассуждая аналогично, получим для вероятности рn того, что из входного потока поступит на обслуживание ровно n заявок, формулу:

Таким образом, на множестве состояний {О, N} системы с заданным числом N обслуживающих устройств банков ОП определена цепь Маркова с переходными вероятностями , задаваемыми (1). Граф состояний цепи Маркова приведен на рис. 2.

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

Значения среднего числа занятых банков Nср приведены в табл. 1. Коэффициент использования ОП, равный R_cp = N_ср/N, падает с ростoм N и для количества банков больше восьми достаточно низкий.

Рисунок 2 – Граф состояний цепи Маркова вероятностной модели блочной ОП

Таблица 1

Показатель	Число банков
Показатель	1	2	4	8	16	32
N_cp	1	1,5	2,22	3,25	4,70	6,77
R_cp	1	0,75	0,58	0,40	0,29	0,21

Вероятностная модель блочной памяти с несколькими входными потоками заявок

Пусть в ОП, состоящую из N одинаковых банков памяти, поступают L независимых параллельных потоков обращения к банкам ОП от устройств обработки и периферийных процессоров мультипроцессорной вычислительной системы. К ограничениям для предыдущей модели добавятся следующие: между потоками установлен абсолютный приоритет на обслуживание в ОП, убывающий с ростом номера потока; каждая заявка любого потока с равными вероятностями 1/N требует обслуживания каждым из N банков ОП; распределение заявок каждого потока по банкам ОП происходит в порядке очередности этих заявок в данном потоке. Если какая-либо заявка l-го потока, , не может быть обслужена в данном такте из-за занятости соответствующего банка, то эта заявка блокирует поступления к банкам ОП и всех последующих заявок l-го потока. Затем происходит распределение на оставшиеся свободные модули ОП заявок из (l + 1)-го потока и так далее.

Состояние системы – число занятых банков n_l, после окончания распределения заявок из входного потока, с l-м приоритетом. Вероятность перехода из состояния n_l-1 в состояние n_l определяется:

где R_l = n_l – n_l-1 – число заявок, выбранных из l-го потока; Р{n_l-1>n_l} – вероятность выбора на обслуживание равно n_l заявок l-го потока при условии, что из потоков более высокого, чем l-й, приоритет выбрано на обслуживание n_l-1 заявок.

На рис. 3 приведена граф-схема марковской цепи для модели ОП с N банками и L входными потоками заявок.

Рисунок 3 – Граф состояний цепи Маркова ОП с N банками и L входными потоками

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

Вероятность перехода цепи Маркова определяется самими значениями n_l-1 = l и n_l = j.

Этот граф состояния можно использовать для любого числа L входных потоков заявок. Матрица переходных вероятностей цепи Маркова, граф состояний которой изображен на рис. 3, имеет вид

Для каждого состояния марковской модели определены следующие стационарные вероятности:

i12 – вероятность застать на l-м шаге загруженные п банков памяти,

i13 – вектор вероятностей состояний на l-м шаге, i14 Поскольку начальное состояние известно, то известен и начальный вектор вероятностей состояний

Вектор вероятностей состояний на любом шаге l + 1 может быть найден по рекуррентной формуле:

или в скалярной форме

Если определена вероятность i18 состояния n банков, занятых на L-м шаге, то можно определить и среднее число банков, занятых обслуживанием

которое характеризует среднюю производительность блочной ОП с блочно-модульной схемой расслоения.

В табл. 2 приведены значения среднего числа занятых банков, из которых видно, что быстродействие памяти при одном и том же числе банков увеличивается вместе с ростом независимых потоков запросов. Однако увеличение производительности ОП, получае- мое за счет разделения общего потока заявок на L независимых потоков, требует существенного усложнения управления работой мультипроцессорных вычислительных систем.

Таблица 2

Число банков	Число потоков
Число банков	1	2	3	4	5	6	7	8
2	1,50	1,75	1,86	1,94	1,97	1,98	1,99	2,00
4	2,29	2,83	3.19	3,42	3,58	3,69	3,77	3,83

Выводы

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

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

Список использованной литературы

1. Цилькер Б.Я. Организация ЭВМ и систем / Б.Я. Цилькер, С.А. Орлов. – М : ПИТЕР, 2004. – 668 с.
2. Столингс У. Структурная организация и архитектура компьютерных систем / Столингс У. – М. :Вильямс, 2002.– 893 с.