Методические указания АВС — 2009

Оглавление

13 TOC \h \z \t "T1;1;T2;2;T3;3;T4;4" 1413 LINK \l "_Toc246557541" 14Оглавление 13 PAGEREF _Toc246557541 \h 1411515
13 LINK \l "_Toc246557542" 14Задание № 1 13 PAGEREF _Toc246557542 \h 1421515
13 LINK \l "_Toc246557543" 14Оценка характеристик параллелизма задач 13 PAGEREF _Toc246557543 \h 1421515
13 LINK \l "_Toc246557544" 141.1. Цель работы 13 PAGEREF _Toc246557544 \h 1421515
13 LINK \l "_Toc246557545" 141.2. Порядок выполнения работы 13 PAGEREF _Toc246557545 \h 1421515
13 LINK \l "_Toc246557546" 141.3. Теоретические положения 13 PAGEREF _Toc246557546 \h 1421515
13 LINK \l "_Toc246557547" 141.3.1. Параллелизм данных 13 PAGEREF _Toc246557547 \h 1431515
13 LINK \l "_Toc246557548" 141.3.2. Параллелизм задач 13 PAGEREF _Toc246557548 \h 1451515
13 LINK \l "_Toc246557549" 141.3.3. Синхронные вычисления 13 PAGEREF _Toc246557549 \h 14101515
13 LINK \l "_Toc246557550" 141.3.4. Асинхронные вычисления 13 PAGEREF _Toc246557550 \h 14111515
13 LINK \l "_Toc246557551" 141.3.5. Исследование ВС на основе диаграмм Ганта 13 PAGEREF _Toc246557551 \h 14131515
13 LINK \l "_Toc246557552" 141.3.6. Конвейерная обработка 13 PAGEREF _Toc246557552 \h 14141515
13 LINK \l "_Toc246557553" 141.3.7. Оценка эффективности конвейера процессоров 13 PAGEREF _Toc246557553 \h 14161515
13 LINK \l "_Toc246557554" 141.4. Пример расчета 13 PAGEREF _Toc246557554 \h 14181515
13 LINK \l "_Toc246557555" 141.5. Варианты заданий 13 PAGEREF _Toc246557555 \h 14261515
13 LINK \l "_Toc246557556" 141.6. Содержание отчета 13 PAGEREF _Toc246557556 \h 14281515
13 LINK \l "_Toc246557557" 141.7. Требования к оформлению 13 PAGEREF _Toc246557557 \h 14281515
13 LINK \l "_Toc246557558" 141.8. Контрольные вопросы (некоторые контрольные вопросы требуют изучения дополнительного материала) 13 PAGEREF _Toc246557558 \h 14281515
13 LINK \l "_Toc246557559" 14Задание № 2 13 PAGEREF _Toc246557559 \h 14301515
13 LINK \l "_Toc246557560" 14Расчет быстродействия процессора и параметров типового задания вычислительной системы 13 PAGEREF _Toc246557560 \h 14301515
13 LINK \l "_Toc246557561" 142.1. Цель работы 13 PAGEREF _Toc246557561 \h 14301515
13 LINK \l "_Toc246557562" 142.2. Порядок выполнения работы 13 PAGEREF _Toc246557562 \h 14301515
13 LINK \l "_Toc246557563" 142.3. Теоретические положения 13 PAGEREF _Toc246557563 \h 14301515
13 LINK \l "_Toc246557564" 142.3.2. Определение параметров типового задания 13 PAGEREF _Toc246557564 \h 14321515
13 LINK \l "_Toc246557565" 142.3.3. Расчет минимального быстродействия процессора 13 PAGEREF _Toc246557565 \h 14341515
13 LINK \l "_Toc246557566" 142.3.4. Основы построения стохастических сетевых моделей систем оперативной обработки 13 PAGEREF _Toc246557566 \h 14371515
13 LINK \l "_Toc246557567" 142.3.5. Размещение файлов в накопителях внешней памяти 13 PAGEREF _Toc246557567 \h 14391515
13 LINK \l "_Toc246557568" 142.3.6. Определение параметров минимальной конфигурации СОО 13 PAGEREF _Toc246557568 \h 14401515
13 LINK \l "_Toc246557569" 142.3.7. Построение стохастической сетевой модели соо минимальной конфигурации 13 PAGEREF _Toc246557569 \h 14421515
13 LINK \l "_Toc246557570" 142.3.8. Расчет характеристик ВС на основе стохастической сетевой модели 13 PAGEREF _Toc246557570 \h 14441515
13 LINK \l "_Toc246557571" 142.4. Варианты заданий 13 PAGEREF _Toc246557571 \h 14471515
13 LINK \l "_Toc246557572" 142.5. Содержание отчета 13 PAGEREF _Toc246557572 \h 14501515
13 LINK \l "_Toc246557573" 142.6. Контрольные вопросы 13 PAGEREF _Toc246557573 \h 14501515
13 LINK \l "_Toc246557574" 14Список литературы 13 PAGEREF _Toc246557574 \h 14521515
15
Задание № 1
Оценка характеристик параллелизма задач
1.1. Цель работы
1.1.1. Ознакомление с основными характеристиками параллелизма задач по ярусно-параллельной форме (ЯПФ) алгоритма, приобретение навыков построения ЯПФ и оценки ее характеристик на примере вычисления арифметического выражения.
1.1.2. Ознакомление с архитектурой параллельных вычислительных систем класса МКМД, освоение методов реализации параллельных алгоритмов на ВС и способов оценки эффективности параллельных ВС.
1.1.3. Ознакомление с принципом реализации конвейерных вычислительных систем, освоение методов подготовки задач для конвейера процессоров и приобретение навыков оценки эффективности конвейерных ВС.
1.2. Порядок выполнения работы
1.2.1. Изучить раздел 1.3 настоящих указаний и соответствующие разделы рекомендованных источников [2, 8].
1.2.2. По заданному преподавателем варианту (см. табл. 1.1) составить ЯПФ алгоритма вычисления арифметического выражения и оценить основные характеристики параллелизма: длину и ширину ЯПФ, коэффициенты ускорения и загрузки. Число процессоров в ВС принять равным ширине ЯПФ. Сделать выводы об эффективности созданной системы.
Используя полученную ЯПФ арифметического выражения, вычислить характеристики эффективности ее реализации (коэффициент ускорения и загрузки) на B-процессорной ВС в синхронном и асинхронном режимах. Повторить вычисления для (В–1)-процессорной системы. Сравнить результаты и сделать выводы.
Используя методику раздела 1.3, построить конвейер процессоров для вычисления заданного арифметического выражения (используя в качестве начальной (B–1)-процессорную ВС) и оценить характеристики этого конвейера относительно характеристик последовательной синхронной реализации ЯПФ арифметического выражения.
1.2.3. Оформить отчет по работе (см. п. 1.6).
1.3. Теоретические положения
В настоящее время существуют два основных подхода к распараллеливанию вычислений. Это параллелизм данных и параллелизм задач. В англоязычной литературе соответствующие термины – data parallel и message passing. В основе обоих подходов лежит распределение вычислительной работы по доступным пользователю процессорам параллельного компьютера. При этом приходится решать разнообразные проблемы. Прежде всего, это достаточно равномерная загрузка процессоров, так как если основная вычислительная работа будет ложиться на один из процессоров, то данный случай можно рассматривать как случай обычных последовательных вычислений и в этом случае никакого выигрыша за счет распараллеливания задачи не будет. Сбалансированная работа процессоров – это первая проблема, которую следует решить при организации параллельных вычислений. Другая и не менее важная проблема – скорость обмена информацией между процессорами. Если вычисления выполняются на высокопроизводительных процессорах, загрузка которых достаточно равномерная, но скорость обмена данными низкая, основная часть времени будет тратиться впустую на ожидание информации, необходимой для дальнейшей работы данного процессора. Рассматриваемые парадигмы программирования различаются методами решения этих двух основных проблем.
1.3.1. Параллелизм данных
Основная идея подхода, основанного на параллелизме данных, заключается в том, что одна операция выполняется сразу над всеми элементами массива данных. Различные фрагменты такого массива обрабатываются на векторном процессоре или на разных процессорах параллельной машины. Распределением данных между процессорами занимается программа. Векторизация или распараллеливание в этом случае чаще всего выполняется уже на этапе компиляции – перевода исходного текста программы в машинные команды. Роль программиста в этом случае обычно сводится к заданию опций векторной или параллельной оптимизации компилятору, директив параллельной компиляции, использованию специализированных языков для параллельных вычислений. Наиболее распространенными языками для параллельных вычислений являются высокопроизводительный ФОРТРАН (High Performance FORTRAN) и параллельные версии языка C (это, например, C*).
Более детальное описание рассматриваемого подхода к распараллеливанию содержит указание на следующие его основные особенности:
обработкой данных управляет одна программа;
пространство имен является глобальным, то есть для программиста существует одна единственная память, а детали структуры данных, доступа к памяти и межпроцессорного обмена данными от него скрыты;
слабая синхронизация вычислений на параллельных процессорах, то есть выполнение команд на разных процессорах происходит, как правило, независимо и только лишь иногда производится согласование выполнения циклов или других программных конструкций – их синхронизация. Каждый процессор выполняет один и тот же фрагмент программы, но нет гарантии, что в заданный момент времени на всех процессорах выполняется одна и та же машинная команда;
параллельные операции над элементами массива выполняются одновременно на всех доступных данной программе процессорах.
Таким образом, что в рамках данного подхода от программиста не требуется больших усилий по векторизации или распараллеливанию вычислений. Даже при программировании сложных вычислительных алгоритмов можно использовать библиотеки подпрограмм, специально разработанных с учетом конкретной архитектуры компьютера и оптимизированных для этой архитектуры.
Подход, основанный на параллелизме данных, базируется на использовании при разработке программ базового набора операций:
операции управления данными;
операции над массивами в целом и их фрагментами;
условные операции;
операции приведения;
операции сдвига;
операции сканирования;
операции, связанные с пересылкой данных.
Далее, для примера, рассмотрены базовые наборы операций.
Управление данными.
В определенных ситуациях возникает необходимость в управлении распределением данных между процессорами. Это может потребоваться, например, для обеспечения равномерной загрузки процессоров. Чем более равномерно загружены работой процессоры, тем более эффективной будет работа компьютера.
Операции над массивами.
Аргументами таких операций являются массивы в целом или их фрагменты (сечения), при этом данная операция применяется одновременно (параллельно) ко всем элементам массива. Примерами операций такого типа являются вычисление поэлементной суммы массивов, умножение элементов массива на скалярный или векторный множитель и т. д. Операции могут быть и более сложными – вычисление функций от массива, например.
Условные операции.
Эти операции могут выполняться лишь над теми элементами массива, которые удовлетворяют какому-то определенному условию. В сеточных методах это может быть четный или нечетный номер строки (столбца) сетки или неравенство нулю элементов матрицы.
Операции приведения.
Операции приведения применяются ко всем элементам массива (или его сечения), а результатом является одно единственное значение, например, сумма элементов массива или максимальное значение его элементов.
Операции сдвига.
Для эффективной реализации некоторых параллельных алгоритмов требуются операции сдвига массивов. Примерами служат алгоритмы обработки изображений, конечно-разностные алгоритмы и некоторые другие.
Операции сканирования.
Операции сканирования еще называются префиксными/суффиксными операциями. Префиксная операция, например, суммирование выполняется следующим образом. Элементы массива суммируются последовательно, а результат очередного суммирования заносится в очередную ячейку нового, результирующего массива, причем номер этой ячейки совпадает с числом просуммированных элементов исходного массива.
Операции пересылки данных.
Это, например, операции пересылки данных между массивами разной формы (то есть имеющими разную размерность и разную протяженность по каждому измерению) и некоторые другие.
При программировании на основе параллелизма данных часто используются специализированные языки – CM FORTRAN, C*, FORTRAN+, MPP FORTRAN, Vienna FORTRAN, а также HIGH PERFORMANCE FORTRAN (HPF). HPF основан на языке программирования ФОРТРАН 90, что связано с наличием в последнем удобных операций над массивами (см., например, М. Меткалф и Дж. Рид Описание языка программирования ФОРТРАН 90, М.: «Мир», 1995).
1.3.2. Параллелизм задач
Стиль программирования, основанный на параллелизме задач подразумевает, что вычислительная задача разбивается на несколько относительно самостоятельных подзадач и каждый процессор загружается своей собственной подзадачей. Компьютер при этом представляет собой MIMD-машину. Аббревиатура MIMD обозначает в известной классификации архитектур ЭВМ компьютер, выполняющий одновременно множество различных операций над множеством, вообще говоря, различных и разнотипных данных. Для каждой подзадачи пишется своя собственная программа на обычном языке программирования, обычно это ФОРТРАН или С. Чем больше подзадач, тем большее число процессоров можно использовать, тем большей эффективности можно добиться. Важно то, что все эти программы должны обмениваться результатами своей работы, практически такой обмен осуществляется вызовом процедур специализированной библиотеки. Программист при этом может контролировать распределение данных между процессорами и подзадачами и обмен данными. Очевидно, что в этом случае требуется определенная работа для того, чтобы обеспечить эффективное совместное выполнение различных программ. По сравнению с подходом, основанным на параллелизме данных, данный подход более трудоемкий, с ним связаны следующие проблемы:
повышенная трудоемкость разработки программы и ее отладки;
на программиста ложится вся ответственность за равномерную загрузку процессоров параллельного компьютера;
программисту приходится минимизировать обмен данными между задачами, так как пересылка данных – наиболее «времяемкий» процесс;
повышенная опасность возникновения тупиковых ситуаций, когда отправленная одной программой посылка с данными не приходит к месту назначения.
Привлекательными особенностями данного подхода являются большая гибкость и большая свобода, предоставляемая программисту в разработке программы, эффективно использующей ресурсы параллельного компьютера и, как следствие, возможность достижения максимального быстродействия. Примерами специализированных библиотек являются библиотеки MPI (Message Passing Interface) и PVM (Parallel Virtual Machines). Эти библиотеки являются свободно распространяемыми и существуют в исходных кодах. Библиотека MPI разработана в Аргоннской Национальной Лаборатории (США), а PVM – разработка Окриджской Национальной Лаборатории, университетов штата Теннеси и Эмори (Атланта).
Наиболее распространенным типом параллелизма задач, реализуемых на вычислительных системах, является параллелизм независимых ветвей. Суть этого типа параллелизма состоит в том, что в алгоритме решения задачи на тех или иных этапах могут быть выделены независимые модули – ветви, которые в ВС могут выполняться одновременно, т. е. параллельно, по независимым программам [1, 2].
Ветвь А программы не зависит от ветви Б, если одновременно выполняются следующие четыре условия:
1) Между А и Б нет функциональных связей, т. е. ни одна из входных переменных для Б не является выходной переменной ветви А либо другой зависящей от А ветви;
2) Между А и Б нет связи по рабочим полям памяти: А и Б не производят записи в одни и те же ячейки памяти;
3) А и Б выполняются по разным программам (или копиям программ);
4) А и Б независимы по управлению, т.е. условия выполнения ветви Б не должны зависеть от признаков, вырабатываемых при реализации А или другой ветви, зависящей от А.
Удобной графической моделью представления параллелизма независимых ветвей является ярусно-параллельная форма (рис. 1.1). Все ветви в ЯПФ разбиваются по N+1 ярусам; в ярус 0 входят ветви, каждая из которых не зависит (в вышеуказанном смысле) ни от одной другой ветви; в 1-й ярус – ветви, зависящие только от ветвей 0-го яруса;... в i-й ярус – ветви, зависящие от ветвей (i–1)-го яруса и, возможно, от ветвей ярусов с номерами, меньшими (i–1); и т.д.
13 EMBED Word.Picture.8 1415
Рис. 1.1. Графическое представление ЯПФ
На рис.1.1 ветви обозначены кружками с соответствующими номерами (вместо номеров могут быть другие идентификаторы), функциональные связи между ветвями показаны отрезками, причем если отрезок не выходит ни из какого кружка, то он соответствует входной переменной программы; если отрезок соединяет два кружка, скажем, от a к b, то этот отрезок соответствует выходной переменной для ветви а и входной – для b; если отрезок не входит ни в какой кружок, то он соответствует выходной переменной программы. Возможные «расщепления» отрезка означают, что одни и те же переменные являются входными для двух или более ветвей.
Каждую ветвь для удобства идентификации можно пронумеровать двойным индексом вида (i, j), где i – номер яруса, j – номер ветви в этом ярусе (см. рис. 1.1).
Важнейшая характеристика ветви (i, j) – это ее «длина» lij, которая в зависимости от ситуации интерпретируется либо как трудоемкость реализации ветви, либо как время реализации на конкретном вычислительном устройстве.
Формирование ЯПФ и оценка lij довольно сложный процесс, зависящий от самой задачи и от квалификации системного программиста. В современных ВС построением ЯПФ занимается специальный блок ОС либо специальная программа-диспетчер. Однако для простых задач ЯПФ можно построить вручную.
Имея ярусно-параллельную форму, легко оценить следующие основные характеристики параллелизма соответствующей задачи:
Ширина В ЯПФ:
13EMBED Equation.31415, (1.1)

