Prezentatsia

Области применения многопроцессорных систем
1
Обработка транзакций в режиме реального времени (OLTP, online transaction processing)
Создание хранилищ данных для организации систем поддержки принятия решений (DSS, Data Mining, Data Warehousing, Decision Support System)

Архитектура многопроцессорных вычислительных систем
2

Многопроцессорные системы с общей памятью
3
ЦП
ЦП
ЦП
ОБЩАЯ ФИЗИЧЕСКАЯ ПАМЯТЬ
I/O
подсистема

Многопроцессорные системы с раздельной памятью
4
ЦП
ОП
ЦП
ОП
I/O подсистема
R1
R1

Многопроцессорные системы гибридного типа
5,
Память
Проц
Проц
Проц
Проц
Память
Проц
Проц
Проц
Проц
Память
Проц
Проц
Проц
Проц
Коммуникационная сеть
Переферия

Кластерные вычислительные системы
ЦП
ЦП
ЦП
ЦП
ЦП
ЦП

Компьютерные сети
ПК
Маршрутизатор
ПК
Маршрутизатор
Канал связи
Линия связи
Линия связи
Линия связи

Коммуникационные среды
В самом общем смысле архитектуру компьютера можно определить как способ соединения компьютеров между собой, с памятью и с внешними устройствами. Реализация этого соединения может идти различными путями. Конкретная реализация такого рода соединений называется коммуникационной средой компьютера.

Транспьютеры

Специализированные языки параллельного программирования

Библиотеки и системы программирования для высокоуровневых языков

Принципы построения параллельных алгоритмов. Основные методы построения параллельных программ
Основные типы параллелизма, используемые для построения параллельных алгоритмов:
Алгоритмический
Геометрический
Конвейерный
«Коллективное решение»
,14

Алгоритмический параллелизм
Алгоритмическим параллелизмом называется параллелизм, который выявляется путем выделения в данном алгоритме тех фрагментов, которые могут выполняться параллельно
15

Геометрический параллелизм
Геометрический параллелизм допускает разбиение данных на части по числу процессоров, при котором обработку каждой части осуществляет соответствующий процессор.
16

Конвейерный параллелизм
Первый каменщик (процессор) укладывает первый ряд кирпичей, второй каменщик - второй ряд, и т.д. Требуется время на передачу информации о свойствах кирпича и о том, что ряд ниже уложен. Неизбежны потери времени в начале и в конце выполнения задачи - например, второй каменщик не может начать работу прежде, чем первый каменщик уложит хотя бы один кирпич.
17

Параллелизм типа «коллективное решение»
Метод предполагает, что неизвестно, с какой скоростью какие процессоры работают. Существует один выделенный процессор, который выполняет управляющие функции, он раздает задачи и принимает результаты, а остальные процессоры выполняют обрабатывающие функции независимо друг от друга.
18

Статическая и динамическая балансировка загрузки процессоров
Статическая балансировка выполняется до начала выполнения параллельного приложения.
Алгоритм динамической балансировки определяет с какого вычислительного узла и на какой следует перенести задачу во время работы системы.
19

Проблема тупиков
Тупик - ситуация, в которой один или несколько процессов ожидают какого-либо события, которое никогда не произойдет.
Необходимые условия тупика:
Условие взаимоисключения
Условие ожидания ресурсов
Условие неперераспределяемости
Условие кругового ожидания
20

Недетерминированность параллельных программ
Недетерминированность процессов происходит от того, что они обмениваются данными в непредсказуемые моменты времени.
Параллельная программа представляется системой взаимодействующих процессов, порядок выполнения которых жестко не фиксирован, что является причиной недетерминизма вычислений
21

Эффективность, ускорение параллельных программ.
Ускорением параллельного алгоритма (Sp), называют отношение времени выполнения алгоритма на одном процессоре ко времени выполнения алгоритма на системе из p процессоров.
Эффективностью параллельного алгоритма (Ep) называют отношение его ускорения к числу процессоров, на котором это ускорение получено.
Степенью параллелизма алгоритма называют число действий алгоритма, которые могут выполняться одновременно, каждое на своем процессоре.
22

Оценка времени выполнения алгоритма
Степенью параллелизма алгоритма называют число действий алгоритма, которые могут выполняться одновременно, каждое на своем процессоре.
Каждое из сложений сi = ai + bi , i=1, ..., n не зависит от других и может выполняться одновременно с ними, таким образом, степень параллелизма данного алгоритма равна n.
От числа процессоров зависит только время выполнения реальной программы при ее запуске на этих процессорах.
Можно сделать вывод о том, что ускорить выполнение программы более чем в число раз, определяемое степенью параллелизма ее алгоритма, нельзя.
23

