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

Здесь содержится краткий конспект материалов для подготовки к экзамену по параллельной обработке данных.

Для удобства курс разбит на части. Лектор — Фисун Владислав Андреевич.

Введение

Информация и её измерения

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

Формула Хартли (количество информации I, содержащееся в выбранном сообщении):

I(N) = log N

Формула Шеннона (неодинаковую вероятность сообщений в наборе):

H = - sum(pi * log pi)

Арифметические вычисления до эры ЭВМ

Греция — абак (дощечка с палочкой). Русь — косточки по кучкам. Начало XVII века — таблицы логарифмов и логарифмические линейки в Шотландии. В 1642 году Машина Паскаля могла суммировать десятичные числа. Первую арифметическую машину создал в 1673 году Лейбниц — механический арифмометр. Аналитическая машина Бэббиджа — первый проект вычислительного автомата. Эра электронных вычислительных машин началась в 30-х годах XX в.

Эволюционная классификация ЭВМ

  • Первое поколение (1946-1957) — электронные лампы.
  • Второе поколение (1958-1964) — транзисторы.
  • Третье поколение (1965-1971) — интегральные схемы.
  • Четвертое поколение (1972-1977) — большие интегральные схемы.
  • Пятое поколение (1978) — сверхбольшие интегральные схемы.

Принципы фон Неймановской архитектуры

  • Программное управление работой — в каждый момент времени 1 команда.
  • Принцип условного перехода — можно делать переходы.
  • Принцип хранимой программы — программа вместе с данными в ОЗУ.
  • Принцип использования двоичной системы счисления для представления информации.

Память

Виды запоминающих устройств

Типы устройств: внешние запоминающие (ВЗУ), ввода и отображения и приема данных.

Обмен данными: блоками или произвольно.

Доступ к данным: чтение и запись или только чтение.

Тип доступа: последовательный (магнитная лента) или прямой (магнитные диски, магнитный барабан, магнитно-электронные устройства).

Иерархия памяти:

  • Регистры
  • Кеш L1
  • Кеш L2
  • ОЗУ
  • ВЗУ прямого доступа с буферизацией
  • ВЗУ прямого доступа без буферизации
  • ВЗУ долговременного хранения

Адресация ОЗУ

Машинное слово — машиннозависимая и платформозависимая величина, измеряемая в битах или байтах (тритах или трайтах), равная разрядности регистров процессора и/или разрядности шины данных.

В ОЗУ все ячейки памяти имеют уникальные имена, имя — адрес ячейки памяти. Обычно адрес — это порядковый номер ячейки памяти (нумерация ячеек памяти возможна как подряд идущими номерами, так и номерами, кратными некоторому значению). Доступ к содержимому машинного слова осуществляется посредством использования адреса.

Расслоение оперативной памяти

Расслоение ОЗУ – один из аппаратных путей решения проблемы дисбаланса в скорости доступа к данным, размещенным в ОЗУ и производительностью ЦП. Суть расслоения ОЗУ состоит в следующем. Все ОЗУ состоит из k блоков, каждый из которых может работать независимо. Ячейки памяти распределены между блоками таким образом, что у любой ячейки ее соседи размещаются в соседних блоках. Возможность предварительной буферизации при чтении команд/данных. Оптимизация при записи в ОЗУ больших объемов данных.

Ассоциативная память

Другой вид оперативной памяти – ассоциативной можно рассматривать также как двумерную таблицу, но у каждой строки которой есть дополнительное поле, поле ключа. Ассоциативная память имеет очевидное преимущества перед адресной, однако, у нее есть большой недостаток - ее аппаратная реализация невозможна для памяти большого объема.

Виртуальная память

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

Физическое адресное пространство — оперативная память, подключенная к данному компьютеру.

Организация памяти:

  • Базирование адресов
  • Страничная
  • Сегментная

Алгоритмы управления страницами ОЗУ

  • NRU (Not Recently Used) — выгружается не используемая в последнее время страница
  • FIFO (First In First Out) — первым прибыл — первым удален
  • LRU (Least Recently Used) — выгружается наиболее давно используемая страница
  • NFU (Not Frequently Used) — выгружается редко использовавшаяся страница
  • Часы

