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

APPLICATION OF THE APPARATUS OF QUEUING THEORY FOR THE SYSTEM ANALYSIS OF MULTIPROCESSOR SYSTEMS

Karaseva E.A. 1 Martyshkin A.I. 1
1 Penza state technological university
At the system design stage of computing systems, analyze the options of the structural organization in order to obtain their characteristics without constructing a real system. To achieve the above goal, the article uses the widely accepted provisions and methods of queuing theory today. The types of analyzed structures, such as UMA and NUMA, are described in detail. The developer of specialized computing systems must know the quantitative characteristics of various ways of constructing such systems. All the characteristics of interest are obtained for given values ​​of the structural parameters and parameters of the problem. The structural parameters include processor speed, memory bandwidth, etc. The task parameters include the complexity of the solution of the problem, the complexity of one branch of the problem, the intensity of the receipt of tasks for processing, etc.
computer system
design
analysis
probability-time characteristics
processor node
priority
common bus

На системном этапе проектирования современных вычислительных систем (ВС) проводят анализ различных вариантов структурной организации с целью получения их характеристик без построения реальной системы. Наработан большой опыт по аналитическому и имитационному моделированию ВС и, в частности, многопроцессорных. В основном работы направлены на анализ аппаратных конфликтов, возникающих в общих ресурсах, таких как общая шина, общие блоки памяти, общие периферийные устройства, являющихся значительным фактором для снижения эффективной производительности многопроцессорных систем (МПС). Посредством аппарата теории массового обслуживания можно проводить исследования, например, реконфигурируемых [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 А).