Параллельная обработка данных

Пособие по успокоению нервов перед эказаменом.

Ни в коем случае не является официальным пособием

Издание 6-е, исправленное и дополненное

Дополнения и исправления приветствуются

ВНИМАНИЕ!

МАТЕРИАЛЫ СОБРАНЫ ПО ВСЕМУ ИНТЕРНЕТУ. К СОЖАЛЕНИЮ, ЕСТЬ НЕ ВСЕ. НАСКОЛЬКО СООТВЕТСТВУЕТ ТОЧКЕ ЗРЕНИЯ ЛЕКТОРА – НЕ ЗНАЮ. ИСПОЛЬЗОВАТЬ НА СВОЙ СТРАХ И РИСК, ПРЕДВАРИТЕЛЬНО ПОМОЛИВШИСЬ…

А. Ельцин, составитель и редактор.

Москва, 2007

Основы информатики. 4

Информация. Меры Хартли, Шеннона. 4

Знания и ЭВМ. 5

Эволюционная классификация вычислительных систем на примере развития отечественной техники. 10

Критерий, положенный в основу эволюционной классификации ЭВМ. 10

Основоположники отечественной вычислительной техники. 14

Вычислители фон-Нейманновской архитектуры. Конвейерная обработка данных и команд. Архитектура памяти. 21

Принципы фон-Нейманновской архитектуры ЭВМ. 22

Конвейерная обработка данных. 22

Зацепление конвейеров. 25

Векторно-конвейерные вычислители. 27

CISC и RISC архитектуры ЭВМ. 28

Внеочередное и спекулятивное выполнения команд. 29

Механизмы предсказания переходов. 30

Управление виртуальной памятью. 32

Полностью ассоциативная кэш-память. 46

Кэш-память с прямым отображением. 48

Частично ассоциативная кэш-память. 49

Дисциплина обновления кэш-памяти. 51

Стратегии записи в кэш-память. 52

Расслоение памяти. 54

Принципы VLIW архитектуры. 56

Суперскалярные и мультитредовые архитектуры микропроцессоров. 57

Стандарт IA-64. 61

Оптимизация программ под архитектуру микропроцессора. 63

Архитектура параллельных вычислительных систем 65

Архитектура параллельных вычислительных систем 65

Метакомпъютинг. 69

Кластерные архитектуры. 72

Симметричные мультипроцессорные системы. 73

Матричные мультипроцессорные системы. 75

Классификации вычислителей по Флинну. 76

Масштабируемость мультипроцессорных вычислителей. 79

Управление памятью в мультипроцессорных системах. 79

Когерентность данных. 84

Топологии мультипроцессорных коммутационных сетей. 85

Типы внутренних связей. 85

Статические и динамические коммуникаторы. 87

Параметры статических коммутационных сетей. 89

Топологии линейки, решетки, пирамиды. 91

Топология гиперкуба. 93

Согласование сеточных топологий со структурой гиперкуба. 95

Перекрестный коммутатор. 96

Многокаскадные коммутационные сети. 99

Производительность вычислительных систем. 101

Пиковая производительность. 101

Методы оценки производительности. 102

Закон Амдала. 110

Нетрадиционные архитектуры: потоковые и нейронные вычислители. 111

Принципы потоковой обработки информации. 111

Схемы потоковых вычислителей. 112

Нейронные сети. 114

Области применения нейронных сетей. 117

Параллельное программирование 120

Модели программирования для систем с разделяемой, распределенной памятью. 120

Разделение последовательных программ на параллельные нити. 124

Ограничения на распараллеливание циклов. 128

Синхронизация параллельных процессов. Барьеры. 129

Критические секции. Двоичные и общие семафоры. 130

Упорядоченные секции. Распараллелить цикл, используя упорядоченные секции и семафоры: 132

Системы передачи сообщений. Фортран-GNS. 134

Статический и динамический способы образования параллельных процессов. 134

Требования с системам программирования методом передачи сообщений. 134

Система программирования MPI. 136

Средства описания и создания процессов в языке Фортран-GNS. 138