Внутренний параллелизм
Внутренние свойства алгоритма, не зависящие от вида и особенностей вычислительных систем.
На разных этапах выполнения алгоритма степень параллелизма может быть различной.
Важно, чтобы высокой степенью внутреннего параллелизма обладали этапы, на выполнение которых тратится основное время.
24

Закон Амдаля
Закон Амдаля характеризует одну из самых серьезных проблем в области параллельного программирования - алгоритмов без определенной доли последовательных команд практически не существует.
25

Параллельная программа как ансамбль взаимодействующих последовательных процессов
Поскольку параллельная программа — это множество взаимодействующих последовательных процессов, разработка параллельного алгоритма сводится к разработке набора последовательных алгоритмов, каждый из которых выполняется на своем процессоре.
26

Основные методы синхронизации
27

Синхронизация с помощью передачи сообщений
28

Виды каналов передачи данных
29

Синхронный и асинхронный обмен сообщениями
30

Защита разделяемых данных
Для организации разделения ресурсов между несколькими потоками необходимо иметь возможность:
определения доступности запрашиваемых ресурсов;
выделения свободного ресурса одному из потоков, запросивших ресурс для использования;
блокировки потоков, выдавших запросы на ресурсы, занятые другими потоками.
Главное требование к механизмам разделения ресурсов является гарантированное обеспечение использования каждого разделяемого ресурса только одним потоком от момента выделения ресурса этому потоку до момента освобождения ресурса.
31

Семафор. Реализация семафора с помощью традиционных операций.
Семафоры были введены в эксплуатацию Эдсжером Дейкстрой в 1965 году и с тех пор являются базовым средством управления доступом к критическим ресурсам. Алгоритм использования семафоров выглядит так:
Для реализации операций над семафором необходимо наличие примитивов, отвечающих за:
Задержку исполнения процесса выполнившего операцию
возобновление исполнения приостановленного процесса
32

Критическая секция. Монитор, Очереди заданий.
Критическая секция — объект синхронизации потоков, позволяющий предотвратить одновременное выполнение некоторого набора операций несколькими потоками. При нахождении в критической секции двух или более потоков возникает состояние «гонки»
Мониторинг системы — это ежедневное рутинное занятие, и этот документ предоставляет систематическую пошаговую процедуру для мониторинга сервера. Он дает обзор технических аспектов и концепций для упреждающего мониторинга системы.
Очередь заданий содержит упорядоченный список заданий, ожидающих обработки подсистемой. Перед активизацией в подсистеме переданное на выполнение пакетное задание попадает в очередь заданий. Задание остается в очереди, пока не будет выполнено несколько условий.
33

Описание поля процессоров
34
Структура микрокоманды
Соответствие между адресами РЗУ и регистрами микропроцессора
Значения полей MA и MB
Поле MEM

Описание поля процессоров
34
Поле SRC
Поле SH
Поле ALU
Поле CCX

Описание поля процессоров
34
Поле DST
Поле WM
Поле CC
Поле CHA

Виртуальные и реальные процессоры
Виртуальным процессором называется процесс сервера баз данных. Виртуальный процессор можно сравнить с операционной системой. Поток по отношению к нему выступает как процесс, подобно тому, как сам виртуальный процессор является процессом с точки зрения операционной системы.
Виртуальные процессоры (ВП) являются специализированными - они подразделяются на классы в соответствии с типом потоков, для выполнения которых они предназначены. Примеры классов ВП:
CPU - Потоки обслуживания клиентов, реализуют оптимизацию и логику выполнения запросов. К этому классу относятся и некоторые системные потоки.
AIO - Операции асинхронного обмена с диском.
ADM - Административные функции, например, системный таймер.
TLI - Контроль сетевого взаимодействия посредством интерфейса TLI (TransportLayerInterface).
35

Параллельное и конкурентное выполнение процессов
36

Физические и виртуальные каналы
Виртуальные каналы — это устойчивые пути следования трафика, создаваемые в сети с коммутацией пакетов. Они представляют собой соединение между двумя конечными станциями сети и являются двунаправленными.
Существуют три вида виртуальных каналов:
постоянные виртуальные каналы (PVC)
коммутируемые виртуальные каналы (SVC)
интеллектуальные постоянные виртуальные каналы (SPVC)
37

