Классификация вычислительных систем

8. Классификация вычислительных систем Классификация ВС весьма сложная проблема и, к сожалению, до сих пор окончательно не решена из-за большого разнообразия ВС, причѐм это разнообразие постоянно растѐт, что приводит к появлению новых признаков классификации. К настоящему времени существует несколько признаков классификации, которые применяются, в зависимости от назначения ВС, либо самостоятельно, либо в определѐнной их совокупности. Например, ВС часто разделяют в зависимости от их структурной организации на следующие классы [C6]: 1. массивно-параллельные системы (МПС; на английском – MPP); 2. симметричные мультипроцессорные системы (СМС – SMP); 3. системы с неоднородным доступом к памяти (СНДП – NUMA); 4. параллельные векторные системы (ПВС – PVP); 5. кластерные системы (КС). Подробнее эти системы будут рассмотрены позднее. 1. 2. 3. 4. 5. Иногда ВС различают: по числу одновременно обрабатываемых программ – однопрограммные и многопрограммные (мультипрограммные); по режиму функционирования – системы реального времени (обычно применяются в системах управления технологическими процессами) и универсальные (не привязанные к реальному времени); по возможности изменения структуры – пассивные (с жѐсткой структурой, созданной в расчѐте на определѐнный класс задач) и активные, способные настраиваться на вновь поступившую прикладную задачу; по типу используемых процессоров – однородные и неоднородные; по условиям использования – индивидуального пользования, использования в пакетном режиме и коллективного пользования и т.д. Применяя известную или создавая новую классификацию, необходимо ответить на главный вопрос – для кого предназначается данная классификация и на решение какой задачи направлена. Так разделение систем обработки данных на персональные ЭВМ, рабочие станции, серверы, большие универсальные ЭВМ, мини супер-ЭВМ, супер-ЭВМ позволяет пользователю примерно прикинуть производительность и стоимость приобретаемого изделия для решения требуемого класса задач. Разработчику классификация должна подсказать возможные пути совершенствования СОД и в этом смысле она должна быть достаточно содержательной. А удачной классификацию можно назвать тогда, когда с еѐ помощью могут быть определены направления поиска новых структур и архитектур средств вычислительной техники. 45 В [3] авторы приводят оригинальный подход к классификации СОД, который основан на выделении «основополагающих, неделимых признаков, имеющих генный характер». Определены пять генетических признаков классификации систем обработки данных. Этими признаками являются: 1. cпособ представления информации; 2. тип запоминающей среды; 3. способ доступа к информации; 4. совмещение функций хранения и обработки информации; 5. способ организации процесса обработки информации. Перечень признаков и видов их реализации приводятся в таблице 10.1. Таблица 8.1. Генетические признаки классификации СОД и виды их реализации Генетический признак Реализация признака Цифровой (символьный); Способ представления информации Образный Дискретная; Распределѐнная Тип запоминающей среды (непрерывная) Способ доступа к информации Адресный; Ассоциативный Совмещение функций хранения и Раздельные; Совмещѐнные обработки информации Способ организации процесса Алгоритмический; обработки информации Самоорганизующийся Рассмотрим данные признаки более подробно. В своей работе [3] авторы отмечают, что известны два способа представления информации: символьное в виде абстрактных цепочек, цифр, букв или других символов; образное в виде чувственных образов. В силу целого ряда объективных причин в технических СОД информация представлена как последовательность символов двоичного алфавита. Такая форма представления информации в наибольшей степени соответствует возможностям современной технологии создания элементов, структурной и логической организации СОД. Однако с ростом сложности решаемых задач, их многомерности всѐ в большей степени проявляются недостатки одномерной символьно-отвлечѐнной формы представления информации как чужеродной нашему мышлению. Важно также отметить, что символьная форма представления информации сложилась как технология работы с готовой информацией, знаниями, базирующаяся на формальной логике. Далее авторы делают вывод о том, что в биологических системах, и, прежде всего, в памяти человека, информация представлена в более сложном виде. Известно, что человек использует два механизма мышления. Во-первых, так называемое символьное или алгебраическое мышление позволяет работать с абстрактными цепочками символов, с которыми связаны семантические и 46 прагматические представления. Другой механизм образное, геометризованное мышление позволяет работать с чувственными образами и представлениями об этих образах. Образы обладают гораздо большей информативностью, чем символы. С точки зрения такого признака классификации как «тип запоминающей среды», авторы выделяют базовое свойство, позволяющее разделить все существующие запоминающие среды на два класса. Это свойство определено как способ фиксации информации в запоминающей среде. В известных запоминающих средах информация фиксируется либо в локальной области (точке) среды, либо распределена по всей поверхности или всему объѐму среды. Запоминающие среды, в которых в любой фиксированный момент времени можно выделить локальную область, точку среды, хранящую наименьшую единицу информации (бит) классифицируются как дискретные запоминающие среды. Запоминающие среды, в которых невозможно выделить локальную область, хранящую наименьшую единицу информации, и информация в которых распределена по всей поверхности или всему объѐму среды классифицируются как распределѐнные (непрерывные) запоминающие среды. К ним относятся, например, нейронные сети и голографические среды. Что касается признака «способ доступа к информации», то стоит отметить лишь следующее. Способ доступа, при котором информация в запоминающей среде находится путѐм указания еѐ местоположения в среде, называется адресным. Способ доступа к информации в запоминающей среде, базирующийся на механизме ассоциации, получил название ассоциативного способа доступа. Четвѐртый признак классификации «совмещение функций хранения и обработки информации» разделяет СОД на два класса. Первый связан с разделением хранения и обработки информации, что приводит к созданию самостоятельных устройств, предназначенных для хранения и обработки информации. В настоящее время этот класс систем является доминирующим в области обработки данных. Второй класс использует принцип переноса процесса обработки непосредственно в память ВС. Это становится возможным только с применением ассоциативного способа доступа к информации, который позволяет совместить функции хранения и обработки данных в одном устройстве. Пятый признак по существу выделяет системы с традиционным алгоритмическим, программным способом организации вычислительного процесса (процесса обработки информации) и системы, базирующиеся на самоорганизации процесса обработки информации за счѐт еѐ непрерывного самообучения. К этому классу систем можно отнести нейрокомпьютеры. Широко распространѐнным признаком классификации параллельных систем, введѐнным М. Дж. Флинном (а по нашему определению любая ВС является параллельной), есть соотношение между числом потоков команд и числом потоков данных, имеющих место в вычислительной системе при 47 выполнении одной общей или нескольких независимых задач. Под потоком команд понимается последовательный ряд команд, выполняемых системой, а под потоком данных - последовательность данных, вызываемых потоком команд, включая и промежуточные результаты. Считается, что в ВС могут присутствовать одиночные (О) и множественные (М) потоки команд (К) и данных (Д). В этом случае существуют четыре класса систем, из которых три последних являются параллельными: 1. ОКОД (SISD) – одиночный поток команд, одиночный поток данных (последовательная ВС); 2. ОКМД (SIMD) – одиночный поток команд, множественный поток данных (параллельная ВС); 3. МКОД (MISD) – множествнный поток команд, одиночный поток данных (параллельная ВС); 4. МКМД (MIMD) – множественный поток команд, множественный поток данных (параллельная ВС). Множественность потока команд предполагает одновременное выполнение нескольких команд, множественность потока данных – одновременную обработку нескольких данных. Следует отметить, что и та, и другая множественность может быть реализована, если в ВС присутствует множественность аппаратных средств (процессоры, модули памяти) и соответствующее программное обеспечение. ОКМД. Различные данные обрабатываются по одной программе (одни и те же действия ОК – одиночный поток команд, с разными данными Д1,Д2,Д3,Д4 – множественный поток данных, см. рис. 8.1). Очевидно, что такая система, составленная из большого числа процессоров, может обеспечить очень высокую производительность только на тех задачах, при решении которых все процессоры могут делать одну и ту же работу. Рис.8.1 Обобщѐнная схема системы ОКМД ВС (ОКМД) может быть построена: 1. на основе векторных процессоров; 2. на основе матричных процессоров; 3. на основе ассоциативных процессоров. 48 МКОД. Одни и те же данные ОД (см. рис ) проходят несколько этапов обработки: экспресс обработка  первичная обработка  вторичная обработка… Каждый этап должен быть выполнен за определѐнное время. Эти системы асинхронны, т.к. время решения различно, у каждого процессора свой поток команд К1,К2,К3,К4. Рис.8.2 Обобщѐнная схема системы МКОД Класс МКОД содержит один вид, который определѐн как магистральные (конвейерные) ВС, иногда их называют мультиконвейерными ВС. Вышеуказанный признак классификации характеризует прежде всего организацию функционирования вычислительной системы и не раскрывает практические вопросы реализации взаимодействия компонент ВС при решении одной общей или нескольких независимых задач. Поэтому в последнее время появилось большое число расширений классификации Флинна. Одно из таких расширений подразумевает разбиение класса ОКМД на три вида. Это вычислительные системы с векторным потоком команд, ВС, построенные на основе матричных процессоров и ВС, построенные на основе ассоциативных процессоров, что представлено на рис. 8.3. Все эти системы будут рассмотрены при дальнейшем изложении материала. 49 Рис. 8.3 Классификация вычислительных систем Несмотря на то, что класс МКМД чрезвычайно широк, он разбивается на три вида – многопроцессорные ВС (МВС) с распределѐнной памятью, МВС с общей памятью и МВС со смешанной организацией памяти. Большое число авторов предлагают различные классификации отдельных классов параллельных ВС. Например, Р. Хокни – известный английский специалист в области параллельных вычислительных систем, разработал свой подход к классификации систем, попадающих в класс МКМД, представленной на рис. 8.4. Основная идея классификации базируется на том, что множественный поток команд может быть обработан двумя способами: либо одним конвейерным устройством обработки, работающим в режиме разделения времени для отдельных потоков, либо каждый поток обрабатывается своим собственным устройством. Первая возможность используется в МКМД системах, которые автор называет конвейерными. 50 Рис. 8.4 Классификация Хокни Архитектуры, использующие вторую возможность, в свою очередь опять делятся на два класса: 1. МКМД системы, в которых возможна прямая связь каждого процессора с каждым, реализуемая с помощью переключателя; 2. МКМД системы, в которых прямая связь каждого процессора возможна только с ближайшими соседями по сети, а взаимодействие удалѐнных процессоров поддерживается специальной системой маршрутизации через процессоры посредники. Далее, среди МКМД систем с переключателем Хокни выделяет те, в которых вся память распределена среди процессоров как их локальная память. В это случае общение самих процессоров реализуется с помощью очень сложного переключателя, составляющего значительную часть системы. Такие системы носят название систем с распределѐнной памятью. Если память разделяемый ресурс, доступный всем процессорам через переключатель, то такие МКМД системы являются системами с общей памятью. В соответствии с типом переключателей можно проводить классификацию и далее: простой переключатель, многокаскадный переключатель, общая шина. Многие современные вычислительные системы имеют как общую разделяемую память, так и распределѐнную локальную память. Такие системы Хокни рассматривает как гибридные МКМД с переключателем. При рассмотрении МКМД систем с сетевой структурой считается, что все они имеют распределѐнную память, а дальнейшая классификация проводится в соответствии с топологией сети. Позднее Е. Джонсон предложил проводить классификацию МКМД систем на основе структуры памяти и реализации механизма взаимодействия и синхронизации между процессорами. По структуре оперативной памяти 51 существующие вычислительные системы делятся на две большие группы: либо это системы с общей памятью, прямо адресуемой всеми процессорами, либо это системы с распределѐнной памятью, каждая часть которой доступна только одному процессору. Одновременно с этим, и для межпроцессорного взаимодействия существует две альтернативы: через разделяемые переменные или с помощью механизма передачи сообщений. Исходя из таких предположений, можно получить четыре класса МКМД систем, уточняющих классификацию Флинна: 1. общая память – разделяемые переменные; 2. распределѐнная память – разделяемые переменные; 3. распределѐнная память – передача сообщений; 4. общая память – передача сообщений. В 1988 году была сделана очередная попытка расширить классификацию Флинна и, тем самым, преодолеть еѐ недостатки. Д. Скилликорн разработал подход, пригодный для описания свойств многопроцессорных систем и некоторых нетрадиционных архитектур, в частности, потоковых машин. Хотя автор излагает свою классификацию как классификацию архитектур вычислительных систем, на мой взгляд речь идѐт о классификации структур ВС. Предлагается рассматривать архитектуру любой системы, как абстрактную архитектуру, состоящую из четырѐх компонент: 1. процессор команд (IP – Instruction Processor) – функциональное устройство, работающее как интерпретатор команд; в системе, вообще говоря, может отсутствовать; 2. процессор данных (DP – Data Processor) – функциональное устройство, работающее как преобразователь данных, в соответствии с арифметическими операциями; 3. иерархия памяти (IM – Instruction Memory, DM – Data Memory) – запоминающее устройство, в котором хранятся команды и данные, пересылаемые между процессорами; 4. переключатель – абстрактное устройство, обеспечивающее связь между процессорами и памятью. Функции процессора команд во многом схожи с функциями устройства управления последовательных машин и, согласно, Д. Скиллкорну, сводятся к следующему: 1. на основе своего состояния и полученной от DP информации IP определяет адрес команды, которая будет выполняться следующей; 2. осуществляет доступ к IM для выборки команды; 3. получает и декодирует выбранную команду; 4. сообщает DP команду, которую надо выполнить; 5. определяет адрес операндов и посылает их в DP; 6. получает от DP информацию о результате выполнения команды. 52 Функции процессора данных делают его, во многом, похожим на арифметическое устройство традиционных процессоров: 1. DP получает от IP команду, которую надо выполнить; 2. получает от IP адреса операндов; 3. выбирает операнды из DM; 4. выполняет команду; 5. запоминает результат в DM; 6. возвращает в IP информацию о состоянии после выполнения команды. В терминах определѐнных таким образом основных частей системы можно представить структуру любой параллельной системы, при этом автор выделяет четыре типа переключателей, без какой-либо явной связи с типом устройств, которые они соединяют: 1-1 – переключатель такого вида связывает пару функциональных устройств; n-n – переключатель связывает i-ое устройство из одного множества устройств с i-ым устройством из другого множества, т.е. фиксирует попарную связь; 1-n – переключатель соединяет одно выделенное устройство со всеми функциональными устройствами из некоторого набора; nn – каждое функциональное устройство одного множества может быть связано с любым устройством другого множества, и наоборот. Примеров подобных переключателей можно привести очень много. Так все матричные процессоры имеют переключатель типа 1-n для связи единственного процессора команд со всеми процессорами данных. В машинах семейства Connection Machine каждый процессор данных имеет свою локальную память и, следовательно, связь будет описываться как n-n. В то же время, каждый процессор команд может связываться с любым другим процессором, поэтому данная связь будет описана как nn. Классификация Д. Скилликорна состоит из двух уровней. На первом уровне она проводится на основе восьми характеристик: 1. количество процессоров команд (IP); 2. число запоминающих устройств (модулей памяти) команд (IM); 3. тип переключателя между IP и IM; 4. количество процессоров данных (DP); 5. число запоминающих устройств (модулей памяти) данных (DM); 6. тип переключателя между DP и DM; 7. тип переключателя между IP и DP; 8. тип переключателя между DP и DP. В терминах данных характеристик машину Connection Machine 2 можно описать так: (1, 1, 1-1, n, n, n-n, 1-n, nn). 53 На втором уровне классификации Д. Скилликорн просто уточняет описание, сделанное на первом уровне, добавляя возможность конвейерной обработки в процессорах команд и данных. Автор сформулировал три цели, которым должна служить хорошо построенная классификация: 1. облегчать понимание того, что достигнуто на сегодняшней день в области архитектур вычислительных систем, и какие архитектуры имеют лучшие перспективы в будущем; 2. подсказывать новые пути организации архитектур - речь идѐт о тех классах, которые в настоящее время по разным причинам пусты; 3. подсказывать, за счѐт каких структурных особенностей достигается увеличение производительности различных вычислительных систем; с этой точки зрения, классификация может служить моделью для анализа производительности. Теперь попытаемся привести свой подход к построению классификации архитектур вычислительных систем (см. рис.8.5). Во введении было определено понятие архитектуры ВС как совокупность трѐх категорий - сущность информационных потоков (ИП), характер их взаимодействия и способ обработки данных. Будем считать эти категории основными признаками классификации. Однако для более детальной проработки классификации необходимо ввести дополнительные признаки, которые уточняют вид архитектуры ВС. Рассмотрим первый признак. На первое место, на мой взгляд, необходимо поставить способ обработки данных, так как он определяет тип реализации непосредственно операций над данными в исполнительных устройствах процессора, и разбиение на классы архитектур по этому признаку не зависит от значений следующих признаков. При анализе способа обработки данных можно выделить две составляющие: 1. координата (обработка может быть горизонтальной, вертикальной и многокоординатной); 2. параллелизм (последовательная, последовательно-параллельная и параллельная обработка элемента потока данных). Второй признак – сущность информационных потоков – определяет совокупность видов информационных потоков, циркулирующих в системе обработки данных. Например, можно выделить четыре вида ИП – данные, команды, функции и задания. В настоящее время можно определить три класса архитектур в соответствии с данной составляющей признака: (команды – данные), (функции – данные) и (задания – данные). После того как определены ИП в СОД, необходимо уточнить характер их прохождения в исполнительных устройствах СОД. Характер прохождения может быть организован либо в виде конвейера, либо без такового. Причѐм конвейер, как было отмечено выше, реализуется на уровне операций, команд, 54 процессов, соответствующих, например, отдельным ветвям программы, и различным сочетаниям этих конвейеров. Важной характеристикой архитектуры ВС является реализация типового контроля элементов информационных потоков. Введение типов устанавливает взаимно однозначное соответствие между объектом и его изображением в информационной среде и, по существу, устраняет последствие семантического разрыва неймановской архитектуры. Задание типов данных и реализация типового контроля может осуществляться либо программно, либо программно-аппаратно, либо аппаратно. Как было отмечено в предыдущих разделах, ещѐ одним узким местом неймановской архитектуры является так называемый побочный эффект. Эффективность смягчения этого эффекта зависит от способа реализации конструкций языков высокого уровня. Таких способов существует три: программный, программно-аппаратный и аппаратный. Из оставшихся пяти признаков следует обратить внимание на следующие два. Один из них основной – характер взаимодействия потоков, который по существу разделяет архитектуру ВС на два класса. Первый использует в том или ином виде неймановский принцип обработки, атрибутом которого является счѐтчик команд. Второй – принцип управления данными, атрибутом этого типа архитектуры является признак готовности данных. Этот основной признак можно уточнить так – очередной элемент ИП данного типа инициирует активизацию порции информационного потока другого вида. Например, в неймановской архитектуре очередная команда содержит информацию о местоположении в памяти элементов потока данных, над которыми и производятся определѐнные действия. Ещѐ один признак, который необходимо уточнить, это реализация параллелизма. На примере рис.8.5 видно, что, если рассматривать параллелизм на уровне команд, то он может быть реализован либо статически (распределение команд по исполнительным устройствам процессора осуществляется на уровне компиляции заранее), либо динамически – то же распределение осуществляется устройством управления в процессе обработки данных. 55 Рис. 8.5 Архитектура вычислительных систем 9. Режимы обработки данных ВС Одним из важнейших путей повышения производительности вычислительных систем является использование того или иного режима функционирования в зависимости от класса решаемых задач и требований к процессу их выполнения. Существуют два режима работы ВС – однопрограммный и мультипрограммный (многопрограммный). По режиму обслуживания данные системы можно разделить на два вида – индивидуального и коллективного пользования. По способу приѐма заданий на обработку различают пакетную обработку и обработку заданий поступающих независимо друг от друга в случайные моменты времени от разных пользователей. Пакетная обработка может производиться как в однопрограммном, так и многопрограммном режимах. Режим коллективного пользования – это форма обслуживания, при которой возможен одновременный доступ нескольких независимых пользователей к вычислительным ресурсам ВС. Системы коллективного пользования с квантованным обслуживанием называются системами с разделением времени [5]. 9.1 Пакетный режим функционирования ВС В этом режиме пользователи не имеют непосредственного доступа к ВС. Подготовленные ими программы передаются по каналам связи в систему, где они накапливаются и оформляются в виде единого пакета. В момент, когда система готова принять на обработку пакет заданий начинается процесс обработки по заранее составленному расписанию. 1 ЯОС Пакет Очереди задач на выполнение (m штук) Очереди к периферийным МОД устройствам. пери фер ийны е устро йства m Рис.9.1 Схема пакетной обработки задач Каждый пакет имеет паспорт, в котором содержится число задач, их тип. В свою очередь каждая задача имеет свой паспорт, в котором указывается приоритет и др. необходимая информация. МОД – модуль обработки данных. ЯОС – ядро операционной системы. 57 Ядро ОС содержит планировщик, который определяет, какую задачу выполнять (с учѐтом приоритетов). Если режим – однопрограммный, то пакеты выполняются последовательно. В мультипрограммном режиме формируются очереди (на основе приоритетов задач). Ядро ОС выделяет определѐнную область памяти для каждой задачи. После того, как задача выполнилась, формируются очереди на пользование периферийными устройствами. В пакетном режиме применяется механизм квантования. Т.е. каждой задаче выделяется время исполнения (время процессора) и если за это время задача не выполнится, то она поступает в конец очереди. Пакетный режим используется очень часто, несмотря на высокие «накладные расходы». Особенности пакетного режима: 1. Развитая система прерываний (необходимо прерывать выполнение задачи и сохранять еѐ вектор, перейти к другой задаче, а затем снова возвращаться к выполнению этой задачи). Это приводит к значительным «накладным расходам». 2. Необходима защита памяти от доступа к данным задачи из других задач. 3. Необходимы специальные привилегированные команды (команды защиты), доступные только системе. 4. Требуется специальный датчик времени (таймер) для реализации механизма квантования. Мультипрограммная пакетная обработка обеспечивает высокую степень загрузки ресурсов ВС, но при этом из-за отсутствия непосредственной связи между системой и пользователем производительность и эффективность труда самих пользователей снижается по сравнению с индивидуальным обслуживанием. 9.2 Режим разделения времени (потоковый режим) В общем случае на вход ВС поступает случайный поток задач от нескольких источников (пользователей). Вычислительная система с разделением времени (СРВ), работающая в мультипрограммном режиме, в определѐнной последовательности обслуживает пользователей, выделяя программе (заданию) каждого пользователя некоторый интервал времени (квант обслуживания). Если в течение выделенного программе кванта времени еѐ обработка не заканчивается, программа прерывается и становится в очередь программ, ожидающих обработку. Порядок распределения между пользователями основного ресурса СРВ – времени процессоров – устанавливается дисциплиной квантованного обслуживания. Выбор значения кванта времени определяется двумя 58 основными факторами – уменьшение времени отклика на запросы пользователя и увеличение загрузки основного ресурса ВС. Малое значение кванта времени, выделяемое программе ведѐт к снижению эффективности использования технических средств системы, так как переключение программы из пассивной фазы в активную сопровождается служебными операциями, доля которых при этом в общем времени работы системы возрастает. Значение кванта времени выбирается в результате разумного компромисса, с тем, чтобы время отклика на запрос, и потери производительности от переключения активности программ были приемлемыми. Возможно два варианта дисциплин обслуживания: а) одноочередная дисциплина обслуживания, упрощенная схема СРВ с которой представлена на рис. 9.2. Вновь поступающие от пользователя программы ставятся в конец очереди. Возврат в начало очереди, если за дача не выполнена за время МОД Одна очередь Рис.9.2 Схема системы с режимом разделения времени с одноочередной дисциплиной обслуживания Здесь обязательно используется режим квантования. Если задача не решена за время Δ, то она отправляется в конец очереди. Время выбирается исходя из параметров ВС. Недостатком такой дисциплины обслуживания является очень длительное время решения больших задач. б) многоочередная дисциплина обслуживания, упрощенная схема СРВ с которой представлена на рис. 9.3. Для сокращения потерь времени, связанных с переключением программ, и обеспечения приоритета для коротких программ используют дисциплину обслуживания с несколькими очередями 59 Возврат в начало очереди, если за дача не выполнена за время Очередь 0 МОД *2 m Очередь m Входы Рис. 9.3 Схема системы с многоочередной дисциплиной обслуживания У каждой очереди свой приоритет (приоритет соответствует номеру очереди: 0- наибольший приоритет, m– наименьший приоритет). У задачи может быть задан приоритет, либо его устанавливает ОС, основываясь на данных, полученных из паспорта задачи (время выполнения задачи и требуемые ресурсы). Если время выполнения задачи не указано, то оно оценивается пропорционально длине кода программы. Чем дольше исполняется программа, тем ниже приоритет, но в таких очередях больше. По приоритету задача направляется в соответствующую очередь. Если задача имеет наивысший приоритет, но не успевает выполниться, в отведенный квант времени (Δ), то вступает в силу механизм динамических приоритетов: если задача не решена за время Δ, то она «проваливается» в очередь с более низким приоритетом. Т.е. пользователь устанавливает максимальный приоритет, а ОС его постепенно понижает. Номер очереди, куда следует поместить задачу, определяется по следующей формуле:  l   p    m  log 2  l  1    m- номер очереди, куда следует поместить задачу, l p - длина кода программы в байтах, l -длина кода программы в байтах, которая может быть передана из оперативной памяти во внешнюю или обратно за квант времени . 60 9.3 ВС реального времени В ряде применений вычислительных систем, таких, как контроль и управление различными технологическими процессами, на обработку вводимых данных и выдачу результатов накладываются жѐсткие ограничения на время выполнения задачи, диктуемые темпом развития процессов в контролируемом объекте. Вычислительной системой реального времени (системой, работающей в масштабе реального времени) называется система, соединенная с некоторым внешним объектом и обрабатывающая поступающую в неѐ информацию о его состоянии достаточно быстро, для того, чтобы результат обработки мог использоваться для воздействия на протекание процессов в объекте. На рис 9.4 представлена упрощѐнная структурная схема автоматизированной системы управления с модулем обработки данных МОД. Принцип обработки в таких системах носит итерационный (периодический) характер, данные D поступают на вход системы через равные промежутки времени и именно в течение этого промежутка времени должны быть выработаны управляющие воздействия Y на объект. ИМ1 Y1 Yk Объект управления ИМк X1 Д 1 X m Дm СЕВ ДПр К2 ЦАП СПр МОД Устройство отображения (дисплей) Архив Рис.9.4 Схема системы реального времени ИМ1…ИМК- исполнительные механизмы. Д1...ДК – датчики. СЕВ – система единого времени. 61 К1 АЦП ДПр – датчик прерываний. СПр – система прерываний. МОД – модуль обработки данных. К1,К2 –коммутаторы АЦП – аналого-цифровой преобразователь ЦАП – цифро-аналоговый преобразователь Таким образом, главной особенностью вычислительных систем реального времени является способность принять данные, как правило, с большого числа датчиков, преобразовать их в цифровую форму, привязать к реальному отсчѐту времени (с помощью системы единого времени), обработать, выдать управляющие воздействия, архивировать данные и постоянно отображать состояние объекта на устройстве отображения за фиксированный интервал времени. Второй главной особенностью таких систем является требование высокой надежности. 10. Системы класса MIMD (МКМД) Системы данного класса делятся, как это было отмечено выше на два основных вида – системы с общей и распределенной памятью. Обычно в качестве синонима систем первого вида используется термин «многопроцессорные вычислительные системы», второго вида «многомашинные вычислительные системы» [C6]. В МКМД системах каждый их процессор выполняет свою программу (или часть большой программы) достаточно независимо от других процессоров. Большой интерес к системам данного класса определяется двумя факторами: 1. свойства систем МКМД дают большую гибкость – при наличии адекватной поддержки со стороны аппаратных средств и программного обеспечения МКМД может работать как однопользовательская система, обеспечивая высокопроизводительную обработку данных для одной прикладной задачи, как многопрограммная система, выполняющая множество задач параллельно, и как комбинация этих возможностей; 2. система МКМД может использовать все преимущества современной микропроцессорной технологии на основе строгого учета соотношения производительность/стоимость. В действительности практически все современные МКМД системы строятся на тех же процессорах, что и персональный компьютер, рабочие станции и сервера. Одной из отличительных особенностей МКМД систем является сеть обмена, с помощью которой процессоры соединяются друг с другом или с памятью. Модель обмена для таких систем настолько важна, что многие характеристики производительности и другие оценки выражаются отношением времени обработки к времени обмена, соответствующим решаемым задачам. Существуют две основные модели межпроцессорного обмена : одна основана на передаче сообщений, другая на использование общей памяти. В многопроцессорной системе с общей памятью один процессор осуществляет запись в конкретную ячейку, а другой производит считывание из этой ячейки памяти. Чтобы обеспечить согласованность данных и синхронизацию процессов, обмен часто реализуется по принципу взаимно исключающего доступа к общей памяти методом «почтового ящика». В многомашинной системе процессоры получают доступ к совместно используемым данным посредством передачи сообщений по сети обмена. Эффективность схем коммуникаций зависит от протоколов обмена, характеристик основных сетей обмена (в том числе каналов связи), пропускной способности памяти. Таким образом, базовой моделью вычислений в МКМД системах является совокупность независимых процессов, эпизодически обращающихся к разделяемым данным. Существует достаточно большое количество вариантов этой модели. На одном конце спектра – это модель распределенных вычислений, в которой программа делится на довольно 63 большое число параллельных задач, состоящих из множества подпрограмм. На другом конце спектра – модель потоковых вычислений, в которой каждая операция в программе может рассматриваться как отдельный процесс. Такая операция ждет своих входных данных (операндов), которые должны быть переданы ей другими процессами. По их получении операция выполняется, и полученное значение передаѐтся тем процессам, которые в нѐм нуждается. На рис. 10.1 представлена упрощѐнная схема МКМД системы. - центральное устройство управления ПД (поток Р1 Р2 Р3 результатов) M1 М2 М3 - Память (обычно модульного типа) Рис. 10.1 Упрощѐнная схема системы МКМД В реализации любой модели вычислений кто-то должен управлять всем этим процессом. Это м.б. специальный процессор (тогда он должен быть мощнее, чем каждый из Р 1,2,3, так как он должен решать сложную задачу назначения). Это система с централизованным управлением. Ее минус в высокой стоимости. Роль управляющего процессора могут играть несколько процессоров (В одной из систем Cray, например, входят 8 обрабатывающих процессоров и 4 управляющих, т.е. 2х1). В ОКМД всегда одно ЦУУ, но здесь будет несколько таких устройств. Один из управляющих процессоров назначается главным – обеспечивая взаимодействие 4-х управляющих процессоров.    Минусы:  Сложная подготовка задач к параллельным вычислениям, ведь «простая» программа здесь не будет эффективна.  Сложное и дорогое ЦУУ Свойства MIMD:  Иерархия управления (управляющий процессор, в каждом процессоре свое управление)  Несколько уровней памяти (cashe 1,2,3; RAM; HD)  Иерархия коммутации (магистрали между процессорами и магистрали между узлами) Как было отмечено выше МКМД делятся на:  Системы с общей памятью (UMA)  Системы с распределенной памятью 64 Системы со «смешанной» памятью (NUMA - Non Uniform Memory Access). В системах со «смешанной» памятью модули памяти физически располагаются в разных процессорах, но адресное пространство у них общее, поэтому доступ к своей локальной памяти быстрее, чем к чужой).  11. ВС с общей памятью (UMA) К данной группе систем МКМД относятся системы с общей (разделяемой) основной памятью, объединяющие до нескольких десятков (обычно не более 32) процессоров. Сравнительно небольшое число процессоров в таких системах определяется наличием одной шины, соединяющей эти процессоры. Таким образом, при наличии у процессоров кэш-памяти достаточной ѐмкости высокопроизводительная шина и общая память могут удовлетворить обращения к ней поступающие от нескольких процессоров. Поскольку имеется единственная общая память с одним и тем же временем доступа для любого процессора, поэтому такие системы и получили название UMA (Uniform Memory Access). Довольно часто, и не всегда обосновано, при анализе систем с общей памятью (в том числе и систем на основе векторных процессоров) затраты на обмен не учитываются, так как проблемы обмена в значительной степени скрыты от программиста. Однако накладные расходы на обмен в этих системах имеются и определяются конфликтами шин, памяти и процессоров. Чем больше процессоров добавляются в систему, тем больше процессов соперничают при использовании одних и тех же ресурсов, что приводит к большему числу конфликтов. Модель системы с общей памятью очень удобна для программирования, так как мало отличается от программирования для однопроцессорной системы [4]. В случае неудовлетворительных результатов применения системы с одной шиной, число их может быть увеличено. На рис. 1.11 представлена схема такой системы. Р1 Р2 Р3 СM1 СМ2 СМ3 - Коммутационная сеть 1-ая и 2-ая шины ВМ1 ВМ2 КВВ - Канал ввода-вывода Общая память ( общее адресное пространство) Рис. 11.1 Упрощѐнная схема системы МКМД с общей памятью 65 В состав данной системы входит арбитр (на каждую шину по одному арбитру – на рисунке не показаны), который регулирует доступ процессора к шине, т.к. процессор может одновременно работать только с одной шиной (т.к. кэш-память СМ у процессора - одна). Такая организация дает положительный эффект при наличии нескольких модулей памяти –ВМ. Любой процессор в данной системе может быть управляющим.  Он анализирует паспорта задач (в каждом есть таблица связности и временные ограничения)   Решает задачу назначения (в статическом режиме), т.е. выбирает стратегию назначения (либо из паспорта, либо с помощью своей экспертной системы).   Ведѐт мониторинг параллельных вычислений. Преимущества систем с общей памятью следующие.  1. Совместимость с хорошо понятными используемые как в однопроцессорных, так и многопроцессорных системах, механизмами, которые используют для обмена общую память. 2. Простота программирования, когда модели обмена между процессами сложные или динамически меняются во время выполнения. Подобные преимущества упрощают процесс создания компиляторов. 3. Более низкая задержка обмена и лучшее использование полосы пропускания при обмене малыми порциями данных. 4. Возможность использования аппаратно управляемого кэширования для снижения частоты доступа к общей памяти. Без предполагаемой поддержки со стороны аппаратуры все обращения к разделяемой памяти потребуют привлечения операционной системы как для преобразования адресов так и защиты памяти. 12. Проблема когерентности в ВС с общей памятью В системах с общей памятью кэши могут содержать как разделяемые («общие») , так и частные данные. Частные данные – это данные, которые используются одним процессором, в то время как разделяемые данные используются многими процессорами, по существу являясь причиной обменов между ними. Когда кэшируется элемент частных данных, их значение переносится в кэш для сокращения среднего времени доступа. Поскольку никакой другой процессор не использует эти данные, этот процесс идентичен процессу для однопроцессорной машины с кэш-памятью. Если кэшируются разделяемые данные, то их значение реплицируется и может содержаться в нескольких кэшах. Поэтому кэширование данных вызывает новую проблему – когерентность кэш-памяти. КЕШ ОП X'=200 X=100 Одна и та же переменная имеет разные значения в кэш-памяти и оперативной памяти. Это и есть нарушение когерентности. Если процессор один, то рано или поздно он 66 все поправит, но если несколько процессоров и одна оперативная память, хранящая данные одной большой задачи, то налицо нарушение когерентности, причем сразу у нескольких процессоров, которым нужно сообщить об этом нарушении. Поэтому, на стадии программирования необходимо помнить об этом и предусмотреть способы смягчения этой проблемы. Существует два механизма решения этой проблемы: 1. Наблюдение – каждый процессор наблюдает за движением данных, помеченных признаком достоверности, тогда процессор обратится за данными в ОП, а не в свою кэш-память. Причем, наблюдение ведется постоянно. Этот механизм позволяет не использовать ложные данные. Механизм наблюдения за магистралью заимствован из сетей. 2. Справочник – считается единым справочником, но фактически распределен (находится у каждой СМ). В справочнике хранится информация обо всех данных. В случае недостоверности общих данных в справочнике выставляется, что это данное недостоверно и передается сообщение об этом справочникам других процессоров. Отличие этого механизма состоит в том, что мы не отлавливаем информацию, а получаем Существуют следующие механизмы замены: 1. Обнуление (во всех IBM). Если общие данные изменились в i-м процессоре, то i-й процессор инициирует (сообщает) другим процессорам, что у них этого блока нет (в любой СМ есть АЗУ, в котором хранятся номера блоков, которые есть в СМ), т.е. обнуляем часть таблицы адресов (с данными не работаем), поэтому процессор обратится к СМ и увидит, что требуемого блока нет и обратится за ним к ОП. Признак недостоверности сохраняется в ОП до тех пор пока данные не будут обновлены (процесс обновления достаточно долгий). 2. Обновление. Если данные изменены, то необходимо посмотреть в справочнике и передать всем «свежие» данные. Это быстрее, но сложнее с точки зрения аппаратуры. 13. ВС с распределенной памятью В данном разделе рассматриваются так называемые крупномасштабные системы с распределенной памятью, т.е. каждый процессор имеет свою локальную память (ЛП)– для того чтобы поддерживать большое количество процессоров приходится распределять основную память между ними, в противном случае полосы пропускания памяти просто может не хватить для удовлетворения запросов, поступающих от очень большого числа процессоров. На рис. 13.1 показана структура такой системы. Для простоты на рис. 13.1 в качестве коммуникационной сети (КС) изображена общая шина. P1 кеш ЛП ... P2 кеш КВВ ЛП КВВ Pn кеш ЛП КВВ КС ЛП КВВ Pm кеш Рис. 13.1 Упрощѐнная схема системы МКМД с распределѐнной памятью В таких системах в рамках одной локальной памяти может находится несколько процессоров, тогда такое образование называется вычислительным узлом системы. Распределение памяти между отдельными узлами системы имеет два главных преимущества. Во-первых, это эффективный с точки зрения стоимости способ увеличения полосы пропускания памяти, поскольку большинство обращений могут выполняться параллельно к локальной памяти в каждом узле. Во-вторых, это уменьшает задержку обращения (время доступа) к локальной памяти. Обычно устройства ввода/вывода, так же как и память, распределяются по узлам. На рис. 13.1 КВВ – контроллер ввода/вывода. Таким образом, каждый вычислительный узел представляет собой отдельный компьютер, поэтому такие системы и называются многомашинными. Поскольку физически адресное пространство распределено по вычислительным узлам доступ к «чужой» памяти осуществляется через механизм передачи сообщений. Основные преимущества обмена с помощью передачи сообщений являются. 68 1. Аппаратура может быть более простой, по сравнению с моделью разделяемой памяти. 2. Модели обмена понятны программистам. Однако, основные трудности возникают при работе с сообщениями, которые могут быть неправильно выровнены и сообщениями произвольной длины в системе памяти, которая обычно ориентирована на передачу выровненных блоков данных, организованных как блоки кэш-памяти. При оценке любого механизма обмена критичными являются три характеристики производительности систем обмена: 1. Полоса пропускания – в идеале полоса пропускания механизма обмена будет ограничена полосами пропускания процессора, памяти и системы межсоединений. 2. Задержка – в идеале задержка должна быть настолько мала, насколько это возможно. Для еѐ определения критичны накладные расходы аппаратуры и программного обеспечения, связанные с инициированием и завершением обмена. 3. Упрятывание задержки – насколько хорошо механизм скрывает задержку путем перекрытия обмена с вычислениями или другими обменами. 14. Постановка задачи назначения Объект исследования – это ВС, которая в одном случае организована как система с общей памятью, а в другом как система с распределенной памятью, и прикладные задачи, которые поступают для решения на вход ВС. Для каждого случая задача назначения должна решаться с учетом характеристик выбранной системы и параметров задач. Предмет исследования – это способ размещения работ (например, вычислений, передач), необходимых при выполнении, поступивших на вход ВС прикладных задач, на выделенные ресурсы ВС. Выбор способа размещения работ получил название «решение задачи назначения». Этой проблеме посвящены лабораторные работы, которым посвящены методические указания. На рис. 14.1 представлены ресурсы ВС, участвующие в выполнении прикладных задач. P – процессор ЛП – локальная память процессора КС – коммутационная сеть МП – модуль оперативной памяти Рис. 14.1 Ресурсы вычислительной системы 70 Множество процессоров – решающее поле. Каждый процессор может обладать своей локальной памятью LM, являющейся элементом единой памяти системы, тогда система определяется как система с распределенной памятью. Либо все процессоры имеют общую память, организованную как автономная оперативная многомодульная память BM. Связь в такой системе между ее компонентами и внешним миром осуществляется с помощью коммутационной сети. Считается, что ВС однородная, т.е. все процессоры и модули памяти одинаковые, причѐм Б1=Б2, т.е. локальная память не вносит задержку в работу процессора. Это важное допущение! Оперативная память в ВС строится по модульному принципу, причѐм число модулей m не превышает число шин (при шинной структуре КС). В ВС с общей памятью (ОП) имеет место единое адресное пространство, обращение к которому осуществляется посредством выполнения команд записи считывания. ОП – это общий ресурс, разделяемый процессорами. В ВС с распределѐнной памятью, в которой имеет место распределѐнное адресное пространство, обмен данными осуществляется с помощью передачи сообщений, поэтому такие ВС иногда называют ВС с сетевой архитектурой. Прикладные задачи – внешняя среда по отношению к ВС. Способ поступления прикладных задач на вход ВС: 1. набор прикладных задач – на вход поступает от 1 до L задач, оформленных в виде пакета; 2. случайный поток задач – на вход поступает одна или несколько задач в случайные моменты времени. 14.1 Модели представления задач Наиболее распространена ярусно-параллельная форма (ЯПФ) представления задач. В этом случае прикладная задача представляется в виде направленного графа, в котором каждая вершина отображает некоторую часть (сегмент) задачи, а дуги – информационные связи между ними. Число ярусов определяет высоту графа, а максимальное число вершин яруса – ширину. Ширина графа влияет на выбор количества процессоров, необходимых для решения данной задачи. Каждая вершина графа взвешивается числом операций, необходимых для выполнения соответствующего сегмента задачи, а дуги объемом данных, передаваемых по соответствующей информационной связи. Это внешние параметры задачи инвариантные относительно вычислительной системы, на которой она будет выполняться. 71 Рис. 14.2 Пример ярусно-параллельной формы Внутренние параметры – это время выполнения сегмента задачи, соответствующего вершине графа, на данном типе процессора – tобр. узла и время передачи данных tпередачи по каналу связи с заданной пропускной способностью, соответствующего дуге графа. На рис. 14.2 изображен граф задачи, состоящий из 4 вершин, номер вершины внутри кружка, сверху кружка цифра, соответствующая времени выполнения данного сегмента задачи в условных единицах, цифра у дуги – время передачи данных в тех же условных единицах. По соотношению времени выполнения сегмента задачи и времени передачи данных задачи можно разделить на: 1. слабосвязные (tобр. узла >> tпередачи); 2. среднесвязные (tобр. узла  tпередачи); 3. сильносвязные (tобр. узла << tпередачи); Постановка задачи назначения в общем виде рассматривается как одна из двух задач оптимизации : 1. при заданных ресурсах ВС (число процессоров, число каналов передачи данных) распределить части прикладных задач по этим ресурсам (рассматривая заданный тип ВС (с общей или распределѐнной памятью) и определенный набор прикладных задач), так, чтобы время решения набора задач (Трешения)min; 2. при заданном (допустимом) времени решения набора задач (Tдоп) распределить части прикладных задач по ресурсам ВС (рассматривая заданный тип ВС (с общей или распределѐнной памятью) и 72 определенный набор прикладных задач) так, чтобы найти минимальные ресурсы, на которых возможно решение задач за допустимое время. Производные показатели: 1. Куск – коэффициент ускорения решения задачи Т К уск  1P , где Т – время решения задачи на одном процессоре, Т 1P nP ТnP – на n процессорах. 2. Кз – коэффициент загрузки оборудования Т обработки Кз  , Tобработки –время, в течении которого данное оборудование Т решения занято выполнением функций при решении задачи (набора задач), Tрешения общее время решения задачи (набора задач). – 14.2 Алгоритм поиска критического пути графа Для оценки минимально возможного времени решения задачи применяется алгоритм поиска критического пути, суть которого заключается в определении минимально возможного и максимально возможного времени начала выполнения узлов графа. При начальном проходе от начальной вершины графа к конечной определяется минимально возможное время начала выполнения каждого узла по формуле: Tmin i = max (Tmin j + tj + Tji) (1) j 1 s – число вершин-предшественников i-ой вершины; Tmin i (j) – минимально возможное время начала выполнения i-ой (j-ой ) вершины; tj – время выполнения j-ой вершины; Tji – время передачи данных между вершинами j и i, которому приписывается одно из значений множества {0, ji, 2ji} в зависимости от способа организации памяти, где ji – время передачи данных между вершинами j и i, задаваемое на исходном графе задачи. При повторном анализе графа при проходе от конечной вершины к начальной определяется максимально возможное время начала выполнения вершины по формуле: Tmin i = min (Tmax r – ti – Tir) (2) r 1 v – число вершин-последователей i-ой вершины; ti – максимально возможное начало выполнения i-ой (r-ой ) вершины; Tir – время передачи данных i-ой вершины вершине r, значение которому присваивается аналогично Tji. 73 При этом для начальной вершины (вершин) Tmin i = 0, а для конечной вершины минимально возможное время начала еѐ выполнения совпадает с максимально возможным временем начала выполнения – Tmax i = Tmin i Вершина является критической, если выполняется равенство: Tmax i = Tmin i Критическим путѐм графа является множество последовательных вершин, начинающихся входной вершиной и заканчивающихся выходной вершиной, у которых Tmax i = Tmin i, в котором для каждой пары вершин графа соотношения (1) и (2) определяются соседней вершиной в паре. Т.е. это такой путь, который имеет максимальное время выполнения среди всех путей графа задачи. И, следовательно, он определяет минимально возможное время выполнения всей задачи при неограниченных ресурсах вычислительной системы, на которой она выполняется. Пример. Определение критического пути. Допустим, каждой вершине графа рис. 14.3 поставлено в соответствие еѐ время выполнения на данном типе процессора в машинных тактах, указанное над вершиной. Тогда, по указанному выше алгоритму, определены минимально (слева от вершины) и максимально (справа от вершины) времена начала соответствующей вершины. 74 Рис. 14.3 Граф задачи Критический путь по определению будет: 1-2-6-9-11-12 Tmin = 23 мт (машинных тактов) - минимально возможное время решения задачи. N Tmax = T j = 48 (N – число вершин графа, т.е. Tmax – время решения j 1 задачи на одном процессоре). Допустим, что необходимо решить задачу за Tдоп =25мт. Для того, чтобы не делать полного перебора при выборе числа процессоров n, определим начальное его значение, необходимое для решения задачи за Tдоп (Tдоп  Tmin, иначе задачу невозможно решить за требуемое время): n = Tmax / Tдоп = 48 / 25  2 75 14.3 Применение стратегий назначения при решении задачи назначения Как назначить готовые к исполнению вершины графа задачи на процессоры? Например, это можно сделать на основе теории расписания, часто прибегая к эвристическим методам, позволяющим найти результат, близкий к оптимальному. Эти методы определяются следующими стратегиями выбора готовых к исполнению вершин и назначения их на свободные процессоры: 1. равновероятный выбор; 2. с максимальным временем исполнения узла; 3. с минимальным временем исполнения узла; 4. на основе принадлежности узла критическому пути. Для автоматического решения задачи назначения граф задачи представляется в виде таблицы связности размерностью NxN, в ячейки которой заносятся признаки связи соответствующих вершин. Будем считать, что на вход многопроцессорной вычислительной системы поступают задачи, относящиеся к классу слабосвязных. Тогда временем передачи данных можно пренебречь. Рассмотрим задачу назначения на основе принадлежности критическому пути, а в случае наличия нескольких готовых к исполнению вершин, не принадлежащих критическому пути, стратегии с минимальным временем выполнения вершины для графа задачи, представленного на рис. На рис. 14.4 представлена диаграмма Ганта, на которой изображены временные диаграммы работы двух процессоров. Рис. 14.4 Диаграмма Ганта В данном случае не уложились в Tдоп =25 мт, следовательно, необходим третий процессор. Изменение стратегии назначения, скорее всего, не поможет, т.к. один процессор занят полностью, а другой вынужден какоето время простаивать. Эмпирически доказано, что чем больше процессоров задействовано в решении задачи, тем больше простаивает каждый из них. Для рассматриваемого случая Tрешения=29 мт, следовательно, Куск = 48/29, Кз первого процессора равен 1 , а второго 19/29.