На системном этапе проектирования современных вычислительных систем (ВС) проводят анализ различных вариантов структурной организации с целью получения их характеристик без построения реальной системы. Наработан большой опыт по аналитическому и имитационному моделированию ВС и, в частности, многопроцессорных. В основном работы направлены на анализ аппаратных конфликтов, возникающих в общих ресурсах, таких как общая шина, общие блоки памяти, общие периферийные устройства, являющихся значительным фактором для снижения эффективной производительности многопроцессорных систем (МПС). Посредством аппарата теории массового обслуживания можно проводить исследования, например, реконфигурируемых [2–5] и других вычислительных систем [6], т.е. проводить исследования в широкой сфере.
Типы анализируемых структур. Существует множество структурных решений МПС, зависящих от способов реализации общей памяти и коммутационной сети. Во-первых, это системы с сосредоточенной и распределённой архитектурами памяти. В первом типе структуры вся память размещается вне вычислительных узлов (ВУ), т.е. является удаленной (рис. 1, а). В ВУ включается только кэш одного или нескольких уровней. Время доступа каждого ВУ к любой ячейке общей памяти является одинаковым. Во втором типе структуры ВУ содержит не только кэш, но и подключенную к локальной шине часть основной памяти (рис. 1, б). Адресное пространство и в первом и во втором типах архитектуры является единым и делится между ВУ. Общий объем адресуемой памяти определяется возможностями системы адресации процессоров, составляющих многопроцессорную систему.
Рис. 1. Многопроцессорные системы с архитектурами памяти типа UMA (а) и NUMA (б)
Другим классификационным признаком является способ организации межпроцессорной связи, которая осуществляется с помощью коммутационных сетей, подразделяющихся на два типа: с временной и пространственной коммутацией.
Организация внешней памяти структурно схожа с организацией общей памяти. Также как и общая память, она может размещаться либо локально, либо с доступом через коммутационную сеть. Возможна также гибридная организация внешней памяти, когда одна часть устройств доступна процессорам локально, другая часть имеет удаленный доступ.
Третьим классификационным признаком является принятый операционной системой способ распределения задач или ветвей задачи по ВУ: статический или динамический. В первом способе задача (или её ветвь) назначается выделенному ВУ, и это назначение не меняется за все время её решения. Во втором способе задачи (ветви задачи) назначаются в любой свободный ВУ, причем освободившийся ВУ запрашивает у диспетчера очередную готовую к выполнению задачу.
Разработчика специализированных МПС в первую очередь интересуют количественные характеристики различных способов построения таких систем. Все характеристики получают при заданных значениях структурных параметров и параметров задачи.
К структурным параметрам относятся [1]: быстродействие ВУ; пропускная способность кэш-памяти; пропускная способность основной памяти; пропускная способность коммутационной сети; скорость передачи данных дисковой памятью; вероятность появления кэш-промахов; вероятность появления события, связанного с поддержанием кэш-когерентности pk.
К параметрам задачи относятся: трудоемкость решения задачи T – число процессорных операций в последовательном алгоритме; трудоемкость одной ветви Θi – число процессорных операций, приходящихся на один ВУ; трудоемкость одного этапа обработки алгоритма Θ0i – число выполняемых ВУ операций между двумя последовательными обращениями к внешней памяти; интенсивность поступления заданий на решение задач (ветвей) λ0; число параллельных ветвей n.
Моделирование на основе стохастических сетей массового обслуживания. Стохастические сети вполне адекватно отображают процессы функционирования многопроцессорных систем и дают приемлемые результаты для оценки их вероятностно-временных характеристик.
Рассмотрим открытую стохастическую сеть массового обслуживания, содержащую n систем обслуживания (СМО) S1, S2..., Sn. Примем, что заявки на обслуживание поступают в сеть из единственного источника S0. Поглощение обслуженных заявок происходит также в СМО S0 (рис. 2). Заявки из источника с вероятностью P0i могут поступать в любую из СМО. Внутри сети заявки перемещаются случайным образом и могут покинуть её из любой СМО с вероятностью Pi0.
Рис. 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 будет иметь следующий вид:
,
где 
, 
.
При заданных параметрах определяются характеристики стохастической сети: интенсивность входящего в каждую СМО сети lj; средняя длина очереди заявок в i-й СМО li и во всей сети L; среднее число заявок, пребывающих в i-й СМО mi и во всей сети M; среднее время ожидания обслуживания заявки i-й СМО ii и во всей сети W; среднее время пребывания заявки в i-й СМО ui и во всей сети U.
Работа выполнена при финансовой поддержке РФФИ (Проект № 16–07–00012 А).
Библиографическая ссылка
Карасева Е.А., Мартышкин А.И. ПРИМЕНЕНИЕ АППАРАТА ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ ДЛЯ СИСТЕМНОГО АНАЛИЗА МНОГОПРОЦЕССОРНЫХ СИСТЕМ // Международный студенческий научный вестник. – 2017. – № 4-9. ;URL: https://eduherald.ru/ru/article/view?id=17720 (дата обращения: 21.11.2024).