Использование потоков, конвейеров и перенаправлений в Linux
Операционные системы Unix традиционно используют такие понятия, как стандартный ввод, вывод и вывод ошибки. Чаще всего ввод — это клавиатура, а вывод это на кран. Но конечно же мы можем выводить исполнение какой-то команды в файл и передавать другой команде, потому что работая в Linux, создается такая последовательность из команд, т.е результат предыдущей мы отправляем следующей и т.д
Целью данной статьи является рассмотреть:
- Перенаправление стандартных ввода, вывода и ошибок;
- Передача вывода одной команды в качестве аргументов другой;
- Получение выходных данных в файл и на стандартный вывод;
- Stdin (0) – ввод
- Stdout(1) – вывод
- Stderr (2) – вывод ошибки
- > — передать в
- >> — дописать в
- — взять из
- | — отправить следующей команде
- Tee — отправить в файл и на стандартный вывод
- Xargs – построчно передать на ввод команде
Для начала воспользуемся командой wc которая посчитает, количество слов, символов и строк в файле wc test.txt .
Мы можем указать данной команде другой input . Мы можем ей сказать взять информацию из файла, т.е. записать вот таким образом wc т.е. данной команде передать информацию из этого файла. И данная команда отработав посчитает в принципе то же самое. В таком варианте команда не знает с каким файлом она работает ей просто поступает вывод из файла. Файл выводит свой результат этой команде. Такая стрелочка редко используется, чаще используется стрелка в другую сторону. Например, мы можем список файлов вывести командой ls . А можем сказать, чтобы данная команда отправила результат не на наш стандартный вывод т.к. результат всех наших команд по умолчанию выводится в консоль, а например в файл ls > list.txt . По сути означает выполнить команду, а результат передать в файл. Фал можно посмотреть командой cat list.txt .
И мы можем убедится, что в данном файле находится перечень, всего что находилось в данной папке. Если мы выполним еще раз команду ls > list.txt , то данный файл каждый раз будет перезаписываться. Если же мы хотим, чтобы наш файл не перезаписывался, а дописывался, используем другую стрелочку ls >> list.txt .
И теперь вы можете видеть, что файл стал больше. Т.е. у нас записалось, то что было, а затем еще раз добавилось. Если опять выполнить команду со стрелочками >> , то опять допишется информация в файл. Вот таким образом работают “стрелочки”.
Стандартный вывод ошибок.
Мы можем, например, сказать машине, выведи нам содержимое папки bob , которая не существует ls bob > result.txt , естественно мы получим ошибку которую система вывела на экран. Экран является стандартным выводом ошибок. В нашем случае нет папки bob и нет файла resut.txt . Если мы хотим отправить ошибку в файл, так же как результат выполнения команды, то ls bob 2> result.txt , вспоминаем основные понятия, в которых было указанно, что 2 – это стандартный вывод ошибки.
Следовательно, на экране мы уже не видим ошибки, потому что она отправилась в указанный файл.
Кстати мы можем объединить стандартный вывод команды и стандартный вывод ошибки. Например: ls bob > result.txt 2> error.txt . Выведи содержимое папки bob в файл result.txt , а если возникнет ошибка внеси в файл error.txt .
В таком случае и команда выполнится и что-то будет в файле и если ошибка возникнет, то она будет записана в файл error.txt . Это можно применять на практике, когда мы что-то делаем и предполагаем, что в процессе выполнения возникнут ошибки, то используя данную конструкцию данные ошибки мы все можем отправить в отдельный файл.
Конвейер
Конвейер умеет передавать выходные данные из одной программы, как входные данные для другой. Т.е. выполняется команда, мы получаем результат и передаем эти данные далее на обработку другой программе.
Например, выполнить команду ls и далее мы могли стрелочкой отправлять результаты выполнения команды в файл, т.е. мы меняли только стандартный вывод, а не передавали другой программе. А можем выполнить ls | grep r , т.е. получить содержимое и передать по конвейеру команде сортировки и сказать отсортировать по наличию буквы r , а если перенаправить еще вывод в файл, то cat имя файла , мы сможем увидеть информацию в файле.
Но есть другая команда tee которая позволяет работать немного удобнее. Например: ls | tee output.txt . Те данная команда выводит информацию сразу на экран и в указанный файл. Что достаточно удобно с точки зрения работы с выводами.
И еще одна команда xargs – она построчно работает с выводами. Если у нас есть какая-то команда, которая выдает нам вывод в виде нескольких строк ответа, то мы можем эти строки построчно передавать этой команде, т.е. не одной кашей, а построчно. Например find . –name “*.txt” найти все файлы в текущем каталоге с расширением txt . И если бы мы захотели удалить все эти файлы нам бы пришлось построчно их удалять, но мы можем сказать, чтобы выходные данные были переданы по конвейеру xargs и удалить.
find . –name “*.txt” | xargs rm -f
Как видите после данной конструкции команд файлов не осталось. Т.е. данные построчно передались на команду удаления, которая построчно каждый файл с ключом –f (принудительно) их и удалила.
Командные языки и командные интерпретаторы
Как и в большинстве интерактивных систем, традиционный интерфейс с пользователем ОС UNIX основан на использовании командных языков. Выражаясь несколько тавтологично, можно сказать, что командный язык — это язык, на котором пользователь взаимодействует с системой в интерактивном режиме. Такой язык называется командным, поскольку каждую строку, вводимую с терминала и отправляемую системе, можно рассматривать как команду пользователя по отношению к системе. Одним из достижений ОС UNIX является то, что командные языки этой операционной системы являются хорошо определенными (не очень хороший русский термин, соответствующий совершенно однозначному английскому термину well-defined) и содержат много средств, приближающих их к языкам программирования.
Если рассматривать категорию командных языков с точки зрения общего направления языков взаимодействия человека с компьютером, то они, естественно, относятся к семейству интерпретируемых языков. Коротко охарактеризуем разницу между компилируемыми и интерпретируемыми компьютерными языками. Язык называется компилируемым, если требует, чтобы любая законченная конструкция языка была настолько замкнутой, чтобы обеспечивала возможность изолированной обработки без потребности привлечения дополнительных языковых конструкций. В противном случае понимание языковой конструкции не гарантируется. Житейским примером компилируемого языка является литературный русский язык. Ни один литературный редактор не примет от вас незаконченное сочинение, в котором имеются ссылки на еще не написанные части. Процесс компиляции (литературного редактирования в нашем примере) требует замкнутости языковых конструкций.
Основным преимуществом интерпретируемых языков является то, что в случае их использования программа пишется «инкрементально» (в пошаговом режиме), т.е. человек принимает решение о своем следующем шаге в зависимости от реакции системы на предыдущий шаг. В принципе, предпочтение компилируемых или интерпретируемых языков является предметом личного вкуса конкретного индивидуума (нам известны крупные авторитеты в области программирования — например, Д.Б. Подшивалов,- которые абсолютно уверены, что любая хорошая программа должна быть сначала написана на бумаге и отлажена за столом).
Особенностью командных языков является то, что в большинстве случаев они не используются для программирования в обычном смысле этого слова, хотя на развитом командном языке можно написать любую программу. По нашему мнению, правильным стилем использования командного языка является его применение в основном для непосредственного взаимодействия с системой с привлечением возможностей составления командных файлов (скриптов или сценариев в терминологии ОС UNIX) для экономии повторяющихся рутинных процедур.
Программы, предназначенные для обработки конструкций командных языков, называются командными интерпретаторами. В отличие от компилируемых языков программирования (таких, как Си или Паскаль), для каждого из которых обычно существует много различных компиляторов, командный язык, как правило, неразрывно связан с соответствующим интерпретатором. Когда ниже мы будем говорить о различных представителях командных языков ОС UNIX, относящихся к семейству shell, то каждый раз под одноименным названием мы будем подразумевать и соответствующий интерпретатор.
Командный интерпретатор
Командный интерпретатор, интерпретатор командной строки — компьютерная программа, часть операционной системы, обеспечивающая базовые возможности управления компьютером посредством интерактивного ввода команд через интерфейс командной строки или последовательного исполнения пакетных командных файлов. Как правило его функции сводятся к предоставлению пользователю возможности запускать другие программы, может также содержать некоторые базовые команды ввода-вывода и свой простой скриптовый язык программирования. В операционные системы MS DOS и Windows 95 включен командный интерпретатор command.com, Windows NT включен cmd.exe, в OS/2 командный интерпретатор тоже называется cmd.exe, самый распространенный командный интерпретатор в Linux и FreeBSD — bash, помимо которого есть большое семейство других. Как правило, при низкоуровневой настройке ОС у пользователя есть возможность менять командный интерпретатор, используемый по умолчанию.
К функциям интерпретатора командной строки относятся:
- Взаимодействие с пользователем (редактирование командной строки, история команд и т.д.).
- Обработка (расширение) шаблонов имен («*», «?» и т.д.).
- Перенаправление ввода-вывода команд.
- Управление заданиями.
Программирование в командном интерпретаторе
Зачастую интерпретатор командной строки предоставляет возможность использования циклов, операторов условного и безусловного перехода и переменных. Он позволяет писать как несложные сценарии для автоматизации повседневных задач, так и довольно сложные программы.
Пример калькулятора для интерпретатора командной строки windows/MS-DOS.
@echo off :begin Cls Title Калькулятор Color 71 Echo Введите уравнение: Set /P exp= Set /A result=%exp% Title Вычислено Echo Ваше уравнение: %exp% Echo Решение: %result% Pause>nul goto begin
Калькулятор, для командной оболочки bash:
#!/usr/bin/env bash echo "Калькулятор" while read -p "Введите выражение: " expr do echo "Результат: $(($expr))" done
Оболочка, в своей работе оперирует простыми командами.
Простая команда — это последовательность слов через пробел. Нажатие клавиши Enter при вводе команды или перевод строки при обработке сценария являются для командного интерпретатора признаком завершения команды. Она обрабатывается и выполняется.
Конвейер — это последовательность одной или более команд, разделенных |(& для cmd.exe). Стандартный выходной поток каждой команды, кроме последней, соединяется при помощи программного канала со стандартным входным потоком следующей команды. Каждая команда выполняется как отдельный процесс; интерпретатор ожидает окончания последней команды. Статусом выхода конвейера является статус выхода его последней команды. Вот пример простого конвейера для интерпретатора bash :
$ ls | tee save | wc 15 15 100
Распространенные командные интерпретаторы
command.com Windows:
PowerShell Unix:
Команды и утилиты
Что действительно существенно при интерактивной работе в среде ОС UNIX, это знание и умение пользоваться разнообразными утилитами или внешними командами языка shell. Многие из этих утилит являются не менее сложными программами, чем сам командный интерпретатор (и между прочим, командный интерпретатор языка shell сам является одной из утилит, которую можно вызвать из командной строки). В этом разделе мы коротко обсудим, как устроены внешние команды shell и что нужно сделать, чтобы создать новую внешнюю команду.
Организация команды в ОС UNIX
Вообще-то, для создания новой команды не нужно делать почти ничего специального, нужно просто следовать правилам программирования на языке Си. Как известно, каждая правильно оформленная Си-программа начинает свое выполнение с функции main. Эта «полусистемная» функция обладает стандартным интерфейсом, являющимся основой организации команд, которые можно вызывать в среде shell. Внешние команды выполняются интерпретатором shell с помощью связки системных вызовов fork и одного из вариантов exec (см. п. 2.1.6). В число параметров системного вызова exec входит набор текстовых строк. Этот набор текстовых строк передается на вход функции main запускаемой программы.
Более точно, функция main получает два параметра — argc (число передаваемых текстовых строк) и argv (указатель на массив указателей на текстовые строки). Программа, претендующая на ее использование в качестве команды shell, должна обладать точно определенным внешним интерфейсом (параметры обычно вводятся с терминала) и должна контролировать и правильно разбирать входные параметры.
Кроме того, чтобы соответствовать стилю shell, такая программа не должна сама переопределять файлы, соответствующие стандартному вводу, стандартному выводу и стандартному выводу ошибок. Тогда команде может обычным образом перенаправляться ввод/вывод, и она может включаться в конвейеры.
Перенаправление ввода/вывода и организация конвейера
Как видно из последнего предложения предыдущего пункта, для обеспечения возможностей перенаправления ввода/вывода и организации конвейера при программировании команд не требуется делать ничего специального. Достаточно просто не трогать три начальные дескриптора файлов и правильно работать с этими файлами, а именно, производить вывод в файл с дескриптором stdout, вводить данные из файла stdin и выводить сообщения об ошибках в файл stderror.
Встроенные, библиотечные и пользовательские команды
Встроенные команды представляют собой часть программного кода командного интерпретатора. Они выполняются как подпрограммы интерпретатора, и их невозможно заменить или переопределить. Синтаксис и семантика встроенных команд определены в соответствующем командном языке.
Библиотечные команды составляют часть системного программного обеспечения. Это набор выполняемых программ (утилит), поставляемых вместе с операционной системой. Большинство этих программ (таких как vi, emacs, grep, find, make и т.д.) исключительно полезно на практике, но их рассмотрение находится за пределами этого курса (по поводу редакторов vi и emacs и утилиты поддержки целостности программных файлов make существуют отдельные толстые книги).
Пользовательской командой является любая выполняемая программа, организованная в соответствии с требованиями, изложенными в п. 5.2.2. Таким образом, любой пользователь ОС UNIX может неограниченно расширять репертуар внешних команд своего командного языка (например, можно написать собственный командный интерпретатор).
Программирование на командном языке
Об этом мы уже говорили. Любой из упоминавшихся вариантов языка shell в принципе можно использовать как язык программирования. Среди пользователей ОС UNIX существует много людей, которые пишут на shell вполне серьезные программы. Однако по нашему мнению правильнее использовать shell для того, для чего он изначально предназначен — для непосредственного интерактивного взаимодействия с системой и для создания не очень сложных командных файлов. Для программирования лучше использовать языки программирования (Си, Си++, Паскаль и т.д.), а не командные языки. Хотя оговоримся, что это личное мнение автора, а выбор способа и стиля программирования является сугубо частным делом каждого программиста.
Общая характеристика командных языков
В этом пункте и далее в данном разделе мы будем более конкретно говорить о командных языках семейства shell. Основное назначение этих языков (их разновидностей существует достаточно много, но мы рассмотрим только три наиболее распространенные варианта — Bourne-shell, C-shell и Korn-shell) состоит в том, чтобы предоставить пользователям удобные средства взаимодействия с системой. Что это означает? Языки не даром называются командными. Они предназначены для того, чтобы дать пользователю возможность выполнять команды, предназначенные для исполнения некоторых действий операционной системы. Существует два вида команд.
Собственные команды shell (такие как cd, echo, exec и т.д.) выполняются непосредственно интерпретатором, т.е. их семантика встроена в соответствующий язык. Имена других команд на самом деле являются именами файлов, содержащих выполняемые программы. В случае вызова такой команды интерпретатор командного языка с использованием соответствующих системных вызовов запускает параллельный процесс, в котором выполняется нужная программа. Конечно, смысл действия подобных команд является достаточно условным, поскольку зависит от конкретного наполнения внешних файлов. Тем не менее, в описании каждого языка содержатся и характеристики «внешних команд» (например, find, grep, cc и т.д.) в расчете на то, что здравомыслящие пользователи (и их администраторы) не будут изменять содержимое соответствующих файлов.
Существенным компонентом командного языка являются средства, позволяющие разнообразными способами комбинировать простые команды, образуя на их основе составные команды. В семействе языков shell возможны следующие средства комбинирования. В одной командной строке (важный термин, означающий единицу информационного взаимодействия с командным интерпретатором) можно указать список команд, которые должны выполняться последовательно, или список команд, которые должны выполняться «параллельно» (т.е. независимо одна от другой).
Очень важной особенностью семейства языков shell являются возможности перенаправления ввода/вывода и организации конвейеров команд. Естественно, эти возможности опираются на базовые средства ОС UNIX (см. п. 2.1.8). Кратко напомним, в чем они состоят. Для каждого пользовательского процесса (а внешние команды shell выполняются в рамках отдельных пользовательских процессов) предопределены три выделенных дескриптора файлов: файла стандартного ввода (standard input), файла стандартного вывода (standard output) и файла стандартного вывода сообщений об ошибках (standard error). Хорошим стилем программирования в среде ОС UNIX является такой, при котором любая программа читает свои вводные данные из файла стандартного ввода, а выводит свои результаты и сообщения об ошибках в файлы стандартного вывода и стандартного вывода сообщений об ошибках соответственно. Поскольку любой порожденный процесс «наследует» все открытые файлы своего предка (см. п. 2.1.7), то при программировании команды рекомендуется не задумываться об источнике вводной информации программы, а также конкретном ресурсе, поддерживающим вывод основных сообщений и сообщений об ошибках. Нужно просто пользоваться стандартными файлами, за конкретное определение которых отвечает процесс-предок (заметим, что по умолчанию все три файла соответствуют вводу и выводу на тот терминал, с которого работает пользователь).
Что обеспечивает такая дисциплина работы? Прежде всего возможность создания программ, «нейтральных» по отношению к источнику своих вводных данных и назначению своих выводных данных. Собственно, на этом и основаны принципы перенаправления ввода/вывода и организации конвейера команд. Все очень просто. Если вы пишете в командной строке конструкцию
com1 par1, par2, . parn > file_name ,
то это означает, что для стандартного вывода команды com1 будет использоваться файл с именем file_name. Если вы пишете
то команда com1 будет использовать файл с именем file_name в качестве источника своего стандартного ввода. Если же вы пишете
com1 par1, par2, . parn | com2 par1, par2, . parm ,
то в качестве стандартного ввода команды com2 будет использоваться стандартный вывод команды com1. (Конечно, при организации такого рода «конвейеров» используются программные каналы, см. п. 3.4.4.)
Конвейер представляет собой простое, но исключительно мощное средство языков семейства shell, поскольку позволяет во время работы динамически создавать «комбинированные» команды. Например, указание в одной командной строке последовательности связанных конвейером команд
приведет к тому, что подробное содержимое текущего каталога будет отсортировано по именам файлов в обратном порядке и выдано на экран терминала. Если бы не было возможности комбинирования команд, до для достижения такой возможности потребовалось бы внедрение в программу ls возможностей сортировки.
Последнее, что нам следует обсудить в этом пункте, это существо команд семейства языков shell. Различаются три вида команд. Первая разновидность состоит из команд, встроенных в командный интерпретатор, т.е. составляющих часть его программного кода. Эти команды предопределены в командном языке, и их невозможно изменить без переделки интерпретатора. Команды второго вида — это выполняемые программы ОС UNIX. Обычно они пишутся на языке Си по определенным правилам (см. п. 5.2.1). Такие команды включают стандартные утилиты ОС UNIX, состав которых может быть расширен любым пользователем (если, конечно, он еще способен программировать). Наконец, команды третьего вида (так называемые скрипты языка shell) пишутся на самом языке shell. Это то, что традиционно называлось командным файлом, поскольку на самом деле представляет собой отдельный файл, содержащий последовательность строк в синтаксисе командного языка.
Базовые возможности семейства командных интерпретаторов
Здесь под командным интерпретатором мы будем понимать не соответствующую программу, а отдельный сеанс ее выполнения. Если в случае компилируемых программ следует различать наличие готовой к выполнению программы и факт запуска такой программы, то в случае интерпретируемых программ приходится различать случаи наличия интерпретатора, программы, которая может быть проинтерпретирована, и запуска интерпретатора с предоставлением ему интерпретируемой программы. Основным свойством динамически выполняемой программы (неважно, является ли она предварительно откомпилированной или интерпретируемой) является наличие ее динамического контекста, в частности, набора определенных переменных, содержащих установленные в них значения.
В случае командных интерпретаторов семейства shell имеется два вида динамических контекстов выполнения интерпретируемой программы. Первый вид контекста состоит из предопределенного набора переменных, которые существуют (и обладают значениями) независимо от того, какая программа интерпретируется. В терминологии ОС UNIX этот набор переменных называется окружением или средой сеанса выполнения командной программы. С другой стороны, программа при своем выполнении может определить и установить дополнительные переменные, которые после этого используются точно так же, как и предопределенные переменные. Спецификой командных интерпретаторов семейства shell (связанной с их ориентацией на обеспечение интерфейса с операционной системой) является то, что все переменные shell-программы (сеанса выполнения командного интерпретатора) являются текстовыми, т.е. содержат строки символов.
Любая разновидность языка shell представляет собой развитый компьютерный язык, и объем этого курса не позволяет представить в деталях хотя бы один из них. Однако в следующих подразделах мы постараемся кратко познакомить вас с особенностями трех распространенных вариантов языка shell.
Bourne-shell
Bourne shell (часто sh по имени исполняемого файла) — ранняя командная оболочка UNIX, разработанная Стивеном Борном из Bell Labs и выпущенная в составе 7-го издания операционной системы UNIX (UNIX Version 7). Данная оболочка является де-факто стандартом и доступна почти в любом дистрибутиве *nix. Существует много командных оболочек, основанных (идейно или напрямую) на Bourne shell. Оболочка была разработана в качестве замены для PWB shell, у которой было такое же имя исполняемого файла — sh.
Среди основных bourne-shell задач были следующие:
- Для использования shell script в качестве фильтров.
- Для обеспечения управления порядком выполнения и переменными.
- Управление вводом/выводом, файловыми дескрипторами.
- Управление сигналами в скриптах.
- Снятие ограничений на длину строк при интерпретации скриптов.
- Рационализация и обобщение экранирования строк.
- Переменные среды. Это позволило объявлять переменные, которые будут созданы при запуске и переходят в подпроцессы запускаемых сценариев без того, чтобы использовать явную передачу параметров.
- Пробел — это либо символ пробела, либо символ горизонтальной табуляции.
- Имя — это последовательность букв, цифр или символов подчеркивания, начинающаяся с буквы или подчеркивания.
- Параметр — имя, цифра или один из символов *, @, #, ?, -, $, !.
- Простая команда — последовательность слов, разделенных пробелами. Первое слово простой команды — это ее имя, остальные слова — аргументы команды (имя команды считается ее нулевым аргументом — см. п. 5.2.1).
- Метасимволы. Аргументы команды (которые обычно задают имена файлов) могут содержать специальные символы (метасимволы) «*», «?», а также заключенные в квадратные скобки списки или указанные диапазоны символов. В этом случае заданное текстовое представление параметра называется шаблоном. Указание звездочки означает, что вместо указанного шаблона может использоваться любое имя, в котором звездочка заменена на произвольную текстовую строку. Задание в шаблоне вопросительного знака означает, что в соответствующей позиции может использоваться любой допустимый символ. Наконец, при использовании в шаблоне квадратных скобок для генерации имени используются все указанные в квадратных скобках символы. Команда применяется в цикле для всех осмысленных сгенерированных имен.
- Значение простой команды — это код ее завершения, если команда заканчивается нормально, либо 128 + код ошибки, если завершение команды не нормальное (все значения выдаются в текстовом виде).
- Команда — это либо простая команда, либо одна из управляющих конструкций (специальных встроенных в язык конструкций, предназначенных для организации сложных shell-программ).
- Командная строка — текстовая строка на языке shell.
- shell-процедура (shell-script) — файл с программой, написанной на языке shell.
- Конвейер — последовательность команд, разделенных символом "|". При выполнении конвейера стандартный вывод каждой команды конвейера, кроме последней, направляется на стандартный вход следующей команды. Интерпретатор shell ожидает завершения последней команды конвейера. Код завершения последней команды считается кодом завершения всего конвейера.
- Список — последовательность нескольких конвейеров, соединенных символами ";", "&", "&&", "||", и, может быть, заканчивающаяся символами ";" или "&". Разделитель между конвейерами ";" означает, что требуется последовательное выполнение конвейеров; "&" означает, что конвейеры могут выполняться параллельно. Использование в качестве разделителя символов "&&" (и "||") означает, что следующий конвейер будет выполняться только в том случае, если предыдущий конвейер завершился с кодом завершения "0" (т.е. абсолютно нормально). При организации списка символы ";" и "&" имеют одинаковые приоритеты, меньшие, чем у разделителей "&&" и "||".
- В любой точке программы может быть объявлена (и установлена) переменная с помощью конструкции "имя = значение" (все значения переменных — текстовые). Использование конструкций $имя или $ приводит к подстановке текущего значения переменной в соответствующее слово.
- Предопределенными переменными Bourne-shell, среди прочих, являются следующие:
- HOME - полное имя домашнего каталога текущего пользователя;
- PATH - список имен каталогов, в которых производится поиск команды, при ее указании коротким именем;
- PS1 - основное приглашение shell ко вводу команды;
- Вызов любой команды можно окружить одиночными кавычками (`), и тогда в соответствующую строку будет подставлен результат стандартного вывода этой команды.
- Среди управляющих конструкций языка содержатся следующие: for и while для организации циклов, if для организации ветвлений и case для организации переключателей (естественно, все это специфически приспособлено для работы с текстовыми значениями).
- Аппаратное прогнозирование адреса возврата из вызываемой процедуры
- Конвейерная организация вычислительных систем
- Естественный параллелизм операций в одной задаче
- Модификация машинного языка низкого уровня.
- список требуемых команд микропроцессоров в произвольной их последовательности;
- список объектов для всех операндов: исходных данных, промежуточных и окончательных результатов. Причем поля ссылок в них обязательно должны быть заполнены либо программистом, либо компилятором еще до запуска программы. Непустыми являются только объекты исходных данных, и только в этих объектах теги готовности Cd=1. В объектах промежуточных и окончательных результатов теги готовностиCd=0, и поэтому поля слов данных в них считаются пустыми.
- Ведущий заносит полученный от ведомого процессора адрес готовой команды в файл адресов готовых команд, а затем с учетом приоритета программы выбирает из него один из адресов для обращения в соответствующую рабочую область программы в одном из модулей общей ОП.
- Ведущий считывает из общей ОП код готовой команды и заносит его во второй файл готовых команд, а затем из него с учетом приоритетов выбирается одна из команд и сразу же передается на исполнение в один из свободных ведомых процессоров.
- Соответствующий ведомый микропроцессор выполняет команду: 1) обращается в тот модуль общей ОП, адрес которого соответствует начальной части составного адреса операнда; 2) выбирает из общей ОП готовые операнды команды; 3) вычисляет результат; 4) записывает его по адресу результата.
- Ведомый процессор под управлением резидентной утилиты модифицирует разряды тегов в объекте результата и в командах рабочей области той программы и в том модуле общей ОП, куда он был адресован адресом результата. В объекте результата признак Cd: 0→1 переводится в состояние, а в кодах тех команд, на адреса которых имеются ссылки в объекте результата, теги С1 (или С2): 0→1 для тех операндов последующих команд, в качестве которых используется результат данной команды. Эти модификации тегов могут выполняться как в одном и том же модуле общей ОП, так и в разных в зависимости от адресов, указанных в ссылках. Последние возможно, если обрабатывается совокупность связанных между собой задач.
- Потоковые вычислительные системы
- Двухвходовая операционная вершина- узел с двумя входам и одним выходом.
- Одновходовая операционная вершина- узел с одним входом и одним выходом. Отображает в графе однооперандные команды.
- Вершина ветвления - узел с одним входом и двумя выходами, копирующий входной токен в две выходные дуги.
- Вершина слияния - узел с двумя входами и одним выходом, допускающий копирование в выходную дугу токена из одной входной дуги. Может использоваться входными токенами только в разные моменты времени.
- Вершины управления:
- TF–коммутатор-узел- с двумя входами, один из которых управляющий, и двумя выходами. Если значение управляющей переменной истинно (T-True), то входной токен выводится через левый выход, а если оно ложно (F-False), то через правый выход.
- TиFветили -узлы с двумя входам, один из которых управляющий, и одним выходом. Токен копируется в выходную дугу, если на управляющем входе истинное значение (T):
- Арбитр – узел с двумя входами и двумя выходами. Первые токены поступившие на первый и второйвходы, копируются в левую выходную дугу, а поступившие на любой из входов позже - в правую выходную дугу
- Вершина копирования- узел с одним входом и двумя выходами. Это особая операционная вершина, выполняющая синхронное копирование входного токена одновременно в две выходные дуги. Аналогичны вершине ветвления.
- Уровни параллелизма
- ПротоколMESI
- Особенности архитектурыUMAмультипроцессоров с коммутаторными коммуникационными средствами.
- Организация мультикомпьютеров
- Myrinet2000 используется для поддержания параллельной распределенной обработки сложных прикладных программ. Она выполняет функции межкластерного межсоединения и позволяет организовать общее виртуальное адресное пространство памяти шести ББ «на уровне виртуальной памяти».
- Сеть FastEthernetиспользуется для организации распределенной двухуровневой мультипроцессорной ОС, верхний уровень которой загружается в управляющую ЭВМ (УЭВМ). А нижний уровень распределен по базовым блокам в виде локальных ОС. В этих сетях использована маршрутизация «червоточиной».
- Сеть GigabitEthernetиспользуется для обмена информацией с централизованной базой данных в файл–сервере, а также управляющей и контрольной информацией между распаралленными ОС процессорных блоков нижнего уровня и основной и резервной управляющими ЭВМ верхнего уровня.
- протокол начальной принудительной загрузки задач в КЭШ2 процессоров П1…Пnпод управлением ведущей ЭВМ;
- протокол принудительной дозагрузки очередной задачи под управлением ведущей ЭВМ с приостановкой обмена смежными данными внутри ММММ;
- протокол организации пересылки смежных данных между ПБ с автоматической без участия ведущей ЭВМ догрузкой из ОП и ОПД в КЭШ-2 свободного ПБ требуемой задачи- приемника, если она еще не загружена ни в один ПБ;
- протокол выгрузки из КЭШ-2 процессорных блоков в ОПД конечных результатов задач;
- протокол завершения задачи в ПБ.
- Объяснитеразницу между взаимодействием программ с помощью разделяемой памяти и обмена сообщениями. Опишите преимущества и недостатки обоих вариантов. В каких случаях предпочтительно использование каждого из них?(приведите несколько примеров)
Bourne shell когда-то входил в стандартную комплектацию всех систем Unix, хотя исторически в BSD системах было много сценариев, написанных на csh. Сценарии sh, обычно, могут быть запущены на bash или dash в GNU/Linux или других Unix-подобных системах.
Во многих системах Linux, /bin/sh является символической ссылкой или hard link на bash. Тем не менее, для повышения эффективности, некоторые системы Linux (например, Ubuntu) перенаправляют /bin/sh на dash.
Bourne-shell является наиболее распространенным командным языком (и одновременно командным интерпретатором) системы UNIX. Вот основные определения языка Bourne-shell (конечно, мы приводим неформальные определения, хотя язык обладает вполне формализованным синтаксисом):
C-shell
Командный язык C-shell главным образом отличается от Bourne-shell тем, что его синтаксис приближен к синтаксису языка Си (это, конечно, не означает действительной близости языков). В основном, C-shell включает в себя функциональные возможности Bourne-shell. Если не вдаваться в детали, то реальными отличиями C-shell от Bourne-shell является поддержка протокола (файла истории) и псевдонимов.
В протоколе сохраняются введенные в данном сеансе работы с интерпретатором командные строки. Размер протокола определяется установкой предопределенной переменной history, но последняя введенная командная строка сохраняется всегда. В любом месте текущей командной строки в нее может быть подставлена командная строка (или ее часть) из протокола.
Механизм псевдонимов (alias) позволяет связать с именем полностью (или частично) определенную командную строку и в дальнейшем пользоваться этим именем.
Кроме того, в C-shell по сравнению с Bourne-shell существенно расширен набор предопределенных переменных, а также введены более развитые возможности вычислений (по-прежнему, все значения представляются в текстовой форме).
Korn-shell
Если C-shell является синтаксической вариацией командного языка семейства shell по направлению к языку программирования Си, то Korn-shell - это непосредственный последователь Bourne-shell.
Если не углубляться в синтаксические различия, то Korn-shell обеспечивает те же возможности, что и C-shell, включая использование протокола и псевдонимов.
Реально, если не стремиться использовать командный язык как язык программирования (это возможно, но по мнению автора, неоправданно), то можно пользоваться любым вариантом командного языка, не ощущая их различий.
Знаете ли Вы, что любой разумный человек скажет, что не может быть улыбки без кота и дыма без огня, что-то там, в космосе, должно быть, теплое, излучающее ЭМ-волны, соответствующее температуре 2.7ºК. Действительно, наблюдаемое космическое микроволновое излучение (CMB) есть тепловое излучение частиц эфира, имеющих температуру 2.7ºK. Еще в начале ХХ века великие химики и физики Д. И. Менделеев и Вальтер Нернст предсказали, что такое излучение (температура) должно обнаруживаться в космосе. В 1933 году проф. Эрих Регенер из Штуттгарта с помощью стратосферных зондов измерил эту температуру. Его измерения дали 2.8ºK - практически точное современное значение. Подробнее читайте в FAQ по эфирной физике.
3.1.3.4 Конвейер команд в устройстве управления процессором
Счетчик команд СчК двухбитовый прогноз выполнения или невыполнения перехода (В/Н): сравнение нет да Биты предистории 10 или 11 (00) нет да Апр В:=1 Н:=0 Да: текущая команда является командой условного перехода и прогнозируемый адрес Апр должен использоваться в качестве следующего значения СчК. Следовательно, команда вносится в данный буфер, если при первом ее исполнении переход выполнился. Второй бит прогноза В/Н вносится при повторном прохождении этой же команды перехода. В дальнейшем при многократном прохождении этой же команды возможны следующие переходы кодов состояния битов предыстории В/Н: 10 В 11; 11 В 11; 11 Н 10; 10 Н 00, т.е при каждом правильном прогнозе выполнения перехода предыстория «11» не изменяется, а при каждом неправильном прогнозе - уменьшается на одну из единиц, а при двух подряд неправильных прогнозах по образовавшемуся конечному коду предыстории «00» запрещается нарушение нормального исполнения команд (игнорируется прогнозируемый переход). Нет: текущая команда не является командой перехода. Продолжается нормальное выполнение команд. Вспомним, что и по «да» при коде предистории «00» переход запрещается. Двухбитовый признак прогноза введен для того, чтобы повысить точность предсказания при многократном выполнении одного и того же цикла, например, вложенного цикла при обработке больших массивов данных. Если бы признак был однобитовый, то переходы бита состояния предыстории имели бы вид: 1 В 1, 1 Н 0. это привело бы к тому, что в начале повторного выполнения одного и того же цикла всегда выполнялось бы неправильное прогнозирование условного перехода и терялось бы 4 конвейерного такта, так как при завершении предыдущего выполнения этого же цикла последний прогноз условного перехода был бы всегда неправильным вида: 1 Н 0. Поэтому при повторе цикла даже при «да» в этой схеме переход будет запрещен, хотя в действительности он должен быть выполнен. В то же время при двухбитовой предыстории в конце предыдущего выполнения цикла код состояния предыстории останется разрешающим из-за изменения его состояния следующего вида: 11 Н 10. Данный метод позволяет исключить потерю конвейерного такта , требуемого на первой ступени конвейера для выборки из КЭШ-памяти команд первой команды в направлении перехода по прогнозируемому адресу перехода, если при заполнении буфера в поле прогнозируемого счетчика команд дополнительно записать код названной первой команды, заранее считанной из КЭШа команд. Тогда потери времени работы конвейера в дальнейшем его функционировании можно уменьшить до нуля. Этот способ называется свертыванием переходов (branchfolding). Очевидно, что по этому способу достигается нулевое время выполнения безусловного перехода, если компилятор внесет дополнительный указатель обязательного внесения команд безусловного перехода в данный буфер целевых адресов из буфера предвыборки команд и по пути организации записи в него не только адреса безусловного перехода, но и кода первой команды в направлении перехода.
Как показали статистические исследования на тестовых пакетах программ SPECвозвраты из вызываемых процедур составляют 80-85% общего числа косвенных переходов, т.е. таких переходов, адреса назначения которых меняются в динамике выполнения программ. Компилятор в статике не может обеспечить требуемую высокую точность их предсказания. Рассмотренный выше буфер целевых адресов не обеспечивает требуемой точности прогнозирования, так как одна и та же процедура часто вызывается из нескольких мест программы. Эта трудность преодолена путем введения в процессор небольшого буфера адресов возврата, емкостью до 16-ти элементов, организованного как стек. Запоминаются последние адреса возвратов из процедур. Адрес возврата, который всегда известен в момент вызова процедуры, вталкивается в стек, а во время возврата он извлекается из стека и используется для перехода без прерывания работы конвейера команд. При емкости стека, равной 8-16 ячеек, точность прогноза адресов возврата составляет 94-97%.
Во второй половине и конце прошлого столетия наибольший объем среди производимых во всем мире супер-ЭВМ занимали векторно-конвейерные ВС, в том числе лидерами по производительности и сбыту были параллельные ВС компании Cray(США). Они проблемно ориентировались на решении задач с массовым параллелизмом данных, широко использовались и продолжают использоваться для обработки больших массивов данных с плавающей запятой. Такие массивы представляются матрицами высоких порядков, которые в свою очередь можно представлять и обрабатывать как множества векторов их строк, или столбцов. Например, умножение двух матриц порядка К можно свести к К 2 скалярных произведений пар векторов: вектора-строки Аiматрицы А вектора-столбца Вjматрицы В. Если мы перемножаем две квадратные матрицы А и В размером К х К элементов: С=А*В = [aij][bij], то вместо обработки элементов матриц можно обрабатывать векторы: A1 С= [cij]= . . Ai * [B1…Bj…Bk]=[AiBj], . . Ak где Ai– вектор-строка; Bj– вектор-столбец; М =K 2 – мощность множества элементов. необходимо вычислитьK 2 скалярных произведений двух векторов: Cij = AiBj, i=1,k; j=1,k ускорить вычисления можно в векторно-конвейерном процессоре следующей организации. Векторные регистры Вектор Аi 5 ступеней Вектор Bj из ОЗУ в ОЗУ 5 ступеней конвейер умножителя с п.3. конвейер сумматора с п.3. Векторный регистр – это последовательность многоразрядных регистров, соединенных каскадно параллельными линиями связи и создающих очередь операндов типа FIFO. в них хранятся компоненты векторов в формате чисел с плавающей запятой и потактно продвигаются вправо. На выходе конвейерного умножителя образуется поток парных произведенийaik bkj, следующих друг за другом с конвейерным тактом Тк. Они конвейерное суммируются в 5-тиступенчатом накапливающем конвейерном сумматоре. После того, как все К произведенийaik bkj будут вычислены и последнее из них загрузится в первую ступень сумматора вместе с промежуточной накопленной суммой, поступившей с выхода конвейера сумматора, в нем на разных 5-ти этапах обработки еще будут находиться 5 пар слагаемых. После этого, к сожалению, в конвейере невозможно вычислить конечный скалярный результатCij, а можно лишь образовать пять финальных его составляющих. Для этого требуется выполнить еще 5 тактов накапливающего сложения с нулевыми слагаемыми на выходе. За эти пять тактов завершатся все 5 этапов сложения 5-ти пар слагаемых с плавающей запятой, и в 5-ти регистрах на выходах ступеней конвейера сохранятся 5 составных частей результата. затем еще за 5 тактов путем сдвига их можно выгрузить из сумматора в выходной векторный регистр в виде 5-ти компонентного вектора: Сij= (Cij (1) ,Cij (2) ,…,Cij (5) ). для получения элемента исходной матрицы эти составные части нужно сложить: 5 Cij= ∑Cij ( k ) . (4) k=1 Так как в выходном векторном регистре после обработки К 2 пар векторов (Aj*Bj) накопится массив из К 2 пятикомпонентных векторов , то целесообразно для ускорения вычисления К 2 пятиместных сумм (4) применить далее векторно-конвейерный пятиместный сумматор с плавающей запятой и эквивалентным числом конвейерных ступеней, равном 15-ти. оценим величину ускорения по сравнению с однопроцессорной машиной без конвейеров. Время обращения в ОЗУ не будем учитывать в обоих вариантах, так как при любом подходе все входные операнды нужно считать из ОЗУ, а выходные результаты записать в ОЗУ. Занизим выигрыш, полагая, что время умножения с п.3. равно 5 Тк, и сложения - 5 Тк в однопроцессорной ЭВМ, где Тк – конвейерный такт, т.е. на каждую операцию умножения – накапливающего сложения с п.3. требуется 10Тк, а всего таких операций нужно выполнить К 3 . Скк (1) …С11 (1) Скк (2) …С11 (2) Скк (3) …С11 (3) Скк (5) …С11 (5) С11…С1кк векторные регистры длиной К 2 из ОЗУ -0 - Ускорение процедур умножения матриц составит η = 10 К 3 / (К 2 *(20+К-1)+15+К 2 -1) = 10К 3 / (К 3 +20 К 2 +14)=10 / (1+(20/К)+(14/ К 3 )), где 20-число тактов начальной загрузки (10) и холостых конечных тактов накапливающего конвейерного сумматора (10); 15-число тактов начальной загрузки пятиместного конвейерного сумматора. Следовательно, ускорение в рассмотренных векторно-конвейерных процессорах возможно в десять раз при порядках матриц К>10….100. В супер-ЭВМ Crayускорение умножения матриц дополнительно увеличили за счет параллельного включения нескольких таких конвейерных процессоров. максимально возможное ускорение можно было бы достичь, если все К 2 скалярных произведений выполнять одновременно. Тогда η = 10 К 3 / (19+К+15+ К 2 -1) = 10К / (1+(1/К)+(33/ К 2 )) ≈ 0(К), т.е. пропорционально порядку К матриц при К>10. Однако при массовом параллелизме данных, когда К = 100….1000 сложность системCrayстановится недоступной для реализации. Если же в однопроцессорной ЭВМ применить такие же два блока конвейерного умножения и сложения, выигрыш векторно-конвейерных систем существенно снизится. В связи с этим поучительна модификация их рынка сбыта. Вначале в середине ХХ века они пользовались большим успехом и сбытом. Их закупили у США многие страны. Например, у нас супер-ЭВМ Cray40 лет применялись для обработки суточных данных сотен гидрометереологических станциях при прогнозировании погоды. К концу ХХ века появились суперскалярные микропроцессоры, работающие на тактовой частоте 1 ГГц и имеющие конвейеры команд и арифметические конвейеры. Спрос на супер-ЭВМ Crayначал резко падать, чтобы вернуть рынок сбыта в ВСCrayввели дополнительные методы ускорения. Все функциональные блоки построили в виде конвейеров, затем продублировали конвейеры в каждом функциональном блоке и во много раз увеличили число и длину векторных регистров. Последняя модификация – процедура сцепления векторов, когда выходной вектор результата одного из векторно-конвейерных процессоров системы сразу же использовался как входной вектор другого векторно-конвейерного процессора без промежуточных этапов записи этого вектора в выходной векторный регистр, затем из него – в ОЗУ, а из ОЗУ – во входной векторный регистр другого процессора. Это существенно ускорило последовательные цепи скалярных операций над векторами, например: 1) в первом процессоре скалярное покомпонентное умножение векторовV2=V0ºV1; 2) во втором процессоре скалярное сложение векторовV4=V2 +V3. тогда, соединив выходы конвейерного умножителя сразу же с первым входом конвейерного сумматора во втором процессоре и применив три входных конвейерных регистров и два выходных, за один цикл конвейерной обработки без промежуточного обращения в ОЗУ в выходных регистрах будут получены одновременно два результирующих вектораV2и V4 . Сцепляя таким образом до трех конвейеров, как например в системе пятиместного конвейерного сумматора, удалось повысить производительность до 240MFLOPS. Но сбыт этих дорогих супер - ЭВМ продолжал падать. Тогда компания перешла на выпуск мультикомпьютерных ВС с организацией ядра по топологии решеток: плоской матричной и кубической, в которых, как мы увидим ниже, ускорение матричных операций пропорционально порядку умножаемых матриц, но с меньшими затратами. Самая мощная векторно-конвейерная супер–ЭВМ, созданная корпорацией NECв 2002 году, называлась «Модель Земли» и содержала 640 сложных вычислительных узлов по 8 векторно-конвейерных процессоров в каждом, а всего 5120 таких же векторных процессоров, как описаны выше. Пиковая производительность - 40TFLOPS. Для таких супер-ЭВМ сейчас производится многопроцессорная платформа - векторно-конвейерный микропроцессор 5х-6; построенный на одной пластине, содержащей 57 млн. транзисторов. Он состоит из 8-ми векторно-конвейерных процессоров, в каждом из которых имеется по 5 арифметико-логических конвейеров (сложение, умножение и деление с пл. зап., сдвиг и логические операции), а также одного суперскалярного процессора. Встроены 288-мь 64-х разрядных векторных регистров. Возможно программирование сцепления векторов для совмещения конвейеров умножения и сложения с пл. зап., аналогично описанной выше схеме. Пиковая производительность этой ультрабольшой ИС равна 8 Gflops.
Он характерен для задач обработки многомерной информации: векторной, матричной, графической, текстовой, когда одна и та же операция или подпрограмма обработки многократно повторяется над разными данными. Такой параллелизм операций называется регулярным. Он может рассматриваться и как массовый параллелизм данных. Договоримся считать его параллелизмом операций, если для его использования с целью повышения производительности применяется множество параллельно работающих обрабатывающих устройств. Однако четкой границы здесь нет. Например, рассмотренные выше матричные ассоциативные однородные вычислительные среды в равной степени используют для повышения скорости обработки и параллелизм данных, и параллелизм операций. По-видимому они неотемлины друг от друга. Классический пример задачи с массовым регулярным параллелизмом операций, сопровождаемым также и массовым параллелизмом данных, - это приближенное решение дифференциальных уравнений в частных производных методом сеток (методом конечных разностей). Плоская двухмерная задача Пуассона , гдеF(x,y) задана, а определяется (x,y)=? при заданных граничных условиях 2=f(L), гдеL[y=(x)] –уравнение контура границы области определения, внутри которой ищутся значения, сводиться к системе линейных алгоритмических уравнений высокого порядка где -шаги декартовой сетки квантования непрерывной области определения по осямxиyсоответственно; -номер узла двумерной сетки (решетки) квантования; - дискретные значения искомой функции двух переменных, определяемые только в узлах сетки. Требуется решать систему уравнений высокого порядка N(n+1) (m+1). Например, для достижения принципиальной (методической) погрешности решения δn3% необходимо решить систему с порядком: N≈(n+1) (m+1)1000. Так как уравнения во всех ik-хNузлах одинаковы, то ускорить решение такой системы высокого порядка можно на основе следующего параллельно-последовательного итеративного алгоритма последовательных приближений. Поставим в соответствие всем ik-м узлам сеткиNодинаковых параллельно работающих обрабатывающих устройств (ОУ), одновременно вычисляющих всев каждомj-м шаге итерации по известным значениям в четырех соседних узлах сетки, найденным в предыдущем (j-1)-ом шаге итерации: при условии сходимости итеративного процесса , где ∆м- абсолютно допустимая и методически достижимая погрешность решения, например при N=1000: ∆м≈0,03 . Каждый j-й шаг итерации начинается с передачи в каждоеik-е ОУ из четырех соседних ОУ старых значений, вычисленных в предыдущем шаге. Затем во всехNОУ одновременно и синхронно выполняются одинаковые последовательности командных циклов для вычисления множества новых значений > и проверки условий сходимости. Признаки выполнения последних со всех узловых ОУ передаются в общее устройство управления или в ведущую ЭВМ. Если хотя бы в одном изNузлов сетки условие сходимости не выполняется инициализируется следующий аналогичный шаг итерации и так далее до выполнения условий сходимости во всехNузловых ОУ. Для выполнения такого параллельно-последовательного процесса обработки множества данных вполне подходит структурная организация параллельной ВС в виде матрицы однотипных ОУ с близкодействием (решетки), в которой ОУ обмениваются данными только с четырьмя ближайшими соседями. Все ОУ синхронно в командном цикле выполняют одну и тоже команду, подавляемую в ОУ из общего устройства управления. В другом командном цикле матрица может выполнять другой тип команды, но одинаковый во всех ОУ. Такой метод управления называетсяSIMD(OKMD) или общим управлением. Если некоторые ОУ матрицы должны пропустить выполнение очередной команды, то общее УУ (контроллер) массива ОУ запрещает их работу. Поэтому командный цикл начинается с передачи во все ОУ кода операции и признака (флага) маскирования. Матрица признака маскирования ОУ обычно видоизменяется от одного командного цикла матрицы ОУ к другому. Все эти матрицы маскирования ОУ, прилагаемые к каждой команде параллельной программыSIMDсистемы, либо заранее в статике создаются компиляторами, либо модифицируются в динамике исполнения программы общим контроллером массива ОУ в результате анализа признаков, образуемых в ОУ. Такой принцип маскирования называется глобальным маскированием. В качестве ОУ могут использоваться любые вычислительные устройства: от простых специализированных, ориентированных на одну конкретную задачу, до программируемых одноразрядных процессоров с сокращенным набором команд или даже многоразрядных микро-ЭВМ со встроенной кэш-памятью или локальной оперативной памятью. Второй пример часто решаемой задачи с регулярным параллелизмом операций - это умножение двух квадратных матриц размером nn: В матричной ВС с общим управлением умножение матриц выполняется за шагов, а не закомандных циклов, требуемых в однопроцессорной ЭВМ. Ускорение пропорционально порядку матриц:=O(n). Заметим, что это ускорение при больших порядках матриц выше, чем в векторно-конвейерных ВС. Поэтому сейчас в США перешли к производству супер-ЭВМCrayT3Eс матричной ориентацией типа мультикомпьютерных ВС с топологией в виде объемной решетки. Параллельно-последовательный вычислительный процесс умножения матриц выполняется за nодинаковых циклов поnшагов в каждом. Цикл начинается с загрузки во всепроцессоров решетки очередного столбца матрицыBпо принципу - столбец во все строки с повторением. Элементы матрицы А загружаются в решеткуnnстроками еще до начала вычислений. В первом шаге цикла всепроцессоров синхронно выполняют одну и тоже команду умножения двух чисел. За оставшиеся (n-1) шагов цикла в решетке выполняется последовательная свертка произведений путем накапливающегоn-местного суммирования одновременно в каждом из строк решетки. Каждый шаг такого суммирования выполняется путем передачи столбца промежуточных сумм в следующий столбец процессоров и выполнение в них одновременно и параллельноnнакапливающих сложений. Остальныеn(n-1) процессоров решетки маскируются. В результате за (n-1) таких шагов в последнем столбце решетки процессоров образуется одна строка элементов результирующей матрицы. Очевидно, что матрицы процессоров в (n-1) шагах используется недостаточно эффективно - только один столбец процессоров в каждом шаге, т.е. имеется еще большой резерв ресурсов для повышения степени ускорения. Регулярный параллелизм – это только один из видов естественного параллелизма операций. В преобладающем большинстве задач встречается другой его вид – нерегулярный параллелизм операций, когда над разными данными возможно одновременное выполнение разных типов операций. Он встречается даже при решении квадратного уравнения: Ax²+Bx+C=0 С дискриминантом D=B²-4AC. Для анализа параллелизма операций применяют специальный графический документ, который называется граф операндов (граф передачи данных - ГПД, потоковый граф, граф потоков данных), вершины которого соответствуют обозначением необходимых операций или команд ЭВМ, а направленные дуги - направлениям передачи данных (операндов) между операциями или командами. Для квадратного уравнения граф операндов имеет следующий вид с учетом знака дискриминанта D. На графе - обозначение дополнительной операции «вентиль», которая при истинном значении на управляющем входе копирует входное данное на свой выход; - обозначение изменения знака на обратный. В зависимости от знака дискриминанта выполняется либо левый подграф ниже вентиля для вычисления действительных корней уравнения, либо правый подграф ниже вентиля для вычисления комплексных корней с действительной и мнимой частями. Три операции в Iслое и по две операции воIIиIIIслоях графа могли бы выполняться параллельно одновременно, если бы в составе АЛУ процессора ЭВМ имелся избыток соответствующих операционных блоков. Как показано выше, существенное ускорение вычислений при регулярном параллелизме операций возможно при матричной организации ВС с общим управлением по принципу SIMD(OKMD). В общем случае чаще встречающегося нерегулярного параллелизма операций более подходящим способом ускорения вычислений считается переход к потоковой организации процессоров, ЭВМ и систем. Если в традиционных фон Неймановских ЭВМ программное управление вычислениями выполняется последовательностью команд, определяемой алгоритмом, то в потоковых ЭВМ программное управление выполняется данными (потоком данных) по степени готовности операндов команд. Определяемой не алгоритмом, а графом операндов. Если в машинах фон Неймана команды вызывают из памяти требуемые данные, то в потоковых ЭВМ готовые данные вызывают из памяти команды, требуемые для их обработки в соответствие с хранимым в памяти закодированным графом операндов. Потоковый принцип программного управления позволяет существенно упростить организацию параллельных вычислений. Если в параллельной ЭВМ или системе имеется достаточный избыток обрабатывающих устройств или ансамбль микропроцессоров, то естественно без трудоемких планирования и диспетчеризации параллельных процессов могут одновременно выполняться те параллельные операции, операнды которых уже подготовлены предыдущими вычислениями. Причем асинхронный принцип загрузки операций или задач в ОУ или процессоры соблюдается автоматически. Для этого достаточно к полю ОУ или процессоров создать очередь готовых команд, вызванных их готовыми операндами, и в первое же освободившиеся ОУ сразу же передавать на обработку готовую команду из очереди. Например, при решение задачи нахождения корней квадратного уравнения вычислительный процесс автоматически назначается с параллельного вычисления трех операций Iслоя графа операндов, входными операндами которых являются готовые заранее исходные данные задачи. Далее процесс развивается по мере готовности операндов. На последовательной ветви вызывается из памяти команда умножения, затем вычитания, проверки логического условия. После перехода вызывается макрооператори лишь после этого- одновременно две команды второго слоя, а затем- две команды деления. В потоковых ЭВМ практически исключается необходимость создания сложной системы организации прерываний программ. Потоковые программы автоматически приостанавливаются, если нет готовых операндов для вызова следующих (по графу операндов) команд, и автоматически запускаются как только операнды будут готовы. В потоковых многопроцессорных многозадачных ВС появилась очень важная возможность выравнивания и повышения степени загрузки множества процессоров, если удачно подобрать смесь задач так, чтобы, когда некоторые задачи выходят на последовательные ветви своих графов операндов, другие задачи выходили бы на слои своих графов операндов с естественным параллелизмом операций. Поэтому сейчас в мультикомпьютерах переходят к макропотоковому параллельному программированию обработки разбитых на фрагментные подзадачи сложных задач. В настоящее время техническая реализация потоковой организации ВС осуществляется следующими способами. 1. Создание последовательных потоковых микропроцессоров с одним АЛУ, которые относятся к классу специализированных и будут изучены в следующем семестре. 2. Создание процессоров с избытком однотипных операционных блоков и дополнение операционных систем потоковым способом организации вычислительных процессов (реализовано в отечественной супер-ЭВМ Эльбрус-2) 3. Специальная функциональная организация вычислительного процесса и модификация машинного языка низкого уровня в мультипроцессорных ансамблевых ВС, построенных на типовых микропроцессорах фон Неймана (английская система LAU-63). 4. Создание потоковых ВС, отключающихся от фон Неймановских ВС по архитектуре, структурной и функциональной организации. 5. Построение современных микропроцессоров на основе суперскалярной и мультискалярной архитектуры, в которой потоковый принцип параллельной обработки команд на нескольких параллельных ОУ реализуется блоком управления процессором без изменения традиционных последовательных языков программирования. 3.1.4.1 Функциональная организация потоковой ансамблевой мультимикропроцессорной ВС Потоковая ВС может быть построена на основе ансамблевой структурной организации параллельной системы, рассмотренной ранее. Однако для реализации в ней потокового принципа программирования по степени готовности операндов необходимо изменить функциональную организацию по сравнению с ЭВМ фон Неймана. Рассмотрим, в чем состоит эта модификация на примере английской потоковой ВС, ансамбль которой построен на 63-х микропроцессорах фон Неймана. Для ускорения вычислений за счет естественного параллелизма операций (команд) применены следующие изменения в функциональной организации.
Незначительно изменен формат команды путем дополнения его коротким управляющим словом- тегом, являющимся признаком готовности и состоящем из трех бит С0, С1, С2. С1=1 –признак готовности операнда 1. С2=1 –признак готовности операнда 2. С0=1 –признак активизации команды, указывающий, что ее адрес после того, как С1=1 и С2=1, помещен в файл адресов готовых команд; т.е. признак того, что готовые данные вызывают эту команду из памяти на свою обработку. Слово данных преобразуется в объект и храниться в памяти в формате объекта данных по адресу операнда или результата команды Тег Cd–это признак готовности данного, находящегося в первом поле записи: Cd=0-поле слова данного пустое; Cd=1-поле слова данного не пустое, т.е. операнд в этом объекте готов к обработке. «Ссылка» -это адрес команды, для которой слово данных этого объекта являются одним из двух операндов, а каким именно: первым или вторым указывает значения однобитового тега перед ссылкой: «1»-операнд 1; «0» -операнд 2. Этот принцип функциональной организации потоковых вычислений называется метод ссылок и тегирования. Известны еще несколько методов: 1) в потоковых микропроцессорах применяется метод меток; 2) в потоковых ВС со специальной архитектурой применяются методы помеченных токенов и явно адресуемых токенов. Потоковая программа ВС LAU-63–это два списка кодов:
2. Модификация способа хранения рабочей области программы в памяти и взаимодействия процессоров с модулями общей памяти. Рабочая область прикладной программы создается в одном из модулей общей памяти и хранится в виде названных выше двух списков команд и объектов, в которых в динамике исполнения изменяется содержимое полей слов данных и тегов объектов и команд. Система обычно эксплуатируется в многозадачном режиме. Если задачи независимые, то названные изменения по каждой из задач локализуется в пределах одного модуля памяти. Если задачи связаны между собой, то по адресу результата выполненной пограничной команды обрабатывающей процессор обращается в любой из модулей памяти, записывает полученный результат в адресуемый объект, устанавливает его тег Cdв состояние готовности и во всех командах, на которые имеется ссылки в этом объекте устанавливает тегC1 или тегC2 в состояние готовности. Если ссылка адресует в другой модуль памяти, то процессор должен обратиться и в него, найти адресуемую команду и модифицировать и ее тегC1 илиC2. Только после этого считается, что данная команда исполнена. Управление вычислительными процессами организуется по принципу «ведущий-ведомый». Один из процессоров системы при начальной загрузки ядра ОС назначается ведущим. За ним закрепляется один из модулей общей памяти, который называется управляющей памятью. В ней по каждой из параллельно выполняемых в системы потоковых программ хранится очередь готовых команд в виде двух файлов: 1) файл адресов готовых команд (очередь к модулям общей памяти для считывания из нее кодов готовых команд. 2) файл готовых команд (очередь к ансамблю процессоров на исполнение). Названные две очереди в многозадачном режиме являются общими для всех обрабатываемых прикладных программ. Вторую очередь ведущий процессор формирует самостоятельно, считывая коды команд из общей памяти по адресам, хранящимся в файле адресов готовых команд. Адреса готовых команд поступают в первую очередь в результате сеансов связи ведомых процессоров с ведущим. Как только в рабочей области в каком – либо модуле памяти при очередном просмотре списка команд в ходе модификации тегов какой-нибудь ведомый процессор обнаружит одну или несколько команд, теги которых С1=1 и С2=1, то он инициализирует соответствующий вектор прерывания ведущего, и после его подтверждения пересылает ему адрес готовой команды, а в теге готовой команды устанавливает признак С0=1 ее активизации. Это необходимо, чтобы при следующем просмотре списка команд не выполнять повторно процедуру вызова этой же команды. Ведомый обрабатывающий процессор не закрепляется за одним определенным модулем ОПiобщей ОП, а выполняет только те готовые команды, которые передает ему ведущий, отыскивая требуемые модули памяти по адресам уже готовых операндов или по адресу ячейки объекта, запланированного программистом для записи результата. Любой освободившийся ведомый процессор сразу же загружается новой готовой командой из очереди готовых команд. Причем эта команда может оказаться из другой параллельной обрабатываемой программы, а не из той, которую он обрабатывал в предыдущем командном цикле. Такой способ организации обеспечивает соблюдение принципа независимости между программами и процессорами. Он реализован в LAU-63 благодаря тому, что ведущий процессор распределяет между процессорами не задачи, а команды. Конечно это привело к увеличению числа сеансов связи с ведомыми. Однако эти дополнительные системные затраты машинного времени окупаются при большом числе совместно обрабатываемых потоковых программ, так как появляется возможность выровнять и повысить степень загрузки процессоров и, в конечном итоге, скомпенсировать эти потери за счет повышения производительности системы. Действительно, если несколько процессоров выходят на последовательные линейные участки потоковых программ (закодированных графов операндов), где не возможно распараллеливание операций, а в одном или нескольких оставшихся процессоров образуется сразу несколько готовых команд, то ведущий процессор сразу же загружает их на параллельную обработку в несколько сводных процессоров. Кроме этого данный принцип независимости существенно упрощает рестарт системы при отказе процессора. Ведущий процессор в управляющей памяти хранит таблицу физических номеров исправных процессоров. При отказе ведомого, или предотказовой ситуации по возрастающей частоте его сбоев, он отключается от внутрисистемного интерфейса, а его номер вычеркивается из системной таблицы. Конечно, из-за уменьшения числа процессоров очередь готовых команд возрастает, но система будет работоспособна при любом числе исправных процессоров вплоть до одного. В каждый ведомый процессор (в его локальную память или в ПЗУ) предварительно загружается простейшая резидентная утилита, которая управляет модификацией тегов в модулях общей памяти в каждом командном цикле. Командный цикл в системе LAU-63 выполняется за четыре шага, первые два из которых выполняется ведущим процессором, а последние два ведомыми.
Сразу же при модификации тега С1 (или С2) проверяется, не равны ли «1» оба тега, т.е. С1=1 и С2=1. Адреса таких готовых команд запоминаются в регистрах процессора, а их теги С0 : 0→1 переводятся в состояние: «команда активизирована». По окончании обработки всех ссылок из объекта результата данной команды, если имеются готовые команды, процессор выставляет ведущему соответствующий вектор прерываний, и после его подтверждения пересылает ему адреса готовых команд из своих регистров. Очевидно, что третий и четвертый шаги могут одновременно и параллельно исполнять несколько ведомых процессоров над разными командами (с небольшими относительным сдвигами повремени начала третьего шага, необходимыми для передачи очередной готовой команды из ведущего в любой свободный ведомый). Причем, чем выше степень связности обрабатываемых задач, тем выше вероятность возникновения конфликта между процессорам и из-за одновременного обращения в одни те же модули памяти. Они успешно разрешаются только очередями запросов на входах в модули памяти (без синхропримитивов). Но из-за ожидания в очередях производительность с повышением степени связности задач может существенно снизиться. 3.1.4.2 Матричные ВС с общим управлением Как известно матричная организация обрабатывающего ядра системы с общим управлением типа SIMD(OKMD) позволяет повысить производительности при массовом регулярном параллелизме и операций, и данных. Поэтому в прошлом веке производился ряд таких ВС:MP-1 (MasPar),CM-2,STARAN,ILLIACIVв США; ПС-1, ПС-2, ПС-3 у нас в стране (ПС - параллельные системы). Топология связей в ядре - решетка или решетчато– тороидальная. Основное их назначение-обработка больших массивов данных. Обрабатывающее ядро – матричный процессор, состоящий из регулярного однородного массива процессорных элементов (ПЭ), в качестве которых в названных типах ВС использовались сравнительно простые микро-ЭВМ: от одноразрядных с 64-мя Кбит локальной памяти до четырехразрядных с 64-мя Кбайтами локальной памяти и с четырьмя последовательными портами ввода-вывода для соединения друг с другом в решетку (матрицу). В последних моделях матричных ВС типа МР-2 качестве ПЭ применены СБИС 32-х разрядных процессоров с 256 Кбайтами локальной памяти. Принцип функционирования таких матриц ПЭ при одиночном потоке команд и множественном потоке данных с применением глобального маскирования массива процессоров мы рассмотрели ранее (п.3.1.4) Изучим особенности архитектуры матричной ВС в целом. Структура матричной SIMD-системы ШР - шина результатов ШШВР - шина широковещательной рассылки. Интерфейсная ВМ (ИВМ)- это серийная однопроцессорная ЭВМ фон Неймана, работающая под управлением операционной системы UNIX. Она используется для подготовки, компилирования и отладки программ параллельной обработки массивов данных в матричном ядре (массиве процессоров). Откомпилированные программы ядра вначале загружаются в память контроллера массива процессоров (КМП). КМП - это специализированная ЭВМ, которая организует выполнение параллельной программы в массиве процессоров (МП), по шине ШШВР передает и распределяет команды и данные по процессорам МП, выполняет глобальное маскирование процессоров МП; по шине ШР считывает результаты, необходимые для организации условных переходов; реализует безусловные переходы. Структура контроллера массива процессоров (КМП) КМП содержит два ОЗУ: 1) ОЗУ КМП, где хранится последовательная программа исполнения последовательных шагов обработки массива данных в матрице ПЭ; 2) ОЗУ КГМ, где хранятся команды параллельной обработки данных в массиве ПЭ, каждая из которых соответствует одному шагу вычислительного процесса, задаваемому центральным процессором (ЦП) КМП по программе, хранимой в ОЗУ КГМ. Каждая из команд в ОЗУ КГМ сопровождается индивидуальным кодом маскирования ПЭ, не используемым кодом маскирования ПЭ, не используемых на данном шаге работы массива ПЭ. Содержимое обоих ОЗУ заготавливается компилятором в ИВМ и загружается ею в КГМ через интерфейс Вв-Выв. КГМ. В динамике исполнения программы ЦП -ра, считываемой из ОЗУ КМП, он в каждом шаге работы массива ПЭ получает от них статусную информацию, собираемую в единое слово и передаваемую по шине результата. Она используется для вычисления предикатов условных переходов при исполнении ЦП -ом организующей последовательной программы. Если вспомнить приведенный выше пример последовательно-параллельного итеративного решения дифференциальных уравнений в частных производных методом сеток, то в качестве такой статусной информации будут признаки проверки условий сходимости, одновременно выполняемой во всех параллельных ПЭ. Они могут быть в массиве ПЭ объединены по ИЛИ, а результирующий бит может передаваться по шине результата в ЦП. Пока этот бит будет иметь значение «1» итеративные шаги параллельных вычислений в массиве ПЭ будут повторяться под управлением ЦП до тех пор, когда он примет значение «0». После этого по программе, хранимой в ОЗУ КМП, ЦП инициализирует передачу из ОЗУ КГМ в массив ПЭ последовательности команд вывода результатов через системный интерфейс вв.-выв. во внешнее запоминающее устройство или на печать. Так как конечный результат вычислений - это массив слов, каждое из которых сохраняется в одном ПЭ, то процедура вывода разворачивается под управлением ЦП в сеанс последовательного опроса всех ПЭ матрицы. Для этого в ОЗУ КГМ нужно хранить массив глобальных масок и последовательно их передавать в матрицу ПЭ, маскируя в каждом шаге все ПЭ кроме того одного, содержимое слово которого по системной шине вв.-выв. в этом шаге будет направлено в ВЗУ или на печать. Таких последовательных шагов опроса матрицы ПЭ нужно выполнять столько, сколько слов содержится в массиве конечных результатов, т.е. в пределе столько, сколько ПЭ содержится в матрице. Точно также по системной шине ввода-вывода можно из ВЗУ во все ПЭ матрицы загрузить новый массив исходных данных, а через интерфейс вв.-выв. КМП в ОЗУ КМП и ОЗУ КГМ - две составляющие программы их обработки, заранее откомпилированной ИВМ и сохраненной ею в ВЗУ. Следовательно, в массиве ПЭ кроме линий связи их межсоединений должны быть проложены три дополнительные общие шины: 1) шина результата; 2) ШШВР команд и битов маскирования; 3) системная шина вв.-выв., соединенная с системным инт-сом вв.-выв. всей ВС. Схема прокладки связей и шин в массиве процессоров Кроме глобального маскирования ПЭ с помощью масок, передаваемых из КМП по ШШВР и сопровождающих маскируемую команду параллельной обработки, возможно также локальное маскирование ПЭ в динамике выполнения параллельной программы (маскирование, определяемое данными). Для этого в каждом ПЭ имеется триггер, в котором ПЭ может самостоятельно установить флаг Fразрешения маскирования. Для работы с этими флагами в системе команд параллельной обработки предусмотрены два типа команд: маскируемые и немаскируемые. Маскируемые команды выполняются в зависимости от состояния флагаFв ПЭ, а немаскируемые флагFигнорируют. Рассмотрим как используется локальное маскирование на примере выполнения процедуры параллельного ветвления: IF(x0)THEN< операторA>ELSE, где х - локальная переменная, хранящаяся в локальной памяти каждого ПЭ. Каждый ПЭ параллельно с другими ПЭ оценивает условие IF. Те ПЭ, в которыхx0 справедливо установят свои флагиFв состояние «1», а остальные ПЭ, в которыхx0,-в состояние «0». Далее КМП широковещательно распределит одинаковый оператор А по всем ПЭ матрицы. Все команды, реализующие этот оператор в ПЭ, должны быть маскируемыми. Тогда оператор А будет выполнен только теми ПЭ матрицы, гдеF=1. Затем КМП передает во все ПЭ немаскируемую команду ELSE, по которой все ПЭ инвертируют состояния всех флагов. В завершение КМП всем ПЭ передаст оператор В, который реализуется только маскируемым и командами. Следовательно, оператор В будет выполнен другой частью ПЭ -ов, в которых , т.е. в которых переменная х поIF…ELSEбыла в состоянии «иначе»: неx0, аx0.. Глобальное и локальное маскирование может использоваться одновременно. Тогда активность ПЭ в равной мере определяется и локальным флагом F, и глобальной маской. Обмен информацией между ПЭ в пределах матрицы управляется специальными командами, поступающими по ШШВР из КМП. Имеются командами: 1) передать результат всем соседям: 2) передать результат только одному соседу (либо левому, либо верхнему, либо нижнему, либо правому); по этой команде организуется множество параллельных синхронных конвейеров; 3) имеется многотактная многокомандная процедура (подпрограмма) организации передачи данных от нескольких ПЭ- источников к одному ПЭ- приемнику. С помощью этих команд организуются любые последовательно-параллельные SIMDпроцедуры, в том числе пирамидальные свертки.
В п.3.1.4.1 был рассмотрен метод организации потоковой обработки по степени готовности данных, основанный на модификации функциональной организации путем введения в машинный язык ссылок и тегирования, но без изменения структурной организации многопроцессорных систем фон Неймана. Степень загрузки процессоров и производительность ВС можно повысить, если ее структурную организацию приспособить к специфике механизма программного управления данными, иными словами – архитектуру ВС полностью переориентировать на потоковое программирование, в том числе - языки высокого уровня. Программа, состоящая из команд и хранящаяся в памяти, может исполняться по следующим альтернативным механизмам программного управления: – команда выполняется после того, как выполнена предыдущая команда последовательности, а для своего исполнения вызывает операнды из памяти; - команда выполняется, когда готовы ее операнды, которые для своей обработки вызывают из памяти требуемую по программе команду; - команда выполняется, когда ее результат требуется по программе другой команде (или другим командам), т.е. она вызывается из памяти другой командой (запрашивается). Первый механизм-это программное управление последовательностью команд, задаваемой счетчиком команд. Применяется в ЭВМ архитектуры фон Неймана и иногда называется декларативным. Второй механизм- это программное управление данными (потоком данных) по степени их готовности. Применяется в потоковых ЭВМ и системах. Третий механизм-это программное управление по запросу. Применяется в новых редукционных ЭВМ и системах, а также в Пролог - машинах, осуществляющих четкие логические выводы или доказательства логической выводимости. В последних вызывающая запрашивающая команда называется вызывающей процедурой, а требуемая ей для подготовки ее операндов запрашиваемая команда называется вызываемой процедурой. Пролог - машины мы рассмотрим в следующей дисциплине, а в данной ознакомимся с идеей организации редукционных ЭВМ, как развитием потоковых машин. Установим коренные отличия между этими тремя механизмами на примере обработки произвольного графа операндов. В потоковой модели вычислительный параллелизм выявляется автоматически по степени готовности операндов. Поэтому в потоковой многопроцессорной ВС данная задача решается параллельно-последовательно за семь командных циклов, а в однопроцессорной ЭВМ фон Неймана- за 18 циклов. Причем при декларативном управлении необходимо граф преобразовать в алгоритмическую последовательность команд с учетом заготовки операндов последующих команд их предшественниками при последовательном обходе всех узлов графа. При потоковой обработке верхние команды графа вызываются исходными данными раньше, чем нижние - промежуточными результатами исполненных верхних команд. При управлении вычислениями по запросу обработка начинается с запроса результата. Так, как он является результатом финишной команды, то, вызвав ее, процессор по адресам ее операндов вызывает те команды, где они являются результатами, а те в свою очередь запрашивают команды, результатами которых являются требуемые им операнды, и так далее образуется дерево запросов с корнем в конечном результате и с листьями на исходных данных. Это дерево-это тот же граф операндов, но в отличие от потокового механизма в запросном механизме этот граф проверяетсяне сверху вниз от листьев к корню, а снизу вверх от корня к листьям. Вызовы новых команд прекращаются вверху на листьях по признакам готовности операндов. Далее обработка вызванных команд выполняется в обратном порядке от листьев к корню. При этом возможна организация их быстрой параллельной обработки, если в процессе первого этапа запросов и вызов команд распределить их по кэш-памятям нескольких процессоров с учетом их расположения на параллельных ярусах графа операндов. Тогда во втором этапе повторный вызов команд из основной памяти не потребуется, так как они уже будут находиться в быстродействующей сверхоперативной памяти процессора, а обработка данных этими командами может выполняться по потоковому принципу, загружая в процессоры готовые команды по мере подготовки их операндов. Рассмотрим основы архитектуры ВС с управлением вычислениями от потока данных. Вычислительная модель потоковой обработки, положенная в основу архитектуры потоковых ВС, разработанных в США в 1970-2000 г.г., оперирует усовершенствованным графом операндом (dataflowgraph– граф потоков данных, потоковый граф) и понятием токен, аналогичном фишке в сетях Петри. Токен (маркер доступа)- это информационный кадр, содержащий в себе операнд и перемещающийся по дуге потокового графа между его узлами. Вершина (узел) потокового графа активируется только тогда, когда на всех ее входных дугах присутствуют токены, а ее выходнойтокенуже востребованпоследующей вершиной (вершинами). Для полного описания потоковыми графами разнообразных вычислительных процессов введен ряд вершин-примитивов следующих типов с числом входов-выходов не более двух.
Отображает в графе двухместные операции.
или альтернативно-ложное значение (F):
Введение этих вершин – примитивов позволяет имитировать в потоковом графе не только исполнение команд условного перехода, как это было показано ранее на примере вычисления корней квадратного уравнения, но и программные циклы, например с индексными переменными, увеличиваемыми после каждого прохода тела цикла до заданного передела N. Установленный выше принцип активирования вершин и передачи токена от узла к узлу с обязательным освобождением выходной дуги от выходного токена узла перед его активированием входными токенами аналогичен принципу действия буферных регистров –защелок между ступенями конвейера. Это позволяет в таких потоковых ВС организовать параллельно-конвейерную обработку потока исходных входных данных. После обработки первым (верхним) параллельным ярусом команд первого набора исходных данных и активирования второго яруса. Т.е. освобождения от токенов выходных дуг вершин первого яруса, можно конвейерно повторно активировать команды первого яруса следующим набором исходных данных, не дожидаясь конечного результата вычислений по первому набору исходных данных. Это позволяет повысить загрузку многопроцессорного обрабатывающего ядра системы, так как при выходе по одному из наборов входных данных на последовательную ветвь графа по другим наборам входных данных обязательно будет обрабатываться параллельные ярусы команд этого же потоковогографа. Для указания вершине о том, что ее выходной токен уже востребован последующей вершиной (вершинами), в ВС прибегают к механизму подтверждения с квитированием также, как и в связях между ступенями асинхронного конвейера. Когда кокая-то готовая команда активирована, т.е. помещена в очередь к процессорному полю, выполняется специальная отметка в командах – предшественниках о возможности их повторного активирования новыми входными токенами. Известны два типа архитектур потоковых ВС: статическая архитектура и динамическая архитектура. Статическая называется также «единственный токен - на - дугу». Допускается присутствие на ребре потокового графа не более, чем одного типа токена. Динамическая отличается тем, что на дуге графа допускается присутствие производительного числа токенов разных типов. В этих ВС в информационный кадр токена кроме значения операнда и адреса последующей команды, для которой требуется этот операнд, дополнительно вводится тег окрашивания, например номер итерации цикла, в которой этот токен участвует в вычислении тела цикла, или номер вхождения в реентерабельную процедуру. Отличается также правило активирования вершин потокового графа: «вершина активируется только тогда, когда на всех ее входных дугах присутствуют одинаково помеченные (окрашенные) токены, имеющие идентичные теги». Структура статической потоковой ВС Процессоры получают пакеты действий в формате: , где «Операнды» - это их значения, а не адреса в памяти; «Адресат» - адрес ячейки следующей команды в общей памяти по потоковому графу, куда в качестве операнда должен быть направлен результат данной команды. Пакеты действий форматируются в модулях памяти ОПi, куда вначале загружаются потоковые программы в виде неготовых пакетов действий с пустыми полями операндов и начальные готовые пакеты с исходными данными. Готовый пакет действий с помощью коммутатора mnзагружается с выходов модулей памяти в свободный процессор. После вычисления результата команды он передается в память в пакете результата: , где «Адресат» - адрес ячейки команды в том модуле, где хранится данная программа, с указанием номера операнда (1-й или 2-й). Когда оба операнда в ячейку команды поступят, она объявляется готовой и ее содержимое, как пакет действий, загружается в любой свободный процессор. Машинные команды низкого уровня соответствуют вершинам-примитивам, описанным выше и имеющим в основном один выход, кроме копирования, TF-коммутатора и арбитра. Следовательно, в пакетах действий в основном один адресат и изредка – два. Разные форматы пакетов действий с разным числом адресатов и возможно операндов распознаются по КОП. Потоковая программа-это код потокового графа, в котором каждой вершине графа сопоставляется пакет действий, в котором заранее заполняются поля: КОП, Адресат, а поля операндов считаются непустым и только в начальных вершинах графа заполняются значениям исходных данных. По данному описанию функциональной организации очевидно, что статические потоковые ВС повышают производительность только за счет естественного параллелизма операций без учета возможности распараллеливания циклов и повторных вхождений в реентерабельные процедуры. Последние является очень важным резервом ускорения исполнения старых наследуемых последовательных программ в многопроцессорных ВС. В связи с этим были разработаны динамические потоковые ВС, позволяющие параллельно одновременно на нескольких процессорах обрабатывать разные распараллеленные итерации (витки) сложных циклов и разные вхождения в реентерабельные процедуры. Для этого потребовалось помечать (окрашивать) токены разными кодовыми значениям тегов. Структура динамической потоковой ВС с помеченными токенами. БСТ - блок согласования токенов. М, ДМ - мультиплексор, демультиплексор. Применена конвейерная кольцевая структурная организация. Блок согласования токенов, построенный на ассоциативной памяти, применен для обнаружения токенов с одинаковыми тегами. Для каждого очередного токена с одинаковым и тегами. Для каждого очередного токена, поступающего из очереди в БСТ, ассоциативно находится в памяти токен с идентичными тегом и адресом назначения. Если такой токен в памяти не обнаружен, то принятый новый токен заносится в память. Если же токен - партнер (парный операнд одной и той же команды) найден в памяти, то БСТ извлекает его из памяти и объединяет оба токена в пакет пары токенов с общим тегом и адресом. В пакет токена внесен дополнительный однобитовый флаг (Ф), чтобы различать два возможных вида команд «Система /Вычисление». В первом варианте он признается пакетом, несущим системное сообщение, например «Загрузить команду в память» и т.п., а во втором - пакет идентифицируется как токен потоковой программы. По адресу из пакета токенов в основной памяти (ОП) находится неготовая ждущая операндов команда («пусто». Тег. КОП. Адр. Адр) потоковой программы. Пакет пары готовых токенов заполняет пустое место операндов команды, составляется выполняемый пакет и направляется на исполнение в любой свободный процессор. В формате команды имеются один или два адреса последующих команд. Их не более, чем два, так как команды соответствуют вершинам-примитивам потокового графа с ограниченным числом входов-выходов. После обработки команды в процессоре ее результат помещается в пакет (пакеты) одного (или двух) токена, в качестве Адр. назначения вносится код одного адресов из формата выполняемого пакета. Далее токен передается во входную очередь и обрабатывается аналогично. В момент формирования очередного токена в его пакет вносится код тега из формата того выполняемого пакета, результат которого помещается в поле данных токена. Недостатком этого варианта динамической потоковый ВС считается необходимость применения в БСТ ассоциативной памяти большой емкости, которая увеличивается из-за распараллеливания на основе команд и использования многозадачного режима для повышения загрузки процессоров. Ассоциативную память заменяют на обычное адресное ОЗУ в динамических потоковых ВС с явно адресуемыми токенами, или с так называемыми непосредственным согласованием токенов. В этом варианте архитектуры ВС токены хранятся в памяти не в отдельности каждый, а группами в кадрах токенов. В один кадр включаются токены с идентичными тегами, т.е. токены одной и той же итерации (витка) распараллеленного цикла, или одного и того же вхождения в реентерабельную процедуру. Так как в пределах кадра необходим адресный поиск нужного токена, этот механизм потоковой обработки назван «с явно адресуемыми токенами». Введены два дополнительных указателя: JP-указатель команды;FP-указатель кадра. Формат одного пакета токена: Значение.FP.JP. Команды потоковой программы хранятся в формате: < КОП .J- Индекс в памяти кадров. Адресат>. Индекс определяет положение ячейки с нужным токеном - операндом внутри кадра, т.е. величину смещения относительно базы кадраFP. Адресат-местоположение в памяти последующей команды (или двух команд), которой должен передаваться результат обработки данного токена. Он также задается в виде смещения относительно базы JP(или двух смещений) Каждое слово в памяти кадров имеет битовый тегналичия:«1»-в ячейке находится токен; «0»-ячейка пуста. В динамике исполнения потоковой программы каждый новый токен, образованный из предыдущего результата V1 , вначале находит по адресуJPсвою команду, где он является операндом, а затем в памяти кадров по адресуFP+(JP.J) проверяется бит наличия, гдеJP.J-это содержимое поля индексаJв формате команды по адресуJP. Если бит наличия «0», то значение заносится в эту ячейку памяти кадров, а бит наличия переводится в состояние «1». Если же токен < V2.FP.JP>по вычисленному адресуFP+(JP.J) находит непустую ячейку с битом наличия «1», то это значит, что там уже его ожидает готовое значениеV1 одного операнда командыJP. Тогда значениеV1 извлекается из этой ячейки кадра токенов, бит наличия сбрасывается в «0», формируется выполняемый пакет команды в формате: , гдеJP.OP-КОП;JP.D-адресат (один или два) в виде смещения.FPиJP–базы, необходимые для вычисления поJP.Dисполнительного адресаJPадресата, т.е. последующей команды. Затем по результатуV3 формируется новый токен и обрабатывается аналогично. 3.1.5 Естественный параллелизм ветвей (задач) сложной последовательной программы В сложных последовательных программах ЭВМ фон Неймана могут быть выделены отдельные параллельные фрагменты (ветви), как задачи, имеющие свои входные операнды и входные результаты. Если в параллельной ВС имеется нескольких процессоров, эти ветви могли бы выполнятся одновременно при условии, что уже подготовлены их входные операнды. Однако их диспетчеризация, т.е. составление расписания моментов их запуска при асинхронной обработке на нескольких процессорах фон Неймана, существенно усложняются по мере увеличения числа связей между выделенными ветвями. Наиболее просто расписание запуска составляется, если удастся при параллельном программировании выделить в наследуемой последовательной программе подмножества независивых ветвей. Зависимость между ветвями возможна: 1) по управлению, когда условия переходов (предикаты) в данной ветви зависят от результатов или признаков, получаемых в других ветвях; 2) по данным, входной операнд данной ветви является выходным результатом другой ветви. Подмножество взаимно независимых ветвей должно обладать следующими свойствами: - ни один входной операнд ни одной ветви подмножества не является выходным результатом другой ветви этого же подмножества; -условия переходов внутри любой из ветвей подмножества не зависят от результатов или признаков, получаемых в другой ветви этого же подмножества; -при их выполнении не производится запись данных разных ветвей в одни и те же ячейки памяти; - все ветви подмножества выполняются по разным подпрограммам или разным копиям одной и той же подпрограммы. Параллелизм независимых ветвей аналогичен параллелизму независимых задач и может быть использован для повышения производительности обработки сложных программ в многопроцессорных ВС фон Неймана, если организовать асинхронный запуск ветвей названного подмножества с учетом ожидаемых времен их процессорной обработки. При распараллеливании сложной последовательной программы в настоящее время в инженерной практике используются автоматизированные системы параллельного программирования, имеющие в своем составе экранные редакторы структур параллельных программ, графически отображаемых в виде ярусно-параллельных форм (ЯПФ). ЯПФ - это многоуровневый граф, узлы которого в каждом из уровней соответствуют подмножеству выделенных независимых ветвей, а дуги – направлениям передачи операндов между ветвями. Ярус – это одно подмножество независимых между собой параллельных ветвей. Например X1,x2, ….,x9 -обозначения входных операндов программы; Yij- обозначения выходных результатовi-х ветвей, являющихся входным и операндами j-х ветвей низлежащих ярусов или выходными результатами всей программы; числа (10,15, 20. ). являющиеся весами вершин - это вычислительные сложности ветвей, измеренные либо в требуемом числе эквивалентных операций, либо в требуемом числе единиц машинного времени (тактов). Они необходимы как исходные данные для программ диспетчеризации. Системные программы-диспетчеры достаточно сложны, так как необходимо составлять оптимальные расписания запуска ветвей. В качестве критериев оптимальности принимаются либо минимизация времени обработки всех ветвей, либо минимизация задержки (ожидания) при запуске ветвей. Задача дополнительно усложняется, если ширина ЯПФ (максимальная мощность подмножеств независимых ветвей в ярусах) превышает наличное число процессоров в системе. Алгоритмы составления расписаний, к сожалению, плохо формализованы и обычно составляются системными программистами интуитивно (эмпирически). Следовательно, параллельное программирование и организация параллельных вычислений в многопроцессорных ВС с архитектурой фон Неймана- это весьма сложная задача, требующая очень высокой квалификации. Требования к квалификации параллельных программистов можно значительно снизить и одновременно добиться хорошей степени загрузки процессоров, т.е. окупить затраты на создание многопроцессорной ВС, если перейти от архитектуры фон Неймана к потоковой архитектуре ВС. В отличие от рассмотренных выше потоковых ВС, выполняющих параллельную обработку на уровне команд, при параллельной обработке ветвей (тредов, потоков, нитей в терминологии UNIXиWindowsNT) применяется макропотоковая обработка, когда вычисления внутри ветвей выполняются по последовательным декларативным подпрограммам, а параллельно последовательная обработка ветвей осуществляется по механизму программного управления данными (по степени готовности входных операндов ветвей). Рассмотрим на примере произвольного потокового графа, как можно было бы его декомпозировать на параллельные ветви (задачи), которые называются также «треды». По способу организации параллельной обработки ветвей различают два вида макропотоковой обработки: без блокирования и с блокированием. В модели вычислений без блокирования выполнение ветви не начинаются до тех пор, пока не получены все ее входные операнды. В этом случае последовательные вычисления внутри ветвей никогда не прерываются. В модели вычислений с блокированием запуск может производиться не по всем входным данным, а по части из них, не ожидая полной готовности всех входных операндов. В нашем примере все три ветви можно запустить одновременно, не ожидая пока будет готов второй (левый) входной операнд третьей ветви. Если на коком-то шаге последовательной обработки ветви неготовый еще при ее запуске операнд так и не успеет перейти в состояние готовности, эта ветвь прерывается с сохранением ее ССП, а освободившийся процессор начинает выполнение другой готовой ветви, или почти готовой ветви по состоянию операндов начальных команд ее последовательной программы. Поэтому в таких макропотоковых ВС полностью сохраняться система прерываний программ фон Неймановской ЭВМ. Такой подход позволяет повысить загрузку параллельных процессоров. Для макропотоковой обработки ветвей подходит способ функциональной организации динамической потоковой ВС с помеченными токенами на дугах, связывающих ветви друг с другом. В данном случае по сравнению с параллелизмом на уровне команд число токенов существенно уменьшиться. Это значит, что число операндов, передаваемых между ветвями в ходе их параллельно последовательной обработки, будет значительно меньшим, чем операндов, передаваемых между командами при распараллеливании на уровне команд. Кроме того, при разбиении сложной исходной программы на ветви программист вправе выбрать такое множество ветвей из всевозможных вариантов, в котором минимизируется число связей между ветвями. Тогда в качестве коммуникационной среды для взаимной передачи операндов может быть использована общая шина, что позволит снизить сложность структурной организации многопроцессорной системы по сравнению со структурой динамической потоковой ВС с помеченными токенами, приведенной на рис.15.12 основного учебника [1], а также макропотоковой ВС, приведенной на рис.15.15 учебника [1]
Мы рассмотрели основные типы параллелизма решаемых задач и установили как повысить производительность ВС, приспосабливая ее структурную и функциональную организацию к типу параллелизма. Кроме этого методы и средства реализации параллелизма зависят от того, на каком уровне он должен обеспечиваться. Различают следующие уровни параллелизма: -уровень заданий; -уровень программ; - уровень команд; - уровень битов. Уровень заданий реализуется на многопроцессорных ВС в многозадачном режиме, когда несколько независимых заданий одновременно выполняются на разных процессорах, практически не взаимодействуя друг с другом. На этом уровне обработка реализуется либо в ансамблевых многопроцессорных ВС, либо как псевдопараллелизм в однопроцессорных ВС. В последнем случае он реализуется в режиме разделения времени процессора и мультипрограммирования. Центральный процессор и система ввода-вывода работают одновременно, обслуживая разные задания. Мультипрограммирование применяется и в многопроцессорных ВС для повышения загрузки процессоров ввода-вывода и периферийных устройств. Уровень программ может быть реализован только в многопроцессорных ВС путем использования параллелизма ветвей сложной программы, параллелизма данных и параллелизма итераций программного цикла. Последний тип параллелизма выявляется на программном (алгоритмическом) уровне. Характерным примером легко распараллеливаемой циклической процедуры может быть следующий фрагмент кода последовательной программы For J:=1toN do A(J):=B(J)+C(J). Здесь все операции суммирования независимы друг от друга. Поэтому их вычисления могут выполняться в любой последовательности, в том числе одновременно на Nпроцессорах. Такое распараллеливание называется расщеплением цикла. К сожалению, многие циклы последовательных программ не могут распараллеливаться так просто. Однако создана теория их распараллеливания путем специального преобразования программных кодов и алгоритмов. Разработаны распараллеливающие компиляторы, позволяющие в полуавтоматическом режиме преобразовывать сложные многократно вложенные циклы. Уровень команд реализуется как в многопроцессорных ВС, так и в многофункциональных конвейерных однопроцессорных ЭВМ и современных суперскалярных и VLIWмикропроцессорах путем использования естественного параллелизма операций и данных в решаемых задачах, команд в программах и возможности одновременного выполнения различных этапов исполнения разных команд в конвейерах. В состав процессора включаются избыточное число АЛУ и операционных блоков, а также многоступенчатый конвейер команд. Уровень битов реализуется в обычных и суперскалярных процессорах путем одновременной обработки бит слова, например в многоразрядных параллельных арифметических функциональных блоках, выполняющих так называемые бит – параллельные операции. Однако биты слов могут обрабатываться последовательно по бит – последовательным операциям, но параллельно во всем массиве операндов. По этому принципу параллелизм на уровне битов реализуется в векторных вертикальных и ортогональных процессорах, ассоциативных однородных вычислительных средах и основан на использовании естественного параллелизма данных. Кроме подразделения по уровням, параллелизм классифицируют по степени связности между одновременно исполняемыми фрагментами программ. Вводится понятие гранулярности параллельных программ. Это мера отношения объема вычислений в параллельных фрагментах к объему коммуникаций (сообщений, передаваемых между ними). Степень гранулярности разделяется на три категории: крупнозернистая, среднезернистая, мелкозернистая, соответственно которым определены три вида параллелизма. Крупнозернистый параллелизм соответствует уровню заданий, когда сложные параллельные программы, включающие тысячи команд, слабо связаны или вовсе не связаны между собой, а их параллельная обработка организуется операционной системой ВС. Среднезернистый параллелизм соответствует уровню программ, когда единицами распараллеливания являются вызываемые процедуры, состоящие из сотен команд и слабо связанные между собой. Параллельная обработка организуется операционной системой, а все вопросы коммуникации заранее в статике разрабатываются программистами или подготавливаются компилятором. Мелкозернистый параллелизм соответствует уровню команд и/или уровню программ при их распараллеливании на достаточно мелкие фрагменты, состоящие из десятков команд, например вычисляющие выражения или отдельные итерации циклов. Причем интенсивность вычислений и обмена данными между фрагментами могут быть примерно равными. Этот вид параллелизма обычно подготавливается в статике распараллеливающим компилятором. Для достижения большого ускорения при параллельной обработке требуется искусно балансировать между степенью гранулярности параллельной программы и величиной коммуникационной задержки в обмене данными между гранулами. При малой коммуникационной задержке целесообразен мелкозернистый параллелизм. Если коммуникационная задержка велика предпочтительней применять крупнозернистый параллелизм. Так как выбор гранулярности неоднозначен и требует выполнения трудоемкого перебора вариантов разбиения исходной программы на параллельные фрагменты, актуальной задачей является создание такого распараллеливающего компилятора, которой мог бы путем комбинаторной оптимизации выбрать компромиссный вариант распараллеливания. В качестве критерия целесообразно выбрать достижение максимального ускорения при заданной величине коммуникационной задержки и ограничении сверху на число связей между выделенными параллельными ветвями, т.е. на число входных операндов и выходных результатов каждого из фрагментов. Последнее, например, обусловлено необходимостью ограничения длины пакета токенов при макропотоковой обработке параллельных ветвей . Конечно, это существенно повысит вычислительную сложность компилятора и потребует применения в ведущей однопроцессорной ЭВМ дополнительных специализированных процессоров – акселератов для ускорения процедур комбинаторной оптимизации. Однако другого пути снижения трудоемкости параллельного программирования нет. Актуальность создания такой сложной системы распараллеливающей компиляции обусловлена также острой необходимостью ускоренного исполнения на параллельных ВС громадного объема старых наследуемых последовательных программ однопроцессорных ЭВМ. 3.3 Основы метрической теории ВС Метрическая теория ВС основана на теории дискретных случайных процессов (цепях Маркова), теории сетей Петри, теории систем массового обслуживания, имитационном моделировании случайных процессов функционирования ВС методом Монте – Карло. Глубокое научное исследование позволяет получить достоверные оценки показателей эффективности ВС. В инженерной практике используются приближенные оценочные и асимптотические формулы, позволяющие принять решение при выборе варианта архитектуры и структуры создаваемой ВС на начальных этапах эскизного системотехнического проектирования. Для оценки эффективности параллельных вычислений используют систему метрик параллельных ВС. 3.3.1 Метрики параллельных вычислений Достигаемая степень распараллеливания программы характеризуется числом процессоров, участвующих в ее выполнении в каждый момент времени D(t) (DOP–DegreeofParallelism). Этот показатель называется степенью параллелизма. График функции D(t) называется профилем параллелизма программы. Степень изменения загрузки процессоров во время обработки программы определяется ее алгоритмом, доступностью ресурсов системы и качеством работы распараллеливающего компилятора. DOP Dmax 8 D(t) 0 t 2 4 8 10 12 14 16 18 20 22 24 26 28 tн tк В общем случае дискретные интервалы (кванты) времени ti,i= 1,mсуммарного времени обработки программы :tк –tн =могут быть неодинаковыми. В течении i–го кванта времени реализуется степень параллелизмаDi. По профилю параллелизма вычисляется средний параллелизм А: К среднему параллелизму асимптотически приближается степень повышения производительности ВС. Если принять, что Δ – это производительность одного процессора системы и число процессоров в системе n>>Dmax, то можно оценить время обработки программы в двух крайних случаях: Т(1) – время обработки на одном процессоре; Т() – время обработки при числе процессоровn=. , где Wi– объем работы, выполненный на интервале времениti, равныйWi= Δ*Di*ti Асимптотическое повышение производительности S=T(1)/T() =/ = A . При ограниченном числе процессоров в системе выполняется оценка следующей системы показателей эффективности параллельной обработки. Ускорение - это среднее значение ускорения за счет параллельного выполнения программы, вычисляемое как отношение времени, требуемого для ее выполнения на однопроцессорной ЭВМ, и времени ее параллельного выполнения вn- процессорной ВС. S(n) =T(1)/T(n), Причем, обычно S(n)n. Ускорение и загрузка каждого отдельного процессора системы жестко связаны между собой. Если ускорение максимально возможное S(n) =n, то загрузка процессоров также максимальна=1. ПриS(n) эффективность n– процессорной системы, вычисляемая как доля ускорения, приходящаяся на один процессор E(n) =S(n) /n=T(1) /nT(n). Диапазон ее изменения: 1/nE(n)1, нижнее значение которого соответствует предельному случаю, когда затраты не окупаются, так как Т(n) = Т(1), т.е. никакого ускорения не получено. Эффективность использования избыточного числа параллельных процессоров характеризуют также показателем избыточности. Избыточность может быть вычислена непосредственно по показателю эффективности. R(n) =(1-E(n)) /E(n) = 1/E(n) – 1, Которая изменяется в диапазоне 0R(n)n-1, где верхний предел соответствует худшему случаю, когдаE(n) = 1/n, никакого ускорения не получено и (n-1) процессоров введены в систему бесполезно. Нижний предел соответствует наилучшему использованию всехnпроцессоров, так как приE(n) = 1 все процессоры полностью загружены. Приведем численный пример. Время обработки программы на однопроцессорной ЭВМ равно 8с. После ее распараллеливания с максимальной степенью распараллеливания Dmax= 5 она обрабатывается в параллельной системе с числом процессоровn=5 за 2с. Ускорение S(n) = 8/2=4. Эффективность E(n) = 4/5=0.8 Избыточность R(n) = 1/0.8-1 = 0.25 Если достигается максимальная эффективность E(n) =1 и ускорениеS(n) =n, то считается, чтоn– процессорная система и выполняемая на ней параллельная программа обеспечиваютлинейное ускорение. Линейное ускорение практически не достижимо во – первых из-за невозможности обеспечить стопроцентную загрузку процессоров потому, что в профилях параллелизма всех программ всегда средний параллелизм (А
Поддержание когерентности требует, чтобы при изменении элемента данных одним из процессоров такие же изменения были бы проведены в кэш-памятях остальных процессорных блоков, где есть копия измененного элемента данных, а также в общей памяти. Для этого недостаточны алгоритмы сквозной или обратной записи и требуются дополнительные приемы, которые называются запись с аннулированием и запись с обновлением. При записи с аннулированием, если процессор записывает слово в одну из строк своей кэш-памяти, все копии этого слова в кэш-памятях других процессорных блоков помечаются как недостоверные (недействительные-Invalid). Для этого в теги строк дополнительно вводится бит достоверности, который для отметки недействительности установлен в «0». Если другой процессор попытается в своей кэш-памяти прочитать копию где-то измененного слова, то при обращении к недействительной строке произойдет промах. В результате контроллер кэш-памяти должен считать корректную копию слова этой же строки из основной памяти, а если она и там помечена как недействительная, то - из той удаленной кэш-памяти, где это слово было изменено. Запись с обновлением предполагает, что любая запись в строку кэша немедленно дублируется в копии этой строки во всех остальных кэшах. Для этого необходим специальный режим широковещательной записи, когда каждое обращение на запись в любую локальную кэш-память сразу же дублируется во всех кэшах системы. Контроллеры кэшей проверяют, нет ли в их кэшах копии изменяемого слова. Если такая копия найдена, то соответствующая строка либо сразу же обновляется, либо предварительно помечается как недействительная в зависимости от типа протокола когерентности. В общей шине это организовать сравнительно просто путем передачи на шину любых запросов процессоров на запись в память и наблюдения за информацией в шине всеми контроллерами кэш-памятей. Протокол обеспечения когерентности кэш-памятей реализуется конечными автоматами их контроллеров. Число состояний автомата не превышает четырех. Состояния автомата тождественны состояниям строк кэш-памяти. В теге каждой строки для этого выделяются два бита, называемые битами состояния (SB-StatusBit). Статусные биты могут изменяться как своим процессором, для которого данная кэш-память является локальной, так и любым другим процессором системы. В протоколе MESIкаждая строка кэш-памяти может находится в одном из следующих четырех состояний. - (M-Modified) - модифицированная. Данные в этой строке модифицированы своим процессором, но измененная информация еще не переписана в основную память, а следовательно и в другие кэши. - (E-Exclusive) - эксклюзивная. Эта строка в данном кэше совпадает с аналогичными данными в основной памяти, но отсутствует в любом другом кэше. Информация в этой строке еще не подвергалась изменению посредством запроса на запись. -(S-Shared) - разделяемая. Строка может присутствовать в одном из нескольких других КЭШах, и ее данные совпадают с аналогичными данными в основной памяти. -(I-Invalid)-недействительная. Она помечена как недостоверная и является логически недоступной. При обращении к этой строке контроллер инициализируетпромах также, как и при отсутствии строки с таким же адресом. В результате обработки этого промаха в основной памяти или в других кэшах отыскивается достоверная информация или такая же достоверная строка и замещает недостоверную, а строкаIпереводится в одно из трех остальных состояний в зависимости от вида запроса (чтение или запись). ПротоколMESIразработан для кэш-памятей собратной записью. Поэтому при обработке промаха нужно учитывать, что информация требуемой строки может оказаться в основной памяти недостоверной. Этот факт устанавливается в результате взаимодействия контроллеров кэшей в сеансах широковещательной передачи по шине запросов к памяти и ответов контроллеров. Строка переводится в состояниеI(недействительная) своим процессором при выполнении записи в одноименную строку в любом удаленном кэше в любом из трех оставшихся ее состояний. Так как все запросы к памяти в любом процессорном блоке широковещательно передаются по шине, все контроллеры кэшей, наблюдая за шиной, узнают адрес строки, куда выполнена запись, и инициализируют перевод в состояниеIкопии этой строки в своих кэшах. Кэш-попадание при чтении не изменяет статус читаемой строки в состояниях M,E,S. Не изменяется статус строки при записи в состоянииM. Метод обработки промаха. Она выполняется однотипно как при отсутствии строки с требуемым адресом, так и при недействительном состоянии подходящей строки. Если в данном процессорном блоке возник промах при чтении, то этот запрос к памяти широковещательно передается по шине. Если при этом от контроллеров других кэшей не поступило ответных сообщений, это указывает на то, что ни в одной из удаленных кэш-памятей нет такой строки, и, следовательно, соответствующие слова в основной памяти достоверны. Тогда информация требуемой строки считывается в данный кэш из основной памяти, и этой строке в этом кэше присваивается статус E. Если же от какого-то контроллера получено ответное сообщение, то это указывает, что соответствующие данные в основной памяти недостоверны. Тогда промахнувшийся процессор откладывает инициализацию обращения в основную память и продолжает вместе со своим контроллером кэша наблюдать за шиной. Другой контроллер, пославший ответ, зная по результатам предыдущего наблюдения за шиной, какая строка была запрошена, сразу же переписывает ее содержимое в основную память. Как только промахнувшийся процессор, наблюдая за шиной, установит, что запись в основную память закончена, выполняет повторный доступ к ней и, наконец переписывает эту достоверную информацию в свою кэш-память. Обе копии этой строки в кэшах этих двух процессорных блоков помечаются как S(разделяемая). Если по запросу данного процессора на запись наблюдается промах по записи в его локальный кэш, то содержимое требуемой строки должно быть считано из основной памяти, а затем модифицировано в кэше. Но вначале нужно убедится, что в основной памяти в данный момент времени находятся достоверные данные этой строки, то есть в других кэшах отсутствует ее модифицированная копия в состоянии М. Для этого процессорный блок, выставив запрос на шину, прослушивает ее. Если отклика других процессорных блоков нет, значит содержимое требуемой строки в основной памяти достоверное. Тогда данный процессорный блок обращается в основную память, переписывает содержимое этой строки в свой кэш и помечает ее как М (модифицированная). Другие процессорные блоки, наблюдая за шиной, и обнаружив в своих кэшах копии этой же строки, но помеченные как SилиE, по результатам этого сеанса переводят их в состояниеI. Если же был оклик другого блока, то это значит, что в его кэше имеется модифицированная копия этой строки (находится в состоянии М). Тогда данный процессорный блок выжидает, наблюдая за шиной, когда другой блок перепишет эту копию строки в основную память. Тот же, выполнив эту запись в основную память, переводит эту же строку в своем кэше в состояние I. Данный процессорный блок после этого переписывает эту строку в свой кэш, модифицирует своей записью и помечает как М. Таким образом, в результате обработки промаха по записи во всей системе окажется только одна модифицированная копия строки и только в одном кэше. В остальных кэшах и в основной памяти ее копии будут недостоверными. Все эти сложные процедуры поддержания когерентности кэш-памятей в мультипроцессорах SMPс общей шиной можно компактно отобразить на диаграмме состояний протоколаMESI Shr- содержимое строки в основной памяти недостоверное (есть отклики контроллеров других кэшей), т.е. строка совместно используется. Pvt- содержимое строки в основной памяти достоверное (нет откликов контроллеров других кэшей), т.е. она не используется совместно. Порядок перехода строки кэш-памяти из одного состояния в другое зависит от текущего статуса строки, выполняемого обращения в память в кэш (попадание или промах), а также от того, является ли строка совместно используемой или нет.
Значительная часть проблем организации памяти SMPархитектур с общей памятью удалось снять путем замены общей шины на коммутаторы. Широко распространен перекрестный коммутатор (кроссбар), описанный выше в разделе 3.1.1. От псевдопараллельного доступа процессоров в параллельные модули общей памяти можно перейти к одновременному параллельному доступу в разные модули памяти. Разрешение конфликтов между процессорами за доступ в один и тот же модуль памяти можно выполнять теми же системными программами ведущего процессора, которые управляют ключами коммутатора. Можно также реализовать эти функции в специальном контроллере коммутатора, переключающем ключи на основании запросов процессоров к памяти. Так как коммутатор обеспечивает множественность путей между процессорами и модулями общей памяти, возможно увеличение числа процессоров без непомерного увеличения коммуникационных задержек, характерного для общей шины. Известны следующие мультипроцессоры, основанные на кроссбаре: - EnterpriseServerS70-12 процессоров; - ProLiant8500-8 процессоров; - супер-ЭВМ Eterprise10000-64 процессора -отечественная супер -ЭВМ Эльбрус 1, 2, 3,-100 процессоров. Основной недостаток кроссбара -степенное возрастание аппаратной сложности коммутатора с увеличением числа процессоров: не менее, чем в n² раз, гдеn-число процессоров. Поэтому от статической схемы взаимодействия между процессорами и модулями общей памяти переходят к динамической схеме, когда в коммутаторе изменяется топология межсоединения при изменении соединенной пары: процессор - модуль памяти. Динамическая схема взаимодействия реализуется каскадным коммутатором (многоступенчатым), который составляется из базовых коммутирующих элементов (БКЭ), так называемых «полных кроссбаров», с небольшим числом входов и выходов. Чаще всего используются простейшие БКЭ с двумя входами и двумя выходами, обозначаемые как 22, хотя применяются и более сложные БКЭ типа 42 или 44. БКЭ в большинстве КК-это ненаправленная ключевая схема, состояния ключей которой задаются внешним управляющим двоичным кодом и обеспечивают любые межсоединения выводов схемы. В БКЭ типа 22 для этого достаточно четырех ключей. Возможные состояния БКЭ типа 22 Из таких БКЭ можно составить сложные коммутаторы типа nn, в которых число входов равноn, а число БКЭ в каждой ступени равноn/2. Число ступеней и схемы межсоединений между БКЭ ступеней подбираются так, чтобы можно было бы одновременно параллельно соединитьnпар объектов в любых их сочетаниях. В мультипроцессорах часто используется каскадный коммутатор (КК) типа «омега-сеть» nnс числом ступеней и межсоединениями между ступенями БКЭ, проложенными согласно функции идеального тасования. Рассмотрим пример омега – сети 88. При идеальном тасовании два узла соседних ступеней с адресамиiиjимеют между собой непосредственную связь при условии, что двоичный код номераjможет быть получен из двоичного кода номераiпутем его циклического сдвига влево. Тогда приn=8 межсоединения между ступенями следует выполнять по следующей схеме: Маршрутизация в омега-сети (прокладка межсоединения в паре процессор-модуль памяти) выполняется по простому правилу: -вычисляется сумма по модулю два двоичных кодов номеров процессора и модуля памяти, например для П3 и ОП7: 010110=100; -по значениям разрядов суммы определяется способ переключения БКЭ: по старшему разряду БКЭ первой ступени слова; по второму-второй ступени, по третьему-третьей ступени и т.д.; -если значение разряда суммы равно 0, то БКЭ должен обеспечивать прямую связь; -если значение разряда суммы равно 1, то в БКЭ выполняется перекрестное соединение. Контроллер сети, получив от процессора запрос к памяти, по номеру процессора и номеру затребованного им модуля памяти на основании приведенного правила управляет соответствующими ключами и прокладывает маршрут межсоединения для доступа процессора в затребованный модуль памяти. Легко проверить, что, какую бы из оставшихся несоединенных пар «процессор-модуль памяти» мы не взяли, по этому правилу всегда найдется независимый параллельный маршрут их соединения без коротких замыканий межсоединений между собой. Конечно, при большом числе абонентов, например при числе процессоров n>32 увеличится число требуемых БКЭ и существенно усложнится контроллер сети. Сеть «омега» обладает важным свойством самомаршрутизации. Если контроллер сделать распределенным и в каждый БКЭ ввести схемы сложения по модулю два, то по заголовку сообщения-запроса, в котором будут передаваться адрес процессора и адрес модуля памяти, БКЭ смогут самостоятельно определять как им переключаться: напрямую, или перекрестно. Главное преимущество этих каскадных коммутаторов - большая экономия ключей по сравнению с перекрестным коммутатором. Для соединения nпроцессоров сnмодулями памяти требуется каскадов поn/2 БКЭ(22) в каждом, т.е.(1/2)n*БКЭ, илиключей. Так как в перекрестном коммутаторе требуетсяn² ключей, экономия числа ключей составит (). Например, приn=128, как в супер-ЭВМ «Эльбрус-3», число ключей перекрестного коммутатора 16384, а в омега-сети потребуется всего 1792 ключа, т.е. почти в десять раз меньше. Поэтому эта технология создания коммуникационных коммутаторных сетей с самомаршрутизацией применяется в архитектуреNUMAс числом процессоровN=256. К сожалению, эта экономия аппаратуры приводит к увеличению коммуникационной задержки. Если в перекрестном коммутаторе она равна задержке одного ключа, то в омега-сети - () таких же задержек ключей, например, приN=128 в семь раз больше. В архитектуреUMAс коммутаторами увеличиваются потери времени на реализацию протоколов когерентности кэш-памятей, так как организовать наблюдение контроллеров кэшей за общей шиной невозможно. Даже если проложить дополнительную шину для коммуникации процессорных блоков между собой, наблюдение только за ней не дает необходимой информации о состоянии основной памяти, так как обращение к ней выполняется по другому интерфейсу - через коммутатор. Следовательно, механизм когерентности, основанный на широковещании, становится дорогостоящим и не эффективным. В системах со сложной многоступенчатой коммуникационной сетью применяются протоколы обеспечения когерентности кэшей на основе справочника. Они предполагают сбор и отслеживание информации о содержимом всех локальных кэш-памятей всех процессорных блоков. Справочник хранится в общей памяти, а заполняется и модифицируется либо централизованным контроллером памяти, либо специальными системными программами ведущего процессора. При обращении в общую память любой процессор вначале посылает запрос к контроллеру справочника и только после его разрешения получает доступ к своей локальной кэш-памяти. Контроллер (или ведущий процессор) для выдачи этого разрешения обращается к справочнику, находит, в каких кэш-памятях есть копии запрошенной строки и в каких они состояниях. Далее процедуры напоминают протокол MESIи завершаются необходимыми изменениями статусов копии запрошенной строки, перезаписью ее модифицированной копии в основную память, а затем в локальный кэш запросившего процессорного блока, а также модификацией справочника. Только после этого процессор - инициатор может считать из своего кэша данные из запрошенной строки, или записать в нее новые данные с гарантией того, что все модификации копий этой строки выполненные другими процессорами в своих кэшах учтены в его копии этой же строки в его локальном кэше. Очевидно, что для хранения полного справочника о всех ячейках основной памяти, копии которых находятся в строках всех кэш-памятей, требуется большой расход основной памяти. Затраты времени на выполнение протокола когерентности увеличивают время обращения в память в несколько раз. Поэтому создаются все новые и новые протоколы, например протоколы с ограниченными или сцепленными справочниками, описанные в учебнике[1]. Потери времени можно существенно снизить, если согласовать содержимое не строк кэш-памятей, а копий разделяемых страниц, т.е. выполнять протоколы обеспечения когерентности копий совместно используемой процессором информации на уровне виртуальной памяти ВС. Так и сделано в последних версиях NUMAархитектур и в мультикомпьютерах. Тогда процедуры когерентности страниц можно выполнять значительно реже, чем строк кэш-памяти. Обращаться к справочнику необходимо при любом обращении к странице в своей локальной оперативной памяти, и, если в системе имеется модифицированная ее копия, следует ее вызвать в свою память, а все ее удаленные копии перевести в состояние недействительности до окончания своей обработки этой страницы. При уходе с этой страницы, если в ней выполняется хотя бы одна запись, нужно вновь обратиться к протоколу когерентности и разослать ее модифицированную копию всем процессорным блокам, где ее копии были временно заблокированы. Если выполнялось только чтение, то достаточно послать им сигнал о снятии блокировки и внести соответствующие пометки в справочник. По принципу локальности команд и данных время обработки страницы почти всегда будет во много раз больше, чем строки кэша, и частота выполнения процедур когерентности существенно снизится. Если затребованной страницы по справочнику не окажется ни в одной локальной памяти ни одного процессорного блока, тогда достаточно считать ее из ВЗУ и объявить эксклюзивной. Обратную запись модифицированных страниц в ВЗУ из локальных памятей процессорных блоков можно выполнять по принципу обратной записи, аналогичному обратной записи строк из кэша в основную память. Однако для внедрения механизма когерентности страниц необходимо перейти от физически общей памяти с общим физическим адресным пространством и адресацией на уровне ячеек памяти к распределенной совместно используемой памяти (DSM) с общим виртуальным адресным пространством и адресацией на уровне страниц. Тогда когерентность на уровне кэшей не потребуется, так как каждая кэш-память будет ускорять обращение к странице в своей локальной основной памяти, а о достоверности информации в странице должен заботится централизованный программный протокол с централизованным справочником. 3.5.2.4 Мультипроцессоры архитектурыNUMA. Особенности этой архитектуры мы уже рассматривали ранее в разделе 3.5. Исторически первой системой с архитектурой NUMAи с аппаратной реализацией распределенной совместно используемой памяти (DSM) и виртуальным единым адресным пространством с адресацией на уровне ячеек оперативных памятей процессорных блоков был кластерный мультимикропроцессорный комплекс (ММПВК)Cm*, созданный в 1970 году и не содержавший кэш-памятей. Процессорный блок называется кластер, а общая транзитная шина, объединяющая процессорные блоки,- межкластерной шиной. Главное отличие кластера от типовой МПС состоит в том, что в общую шину МПС включается дополнительный контроллер памяти (КП), который организует и исполняет межкластерные обмены информацией по принципу прямой физической адресации ячеек удаленной локальной оперативной памяти (ЛОП), если требуемая информация отсутствует в своей ЛОП. Тогда программа, хранящаяся в ЛОП любого кластера может выполняться любым удаленным процессором другого кластера. Однако обработка в пределах кластера выполняется гораздо быстрее, чем удаленным процессором другого кластера. Это объясняется не только более высокими величинами задержек при обмене через межкластерную шину, но и дополнительными затратами времени на разрешение конфликтов между процессорами за захват транзитной шины (ожидание ее освобождения). Современные микропроцессоры содержат встроенные кэш-памяти. Поэтому в архитектуре NUMAвозникла дополнительная проблема, замедляющая удаленные обращения в чужую память. Появилась необходимость обеспечения когерентности кэш-памятей. Системы архитектурыNUMA,в которых применены аппаратно-программные протоколы когерентности кэшей называются системами с архитектурой ССNUMA. В многошинных системах, подобных Cm*, применяются на аппаратном уровне механизмы когерентности, основанные на широковещании и наблюдении контроллерами памятей за транзитной шиной, и они совмещаются с программными протоколами когерентности по справочнику, реализуемыми ведущим процессорным блоком. На основе этого подхода архитектура ССNUMAреализована в суперЭВМ: -SGO(SiliconGraphicsOrigin) с числом процессоров 1024 по два в каждом процессорном блоке, объединенных кольцевым высокоскоростным каналом связи; -SequentNUMA-Qс числом процессоровPentiumII, равно 252, по четыре процессора в каждом процессорном блоке с локальной шиной и встроенным контроллером памятей. Коммуникационная сеть выполнена в виде перекрестного коммутатора 3232. Отличительной чертой этих супер-ЭВМ является то, что с целью ускорения процедур, программных протоколов когерентности хранение справочника дублируется в каждом из процессорных блоков. Это требует поддержания и их когерентности, но это во-первых снижает потери времени по сравнению с удаленными обращениями процессоров в централизованный справочник, а во-вторых повышает отказоустойчивость в случае отказа любого процессорного блока. Главное направление развитие архитектуры СС NUMA– выравнивание величин времен обращений к своей ЛОП и удаленной ЛОП другого узла, соотношение между которыми в названных супер-ЭВМ достигает 7-ми раз. Снизить это соотношение до 3-х раз (при времени обращения в свою ЛОП, равном 2 мкс, а в удаленную ЛОП-6 мкс) удалось в супер –ЭВМBBNButterfly, содержащей 256 процессоров. Это удалось благодаря применению в качестве коммуникационной среды между процессорными блоками динамической омега сети. Омега- сеть каждого процессорного блока (ПБ) двухкаскадная. Каждый каскад содержит по 4-ре БКЭ типа 44. К коммутатору с двух сторон подключаются по 16 процессоров. Возможно любое параллельное парное соединение двух из 32-х процессоров с задержкой, равной двум задержкам двух БКЭ. Таких 32-х процессорных блоков в системе восемь. Они разбиваются на две группы по четыре и соединяются между собой двухкаскадной омега-сетью на БКЭ типа 22: 3.5.2.5 ПротоколDASHобеспечения когерентности кэш-памятей в системах архитектуры ССNUMA Протокол DASHпозволяет поддерживать когерентность строк кэш-памятей процессоров в мультипроцессорах ССNUMA, в которых организована общая память с единым адресным пространством несмотря на то, что модули основной памяти распределены по процессорным блокам. Он реализуется в основном аппаратными средствами контроллеров кэш-памятей и модулей основной памяти с распределенными справочниками состояний строк кэш-памятей, сохраняемыми в памятях названных контроллеров и модифицируемыми процессорами и контроллерами в динамике исполнения программ. Модификация распределенных справочников выполняется локально в каждом из процессорных блоков в результате распределенной обработки» промахов» по чтению и по записи и обмена между процессорными блоками небольшим числом служебных сообщений. Достоинства протоколаDASHв том, что он применим при любом типе коммуникационной среды между процессорными блоками (многошинной, кроссбаре, динамической на многоступенчатых каскадных коммутаторах, кольцевой и т.п.) и существенно уменьшает простои процессоров при записях в кэш-памяти. Протокол DASHвыполняется за два этапа: -назначение резидентного для каждой строки кэш-памятей модуля основной памяти (РМОП) системы СС NUMA; -поддержание когерентности строк кэш-памятей процессоров. На первом этапе РМОП для каждой строки назначается в процессе начального заполнения кэш-памятей. При каждом первом промахе в любом процессоре инициализируется запрос отсутствующей в кэш-памяти строки в распределенной совместно используемой памяти системы (DSM). Тот модуль основной памяти (МОП), в котором в соответствии с единым адресом находится эта запрошенная по промаху строка, назначается РМОП по отношению к этой строке. Идентификатор строки запоминается в памяти контроллера этого МОП. Информация затребованной строки считывается в данном МОП, передается через коммуникационную среду в запросивший процессорный ее блок (ПБ) и записывается в его кэш-память, а в памяти контроллера РМОП запоминаются номера того ПБ, где имеется копия этой строки. В памяти контроллера кэш-памяти запоминается идентификатор этой строки и адрес ее резидентного РМОП. Следовательно, в памяти контроллера РМОП для каждой строки кэш-памяти, по отношению к которой он стал резидентным, хранится список тех ПБ, в кэш-памятях которых размещены ее копии, а в контроллерах кэш-памятей адрес того РМОП, который является резидентом для нее. Названный список ПБ является динамическим и расширяется по мере обращения в этот же РМОП других ПБ за информацией этой же строки. Очевидно, что один и тот же МОП может оказаться резидентным для множества строк разных кэш-памятей разных ПБ. Однако для поддержания когерентности строк кэш-памятей названной взаимной информации недостаточно. Кроме этого по каждой строкенеобходимо хранить и модифицировать в памятях контроллеров статусную информацию о ее состоянии: -в контроллере РМОП по каждой строке, по отношению к которой данный МОП является резидентным, хранятся коды трех ее возможных глобальных состояний: 1) «не кэшированная», если копия строки не находится в кэш-памяти какого-либо другого ПБ, кроме, возможно, в кэш-памяти одного ПБ, МОП которого является РМОП по отношению к этой строке; 2) «удаленно-разделенная», если копии этой строки размещены в кэш-памятях других ПБ; 3) «удаленно - измененная», если копия этой строки изменена операцией записи в кэш-память какого-либо ПБ; -в контроллере кэш-памяти каждого ПБ по каждой ее строке хранятся коды трех ее локальных состояний: 1) «невозможная к использованию», аналогично состоянию Invalidв протоколеMES1; 2) «разделяемая», если есть ее еще неизмененная копия не менее, чем в одной кэш-памяти другого (других) ПБ; 3) «измененная», если она изменена операцией записи в данный кэш данного ПБ. Процедуры протокола выполняются по разным алгоритмам в зависимости от режима: чтение строки процессором в своей кэш памяти; запись в строку процессором в своей кэш-памяти. 1. Режим чтения строки в своей кэш-памяти. Каждый процессор может беспрепятственно читать строку в своей кэш-памяти, если ее локальное состояние «измененная» или « разделяемая». Если строка отсутствует или находится в локальном состоянии «невозможная к использованию», то данный ПБ и контроллер его КЭШа посылает через коммуникационную среду запрос «промах чтения» в тот ПБ, где находится РМОП, резидентный для запрошенной строки. Он посылается в либо виде единого адреса общей DSM, либо служебным сообщением во втором варианте, когда данному ПБ уже известен РМОП. В первом варианте для этой строки может быть еще не назначен РМОП, и тогда он будет здесь назначаться по принципу первого этапа работыDASH. Далее процедура разворачивается в зависимости от глобального состояния запрошенной строки в памяти контроллера РМОП. Если глобальное состояние этой строки в РМОП «некэшированная» или «удаленно-разделенная», то информация строки считывается с РМОП и передается в запросивший ПБ, а в контроллере РМОП в список ПБ, содержащих копии этой строки, вносится номер ПБ, запросившего ее. Если глобальное состояние этой строки в РМОП «удаленно-измененная», то запрос пересылается в тот ПБ, кэш которого содержит измененную копию этой строки. Строка переходит в это глобальное состояние «удаленно-измененная» ранее в предыдущем режиме записи, который рассмотрим ниже. В данном режиме ПБ пересылает копию запрошенной строки в тот ПБ, в котором возник «промах по чтению», и одновременно в РМОП, резидентный для этой строки. Ее информация записывается в РМОП по единому адресу DSM, а состояние этой строки в контроллере РМОП переводится в глобальное состояние «удаленно-разделенная». 2. Режим записи в строку в своей кэш-памяти Если состояние строки в своем кэше «измененная», то запись выполняется беспрепятственно без приостановки программы в своем ПБ. Если локальное состояние адресуемой в своем кэше строки «невозможная к использованию» или «разделяемая», то программа обработки в своем ПБ приостанавливается и из данного ПБ в контроллер резидентного для данной строки РМОП посылается служебное сообщение на захват этой строки в исключительное пользование. Контроллер РМОП рассылает во все ПБ, кэши которых содержат копию этой строки, команду о переводе копий этой строки в локальные состояния «невозможная к использованию». После получения подтверждения от них о выполнение этой команды контроллер РМОП проверяет глобальное состояние запрошенной строки. Если глобальное состояние этой строки в РМОП «не кэшированная», то запрошенная строка переводится в глобальное состояние «удаленно-измененная», а ее копия отсылается запросившему ее ПБ. Он возобновляет прерванную обработку, начиная ее с записи в своем кэше в полученную копию затребованной строки, а сама строка переводится в локальное состояние «измененная». Если глобальное состояние этой строки в РМОП « удаленно-разделенная», то контроллер РМОП рассылает по списку всем ПБ, имеющим копию этой строки, команду на перевод их в локальное состояние «невозможная к использованию». После получения от них подтверждения о выполнение этой команды контроллер РМОП сообщает об этом запросившему запись ПБ, а копию этой строки переводит в глобальное состояние «удаленно-измененная», но не пересылает ее в запросивший ПБ. Этот же ПБ, получив подтверждение, что все удаленные копии его строки стали «невозможными к использованию», выполняет запись в кэш в свою копию этой строки, переводит ее в локальное состояние «измененная» и продолжает обработку приостановленной программы. Этот протокол является достижением разработчиков архитектуры СС NUMA, так как он с помощью контроллеров кэш-памятей и контроллеров МОП позволил на аппаратном уровне организовать распределенную совместно используемую общую память (DSM) с общим адресным пространством и адресацией на уровне общих переменных (общих ячеек памяти). Это позволило существенно снизить затраты времени на поддержание когерентности и на коммуникацию между ПБ. В этом и заключается главное преимущество мультипроцессоров сс NUMAпо сравнению с мультикомпьютерами с распределенной памятью, так как в последних когерентность обеспечивается только на программном уровне общей виртуальной памяти с адресацией на уровне страниц и только по централизованным справочникам состояний страниц в разных процессорных блоках. Причем обойтись без больших потерь времени на передачу сообщений все равно невозможно. Так как в системах типа СС NUMAосновная память распределена по множеству ПБ, то они по числу процессоров догоняют мультикомпьютеры.
Человечество в последние 50 лет постоянно испытывает потребность в ЭВМ гигантской производительности. Скорости компьютеров постоянно не хватает как для решения уникальных научных задач, так и для обработки громадного объема данных в целом ряде прикладных задач (проблема «большого вызова»). Разработчики самолетов мечтают промоделировать все условия полета и все виды нагрузок на все конструктивные элементы, не прибегая к созданию все новых видов аэродинамической трубы. Астрономы хотят воспроизвести всю историю Вселенной с момента большого взрыва до конца ее жизни и до очередного взрыва. Фармацевтам надоело уничтожать легионы крыс и других подопытных животных, и они хотят разрабатывать новые лекарства с помощью компьютерных моделей болезней и процесса воздействия препарата на организм человека. Остро стоит проблема определения пространственной структуры одной макромолекулы в химии, биологии генетике. Экономисты не могут обойтись без сложнейших расчетов для оценки внутриотраслевой и межотраслевой кооперации, для прогнозирования кризисов и курсов валют. Громадный объем информации приходится обрабатывать при автоматизации выборной системы, предсказании погоды, диспетчеризации и авиации и электроэнергетических системах, разведке воздушной обстановки в противовоздушной и противоракетной обороне, автоматизации проектирования современных ВС и СБИС, управлении самолетами и ракетами, современными аэропортами, сложными физическими опытами, атомными и тепловыми электростанциями, электрическими и тепловыми сетями и т.п. Сейчас всем стало ясно, что дальнейший прогресс зависит от производительности компьютеров. Что же нам делать? Образный ответ на это дал Таненбаум. «Транзисторы скоро уменьшатся до размеров нескольких атомов. Скорость передачи информации ограничивается скоростью света. Перегрев СБИС достиг такой степени, что ЭВМ придется помещать в холодильники. Невозможно построить процессор с временем командного цикла 0,001 нс, но зато можно построить ЭВМ с 1000-ю параллельных процессоров и при командном цикле 1 нс виртуально достигать такой же скорости обработки, если удастся ее организовать. Мелкозернистый параллелизм на уровне команд, использованный в суперскалярных микропроцессорах, проблемы не решает, так как достигаемое ускорение возможно не более чем в 10 раз. Наиболее правильный путь- это реализация крупнозернистого и среднезернистого параллелизма на уровне заданий, программ, задач, подзадач и ветвей на большом числе (более 1000) процессоров. Тогда, если удастся решить проблемы автоматизации параллельного программирования и обеспечения хорошей загрузки процессоров, возможно повышение производительности в 100.. раз без перегрева микросхем. Однако на этом пути нас ждут большие трудности, преодолеть которые, как мы уже увидели, без усложнения организации ЭВМ невозможно. Переход к архитектурам мультикомпьютеров число этих трудностей не уменьшает. В мультикомпьютерах взаимодействие между удаленными процессами возможно только путем передачи сообщений между ними через коммуникационную сеть. Это упростило наращивание числа процессоров по сравнению с мультипроцессорами и архитектурами NUMA, так как исключаютсяаппаратные средства, организующие физическую или виртуальную общую память, и нет необходимости обеспечивать когерентность нанизком уровнекэш-памятей процессорных блоков. Однако усложнилась организация взаимодействия, так как для его реализации потребовались специальные системные программы и методы прикладного программирования коммуникаций между параллельными вычислительными процессами. Для получения требуемых данных каким-либо процессом он должен с помощью системного ПО определить, в каком процессорном блоке находятся эти данные, а затем послать удаленному процессу сообщение с запросом копии этих данных. Процесс-инициатор нужно приостановить (заблокировать) до получения ответа. В это время в удаленном процессоре системное ПО и процесс-ответчик анализируют полученное сообщение и отправляют первому процессу ответное сообщение с затребованными данными. Получив это ответное сообщение, процессор-инициатор разблокирует свой процесс-инициатор и разрешает ему продолжать работу. Для выполнения процедур блокирования и разблокирования процессов потребовались специальные программные средства синхронизации параллельных процессов. Рассмотрим как выполняется взаимная синхронизация двух процессов, параллельно работающих на двух удаленных процессорах. Изобразим структуру процедуры обмена информацией между ними в виде графа. Пусть первый процесс находится в состоянии «работа 1.1». Когда он достигнет оператора коммуникации, он посылает сообщение 1 второму процессу. В этом сообщение должна быть информация, необходимая для синхронизации. Послав сообщение, первый процесс переходит в состояние «ждать 1», выполнив для этого перехода «работу 1.2». Если второй процесс готов принять сообщение, т.е. он находился в состоянии «ждать 2», то он принимает сообщение и обрабатывает его в состоянии «работа 2.1». Результат этой обработки передаются назад первому процессу через состояния «ответ 2» второго процесса и «ждать 1» первого процесса. После этого процесс-передатчик переходит в состояние «работа 1.1», чем и завершается сеанс взаимной синхронизации двух процессов. Реально ситуация гораздо сложнее. Процесс 2 может не находиться в состоянии «ждать». Тогда после получения «сообщения 1» он должен из любого состояния перейти в состояние «ждать 2» и «ответ 2». Может образоваться очередь сообщений нескольких процессов-отправителей к одному и тому же процессу-приемнику. Так как все эти коллизии и конфликты требует времени на их разрешение, процедуры коммуникации и синхронизации существенно увеличивают время обращения в чужую память по сравнению с временем обращения в собственную локальную память (более, чем в 7 раз). Это объясняется тем, что любое парное взаимодействие двух процессов выполняется за несколько шагов: начать передачу, проверить окончание передачи, ждать конца передачи, начать прием, проверить окончание приема, ждать конца приема. В системах параллельного программирования мультикомпьютеров применяются операторы посылки (send) и приема (receive) сообщений: где 1 содержит значения параметров в момент посылки сообщения; 2-(оператор) команда программы-передатчика, который отправил данное сообщение, -адрес приемника. RECEIVE(RecV)FROM, где 2-адрес отправителя – оператор (команда) удаленной программы, к которому направляется данное сообщение. На прием можно наложить ограничения оператором синхронизации WHEN,LгдеL- составленное программистом логическое выражение, зависящие от вектора признаков ожидаемых событий (буфер переполнен, процессор занят более срочной работой и т.п.) Если L-истина, то сообщение принимается, иначе оно ставится системным ПО в очередь к данному приемнику, а процесс-отправитель блокируется до получения разрешения на повторную передачу сообщений. Процессор-отправитель сохраняет непреданное сообщение в своем выходном буфере. Вызов удаленной процедуры организуется по оператору, введенному в программу процесса-передатчика: ACCEPT (список входных параметров), где - имя вызываемой процедуры. Процессу-приемнику посылается поsendспециальное сообщение, адресату сообщается имя вызываемой процедуры и входные параметры. Вызывающий процесс задерживается до тех пор, пока приемник не примет вызова. Затем он блокируется до тех пор, пока в приемнике не будет выполнена вызванная процедура и ее результаты не будут переданы назад передатчику в виде выходных параметров. Процесс-приемник после обработки вызова задерживается до тех пор, пока ответ не будет отправлен передатчику и не будет им принят. Такой принцип синхронизации взаимодействия называется «рандеву». Рассмотренные операторы основаны на алгоритмах синхронизации, реализуемых специальными программами общесистемной операционной системы, выполняемыми центральным ведущим процессорным блоком. Кроме этого централизованно выполняется функции планирования и диспетчеризации заданий, субоптимального размещения задач и данных в локальных памятях процессорных блоков, распределения общих ресурсов, контроля работы подчиненных процессоров, организации отказоустойчивых вычислений. Это самое слабое место мультикомпьютеров, так как при выходе из строя ведущего процессорного блока вся система оказывается неработоспособной. Надежность повышается путем дублирования или мажорирования ведущего процессорного блока. Без централизованного управления вычислительными процессами возникают трудности в автоматизации параллельного программирования. Как известно с целью уменьшения его сложности в мультикомпьютерах программно организуется единое виртуальное адресное пространство, разбитое на страницы. Но без централизованной мультисистемной ОС обеспечить когерентность страниц пока не удалось. При страничном промахе или необходимости распространить модификацию страницы на все ее копии в других процессорных блоках локальная ОС данного процессорного блока посылает системный вызов в ведущий процессор, где хранится полный справочник о распределении страниц и их состоянии во всех процессорных блоках. От централизации справочника попытались уйти в системе прикладного параллельного программирования Linda. Виртуальная общая память создается с помощью специального языка параллельного программирования и компилятора в статике (до начала вычислений). Однако это привело к повышению трудоемкости написания программ, а не к автоматизации, а также к усложнению компилятора. Наконец, производительность мультикомпьютеров существенно зависит от величины коммуникационной задержки. С целью ее уменьшения создаются все новые и новые топологии коммуникационных сетей. Они популярно описаны в главе 12 основного учебника [1]. Наиболее совершенные топологии межпроцессорных сетей межсоединений применены в супер-ЭВМ CrayT3E,OptionWhire, в которых 2048, 9416 процессорных блоков соединятся между собой по топологии трехмерной тороидальной решетки, а также в суперЭВМNCube;CM1, 2, 3, в которых 1024, 4096 процессорных блоков объединятся гиперкубическими сетями,. Если в первых каждый процессорный блок непосредственно связан с 6-ю соседями, то в гиперкубовых ВС – с 10 –ю, 12 –ю соседями. В связи с тем, что в мультикомпьютеррах этого подкласса число процессоров превышает 1000, они называются в США: MPP-процессоры с массовым параллелизмом. Главная их черта - специально создаваемые для них сложнейшие коммуникационные сети с уникальными топологиями. Второй путь уменьшения коммуникационной задержки – создание новых способов и алгоритмов маршрутизации пакетов передаваемых данных в коммуникационной сети. Последние достижение – это сочетание двух видов коммуникации: коммутации пакетов (адресной маршрутизации) и коммутации каналов с помощью коммутаторов в каждом узле коммуникационной сети. А также применение в таких сетях с коммутаторами нового способа маршрутизации, который называется «червоточина» (Wormholerouting). Каждый стандартный пакет данных разбивается на несколько коротких блоков, например длиной до 53-х байт. Пакет передается по сети последовательной цепочкой блоков друг за другом, но в целом по принципу адресной маршрутизации. В узловых коммутаторах буферизируются не пакеты в целом, а каждый блок пакета в отдельности. При маршрутизации коммутаторы создают временную цепь каналов так, чтобы не было разрыва в пакете. Блоки пакета при движении занимают последовательную цепь коммутаторов, т.е. пакет движется по сети «поездом», въезжает в сеть постепенно поблочно и выезжает из сети также цепочкой поблочно. Выигрыш в уменьшении задержки похож на выигрыш, получаемый в конвейерах. Пусть Т-время обработки пакета в одном узловом коммутаторе сети; n-длина цепи коммутаторов (узлов сети) последовательно проходимых в сети связи;Nбл-число блоков пакета (Nбл
Каждый базовый блок содержит 64-ре С БИС, где на одном кристалле каждой СБИС размещены 2 микропроцессора Alpha21264(тактовая частота 667 МГц) со встроенными кэш-памятямиI-го уровня. Каждая двухпроцессорная СБИС подсоединяется к БИС кэш-памятиII-го уровня емкостью 4 Мбайта. Каждый из этих шести базовых блоков содержит 64-ре общих на каждые два процессора модулей основных памятей емкостью по 2 Гбайта, контроллеры памятей и 64 жестких диска. 64 процессорных блока в каждом базовом блоке соединяются между собой по матрично – торроидальной топологии и организованы по архитектуре МРР с распределенными кэш-памятями, основной и внешней памятью. Таким образом в МВС имеется 768 процессоров, 768 Гбайт основной оперативной памяти, 384 параллельно работающих локальных жестких дисков. Пиковая производительность составляет 1 Тфлопс. Однако такая высокая производительность обходится слишком дорого. МВС-1000 М собрана в 18-ти стойках, потребляет 120 кВт электроэнергии, стоит 10 млн. дол. Правда, удалось обойтись без жидкостного охлаждения, и ограничиться воздушно-вентиляторным охлаждением благодаря тому, что тактовая частота процессоров не превышает 1 ГГц. При создании кластеров ставятся две задачи: достичь большой вычислительной мощности и обеспечить повышенную надежность и готовность на основе отказоустойчивых вычислений. Узлы кластера контролируют работоспособность друг друга путем передачи узлами друг другу специальных сигналов: (heartbeat) называемого «сердцебиение», или путем периодической рассылки каждым узлом сигнала (keepalive) «пока жив», а также путем формирования в каждом компьютерепризнаков«подвеска процессора (или процесса») у нескольких ближайших соседних компьютеров. Они образуются по превышению допустимых тайм–аутов, сообщаемых ему соседями заранее. Если сигнал от какого–либо узла не поступает своевременно до истечения его тайм- аута, то он считается вышедшим из строя, его диски и другие ресурсы, в том числе сетевые адреса переназначаются управляющей машиной другим узлам, а выполнявшиеся ими программы перезапускаются в режиме разделения времени в других узлах. Для этого имеется специальное ПО на всех уровнях распределенной общесистемной ОС (так называемая ОС надежности или система мониторинга ресурсов). Это позволило повысить коэффициент готовности кластеров до 0.9999 по сравнению с 0.9 отдельных компьютеров, т.е. уменьшить время простоя с 4 дней до нескольких минут в год. Кроме этого системное ПО поддерживает единую файловую систему во всей двухуровневой распределенной внешней памяти с постоянным копированием файлов, например в централизованный файл-сервер, чтобы при отказе любого узла другой узел мог бы перехватить и завершить прерванную прикладную программу. Применяется комплекс системных программ: ОС Linux,MPI, менеджер ресурсовFLAME, система управления заданиямиGlobusToolkit. Обязательным компонентом системного ПО кластеров является планировщик заданий, главными задачами которого являются: - обеспечение равномерной загрузки процессорных блоков; -планирование размещения программ и данных по процессорным блокам и памятям: основной оперативной и внешней на локальных дисках; -корректировка плана размещения при отказах устройств. 3.5.3.2. Перспективы развития мультикомпьютеров Созданные MPPиCOWсистемы показали принципиальную возможность существенного повышения производительности на основе массового параллелизма и достижения очень высоких ее пиковых (потенциальных) значений 1-100 Тфлопс без перегрева микросхем на тактовых частотах до 1 Гц. Это не придел. Следующий скачок пиковой производительности по- видимому возможен при замене однокристальных процессорных блоков, содержащих сейчас 1-2 многоразрядных микропроцессора, на многопроцессорные платформы на одной полупроводниковой пластине. К сожалению программные средства отстают от технических средств. Операционные системы разбиваются такими же темпами, как и технические средства, и гарантируют достижение высокой пиковой производительности. Внедрены распределенные многоуровневые ОС, в том числе программы поддерживающие отказоустойчивые вычисления, например в MPPсистемахCrayT3Eи в кластерах. Большие трудности встретились при создании программных средств автоматизации параллельного программирования: распараллеливающих компиляторов и систем параллельного программирования. Параллельное программирование MPPмультикомпьютеров требует высокого искусства даже на этапе планирования субоптимального размещения фрагментов программ и массивов данных по процессорным блокам. Главная проблема состоит в том, как обеспечить хорошую загрузку всех процессоров. В статике до начала обработки программ ее решают путем субоптимального разбиения сложных программ на параллельно и последовательно исполняемые фрагменты, размещения их в процессорных блоках и составления расписания их асинхронного параллельного запуска в разных процессорах, а также проработки всех режимов их принудительной и взаимной синхронизации и предотвращения тупиков. Для решения всех этих задач параллельному программисту недостаточно знания алгоритмических языков высокого уровня, требуются знания и навыки преобразования алгоритмов и программ, а подчас и математические научные исследования для разработки новых математических методов параллельных вычислений и алгоритмов. Несмотря на высокую наукоемкость и трудоемкость параллельного программирования пока не удалось преодолеть следующие трудности: - для ряда уникально сложных задач (а именно на них ориентированы мультикомпьютеры) не удается в статике локализовать данные программных фрагментов в локальной памяти каждого процессорного блока, и поэтому в динамике параллельной обработки требуется интенсивная пересылка распределенных данных с большим объемом межпроцессорных обменов данными; -занятость ресурсов системы в динамике обработки зависит от конкретных наборов входных данных. Программисту в статике практически невозможно справиться с учетом особенностей поведения системы на разных наборах данных, так как при числе процессоров более 100 он имеет дело с очень сложной системой реального времени, временная диаграмма работы которой зависит от конкретных значений входных данных. Кроме названных ограниченных возможностей интеллекта программистов, имеются объективные причины снижения загрузки процессоров в мультикомпьютерах: -потери времени на пространственное перемещение данных из одной локальной памяти процессорного блока в другую в другом блоке, в ходе которого процессоры вынуждены простаивают; -дополнительные к названным потери времени на синхронизацию, приводящую к блокировкам (приостановкам) программ в одном из процессоров в связи с тем, что данные его процесса могут использоваться другим удаленным процессом только в соответствии с очередностью, заданной алгоритмом второго процесса. Все это привело к существенному падению реальной производительности мультикомпьютеров по сравнению с пиковой при увеличении числа процессоров более 128-ми из-за уменьшения загрузки каждого из них. На отечественном кластере МВС-1000М выполнены продолжительные тщательные исследования его производительности на множестве тестовых задач при разном числе задействованных процессоров и получена следующая зависимость. Здесь Пр1-это производительность на один процессор, т.е. общая производительность системы, деленная на число задействованных процессоров Nпр. Конечно, в среднем даже при Пр1=50Мфлопс и Nпр=256 ускорение составило =256*50/300=43 раза, а могло быть по закону Густафсона около 200 раз. В результате этих исследований группой наших ученых из института проблем информатики РАН во главе с академиком Бурцевым В.С. экспериментально на имитационной модели и на тех же тестовых задачах доказано, что, если применить потоковую и макропотоковую архитектуру мультикомпьютера, то степень загрузки процессоров составит не менее 90%. Разработана структурно-функциональная организация потокового мультикомпьютера, которая является развитием динамической потоковой ВС с помеченными токенами (см. рис.15.12 основного учебника [1]). Завершается разработка микросхем блоков системы. В этой системе исключена коммуникационная сеть и необходимость обмена сообщениями между процессорами через сеть связи. Вместо нее используются простые мультиплексоры и демультиплексоры и обратная связь через ассоциативную память с выхода на вход ансамбля процессорных блоков. В результате синхронизация асинхронных параллельных вычислительных процессов и их диспетчеризация выполняется автоматически аппаратными средствами в динамике исполнения и взаимодействия фрагментов сложной программы через цепь обратной связи. Все устройства обратной связи организованны в виде многоступенчатого конвейера, а число таких параллельных обратных связей через ассоциативные памяти доведено до числа обрабатывающих процессоров. Это позволило снизить коммуникационную задержку при обмене данными между процессорными блоками. Главное преимущество этой потоковой архитектуры состоит в том, что программисту не нужно заботиться о загрузке параллельных процессоров путем трудоемкого программирования коммуникаций между процессорными блоками и операторов синхронизации вычислительных процессов. А это, как указано выше, и есть основные практически непреодолимые трудности параллельного программирования мультикомпьютеров с передачей сообщений. К сожалению программирование потоковой ЭВМ возможно пока только на неалгоритмическом языке высокого уровня. В настоящее время уже имеется язык потокового параллельного программирования Sisal(язык однократного присваивания), и новые программы вполне могут разрабатываться на этом языке. Остается нерешенной проблема использования громадного объема старых наследуемых последовательных программ (общей стоимостью более 3-х триллионов долларов) в новых мультикомпьютерах. Не менее дорогая проблема переучивания армии программистов с последовательных алгоритмических языков на параллельные. Пути решения этих проблем намечены. Наиболее просто они могут быть решены при использовании в мультикомпьютерах макропотоковой архитектуры, когда фрагменты последовательных программ, полученные в результате их распараллеливания, останутся в виде последовательных программ и будут исполняться процессорами фон Неймана. Организация их параллельной обработки будет выполняться по потоковому принципу по степени готовности их входных операндов. Для этого сейчас создаются распараллеливающие компиляторы, способные распараллеливать как уже оттранслированные программы, так и некомпилированные программы, написанные на традиционных алгоритмических языках. Тогда и программисты, не владеющие искусством параллельного программирования, смогут решать задачи на мультикомпьютерах, получая выигрыш в скорости. В результате будет снижена наукоемкость и трудоемкость параллельного программирования мощных мультикомпьютеров и от программистов супер-ЭВМ не потребуется очень высокого искусства программирования ради высокой загрузки процессоров. Поскольку мы говорим о задачах уникальной сложности, возникает вопрос, готова ли сегодня наша техника решать такие сложные задачи, к которым еще вчера человечество и не пыталось подступиться. Ответ утвердительный в связи с широким внедрением Интернета. Уже имеется опыт его использования для территориально-распределенного параллельного решения таких задач в режиме метакомпьютера. Пока это добровольные объединения множества рабочих станций и кластеров для решения задач с громадной вычислительной сложностью. Например, сегодня 200 тысяч пользователей Интернета предоставляют свои компьютеры для распределенного решения задач раскрытия криптографических шифров (http://www.Distributed.net/.). Десятки тысяч ЭВМ по всему миру отдают свои ресурсы для поиска очень больших простых чисел Мерсена таких, как , где степеньp-это простое число. Уже найдено самое большое простое число (). Предлагается приз 100 000 $ тому, кто сможет в этом режиме территориально-распределенной параллельной обработки найти простое число Мерсена с 10 миллионами цифр (http://mersenne.org/). Создаются Web- интерфейсы к сложным программам, ранее созданным и отлаженным, а сейчас введенным в метакомпьютинг. Наименование системы:UNICORE. Адрес:http://www.fz-juelich.de/unicore/. До сих пор мы уделяли внимание решению задач уникальной сложности. В тоже время большинству организаций, вузов, НИИ, КБ и предприятий невыгодно приобретать дорогие супер-ЭВМ стоимостью 10-16 млн. долл. и содержать штат математиков и программистов, но решать все более сложные задачи необходимо. В них давно сложился опыт применения ЭВМ на основе стандартного ПО и мощных библиотек отлаженных пакетов прикладных программ, доступных пользователям и программистам средней классификации. В результате накоплен громадный объем последовательных программ для однопроцессорных ЭВМ, но сами однопроцессорные машины устарели и сдерживают как повышение скорости обработки, так и возможность дальнейшего усложнения решаемых задач, а главное расширение сферы эффективного использования ЭВМ и рынка сбыта. Пути развития этой сферы массового применения ЭВМ уже определены. Электронная промышленность готова при условии массового производства выпускать дешевые микросхемы высокой степени интеграции (100-150 млн. транзисторов на кристалле). Это позволяет внедрить в ЭВМ широкого назначения параллельную элементную базу. Если же не снизить наукоемкость и трудоемкость параллельного программирования, то это может стать препятствием для ее широкого внедрения. Эту нишу сейчас заняли суперскалярные и VLIWEPICмикропроцессоры с избыточными по числу однотипных обрабатывающих устройств и функционально-распределенными АЛУ. Они снабжаются компиляторами полуавтоматического распараллеливания последовательных программ на уровне команд, а в суперскалярных МП применяются дополнительные аппаратные средства, которые автоматически извлекают из последовательных программ в динамике их исполнения замаскированный ранее в них параллелизм команд. Это позволяет повысить производительность массовых рабочих станций до 10 раз. Следующим шагом будут многопроцессорные мультискалярные микропроцессоры с небольшим числом процессоров (около 16). Если их построить на суперскалярных процессорах и по макропотоковой архитектуре, что можно использовать и мелкозернистый параллелизм (на уровне команд), и среднезернистый параллелизм (на уровне программ). Первый автоматически будет извлекаться в последовательных фрагментах суперскалярными процессорами. Второй – путем распараллеливания исходных последовательных программ и исполнения их параллельных фрагментов по степени готовности входных операндов. Это позволит повысить производительность рабочих станций до 100 раз. Если удастся выполнять распараллеливающую компиляцию автоматически, например в мощных серверах со специальными акселераторами комбинаторной оптимизации разбиения на фрагменты, то и программистов переучивать не потребуется, так как сохранится возможность написания новых программ на традиционных алгоритмических языках последовательных ЭВМ. 3.6 Архитектуры параллельных микропроцессоров Как следует из оценки перспективы автоматизации параллельного программирования автоматизацию распараллеливания наследуемых последовательных программ на уровне команд целесообразно осуществлять непосредственно в микропроцессорах, а автоматизацию крупнозернистого и среднезернистого распараллеливания на уровне заданий и программ - на мультикомпьютерном уровне параллельных ВС. Такой путь развития архитектур мультикомпьютеров широкого назначения сложился в настоящие время. Очевидно, что при таком подходе придется пойти на существенное усложнение аппаратных средств микропроцессоров. Микроэлектронная промышленность с этой задачей справилась и сейчас серийно выпускаются сложные параллельные микропроцессоры с числом транзисторов на кристалле 10-100 миллионов. Микропроцессоры, в которых распараллеливание на уровне команд выполняется автоматически аппаратными средствами, называются суперскалярными. Как показал опыт их эксплуатации, ускорение обработки старых наследуемых последовательных программ составило в среднем 2-8 раз по сравнению с процессорами фон Неймана старой неизбыточной архитектуры, работающими на такой же тактовой частоте. Теоретический анализ и имитационное моделирование показали, что при распараллеливании на уровне команд возможно ускорение до 10 раз. Таким образом, удалось, не потеряв этой возможности ускорения, освободить программы распараллеливающего компилятора от рутинной работы и сосредоточить их внимание на решении более важной задачи распараллеливания на уровне программ, где ожидаемое ускорение при макропотоковой обработке выделенных параллельных ветвей может составить не менее, чем 100 раз, и в итоге в целом добиться ускорения в 1000 раз. Это позволяет на данной стадии развития микроэлектроники решить многие из сложных задач, поставленных перед нами и описанных в п.3.5.2, без перегрева микросхем. Такой подход нельзя считать единственным генеральным путем вычислительной техники. Например, предстоящий переход на новую технологию микросхем на основе бимолекулярных чипов, который позволит повысить степень интеграции в 1000 раз и существенно упростить решение проблемы отвода тепла, может многое изменить в идеологии архитектур. Кроме того, при создании параллельных средств специализированной вычислительной техники совершенно не обязательно придерживаться этого сложившегося субоптимального пути развития мультикомпьютеров широкого назначения. Мы с Вами в этом убедимся в следующей учебной дисциплине: «Специализированные процессоры, машины и сети». Так как суперскалярные микропроцессоры в настоящие время – это основная элементная база для создания процессорных блоков мультикомпьютеров, нам необходимо их изучить и оценить их возможности. 3.6.1 Архитектура суперскалярного процессора Суперскалярным процессором (впервые так назван в 1987 году) называется центральный обрабатывающий процессор, который за один конвейерный такт конвейера команд одновременно выполняет более, чем одну скалярную команду, и в настоящие время – от 4-х до 8-ми RISCкоманд. Исторически появление суперскалярных процессоров связано с переходом в микропроцессорах от CISCархитектур с полным набором команд кRISCархитектурам с сокращенным наборам команд. Главные отличияRISCархитектуры: - максимально сокращено число команд, имеющих доступ к кэш и основной оперативной памяти, и введены специальные команды обращения в память: команды «Чтение» и «Запись»; -все основные команды являются командами типа «регистр-регистр»; - длины всех команд стандартные однословные, равные ширине шине данных, что позволило унифицировать конвейер команд; - число форматов команд минимальное: не более 4-х; -число способов адресации не более 4-х; -число команд сравнительно невелико: не более 128-ми; -75 % процентов команд при конвейерной их обработке выполняются за один конвейерный такт; -25% процентов команд выполняется по подпрограммам, составленным в основных коротких RISC-командах, расходуя в среднем 4-5RISCкоманд на эмуляциюCISC-команды; - сравнительно большой файл регистров общего назначения: от 32 до 512; - устройство управления обязательно реализуется на «жесткой» логике и оно гораздо (в 5 раз) проще и более быстродействующее, чем в CISCпроцессорах. Хотя RISC-программы в среднем на 30% длиннееCISC- программ, они выполняются в 1,5 раза быстрее, чемCISC- программ. Переносимость старых CISC-программ, т.е. преемственность программного обеспечения, достигается путем встраивания вRISC-процессоры аппаратного транслятораCISC-команд вRISC- команды. Таким образом, в системе командRISC- процессора появляются команды, отсутствовавшие вCISC–процессорах: «Чтение» (иногда называются «Загрузка» в регистры); «Запись» (иногда называется «Сохранение» результатов в кэше данных); «Переход». После перехода к RISC-архитектуре и широкого внедрения конвейера команд с шестью стадиями (ступенями): -выборка команды; -декодирование КОП; -вычисление адреса операнда; -выборка операнда; -исполнение команды; -запись результата; было замечено, что самой длительной ступенью является пятая «исполнение команды» и она определяет длительность конвейерного такта синхронного конвейера: Tk=max=t5 При этом 4-я стадия для всех RISC-команд завершается гораздо быстрее, чем 5-я, т.е. 1-4-я ступени конвейера команд простаивают и могли бы за времяt5 конвейерно подготовить к исполнению несколько команд. Тогда для первых 4-х стадий нужно выбрать свой более короткий конвейерный тактTk1=max,который в среднем оказался в 4-5 раз меньше, чемt5ср,Tk1≈1/5t5ср. Следовательно, первые четыре ступени могут заготовить операнды не на одно АЛУ, а на 4-5 АЛУ. Если быстро записать результаты всех 5-ти АЛУ в память, а вRISC-архитектуре это возможно, так как результаты записываются только в регистры или в быструю кэш-память данных, то на 5-й ступени конвейера команд можно организовать параллельную работу нескольких АЛУ с фиксированной запятой и дополнительных функциональных блоков типа «переход», «запись», «чтение». Далее стало очевидным, что параллельно с ним в 5-й ступени можно включить конвейерные АЛУ с плавающей точкой. Тогда на операциях с плавающей точкой конвейер команд удлинится на 4-ре ступени, так как конвейер с п.3. содержит 5 ступеней, его общая длина составит до 10 ступеней. Структура суперскалярного конвейера команд Эта идея новой организации конвейерного процессора появилась в 1987 году и успешно была внедрена в отечественной супер-ЭВМ «Эльбрус». Но от идеи до серийного выпуска суперскалярных микропроцессоров прошло еще 8-10 лет. За это время было доказано и реализовано, что с помощью встроенных дополнительных средств можно автоматически выявлять скрытый в последовательных программах однопроцессорных фон Неймановских машин параллелизм на уровне команд и за счет этого повысить скорость их обработки в среднем в 2-8 раз. Эти аппаратные средства оказались весьма сложными и потребовали для своей реализации до 3-4 млн. транзисторов. Рассмотрим основы их функциональной организации. Блок предсказания переходов введен для повышения пропускной способности конвейера команд на основании истории переходов, а также для снижения частоты промахов при обращении в кэш- память команд. Это позволяет выполнять команду по предположению (агрессивно на недостоверных «спекулятивных» операндах) с опережением по отношению к моменту времени окончательного определения направления условного перехода, от которого данная команда зависит. Блоки 6, 7, 11 предназначены для выявления скрытого параллелизма команд в наследуемых последовательных программах однопроцессорной ЭВМ фон Неймана и организации параллельной обработки распараллеленных RISC-команд. Основные виды скрытого параллелизма, выявляемого аппаратными средствами суперскалярного процессора: -независимость между командами на линейных участках программ; -возможность изменения порядка последовательной обработки независимых команд. В старых последовательных программах фактически независимые между собой команды вынужденно из-за наличия только одного АЛУ искусственно объединяются в последовательные линейные участки (ветви). При этом с целью экономии регистровой памяти один и тот же регистр и одна и таже ячейка ОП последовательно путем замещения содержимого используется вначале для хранения значения одной переменной, а после его использования замещается значением другой переменной. Из-за этого фактически независимые команды условно считаются информационно связанными. Например, исходный последовательный участок 1.A=B+C, 2.B=A+E, 3.A=X+Y, 4.F=A*Z. организован как последовательный линейный путем занесения на третьем шаге в одну и ту же ячейку А результата обработки новых переменных XиY, не связанных с предыдущим отрезком участка. Если ввести дополнительную переменнуюA1 и дополнительный регистр для хранения ее значения, то эти два последовательных отрезка линейного участка можно выполнить параллельно: 1. A1=B+C, 1. A=X+Y, 2. B=A1+E 2. F=A*Z. Такой способ преобразования последовательных участков в несколько параллельных отрезков называется метод переименования регистров(или переменных). Переименование регистров может не потребоваться, если на линейном участке исходной последовательной программы независимые отрезки искусственно объединены программистом в одну линейную ветвь. Такие отрезки выявляются в динамике исполнения программы на основе принципа потоковой обработки по степени готовности их операндов. При диспетчеризации команд создается буфер команд (окно исполнения) и постоянно выполняется проверка готовности их операндов. Любая из команд буфера направляется на обработку как только будет готовы ее операнды. В этом случае может измениться очередность обработки команд по сравнению с порядком их исполнения, предусмотренным программистом наследуемой последовательной программы. В то же время такой принцип направления команд на обработку позволяет естественно перейти от последовательной их обработки к параллельной. Этот метод выявления скрытого параллелизма называется переупорядочиванием команд. Конечно, после исполнения команд нужно обязательно восстановить упорядоченную последовательность результатов перед их записью в кэш-память данных. Восстановление можно выполнить, если сохранить во входном буфере команд в блоке 6 исходную последовательность команд обрабатываемой программы. Очевидно, что перед переупорядочиванием команд нужно в начале выполнить распараллеливание путем переименования регистров. Оно выполняется путем выявления типа зависимости по данным: ЧПЗ - чтение после записи, ЧПЧ - чтение после чтения, ЗПЗ - запись после записи, ЗПЧ - запись после чтения. ЗПЗ и ЗПЧ - это лишние зависимости, которые появляются в исходных последовательных программах из-за ограниченного числа регистров общего назначения, недостаточной емкости ОП и наличия программных циклов. Тогда если фактически, как в RISC-процессорах, или виртуально увеличить число РОН, запись можно выполнять в любой другой регистр, а не в тот же как в ЗПЗ и ЗПЧ, и тем самым удалить эти лишние зависимости по данным. После выполнения в конвейере команд этапа декодирования команды по коду операции должен быть выбран требуемый функциональный обрабатывающий блок, созданы указатели на операнды и на место помещения результата и затем выполнена выборка операндов. В связи с возможностью аннулирования результатов команд при неправильном предсказании перехода, из-за переименования регистров и переупорядочивания команд в суперскалярном процессоре чаще всего применяется неупорядоченная выдача команд на исполнение и неупорядоченное их завершение. При выдаче команд необходимо распределить готовые команды по требуемым функциональным блокам с учетом их занятости. Эта функция называется диспетчеризацией. С целью упрощения диспетчеризации на входах функциональных блоков устанавливаются буферы распределения, в которых хранятся очереди готовых команд (декодированный КОП и готовые значения операндов), например в изображенной структуре требуется 6 параллельных буферов небольшой емкости (не более 5-ти команд в каждом). На однотипные блоки: на 2АЛУ с п.з. и на 2 АЛУ с ф.з. достаточно по одному буферу. Готовые команды из буферов распределения считываются периодически в каждом конвейерном такте конвейеров с плавающей запятой. При этом в блоках с ф.з. они исполняются за одним такой конвейерный такт, а в блоках с П.З - за 5 конвейерных тактов. Готовые команды передаются в требуемые буферы распределения блоком 6 диспетчера команд с учетом значения кода их КОП. Функции переименования регистров, переупорядочивания и диспетчеризации команд выполняются обычно одним сложным блоком, который называется резервирующей станцией. Основой этого блока чаще всего является кольцевой регистровый FIFO-буфер с перемещаемыми указателями «начало-конец» очереди ипамять таблицы соответствия, в которой ведется учет местоположений операндов, а именно каждой исходный операнд и какой результат команды, находящейся вFIFO-буфере, хранится в данный момент времени в каком физическом регистре или в каком элементеFIFO-буфера. Эти места хранения операндов устанавливаются после декодирования каждой команды и заносятся в таблицу соответствия. При этом используется механизм динамического отображения логических ресурсов старых программ на физические ресурсы новых микропроцессоров. Каждая команда создает новое имя физического регистра дляисходного логического регистраи помещает в него свой операнд или результат. Если последующие команды используют это же значение, то они при декодировании получают в процессоре это же новое имя физического регистра. Эта процедура называется переименованием регистров. В процессорах с FIFO-буферами числоиспользуемыхфизических регистровPOHвсегда выбирается равным числу логических регистров программы. Требуемые дополнительные регистры для переименования используются не из числа РОН, а из FIFO– буфера. Операнды могут находиться либо в физических регистрах, либо временно вFIFO- буфере. В нем всегда хранятся результаты выполненных команд, пока они не достигнут «начала» очереди в буфере. Этот же буфер используется и для переупорядочивания, и для диспетчеризации команд. Его емкость ограничена и рассчитана на 5 -10 команд. Если буфер заполнен, то диспетчеризация приостанавливается до освобождения хотя бы одного места. Процедура переименования регистров инициализируется после декодирования каждой очередной команды и завершается определением места хранения ее результата. Для этого ассоциативно просматриваются логические адреса (левая часть таблицы соответствия) и сравниваются с логическим адресом результата, указанным в коде команды. Если такая строка в таблице соответствия уже имеется, это значит, что по адресу, указанному в правой ее части уже выполнена запись, а возможно и было чтение. Следовательно, по этому месту записывать новое значение результата нельзя, иначе сохранится лишняя зависимость между командами типа ЗПЗ и ЗПЧ. Тогда начинает заполняться новая строка в таблице соответствия, и этот же логический адрес записывается в левую часть свободной строки таблицы, а правая ее часть пока остается пустой (неопределенной). Затем декодированный КОП этой команды записывается в кольцевойFIFO-буфер. Формат ее записи: минимальной длины . По-видимому, длину записи команды придется увеличить для того, чтобы реализовать все функции резервирующей станции. Эта новая команда заносится в конецFIFO - очереди, поймав при циклическом сдвиге содержимого буфера отметку «конец» очереди и перенеся эту отметку на новую команду. Одновременно по счетчику числа сдвигов от подвижного «начала»FIFO-очереди определяется адрес вFIFO– буфере для записи результата этой команды и копируется в правую часть новой строки таблицы соответствия. Отметки «начало» и «конец»FIFO-очереди в буфере обнаруживаются при прохождение мимо неподвижного окна по ходу циклических сдвигов содержимогоFIFO-буфера. Аналогично по счетчику, сбрасываемому отметкой «начало», легко найти в дальнейшем это же место для последующей записи или чтения значения результата какой-либо команды, адресуемого содержимым правой части строки таблицы соответствия. Итак, имеется два возможных места хранения результата команды либо в регистре РОН, либо вFIFO-буфере. Место его хранения в РОН назначается и заносится в таблицу соответствия, если при ассоциативном ее просмотре его логическим адресом такой заполненной строки не обнаружится т. е строка соответствия выносится впервые. В таблицу заносится содержимое счетчика занятых регистров РОН с инкрементом +1 в строку, поименованную в левой части логическим адресом результата. Исходные данные, читаемые из кэш-памяти данных, записываются в регистры РОН, а их местоположение описывается аналогично в таблице соответствия < логический адрес-адрес физического регистра >. Каждая очередная декодированная команда по результату обращения в таблицу соответствия логическими адресамисвоих операндов может оказаться в двух возможных состояниях:готовак использованию,не готова. Проверка готовности выполняется очень просто. Если после ассоциативного опроса левой части таблицы логическим адресом операнда такая строка в таблице найдена, то этот операнд готов, а по содержимому ее правой части ясно, где он хранится: в регистре или вFIFO-буфере. Если оба операнда по таблице соответствия готовы, команда готова к исполнению. Рассмотрим вначале принцип обработки такой готовой команды. Аналогично предыдущему, опрашивая таблицу соответствия логическим адресом результата, заполняется новая ее строка и в случае необходимости выполняется переименование регистра. Если можно запланировать помещение ее результата без переименования в регистр РОН, то готовая команда сразу же направляется на исполнение, а именно по ее декодированному КОП находится буфер распределения и туда переносятся значения ее операндов либо из РОН, либо изFIFO-буфера. Адреса этих операндов, как известно, имеются в правой части таблицы соответствия и находятся в результате обращения в таблицу по логическим адресам операндов команды. После исполнения команды – вновь обращение в таблицу логическим адресом ее результата и запись результата по адресу в правой ее части, либо в регистр РОН, либо вFIFO-буфер. Следовательно, логический адрес результата также нужно хранить в буфере распределения и извлекать его оттуда после окончания исполнения очередной команды. Если декодированная команда оказалась неготовой, т.е. в таблице соответствия нет указателей на место хранения одного или обоих ее операндов, она должна ожидать пока не будут готовы операнды. Тогда ее код заносится вFIFO-буфер вFIFO-очередь. Она будет циркулировать в кольцевомFIFO - буфере до тех пор, пока в таблице соответствия не появятся ссылки на места хранения ее операндов. Следовательно, вFIFO-буфер нужно записывать и логические адреса ее операндов (один или два). Если заносится два, то после проверки готовности и наступления готовности одного из операндов его логический адресFIFO- буфере нужно отмечать тегом готовности. Готовность операндов проверяется и уточняется в момент прохождения при циклическом сдвиге мимо неподвижного окна. Если логические адреса операндов еще не отмечены тегами готовности, тогда сдвигFIFO-буфера приостанавливается, неготовый логический адрес считывается изFIFO-буфера, по нему выполняется обращение в таблицу соответствия, и, если оно было успешным, данный логический адрес вFIFO-получает тег готовности, аFIFO-буфер продолжает циклические сдвиги. Если же оба логических адреса тегированы как готовые, то по декодированному КОП быстро находится требуемыйбуфер распределения, куда путем переадресации через таблицу соответствия переписываются из РОН илиFIFO-буфера значения операндов, и команда наконец уходит на исполнение. Результат ее будет записан либо в РОН, либо вFIFO-буфер с учетом переадресации по его логическому адресу через таблицу соответствия, а эта строка переадресации, как известно, создается сразу же после декодирования команды. Следовательно, логический адрес результата тоже нужно хранить вFIFO-буфере по всемнеготовымкомандам и переписывать его в буфер распределения вместе со значениями готовых операндов. Любая готовая и уже исполненная команда стирается в кольцевом FIFO-буфере только после фиксации достоверных ее результатов, заключающейся в записи ее результатов в выходной буфер восстановления последовательности. По принципуFIFO-очереди она всегда в «начале» очереди. Как только при циклическом сдвиге она появится в неподвижном окне, содержимое ее ячейки стирается, а метка «начало очереди» переносится на следующую ячейку буфера. ПереполнениеFIFO-буфера обнаруживается, когда в неподвижном окне за меткой «конец очереди» сразу же появится метка «начало очереди» в соседней ячейке кольцевого буфера. Тогда диспетчеризация команд приостанавливается путем приостановки конвейера команд. Несколько иная ситуация с удалением из FIFO-буфера команды, внесенной в него по процедуре переименования регистров. Она сохраняется в регистре до тех пор, пока значение ее результата не будет использовано, т.е. не только будет выполнено его копирование в один из буферов распределения, но и команда, его затребовавшая, не будет исполнена, а результат последней не будет записан. Только после этого команда-источник переименованного операнда стирается вFIFO-буфере, а значение ее результата переписываются в тот регистр РОН, который по таблице соответствия соответствует месту хранения логического результата. Это необходимо для того, чтобы, во-первых, исключить использование в качестве операнда устаревшего значения логического регистра и, во-вторых, не допустить, чтобы очередная команда из-за нарушения последовательности выполнения команд занесла свой результат в регистр еще до того, как это сделала предшествующую команда, т.е. не нарушить последовательность использования с замещением записей одного и того же логического регистра, предусмотренную исходной последовательной программой. ВFIFO-буфере команды сохраняются дофиксацииих результатов в выходном буфере восстановления последовательности. Значения условных переходов, вычисленные по команде перехода,не фиксируются, а используются для управления очисткойFIFO-буфера от неправильно предсказанных команд и их ложных результатов, также еще не зафиксированных. Поэтому, когда команда условного перехода достигает начала очереди вFIFO-буфере и выясняется, что предсказание было неправильным, содержимое буфера гасится, и начинается выборка команд из другой ветви. Так как вFIFO-буфере циркулируют команды разных типов: внесенные по переименованию, неготовые команды, а некоторое время и готовые команды, а также ложные неправильно предсказанные команды, в общем случае нужно команду хранить в его ячейке в широком формате < декодированный КОП; тег, логический адрес операнда; логический адрес результата; место для записи значения результата >. Утешает только то, что число хранимых команд (окно исполнения) невелико: 5-10 команд. Таким образом, с целью обеспечения максимальной загрузки параллельных функциональных блоков в суперскалярном процессоре применяется неупорядоченная выдача и неупорядоченное завершение команд. Поэтому на выходе перед записью результата в кэш – данных их нужно упорядочить в соответствии с логической их адресацией, предусмотренной в исходной программе. Это сделать сравнительно просто по таблице соответствия с помощью дополнительного буфера восстановления последовательности. При перезаписи из регистра РОН в этот буфер нужно ассоциативно адресом регистра обратится теперь в правую часть таблицы соответствия, а из левой части найденной строки прочитать истинный логический адрес значения этого регистра РОН и передать его в выходной буфер вместе со значением, а далее использовать как адрес в памяти данных при записи в КЭШ. 3.6.2 АрхитектурыVLIW-иEPIC-микропроцессоров. Альтернативой рассмотренному суперскалярному микропроцессору считается VLIW-микропроцессор с командными словами сверхбольшой длины (VeryLongInstructionWord), в котором отсутствуют аппаратные средства автоматического распараллеливания на уровне команд. Вместо этого эффективное планирование параллельного выполнения нескольких команд возлагается на сложный программный «разумный» компилятор. Он вначале исследует исходную программу с целью обнаружения таких групп команд, которые могут быть выполнены одновременно, причем так, чтобы это не приводило к конфликтам. В процессе анализа компилятор даже делает пробные исполнения распараллеленных участков (профилирование). На следующем этапе компилятор пытается объединить группы подобранных команд в пакеты, каждый из которых рассматривается как одно командное слово сверхбольшой длины. При этом число простых объединяемых команд не должно превышать числа имеющихся в процессоре параллельных исполнительных функциональных блоков, и желательно, чтобы эти числа совпадали. В сверхдлинную команду объединяются только такие простые команды, которые могут одновременно исполнятся имеющимися разными функциональными блоками. Варианты таких «разумных»VLIW-компиляторов уже эксплуатируются. Основные их недостатки – неполное извлечение скрытого параллелизма, меньшая степень загрузки параллельных функциональных блоков, чем в суперскалярном процессоре, невозможность достаточно точного предсказания переходов в статике (точность предсказания в среднем 80%) в то время, как аппаратные предсказатели суперскалярных процессоров предсказывают в динамике с точностью не хуже 97%. Основные подкупающие преимущества VLIW-процессоров – это большое снижение аппаратной сложности по сравнению с суперскалярным процессором (на миллионы транзисторов), так как в них не требуется резервирующие станции, в том числе переупорядочивающиеся буферы, буферы распределения, таблицы соответствия, буфер восстановления, а также блок предсказания переходов. Компилятор исключает возможность конфликтов между простыми командами, включенными в состав длинного командного слова. ПоэтомуVLIW-процессоры имеют большее быстродействие, чем суперскалярные. Благодаря появившемуся резерву места на кристалле число параллельных функциональных блоков увеличено в современныхVLIW-и их развитииEPIC- процессорах до 20-ти, и длина сверхдлинной команды колеблется от 256 до 1024 бит. К сожалению, современные компиляторы не справляются с загрузкой всех функциональных блоков даже при одновременной мультипрограммной обработке смеси команд нескольких разных программ. Поэтому в серийныхVLIW- микропроцессорах (ЦПС и мультимедийный МП), например в ЦПСTMS320C6201 число функциональных блоков и простых команд в длинном составном командном слове (256 бит) равно 8-ми. Структура VLIW-микропроцессора TMS320C6201 РФА, РФВ - регистровые файлы. L,S,M,D-исполнительные функциональные блоки: сдвига, сложения (логических операций), умножения, адресные операции. КПДП - контроллер прямого доступа в память данных. ИНП - интерфейс наружного ОЗУ. ПРП - параллельный порт хост-машины (ведущей ЭВМ). БПСП - буферизированный последовательный порт. Дальнейшим развитием VLIWархитектуры стала новая архитектура микропроцессоровEPIC(ExplicitlyParallelInstructionComputing) типаIA-64 с 64-х разрядной целочисленной арифметикой, так называемые вычисления с явным параллелизмом команд. Принципиальные отличия архитектуры IA-64(EPIC): -увеличенная разрядность данных: 64 разряда с фиксированной запятой, 80 разрядов с плавающей запятой; -большое количество регистров общего назначения (РОН): 128 регистров с Ф.З. и 128 регистров с П.З.; - усовершенствованы форматы простых составных команд где три команды в связке (пучке) независимы между собой и не конфликтуют друг с другом. Предикат и шаблон определим ниже. -возможность удлинения VLIWпутем объединения пучков; -компилятор усложняется по сравнению с VLIW-микропроцессорами: кроме выявления параллелизма команд, он переупорядочивает команды, выявляет связи между ними, переименовывает переменные, формирует пучки по три с шаблоном, связывает в более длинное командное слово несколько пучков, планирует в статике доступность и занятость параллельных функциональных блоков; - расширено физическое адресное пространство: применены 64- х. битные адреса; - применены спекулятивная загрузка операндов в исполнительные функциональные блоки и новый способ обработки условных переходов на основе предикации, причем для хранения однобитовых предикатов (1 или 0) дополнительно в процессор включены 64-ре одноразрядных регистров предикатов, адреса которых указываются в поле «предикат» каждой простой команды. Рассмотрим основные усовершенствования, внесенные в архитектуру IA-64. Заключительное поле «шаблон» в формате пучка 3-х простых команд заполняются компилятором, и содержит код описания вида зависимости между тремя простыми командами данного пучка, а именно: какие из 3-х можно обрабатывать параллельно, или какие из них только последовательно и в каком порядке друг за другом. Кроме этого путем дополнительного кодирования вида зависимости можно указывать даже аналогичные допустимые способы параллельно - последовательной обработки разных пар простых команд, вписанных в разные пучки, образующие длинное многопучковое командное слово. Например, в пределах одного пучка шаблономкомпилятор может дать указания аппаратным средствам на следующие способы параллельно-последовательной обработки трех командI0,I1,I2: 1) Io||I1 ||I2– все три команды можно исполнять одновременно параллельно; 2 Io&I1 ||I2– вначале исполнитьI0 и только после этого – параллельноI1 иI2; 3) Io||I1 &I2- вначале исполняются параллельно две командыI0 иI1 и после этого - командаI2; 4) Io&I1 &I2-команды можно исполнять только последовательно в строгой очередности:I0→I1→I2. «Спекуляция» операндами команды также планируется компилятором путем внесения в кодовую цепь объектной программы специальной команды CHECKдля загрузки операнда. Команду, конечно, исполняют аппаратные средства. Эта команда вносится в возможно ранние позиции кодовой цепи по отношению к той обрабатывающей команде, где этот операнд потребуется. Главное условие, чтобы регистр требуемого операнда был бы уже непустым к этому моменту. При этом не обращается внимание на то, является ли это значение окончательным, или оно еще будет уточняться повторными записями в этот регистр по принципу замещения. Тогда последующие команды, потребляющие этот же операнд, будут выполнены «агрессивно» на недостоверных данных и значительно раньше чем, это было бы, если бы они ожидали достоверных значений этого операнда. Они могут быть выполнены раньше, чем их результаты потребуются. Поэтому результаты таких агрессивных команд сохраняются в РОН, и они могут быть отменены, если «спекуляция» операндом оказалась неудачной. Однако путем моделирования показано, что более чем в 50% случаев, спекулятивное значение может и не уточняться до конца обработки программы, а это является дополнительным резервом повышения производительности. Проверка достоверности результатов агрессивно выполненных команд также заранее планируется компилятором с помощью механизма предикатов. Новый способ предикации в архитектуре EPIC:IA-64 является развитием применяемого в современных компиляторахVLIW- процессоров метода замены команд условного перехода командами условного исполнения. Главная причина этого состоит в том, чтоVLIW-процессоры не содержат блоки предсказания переходов. В то же время в динамике исполнения программ функции вычисления предикатов в вершинах условных переходов часто зависят от аргументов, значения которых невозможно предвидеть в статике при компиляции. Выход из этого положения прост. Так как вVLIW-процессорах имеется избыток однотипных функциональных блоков, можно пойти на агрессивное параллельное исполнение обеих выходных ветвей и в направлении по «да», и в направлении по «нет», спекулируя результатом предикатной функции, т.е считая для обоих направлений его значение, равным «да». Спустя некоторое число исполненных команд в обоих направлениях будет параллельно другими избыточными функциональными блоками завершено вычисление предикатной функции и образованы истинные значения направления перехода. В обе агрессивно исполняемые ветви компилятор вносит команды проверки «спекуляции». Их местоположение определить нетрудно, зная за сколько команд завершится вычисления предикатной функции. По крайней мере они не выходят за пределы линейных разветвлений. Как только истинное направление перехода установлено, все результаты вычислений неправильно выбранной ветви отменяются. Тем самым ограничиваются пределы распределения ложных результатов. Предикация вEPIC- процессорах - это усовершенствованный способ спекулятивно- агрессивной обработки условных ветвлений. Суть метода та же, что воVLIW-процессорах, и заключается в агрессивном параллельном исполнение обоих ветвей. Если в исходной программе встречается условное ветвление, то компилятор команды из разных ветвей помечает разными адресами двух разных однобитовых регистров предикатов (РП). Далее они выполняются одновременно разными функциональными блоками, но результаты вычислений не фиксируются, т.е. не записываются в кэш- памяти, до тех пор, пока содержимые биты регистров предиката не определенны. Когда наконец, параллельно с обработкой ветвей вычисляется условие ветвления, то значения в РП, соответствующим «правильно» обработанной ветви, устанавливается в «1», а другой «неправильной» ветви – в «0». Перед записью результатов в кэш- память процессор проверяет содержимые регистров РП, адресуемых через поле предиката в командах, и записывает в память результаты только тех команд, поля предикатов которых указывают на РП с единичными значениями. Результаты команд, ссылающихся через предикаты на РП с нулевыми значениями, считываются неправильными, в кэш-память не записываются и стираются в регистрах РОН. Тем самым устраняется условный переход по операнду if, а команды ветвей по обоим переходам сливаются в одну линейную последовательную ветвь в виде цепи команд с предикацией. Причем в процессоре две команды с разными адресами регистров РП в полях предикатов могут исполнятся параллельно разными функциональными блоками, т.е . будут компилятором включены в один пучок кодом его шаблонаI0 ||I1 ||I2, гдеI2- параллельно исполняемая третья команда вычисления условия ветвлениями и, если она заключительная в нахождении значения предикатной функции, то в ней будет в качестве адреса результата адрес регистра РП, куда она запишет «1» или «0», по которым будет принято решение, какая из двух командI0 илиI1вычислила правильный результат. Для того, чтобы аналогично сливать в одну ветвь ветвления по thenи поelse, число регистров предикатов увеличивают в два раза, и по первому направлению ветвления используются основной РП, где может быть 1 или 0, а по второму - в команду в поле предиката вписывают адрес дополнительного РП, куда записываются инверсные значения условий перехода: 0 или 1 соответственно. Например, если исходная программа с оператором ifимеет вид: If (R1= =R2) R3=R4+R5 Else R6=R4-R5, то в Ассемблере процессора EPICпосле компиляции с предикацией она примет вид: CMPEQ R1, R2, P4 ADD R3, R4, R5 SUBR6,R4,R5. CMPEQ-дополнительная командаEPICсравнения содержимых двух регистров и записи в предикатный регистрP4: «1» приR1=R2, «0» приR1≠R2. По этой же команде по умолчанию в соседний РП с адресомP5 заносится инверсное значение признака: «0» или «1» соответственно. Очевидно, при этом из двух последовательных команд исполняется только одна, а другая могла быть пропущена в однопроцессорной ЭВМ. В EPICархитектуре пропуск не делается с тем, чтобы не прерывать работу конвейера команд. Чтобы сохранить однотипность формата команды, безусловные команды также содержат поле «предикат», в котором указывается адрес одного и того же предикатного регистра, в который всегда заранее заносится код условия «1» а в парный ему – инверсное значение «0». Таким образом, используя «спекуляцию» операндами и предикацию, получили объектный программный код в виде непрерывной неразветвляющейся последовательной цепи команд с предикатами. Такой поток команд загружается в конвейер команд непрерывно без приостановок и перезагрузки конвейера, разветвляя в процессоре на пятой его ступени по параллельным функциональным блокам, если это допустимо в соответствии с шаблоном каждого пучка. При этом компилятор должен так связать по несколько последовательных длинных командных слов, чтобы параллельно с пучками типа I0&I1&I2 (последовательными) проходили бы пучки типаI0||I1||I2,I0&I1||I2,I0 ||I1 &I2, и тем самым обеспечить загрузку избыточных функциональных блоков. Все команды обрабатываются вначале, не обращая внимания на их предикаты. Но на выходе из конвейера перед записью результатов команд в кэш- данных проверяются содержимые их предикатных регистров, и сохраняется результаты только тех команд, в ПР которых значения «1», а по ПР: «0»- считаются ложными и отбрасываются. Тем самым исключаются простои конвейера команд за счет избыточности функциональных блоков, но некоторые из них всегда будут работать впустую, выполняя ложные вычисления. Существенным преимуществом VLIWиEPICархитектур по сравнению с суперскалярной считается то, что все процедуры выявления параллелизма выполняются один раз при компиляции и запоминаются в объектном программном коде, в то время как в суперскалярных микропроцессорах они выполняются аппаратно и повторяются многократно при каждом запуске одной и той же исходной программы. В то же время при создании « разумного» компилятора дляEPICархитектуры встретились большие трудности, в частности необходимость внесения в объектный код откомпилированной программы таблицы соответствия между логическими и физическими адресами регистров операндов и результатов для восстановления исходной последовательности выдачи результатов в кэш-памяти в связи с тем, что команды выполняются неупорядоченно. Поэтому пока VLIWиEPICархитектуры широко применяются при создании специализированных микропроцессоров: цифровых процессоров сигналов и мультимедийных микропроцессоров, где полуавтоматический компилятор не является препятствием, так как прикладное программирование выполняется однократно при создание специализированных микро-ЭВМ. В машинах широкого назначения необходима полная автоматизация компиляции и прикладного параллельного программирования. Поэтому процессорные блоки многопроцессорных мультикомпьютеров, серверов и рабочих станций целесообразно строить на суперскалярных микропроцессорах типа AlphaиPentium. 3.6.3 Архитектура перспективного многопроцессорного мультискалярного микропроцессора. Дальнейшее увеличение производительности суперскалярных микропроцессоров осуществляется на основе технологии TLP(ThreadLevelParallelism).Обрабатываемые программы должны быть предварительно распараллелены и подготовлены к исполнению на многопроцессорных системах в виде параллельных потоков или нитей, предусмотренных в операционных системахUNIIXиWindowsNT. Это позволило повысить степень параллелизма команд, исполняемых избыточными функциональными устройствами, увеличить их загрузку и производительность процессора на 10-30% за счет того, что разные потоки и нити используют одни и те же функциональные устройства с разделением времени. Следующий, уже реализованный подход: ChipMultiProcessing(CMP) – размещение нескольких суперскалярных процессоров на одном кристалле. Наиболее мощный микропроцессор, построенный по этому принципу, - этоPOWER4 компанииIBM. Он содержит на кристалле размером 400 мм 2 два сложных суперскалярных процессора с собственными кэш-памятями первого уровня, единый общий кэш второго уровня емкостью 1,5 Мбайта, пять контроллеров памятей (контроллеры встроенных кэш-памятей и контроллеры наружной основной памяти большой емкости), множество шин разной разрядности (32, 64и 256 разрядов), блоки поддержки некэшируемых операций, интерфейсные блоки для связи с подсистемой ввода- вывода и коммутатором. Число транзисторов на кристалле превышает 170 миллионов. Тактовая частота 1,3 ГГц. В одном корпусе по методу микросборки размещают четыре таких кристалла, т.е. 8- мимикропроцессорный мультипроцессор типаSMP. Для связи процессоров друг с другом используются на микросборке четыре 128-битные шины. Благодаря компактному расположению процессоров и кеш-памятей, и множества быстрых шин достигается очень высокая скорость обмена данными между процессорами. Каждый суперскалярный процессор содержит 8 конвейерных функциональных устройств, может параллельно за один конвейерный такт выполнять до 8-ми команд, и построен на 10 миллионах транзисторов. Такие 8-ми процессорные модули могут быть элементной базой высокопроизводительных кластеров и суперсерверов. К сожалению, требуемые по этому подходу автоматически распараллеливающие компиляторы, которые позволили бы без больших затрат труда программистов достичь программной совместимости этих новых многопроцессорных ультрабольших ИС, пока не созданы. В тоже время уже созрел обширный рынок массового применения чиповCMPв ПЭВМ, рабочих станциях и серверах, развитие которого сдерживается из-за высокой трудоемкости и наукоемкости параллельного программирования; неэффективности их программирования на традиционных последовательных языках высокого уровня, а также эксплуатации на них громадного объема старого последовательного программного обеспечения. И все же главным итогом создания первыхCMPчипов является промышленное освоение производства больших кристаллов размером 2020 мм с нормой на один транзистор около 0.1- 0.2 мкм и тактовой частотой более 1 ГГЦ и возможностью интегрирования на них многошинных, многоконтроллерных, многокэшовых и многопроцессорных схем, требующих для своей реализации около 150 млн. транзисторов. При рассмотрении перспектив в п. 3.5.2.2. нами было установлена целесообразность создания многопроцессорного мультискалярного мультипроцессора на базе суперскалярных процессоров и автоматического распараллеливающего компилятора, выявляющего среднезернистый параллелизм, скрытый как в наследуемых, так и в новых последовательных программах, изначально написанных на традиционно алгоритмических языках. Это позволит за счет возможности увеличения сложности решаемых прикладных задач и скорости их решения при сравнительно небольших дополнительных затратах массовых пользователей расширить сферы использования и рынок сбыта ЭВМ широкого назначения, а также одновременно сэкономитьтриллионыдолларов путем сохранения преемственности программного обеспечения и исключения необходимости переучивания армии «последовательных» программистов средней квалификации. Такой микропроцессор может быть построен на полупроводниковой пластине по новой архитектуре ММММ, которая имеет два расшифрования: -многопроцессорный макропотоковый мультискалярный микропроцессор ( - - микросистема); - макропотоковый мультискалярный мультикомпьютер в микросхеме. Как мы увидели выше, микроэлектронная промышленность имеет технологию для размещения на одной неразрезной пластине до 16-ти суперскалярных микропроцессоров, среднего класса типа Pentium2 или 3,Alpha21164,PowerPC603, если ограничить требуемую емкость встроенной кэш- памяти второго уровня в пределах 64-128 Кбайт и расход транзисторов на процессор не более 5 миллионов штук. Этого достаточно, чтобы дополнительно к 2-8 разам ускорения в суперскалярных процессорах получить ускорение еще в десять раз за счет выявления параллелизма на уровне программ. Компилятор освобождается от необходимости распараллеливания на уровне команд и выполняет покритерию максимального ускоренияразбиение сложных последовательных программ на совокупность параллельно и последовательного исполняемых фрагментов (задач) в виде последовательных фон Неймановских подпрограмм. Основные ограничения субоптимальной декомпиляции: 1) нижний и верхние уровни допустимой вычислительной сложности фрагментов, например, измеренной числом команд фрагмента; 2) максимально допустимые числа входов и выходов фрагментов для реализации связей между ними по управлению и по данным. Ограничения сложности подпрограмм фрагментов задач необходимы, чтобы во-первых не опуститься при распараллеливании до уровня команд, а во- вторых учесть ограничение сверху на максимально возможную емкость встроенной кэш памяти второго уровня в каждом процессорном блоке не более 64-128 –ми Кбайт. Ограничение на число связей между фрагментами позволяет уменьшить интенсивность трафика в коммуникационной среде между процессорными блоками и использовать для обмена данными между ними системную общую шину. Создание единого адресного пространства для обрабатывающих процессоров в любом его виде: физическом или виртуальном нецелесообразно, так как параллельное программирование на пользовательском уровне исключено и должно полностью автоматизироваться компилятором и ведущим управляющим процессорным блоком. Сохраняется единое адресное пространство на системной шине только для ведущего процессора. Основная память ведущей системы используется только как буфер для сохранения очереди заданий и задач для подчиненных обрабатывающих процессоров. В ней хранятся откомпилированные фрагменты-задачи или нераспараллеливаемые независимые задачи в любой их смеси, а также их данные. Подчиненные процессоры обращаются в основную память только за новыми задачами и их данными, а также для записи результатов. Обмен промежуточными результатами возможен только между обрабатывающими процессорами по общей шине. Если потребуется обмен массивом данных между задачами, то компилятор планирует его в описателях задач как выходные данные одной задачи, подлежащие передаче в основную память данных, и как входные данные другой задачи с указанием ей их местоположения в памяти данных, резервируя для этого место в ней. Следовательно, компилятор заранее в статистике планирует размещение данных в памяти для всех задач, заготовленных им для подчиненных процессов и хранящихся в основной памяти в виде подпрограмм с описателями. Тогда значение адреса на адресной подшине основной системной шины ведущей ЭВМ можно использовать для простейшей маршрутизации передаваемых данных или сообщений, выставляемых на подшину данных системной шины: 1) в основную память; 2) память данных; 3) в ведущую машину; 4) порт ввода-вывода; 5) в другой обрабатывающий процессорный блок. В последнем случае легко блокируются на подшине управления соответствующие сигналы записи-чтения, чтобы в этой транзакции на передаваемый адрес задачи, номер ее входа и данные реагировали только подчиненные процессорные блоки. Арбитр системной шины ведущей ЭВМ можно использовать для разрешения конфликта между несколькими инициализаторами передачи, назначая разные уровни приоритетов разным по целям транзакциям подчиненных процессоров, например, высший уровень приоритета-транзакции передачи недостающего операнда приостановленной или прерванной задаче ; второй уровень- передаче спекулятивного операнда ; третий –передаче результатов в память данных. При таком подходе многопроцессорное обрабатывающее ядро сателитного ММММ можно организовать по архитектуре однородного симметричного мультикомпьютера с распределенной памятью и автономными адресными пространствами процессорных блоков без необходимости соблюдения когерентности их локальных кэш-памятей между собой. Структурная схема вычислительной системы с сателитным ММММ ОП- основная оперативная память ведущей ЭВМ большой емкости ( динамического типа). ОПД- основная память данных ( статического типа). ПВВ- процессор ввода- вывода ведущей ЭВМ. СКМП- суперскалярный микропроцессор среднего класса со встроенными кэш-памятями команд и данных ( кэш1-первого уровня). КЭШ 2- кэш-память второго уровня средней емкости 64-128 Кбайт для хранения одной - двух обрабатываемых задач (их подпрограмм и данных). ВШУ - внутренняя шина управления для широковещательного обмена сигналами между блоками КЗА и КПБ с использованием «монтажного» ИЛИ. КЗА - контроллер загрузки и арбитража процессорных блоков (ПБ). КПБ - однотипные контроллеры процессорных блоков для управления обменом информацией как между процессорными блоками (ПБ) внутри ММММ, так и с ведущей ЭВМ по одной той же системной шине. ПШ - сигнал предоставления системной шины одному из ПБ. Вычислительная система с сателитным ММММ функционирует в следующих режимах работы: -ввод, например с диска, пакета заданий в виде набора исходных последовательных программ и их данных в режиме прямого доступа в ОП;- компиляция пакета программ и преобразование его в смесь задач для ПБ: смесь подпрограмм фрагментов сложных программ и неподлежащих распараллеливанию исходных программ с учетом критерия субоптимального критерия, а также разбиения исходных данных и массивов на блоки входных данных для образования задач; подготовка для каждой задачи ее описателя, в том числе таблиц описания ее входов и выходов с учетом спланированного размещения в ОПД ее исходных данных и резервированного места для хранения результатов; запись в ОП откомпилированных задач, озаглавленных их описателями; копирование в ЛОП ведущего ПБ описателей всех задач, записанных в ОП; - обработка смеси задач из ОП в обрабатывающих ПБ1-ПБn; старт обработки задает ведущий ПБ путем передачи в ПБ1-ПБnначальных адресов в ОП описателей задач запланированных планировщиком ОС к начальной обработке в подчиненных процессорных блоках путем анализа описателей всех задач и выбора из них тех, которые по исходным данным имеют наибольшую степень готовности операндов; далее процесс перегрузки задач и их данных из ОП и ОПД в КЭШ2 блоков ПБ и обработки смеси задач из ОП выполняется автоматически без участия ведущего ПБ на основе результатов совещания обрабатывающих ПБ друг с другом путем широковещательного обмена информацией по системной шине и шине ВШУ; - освобождение ПБ от завершенных задач и текущая дозагрузка новых задач в свободные ПБ под управлением ведущей ЭВМ; -вывод результатов обработки заданных исходных последовательных программ из ОПД через ПВВ; -вывод из ОП и ОПД на диск смеси откомпилированных задач, их описателей и способа размещения их входных и выходных операндов в ОПД для повторного исполнения в будущем без затрат времени на компиляцию. Из названных режимов оригинальным является процесс автоматической обработки смеси откомпилированных задач подчиненными процессорами ПБ1-ПБnбез участия ведущего ПБ. Он организуется контроллерами процессорных блоков (их конечными автоматами) на основе широковещательного совещания друг с другом на общей шине и наблюдения ими за шиной ВШУ. Идея заимствована из аппаратных протоколов поддержания когерентности кэш- памятей контроллерами локальных кэшей в мультипроцессорах с общей шиной, например из протоколаMESI. Можно заранее определить конечное число состояний каждого из обрабатывающих ПБ и загруженных в него задач, ограничив число загружаемых задач, например не более двух задач в одном ПБ. Состояния зависят от текущего числа задач в ПБ: нет задач, одна или две задачи; состояний самих задач: операнды готовы и обрабатываются в процессоре, приостановлена или прервана по ожиданию недостающих операндов, исполняется на окончательных или спекулятивных входных данных, инициализирована к накоплению входных операндов, накапливает входные операнды, не инициализирована к накоплению операндов, исполняется агрессивно на неполном наборе входных достоверных данных: окончательных или спекулятивных; входит в тело цикла, образованного из задач, или не входит; имеет входные операнды для передачи управления от задачи к задаче по переходам (связи управления) или нет и тому подобное. Значительную часть требуемой для управления информации КПБ получает локально из описателей задач и в результате наблюдения за состояниями одной- двух задач в своем ПБ. Требуемые для задач входные операнды на связях по данным и по управлению между задачами передаются по общей шине по мере их готовности, блокируя на основной шине управления сигналы записи-чтения в ОПД, ОП и ПВВ. Они передаются не более, чем за две транзакции на системной шине. Основным идентификатором является адрес в ОП задачи потребителя. Передающий КПБ с ведома арбитра захватывает системную шину, широковещательно передает символ «внимание» по сигнальным линиям ВШУ, а затем широковещательно и быстро за две транзакции передает по системной шине свой готовый результат, явно нужный другой задаче по описанию выходов своей задачи в своем ПБ. (Далее смотри следующий ниже рисунок и расшифровку абревиатур под ним). Эти транзакции слушают и принимают все остальные КПБ, а затем только один из них оставляет данные у себя в соответствии с описанием входов своих задач. Если задача – приемник еще не инициализирована ни в одном из ПБ, т.е. ни в одном из них нет в памяти КПБ адреса этой задачи в ОП, требуется провести соответствующее совещание между КПБ под наблюдением передающего КПБ и КЗА и принять решение, в каком из ПБ целесообразно эту новую задачу инициализировать. Разрешение этой новой коллизии можно выполнить по специальному протоколу, в результате которого один из ПБ ( с состоянием СПБ или МПЗ ) получает право обратиться в ОП и ОПД и перегрузить в свою КЭШ2 недостающую задачу- приемник, установить ей состояние накопления входных данных, зафиксировать у себя переданный результат и подтвердить сигналом ПР на ВШУ его прием. Исходные данные задач, подготовленных компилятором для ПБ, целесообразно вначале хранить в отдельной основной памяти данных (ОПД). При циклической обработке массивом данных несколькими задачами тела цикла, реализуемыми в нескольких ПБ, возможен групповой поблочный обмен подмассивами данных между ОПД ведущей ЭВМ и кэш- памятями второго уровня (кэш2) процессорных блоков. Поэтому быстродействие ОПД должно быть выше, чем ОП, и ее целесообразно строить на ОЗУ статического типа. Соответствие между системными адресами данных (операндов и результатов) задач в ОПД и их же локальными адресами в КЭШ2, относящимися к однотипным автономным адресным пространствам разных ПБ, устанавливается компилятором и указывается в описателе каждой задачи, а преобразование этих адресов выполняется в каждом КПБ по хранящейся в его памяти таблице описания задачи, загруженной в данный ПБ. Применяется двухуровневая схема арбитра системной шины: 1) арбитр ведущей ЭВМ; 2) подчиненный ему арбитр системной шины внутри ММММ, который реализуется по простейшей схеме централизованного последовательного арбитража с цепочкой для передачи сигнала предоставления шины (ПШ). Последний управляется контроллером КЗА, в котором совмещаются функции управления арбитражем процессорных блоков, загрузкой и аппаратной диспетчеризацией задач, обменом смежными данными между задачами. Принцип такого совмещения функций можно понять, рассмотрев структурную схему подсистемы арбитража, загрузки, диспетчеризации и организации обмена смежными данными. Обозначение сигналов на ВШУ: ШЗ- шина занята; ПШ- предоставление шины; ЗШ- запрос шины ; СПБ - есть свободный ПБ (хотя бы один) ; МПЗ- можно принять вторую задачу (хотя бы в один ПБ); ПР- принято (либо задача, либо смежные данные). Функционирование подсистемы регламентируется пятью протоколами организации взаимодействия ведущей ЭВМ, арбитра ведущей ЭВМ, контроллеров КЗА, КПБ1,…, КПБnи подчиненных обрабатывающих процессоров П1…Пn:
Последний протокол дифференцирует процедуры завершения в зависимости от типа законченной задачи и ее состояния: - если задача закончена на полностью готовых входных данных, то, после рассылки смежных данных другим задачам и подтверждения об их приеме сигналом «принято» (ПР), а также перегрузке конечных результатов из локальной КЭШ2 в ОПД, подпрограмма и данные этой задачи стираются в КЭШ-2, а ее описатель стирается в памяти соответствующего КПБ; -если задача закончена агрессивно на спекулятивных входных данных, то рассылка ее результатов запрещается и она переводится в приостановленный режим ожидания (накопления и уточнения) повторного приема от других задач смежных уточненных спекулятивных данных, которые ей пришлют другие задачи после их завершения на полностью готовых достоверных входных данных; -если задача закончена, но является одной из задач тела цикла, то ее нельзя уничтожать в ПБ до тех пор, пока не будут выполнены все итерации (витки) цикла, однако рассылку смежных ее результатов, а возможно и несмежных, указанных в описателе, необходимо выполнять в каждой итерации. Такая задача цикла может быть уничтожена в своем ПБ только после выхода из цикла по значению условного перехода, которое требуется сообщить всем задачам входящим в этот цикл. Если предполагается многократное выполнение цикла, как вложенного, то это должно быть указано в описателях цикловых задач компилятором, в том числе - от какой другой задачи ожидать признак выхода из сложного вложенного цикла. Только после этого задачи вложенных циклов могут быть уничтожены в своих ПБ. Описанный подход позволяет существенно сэкономить время на многократную загрузку и уничтожение цикловых задач в процессорных блоках. Подобные многопроцессорные платформы на чипах CMP, предназначенные для массового применения, в настоящее время называются за рубежоммультитредовыми микросистемами(микропроцессорами). Тред - это фрагмент последовательной программы, выделенный компилятором в статике в результатеразбиения исходнойпрограммы, и оформленный как отдельный процесс, слабо связанный с другими процессами. Рассмотренные выше задачи – фрагменты по сути являются тредами. Термин «тред», по- видимому, более адекватен, чем термин «задача», учитывая неоднозначность применения слова «задача» в вычислительной технике. Термин «мультискалярный» подчеркивает только то, что такие многопроцессорные платформы предназначены для параллельной обработки скалярных команд фон Неймановской архитектуры и не имеют никаких дополнительных способов организации для ускорения обработки векторной и матричной информации. Поэтому полное название этого типа микропроцессора: мультитредовый мультискалярный макропотоковый микропроцессор ( --я -- я --я микросистема). Мультитредовый мультискалярный макропотоковый мультикомпьютер в микросхеме. Таким образом, по архитектуре ММММ может быть создан массовый малогабаритный мультикомпьютер в одном корпусе микросхемы, отличающихся предельной простотой комунникационной среды, однородностью обрабатывающей подсистемы и минимально возможными коммуникационными задержками. Макропотоковый принцип управления параллельной обработкой задач позволяет исключить их программно управляемую синхронизацию и составление расписания их асинхронного запуска в процессорных блоках, а также диспетчеризацию задач с учетом занятости процессорных блоков. Все это выполняется автоматически благодаря потоковой обработке задач по степени готовности их операндов. Самым важным и экономически ценным свойством ММММ является возможность использования его в качестве центрального обрабатывающего процессорного блока рабочих станций и серверов массового применения, на которых без всяких дополнительных затруднений можно эксплуатировать все старое последовательное ПО и новые сложные последовательные программы, получая при этом выигрыш по производительности. Наибольший эффект в повышении скорости обработки возможен в мультипрограммном многозадачном режиме обработки. В этом случае даже, если компилятор сможет разбивать исходные сложные последовательные программы только на последовательную цепь фрагментов, высокая загрузка всех ПБ обеспечивается за счет параллелизма нескольких исходных программ и агрессивного исполнения задач в цепях фрагментов – тредов, зависимых по управлению и по данным. Еще большая загрузка ПБ и повышения производительности возможны, если компилятор сможет разбивать сложные программы на фрагменты по структуре ярусно- параллельной формы.
Что такое конвейер (pipe)? Что такое именованный конвейер? Охарактеризуйте их. Как эти объекты можно использовать для взаимодействия программ (приведите несколько примеров)?
Конвейеры (PIPE)— это возможность нескольких программ работать совместно, когда выход одной программы непосредственно идет на вход другой без использования промежуточных временных файлов.
В программировании именованный канал или именованный конвейер (англ. named pipe) — расширение понятия конвейера в Unix и подобных ОС, один из методов межпроцессного взаимодействия. Это понятие также существует и в Microsoft Windows, хотя там его семантика существенно отличается. Традиционный канал — «безымянен», потому что существует анонимно и только во время выполнения процесса. Именованный канал — существует в системе и после завершения процесса. Он должен быть «отсоединён» или удалён когда уже не используется. Процессы обычно подсоединяются к каналу для осуществления взаимодействия между процессами.
Именованные каналы в Unix
Вместо традиционного, безымянного конвейера оболочки (англ. shell pipeline), именованный канал создаётся явно с помощью mknod или mkfifo, и два различных процесса могут обратиться к нему по имени.
Например, можно создать канал и настроить gzip на сжатие того, что туда попадает:
Параллельно, в другом процессе можно выполнить:
что приведёт к сжатию передаваемых данных gzip-ом.
Конвейер (pipe) - перенаправление ввода-вывода в Linux
В UNIX-подобных операционных системах пользователю открывается огромный простор для перенаправления ввода-вывода команд. Простым примером перенаправления является pipe (конвейер). Обозначается он символом “|”. Используется pipe следующим образом: команда 1 | команда 2 | команда 3 . При таком вызове все данные, которые при обычном запуске команды 1 выводились бы на экран будут поступать на стандартный ввод команды 2, как будто бы мы вводим эти данные с клавиатуры. Поясню на примере. Введите команду "ls -l /" (Без кавычек). Вы увидите как на экран будет выведено содержимое корневого каталога. Теперь давайте перенаправим вывод этой команды на ввод другой команды: grep, которая ищет во входных данных некоторое сочетание символов. Например, используем такую команду: "ls -l / | grep tmp". Объясню поподробнее что это значит: команда ls -l / Выведет содержимое корневого каталога (как мы убедились выше). Дальше данные поступают команде grep tmp, которая произведет поиск по входным данным (полученным из 1 команды). После чего команда grep выведет то, что нашла на экран (разумеется, это дело опять можно перенаправить). Что очень важно отметить, команды исполняются одновременно, то есть все, что поступает на вывод в первой программе немедленно поступает на вход второй, не дожидаясь завершения 1. Если проводить ассоциации с реальным миром, то можно представить pipe в виде длинной трубы, распооженной вертикально (что-то мне подсказывает, что разработчики системы преставляли себе это именно также, потому и выбрали такое название и символ |). В эту трубу некто (команда 1) сверху кидает яблоки (данные). Второй некто (команда 2) достает из трубы эти яблоки. Ширина трубы не позволяет яблакам менять порядок, то есть в каком порядке они были отправлены командой 1, в таком порядке они будут приняты командой 2. Скорости работы команд также могут различаться. В случае, если второй некто замешкается, яблоки будут оставаться в трубе, дожидаясь обработки. Если замешкается первый, то второй будет ждать поступления данных.
Виды параллельного взаимодействия
В некоторых параллельных системах программирования передача данных между компонентами скрыта от программиста (например, с помощью механизма обещаний (англ.)), тогда как в других она должна указываться явно. Явные взаимодействия могут быть разделены на два типа:
Взаимодействие через разделяемую память (например, в Java или C#). Данный вид параллельного программирования обычно требует какой-то формы захвата управления (мутексы, семафоры, мониторы) для координации потоков между собой.
Взаимодействие c помощью передачи сообщений (например, в Erlang или occam). Обмен сообщениями может происходить асинхронно, либо c использованием метода «рандеву», при котором отправитель блокирован до тех пор, пока его сообщение не будет доставлено. Асинхронная передача сообщений может быть надёжной либо ненадёжной.
Параллельные системы, основанные на передаче сообщений, зачастую более просты для понимания, чем системы с разделяемой памятью, и обычно рассматриваются как более совершенный метод параллельного программирования. Существует большой выбор математичесих теорий для изучения и анализа систем с передачей сообщений, включая модель акторов (англ.) и различные виды исчислений процессов. Передача сообщений может быть эффективно реализована на симметричных мультипроцессорах как с разделяемой когерентной памятью, так и без неё.
У параллелизма с разделяемой памятью и с передачей сообщений разные характеристики производительности; обычно (но не всегда), накладные расходы памяти на процесс и времени на переключение задач у систем с передачей сообщений ниже, однако передача самих сообщений более накладна, чем вызовы процедур. Эти различия часто перекрываются другими факторами, влияющими на производительность.
При использовании разделяемой памяти используются локальные копии данных, для каждого процессора, а при использовании обмена сообщений используются общие данные.
Недостатки: разделяемая память – меньшее быстродействие за счет пересылки данных;
обмен сообщениями – ситуация взаимного исключения, блокировка за счет непришедшего сообщения.
Преимущества: разделяемая память – нет конфликта за счет локализации данных;
обмен сообщениями – большее быстродействие за счет копирования, а не пересылки данных.
Системы с разделяемой памятью лучше использовать на суперкомпьютерах, выполняющих однотипные операции, когда длинна линий связи не значительна.
Системы с обменом сообщений, на многоядерных процессорах, которые используют общие ресурсы.