Средства передачи и приема сообщений в языке Фортран-GNS. 143

Протоколы передачи и приема сообщений в языке Фортран-GNS. 144

Идентификация абонентов при передачи сообщений в языке Фортран-GNS. 148

Адаптация последовательных программ к параллельным архитектурам. Векторизация и распараллеливание циклов. Методы координат, гиперплоскостей. 149

Автоматическое распараллеливание последовательных программ. 149

Семантика циклов, выполняемых параллельно на ОКМД системах. 153

Алгоритмы преобразования программ методом координат. 155

Схема преобразования программ методом гиперплоскостей. 162

Метод параллелепипедов. 163

Оценить возможность параллельного выполнения цикла: 164

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

Стандарты OpenMP. 164

Язык Фортран-DVM. 169

Язык Sisal. 171

Система программирования Норма. 173

Особенности выполнения арифметических выражения на ЭВМ. Распараллеливание вычислительных алгоритмов. Метод распараллеливания алгоритма общей рекурсии 1-го порядка. 174

Распараллеливание алгоритмов сложения методом редукции 174

Метод распараллеливания алгоритма общей рекурсии 1-го порядка. 176

Представление машинных чисел. 177

Арифметика машинных чисел. 182

Погрешности при вычислениях чисел на параллельных системах. Оценить полную ошибку суммирования положительных чисел. 189

Точность плавающей арифметики. Машинный эпсилон. 190

Перечислить алгоритмы оптимизации объектных программ, которые могут повлиять на точность вычислений. 191

Основы информатики.

Информация. Меры Хартли, Шеннона.

Термин "информация" происходит от латинского слова "informatio", что означает сведения, разъяснения, изложение. Несмотря на широкое распространение этого термина, понятие информации является одним из самых дискуссионных в науке. В настоящее время наука пытается найти общие свойства и закономерности, присущие многогранному понятию информация, но пока это понятие во многом остается интуитивным и получает различные смысловые наполнения в различных отраслях человеческой деятельности:

в обиходе информацией называют любые данные или сведения, которые кого-либо интересуют. Например, сообщение о каких-либо событиях, о чьей-либо деятельности и т.п. "Информировать" в этом смысле означает "сообщить нечто, неизвестное раньше";

в технике под информацией понимают сообщения, передаваемые в форме знаков или сигналов;

в кибернетике под информацией понимает ту часть знаний, которая используется для ориентирования, активного действия, управления, т.е. в целях сохранения, совершенствования, развития системы (Н. Винер).

Клод Шеннон, американский учёный, заложивший основы теории информации — науки, изучающей процессы, связанные с передачей, приёмом, преобразованием и хранением информации, — рассматривает информацию как снятую неопределенность наших знаний о чем-то.

Приведем еще несколько определений:

Информация — это сведения об объектах и явлениях окружающей среды, их параметрах, свойствах и состоянии, которые уменьшают имеющуюся о них степень неопределенности, неполноты знаний (Н.В. Макарова);

Информация — это отрицание энтропии (Леон Бриллюэн);

Информация — это мера сложности структур (Моль);

Информация — это отраженное разнообразие (Урсул);

Информация — это содержание процесса отражения (Тузов);

Информация — это вероятность выбора (Яглом).

Современное научное представление об информации очень точно сформулировал Норберт Винер, "отец" кибернетики. А именно:

Информация — это обозначение содержания, полученного из внешнего мира в процессе нашего приспособления к нему и приспособления к нему наших чувств.

Подходы к определению количества информации. Формулы Хартли и Шеннона.

Американский инженер Р. Хартли в 1928 г. процесс получения информации рассматривал как выбор одного сообщения из конечного наперёд заданного множества из N равновероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определял как двоичный логарифм N.

Формула Хартли: I = log2N

Допустим, нужно угадать одно число из набора чисел от единицы до ста. По формуле Хартли можно вычислить, какое количество информации для этого требуется: I = log2100 > 6,644. Таким образом, сообщение о верно угаданном числе содержит количество информации, приблизительно равное 6,644 единицы информации.

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