где Вi – ширина i-го яруса – количество ветвей в этом ярусе.
Длина L ЯПФ:
13EMBED Equation.31415, (1.2)
где li – длина i-го яруса:
13EMBED Equation.31415. (1.3)
Например, для рис.1.1, легко подсчитать, В = 5, L = 19.
Характеристики (1.1) и (1.2) в значительной степени можно считать атрибутами (неотъемлемыми свойствами) задачи как таковой, вне зависимости от того, на каких ВС она реализуется.
Рассмотрим теперь возможность реализации ЯПФ на некоторой мультипроцессорной ВС. Сделаем следующие допущения:
время lij реализации ветви ij не зависит от того, на каком процессоре ВС она реализуется (т.е. все процессоры функционально идентичны);
число процессоров ВС не ограничено, в том смысле, что система для реализации любого яруса ЯПФ может предоставить столько процессоров, сколько необходимо для полного распараллеливания работ на данном ярусе;
ЯПФ на ВС реализуется синхронно: все ветви очередного яруса начинают выполняться одновременно, после завершения работ самой длинной ветви предыдущего яруса;
в любой момент времени любой из процессоров может выполнять только одну из операций, принадлежащую совокупному набору операций данного процессора;
в каждой операции, выполняемой на любом процессоре, может присутствовать не более двух операндов.
Тогда характеристики В и L приобретают следующий смысл: В – минимальное число процессоров для полного распараллеливания, а L – минимальное время решения задачи на ВС при синхронной реализации ЯПФ:
13 EMBED Equation.3 1415 (1.4)
С другой стороны, при числе n процессоров ВС, равном 1 (однопроцессорная ВС), время решения задачи, очевидно, равно максимальному:
13 EMBED Equation.3 1415. (1.5)
Таким образом, время L(n) решения задачи на n-процессорной ВС, n
· B, лежит в пределах
13 EMBED Equation.3 1415. (1.6)
Одной из основных проблем мультипроцессорных ВС является проблема выбора архитектуры ВС и организации вычислительного процесса, таким образом, чтобы обеспечить L(n), возможно более близкое к Lmin при данном n. Об этом речь пойдет в последующих работах. А пока рассмотрим еще две полезные характеристики эффективности вычислений.
Коэффициент К ускорения вычислений:
13 EMBED Equation.3 1415. (1.7)
Коэффициент ускорения, очевидно, показывает, во сколько раз быстрее решается задача на n-процессорной системе по сравнению с однопроцессорной ВС, и, таким образом, он характеризует степень повышения производительности при использовании многопроцессорных ВС.
О том, насколько эффективно используется при этом оборудование, позволяет судить коэффициент загрузки, или просто загрузка:
13 EMBED Equation.3 1415, n
· B (1.8)
который показывает долю процессорного времени Lmax, использованного на решение задачи, по отношению к общему времени nL(n), потраченному на задачу. Из (1.8) и (1.7) следует, что
13 EMBED Equation.3 1415, n
· B. (1.9)
1.3.3. Синхронные вычисления
Все микрокомпьютеры со времен их создания состояли из процессора, памяти и периферийных устройств. Причем активной частью компьютера является именно процессор, а память и периферийные устройства только подчиняются его командам. Программы и данные хранятся в памяти. Периферийные устройства позволяют процессору общаться с внешним миром – здесь имеются в виду пользователи, другие компьютеры, жесткие диски и дополнительные устройства. Причем за один такт машинного времени процессор может обратиться только к одной ячейке памяти или к одному внешнему устройству. Процесс вычислений с помощью процессора организован в соответствии с изложенной ниже схемой.
Процессор выставляет на шину адресов адрес необходимой ему ячейки памяти или порта внешнего устройства.
Внешнее устройство или память должны выставить на шине данных свою информацию, которую запросил процессор.
Процессор, считав информацию с шины данных, обрабатывает ее, записывая в память или во внешнее устройство. При этом опять выставляются соответствующие сигналы и происходит синхронизация процессора с другими элементами компьютера.
Выполнение одной команды в процессоре или обмен информацией между процессором и другими микросхемами должны закончиться за один системный такт, до следующего импульса тактового генератора. Таким образом, вся плата или ее отдельная часть, особо приближенная к процессору, синхронно и одновременно переходит из одного стабильного состояния в другое. Так протекает работа компьютера. Поскольку вычисления в нем синхронизируются сигналами тактовой частоты, такие вычисления называются синхронными.
Основной недостаток синхронных вычислений заключается в том, что очень многие активные элементы должны работать совместно, повинуясь сигналам тактового генератора. С увеличением частоты тактового генератора становится труднее согласовывать работу процессора и его окружения. Поэтому современные процессоры выпускают на одной микросхеме или в форме специальных процессорных плат. Однако даже основная память работает на более низкой частоте. Для этого приходится использовать сложные системы предсказания переходов, кэширования информации и изобретать другие технические ухищрения.
При такой организации вычислений просто необходимо интегрировать в процессор все необходимые функции, что еще более усложняет разработку следующих поколений микросхем. Однако, синхронизация процессора просто необходима из-за адресной организации памяти, при которой для извлечения каждого конкретного байта из памяти необходимо указать его адрес.
По своей конструкции вычислительные системы, реализующие методы синхронных вычислений, состоят из набора аппаратных компонент, синхронизированных генератором тактовых импульсов. В каждый момент срабатывания генератора тактовых импульсов выполняется небольшой набор операций, выполнение которых возможно одновременно на используемой аппаратуре и неконфликтно между собой. Однако в данном случае некоторые логические схемы могут простаивать или использоваться в режиме не полноценной загрузки. Для ускорения процесса вычислений существует метод асинхронных вычислений, при котором в любой момент времени может быть задействовано любой функциональной устройство, свободное в момент обращения к нему.
1.3.4. Асинхронные вычисления
В настоящее время существует большое число задач, решение которых основано на применении концепции распределенных вычислений. Это научные задачи связанны с предоставлением информационных услуг (например, осуществления электронных платежей), задачи контроля и управления объектами. Последние два вида задач для своего решения, как правило, требуют режима реального времени.
Асинхронное управление широко используется в параллельном программировании. На его основе разработаны различные модели вычислений и языки программирования. Одной из основополагающих работ является книга Хоара [8], в которой описаны базовые методы асинхронного взаимодействия и подведен соответствующий теоретический фундамент. Теоретические аспекты асинхронного автоматного программирования представлены в работе [2].
Различают несколько подклассов асинхронных вычислительных моделей, среди них асинхронные вычислительные сети [4] и асинхронные вычислительные конвейеры [5].
Для асинхронных вычислительных сетей характерно наличие конечных, завершающих состояний – совокупности соответствующих состояний ее компонентов. Для сетей, ориентированных на однократное получение результата, достижение завершающего состояния является целью их функционирования. Для конвейеров, наоборот, целью являются непрерывные параллельные вычисления, связанные с получением и выдачей данных. Можно сказать, что первый случай применим для спецификации расчетных научных задач, второй – для спецификации интерактивных информационных систем, систем управления технологическими процессами и т. д.
Базовая модель асинхронных вычислений предусматривает наличие четырех типов объектов: компонента, буфера, источника и приемника данных. Связи между объектами – «точка-точка», направленные. Компонент является активным объектом, то есть имеет собственную логику работы и может инициировать обращение к другим объектам. Объекты остальных типов пассивны.
Асинхронная вычислительная машина – это ЭВМ, в которой начало выполнения каждой операции определяется сигналом окончания предыдущей операции. Асинхронные вычислительные машины обладают переменным рабочим тактом, величина которого зависит от длительности операции. Асинхронный принцип обеспечивает машине сравнительно большую скорость вычислений и позволяет достаточно просто согласовать работу устройств с различным быстродействием. Кроме того, он создаёт некоторый самоконтроль машины, поскольку в случае невыполнения какой-либо операции или неполучения сигнала о её окончании машина останавливается. Асинхронные вычислительные машины могут быть частично асинхронными – асинхронный принцип применяется лишь для выполнения тех операций, продолжительность которых существенно больше времени обращения к оперативному запоминающему устройству (например, умножение, деление, ввод информации и т. д.), а остальные операции имеют постоянный такт работы.
Асинхронные вычисления имеют свои плюсы и минусы. Их основное достоинство – модульность полученной вычислительной системы, что позволяет точнее согласовать возможности аппаратного и программного обеспечения. Кроме того, изначальная ориентация на многопотоковые вычисления позволяет достигнуть недоступной для синхронных вычислений производительности.
В случае синхронных вычислений неиспользуемый компьютер все же выполняет какие-то минимальные действия. При асинхронных вычислениях в момент отсутствия обрабатываемых пакетов никаких процессов внутри вычислительной системы не происходит. Таким образом, если спроектировать каждый отдельный блок в асинхронном компьютере так, чтобы он выключался при отсутствии предназначенных для него пакетов и включался при получении первого пакета, то можно снизить потребление электроэнергии в неиспользуемом компьютере.
Реализация асинхронных вычислений значительно проще, так как отсутствует необходимость синхронизации всех частей вычислительной системы. Достаточно синхронизировать только канал связи между устройством и ближайшим коммутатором. Таким образом, реализовать асинхронные вычислительные устройства достаточно просто. Для этого необходимо разработать спецификацию команд всех основных блоков и соответствующую систему составления модульных процессоров, а также аппаратно реализовать все решения.
1.3.5. Исследование ВС на основе диаграмм Ганта
Повышение эффективности использования параллельных вычислительных систем – одна из основных задач в области современных информационных технологий. Решение данной проблемы зависит, с одной стороны, от характеристик параллельного алгоритма, а с другой – от его отображения на конкретную параллельную ВС. Только оптимальное согласование структур алгоритмов с особенностями параллельных архитектур позволяет достичь максимальной производительности.
Модели параллельных программ и операционные характеристики процессов их выполнения служат основой для планирования параллельных вычислительных процессов. Расписания параллельных вычислительных определяют порядок выполнения программы на ВС, включая распределение частей программы между процессорами. Распределение работ по процессорам, их упорядочивание и затрачиваемые при этом времена работы процессоров представляются с помощью специальных моделей – диаграмм Ганта [8].
Диаграмма Ганта – форма графической организации процессов; горизонтальная линейная диаграмма, на которой задачи проекта представляются протяженными во времени отрезками, характеризующимися датами начала и окончания, задержками и возможно другими временными параметрами. Задачи, составляющие план, размещаются по вертикали. Начало, конец и длина отрезка на шкале времени соответствуют началу, концу и длительности задачи.
Использование данных моделей связано с определёнными трудностями, заключающимися в определённой сложности распределения частей алгоритма между процессорами, то есть отсутствии связующего звена между алгоритмом и его расписанием.
Таким образом, разработка методов и средств, решающих проблему формального перехода от схем программ к их расписаниям является актуальной задачей, так как позволит добиться значительного успеха в автоматизации процесса распараллеливания программ.
В данной лабораторной работе предполагается построение по заданному математическому выражению, используемому в лабораторной работе №1, диаграмм Ганта асинхронного и синхронного режимов вычислений. Кроме этого требуется уменьшить количество процессорных элементов на единицу и выполнить построения диаграмм Ганта для новой многопроцессорной системы.
1.3.6. Конвейерная обработка
В простом последовательном процессоре для выполнения одной операции сложения функциональное устройство блокируется на время всего цикла выполнения операции. Поэтому в последовательном устройстве в каждый момент времени выполняется только одна арифметическая операция. Если предположить, что операция сложения чисел с плавающей запятой выполняется за 5 машинных тактов, то в течение пяти тактов, которые требуются на выполнение операции сложения, никакой другой работы выполнено не будет. Однако можно изменить логику выполнения данной операции. Сложение каждой пары чисел выполняется в виде последовательности микроопераций, таких как сравнение порядков, выравнивание порядков, сложение мантисс, нормализация и т. п. В процессе обработки каждой пары входных данных микрооперации задействуются только один раз и всегда в одном и том же порядке: одна за другой. Это, в частности, означает, что если первая микрооперация выполнила свою работу и передала результаты второй, то для обработки текущей пары она больше не понадобится, и значит, она вполне может начинать обработку следующей ждущей на входе устройства пары аргументов.
Исходя их этих рассуждений, с учетом предположения, что каждая микрооперация выполняется за один машинный такт, можно сконструировать устройство следующим образом. Каждая микрооперация выделяется в отдельную часть устройства, в совокупности которые расположены в порядке выполнения. В первый момент времени входные данные поступают для обработки первой частью процессора, которая реализует первую микрооперацию. После выполнения первой микрооперации первая часть передает результаты своей работы второй части, а сама берет новую пару. Когда входные аргументы пройдут через все этапы обработки, на выходе устройства появится результат выполнения операции.
Такой способ организации вычислений носит название конвейерной обработки. Каждая часть устройства называется ступенью конвейера, а общее число ступеней – длиной конвейера. Предположим, что для выполнения операции сложения вещественных чисел спроектировано конвейерное устройство, состоящее из пяти ступеней, срабатывающих за один такт каждая. Время выполнения одной операции конвейерным устройством равно сумме времен срабатывания всех ступеней конвейера. Это значит, что одна операция сложения двух чисел выполнится за пять тактов, т. е. за такое же временя, которое потребуется для выполнения данной операции последовательном устройстве.
Теперь рассмотрим процесс сложения двух массивов из 500 чисел каждый. На рис. 1.2 показан пример реализации пятиступенчатого арифметического конвейера.
13 EMBED Word.Picture.8 1415
Рис. 1.2. Суммирование векторов из 50 чисел с помощью конвейерного устройства
Каждая из пяти ступеней конвейера срабатывает за один такт Так же как и в последовательном устройстве, через пять тактов будет получен результат сложения первой пары чисел. Однако одновременно с первой парой прошли частичную обработку и другие элементы. Каждый последующий такт на выходе конвейерного устройства будет появляться сумма очередных элементов. На выполнение всей операции сложения 500 чисел потребуется 104 такта, вместо 500 тактов при использовании последовательного устройства, что дает выигрыш во времени почти в пять раз. Приблизительно так же конвейерное устройство будет вести себя в общем случае. Если конвейерное устройство содержит L ступеней, а каждая ступень срабатывает за одну единицу времени, то время обработки n независимых операций этим устройством составит L+n–1 единиц. Если это же устройство использовать в монопольном режиме (как последовательное), то время обработки будет равно L*n. В результате для больших значений n можно получить ускорение почти в L раз за счет использования конвейерной обработки данных.
1.3.7. Оценка эффективности конвейера процессоров
Конвейерные вычислительные системы, в частности, реализуют принцип обработки МКОД (множественный поток команд – одиночный поток данных), и по этой причине их часто отождествляют только с ВС этого класса, хотя понятие конвейерной обработки шире понятия МКОД.
Конвейерная обработка может быть реализована как на уровне процессоров, так и на уровне функциональных элементов, входящих в состав арифметико-логического устройства процессора. Далее рассмотрена реализация конвейерной системы на уровне конвейеризации с помощью процессорных элементов.
Общий принцип конвейерной обработки данных показан на следующем примере. Пусть требуется вычислить функцию F(x) для последовательности х1, х2, ... данных по алгоритму
F(x) = f3(f2(f1(x))), (1.10)
где f1, f2 и f3 – заданные функции, причем известно, что на операцию fi ВС тратит время (i, i = 1, 2, 3. Здесь как аргумент х, так и функции fi и F могут быть как скалярными, так и векторными.
При реализации последовательного алгоритма (1.10) результат F(x) появится на выходе ВС спустя время
13 EMBED Equation.3 1415. (1.11)
Теперь допустим, что имеются три процессора, и процессор i специализируется на выполнении операции fi. Свяжем процессоры в конвейер по схеме рис. 1.3 и определим такт конвейера, (к, как
(к = max {(i}. (1.12)
13 EMBED Word.Picture.8 1415
В каждом такте будем подавать на вход конвейера, т. е. на вход процессора 1, очередной набор данных, т.е. в первом такте – х1, во втором – х2, и т. д. В результате можно получить схему, или диаграмму вычислений, показанную на рис. 1.4.
13 EMBED Word.Picture.8 1415
Из схемы видно, что первый результат, F(x1), появится на выходе конвейера спустя 3 такта, т.е. через время 3(к (иногда его называют временем разгона), но зато каждый следующий, т.е. F(x2), F(x3) и т. д. – в каждом следующем такте, т.е. через время (к. При достаточно длинной последовательности х1, х2, ... можно пренебречь временем разгона, и тогда эффективность конвейера, оцениваемая коэффициентом ускорения К, составит величину
13 EMBED Equation.3 1415. (1.13)
Эти рассуждения, а, следовательно, и формулы (1.10)–(1.13), можно обобщить на случай произвольного числа (n) процессоров в конвейере. В этом случае, подставляя в (1.13) значения (п и (к из (1.11) и (1.12), можно получить такую оценку
13 EMBED Equation.3 1415,
т. е.
К
· n, (1.14)
и загрузка конвейера –
( = K/n
· 1 . (1.15)
Предельное значение Кmax=n достигается при одинаковой длительности (i обработки данных во всех процессорах конвейера и при «сплошной» загрузке всех процессоров во всех тактах работы, т. е. когда коэффициент загрузки ( равен 1.
В реальных конвейерных ВС эти значения не достигаются вследствие приостановок конвейера из-за команд условного и безусловного переходов и тому подобных причин. Реальное ускорение можно оценить по формуле [10]:
13EMBED Equation.31415, (1.16)
где pi – вероятность приостановки конвейера на i тактов. Загрузка (, определяемая как ( = К/n, при этом равна
13EMBED Equation.31415 (1.17)
Все расчеты требуется произвести, с учетом того, что каждый процессор является конвейерным и состоит в свою очередь их нескольких ступеней (функциональных устройств), где их число определяется количеством тактов требуемых для выполнения функции из набора функций {fi}. Каждая функция из набора {fi} определяется комбинаций стандартных операций из заданного набора {j}, расположенных на соответствующем ярусе ЯПФ. При этом число ступеней в процессорном конвейере не может превышать максимального числа тактов, требуемых на выполнение любой операции из множества {j} заданных (стандартных).
1.4. Пример расчета
Рассмотрим процесс построения ЯПФ и оценки характеристик параллелизма на примере вычисления арифметического выражения:
13 EMBED Equation.3 1415. (1.18)
Пусть известно, что процессор ВС тратит на выполнение операций умножения, деления и сложения времена ty, td и tc, связанные соотношениями
ty = (tc,
td = (tc.
Без ограничения общности можно принять tc = 1; тогда ty = ( и td = (. Известно также, что ( > ( > 1.
Используя эти данные, а также определение независимости ветвей, можно построить ЯПФ выражения (1.18). Она имеет вид, представленный на рис. 1.5.
13 EMBED Word.Picture.8 1415
Рис. 1.5. ЯПФ для выражения (1.18)
Непосредственно из этого рисунка получим, используя соотношения (1.1) – (1.4):
B = max {B0, B1, B2, B3} = max {3, 2, 1, 1} = 3,
l0 = max {(, 1, (} = ( ,
l1 = max {1, (} = ( ,
l2 = 1,
l3 = 1,
Следовательно,
L = l0 + l1 + l2 + l3 = ( + ( + 2.
Далее, по формуле (1.5) имеем:
Lmax = 2( + ( + 4 .
Если число n процессоров ВС не менее 3, то при этом, согласно (1.4), достигается минимально возможное время решения задачи
Lmin = L = ( + ( + 2 ,
и коэффициент ускорения вычислений, в соответствии с (1.7), равен
13 EMBED Equation.3 1415,
в числах
13 EMBED Equation.3 1415.
Коэффициент загрузки (1.9), при n = 3:
13EMBED Equation.31415,
в числах
13EMBED Equation.31415.
Результатом вычислений являются результирующие значения коэффициента ускорения и загрузки, при ( = 2 и ( = 3
K = 1,571,
( = 0,523.
При загрузке системы более чем на 50% и коэффициенте ускорения более 50% можно считать систему экономически обоснованной. В противном случае в выводах нужно привести рекомендации для достижения данных показателей.
Далее рассмотрен процесс преобразования ЯПФ и оценки эффективности ВС на примере реализации арифметического выражения (1.18) (при выполнении требуется выбрать выражение в соответствии с вариантом задания). ЯПФ этого выражения воспроизведена на рис. 1.5, где ( = 2 и ( = 3.
Если имеется 3-процессорная параллельная ВС, то эта форма без всяких преобразований может быть реализована так, как показано на рис. 1.6, где по-прежнему принято tс=1, ty=2 и tд=3.
13 EMBED Word.Picture.8 1415
Рисунок подобного рода обычно называют диаграммой Ганта. Рис. 1.6,а соответствует синхронной реализации ЯПФ. Из этого рисунка непосредственно видно, что L=7, Lmax=11, так что коэффициент ускорения К=11/7
·1,56, а коэффициент загрузки (=К/3
·0,52 (можно заметить, что диаграмма рис.1.6,а позволяет вычислить (, используя само понятие загрузки как отношения суммарного полезного времени процессоров Lmax =11 к общему истраченному времени, B
·L=3
·7=21).
Эффективность ВС можно повысить, если снять ограничение синхронности, а именно: разрешить процессору, освободившемуся на каком-либо ярусе, начать реализацию ветви следующего яруса немедленно, не дожидаясь освобождения остальных процессоров. Диаграмма Ганта реализации асинхронного режима для ЯПФ, представленной на рис. 1.5, представлена на рис. 1.6,б.
Из этого рисунка непосредственно видно, что L=6 Lmax=11, так что коэффициент ускорения К=11/6
·1,83, а коэффициент загрузки (=К/3
·0,61. Эффективность системы при использовании асинхронного режима функционирования ВС повышается.
Иногда диаграммы Ганта для синхронного и асинхронного режимов могут совпадать (при выполнении задания требуется рассмотреть асинхронный режим и в случае совпадения с результатами синхронного режима отметить данный факт в выводах к работе).
Для большей эффективности ВС часто используют метод уменьшения количества процессорных элементов. Далее рассмотрен случай 2-процессорной ВС. На первый взгляд кажется, что задача параллельно реализована не может быть, поскольку ярус 0 требует наличия 3-х процессоров. Однако, как легко увидеть, преобразованная форма, изображенная на рис. 1.7, эквивалентна ЯПФ рис. 1.5 в смысле задачи (1.18).
13 EMBED Word.Picture.8 1415
В то же время для реализации преобразованной ЯПФ достаточно 2-х процессоров. Процесс реализации показан на рис. 1.7. Из диаграммы Ганта, представленной на рис. 1.8, следует, что при синхронной реализации ЯПФ длительность решения задачи равна 8, коэффициент ускорения К=11/8=1,38, а загрузка (=11/(2
·8)=0,69.
13 EMBED Word.Picture.8 1415
При асинхронной реализации ЯПФ (рис. 1.7) можно получить результаты, представленные далее.
Соответствующая диаграмма показана на рис. 1.9, откуда следует К=11/7 =1,56, а (=11/(2*7) = 0,79. Т. е. в данном случае достигнуто такое же ускорение, как и в 3-процессорной системе, с одновременным увеличением загрузки ВС.
13 EMBED Word.Picture.8 1415
Однако описанные выше расчеты могут быть использованы лишь в грубых моделях вычислительных процессов, не учитывающих затраты процессорного времени на подготовку полезного процесса и на различные задержки, связанные с пересылкой файлов, команд и данных в оперативную память. Тем не менее, там, где эти затраты малы по сравнению с длиной ветвей ЯПФ, асинхронный процесс оказывается более эффективным.
В выводах к работе всегда нужно комментировать полученный результат на основе анализ коэффициентов ускорения и загрузки ВС.
Для реализации конвейерной системы требуется использовать заданное выражение, в данном случае (1.18) и выбрать систему B–1, в данном случае показанную на рис. 1.7.
Эффективность конвейерной ВC можно оценить полагая, как и прежде, что длительности операций сложения, умножения и деления равны соответственно 1, 2 и 3. ЯПФ, с указанием длительности тактов, представлена на рис. 1.10.
13 EMBED Word.Picture.8 1415
Рис. 1.10. ЯПФ (B–1) математического выражения (1.18)
Для этой формы, в обозначениях типа (1.10), можно записать: для вектора х исходных данных –
x = (a, b, c, d, e, f, g, h);
для вектор-функции, реализующей ярус 0,
f1(x) = (bc, a, e+f, d, g, h),
или, используя обозначения ЯПФ: 01 = bc, 02 = e+f ,
f1(x) = (01, a, 02, d, g, h);
причем, как легко видеть из этой же ЯПФ, (1=2. Для определения ( можно воспользоваться схемой, представленной на рис. 1.3. Для определения ( всегда считается, что процессор начинает выполнение операции с максимальной продолжительностью. В данном случае сначала на вход конвейера поступит операция умножения, а затем операция сложения, как это показано на рис. 1.11.
13 EMBED Word.Picture.8 1415
Рис. 1.11. Этапы выполнения ярусных операций
Далее, ярус 1 ЯПФ реализуется вектор-функцией
f2(f1) = (11, 12, g, h),
и длительность операции f2 равна (2 = 3.
13 EMBED Word.Picture.8 1415
Ярус 2 реализуется вектор-функцией
f3(f2) = (21, 22)
с длительностью (3 = 2,
13 EMBED Word.Picture.8 1415
и, наконец, ярус 3 реализуется скалярной функцией

f4(f3) =(31) = F(x)
с длительностью (4 = 1.
Таким образом, время (п последовательной реализации ярусов ЯПФ, в соответствии с (1.11), равно
13EMBED Equation.31415
Для построения конвейера, прежде всего, требуется определить такт, 13 EMBED Equation.3 1415, конвейера:
13EMBED Equation.31415.
Следует отметить, что, поскольку операция считается элементарной (т. е. неделимой), то уменьшить величину 13 EMBED Equation.3 1415 невозможно. Следовательно, коэффициент ускорения конвейера в данном случае, согласно (4.4), не может превышать величины
К = 8/3 = 2,67 . (1.19)
Далее можно определить структуру конвейера. Самое простое решение состоит в назначении для каждого яруса ЯПФ специализированного процессора. Тогда конвейер будет содержать n = 4 процессора, и загрузка ВС составит величину
13 EMBED Equation.3 1415 = 2,67/4 =0,67. (1.20)
Однако при этом, как показывают соотношения (1.14) и (1.15), значения К и ( оказываются далекими от предельных (4 и 1 соответственно).
Характеристики конвейера можно улучшить, если для операций ярусов 3 и 4 ЯПФ назначить один процессор (см. рис. 1.10). Тогда, как нетрудно видеть, Пр3 исполнит все эти операции за время (3 = 3, т. е. в пределах такта конвейера, и в то же время загрузка конвейера возрастет до величины
( = 13 EMBED Equation.3 1415 = 0,887,
при том же самом коэффициенте ускорения (1.19).
Итак, решение задачи состоит в следующем. Предлагается 3-процессорная конвейерная ВС; структура конвейера показана на рис. 1.12.
13 EMBED Word.Picture.8 1415
Рис. 1.12. Структура конвейерного устройства
Процессоры Пр1, Пр2 и Пр3 реализуют соответственно вектор-функции
f1(x) = (01, a, 02, d, g, h),
f2(f1) = (11, 12, g, h),
f3(f2) = (21, 22, 31), с выходом 31 = F(x).
Длительность такта конвейера равна 3, коэффициент ускорения по отношению к последовательной реализации ЯПФ равен 2,67, загрузка конвейера – 0,867.
В заключении следует отметить, что если речь идет об абсолютном коэффициенте ускорения, т. е. об отношении времени реализации (арифметического выражения, например) на ВС класса SISD (один поток команд при одном потоке данных) к времени на рассматриваемой конвейерной ВС, то этот абсолютный коэффициент в данном случае равен 11/8 = 1,375.
1.5. Варианты заданий
В качестве входных данных выбираются параметры ( и (, а также арифметическое выражение. Последние две цифры в номере зачетной книжки (KK) определяют номер варианта. Если полученное значение KK больше 30, то номер варианта определяется из соотношения KK-30.

Вариант

·
(
Арифметическое выражение

01
2
4
abc + de/f + g (h + k) + m

02
2
3
ab + cd + e/(f + g) + (h + k)/m

03
3
5
(a + b + c)/d + ef/g + hkm

04
2
4
a + b + cd + e/f + gh + k/m

05
2
3
(ab + c) (de + f) + (g + h)/(k + m)

06
3
5
(ab + cd + e/f + gh)/k + m

07
2
3
(abcde + f)/(gh +k/m)

08
2
4
a/b + c/d + ef/(g + h) + k/m

09
3
5
(a + b)/(c + d) + efg + h/(k + m)

10
3
5
(ab + cde)/(fg + h/k) + m

11
2
5
(a + b + c)/(d + e + f) (g + hk/m)

12
2
3
(a + bc)/(d + ef) + g/(h + km)

13
2
4
(a/b + cd + e/f) (gh + k/m)

14
2
3
(a + b + c + d/e + fg)/(h + km)

15
3
5
a/b + c/d + e/f + ghk + m

16
2
4
a/(b + c + d + ef + gh) + k/m

17
2
3
(a + bc)/(d + ef) + g/(h + k + m)

18
3
5
ab + cd + ef + g/h + k/m

19
2
3
(a + b)/(c + d) + (e + f)/(h + k) + m

20
2
4
(a + b)(c + d)(e + f)(h + k)/m

21
3
5
(ab + cd)/(ef + hk)/m

22
2
5
(a + b + c)(d + e/f)(hk + g) m

23
2
3
a/b/c/d + (e + f + g + h)k + m

24
2
4
(a + b)/c + (d + e)/f + (g + h)k/m

25
2
5
(a + bc)(d + ef)/(g + hk) + m

26
3
4
(abcd + efgh)/(k/m)

27
3
5
(a/b + c/d + e/f + g/h)(k + m)

28
2
5
abcd/e + (f + g + h)k + m

29
2
3
(a + b)/(cd) + e/f + g/h + k/m

30
2
4
(ab + cd)/(e + f + g/h)/k + m

1.6. Содержание отчета
Постановка задачи, ЯПФ арифметического выражения (в каждой арифметической операции любого из выражений может участвовать не более двух операндов), результаты расчетов, выводы о эффективности использования полученного числа процессоров, диаграммы Ганта и ЯПФ для синхронных и асинхронных реализаций с (В)- и (В–1)-процессорными ВС, результаты расчетов коэффициентов ускорения для каждой реализации, сравнительные результаты расчетов для (B)- и (B–1)-процессорных систем.
Для конвейерной ВС привести описание решения поставленных задач, результаты, включая ЯПФ математического выражения (ЯПФ может быть изменена), длительности выполнения ярусов, систему полученных вектор-функций, структуру конвейера, расчеты, для определения коэффициента укореняя. Следует оценить возможность уменьшения количества процессоров и если это возможно, то привести новую структуру конвейера с указанием изменившихся функциональных выражений.
В выводах требуется оценить другие возможные варианты решения задачи построения ЯПФ по математическому выражению, если такие существуют. Если решения данной задачи не соответствующие найденному решению отсутствуют, то это требуется отметить в выводах и обосновать. Также требуется сравнить результаты расчетов для (B)- и (B–1)-процессорных систем, оценить абсолютный коэффициент ускорения конвейерной системы и сравнить его с коэффициентом ускорения для параллельной реализации.
1.7. Требования к оформлению
При выполнении лабораторных работ рекомендуется выполнять расчеты в черновике. Отчет по лабораторным работам оформляется индивидуально каждым студентом и выполняется на двойных тетрадных листах. Лицевая сторона отчета оформляется в соответствии с правилами оформления отчетов в Томском политехническом университете. Принимаются отчеты написанные только собственноручно. Отчеты, распечатанные с помощью офисных средств, не рассматриваются!
1.8. Контрольные вопросы (некоторые контрольные вопросы требуют изучения дополнительного материала)
Назовите основные методы распараллеливания вычислений.
Какие проблемы требуется решить для обеспечения распределения вычислительной работы по доступным процессорам параллельного компьютера.
Что такое параллелизм данных?
Основные особенности параллелизма данных.
Перечислить операции, используемые при разработке программ на основе концепции параллелизма данных.
Что такое параллелизм задач?
Основные трудности реализации параллелизма задач.
Что такое ярусно-параллельная форма. Привести пример.
Дать определение длины ветви ярусно-параллельной формы.
Объяснить понятие ширины ярусно-параллельной формы.
Объяснить расчет коэффициента ускорения вычислительной системы на основе ярусно-параллельной формы.
Организация процесса вычислений с помощью процессора.
Какие вычисления называются синхронными.
Основной недостаток синхронных вычислений.
Отличие методов синхронных и асинхронных вычислений.
Какие типы объектов предусматривает модель асинхронных вычислений.
Какая вычислительная машина называется асинхронной.
Достоинства асинхронных вычислений.
Что такое диаграмма Ганта.
Связь диаграммы Ганта и ЯПФ.
Закон Мура. Производительность компьютеров.
Основные способы повышения производительности компьютеров.
Принцип конвейерной обработки.
Коэффициент ускорения конвейерной системы.
Эффективность конвейера процессоров.
Расчет реального ускорения конвейерной системы.
Задание № 2
Расчет быстродействия процессора и параметров типового задания вычислительной системы
2.1. Цель работы
Приобретение навыков расчета основных параметров типового задания из потока, подлежащего обработке на однопроцессорной вычислительной системе, и определения необходимого быстродействия процессора при заданном времени реакции системы. Овладение навыками расчета вычислительной системы минимальной конфигурации, обрабатывающей поток заданий в оперативном режиме. Освоение методики расчета основных характеристик вычислительной системы оперативной обработки (СОО) на основе её модели как экспоненциальной стохастической сети массового обслуживания и исследование этих характеристик как функций различных параметров СОО.
2.2. Порядок выполнения работы
2.2.1. Изучить раздел 2.3 настоящих указаний и рекомендованную литературу [1,5,6].
2.2.2. По заданному варианту вычислить параметры типового задания ВС в соответствии с выражениями (2.1) – (2.6). Определить нижнюю оценку быстродействия Vпр процессора ВС (2.12), а также минимально необходимое быстродействие процессора при различных временах пребывания заданий в системе (2.13). Построить график Vпр((*), оценить полученные результаты. На основе полученных данных определить состав и структуру вычислительной системы минимальной конфигурации и построить соответствующую стохастическую сетевую модель системы. Используя модель СОО как открытую стохастическую сеть массового обслуживания, рассчитать узловые и сетевые характеристики СОО минимальной конфигурации, спроектированной в предыдущей лабораторной работе. Провести анализ результатов расчета и сделать выводы.
2.2.3. Оформить отчет по работе (см. раздел 2.5).
2.3. Теоретические положения
Обычно вычислительная система, подлежащая проектированию, предназначена для решения некоторого потока заданий, параметры которых более или менее известны. В данной работе значения параметров заданий считаются известными и выбираются из соответствующих таблиц в соответствии с заданным вариантом.
По определению, типовым заданием потока называется задание, параметры которого усреднены по множеству значений параметров всех заданий потока. В работе требуется определить быстродействие процессора ВС как количество процессорных операций, выполняемых им в единицу времени.
Оценка быстродействия процессора является, безусловно, необходимой при выборе того или иного класса ВС, способной справиться с комплексом заданий.
2.3.1. Методика расчета параметров типового задания и необходимого быстродействия процессора ВС
При оперативной обработке информации ставится цель уменьшить среднее время решения задачи. Если поступившая заявка на выполнение работы немедленно принимается к исполнению, то вычислительная система функционирует в режиме оперативной обработки. Такие вычислительные системы получили специальное название – системы оперативной обработки (СОО). Процесс решения задачи Zi представляется произвольной последовательностью этапов счета (обработки в процессоре) и обращения к файлам F1,, FN (обмена информацией между внешней и оперативной памятью системы).
Предполагается, что исследуемая СОО предназначена для решения заданного набора задач {Zi} (i=1,2,.., M), где М – число задач, возлагаемых на систему с целью реализации определенных функций. Каждая задача Zi характеризуется интенсивностью потока запросов на ее решение, трудоемкостью (i процессорных операций, трудоемкостью операций обмена с внешней памятью, которая задается средним числом обращений Nij к файлу Fj в процессе решения задачи Zi.
Множество файлов {Fj} (j=1,2,.., N), где N – число файлов, используемых в процессе решения множества задач {Zi} размещается во внешней памяти системы, состоящей из накопителей двух типов НМД (накопители на магнитных дисках) и НМЛ (накопители на магнитной ленте). Обмен информацией между оперативной и внешней памятью системы производится на уровне записей, представляющих структурно неделимую единицу информации при обмене. Файл Fj (j=1,2,..,N) характеризуется длиной файла Gj, средней длиной записи gj.
Накопители, используемые в составе внешней памяти СОО, характеризуются такими техническими параметрами как среднее время доступа к данным, размещаемым в НМД – UД и в НМЛ – UЛ, скорость передачи данных при обмене через канал передачи данных – VД и VЛ для НМД и НМЛ соответственно, емкость накопителя – GД и GЛ.
Исследования проводятся на сетевых моделях СОО с однородным потоком заявок. Этап обращения к файлам рассматривается как последовательность двух фаз: подготовительной и передачи информации.
В модели отображаются только те устройства СОО, которые оказывают наиболее существенное влияние на процесс решения задач пользователей в смысле задержки получения ответа во времени. Каждое из устройств участвует в реализации определенного этапа в процессе решения задачи.
Любое устройство СОО представляется в модели одноканальной системы массового обслуживания (СМО). Дисциплина обслуживания заявок в любой СМО предполагается простейшей бесприоритетной очередью FIFO (обслуживание в порядке поступления). Одноканальная СМО характеризуется интенсивностью (i входящего потока и средним временем U – обслуживания заявок.
2.3.2. Определение параметров типового задания
Вычислительный процесс, развивающийся в ВС, графически может быть представлен простой моделью, показанной на рис. 2.1.
13 EMBED Word.Picture.8 1415
Выполнение каждого задания начинается с запроса пользователя ВС на решение соответствующей задачи Zi (i=1,...,M) и кончается выдачей ответа пользователю в виде результатов решения. В процессе выполнения задания оно проходит этапы счета (обработка в процессоре с обращениями к оперативной памяти), чередующиеся с этапами обращения к файлам F1,...,FN, расположенным во внешней памяти ВС.
Варианты перечисленных данных для расчетов по лабораторной работе приведены в табл. 2.1 и 2.2.
Для построения сетевой модели системы оперативной обработки требуется выполнить усреднение параметров задач из множества задач {Zi}, возлагаемых на систему, с целью приведения неоднородного потока заявок к однородному. Параметры, получаемые в результате усреднения, описывают, так называемую, среднюю задачу. Приведение неоднородного потока заявок к однородному должно проводиться таким образом, чтобы однородный поток запросов на решение средней задачи создавал в среднем такую же нагрузку на систему, как неоднородный поток запросов на решение множества задач {Zi}. Вследствие этого параметры средней задачи определяются посредством усреднения параметров множества задач {Zi}, решаемых системой, по интенсивностям их поступления (i (i=1,2,..,M), где М – количество входных потоков заявок.
Параметры типового задания вычисляются с использованием следующих предположений и соотношений. Предполагается, что процесс выполнения всегда начинается этапом счета, и что процесс как таковой может считаться марковским процессом. Тогда справедливы следующие соотношения:
интенсивность ( потока заданий:
13 EMBED Equation.3 1415; (2.1)
число 13 EMBED Equation.DSMT4 1415 процессорных операций при выполнении типового задания:
13 EMBED Equation.3 1415; (2.2)
среднее число 13 EMBED Equation.3 1415 обращений к файлу 13 EMBED Equation.3 1415 для типового задания:
13 EMBED Equation.3 1415; (2.3)
число D обращений к файлам для типового задания:
13 EMBED Equation.3 1415, (2.4)
вероятность pj использования файла Fj:
13 EMBED Equation.3 1415 (2.5)
средняя трудоемкость 13 EMBED Equation.3 1415 этапа счета:
13 EMBED Equation.3 1415, (2.6)
где (D+1) – среднее число этапов счета, приходящихся на одну среднюю задачу
2.3.3. Расчет минимального быстродействия процессора
Система массового обслуживания – одна из основных моделей, используемых инженерами-системотехниками. Далее представлено ее краткое описание.
Заявки (требования) на обслуживание поступают через постоянные или случайные интервалы времени. Приборы (каналы) служат для обслуживания этих заявок. Обслуживание длится некоторое время, постоянное или случайное. Если в момент поступления заявки все приборы заняты, заявка помещается в ячейку буфера и ждет там начала обслуживания. Заявки, находящиеся в буфере, составляют очередь на обслуживание. Если все ячейки буфера заняты, заявка получает отказ в обслуживании и теряется. Вероятность потери заявки (вероятность отказа) – одна из основных характеристик СМО. Другие характеристики: среднее время ожидания начала обслуживания, средняя длина очереди, коэффициент загрузки прибора (доля времени, в течение которого прибор занят обслуживанием) и т.д.
В зависимости от объема буфера различают СМО с отказами, где нет буфера, СМО с ожиданием, где буфер не ограничен (например, очередь в магазин на улице) и СМО смешанного типа, где буфер имеет конечное число заявок. В СМО с отказами нет очереди, в СМО с ожиданием нет потерь заявок, в СМО смешанного типа то и другое возможно.
Иногда различают заявки по их приоритету, т. е. по важности. Заявки высокого приоритета обслуживаются в первую очередь. Абсолютный приоритет дает право прервать обслуживание менее важной заявки и занять ее место в приборе (или в буфере, если все приборы заняты столь же важными заявками). Вытесненная заявка либо теряется, либо поступает в буфер, где ждет дообслуживания. Иногда приходится возобновлять обслуживание вытесненной заявки с начала, а не продолжать с точки прерывания. Если заявка вытеснена из буфера, она, естественно, теряется. Примером заявки с абсолютным приоритетом является судно, получившее пробоину и нуждающееся в срочной разгрузке. В вычислительных системах абсолютным приоритетом обладают команды оператора. Относительный приоритет дает право первоочередного занятия освободившегося прибора. Он не дает право на вытеснение заявки из прибора или буфера. Лица, имеющие льготы при обслуживании в кассе, у врача и т.п., как правило, имеют относительный приоритет. Абсолютный и относительный приоритеты различаются и моментом действия: абсолютный реализуется в момент поступления, а относительный – в момент освобождения прибора.
Различают фиксированные и динамические приоритеты. Фиксированные приоритеты чаще называют дисциплиной обслуживания.
Дисциплина обслуживания задает порядок выбора из очереди в освободившийся прибор заявок одинакового приоритета. Можно выделить следующие дисциплины обслуживания: FIFO (First Input – First Output): первым пришел – первым обслужен, LIFO (Last Input – First Output): последним пришел – первым обслужен, RAND (Random): случайный выбор из очереди. Как правило, используется дисциплина FIFO. Дисциплина LIFO реализуется в буфере, организованном по принципу стека. Такая дисциплина может оказаться целесообразной, например, при передаче информации, если ее ценность быстро падает со временем.
Одноканальная СМО определяется следующими свойствами. СМО имеет канал. В СМО приходят заявки. Если СМО пустая (нет заявок), то приходящая заявка занимает канал. Приходящая в непустую СМО заявка становится в очередь последней. Любая занявшая канал заявка обслуживается, освобождает канал и уходит из СМО. Если в момент ухода очередь непустая, первая в ней заявка выходит из очереди и занимает канал.
Рассматривая процессор как систему массового обслуживания, нетрудно получить следующую элементарную оценку его быстродействия В, которое необходимо, чтобы обслуживать поступающие задания без образования неограниченно растущей очереди. Определение производится с учетом существования стационарного режима в каждой СМО сети. Последнее условие определяет существование стационарного режима во всей сети в целом. Для одноканальной СМО условие существования стационарного режима имеет вид:
13 EMBED Equation.3 1415 (2.7)
где (i – интенсивность потока заявок в СМО;
(i – среднее время обслуживания заявок в СМО
Интенсивность (i потока заявок к любой СМО, линейной стохастической сети связана с интенсивностью источника заявок ( соотношением:
13 EMBED Equation.3 1415 (2.8)
где (i – коэффициент передачи СМО
Использование физического смысла коэффициента передачи, как среднего числа прохождений заявки из источника через СМО от момента ее поступления в сеть до момента выхода из сети, позволяет существенно упростить процедуру определения величин (i.
Определение минимального быстродействия процессора сводится к следующему. Число запросов на этап счета в процессе решения одной задачи равно (D+1). Вследствие этого значение (D+1) можно рассматривать как коэффициент передачи СМО, отображающей процессор. Таким образом, на основе выражения (2.8) интенсивность потока заявок к процессору определяется выражением:
13 EMBED Equation.3 1415 (2.9)
Среднее время обслуживания заявки в процессоре (средняя продолжительность этапа счета) с учетом выражения (2.7) и (2.8) может быть определена:
13 EMBED Equation.3 1415 (2.10)
где 13 EMBED Equation.3 1415 – быстродействие процессора
С учетом соотношений (2.7), (2.9) и (2.10) условие существования стационарного режима в СМО, отображающей в сетевой модели СОО процессор, принимает вид:
13 EMBED Equation.3 1415 (2.11)
Таким образом, минимальное быстродействие процессора, обеспечивающее существование стационарного режима можно определить из следующего выражения:
13 EMBED Equation.3 1415 (2.12)
Величина 13 EMBED Equation.3 1415 является минимально необходимым быстродействием, при котором в системе еще возможен стационарный режим; при этом время ( пребывания задания в системе, хотя и является конечным, однако может принять очень большие значения. Если же это время не должно превышать некоторую предельную заданную величину (*, то быстродействие 13 EMBED Equation.3 1415 процессора должно удовлетворять соотношению, 13 EMBED Equation.3 1415(13 EMBED Equation.3 1415, где
13 EMBED Equation.3 1415, (2.13)
и 13 EMBED Equation.3 1415 определяется по формулам (2.12) или (2.13). Из (2.13) следует, что при 13 EMBED Equation.3 1415(( величина 13 EMBED Equation.3 1415 в пределе равна 13 EMBED Equation.3 1415, но при любом конечном (* всегда 13 EMBED Equation.3 1415(13 EMBED Equation.3 1415. Обычно для быстрой оценки 13 EMBED Equation.3 1415 пользуются графиком функции 13 EMBED Equation.3 1415, выбирая 13 EMBED Equation.3 1415 при заданном (* и округляя полученное значение в большую сторону с точностью до миллионов оп/с.
2.3.4. Основы построения стохастических сетевых моделей систем оперативной обработки
Важнейшей характеристикой системы оперативной обработки (СОО) является время реакции системы – среднее время между моментом поступления задания на обработку и моментом выдачи ответа пользователю. Для оценки времени реакции, а также других характеристик СОО используются различные модели, среди которых наибольшее распространение в последнее время находит модель СОО как разомкнутой стохастической сети массового обслуживания (в дальнейшем – просто сети).
Подобная сеть может быть отображена графом, в котором узлами являются некоторые системы массового обслуживания (СМО) Si, а дуги используются для указания связей между этими СМО (рис. 2.2).
Каждая СМО может представлять либо отдельное устройство СОО (например, процессор в однопроцессорной системе), либо совокупность однотипных устройств (например, накопителей на магнитных дисках). В последнем случае говорят о многоканальной СМО с общей очередью (рис. 2.3), где каждому устройству j соответствует обслуживающий прибор Пj, а заявки (т. е. задания) выбираются из общей очереди О в соответствии с некоторой дисциплиной обслуживания.
13 EMBED Word.Picture.8 1415
13 EMBED Word.Picture.8 1415
В сети должны быть отображены только те устройства, которые оказывают наиболее существенное влияние на процесс выполнения задания пользователя в смысле величины времени реакции СОО. К этим устройствам относятся процессор (Пр), селекторные каналы (СК) и накопители, используемые в составе внешней памяти системы: на магнитных дисках (НМД) и магнитных лентах (НМЛ). Каждое из устройств реализует некоторые этапы выполнения задания: процессор выполняет этапы счета, а накопители совместно с СК – этапы взаимодействия с файлами. Технически этап обращения к файлу выполняется в две фазы: подготовительную и передачи информации. Подготовительная фаза, или фаза доступа, состоит в перемещении механизма доступа на заданный цилиндр – для НМД, и в подводе носителя – для НМЛ. Фаза передачи информации – это непосредственно обмен данными между оперативной и внешней памятью через СК. В модели СОО удобно считать, что фаза доступа выполняется самим накопителем без участия СК, а фаза передачи информации – только селекторным каналом.
С учетом этих допущений в качестве простейшей модели СОО может быть принята сеть типа рис. 2.2. В этой сети узел S0 представляет источник заявок (заданий), интенсивность ( поступления которых не зависит от числа заданий, уже находящихся в СОО (это справедливо в реальных системах, где время обдумывания пользователя много больше времени реакции системы).
Поток заданий предполагается простейшим с известным значением (. Узел S1 – это процессор (либо совокупность процессоров в мультипроцессорной системе), который, восприняв задание от источника S0, выполняет этап счета. Затем с вероятностью p10 заявка возвращается к источнику (задача решена), с вероятностью p12 направляется в узел S2, представляющий совокупность НМД, либо с вероятностью p13 – в узел S3 (совокупность селекторных каналов), после чего возвращается в процессор S1. Очевидно, в этой интерпретации на сети рис. 2.2 всегда p01 =p24 =p34 =p41 =1. Каждый из узлов S1...S4 может представлять собой СМО типа рис. 2.3. Предполагается, что дисциплина выбора заявок из очереди О для всех СМО – простейшая (в порядке поступления).
Задачей данной работы является определение минимального состава (числа устройств) СОО, необходимого для обработки потока заданий, рассчитанных при выполнении п. 2.3.2. Эта задача решается в несколько последовательных этапов, описание которых приводится в п.п. 2.3.5 – 2.3.7.
2.3.5. Размещение файлов в накопителях внешней памяти
Цель данного этапа – рациональное в заданном смысле размещение файлов данных в накопителях НМД и НМЛ. Каждый тип накопителя характеризуется своим временем доступа UД и UЛ соответственно, причем UЛ((UД.
Накопитель с размещенным в нем файлом Fj можно рассматривать как некоторую СМО, в которую поступает поток запросов интенсивностью (j, и каждый такой запрос обслуживается в среднем за время (j. Тогда условие существования стационарного режима в данной СМО:
13 EMBED Equation.3 1415 (2.14)
Интенсивность (j оценивается следующим образом. Из предыдущей лабораторной работы известны средние числа Dj обращения к файлу Fj при выполнении типового задания. Если ( – интенсивность потока заданий в СОО, то, очевидно, (j=(Dj. Подставляя это значение в (2.14) и разрешая относительно (j, получим (j ((j*, где величина
13 EMBED Equation.3 1415 (2.15)
может рассматриваться как максимально допустимое время обращения к файлу Fj. Таким образом, файл Fj может размещаться в рассматриваемом накопителе, если только время доступа этого накопителя меньше (j*.
Отсюда вытекает следующий алгоритм размещения файлов. Для каждого файла Fj, j=1,...,N, подсчитывается величина (j* по формуле (2.15). Далее проверяется условие (Л ((j*. Если оно выполняется, то файл размещается в НМЛ. В противном случае проверятся условие (Д((j*((Л. Если оно выполняется, то файл размещается в НМД. Если же и оно не выполняется (т. е. (Д ((j*), то данный файл не может быть полностью размещен в НМД, и его необходимо разделить на некоторое количество (j частей; где (j выбирается из аналогичного (2.14) условия стационарности: 13 EMBED Equation.3 1415(j(Д / nj ( 1, откуда (j((j*, где
13 EMBED Equation.3 1415 (2.16)
Значение (j фиксируется как ближайшее к (j* сверху натуральное число.
Величины (Д и (Л для каждого варианта заданы в табл. 2.3.
2.3.6. Определение параметров минимальной конфигурации СОО
Минимальной называется конфигурация СОО, в которой существует стационарный режим при обработке заданий, и все необходимые для работы файлы размещены в накопителях внешней памяти.
Важнейшими параметрами СОО являются: быстродействие процессора, количество НМД, количество НМЛ и число селекторных каналов. Быстродействие процессора было определено ранее. Требуется вычислить количество НМД, НМЛ и СК.
При определении количества накопителей внешней памяти необходимо удовлетворить условиям существования стационарного режима и полного размещения файлов в накопителях одновременно.
Далее рассмотрен способ оценки необходимого количества, mЛ, НМЛ. Совокупность НМЛ можно рассматривать как mЛ – канальную СМО, на вход которой поступает поток заявок интенсивностью (Л, и которая обслуживает каждую такую заявку в среднем за время (Л. Стационарный режим существует, если
13 EMBED Equation.3 1415. (2.17)
Интенсивность (Л обращений к файлам, размещенным к НМЛ, равна
13 EMBED Equation.3 1415, (2.18)
где pЛ – вероятность обращения к «ленточным» файлам,
13 EMBED Equation.3 1415, (2.19)
где Л – множество файлов, размещенных на НМЛ. Из (2.17), (2.18) и (2.19) следует ограничение снизу на количество НМЛ:
13 EMBED Equation.3 1415. (2.20)
Кроме (2.20), необходимо еще удовлетворить условию, при котором суммарная емкость НМЛ, используемых в СОО, не меньше необходимой суммарной длины ленточных файлов, т. е.
13 EMBED Equation.3 1415, (2.21)
где Gj – длина файла Fj, GЛ – емкость одного НМЛ.
Условия (2.20) и (2.21) удовлетворяются одновременно, если в качестве mЛ выбрать величину
13 EMBED Equation.3 1415, (2.22)
где (Z( – ближайшее сверху к Z целое число.
Аналогично, можно получить и формулу для определения интенсивности (Д обращений к файлам, размещенным к НМД, вероятность обращения к «дисковым» файлам, а также количества mД накопителей на дисках:
13 EMBED Equation.3 1415 (2.23)
13 EMBED Equation.3 1415 (2.24)
13 EMBED Equation.3 1415, (2.25)
где Д – множество файлов, размещенных на НМД, GД – емкость одного НМД.
СМО, представляющая совокупность mК селекторных каналов, характеризуется интенсивностью (К поступления заявок и средним временем (К обслуживания заявки. Следовательно условие стационарности выглядит определяется выражением:
13 EMBED Equation.3 1415. (2.26)
Очевидно, 13 EMBED Equation.3 1415. Далее, (К можно определить усреднением по времени передачи данных из НМЛ и НМД:
13 EMBED Equation.3 1415, (2.27)
где gЛ и VЛ – средняя длина записи и скорость передачи данных в НМЛ; gД и VД – те же величины для НМД. Средние длины gЛ и gД можно определить как
13 EMBED Equation.3 1415, (2.28)
13 EMBED Equation.3 1415. (2.29)
Подставляя (2.28) и (2.29) в (2.27) и разрешая неравенство (2.26) относительно mК, получим
13 EMBED Equation.3 1415. (2.30)
Таким образом, в качестве mК можно взять ближайшее к правой части неравенства (2.30) сверху целое число.
Величины VЛ, VД, GЛ и GД выбираются для расчета из табл. 2.1 в соответствии с заданным вариантом, длины Gj файлов и записей gj в них – из табл. 2.4.
2.3.7. Построение стохастической сетевой модели соо минимальной конфигурации
Считается, что стохастическая сетевая модель СОО построена, если определены структура сети и следующие параметры:
интенсивность ( входящего потока заявок;
матрица p = (pij) вероятностей передач;
количество mi обслуживающих приборов в каждой СМО Si, входящих в сеть;
трудоемкость (i однократного обслуживания в СМО Si;
быстродействие Vi одного прибора в СМО Si.
Исследование характеристик функционирования СОО проводится на модели М6, граф которой представлен на рис. 2.4. Модели ВС удобно представлять в виде направленных графов, в которых вершины графа соответствуют различным СМО, а направленные дуги – процессам перехода заявок из одной СМО в другую.
13 EMBED Word.Picture.8 1415
На рис. 2.4. приняты следущие обозначения:
S0 – процесс поступления (прихода) заявки в сеть и процесс ее выхода из сети;
S1 – процессор;
S2 – накопители на магнитооптических дисках;
S3 – накопители на жестких магнитных дисках;
S4 – каналы передачи данных.
Определение параметров упрощенных сетевых моделей сводится к следующему. Определяется матрица вероятностей передач Р=|(ij|, где (ij – вероятность того, что заявка, поступающая в систему Si, поступит в систему Sj (i,j=0,, n), где n – число каналов в системе. Очевидно, что (ii = 0 и сумма ((ii =0 для любого i.
Для сети, изображенной на рис. 2.4 очевидно, что (01=(24=(34=(41=1. Диагональные элементы матрицы нулевые. Таким образом, требуется определить элементы (10, (12, (13. Вероятность (10 представляет собой вероятность завершения задачи на очередном этапе счета. Учитывая, что задача может завершиться на любом этапе с равной вероятностью, а общее число этапов счета, приходящихся на одну задачу равно (D+1), получим:
13 EMBED Equation.3 1415 (2.31)
Вероятности (12, (13 можно представить как произведение двух вероятностей: продолжение этапа решения задачи и обращение к соответствующему накопителю.
Если счет продолжается, что происходит с вероятностью 13 EMBED Equation.3 1415, то с вероятностью (Д за этапом счета следует обращение к НМД, либо с вероятностью (Л – к НМЛ, и, следовательно,
13 EMBED Equation.3 1415, (2.32)
13 EMBED Equation.3 1415. (2.33)
В соответствии с вышеизложенным, матрица вероятностей передач для данной модели будет выглядеть следующим образом:


S0
S1
S2
S3
S4


S0
0
1
0
0
0


S1
p10
0
p12
p13
0

( =
S2
0
0
0
0
1


S3
0
0
0
0
1


S4
0
1
0
0
0

Для завершения расчетов требуется определить тройки параметров (mi, (i, (i) для систем Si. В системе S1 (процессор): m1 = 1, 13 EMBED Equation.3 1415, где (0 – трудоемкость одного этапа счета типового задания, а Vпр|(
·=10) – быстродействие процессора (определены в п. 2.3.3). В системах S2, S3 и S4 m2 = mД, m3 = mЛ, m4 = mК, а средние времена обслуживания равны соответственно (2=(Д, (3=(Л и (4=(К. Также требуется выделить все интенсивности (i.
Результат должен быть представлен в виде:
(1= m1= (1=
(2= m2= (2=
(3= m3= (3=
(4= m4= (4=
2.3.8. Расчет характеристик ВС на основе стохастической сетевой модели
Оценку характеристик СОО можно произвести на базе её модели как сети массового обслуживания [4].
Сетью массового обслуживания (СтМО) называется совокупность n+1 систем массового обслуживания (СМО), которые обмениваются между собой заявками. При этом система S0 выделяется особо и называется источником заявок; её функция – генерировать в общем случайный поток заявок интенсивности
·0. Другие системы, S1, , Sn, представляют собой в общем случае многоканальные СОО с известным числом каналов m1, , mn и известными средними временами (1, , (n обслуживания заявок в них.
СтМО называется стохастической, если поток заявок от источника, маршруты передачи заявок и времена обслуживания их в СМО носят случайный характер. Для стохастической СтМО считается, в частности, известной матрица
13 EMBED Equation.3 1415,
где 13 EMBED Equation.3 1415 – вероятность того, что заявка системы из 13 EMBED Equation.3 1415 направляется в 13 EMBED Equation.3 1415.
Интенсивности 13 EMBED Equation.3 1415 потоков заявок, входящих в СМО 13 EMBED Equation.3 1415, вычисляются как корни системы линейных уравнений
13 EMBED Equation.3 1415. (2.34)
Решая эту систему, можно получить выражения вида
13 EMBED Equation.3 1415 (2.35)
Коэффициент (і при этом обычно называется коэффициентом передачи и имеет смысл среднего числа прохождений какой-либо заявки через СМО 13 EMBED Equation.DSMT4 1415 в процессе обслуживания.
СтМО называется открытой, или разомкнутой, если интенсивность
·0 не зависит от числа заявок, находящихся в сети. В разомкнутой СтМО существует стационарный режим (т. е. режим, в котором характеристики сети «не плывут» во времени), если выполняется условие
13 EMBED Equation.3 1415. (2.36)
В этом режиме можно определить следующие не зависящие от времени сетевые характеристики: L – среднюю суммарную длину очередей, K – среднее число заявок, пребывающих в сети, W – среднее время ожидания заявки в очередях, и T – среднее время пребывания заявки в СтМО, а также одноименные узловые характеристики li, ki, wi и ti – для всех систем (узлов) 13EMBED Equation.31415, i=1,, n. Указанные характеристики связаны соотношениями:
13 EMBED Equation.3 1415, (2.37)
13 EMBED Equation.3 1415, (2.38)
13 EMBED Equation.3 1415, (2.39)
13 EMBED Equation.3 1415. 2.40)

Полезны также и связи между сетевыми характеристиками – «сетевые» формулы Литтла:
13 EMBED Equation.3 1415, (2.41)
13 EMBED Equation.3 1415. (2.42)
Стохастическая СтМО называется экспоненциальной, если поток заявок от источника – простейший, а времена обслуживания во всех системах сети распределены по экспоненциальному закону. Для экспоненциальной разомкнутой сети узловые характеристики можно вычислить по формулам:
13 EMBED Equation.3 1415 (2.43)
где
13 EMBED Equation.3 1415, (2.44)
13 EMBED Equation.3 1415 (2.45)
и
13 EMBED Equation.3 1415. (2.46)
Далее,

13 EMBED Equation.3 1415; (2.47)
13 EMBED Equation.3 1415; (2.48)
13 EMBED Equation.3 1415. (2.49)
Величина 13EMBED Equation.31415, вычисляемая по формуле (2.44), имеет смысл средней загрузки одного канала системы 13 EMBED Equation.3 1415, а величина 13 EMBED Equation.3 1415 из (2.46) – полная загрузка этой системы. В силу условия (2.36), очевидно, 13EMBED Equation.31415< 1 и 13 EMBED Equation.3 1415<13 EMBED Equation.3 1415.
В приложении к вычислительным системам оперативной обработки среднее время 13 EMBED Equation.3 1415 обслуживания заявки (задания) в системе 13EMBED Equation.31415 вычисляется как
13 EMBED Equation.3 1415, (2.50)
где 13 EMBED Equation.3 1415 – трудоемкость обслуживания заявки в системе 13EMBED Equation.31415, а 13EMBED Equation.31415 – быстродействие прибора (канала) в этой системе.
2.4. Варианты заданий
Последние две цифры в номере зачетной книжки (KK) определяют номер варианта. Если полученное значение KK больше 30, то номер варианта определяется из соотношения KK-30. В случае наличия только 10 вариантов в таблицах задания выбирается вариант в соответствии с последней цифрой номера зачетной книжки. Обращайте внимание на примечания к таблицам!
Таблица № 2.1
Интенсивность (i поступления заданий (с–1)

вар.

задачи
(i

задачи
(i

задачи
(i

задачи
(i

задачи
(i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
2
3
4
5
6
7
8
9
10
1
9
8
7
6
5
4
3
2
1
1
9
8
7
6
5
4
3
2
1
10
9
8
7
6
5
4
3
2
1
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
20
19
18
17
16
15
14
13
12
11
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
4
5
6
7
8
9
10
18
2
3
14
15
16
17
18
19
20
11
12
13
14
15
16
10
11
12
13
14
15
16
1
3
1
1
2
2
1
3
5
4
2
6
3
2
3
2
1
3
5
5
6
5
1
2
4
1
3
1
1
2
16
15
14
13
12
20
19
1
17
16
15
13
12
11
10
9
8
7
6
5
10
9
8
7
6
5
16
15
13
12
1
1
2
1
2
2
1
1
1
2
2
1
3
4
1
1
3
3
2
3
1
2
1
3
4
1
2
1
3
4
10
12
11
9
19
2
1
10
6
9
8
4
3
2
1
12
11
13
15
9
8
7
11
13
3
2
1
12
11
13
1
1
1
2
1
2
4
2
1
1
3
1
2
2
4
5
5
3
3
2
3
4
7
6
4
3
2
3
4
1

Примечание: в таблице даны значения (
·100
Таблица № 2.2
Среднее число (i процессорных операций и средние числа Nij обращений к файлам
№ задачи
(i, дес.
млн.

Nij



F1
F2
F3
F4
F5
F6
F7
F8
F9
F10

1
1
10
5




2
1



2
2

8
5
3




3


3
3


10

5




2

4
4
12
4



3

2



5
5

15
8

6

4




6
6
8

8


7


3
1

7
7
10


5


1

2


8
8

12
6

8


2

2

9
9
10
5

9





3

10
10

15



10
3

4


11
1
12

8
10



2
2
1

12
2
15
10


8

1

1


13
3

20
5


8

4



14
4
5

15
7


2

3


15
5

10
20


10

4

3

16
6

15
25
6
4

3

2


17
7
30
10

8

10



5

18
8
20

25

12



4
1

19
9

40

15


4


2

20
10
30

20

10
5

8



Таблица № 2.3
Характеристики накопителей
Номер варианта
Среднее время доступа к данным (с)
Скорость передачи данных (Кбайт/с)
Емкость накопителя
(Мбайт)


НМД
НМЛ
НМД
НМЛ
НМД
НМЛ

1
0,05
2,5
200
100
4,0
10

2
0,06
1,5
190
90
5,0
12

3
0,07
2,0
180
80
5,5
15

4
0,08
2,5
170
75
6,0
20

5
0,09
3,0
160
70
6,5
22

6
0,10
3,0
150
60
7,7
25

7
0,11
2,5
140
55
7,5
30

8
0,12
2,0
130
50
8,0
25

9
0,13
1,5
120
40
8,5
22

10
0,14
1,0
110
45
9,0
20

Таблица № 2.4
Характеристики используемых файлов
Файлы
F1
F2
F3
F4
F5
F6
F7
F8
F9
F10

Длина файла
(Мбайт)

0,5

1,0

1,0

1,5

1,5

2,0

2,5

3,0

4,0

5,0

Средняя длина
записи (Кбайт)

5

8

15

6

14

18

10

15

20

25

2.5. Содержание отчета
Постановка задачи, расчетные данные, график функции Vпр((*),результаты расчетов в соответствии с формулами (2.1) – (2.20), структура СОО минимальной конфигурации, структура СОО, структура соответствующей стохастической сети, расчетные соотношения, анализ результатов расчета и выводы.
В качестве расчетных данных должны быть приведены количественные оценки интенсивности потока заданий, числа обращений к каждому файлу, числа обращений к файлам типового задания, вероятностей использования файлов, средней трудоемкости этапа счета и нижней границы необходимого быстродействия. Для СОО требуется указать интенсивности обращений, количество каналов и среднее время обслуживания для каждой подсистемы. Для СтМО требуется указать среднюю суммарную длину очереди, среднее число заявок, среднее время ожидания и среднее время пребывания заявки в СтМО.
2.6. Контрольные вопросы
Дать определение типового задания потока.
Дать определение быстродействия процессора.
Дать определение системы оперативной обработки.
Раскрыть суть методики расчета параметров типового задания.
Какие характеристики вычислительной системы требуется знать для расчета быстродействия процессора.
Значения, каких параметров требуются для расчета числа обращений вычислительного процесса к одному, заранее заданному, файлу.
Отличие абсолютного приоритета заявки от относительного.
Дисциплины обслуживания заявок.
Свойства одноканальной системы массового обслуживания.
Дать определение времени реакции СОО.
Объяснить термин «многоканальная СМО с общей очередью».
Привести пример структурной схемы многоканальной СМО.
Какие устройства, в данной лабораторной работе, отнесены к устройствам, оказывающим наиболее существенное влияние на процесс выполнения задания пользователя.
Какие выполняются действия на подготовительной фазе этапа обращения к файлу.
Какая основная характеристика накопителя внешней памяти.
Значения каких параметров требуются для расчета максимально допустимого времени обращения к файлу.
Алгоритм размещения файлов.
Дать определение минимальной конфигурации СОО.
Привести математическое выражение, характеризующее стационарный режим СМО, реализованной в данной работе.
Значения каких параметров требуются для вычисления среднего времени обслуживания заявок СМО, представляющей совокупность селекторных каналов.
Какие параметры требуются определить, чтобы построить стохастическую сетевую модель СОО.
Алгоритм определения параметров упрощенных сетевых моделей.
Дать определение сети массового обслуживания.
Какая сеть массового обслуживания называется стохастической.
Значения каких параметров требуются для определения среднего числа прохождений какой-либо заявки через СМО Si.
Какая сеть массового обслуживания называется открытой.
Какая сеть массового обслуживания называется экспоненциальной.
Значения каких параметров требуются для расчета суммарной длины очереди для системы Si.
Для расчета какого параметра требуется значение трудоемкости обслуживания заявки в системе Si.
Список литературы
Хорошвский В.Г. Архитектура вычислительных систем. – М.: МГТУ, 2005. – 512 с.
Буза М.К. Архитектура как интерфейс между различными уровнями физической системы – Минск: БГУ, 1994. – 276 с.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Питербург, 2002. – 608 с.
Головкин Б.А. Вычислительные системы с большим числом процессоров.– М.: Радио и связь, 1995. – 318 с.
Дейкстра Э. Взаимодействие последовательных процессов // Языки программировании – М.: Мир, 1972. – 312 с.
Корнеев В.В. Параллельные вычислительные системы. – М.: Нолидж, 1999. – 320с.
Hack M. Petri net languages: Tech. Rep. / MIT. – 1976. – № 159. – 128 p. – Режим доступа: http://parallel.srcc.msu.su/computers/, вход свободный.
Борщев В.Б., Шрейдер Ю.А. Алгоритмы, языки программирования и диспозиции // Кибернетика. – 1965. – № 4.
Валиев К.А. Квантовые компьютеры: надежды и реальность. – М.: Ижевск: Регулярная и хаотическая динамика, 2002. – 320 с
Джоунз Г. Программирование на языке OKKAM. – М.: Мир, 1989.
Зарубежная радиоэлектроника. – М.: Наука, 1997. – № 2.
Карп Р.М., Миллер Р.Е. Параллельные схемы программ // Киб. сб. Новая серия.– М.: Мир, 1976.– № 13.
Майерс Г. Архитектура современных ЭВМ: в 2 ч. – М.: Мир, 1985.
Мельников В. Защита информации в компьютерных сетях. – М.: Финансы и статистика, 1997.
Нариньяни А.С. Теория параллельного программирования: Формальные модели // Кибернетика. – 1974. – № 3, № 5.
Немнюгин С.А. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Петербург, 2002.– 400 с.
Смирнов А.Д. Архитектура вычислительных систем. – М.: Наука, 1990.
Уолренд Дж. Телекоммуникационные и компьютерные сети. – М.: Постмаркет, 2001. – 480 с.
Цикритзис Д., Бернстайн Ф. Операционные системы. – М.: Мир, 1977.
Шнитман В. Современные высокопроизводительные компьютеры – Режим доступа: http://www.citforum.ru/hardware/svk/, вход свободный.








13PAGE 15


13PAGE 144415
















































Приложенные файлы

  • doc 8814545
    Размер файла: 1 MB Загрузок: 0

Добавить комментарий