Программирование параллельных систем
Модель машины фон Неймана предполагает, что процессор выполняет последовательность инструкций. Инструкции могут определять в дополнение к различным арифметическим операциям адреса данных, которые надо прочитать/записать в памяти, и/или адрес следующей инструкции, которую надо выполнить. Пока возможно только программировать компьютер с точки зрения этой основной модели, этот метод для большинства целей недопустимо сложен из-за того, что мы должны следить за миллионами позиций памяти и организовать выполнение тысяч машинных инструкций. Следовательно, прикладывается модульная техника разработки, посредством которой сложные программы создаются из простых компонент, и компоненты структуры с точки зрения абстракций более высокого уровня (такие, как структуры данных, итерационные циклы и процедуры). Абстракции (например, процедуры) делают эксплуатацию модульности легче, допуская объекты, которыми должны управлять без беспокойства для их внутренней структуры. Так сделаны высокоуровневые языки, как, например, Fortran, C, Ada и Java, которые допускают разработку, выраженную с точки зрения этих абстракций, которые переводятся автоматически в выполняемый код. Параллельное программирование вводит дополнительные источники сложности: если мы должны запрограммировать на самом низком уровне, нам нужно не только увеличить количество выполняемых инструкций, но также управлять выполнением тысяч процессоров и координированием миллионов межпроцессорных взаимодействий. Следовательно, абстракция и модульность по крайней мере так же важны, как и в последовательном программировании. Фактически, мы выделим модульность как четвертое фундаментальное требование для параллельного программного обеспечения, дополнительно к параллелизму, масштабируемости, и локальности.
Основные абстракции, используемые в параллельном программиро-вании, сводятся к задачам и каналам:
1. Параллельное вычисление состоит из одной или более задач. Задачи выполняются параллельно. Количество задач может меняться во время выполнения программы.
2. Задача изолирует последовательную программу и локальную память. Вдобавок набор вводов и выводов определяет свой интерфейс в своей среде.
3. Задача может выполнять четыре основных действия дополнительно к чтению и записи в локальной памяти: послать сообщение на свои порты вывода, получить сообщение со своих портов ввода, создать новые задачи и уничтожить (завершить) задачу.
4. Операция отправления сообщения – асинхронная, она завершается немедленно. Операция получения – синхронная, она вызывает выполнение задачи, блокируя процесс, пока сообщение не будет получено.
5. Пары ввода/вывода могут связываться сообщениями в очереди, называемыми каналами. Каналы могут создаваться и удаляться, и ссылки на каналы (порты) способны включаться в сообщения, так что связность изменяется динамически.
6. Задания могут отображаться в физических процессорах различными способами; отображающее применение не влияет на семантику программы. Конкретно многочисленные задания могут отображаться в единственном процессоре (можно также представить, что единичная задача может быть отображенной в множестве процессоров, но эта возможность здесь не учитывается.)
Абстракция задач требует свойство локальности: данные, содержащиеся в локальной памяти задачи – «закрытые»; другие данные – «удаленные». Канальная абстракция обеспечивает механизм для указания, вычисление каких данных из одной задачи требуется для начала работы другой задачи. (Это охарактеризовано зависимостью данных). Модель задач и каналов обладает и некоторыми другими свойствами:
Производительность. Последовательные абстракции программирования, такие как, например, процедуры и структуры данных, эффективны из-за того, что они могут быть отображены просто и эффективно в компьютере фон Неймана. Задачи и каналы имеют аналогично прямое распределение в мультикомпьютере. Задача представляет часть кода, который может быть выполнен последовательно в единственном процессоре. Если две задачи, которые делят канал, отображаются в других процессорах, канальное соединение осуществлено как межпроцессорное соединение; если они отображаются в том же процессоре, могут быть использованы некоторые более эффективные механизмы.
Независимость распределения. Поскольку задания взаимодействуют, используя тот же механизм (каналы) независимо от положения задачи, результат вычисленный программой не зависит от того, где задача выполняется. Следовательно, алгоритмы могут разрабатываться и осуществляться без беспокойства о количестве процессоров, на которых они будут выполняться; фактически, алгоритмы часто разрабатываются так, что создают гораздо больше задач, чем процессоров. Это простой путь достижения масштабности: когда количество процессоров увеличивается, количество задач на процессор уменьшается, но сам алгоритм не должен быть модифицирован. Когда имеется большее число задач, чем процессоры смогли бы обслуживать, чтобы замаскировать задержки связи, обеспечиваются другие вычисления, которые могут выполняться, пока выполняется связь для доступа к удаленным данным.
Модульность. В модульном составлении программы различные компоненты программ разрабатываются отдельно как независимые модули и затем объединяются, чтобы получить полную программу. Взаимодействие между модулями ограничивается отчетливо выраженными интерфейсами. Следовательно, модульные реализации могут быть изменены без модификации других компонент, и свойства программы могут определяться из спецификации ее модулей и кода, который соединяет эти модули вместе. Когда успешно приложена модульная разработка, уменьшается программная сложность и облегчается многократное использование кода.
Детерминизм. Алгоритм или программа детерминированы, если при выполнении с конкретным вводом всегда получается один и тот же вывод. Он недетерминирован, если многочисленные выполнения с тем же вводом могут дать другой вывод. Хотя недетерминизм иногда полезен и должен поддерживаться, параллельная модель программирования, которая облегчает написание детерминированных программ, очень желательна. Детерминированные программы имеют тенденцию быть более понятными. Также при проверке на правильность должна вычисляться только одна последовательность выполнения параллельной программы, а не все возможные для выполнения.
Сети ЭВМ (Лекция 14)
Организация сети
Главная цель, которая преследуется при соединении компьютеров в сеть – это возможность использования ресурсов каждого компьютера всеми пользователями сети. Для того чтобы реализовать эту возможность, компьютеры, подсоединенные к сети, должны иметь необходимые для этого средства взаимодействия с другими компьютерами сети.
Определенный набор функций, выполняемых данным уровнем для вышележащего уровня, а также форматы сообщений, которыми обмениваются два соседних уровня в ходе своего взаимодействия, называется интерфейсом.
Интерфейс определяет совокупный сервис, предоставляемый данным уровнем вышележащему уровню.
При организации взаимодействия компьютеров в сети каждый уровень ведет "переговоры" с соответствующим уровнем другого компьютера. При передаче сообщений оба участника сетевого обмена должны принять множество соглашений. Например, они должны согласовать уровни и форму электрических сигналов, способ определения длины сообщений, договориться о методах контроля достоверности и т.п.
Правила взаимодействия двух машин могут быть описаны в виде набора процедур для каждого из уровней. Такие формализованные правила, определяющие последовательность и формат сообщений, которыми обмениваются сетевые компоненты, лежащие на одном уровне, но в разных узлах, называются протоколами.
Согласованный набор протоколов разных уровней, достаточный для организации межсетевого взаимодействия, называется стеком протоколов.
Программные средства, реализующие некоторый протокол, также называют протоколом. При этом соотношение между протоколом – формально определенной процедурой взаимодействия и протоколом – средством, реализующим эту процедуру, аналогично соотношению между алгоритмом решения некоторой задачи и программой, решающей эту задачу. Понятно, что один и тот же алгоритм может быть запрограммирован с разной степенью эффективности. Точно также и протокол может иметь несколько программных реализаций, например, протокол IPX, реализованный компанией Microsoft для Windows NT в виде программного продукта NWLink, имеет характеристики, отличающиеся от реализации этого же протокола компанией Novell. Именно поэтому, при сравнении протоколов следует учитывать не только логику их работы, но и качество программных решений. Более того, на эффективность взаимодействия устройств в сети влияет качество всей совокупности протоколов, составляющих стек, то есть, насколько рационально распределены функции между протоколами разных уровней и насколько хорошо определены интерфейсы между ними.
Протоколы реализуются не только программно-аппаратными средствами компьютеров, но и коммуникационными устройствами. Действительно, в общем случае связь компьютеров в сети осуществляется не напрямую – "компьютер-компьютер", а через различные коммуникационные устройства такие, например, как концентраторы, коммутаторы или маршрутизаторы. В зависимости от типа устройства, в нем должны быть встроены средства, реализующие некоторый набор сетевых протоколов.
При организации взаимодействия могут быть использованы два основных типа протоколов. В протоколах с установлением соединения (connection-oriented network service, CONS) перед обменом данными отправитель и получатель должны сначала установить логическое соединение, то есть договориться о параметрах процедуры обмена, которые будут действовать только в рамках данного соединения. После завершения диалога они должны разорвать это соединение. Когда устанавливается новое соединение, переговорная процедура выполняется заново. Телефон – это пример взаимодействия, основанного на установлении соединения.
Вторая группа протоколов – протоколы без предварительного установления соединения (connectionless network service, CLNS). Такие протоколы называются также дейтаграммными протоколами. Отправитель просто передает сообщение, когда оно готово. Опускание письма в почтовый ящик - это пример связи без установления соединения.
Сети соединяются между собой специальными устройствами, называемыми маршрутизаторами. Маршрутизатор – это устройство, которое собирает информацию о топологии межсетевых соединений и на ее основании пересылает пакеты сетевого уровня в сеть назначения. Для того, чтобы передать сообщение от отправителя, находящегося в одной сети, получателю, находящемуся в другой сети, нужно совершить некоторое количество транзитных передач (hops) между сетями, каждый раз выбирая подходящий маршрут. Таким образом, маршрут представляет собой последовательность маршрутизаторов, через которые проходит пакет.
Проблема выбора наилучшего пути называется маршрутизацией. Часто критерием при выборе маршрута является время передачи данных по этому маршруту или, например, надежность передачи.