Формула Шеннона: I = — ( p1log2 p1 + p2 log2 p2 + . . . + pN log2 pN),

где pi — вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.

Легко заметить, что если вероятности p1, ..., pN равны, то каждая из них равна 1 / N, и формула Шеннона превращается в формулу Хартли.

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

В качестве единицы информации Клод Шеннон предложил принять один бит (англ. bit — binary digit — двоичная цифра).

Бит в теории информации — количество информации, необходимое для различения двух равновероятных сообщений (типа "орел"—"решка", "чет"—"нечет" и т.п.).

В вычислительной технике битом называют наименьшую "порцию" памяти компьютера, необходимую для хранения одного из двух знаков "0" и "1", используемых для внутримашинного представления данных и команд.

Знания и ЭВМ.

Что-то типа…

Числа в ЭВМ

Рассмотрим теперь более подробно процесс кодирования чисел в компьютере. Среди чисел, которые мы используем, встречаются натуральные, целые, рациональные, иррациональные. В вычислительных машинах применяются две формы представления чисел:

- естественная форма или форма с фиксированной запятой (точкой);

- нормализованная форма или форма с плавающей запятой (точкой);

С фиксированной запятой числа изображаются в виде последовательности цифр с постоянным для всех чисел положением запятой, отделяющей целую часть от дробной. Например, 32,54; 0,0036; –108,2. Эта форма проста, естественна, но имеет небольшой диапазон представления чисел и поэтому не всегда приемлема при вычислениях. Если в результате операции получится число, выходящее за допустимый диапазон, происходит переполнение разрядной сетки и дальнейшие вычисления теряют смысл. В современных компьютерах форма представления чисел с фиксированной запятой используется только для целых чисел.

С плавающей запятой числа изображаются в виде X = ±M×P±r, где M - мантисса числа (правильная дробь в пределах 0,1 ≤ M < 1), r - порядок числа (целое), P - основание системы счисления. Например, приведенные выше числа с фиксированной запятой можно преобразовать в числа с плавающей запятой так: 0,3254×102, 0,36×10–2, –0,1082×103. Нормализованная форма представления имеет огромный диапазон чисел и является основной в современных ЭВМ.

Всякое десятичное число, прежде чем оно попадает в память компьютера, преобразуется по схеме:X10→X2→X2 = M2×102r

После этого осуществляется ещё одна важная процедура:

- мантисса с её знаком заменяется кодом мантиссы с её знаком;

- порядок числа с его знаком заменяется кодом порядка с его знаком.

Указанные коды двоичных чисел - это образы чисел, которые и воспринимают вычислительные устройства.

Каждому двоичному числу можно поставить в соответствие несколько видов кодов. Существуют следующие коды двоичных чисел:

Прямой код. Прямой код двоичного числа (а это либо мантисса, либо порядок) образуется по такому алгоритму:

1. Определить данное двоичное число - оно либо целое (порядок), либо правильная дробь (мантисса).

2. Если это дробь. то цифры после запятой можно рассматривать как целое число.

3. Если это целое и положительное двоичное число, то вместе с добавлением 0 в старший разряд число превращается в код. Для отрицательного двоичного числа перед ним ставится единица. Например:

число X2 = –0,1011012→ код числа X пр = 1101101; число Y2 = +0,11011012→ код числа Yпр = 01101101.

Красным цветом выделены знаковые разряды и, кроме того, у кодов отсутствует индекс "2".

Обратный код. Обратный код положительного двоичного числа совпадает с прямым кодом, а для отрицательного числа нужно, исключая знаковый разряд, во всех остальных разрядах нули заменить на единицы и наоборот. Например: число X2 = –0,101012 → Xпр = 1 10101 → Xобр = 101010;

числоY2 = +0,11012 → Yпр = 01101 = Yобр.

Дополнительный код. Дополнительный код положительного числа совпадает с его прямым кодом. Дополнительный код отрицательного числа образуется путём прибавления 1 к обратному коду. Например: