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

INVESTIGATION OF THE CHARACTERISTICS OF HIGH-PERFORMANCE MULTIPROCESSOR SYSTEMS ON OPEN QUEUEING NETWORKS

Alexey Martyshkin

candidate of Science, assistant professor Department of Computational Systems and Machines of Penza State Technological University,

Russia, Penza

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

АННОТАЦИЯ

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

ABSTRACT

The article considers mathematical models of multiprocessor computing systems. To describe them using the method of open stochastic queuing from the general theory of queuing networks, mathematical apparatus which has been developed and is well described. It shows a generalized network model of service applications. Recommendations are given for the calculation of the models either analytically or using imitation programs. At the end of the article sets out the findings.

Ключевые слова: математическая модель, система массового обслуживания, аналитическое моделирование, имитационное моделирование вычислительная система, транзакция.

Keywords: mathematical model, a queuing system, analytical modeling, simulation, computer system, transaction.

При анализе вычислительных систем (ВС) выделяют макроанализ и микроанализ. Макроанализ проводят на этапе проектирования, когда определяется конфигурация системы под заданные требования. В качестве входных здесь выступают потоки задач, поступающих в ВС. Результаты макроанализа используются для оценки общей производительности ВС, времени ответа системы, латентности и др. Микроанализ производят с целью получения характеристик ВС на более низких уровнях проектирования, т. е. на уровне отдельных устройств или частей ВС.

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

Обмен по ОШ может производиться либо с расщеплением (с буферизацией), либо без расщепления транзакций (без буферизации данных). Режим расщепления транзакций уменьшает простой ОШ, неизбежный при выполнении определенных операций или команд. Например, транзакция чтения слова или строки кэш из удаленной памяти может быть расщеплена на две: передачу ЦП адреса в контроллер памяти и возвращения данных из памяти в ЦП. Между транзакциями образуется временной интервал, связанный с физическим процессом чтения данных из модуля памяти, в течение которого ОШ не задействована. Если посланный ЦП адрес ячейки памяти будет зафиксирован в буфере контроллера памяти, то ОШ может быть освобождена и использована другим ЦП для передачи своей транзакции. По окончании физического процесса чтения слова данных из памяти происходит деактивация строки запоминающей матрицы, а контроллер памяти одновременно с этим должен произвести необходимую процедуру по арбитражу ОШ и возвратить данные запрашивающему ЦП.

Еще одним классификационным признаком является способ назначения задач по ЦП: статический или динамический. При статическом распределении задача направляется в выделенный для неё ЦП. Это назначение не меняется в течение всего времени решения задачи. При динамическом – задачи направляются в любой свободный ЦП.

При исследовании ВС с различной архитектурой часто интересны её количественные характеристики. Наиболее актуальными характеристиками являются суммарная производительность МПС, латентность системы, средняя длина очередей к устройствам ВС и др. при заданных значениях структурных параметров и параметров задачи. К структурным параметрам относят: быстродействие ЦП V_ср; пропускная способность кэш–памяти V_K; пропускная способность основной памяти V_M; пропускная способность ОШ V_B; вероятность кэш-промахов p_m; вероятность появления события, связанного с необходимостью поддержанием кэш-когерентности p_k и др. К параметрам задачи относят: трудоемкость задачи T – число процессорных операций в последовательном алгоритме; трудоемкость одной ветви Q_i; трудоемкость одного этапа обработки алгоритма Q_0i, – число выполняемых ПУ операций между двумя последовательными обращениями к внешней памяти; интенсивность поступления заданий на решение задач (ветвей) l₀; число параллельных ветвей n.

Обобщенная модель для получения вероятностно-временных характеристик МПС, основанная на разомкнутых сетях массового обслуживания (РСеМО) [1], представлена на рисунке 1. В такой модели каждое устройство может представляться либо многоканальной СМО (рис. 1.2.а), либо одноканальной СМО, либо совокупностью одноканальных СМО (рис. 1.2.б).

Рисунок 1. Обобщенная сетевая модель обслуживания заявок (1) и типы моделей массового обслуживания отдельных устройств (2)

СМО S₀ является источником и поглотителем заявок. Она генерирует поток заявок l₀ на обслуживание запросов, формируемых пользователями или прикладными программами. Заявки с некоторой вероятностью вначале поступают на обслуживание в ПУ. Если заявка получила полное обслуживание, то она выходит из сети с вероятностью , где N – число этапов решения задачи в ПУ. Если в процессе выполнения задачи произошел кэш-промах, то заявка перемещается с вероятностью p_m на обслуживание памятью, иначе с вероятностью p_h она остается на обслуживании ЦП в совокупности с кэш. При страничных прерываниях заявка с вероятностью p_s поступает на обслуживание во внешнюю память.

Способ представления моделей устройств: ОШ, кэш, основной и внешней памяти зависит от их структурной организации, а ПУ – от примененного способа распределения задач. Так модель ОШ может быть представлена одноканальной СМО. В общем случае сеть межпроцессорного обмена может быть основана на множестве шин или на коммутаторе, тогда она представляется многоканальной СМО.

ПУ представляются совокупностью одноканальных СМО, если применено статическое назначение задач. При динамическом назначении задач ПУ представляется многоканальной СМО. Следует учитывать, что модель ПУ зависит от типа примененной архитектуры памяти UMA или NUMA [4]. Если применена архитектура UMA, то модель обслуживания состоит из ЦП и кэш. При использовании архитектуры NUMA, в модель обслуживания включают ещё и локальная память. Модель кэш-памяти является наиболее простой и представляется одноканальной СМО. Её основное назначение заключается в учете дополнительного трафика в сети, возникающего при выполнении операций, связанных с обеспечением когерентности.

Предложенную математическую модель МПС можно рассчитать либо аналитически, либо имитационно. Если времена обслуживания распределены по экспоненциальному закону, а потоки запросов являются пуассоновскими, то применяют аналитическое моделирование. В остальных случаях нужно применять имитационное моделирование. Для автоматизации расчетов можно воспользоваться визуальными программами аналитического и имитационного моделирования [2; 5].

Список литературы:

1. Алиев Т.И. Основы моделирования дискретных систем. – СПб.: СПбГУ ИТМО, 2009. – 363 с.
2. Бикташев Р.А., Мартышкин А.И., Востоков Н.Г. Комплекс программ для определения характеристик диспетчеров задач многопроцессорных систем с использованием приоритетных стохастических сетей массового обслуживания // Фундаментальные исследования. – 2013. – № 10 (ч. 1). – С. 13–20.
3. Бикташев Р.А., Князьков В.С. Многопроцессорные системы. Архитектура, топология, анализ производительности: Учебное пособие. – Пенза: Пенз. гос. ун-т, 2003. – 103 с.
4. Мартышкин А.И. Разработка аппаратного буферного устройства памяти многопроцессорной системы // Фундаментальные исследования. – 2015. – № 12 (ч. 3). – С. 485–489.
5. Мартышкин А.И., Бикташев Р.А., Востоков Н.Г. Программный комплекс для имитационного моделирования диспетчеров задач многопроцессорных систем с использованием приоритетных сетей массового обслуживания // Фундаментальные исследования. – 2014. – № 11 (ч. 10). – С. 2155–2159.