Физические и виртуальные топологии
В MPI топология представляет собой механизм сопоставления процессам, принадлежащим группе, альтернативных по отношению к обычной схем нумерации. Топологии обменов сообщениями в MPI являются виртуальными, они не связаны с физической топологией коммуникационной сети параллельной вычислительной системы. Использование коммуникаторов и топологий отличает MPI от большинства других систем передачи сообщений. Топологией в данном случае называют структуру соединений - линий и узлов сети без учета характеристик самих этих узлов. Узлами здесь являются процессы, соединениями - каналы обмена сообщениями, а сетью мы, фактически, называем все процессы, входящие в состав параллельной программы.
38

Режимы передачи данных
Режим передачи (transmissionmode) определяет возможные направления передачи сигналов между узлами сети. Существуют три режима передачи (режима использования канала):
симплексный или односторонний (simplexmode),
полудуплексный (half-duplexmode) и
дуплексный (full-duplexmode).
39

40
Измерение времени
На время выполнения программы влияют следующие факторы:
Ввод исходной информации в программу.
Качество скомпилированного кода исполняемой программы.
Машинные инструкции (естественные и ускоряющие), используемые для выполнения программы.
Временная сложность алгоритма соответствующей программы.

41
Отладка программы
Отладка — этап разработки компьютерной программы, на котором обнаруживают, локализуют и устраняют ошибки. Чтобы понять, где возникла ошибка, приходится:
узнавать текущие значения переменных;
выяснять, по какому пути выполнялась программа.

42
Выполнение процессов на общей памяти (треды)
Поток выполнения / тред — наименьшая единица обработки, исполнение которой может быть назначено ядром операционной системы. Реализация потоков выполнения и процессов в разных операционных системах отличается друг от друга, но в большинстве случаев поток выполнения находится внутри процесса.

43
Использование семафоров для синхронизации тредов
Семафоры традиционно использовались для синхронизации процессов, обращающихся к разделяемым данным. Каждый процесс должен исключать для всех других процессов возможность одновременно с ним обращаться к этим данным (взаимоисключение). Когда процесс обращается к разделяемым данным, говорят, что он находится в своем критическом участке.

44
Примеры математических моделей применение которых требуют суперкомпьютерных вычислений
Кратко разработку и программную реализацию моделирования задач механики сплошной среды можно сформулировать следующим образом. Сначала алгоритм разделяется на базовые операции. Затем, исходя из зависимости по данным между операциями, на первом уровне реализуется традиционное MPI распараллеливание. Далее, работая с операциями в отдельности, выполняется адаптация к потоковой обработке и различным вычислительным архитектурам, оптимизация структур данных и доступа к памяти.

45
Кинетически согласованные разностные схемы
Многие из проблем, связанных с использованием многопроцессорных вычислительных систем для решения задач газовой динамики, могут быть решены с помощью применения кинетически согласованных схем, опирающихся на представления статистической механики и механики сплошных сред.

46
Компиляция и выполнение параллельных программ под
управлением PARIX
Для компиляции программных модулей используется команда:
px ancc <имя файла.c> -с -qcpluscmt –O3
Для сборки программы используется команда:
px ancc <имя файла1>.o ... <имя файла n>.o [опции] –о <имя создаваемого выполняемого файла программы>

47
Уровни оптимизации выполняемого программного кода
Решение проблемы быстрой и недорогой разработки эффективного программного обеспечения для параллельных архитектур невозможно без оптимизирующих распараллеливающих компиляторов. Распараллеливающий компилятор — частный случай оптимизирующего, который условно можно разделить на блок синтаксического разбора текста, блок оптимизации и генератор кода.

48
Заголовочные файлы и библиотеки передачи данных, порождения процессов и доступа к семафорам
Send, Recv – функции синхронного обмена данными через каналы виртуальных топологий
AInit, ASend, ARecv, ASync, AInfo, AExit – функции асинхронного обмена данными через каналы виртуальных топологий
Select, CondSelect, SelectList, CondSelectList, ReceiveOption, ReceiveOption_B, TimeAfterOption, TimeAfterOption – Селективное ожидание ввода данных или таймаута
TimeNow, TimeWait, TimeAfter – доступ к процессорному таймеру
CreateSem, InitSem, DestroySem, Wait, TestWait, Signal - управление семафорами

49
Запуск и прекращение выполнения программы. Утилита nrm. Сервер epxd
Для запуска PARIX-приложения используется команда run.
Px nrm - утилита управления ресурсами многопроцессорной системы. Информацию о имеющихся в системе разделах можно получить с помощью команды px nrm –pp.
EPX - специализированный API-интерфейс используемый в качестве средства распараллеливания который образует «среду» Embedded PARIX (Parallel Extension to Unix - EPX). Благодаря этому API-интерфейсу можно создавать виртуальные каналы между пользовательскими потоками. Каждый узел ввода-вывода работает под управлением AIX и Parsytec EPX.

