Особенности построения имитационной модели многопроцессорной вычислительной системы С ОБЩЕЙ МНОГОМОДУЛЬНОЙ ПАМЯТЬЮ
Гилев Ю.М., Дерюгин А.А.
(Москва, Московский энергетический
институт (технический университет), Россия)
Объектом рассмотрения является многопроцессорная вычислительная система (МВС) с общей многомодульной памятью (рис.1).
В ее состав входят N процессоров (P) с кэш-памятью (CM), M модулей общей памяти (MM) и коммутаторов K. Число модулей памяти не превышает число процессоров (M ≤N).
В такой системе возникает конфликт в том случае, когда обращение двух или более процессоров идет одновременно к одному модулю памяти. При этом очередность обслуживания определяется службой приоритетов арбитра (AR), входящего в состав коммутатора. Существует три различные службы приоритетов арбитра: фиксированный, циклический и случайный.
В общем случае, вместо некоторых процессоров стоят устройства ввода/вывода (УВВ) со своими контроллерами прямого доступа к памяти (контроллеры ПДП или КПДП). Они, как и процессоры, являются активными элементами МВС. УВВ со своими КПДП можно рассматривать как процессоры ввода-вывода.
Каждый модуль памяти делается секционированным. Число секций модуля памяти определяется размером блока кэш-памяти (обычно 4 слова). Способ формирования адресов самих модулей памяти описан в [1].
Назначение рассматриваемой МВС – решение стационарного потока задач. Поток задач состоит из набора задач нескольких типов. Предполагается, что команды обработки задач заранее записаны в ММ. Данные для каждой задачи поступают через определенное УВВ через фиксированные интервалы времени. Каждая задача характеризуется своим графом, представленным в ярусно-параллельной форме. Каждый сегмент графа задачи выполняется на одном из процессоров. Сегменты графа могут выполнятся параллельно при наличии свободных процессоров.
Рис. 1. Структура МВС с общей многомодульной памятью
AR – арбитр; CM – кэш-память; K – коммутатор; MM – модуль общей памяти; P – процессор
Сегмент считается готовым к выполнению, если есть все необходимые данные для его решения. Для распределения готовых к выполнению сегментов задач по процессорам отводится один управляющий процессор (УП). Остальные процессоры – рабочие процессоры (РП) – предназначены для решения сегментов задач.
Целью построения модели МВС является определение, справляется ли заданная МВС с потоком задач, а также определение минимального числа процессоров, необходимого для решения заданного потока задач.
Модель какой-либо системы состоит из набора моделей ее элементов и правила их взаимодействия. Выбор элементов определяется требуемой степенью детализации. Правила взаимодействия моделей должны отражать реальные взаимодействия элементов системы на выбранном уровне детализации [2].
Модель элемента системы может находиться в каком-либо состоянии. Состоянию модели элемента соответствует определенный процесс в соответствующем элементе системы. Число состояний модели определяется числом выполняемых действий соответствующим элементом системы. Модель может переходить из одного состояния в другое, что означает переход элемента системы от выполнения одного действия к другому. Смена состояний модели называется событием. В отличие от реального перехода элемента системы от одного действия к другому, длительность события принимается равной нулю. Алгоритм смены состояний модели элемента определяется алгоритмом функционирования элемента системы.
Каждая модель элемента характеризуется набором своих состояний, алгоритмом смены состояний и уникальным идентификатором, определяющим эту модель элемента в модели системы.
Состояние модели всей системы в конкретный момент времени характеризуется набором состояний моделей ее элементов в этот момент.
Для учета длительности состояний моделей элементов в модель системы вводится счетчик текущего времени. Значение счетчика может быть выражено в реальных единицах времени, например в секундах, минутах и так далее, но может быть выражено и в модельных единицах времени. В последнем случае, должно быть установлено соответствие между реальными единицами времени и модельными.
Событие может сопровождаться передачей сообщения другим моделям элементов МВС. Сообщение должно содержать уникальный идентификатор, характеризующий тип этого сообщения и параметры.
Моделируемыми элементами системы в нашем случае являются: РП с кэш-памятью, УП, УВВ и ММ с коммутатором и арбитром. ММ с коммутатором и арбитром – единый элемент в модели, так как характеризуются единым набором состояний, определяемым арбитром.
Управляющий процессор получает сигналы от устройства ввода/вывода об окончании записи входных данных задачи и сигналы об окончании решения сегментов от рабочих процессоров.
Функциями управляющего процессора являются выбор готового к выполнению сегмента, выбор свободного процессора и назначение выбранного сегмента на свободный процессор. Назначение заключается в отправке сигнала рабочему процессору с указанием номера задачи и сегмента.
Рабочий процессор решает назначенный на него сегмент задачи и отправляет сигнал УП об окончании решения сегмента задачи. Для построения алгоритма решения задачи рабочим процессором приняты следующие допущения:
– РП считывает из ММ в кэш соответствующую прикладную программу решения сегмента не распределено в процессе его решения, а перед решением;
– РП считывает входные данные сегмента из ММ в кэш-память не распределено в процессе его решения, а перед решением;
– запись результатов в общую память осуществляется только после решения сегмента.
Время считывания программы можно определить из следующих предположений. Пусть команда выполняется в среднем за 2 такта. Тогда количество выполняемых команд NВЫП за время решения сегмента вычисляется по формуле:
,
где TSEG – время решения сегмента, TCY– длительность одного такта.
Число считываемых команд из оперативной памяти меньше этого значения, так как одни и те же команды могут, находясь в кэш-памяти, выполняться несколько раз (например, в цикле). Для вычисления числа считываемых из общей памяти команд введем коэффициент цикличности КЦИКЛ (например, 2). Тогда число считываемых из общей памяти команд NСЧИТ вычисляется по формуле:
. (1)
Если предположить, что средняя длина команды равняется одному слову, то это значение NСЧИТ будет равно числу считываемых слов.
Команды и входные данные сегмента считываются блоками. Последовательно идущие блоки располагаются в различных модулях памяти, доступом к каждому управляет соответствующий арбитр, входящий в состав коммутатора. Время, необходимое арбитру для выбора кандидата для передачи в модуль памяти, принято равным нулю.
Приход задач в МВС осуществляется через устройства ввода/вывода. Задача каждого типа приходит через определенное устройство ввода/вывода, то есть распределение задач по устройствам ввода/вывода осуществляется статически. Перед записью новых входных данных УВВ считывает результаты решения предыдущей задачи.
Взаимодействие УВВ с общей памятью осуществляется по словам в режиме прямого доступа к памяти на частоте работы общей памяти. Время TIN, требуемое для записи новых входных данных задачи объёмом VIN слов, определяется по формуле:
. (2)
Время TOUT , требуемое для считывания результатов решения задачи объёмом VOUT слов, определяется по формуле:
. (3)
Таким образом, можно построить имитационную модель МВС с общей многомодульной памятью, используя допущения, принятые для рабочих процессоров и используя формулы 1-3 для определения времен состояний моделей элементов МВС.
ЛИТЕРАТУРА:
1.
Гилев Ю.М., Дерюгин А.А. Особенности работы
многопроцессорной вычислительной системы с общей многомодульной памятью./Международный
форум информатизации – 2002: Доклады международной конференции «Информационные
средства и технологии». 14-16 октября 2003 г., в 3-х т.т. Т3. – М.: Янус-К,
2003. – 221 с.
2.
Марков А.А. Моделирование информационно-вычислительных
процессов: Учебное пособие для вузов. – М.: Изд-во МГТУ им.
Н.Э.Баумана,1999.-360 с.