Электронный научный журнал
Международный студенческий научный вестник
ISSN 2409-529X

ПРИМЕНЕНИЕ АППАРАТА ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ ДЛЯ СИСТЕМНОГО АНАЛИЗА МНОГОПРОЦЕССОРНЫХ СИСТЕМ

Карасева Е.А. 1 Мартышкин А.И. 1
1 Пензенский государственный технологический университет
На системном этапе проектирования вычислительных систем проводить анализ вариантов структурной организации с целью получения их характеристик без построения реальной системы. Для достижения указанной выше цели в статье используются широко применяемые сегодня положения и методы теории массового обслуживания. Подробно описываются типы анализируемых структур, таких как UMA и NUMA. Разработчик специализированных вычислительных систем должен знать количественные характеристики различных способов построения таких систем. Все интересующие характеристики получают при заданных значениях структурных параметров и параметров задачи. К структурным параметрам относятся быстродействие процессора, пропускная способность памяти и др. К параметрам задачи относятся трудоемкость решения задачи, трудоемкость одной ветви задачи, интенсивность поступления задач на обработку и др.
вычислительная система
проектирование
анализ
вероятностно-временные характеристики
процессорный узел
приоритет
общая шина
1. Бикташев Р.А., Князьков В.С. Многопроцессорные системы. Архитектура, топология, анализ производительности. – Пенза: Пенз. гос. ун-т, 2004. – 108 с.
2. Мартенс-Атюшев Д.С., Мартышкин А.И. Разработка и исследование реконфигурируемого вычислительного кластера для цифровой обработки сигнала // Современные информационные технологии. 2015. – № 21. – С. 190–195.
3. Мартенс-Атюшев Д.С., Мартышкин А.И. Разработка и исследование реконфигурируемой системы для цифровой обработки сигнала // Международный студенческий научный вестник. 2016. – № 3–1. – С. 86–88.
4. Мартенс-Атюшев Д.С., Мартышкин А.И. Разработка реконфигурируемой вычислительной системы для цифровой обработки сигнала // Технические науки – от теории к практике. 2015. – № 52. – С. 50–58.
5. Мартенс-Атюшев Д.С., Мартышкин А.И. Реконфигурируемый вычислительный кластер для цифровой обработки сигнала // Современные методы и средства обработки пространственно-временных сигналов сборник статей XIII Всероссийской научно-технической конференции / Под ред. И.И. Сальникова. 2015. – С. 112–117.
6. Мартышкин А.И. Математическая модель диспетчера задач с общей очередью для систем параллельной обработки // Современные методы и средства обработки пространственно-временных сигналов: Сборник статей XI Всероссийской научно-технической конференции / Под ред. И.И. Сальникова, 2013. – С. 87–91.

На системном этапе проектирования современных вычислительных систем (ВС) проводят анализ различных вариантов структурной организации с целью получения их характеристик без построения реальной системы. Наработан большой опыт по аналитическому и имитационному моделированию ВС и, в частности, многопроцессорных. В основном работы направлены на анализ аппаратных конфликтов, возникающих в общих ресурсах, таких как общая шина, общие блоки памяти, общие периферийные устройства, являющихся значительным фактором для снижения эффективной производительности многопроцессорных систем (МПС). Посредством аппарата теории массового обслуживания можно проводить исследования, например, реконфигурируемых [2–5] и других вычислительных систем [6], т.е. проводить исследования в широкой сфере.

Типы анализируемых структур. Существует множество структурных решений МПС, зависящих от способов реализации общей памяти и коммутационной сети. Во-первых, это системы с сосредоточенной и распределённой архитектурами памяти. В первом типе структуры вся память размещается вне вычислительных узлов (ВУ), т.е. является удаленной (рис. 1, а). В ВУ включается только кэш одного или нескольких уровней. Время доступа каждого ВУ к любой ячейке общей памяти является одинаковым. Во втором типе структуры ВУ содержит не только кэш, но и подключенную к локальной шине часть основной памяти (рис. 1, б). Адресное пространство и в первом и во втором типах архитектуры является единым и делится между ВУ. Общий объем адресуемой памяти определяется возможностями системы адресации процессоров, составляющих многопроцессорную систему.