50
Анализ результатов выполнения параллельной программы. Распределение и освобождение разделов
Команда run занимает указанный раздел, так что он (вместе с перекрывающимися разделами) становится недоступен для запуска других приложений PARIX. По окончании PARIX-приложения, run автоматически освобождает занятый раздел, так что он становится доступен для других PARIX- приложений.

51
Заголовочные файлы и библиотеке MPI. Версии MPI: lam, mpich. Версии Mpi для Unix. Версия Mpi для Windows
LAM - Реализация MPI и среда разработки MPI-программ для гетерогенных кластеров из UNIX-машин, разработана в Ohio Supercomputer Center, теперь эта реализация перешла в ведение Laboratory for Scientific Computing (университет Notre-Damme). Последняя версия - 6.1.
MPICH - это высокопроизводительная и широко переносимая реализация стандарта интерфейса передачи сообщений (MPI) (MPI-1, MPI-2 и MPI-3). Работает почти на всех UNIX-системах и Windows, разработанная в Argonne National Laboratory. Поддерживаются кластеры на базе SMP-узлов.

52
Мониторинг выполнения параллельной программы
Обычно для целей трассировки в исследуемую программу встраиваются "профилировочные" вызовы, которые фиксируют наступление определенных событий или продолжительность интервалов, и фиксируют эту информацию в журнале трассировки, передают ее онлайн-анализатору или просто модифицируют собираемую статистику.

53
Некоторые средства Unix (rsh, ssh, bash, ping, scp) их использование для подготовки, выполнения и отладки
параллельных программ
rsh – удалённый командный интерпретатор.
SSH - (Secure Shell) - это протокол удаленного управления компьютером с операционной системой Linux.
Bash - это самый популярный интерпретатор команд, который используется в большинстве дистрибутивов Linux.
Утилита ping - это очень простой инструмент для диагностики сети.
Команда scp - это утилита, которая работает по протоколу SSH, а значит, все что вам нужно для передачи файла на компьютер

Работа в режиме удаленного доступа
54
Клиент
Сервер
БД
База мета-данных
Файловые команды
Блоки данных
Модель файлового сервера

Работа в режиме удаленного доступа
54
Клиент
Сервер
БД и БМД
SQL запросы
Результаты запросов
Модель удаленного доступа

Статическая и динамическая балансировка нагрузки
55

Диффузная балансировка нагрузки
56
Диффузная балансировка нагрузки является методом динамической балансировки загрузки процессоров, где перераспределение вычислительной нагрузки выполняется между логически соседними процессорами.

Централизованное и децентрализованное управление вычислениями
57

Построение алгоритмов динамической балансировки загрузки на основе технологии «клиент-сервер»
Нагрузка на объединенные между собой серверы распределяется с учетом закрепленных за ними ролей.
Автономный сервер
Рабочий сервер
Мастер-сервер
Выделенный мастер-сервер
58

Особенности обеспечения балансировки загрузки процессоров при использовании неструктурированных сеток
Проблема балансировки загрузки при решении задач на нерегулярных сетках часто сводится к задаче разбиения графа на заданное число частей.
Для графов небольшого объема - спектральный алгоритм.
Для графов большого размера - иерархические алгоритмы:
рекурсивное огрубление графа (уменьшение его размера)
рекурсивная бисекция (разбиение графа на две части) вершин графа на заданное число групп
рекурсивное разукрупнение графа и локальное уточнение разбиения промежуточных графов
59

Спектральная матрица графа. Вектора Фидлера
60

Иерархические алгоритмы разбиения больших графов
Алгоритм Кернигана-Лина:
Формирование множества пар вершин для перестановки.
Построение новых вариантов разбиения графа.
Выбор лучшего варианта разбиения графа.
Проверка использования всех вершин.
Выбор наилучшего варианта разбиения графа.
61

Методы визуализации двух и трехмерных сеточных данных
Под двухмерной визуализацией понимается отображение данных на плоскости в виде изображения. Для формирования изображений обычно используется либо растровый, либо векторный способы.
Трёхмерная визуализация данных осуществляется на основе модели данных, полученных при помощи обработки снимков. Под моделью в данном случае понимается описание исходных данных на строго определённом языке или в виде структуры.
62

63
Сжатие сеточных данных, заданных на структурированных и неструктурированных сетках.
Работоспособность системы распределенной визуализации трехмерных скалярных полей определяется, главным образом, качеством алгоритмов сжатия неструктурированных сеток. Появление триангуляции вызвано наличием разбиения каждого из кубов сетки на набор пирамид, обеспечивающих в большинстве случаев однозначность построения изоповерхности.