Использование в ЭВМ принципа локальности вычислений

Соседние инструкции программы, как правило, обращаются к соседним ячейкам памяти. Это можно использовать по-разному:

  • Расслоение памяти — ускорение доступа к последовательным ячейкам
  • Страничная организация — пока используются данные с одной страницы, не нужно менять базовый регистр

Кеши

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

Кэш-контроллер может поместить любой блок оперативной памяти в любую строку кэш-памяти. Физический адрес разбивается на две части: смещение в блоке (строке кэша) и номер блока. При помещении блока в кэш номер блока сохраняется в теге соответствующей строки.

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

Адрес памяти (номер блока) однозначно определяет строку кэша, в которую будет помещен данный блок. Физический адрес разбивается на три части: смещение в блоке (строке кэша), номер строки кэша и тег. Тот или иной блок будет всегда помещаться в строго определенную строку кэша, при необходимости заменяя собой хранящийся там другой блок.

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

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

Изменение данных в кэш памяти

  • WriteBack — бит "изменения" в поле тэга.
  • WriteThru — основная память отражает текущее содержимое кэш-памяти.
  • Буферизованная сквозная запись — информация задерживается в кэш-памяти перед записью в основную память.
  • Запись с размещением и без — обновляемые данные в кеше отсутствуют.
  • Запись при кэш-промахе.

Учет параметров кэша при программировании задач

Структуры данных — связный список маленьких массивов — сочетает в себе преимущества кэша, которые дает массив, но при этом позволяет быстро вставлять элементы и увеличивать размер, как это свойственно спискам. Например, оптимизация сортировки слиянием.

Конвейеры

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

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

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

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

Механизмы:

  • Статические — работа возлагается на компилятор.
  • Динамические — работа возлагается на процессор.

Производительность можно повысить, сделав АЛУ многофункциональным. Если сделать отдельные функциональные элементы для сложения, вычитания, умножения и деления, то схемы становятся проще, а система будет работать быстрее.

Производительность конвейеров

Операция Время выполнения Производительность
Скалярная S + K 1 / (S + K)
Векторная S + K * N N / (S + K * N) ~ 1 / K
  • m — число ступеней
  • K — время выдачи очередного результата
  • N — длина вектора
  • S = K * (m - 1) — время запуска конвейера

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

Циклы вызывают накладные расходы на скалярных вычислителях — эффективнее векторно-конвейерных. Например, векторная команда сложения VADD(B, C, A, N).

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

Конвейер для однотипных операций дешевле и быстрее. Для их совместной работы используется принцип зацепления конвейеров.

Конвейерная обработка команд

  1. Принять команду.
  2. Дешифровать КОП.
  3. Сформировать исполнительный адрес.
  4. Выбрать операнды.
  5. Выполнить команду.
  6. Записать результат.

Конвейерные конфликты

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

Условные переходы

Спекулятивное выполнение команд

Еще до вычисления значения условного выражения необходимо решать задачу о заполнении конвейера (чтобы не было пропуска тактов конвейера из-за неверно выбранной ветки, коды которой потребуется убирать из конвейера).

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

Статическое предсказание условных переходов

Такие предсказания делаются компилятором еще до момента выполнения программы.

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

Большинство производителей современных микропроцессоров снабжают их различными средствами динамического предсказания переходов, производимого на базе анализа "предыстории". Тогда аппаратура собирает статистику переходов, которая помещается в таблицу истории переходов BHT (Branch History Table). Однако у динамического предсказания есть и свои слабые места — это проблемы, возникающие из-за ограниченности ресурсов для сбора статистики.

Обработка условных операторов в EPIC

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

Команды

Эволюция системы команд микропроцессоров

CISC (Complete Instruction Set Computer):

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

RISC (Reduced Instruction Set Computer):

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

Суперскалярные микропроцессоры

