Вероятностная модель блочной памяти
Предложена вероятностная модель блочной памяти с одним и несколькими входными потоками, получены среднее число использованных банков и коэффициент загрузки, которое характеризует среднюю производительность модульной ОП. Запропонована ймовірнісна модель блочної пам’яті з одним і декількома вхідни...
Gespeichert in:
| Veröffentlicht in: | Штучний інтелект |
|---|---|
| Datum: | 2010 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/56577 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Вероятностная модель блочной памяти / Л.П. Фельдман, Т.В. Михайлова // Штучний інтелект. — 2010. — № 3. — С. 547-551. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859761906907086848 |
|---|---|
| author | Фельдман, Л.П. Михайлова, Т.В. |
| author_facet | Фельдман, Л.П. Михайлова, Т.В. |
| citation_txt | Вероятностная модель блочной памяти / Л.П. Фельдман, Т.В. Михайлова // Штучний інтелект. — 2010. — № 3. — С. 547-551. — Бібліогр.: 2 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | Предложена вероятностная модель блочной памяти с одним и несколькими входными потоками, получены среднее число использованных банков и коэффициент загрузки, которое характеризует среднюю производительность модульной ОП.
Запропонована ймовірнісна модель блочної пам’яті з одним і декількома вхідними потоками, отримані середнє число використаних банків та коефіцієнт завантаження, яке характеризує середню продуктивність модульної ОП.
The probabilistic model of block memory with one and several input streams is suggested, the average number of used banks and factor of loading, which characterizes average capacity of module RAM are determined. The speed of memory under the same number of banks increases with the rise of independent flow of requests. However increasing of RAM capacity, which is got because of division of the general flow of the applications on L independent flows, requires the essential complication of management multiprocessor computing systems.
|
| first_indexed | 2025-12-02T03:57:52Z |
| format | Article |
| fulltext |
«Штучний інтелект» 3’2010 547
5Ф
УДК 004.272
Л.П. Фельдман, Т.В. Михайлова
Донецкий национальный технический университет, г. Донецк, Украина
feldman@r5.dgtu.donetsk.ua, tanya@r5.dgtu.donetsk.ua
Вероятностная модель блочной памяти
Предложена вероятностная модель блочной памяти с одним и несколькими входными потоками, получены
среднее число использованных банков и коэффициент загрузки, которое характеризует среднюю
производительность модульной ОП.
Введение
Для реализации основной памяти используют объединение нескольких интеграль-
ных микросхем (ИМС). Совокупность микросхем называют модулем памяти. Один или
несколько модулей образуют банк памяти.
В общем случае основная память вычислительного модуля практически всегда
имеет блочную структуру, то есть содержит несколько банков.
При использовании блочной памяти, состоящей из В банков, адрес ячейки А пре-
образуется в пару (b, w), где b – номер банка, w – адрес ячейки внутри банка [1].
Cхемы распределения разрядов адреса А между b и w:
– блочная (номер банка b определяет старшие разряды адреса);
– циклическая (b = A mod В; w = A div В);
– блочно-циклическая (комбинация двух предыдущих схем).
Типовая структура памяти, организованная в соответствии с блочной структурой,
показана на рис. 1.
Банк 1 Банк 2 Банк N
. . . . . . . . .
Дешифратор
Мультиплексор
Блок
управления
Регистр
адреса
Шина данных
Рисунок 1 – Структура основной памяти на основе блочной схемы
Выбор банка обеспечивается либо с помощью дешифратора номера банка памяти,
либо путем мультиплексирования информации. Емкость ОП равна суммарной емкости
составляющих, а быстродействие – быстродействию отдельного банка [1].
Фельдман Л.П., Михайлова Т.В.
«Искусственный интеллект» 3’2010 548
5Ф
Последовательный доступ в память обычно производится к ячейкам, имеющим
смежные адреса. Можно достичь в N (N – количество банков) раз большей скорости
обмена с памятью в целом, чем у отдельного ее банка, если обеспечить одновременное
последовательное обращение к данным в каждом из банков.
В блочно-циклической схеме расслоения памяти каждый банк состоит из неско-
льких модулей, адресуемых по круговой схеме. Адреса между банками распределены
по блочной схеме [1].
Целью работы является повышение эффективности работы блочной памяти на
основе её аналитической модели с блочно-циклической схемой расслоения с одним мо-
дулем в каждом банке.
Вероятностная модель блочной памяти
с одним входным потоком заявок
Основные предположения о функционировании блочной памяти, отражающие
организацию работы ОП:
1. Все модули ОП работают синхронно так, что за один такт (цикл обращения)
каждый модуль может обслужить не более одной заявки, а все модули не более N
заявок одновременно.
2. В каждом такте работы число заявок во входном потоке не меньше числа
банков системы, т.к. максимальная производительность всех существующих мультипро-
цессорных вычислительных систем достигается при вычислениях, производимых над
регулярно организованными массивами информации. Число обращения к ОП за коман-
дами мало по сравнению с обращением за операндами. Потоки в рассматриваемой мо-
дели – это потоки обращения к ОП за считыванием или записью векторов, каждый из
которых содержит элементов не менее, чем число банков ОП. Каждая заявка с равными
вероятностями 1/N требует обслуживания каждым из банков ОП.
3. Все заявки, которые могут быть обслужены в одном такте работы ОП, посту-
пают на обслуживание в соответствующие банки мгновенно, т.к. время пересылки од-
ной заявки в несколько раз меньше цикла памяти.
4. Распределение заявок по банкам памяти происходит в порядке очередности
этих заявок во входном потоке, из которого на обслуживание заявки поступают до тех
пор, пока не появится первая заявка с запросом на обслуживание занятым банком. Это
значит, что если какая-либо заявка не может быть обслужена в данном такте из-за заня-
тости соответствующего банка, то она блокирует поступления к банкам ОП всех после-
дующих заявок.
Интервал времени распределения и обслуживания заявок назовем тактом работы
системы. Обозначим п число заявок входного потока, выбранных на обслуживание в
одном такте, которое примем за состояние системы. Вероятность того, что первая заявка
из входного потока поступит на обслуживание, равна 1, так как она застает свободными
все N модулей. Вероятность р1 того, что из входного потока на обслуживание поступит
точно одна заявка, может быть вычислена как произведение вероятности того, что пер-
вая заявка поступит на обслуживание в один из N свободных банков, и вероятности
того, что вторая заявка требует обслуживания тем же банком, т.е. рl = 1/N.
Вероятность того, что из входного потока на обслуживание поступит ровно две
заявки, равна произведению вероятности поступления двух первых заявок на свободные
модули и вероятности того, что третья заявка требует обслуживания одним из двух уже
Вероятностная модель блочной памяти
«Штучний інтелект» 3’2010 549
5Ф
занятых банков, т.е. Р2 = ((N – 1)/N) x (2/N). Рассуждая аналогично, получим для вероят-
ности рn того, что из входного потока поступит на обслуживание ровно п заявок, формулу:
1 2 ( 1) ( 1)! , 1,
( )!n n
N N N n n N nP n N
N N N N N n N
− − − − − −
= ⋅ ⋅ ⋅ ⋅ ⋅ = =
−
. (1)
Таким образом, на множестве состояний {О, N} системы с заданным числом N об-
служивающих устройств банков ОП определена цепь Маркова с переходными вероятно-
стями рn , n ∈ {О, N}, задаваемыми (1). Граф состояний цепи Маркова приведен на рис. 2.
Среднее число банков, занятых обслуживанием в течение одного такта, можно
определить по формуле:
∑∑
−
×−==
=
N
1-n
n
2N
n
nср .
N)!nN(
n )!N(прN
1
1 (2)
Значения среднего числа занятых банков Nср приведены в табл. 1. Коэффициент
использования ОП, равный Rcp = Nср /N, падает с ростoм N и для количества банков
больше восьми достаточно низкий.
Рисунок 2 – Граф состояний цепи Маркова вероятностной модели блочной ОП
Таблица 1
Число банков Показатель 1 2 4 8 16 32
Ncp 1 1,5 2,22 3,25 4,70 6,77
Rcp 1 0,75 0,58 0,40 0,29 0,21
Вероятностная модель блочной памяти
с несколькими входными потоками заявок
Пусть в ОП, состоящую из N одинаковых банков памяти, поступают L незави-
симых параллельных потоков обращения к банкам ОП от устройств обработки и перифе-
рийных процессоров мультипроцессорной вычислительной системы. К ограничениям
для предыдущей модели добавятся следующие: между потоками установлен абсолют-
ный приоритет на обслуживание в ОП, убывающий с ростом номера потока; каждая
заявка любого потока с равными вероятностями 1/N требует обслуживания каждым из
N банков ОП; распределение заявок каждого потока по банкам ОП происходит в
порядке очередности этих заявок в данном потоке. Если какая-либо заявка l-го потока,
l = L,1 , не может быть обслужена в данном такте из-за занятости соответствующего бан-
ка, то эта заявка блокирует поступления к банкам ОП и всех последующих заявок l-го
потока. Затем происходит распределение на оставшиеся свободные модули ОП заявок
из (l + 1)-го потока и так далее.
Фельдман Л.П., Михайлова Т.В.
«Искусственный интеллект» 3’2010 550
5Ф
Состояние системы – число занятых банков nl, после окончания распределения
заявок из входного потока, с l-м приоритетом. Вероятность перехода из состояния пl-1
в состояние пl определяется:
1
1 1
( )!{ }
( )! l
l l
l l R
l
N n nP n n
N n N
−
− +
−
→ =
−
, (3)
где Rl = nl – nl-1 – число заявок, выбранных из l-го потока; Р{nl-1→nl} – вероятность
выбора на обслуживание равно nl заявок l-го потока при условии, что из потоков
более высокого, чем l-й, приоритет выбрано на обслуживание nl-1 заявок.
На рис. 3 приведена граф-схема марковской цепи для модели ОП с N банками и
L входными потоками заявок.
0 2
1
...
N
1/N
2/N
1/N
1/N
Рисунок 3 – Граф состояний цепи Маркова ОП с N банками и L входными потоками
В начальном состоянии цепи Маркова все модули памяти свободны, l-й шаг цепи
Маркова соответствует распределению заявок L-го входного потока.
Вероятность перехода Р{nl-1→nl} цепи Маркова определяется самими значения-
ми nl-1 = l и nl = j.
1
( )! , для l j, l =0,N
( )!
0 , для l j
j l
i j
N l j
N j Np + +
− ≤ −=
>
. (4)
Этот граф состояния можно использовать для любого числа L входных потоков
заявок. Матрица переходных вероятностей цепи Маркова, граф состояний которой
изображен на рис. 3, имеет вид
.
P000
PР00
PРР0
РРР0
Р
NN
N222
N11211
ОN0201
=
L
MMMMMMM
L
K
K
Для каждого состояния марковской модели определены следующие стацио-
нарные вероятности:
( )n lπ – вероятность застать на l-м шаге загруженные п банков памяти,
0 1( ) ( ( ), ( ),..., ( ))Nl l l lπ π π π= – вектор вероятностей состояний на l-м шаге, 0,l L= . По-
скольку начальное состояние известно, то известен и начальный вектор вероятностей
состояний
(0) (1, 0, 0, ..., 0).π =
Вероятностная модель блочной памяти
«Штучний інтелект» 3’2010 551
5Ф
Вектор вероятностей состояний на любом шаге l + 1 может быть найден по рекур-
рентной формуле:
l 1(l 1) (l)Р (0)Рπ π π ++ = = (5)
или в скалярной форме
.N1,n ,p)l()1l( l
N
1l
ln ==+ ∑
=
nππ (6)
Если определена вероятность πn (L) состояния п банков, занятых на L-м шаге,
то можно определить и среднее число банков, занятых обслуживанием
cp
1
( ) ( )
N
n
n
N L n Lπ
=
=∑ , (7)
которое характеризует среднюю производительность блочной ОП с блочно-модуль-
ной схемой расслоения.
В табл. 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 с.
Л.П. Фельдман, Т.В. Михайлова
Ймовірнісна модель блочної пам’яті
Запропонована ймовірнісна модель блочної пам’яті з одним і декількома вхідними потоками, отримані
середнє число використаних банків та коефіцієнт завантаження, яке характеризує середню продуктивність
модульної ОП.
L. Feldman, T. Mikhaylova
Probabilistic Model of Block Memory
The probabilistic model of block memory with one and several input streams is suggested, the average number of
used banks and factor of loading, which characterizes average capacity of module RAM are determined. The speed
of memory under the same number of banks increases with the rise of independent flow of requests. However
increasing of RAM capacity, which is got because of division of the general flow of the applications on L
independent flows, requires the essential complication of management multiprocessor computing systems.
Статья поступила в редакцию 14.07.2010.
|
| id | nasplib_isofts_kiev_ua-123456789-56577 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-02T03:57:52Z |
| publishDate | 2010 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Фельдман, Л.П. Михайлова, Т.В. 2014-02-19T21:57:40Z 2014-02-19T21:57:40Z 2010 Вероятностная модель блочной памяти / Л.П. Фельдман, Т.В. Михайлова // Штучний інтелект. — 2010. — № 3. — С. 547-551. — Бібліогр.: 2 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/56577 004.272 Предложена вероятностная модель блочной памяти с одним и несколькими входными потоками, получены среднее число использованных банков и коэффициент загрузки, которое характеризует среднюю производительность модульной ОП. Запропонована ймовірнісна модель блочної пам’яті з одним і декількома вхідними потоками, отримані середнє число використаних банків та коефіцієнт завантаження, яке характеризує середню продуктивність модульної ОП. The probabilistic model of block memory with one and several input streams is suggested, the average number of used banks and factor of loading, which characterizes average capacity of module RAM are determined. The speed of memory under the same number of banks increases with the rise of independent flow of requests. However increasing of RAM capacity, which is got because of division of the general flow of the applications on L independent flows, requires the essential complication of management multiprocessor computing systems. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Интеллектуальные системы планирования, управления, моделирования и принятия решений Вероятностная модель блочной памяти Ймовірнісна модель блочної пам’яті Probabilistic Model of Block Memory Article published earlier |
| spellingShingle | Вероятностная модель блочной памяти Фельдман, Л.П. Михайлова, Т.В. Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| title | Вероятностная модель блочной памяти |
| title_alt | Ймовірнісна модель блочної пам’яті Probabilistic Model of Block Memory |
| title_full | Вероятностная модель блочной памяти |
| title_fullStr | Вероятностная модель блочной памяти |
| title_full_unstemmed | Вероятностная модель блочной памяти |
| title_short | Вероятностная модель блочной памяти |
| title_sort | вероятностная модель блочной памяти |
| topic | Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| topic_facet | Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/56577 |
| work_keys_str_mv | AT felʹdmanlp veroâtnostnaâmodelʹbločnoipamâti AT mihailovatv veroâtnostnaâmodelʹbločnoipamâti AT felʹdmanlp imovírnísnamodelʹbločnoípamâtí AT mihailovatv imovírnísnamodelʹbločnoípamâtí AT felʹdmanlp probabilisticmodelofblockmemory AT mihailovatv probabilisticmodelofblockmemory |