ka1.tiff

Рис. 1. Многопроцессорные системы с архитектурами памяти типа UMA (а) и NUMA (б)

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

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

Третьим классификационным признаком является принятый операционной системой способ распределения задач или ветвей задачи по ВУ: статический или динамический. В первом способе задача (или её ветвь) назначается выделенному ВУ, и это назначение не меняется за все время её решения. Во втором способе задачи (ветви задачи) назначаются в любой свободный ВУ, причем освободившийся ВУ запрашивает у диспетчера очередную готовую к выполнению задачу.

Разработчика специализированных МПС в первую очередь интересуют количественные характеристики различных способов построения таких систем. Все характеристики получают при заданных значениях структурных параметров и параметров задачи.

К структурным параметрам относятся [1]: быстродействие ВУ; пропускная способность кэш-памяти; пропускная способность основной памяти; пропускная способность коммутационной сети; скорость передачи данных дисковой памятью; вероятность появления кэш-промахов; вероятность появления события, связанного с поддержанием кэш-когерентности pk.

К параметрам задачи относятся: трудоемкость решения задачи T – число процессорных операций в последовательном алгоритме; трудоемкость одной ветви Θi – число процессорных операций, приходящихся на один ВУ; трудоемкость одного этапа обработки алгоритма Θ0i – число выполняемых ВУ операций между двумя последовательными обращениями к внешней памяти; интенсивность поступления заданий на решение задач (ветвей) λ0; число параллельных ветвей n.

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

Рассмотрим открытую стохастическую сеть массового обслуживания, содержащую n систем обслуживания (СМО) S1, S2..., Sn. Примем, что заявки на обслуживание поступают в сеть из единственного источника S0. Поглощение обслуженных заявок происходит также в СМО S0 (рис. 2). Заявки из источника с вероятностью P0i могут поступать в любую из СМО. Внутри сети заявки перемещаются случайным образом и могут покинуть её из любой СМО с вероятностью Pi0.

ka2.tiff

Рис. 2. Пример открытой сети с единственным источником заявок

Такая постановка не противоречит теории сетей массового обслуживания [1] и вызвана тем, что в ВС существует единственный вход, куда поступают задания на выполнение программ – процессор или процессорный блок. В качестве источника заявок могут выступать задания, поступающие от периферийных устройств (терминалов, контроллеров, различного рода датчиков и других источников) или от компьютеров в системах с распределенной обработкой и др.

Стохастическая сеть задаётся следующими параметрами [1]: числом n СМО в сети (S0,S1,…,Sn), где S0 – фиктивная СМО, моделирующая источник заявок с интенсивностью их обслуживания λ0; числом каналов ki в каждой СМО сети (k1, k2,...,kn); интенсивностью потока заявок λ0 источника S0; интенсивностью потока на входе i-й СМО ii; средним временем обслуживания заявок в каждой СМО сети (v1, v2,...,vn); матрицей вероятности передач P=[pij], где pij- вероятность того, что заявка, покидающая СМО Si, поступит на обслуживание в СМО Sj.

Для сети, состоящей из n СМО, матрица P будет иметь следующий вид:

k1.wmf,

где k2.wmf, k3.wmf.

При заданных параметрах определяются характеристики стохастической сети: интенсивность входящего в каждую СМО сети lj; средняя длина очереди заявок в i-й СМО li и во всей сети L; среднее число заявок, пребывающих в i-й СМО mi и во всей сети M; среднее время ожидания обслуживания заявки i-й СМО ii и во всей сети W; среднее время пребывания заявки в i-й СМО ui и во всей сети U.

Работа выполнена при финансовой поддержке РФФИ (Проект № 16–07–00012 А).


Библиографическая ссылка

Карасева Е.А., Мартышкин А.И. ПРИМЕНЕНИЕ АППАРАТА ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ ДЛЯ СИСТЕМНОГО АНАЛИЗА МНОГОПРОЦЕССОРНЫХ СИСТЕМ // Международный студенческий научный вестник. – 2017. – № 4-9.;
URL: http://eduherald.ru/ru/article/view?id=17720 (дата обращения: 06.08.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074