В отличие от последнего, он может выполнять несколько операций за один такт. Основными компонентами суперскалярного процессора являются устройства для интерпретации команд (УУ), снабженные логикой, позволяющей определить, являются ли команды независимыми, и достаточное число исполняющих устройств (ФУ, АЛУ). В исполняющих устройствах могут быть конвейеры.

Широкоформатные команды для параллельной обработки данных

VLIW (Very Long Instruction Word):

  • Одно центральное управляющее устройство, обрабатывающее за один такт одну длинную команду.
  • Большое число функциональных устройств (ФУ) — АЛУ.
  • Наличия в длинной команде полей, каждое из которых содержит команду управления некоторым функциональным устройством или команду обращения к памяти.
  • Статически определенная длительность в тактах исполнения каждой операции. Операции могут быть конвейеризованы.
  • Закрепление во время компиляции банков расслоенной памяти за ФУ для получения максимальной ширины доступа для данных, которые можно соединить в одну команду.
  • Система передвижения данных между ФУ, минуя память. Маршрут передвижения полностью специфицируется во время компиляции.
  • Практическая невозможность ручного программирования в силу большой сложности возникающих комбинаторных задач.

Вычислители

Проект EPIC

EPIC (Explicitly Parallel Instruction Computing)

  • Поддержка явно выделенного компилятором параллелизма.
  • Наличие большого регистрового файла.
  • Наличие предикатных регистров.
  • Спекулятивная загрузка данных.
  • Поддержка предикатно-выполняемых команд.
  • Аппаратная поддержка програмной конвейеризации.
  • Поддержка инструкций циклического выполнения команд.

Классификация параллельных вычислителей по Флинну

  • ОКОД — классические последовательные машины, или иначе, машины фон-неймановского типа.
  • ОКМД — состоят из большого числа идентичных процессорных элементов, имеющих собственную память (ILLIAC IV, CRAY-1).
  • МКОД — пока данный класс пуст.
  • МКМД — несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных (Intel Paragon, CRAY T3D).

Статические коммутационные сети

Статические сети имеют жестко фиксированные соединения, вход и выход зафиксированы без возможности переключения. Наиболее простой топологией сети является линейка — одномерная сетка. По топологии гиперкуба, каждое ПЭ связывается со своим ближайшем соседом в n мерном пространстве.

Динамические коммутаторы

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

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

GRID-сети это совокупность вычислительных систем, связанных через Интернет (метакомпьютинг). Используются для решения задач, допускающих сегментацию на независимые вычислительные процессы с большим объемом вычислений. Такими задачами являются задача исследования генома, обработку результатов физических испытаний, проект CETI.

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

Вычислительные кластеры

Группа ЭВМ (серверов), связанная между собой системной сетью и функционирующая с точки зрения пользователя как единый вычислительный узел.

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

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

Система состоит из однородных вычислительных узлов (объединенных в матрицы или гиперкубы), включающих:

  • Один или несколько центральных процессоров (обычно RISC).
  • Локальную память (прямой доступ к памяти других узлов невозможен).
  • Коммуникационный процессор или сетевой адаптер.
  • Иногда — жесткие диски (как в SP) и/или другие устройства В/В.

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

Системы данного класса: SMP (Symmetric Multiprocessing?) состоят из нескольких однородных процессоров и массива общей памяти (разделяемой памяти — shared memory): любой процессор может обращаться к любому элементу памяти. Любой процессор системы получает данное по произвольному адресу памяти за одинаковое время, такая структура памяти называется: UMA — Uniform Memory Access (Architecture). Дальнейшее масштабирование (увеличение числа процессоров системы) SMP систем обеспечивается переходом к архитектуре памяти: NUMA — Nоn Uniform Memory Access. Системы, в которых обеспечена когерентность данных, буферизуемых в кэшах, называются кэш когерентными (cc-cache coherent), а архитектура памяти описываемого кластера: cc-NUMA (cache coherent Nоn Uniform Memory Access).

Архитектура памяти cc-NUMA

