Возможности исследования и анализа основных вероятностно-временных характеристик многопроцессорных систем методом моделирования

АННОТАЦИЯ

Сегодня всё большее применение находят высокопроизводительные вычислительные системы, например, распределённые и многопроцессорные системы. В статье рассмотрены вопросы, касающиеся проблем аналитического моделирования многопроцессорных вычислительных систем c общей шиной и разделяемой памятью. Упомянутый вид моделирования проводят на системном этапе проектирования любой вычислительной системы. Широко известны и активно применяются два основных этапа анализа вычислительных систем: макроанализ и микроанализ, отличающиеся назначением. В результате аналитического моделирования получают вероятностно-временные характеристики различных вариантов структур без фактического построения реальной системы. Кроме количественных оценок рассмотренные методы анализа позволяют получать и качественные. В этом и заключается ценность аналитического моделирования, необходимость применения которого обычно объясняется существованием задержек вычислительного процесса из-за ограниченности системных ресурсов. Основной целью, поставленной в статье, является определение аналитических формул для оценки времен обмена в подсистеме «процессор-память» многопроцессорных систем с общей шиной. Для достижения поставленной цели использованы методы теории массового обслуживания, а именно: разомкнутые сети массового обслуживания, средства, хорошо разработанные и описанные. Результатами настоящей статьи являются выражения и выкладки для расчета основных вероятностно-временных характеристик многопроцессорных систем. В заключении сделаны выводы по работе. Использование приведенных в статье результатов имеет важное практическое значение, они будут полезны разработчикам новых многопроцессорных вычислительных систем. Ведь проще проводить исследование проектируемой системы на модельном уровне, чем строить реальную систему.

ABSTRACT

Nowadays high-performance computing systems find more application such as distributed and multiprocessor systems. The article deals with issues relating to problems of analytical modeling of multiprocessor computer systems with shared bus and shared memory. The mentioned type of modeling is carried out at the system design stage of any computer system. Two main stages of the analysis of computer systems are widely known and actively used: macroanalysis and microanalysis which differ in purpose. As a result of analytical modeling, random time characteristics of different structural options without actual building of the real system are obtained. Besides quantitative estimations, considered analysis methods allow obtaining qualitative ones. Therein lies the value of analytical modeling, the application necessity of which is usually attributed to the existence of delays in the computational process due to limited system resources. The main objective, set in the article, is to determine analytical formulas for evaluation of the time exchange in the subsystem “processor-memory” of multiprocessor systems with the shared bus. To achieve this goal, methods of the queuing theory are used, namely: open-loop networks of the mass service, means which are well-designed and described. Results of this article are expressions and displays to calculate basic random time characteristics of multiprocessor systems. Finally, conclusions are drawn in the article. Using the above mentioned results in the article has practical importance; they will be useful for developers of new multiprocessor systems. It is easier to conduct research in the designed system at the model level than to build up a real system.

Аналитическое, имитационное или аналитико-имитационное моделирование), а назначением. моделирование проводят на системном этапе проектирования вычислительной системы (ВС). По результатам моделирования получают характеристики различных вариантов структур ВС без построения реальной системы. Широко известно два основных этапа анализа ВС: макроанализ и микроанализ [2]. Эти этапы отличаются не методами анализа (измерение, аналитическое

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

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

Кроме количественных оценок упомянутые виды анализа позволяют получать и качественные, т. к. в процессе аналитического моделирования вскрывается сущность процессов, происходящих в ВС. В этом и есть познавательная ценность метода аналитического моделирования. Необходимость применения аналитического моделирования ВС объясняется существованием задержек вычислительного процесса из-за ограниченности ресурсов системных. Более всего этому явлению подвержены многопроцессорные вычислительные системы (МПВС), где ресурсы разделяются не только между устройствами, как у однопроцессорных ВС, но ещё и между несколькими процессорами, претендующими на доступ к ним [1; 2; 18; 19].

В ВС существует множество источников задержек: процессор, оперативная и кэш-память, внешние запоминающие устройства, каналы ввода-вывода, шины обмена и др. Соперничество за память, пожалуй, является наиболее распространенной причиной замедле­ния [4; 6]. Память разделяется несколькими устройствами, включая процессоры, каналы прямого доступа к памяти, и др. Даже если память организуется в виде нескольких независимых блоков, пропускная способность которой выше одноблочной, всё равно избежать конфликтов не удаётся из-за случайного характера обращений к этим блокам [7; 15; 20].

Разделение общей шины (ОШ) между устройствами ВС также ведет к замедлению, т.к. при большой загрузке ОШ, на­пример, в случае попытки одновременно занять ее несколькими процессорами, после обнаружения конфликта продолжится работа только одного устройства, другие будут приостановлены. Поэтому соперничество за ОШ требует детального анализа, поскольку возникающие конфликты влияют на пропускную способность ОШ и, в конечном счете, на производительность МПВС в целом [5; 17].

Рисунок 1. Архитектура многопроцессорной вычислительной системы
с общей шиной и разделяемой памятью

МПВС является симметричной (SMP) системой [2], содержащей два или более процессоров, общую память (ОП₁ – ОП_m), общие внешние запоминающие устройства (ВЗУ₁ – ВЗУ_к). Процессор, КЭШ и шинный интерфейс (ШИ) составляют вычислительный модуль (ВМ). Все ВМ имеют доступ ко всем ресурсам МПВС.

Известно два способа организации разделяемой памяти: сосредоточенный (здесь обеспечивается одинаковое время доступа для всех процессоров, поэтому ее называют UMA [13], а системы с такой организацией памяти называют SMP-системами) и распределенный (система памяти с единым адресным пространством, распределенная по ВМ и доступная для процессоров с не одинаковым временем, ее называют NUMA [3; 12; 13]).

Арбитраж ОШ может производиться либо в соответствии с присвоенными ВМ₁ – ВМ_n приоритетами, либо в порядке поступления запросов.

Обмен информацией осуществляется по ОШ, разделяемой всеми устройствами, причем обмен ведется блоками определенной длины. Между КЭШ и памятью обмен производится строками, а между памятью и ВЗУ – страницами. Все процессоры одновременно обрабатывают данные, хранящиеся в единой памяти системы. В процессе выполнения программы происходит обращение как к строкам, размещенным в КЭШ, так и к страницам, находящимся в ОП и ВЗУ. Обмен данными между процессором и памятью по ОШ может производиться либо с буферизацией сообщений [8; 9; 10; 11; 16], либо без буферизации [14]. В первом случае в контроллер ОП и в шинный интерфейс включаются буферы типа КЭШ II и III уровней. Если применяется обмен без буферизации, то для записи или чтения слова используется обычный цикл шины процессора. По окончании цикла шины память освобождается и может быть передана в распоряжение другому ВМ. Время обмена составляет

t_o=t+ t_мс,                                                   (1)

где: t – время арбитража ОШ;

t_мс – цикл шины процессора, связанный с обращением в ОП.

Время арбитража зависит от способа управления ОШ, а цикл шины зависит от типа процессора, но не зависит от цикла памяти, если цикл памяти и цикл шины сбалансированы (т.е. цикл памяти не создаёт задержек выполнения команды процессором, когда отсутствуют помехи от других процессоров).

Пропускная способность ОШ может варьироваться, поскольку она зависит от ширины шины, определяемой величиной, обратной числу циклов шины, необходимых для передачи одного слова данных. Если обозначить ширину шины буквой b, то при b=1 число линий в шине равно числу разрядов в информационной части передаваемого сообщения. Для небольших МПВС, как правило, b=1. В крупных системах b>>1, т. е. разрядность только системной шины данных составляет 64 – 256 или более разрядов. От величины b зависят характеристики шинного интерфейса. Чем меньше b, тем меньше затраты на изготовление интерфейсного оборудования, однако ниже пропускная способность, и, следовательно, потенциальная производительность и масштабируемость системы.

Учитывая, что число слов, передаваемых в одном пакете, составляет N, а на одну команду приходится C циклов шины, и каждый машинный цикл выполняется за T машинных тактов, то время обмена процессора с ОП при выполнении одной команды составит

t_o=t+ μt_T ,                                                           (2)

где: μ= C∙T / b∙N.

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

При применении способа обмена с буферизацией сообщений цикл шины значительно сокращается и становится много меньше цикла памяти, поскольку время обмена между КЭШ разных уровней составляет 1–3 процессорных такта, что значительно меньше времени обмена с ОП. Следовательно, в течение цикла памяти возможна передача по ОШ нескольких слов. Отсюда ясно, что число модулей в ОП может быть увеличено во столько раз, во сколько цикл памяти больше цикла шины. Время обращения к ОП составит

t_o=t+ t_B+p t_мс ,                                                   (3)

где: t_B – время обращения к буферной памяти,

p – вероятность отсутствия адресуемых данных в буфере.

Поскольку t_B << t_мс и p=1/M, где M – число обращений в буферную память, приходящихся на одно обращение к ОП, то приближенное время обмена с разделяемой памятью при выполнении одной команды процессором составит

t_o=t+ μt_T /M.                                                       (4)

Программы и данные первоначально размещаются в ВЗУ. Запускаемые программы и нуждающиеся в обработке данные хранятся в ОП, но лишь их небольшая часть, используемая наиболее интенсивно, копируется в КЭШ ВМ, где реализуется вычислительный процесс. Если при запросе памяти процессор не обнаружит в КЭШ необходимой строки, то возникает КЭШ-промах, по которому нужная страница «подкачивается» из ОП. Если нужная страница отсутствует в ОП, то возникает страничное прерывание, вызывающее обращение к ВЗУ.

В процессе выполнения программ возможно изменение данных в КЭШ j-го процессора. Чтобы сохранить единство данных необходимо такие же изменения произвести в ее копиях, хранящихся в КЭШ других процессоров. Для этой цели применяют механизм поддержки когерентности данных, следящий за тем, чтобы операции с одними и теми же данными происходили не одновременно во всех процессорах, а последовательно во времени, причем устаревшие копии необходимо удалять и заменять обновленными. Для поддержания когерентности используют шину слежения [2]. Для того чтобы все КЭШ были когерентными, каждый процессор ведет контроль ОШ, выявляя операции считывания-записи между другими процессорами и ОП, которые влияют на содержимое их собственных КЭШ. Когда j-ый процессор записывает свою измененную i-ю строку из собственной КЭШ в ОП, то другие, обнаруживая прохождение этой записи по ОШ, удаляют устаревшие копии i-й строки из собственных КЭШ.

КЭШ-промахи, страничные сбои и механизм поддержания когерентности вносят значительные задержки в вычислительный процесс и создают повышенный трафик на ОШ. Для оценки влияния этих процессов на характеристики систем SMP-архитектуры можно применять аналитическую модель, основанную на разомкнутых стохастических сетях массового обслуживания.

Принято считать, что потоки заданий на решение задач формируются локальными терминалами или поступают по локальной или глобальной сети. Кроме того, принято, что каждый процессор производит обработку заданий в мультипрограммном режиме. Пусть на вход системы поступает поток заданий на решение задач с интенсивностью l, причем задания распределяются динамически, т.е. новое задание направляется в свободный процессор. Предполагается, что задачи распараллелены на n независимых ветвей, каждая из которых может обрабатываться на любом свободном процессоре. Пусть p_к – суммарная вероятность появления КЭШ-промахов в n процессорах системы, определяемая числом КЭШ-промахов N_к; p_s – суммарная вероятность страничного сбоя, определяемая числом страничных прерываний N_s. Тогда считая, что вычислительный процесс начинается в процессоре и заканчивается в процессоре, число этапов счета составит N=N_k+N_s+1, а вероятность получения результата (вероятность выхода заявки из сети) составит p_r=1- (p_к+p_s). Если считать, что при каждом КЭШ-промахе происходит процедура замены устаревших копий во всех КЭШ SMP-системы (что соответствует наихудшему варианту), то интенсивность потока запросов в ОП составит l_оп=n×p_к×l_цп, где l_цп=N×l – интенсивность потока заявок на входе процессора. Интенсивность потока запросов к ВЗУ составит l_ВЗУ=n×p_S×l_цп.

Среднее время обслуживания одного задания в процессоре составляет t_цп=Θ₀/V_цп, где Θ₀ – трудоемкость вычислительных операций, в среднем приходящихся на одно задание, V_цп – быстродействие процессора. Причём Θ₀ = Θ/N, где Θ – трудоемкость задачи [2], измеряемая числом команд, реализуемых алгоритмом задачи. Среднее время доступа к странице в ОП, t_оп=q/V_оп, где q – объем страницы, а V_оп – пропускная способность ОП. Среднее время обмена с ВЗУ состоит из времени доступа к заданному сектору (t_д) и времени передачи страницы в ОП t_взу= t_д+q/V_взу, где V_взу – скорость передачи данных в ВЗУ. Среднее время передачи данных каналом прямого доступа в память составит t_квв=p_s×q/V_взу, а среднее время обмена через ОШ t_ош=p_s×t_квв+p_к×t_оп. Если принять допущение, что времена обслуживания распределены по экспоненциальному закону, а потоки запросов являются пуассоновскими, то анализ функционирования SMP-системы сводится к получению характеристик стохастической сети массового обслуживания, в которой процессорный блок является многоканальной СМО, а узлы ОП, ВЗУ, КВВ и ОШ – одноканальными.

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