Логически память NUMA системы представляется единым сплошным массивом, но распределена между узлами. Любые изменения сделанные каким-либо процессором в памяти становятся доступны всем процессорам благодаря механизму поддержания когерентности кэшей. Архитектура cc-NUMA предполагает кэширование как вертикальных (процессор—локальная память) так и горизонтальных (узел—узел) связей.

Парадигмы программирования для параллельных вычислителей

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

Нетрадиционные вычислители

  • Графические процессоры
  • DSP (Digital signal processor)

Организация вычислений на графе

Потоковая архитектура (data-flow) вычислительных систем обеспечивает интерпретацию алгоритмов на графах, управляемых данными. Идеи потоковой обработки информации, организации вычислений, управляемых потоками данных можно рассмотреть на примере организации ввода и суммирования трех чисел.

Реализация потоковых машин

Основными компонентами потоковой ВС являются:

  • Память команд (ПК)
  • Селекторная (арбитражная) сеть
  • Множество исполнительных (функциональных) устройств (ФУ)
  • Распределительная сеть

Производительность

Измерения производительности ЭВМ

  • На базе аналитических модели (системами массового обслуживания)
  • Имитационное моделирование (эмуляция ядерного оружия)
  • Измерения

Реальная и полная производительность вычислителей

  • Оценка пиковой производительности — номинального быстродействия системы.
  • Получение оценок максимальной — "реальной" производительности.

Пакеты для измерения производительности вычислительных систем

  • Linpack — программная библиотека, написанная на языке Фортран, которая содержит набор подпрограмм для решения систем линейных алгебраических уравнений.
  • SPEC-89

Параметры рейтинга ТОР500

  • Номер в списке
  • Производитель
  • Computer — Type indicated by manufacturer or vendor
  • Installation Site — Customer
  • Страна
  • Год последнего обновления информации о системе
  • Field of Application
  • Количество процессоров
  • Rmax — максиальная производительность, достигнутая на тесте LINPACK
  • Rpeak — теоретическая пиковая производительность
  • Nmax — Problem size for achieving Rmax
  • N1/2 — Problem size for achieving half of Rmax

Закон Амдала

  • N — число процессоров системы
  • P — доля распараллеливаемой части программы
  • S = 1 - P — доля скалярных операций программы, выполняемых без совмещения по времени
  • S + P — время выполнения программы на однопроцессорном вычислителе
  • S + P / N — на мультипроцессоре

Ускорение по Амдалу:

Sp = (S + P) / (S + P / N) = 1 / (S + P / N)

Алгоритмы

Параллельные алгоритмы. Метрики

  • DOP (Degree Of Parallelism) — число процессоров, участвующих в исполнении программы в момент времени t.
  • Speedup — ускорение за счёт параллельного выполнения S(n) = T(1) / T(n).
  • Efficiency — эффективность системы из n процессоров E(n) = S(n) / n.

Параллельные алгоритмы редукции

Пусть группа вычислений может производиться параллельно, использую результаты вычислений, выполненных на предыдущих этапах (полученных в виде начальных данных). Тогда, каждая группа вычислений называется "ярусом" параллельной формы, число групп — "высотой", максимальное число операций в группе "шириной" параллельной формы.

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

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

Векторизация последовательных программ

Под векторизацией понимается распараллеливание. Наибольшим внутренним параллелизмом, который можно использовать для векторизации программ, являются циклические участки, так как на них приходится основное время вычислений, и в случае распараллеливания вычисления в каждой ветви производится по одному и тому же алгоритму. В методах распараллеливания циклов используется довольно сложный математический аппарат. Наиболее распространенными методами распараллеливания являются: метод параллелепипедов, метод координат, метод гиперплоскостей. Объектами векторизации в этих методах являются циклы типа DО в Фортране.

  • Метод координат — векторизация циклов для синхронных ЭВМ (ОКМД).
  • Метод гиперплоскостей — в пространстве итераций ищется прямая (плоскость), на которой возможно параллельное асинхронное выполнение тела цикла.
  • Метод параллелепипедов — выявление зависимых итераций цикла и объединение их в последовательности — ветви, которые могут быть выполнены независимо друг от друга.

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

  • Барьеры — точки синхронизации параллельных процессов программы.
  • MPI — с помощью синхронных (небуферизированных) send/receive.
  • Алгоритм Деккера — очередь процессов к критической секции.
  • Алгоритм банкира — ресурсы выдаются процессу, если их хватит для завершения.

Системы

Исполняемые комментарии в языках программирования

Это прагмы. Специальные директивы, которые компилятор пропускает, если не знает, что с ними делать. На них основан весь OpenMP и любимый лектором DVM. Подсовываем программу обычному компилятору - он делате последовательную программу.

Система OpenMP

OpenMP (Open Multi-Processing) это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с единой памятью на языках C, C++ и Fortran.

Ключевыми элементами OpenMP являются:

  • Конструкции для создания потоков (директива parallel)
  • Конструкции распределения работы между потоками (директивы DO/for и section)
  • Конструкции для управления работой с данными (выражения shared и private)
  • Конструкции для синхронизации потоков (директивы critical, atomic и barrier)
  • Процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num)
  • Переменные окружения (например, OMP_NUM_THREADS)

Пакет MPI

Проект стандарта MPI (Message Passing Interface) представляет собой стандартный набор библиотечных интерфейсов для передачи сообщений. Хотя MPI предлагает большой набор средств, все же, как уже отмечалось, для прикладных программистов более предпочтительными являются системы, основанные на расширении языков.

Язык Фортран-GNS

Фортран GNS представляет собою расширение языка Фортран 77 средствами для образования параллельных процессов и обмена сообщениями между процессами. Для идентификации порожденных процессов в язык добавлен новый тип данных. Передача сообщений между параллельными процессами осуществляется директивами, подобными операторам ввода-вывода языка Фортран 77. В языке отсутствуют средства для получения информации о топологии реальной вычислительной среды. Аналогом Фортрана GNS является система параллельного программирования MPI.

Порождение параллельных процессов. Идентификация абонентов

Идентификация абонентов:

  • По имени процесса
  • По имени программной единицы-задачи
  • Безымянные абоненты
  • Помеченные сообщения

Протоколы передачи сообщений

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

Учет топологии кластера в МР программировании

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

  • Часто обменивающиеся потоки были на близких процессорах.
  • Чтобы не было заторов, т.е. нагрузка на коммуникаторы была равномерной.

Если у тебя разные ноды в машине или разные задачи считаются, то еще балансируешь нагрузку на процессоры, на сильные больше и задачи посложнее. (c) kibergus

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

Модель параллелизма DVM базируется на модели параллелизма по данным. Аббревиатура DVM отражает два названия модели: распределенная виртуальная память (Distributed Virtual Memory) и распределенная виртуальная машина (Distributed Virtual Mashine). Эти два названия указывают на адаптацию модели DVM как для систем с общей памятью, так и для систем с распределенной памятью.

Директивы:

  • Распределение данных
  • Распределение вычислений
  • Спецификация удаленных данных

Модель FDVM определяет два уровня параллелизма:

  • Параллелизм по данным на секции массива процессоров.
  • Параллелизм задач — независимые вычисления на секциях массива процессоров.

Система программирования НОРМА

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

Точность

Особенности машинной арифметики

Две формы представления чисел:

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

Коды двоичных чисел:

  • Прямой
  • Обратный
  • Дополнительный

Сложение чисел, а также вычитание чисел в обратном или дополнительном кодах выполняется с использованием обычного правила арифметического сложения многоразрядных чисел.

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

Результат арифметических операций чисел с плавающей запятой может:

  • Иметь абсолютное значение, больше M (максимального числа) — машинное переполнение.
  • Иметь ненулевое значение, меньшее m (минимального числа) по абсолютной величине — машинный нуль.
  • Иметь значение в диапазоне [m:M] и тем не не менее не принадлежать исходному множеству.

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

Алгоритмы оптимизации программ, влияющие на точность вычислений

  • Балансировка дерева вычислений
  • Исключение общих подвыражений
  • Разворачивание циклов