Архитектура вычислительных систем. Лекция 2
Общая структура компьютера
Иерархия памяти в современных компьютерах (1)
Иерархия памяти в современных компьютерах (2)
Классификация архитектуры вычислительных систем (1)
Классификация архитектуры вычислительных систем (2)
Классификация архитектуры вычислительных систем (3)
Классификация архитектуры вычислительных систем (4)
Классификация архитектуры вычислительных систем (5)
Классификация архитектуры вычислительных систем (6)
Классификация архитектуры вычислительных систем (7)
Классификация архитектуры вычислительных систем (8)
Методы тестирования производительности (1)
Методы тестирования производительности (2)
Методы тестирования производительности (3) «Синтетические» бенчмарки
Методы тестирования производительности (4)
Методы тестирования производительности (5) LINPACK
Методы тестирования производительности (6) LINPACK
Методы тестирования производительности (7) LINPACK
Методы тестирования производительности (8) LINPACK
Методы тестирования производительности (9) Бенчмарки на основе реальных задач
Методы тестирования производительности (10)
Реальная и пиковая производительность (1)
Реальная и пиковая производительность (2)
ЗАКОН АМДАЛА (Gene Amdahl, 1967)
Закон Амдала и его следствия (1)
Закон Амдала и его следствия (2)
Закон Амдала и его следствия (3)
Что еще влияет на производительность вычислительных систем, кроме закона Амдала?
644.50K
Category: informaticsinformatics

Архитектура вычислительных систем. (Лекция 2)

1. Архитектура вычислительных систем. Лекция 2

Общая схема компьютера, иерархия памяти
Классификация вычислительных систем
Методы тестирования производительности
вычислительных систем
Закон Амдала
Факторы, влияющие на производительность

2. Общая структура компьютера

Современные компьютеры, при всем их разнообразии, в
целом сохраняют общую структуру, отвечающую базовым
принципам фон Неймана
На рисунке: схема компьютера и схема работы АЛУ
Современные ЦПУ имеют несколько АЛУ, много регистров
и иерархическую структуру памяти.

3. Иерархия памяти в современных компьютерах (1)

Различные виды памяти образуют иерархию, на различных уровнях
которой расположена память с отличающимися временем доступа,
сложностью, стоимостью и объёмом. Необходимость такой иерархии
вызвана тем, что большинство алгоритмов обращаются в каждый
промежуток времени к небольшому набору данных, который может
быть помещен в более быструю, но дорогую и поэтому небольшую,
память. Использование более быстрой памяти увеличивает
производительность вычислительного комплекса.
Регистры процессора — блок ячеек памяти внутри процессора с
наиболее быстрым доступом (порядка 1 такта). Используется самим
процессором, обычно недоступен программисту.
Кэш процессора (уровни L1, L2, L3) — время доступа от нескольких
тактов (L1) до сотни таков (L3). Промежуточный буфер с быстрым
доступом, содержащий информацию, которая может быть запрошена с
наибольшей вероятностью
ОЗУ (ОП с произвольным доступом, RAM) — время доступа от сотен до
тысячи тактов, но огромные размеры (от нескольких до сотен Гбайт).
Время доступа к ОЗУ может варьироваться для разных его частей
(NUMA-системы). В ОЗУ во время работы компьютера хранится выполняемый машинный код, входные, выходные и промежуточные данные.
Дисковое хранилище — миллионы тактов, размер до нескольких Тбайт.
Внешняя память (ленточные носители, оптические диски) — задержки
до нескольких сек или мин, но практически неограниченные объёмы

4. Иерархия памяти в современных компьютерах (2)

Пятиуровневая структура памяти
По мере продвижения вниз по пирамиде
растет объем памяти
увеличивается время доступа
От 8 до 256,
(целочисленные, с
плавающей точкой)
От 32 Кбайт до
нескольких Мбайт

5. Классификация архитектуры вычислительных систем (1)

Классификация по способу организации памяти в
многопроцессорных архитектурах:
Параллельные компьютеры
с общей памятью
Параллельные компьютеры
с распределённой памятью
Классическая систематика М.Флинна (1966)
Классификация базируется на понятии потока, под которым понимается
обрабатываемая процессором последовательность элементов
(команд или данных).
На основе числа потоков команд и потоков данных Флинн выделяет
четыре класса архитектур:
SISD, MISD, SIMD, MIMD.

6. Классификация архитектуры вычислительных систем (2)

SISD (single instruction stream / single data stream) –
одиночный поток команд, одиночный поток данных
Классические
последовательные
машины
фоннеймановского типа. В таких машинах есть один
поток команд, все команды обрабатываются
последовательно друг за другом, каждая команда
инициирует одну операцию с одним потоком
данных. Для увеличения скорости обработки
команд и выполнения арифметических операций
может применяться конвейерная обработка: ЭВМ
со скалярными (CDC 6600) и векторными ФУ (CDC
7600) попадают в этот класс.
SIMD (single instruction stream / multiple data stream)
один поток команд, множество потоков данных
Сохраняется один поток команд, включающий, в
отличие от предыдущего класса, векторные
команды.
Это
позволяет
выполнять
одну
арифметическую операцию сразу над многими
данными. Способ выполнения векторных операций
не оговаривается. Обработка элементов вектора
может производиться либо матрицей ПЭ (ILLIAC IV),
либо с помощью конвейера (CRAY-1).

7. Классификация архитектуры вычислительных систем (3)

MISD (multiple instruction stream / single data stream)
– множество потоков команд, один поток данных
Определение подразумевает наличие в архитектуре
многих процессоров, обрабатывающих один и тот
же поток данных. Однако ни Флинн, ни другие
специалисты в области архитектуры компьютеров
до сих пор не смогли представить убедительный
пример реально существующей вычислительной
системы, построенной на данном принципе.
Поэтому данный класс считается пустым.
MIMD (multiple instruction stream / multiple data
stream) – множество потоков команд, множество
потоков данных
Этот класс предполагает, что в вычислительной
системе есть несколько устройств обработки
команд, объединенных в единый комплекс и
работающих каждое со своим потоком команд и
данных. Класс чрезвычайно широк, поскольку
включает
всевозможные
мультипроцессорные
системы: Cm*, C.mmp, CRAY Y-MP, Denelcor HEP,
BBN Butterfly, Intel Paragon, CRAY T3D и др.

8. Классификация архитектуры вычислительных систем (4)

Классификация
Флинна
Плюсы: Классификация Флинна остается самой применяемой при
начальной характеристике того или иного компьютера. Если говорят,
что компьютер принадлежит классу SIMD или MIMD, сразу понятен
базовый принцип его работы, во многих случаях этого достаточно.
Минусы: (1) Не все архитектуры четко не вписываются в классификацию
(2) Класс MIMD чрезмерно заполнен
(3) Архитектуры из одного класса могут существенно различаться
по числу процессоров, топологии связей между ними, способу
организации памяти, и др.
Наличие пустого класса (MISD) – не есть недостаток! Такие классы, по
мнению ряда исследователей, могут быть чрезвычайно полезными
для разработки принципиально новых концепций в теории и практике
построения вычислительных систем.

9. Классификация архитектуры вычислительных систем (5)

Дополнения Ванга и Бриггса к классификации Флинна.
Оставлены четыре ранее введенных базовых класса (SISD, SIMD, MISD,
MIMD)
MIMD:
- вычислительные системы со слабой связью между процессорами,
к которым авторы относят все системы с распределенной памятью
- вычислительные системы с сильной связью (с общей памятью)
SISD:
- архитектуры с единственным функциональным устройством
- архитектуры, имеющие в своем составе несколько ФУ
SIMD:
- ЭВМ с пословно-последовательной обработкой информации
- архитектуры с разрядно-последовательной обработкой
Классификация Хендлера
В основе лежит явное описание возможностей параллельной и
конвейерной обработки информации вычислительной системой.
Способы связи между процессорами и элементами памяти не
рассматриваются.

10. Классификация архитектуры вычислительных систем (6)

Классификация Хокни
разбиение класса MIMD по Флинну на подклассы по способу
обработки множественного потока команд:
– конвейерный,
– параллельный.
Параллельный подкласс, в свою очередь, делится на
– «сети», где нет прямой связи каждого процессора с каждым,
– «переключатели»,где такая связь есть.
«Сети» классифицируются по топологии связей
процессоров:
- регулярные решетки,
- гиперкубы,
- иерархические стуктуры и др.

11. Классификация архитектуры вычислительных систем (7)

Классификация Кришнамарфи
Предложены четыре качественные характеристики параллелизма:
степень параллелизма,
способ реализации,
топология и природа связи процессоров,
способ управления процессорами
Классификация Фенга (1972)
Введены две числовые характеристики
(1) число бит n в машинном слове, обрабатываемых параллельно. В
современных компьютерах n – длина машинного слова.
(2) число слов машинных m, обрабатываемых одновременно.
На основе введенных характеристик получаем четыре класса,
характеризуемых парой чисел (n,m)

12. Классификация архитектуры вычислительных систем (8)

Разрядно-последовательные пословно-последовательные (n=m=1). В
каждый момент времени обрабатывается один двоичный разряд.
Представителем данного класса служит давняя система MINIMA с
естественным описанием (1,1).
Разрядно-параллельные пословно-последовательные (n > 1 , m = 1).
Большинство классических последовательных компьютеров, IBM701 с
описанием (36,1), PDP-11 (16,1), IBM 360/50 с метрикой (32,1).
Разрядно-последовательные пословно-параллельные (n = 1 , m > 1).
Вычислительные системы данного класса состоят из большого числа
одноразрядных процессорных элементов, каждый из которых может
независимо от остальных обрабатывать свои данные. Примеры:
STARAN (1,256), и MPP (1,16384), SOLOMON (1,1024).
Разрядно-параллельные пословно-параллельные (n > 1, m > 1). Большая
часть существующих параллельных вычислительных систем
обрабатывает одновременно m×n двоичных разрядов: ILLIAC IV
(64,64), TI ASC (64,32), CDC6600 (60,10), BBN Butterfly (32,256).
Недостатки: нет различия между процессорными матрицами, векторноконвейерными и многопроцессорными системами. Не ясно, за счет
чего компьютер может одновременно обрабатывать более одного
слова (много ФУ, конвейерность, многопроцессорность).
Достоинство: введение для всех типов ЭВМ единой числовой метрики

13. Методы тестирования производительности (1)

Цели тестирования
Особенности аппаратуры (структура процессора, система команд,
состав ФУ, строение и объем кэш-памяти, реализация ввода\вывода
и др.) оказывают существенное влияние на выполнение реальной
программы.
Поэтому эффективность работы программно-аппаратной среды
оценивается на фиксированном наборе тестовых программ. Такой
набор играет роль эталона, по которому можно судить о
возможностях конкретной вычислительной системы.
Изначально оценочное тестирование на специально подготовленных
для этих целей задачах (бенчмарках) имело цель дать прогноз
относительно возможностей исследуемой системы при решении
интересующего класса задач. Это важное для пользователей
назначение бенчмарков является основным и в настоящее время.
По мере накопления бенчмарков, опыта их использования и результатов
анализа полученных данных стало ясно, что бенчмарки
чрезвычайно полезны для разработчиков вычислительных систем,
позволяя оптимизировать разрабатываемую аппаратуру под
выявленные на бенчмарках закономерности.

14. Методы тестирования производительности (2)

Важность применения оценочного тестирования значительно возросла в
последнее время, когда стало возможным и экономически выгодным
строить системы из готовых компонентов – вычислительных узлов на
базе материнских плат ПК либо рабочих станций, с использованием
высокоскоростных коммутационных сетей. Правильность выбора
компонентов в таких работах – основа успеха.
Производительность ЦП зависит от трех параметров:
- такта (или частоты) синхронизации,
- среднего количества тактов на команду,
- количества выполняемых команд.
Невозможно изменить ни один из указанных параметров изолированно от
другого, поскольку базовые технологии, используемые для изменения
каждого из этих параметров, взаимосвязаны. Поэтому при оценке и
сравнении машин необходимо рассматривать все три компоненты.
Таким образом, оценочное тестирование имеет цели обеспечить
необходимой информацией:
(1) пользователя
(2) разработчика вычислительной системы.
В качестве метрики в бенчмарках используются две характеристики
MIPS – миллионы машинных инструкций в секунду
MFLOPS – миллионы арифметических операций в секунду

15. Методы тестирования производительности (3) «Синтетические» бенчмарки

Типы бенчмарков:
Синтетические тесты
Тесты на основе реальных задач
Синтетический тест Dhrystone
Один из первых тестов на базе MIPS, получивших широкое
распространение. Позволял оценивать эффективность процессоров и
компиляторов с языка C для программ нечисловой обработки.
Тестовая смесь: 53% – операторы присваивания, 32% – операторы
управления, 15% – вызовы функций. Очень короткий тест: общее
число команд равнялось 100. Скорость выполнения программы из
этих 100 команд измерялась в Dhrystone в сек. Быстродействие VAX
11/780 на этом синтетическом тесте составляло 1757 Dhrystone в
секунду. 1 MIPS равен 1757 Dhrystone в секунду.
В настоящее время Dhrystone практически не применяется, т.к. малый
объем позволяет разместить все команды теста в кэш-памяти 1го
уровня современного микропроцессора.
Whetstone – синтетический тест, построенный по такой же схеме,
ориентированный на численное программирование с плавающей
запятой. Не учитывает кэш.

16. Методы тестирования производительности (4)

Набор синтетических тестов STREAM состоит из четырех небольших
циклов, работающих с очень длинными векторами. Цель состоит в
проверке сбалансированности скорости работы процессора
и
скорости доступа к памяти. Ключевыми являются операции
A(i) = b(i)
A(i) = b(i)*q
A(i) = b(i)+c(i)
A(i) = b(i)+c(i)*q
Все тесты работают с 64-разрядными числами. Размеры массивов
подбираются так, чтобы ни один не попадал в кэш-память. Форма
записи теста исключает повторное использование данных, что
исказило бы картину. Результатом тестирования являются
вычисленные реальные значения скорости передачи данных и
производительности.
1й тест – оценка скорости передачи данных в отсутствии арифметики.
2й тест – оценка способности выполнять арифметические операции одновременно с доступом к памяти (тот же объем передаваемых данных)
В 3м тесте появляется второй входной вектор, т.е. увеличивается нагрузка
на тракт процессор – память.
В 4м тесте добавляется еще одна арифметическая операция.
НО! Искусственные тесты не дают реальной картины при решении
конкретных пользовательских задач

17. Методы тестирования производительности (5) LINPACK

LINPACK – наиболее популярный синтетический тест на базе MFLOPS.
Первая версия создана в 1979.
Изначально - пакет фортран-программ для решения систем линейных
алгебраических уравнений (ЛА). Алгоритмы ЛА широко используются,
поэтому измерение производительности на LINPACK представляют
интерес для многих пользователей. В процессе работы пакета
выполняются базовые арифметические действия над матрицами
чисел с плавающей запятой с двойной точностью.
Результат LINPACK–тестирования измеряется в MFLOPS.
Плюсы:
простой алгоритм, регулярные структуры данных, значительная
вычислительная
емкость.
Высокая
корреляция
с
пиковой
производительностью. Не затрагиваются операции ввода\вывода.
Эти «удобные» особенности делают чрезвычайно популярным.
В 1м варианте теста решалась система уравнений с матрицей размером
100х100 элементов. В качестве теста предоставляется уже готовый
исходный текст, в который не разрешается вносить изменений. В
настоящее время матрица 100х100 легко помещается в кэш-памяти
современного процессора.

18. Методы тестирования производительности (6) LINPACK

Во 2м варианте теста размер матриц увеличен до 1000х1000. Разрешено
внесение изменений в тест в части, реализующей метод решения
системы. Неизменной должна оставаться часть кода, выполняющая
инициализацию матрицы и вызывающая стандартные подпрограммы
для решения системы и проверки корректности результатов.
Производительность вычисляется по формуле 2n3/3+2n2, где n –
размер матрицы, независимо от реально используемого алгоритма.
С появлением больших массивно-параллельных ЭВМ вопрос подбора
размера матрицы стал исключительно актуальным. На матрицах
100х100 и 1000х1000 разумных показателей получить не удавалось,
т.к. матрица порядка 1000х1000 занимает порядка 0.01% всей
оперативной памяти подобного компьютера.
Эксперименты на реальных массивно-параллельных компьютерах
показали, что фиксировать размер задачи нельзя.
В 3м варианте теста разрешено использовать методику второго варианта,
но для матриц сколь угодно большого размера. Сколько есть
оперативной памяти на всех узлах системы, столько и надо
использовать.
Для современных компьютеров размер матрицы перевалил за миллион.

19. Методы тестирования производительности (7) LINPACK

Для работы на распределенных вычислительных системах создана
специальная версия теста, HPL, High Performance Linpack.
В HPL пользователь может управлять большим числом параметров для
достижения высокой производительности на своей установке.
В настоящее время Linpack используется для формирования списка
Тор500 – пятисот самых мощных компьютеров мира. Существуют
различные варианты этого теста, адаптированные под различную
архитектуру.
Правилами проведения измерений разрешается модифицировать или
даже полностью переписывать код HPL для оптимизации его под
конкретную архитектуру при условии, что вычисленные решения
проходят проверку на корректность.
Поэтому
неудивителен
факт,
что
каждый
производитель
микропроцессоров стремится выпустить свою версию теста,
способную выжать всю производительность из их аппаратного
обеспечения.

20. Методы тестирования производительности (8) LINPACK

• Intel MP Linpack поставляется компанией Intel в составе своих
пакетов библиотек и компиляторов (частично открытый код)
• Intel SMP Linpack поставляется компанией Intel вместе с
библиотекой MKL (полностью закрытый код)
Однако, нужно ясно понимать, что высокая производительность
Linpack совершенно не означает того, что и на конкретной
программе пользователя будет достигнута такая же высокая
производительность.
Для получения полной картины о возможностях компьютера данных
одного лишь теста Linpack недостаточно.
В реальности – единственной подходящей и надежной
характеристикой
производительности
является
время
выполнения реальных программ, и все предлагаемые замены
реальных программ на синтетические тесты в определенной
степени вводят в заблуждение.
Одно из возможных направлений выхода из данной ситуации –
формирование набора взаимодополняющих тестов на основе
реальных кодов.

21. Методы тестирования производительности (9) Бенчмарки на основе реальных задач

Один из первых пакетов (70е годы), построенных на этом принципе –
Ливерморские циклы, the Livermore Fortran Kernels, LFK. В его
состав вошли вычислительные ядра 24х прикладных программ,
используемых в Ливерморской национальной лаборатории. Тесты
включают вычисление скалярных произведений, рекурсивные
соотношения, вычисление значений полиномов и т.д.
К бенчмаркам тестам этого типа относится также пакет тестов PERFECT
Club Benchmarks (80е годы), включающий 13 реальных
приложений из различных предметных областей (гидродинамика,
прогноз погоды, квантовая механика и др.). Пакет не получил
широкого распространения из-за достаточно сложной адаптации
входящих в него тестов к каждому новому тестируемому компьютеру.
С появлением параллельных вычислительных систем ситуация
ухудшилась, т.к. требовалось переписывать программы в терминах
технологий, реализующих параллельные вычисления на конкретном
компьютере.
Наибольшую известность среди бенчмарков этого типа получил пакет
NAS Parallel Benchmarks (NRB), основанных на реальных кодах
вычислительной гидродинамики и представляющих типичные
вычислительные ядра и модельные приложения.

22. Методы тестирования производительности (10)

Ключевыми в NAS Parallel Benchmarks являются следующие операции.
генерация большого объема псевдослучайных чисел
сортировка большого массива целых чисел
быстрое преобразование Фурье на трехмерной решетке
решение трехмерного уравнения Пуассона многосеточным методом
вычисление наименьшего собственного значения разреженной
симметричной матрицы методом сопряженных градиентов
реализация алгоритма релаксации на регулярно разреженных,
блочных и треугольных системах
решение последовательности независимых 5-диагональных систем
решение блочных трех-диагональных систем
В первой версии фиксировалась только постановка задач, для конкретной
вычислительной системы тесты требовалось переписывать заново.
Во второй версии (1995) фиксировались алгоритмы и тексты программ на
FORTRAN77–MPI, т.е. упор сделан на компьютеры с распределенной
памятью и большим числом процессоров.
Конечно же, для полной оценки эффективности ЭВМ необходимо
тестирование не только производительности, но комплексное
тестирование системы в целом (ОС, скорость, ввод\вывод и т.п.)

23. Реальная и пиковая производительность (1)

Пиковая производительность – суммарная производительность всего
оборудования какого-либо устройства.
Реальная производительность – производительность, которая реально
достигнута при выполнении какой-либо работы.
Эффективность - отношение реальной производительности к пиковой.
Cформулируем все это применительно к вычислительным системам,
состоящим из s функциональных (вычислительных) устройств – ФУ.
Стоимость операции – это время ее выполнения.
Стоимость работы – время последовательной реализации всех операций
на простых (не конвейерных) ФУ.
Максимальная стоимость работы ФУ за период Т равна Т для простых ФУ
и nT для конвейерных ФУ с n ступенями.
Загруженность ФУ на данном отрезке времени – отношение стоимости
реально выполненной работы за этот отрезок к максимально возможной
стоимости на данном устройстве.
Загруженность Р всегда удовлетворяет соотношению 0 P 1.
Реальная производительность системы ФУ – количество операций,
выполненное реально в среднем за единицу времени.
Пиковая производительность – максимальное количество операций,
которое может быть выполнено той же системой за единицу времени.

24. Реальная и пиковая производительность (2)

И реальная, и пиковая производительности равны сумме
производительностей составляющих их устройств.
Пусть система состоит из s устройств одинаковой пиковой
производительности (простых или конвейерных).
Можно показать, что:
- Загруженность системы – среднее арифметическое
загруженностей всех ФУ.
- Реальная производительность – сумма реальных
производительностей одного ФУ
- Пиковая производительность системы в s раз больше
пиковой производительности одного ФУ.
- Производительность вычислительной системы, состоящей
из связанных между собой устройств, в общем случае
определяется ее самым непроизводительным устройством (иногда
это утверждение называют 1-м законом Амдала).
- Асимптотическая производительность системы будет
максимальной, если все устройства имеют одинаковые пиковые
производительности (следствие предыдущего утверждения).

25. ЗАКОН АМДАЛА (Gene Amdahl, 1967)

Описывает предел эффекта от
параллельного выполнения
программы.
Пусть 0 <= S <= 1 – часть операций в нашей
программе, выполняемая последовательно.
• P – число параллельных ФУ, выполняющих
нашу программу.
• Ускорение А (отношение времени выполнения
программу на одном ФУ ко времени
выполнения на Р устройствах) можно оценить
как
Code
S
1-S
a = b+c;
d = e+f;
Параллельно!!! (1-s)
a = b+c;
d = a+f;
(s) Последовательно!!!

26. Закон Амдала и его следствия (1)

Пусть в нашей программе доля операций, которые нужно выполнять
последовательно, равна s=N/n, где N – последовательные операции, n
– все операции. Случаи s=0 и s=1 соответствуют полностью
параллельным и полностью последовательным программам.
Чтобы оценить, какое ускорение A может быть получено на
компьютере из P процессоров при данном значении s, можно
воспользоваться 2м законом Амдала (или просто Законом Амдала):
A = P / [P×s + (1-s)] = 1 / [s + (1-s)/P].
• Пусть – время выполнения одной операции.
• Тогда время реализации всего алгоритмa на одном ФУ:
Т1 = n ×
• Время реализации параллельной части (n-N операций) на каждом ФУ:
Tn-N = [(n-N)/P] ×
• N последовательных операций все равно выполняются на одном ФУ за:
TN = N ×
• Время параллельной реализации алгоритма на P ФУ:
ТP = TN + Tn-N = N× + [(n-N)/P]×
• Тогда ускорение равно
A = T1/TP = [n× ] / [N× + [(n-N)/P]× ]] = n /[N + (n-N)/P] =
P /[s×P + (1- s)] (разделили на n, умножили на Р)

27. Закон Амдала и его следствия (2)

Формулу Амдала применяют для
асимптотического прогноза
ускорения на основе теоретической
оценки доли параллельных
вычислений в программе. Нет
необходимости реально запускать
программу.
s 0 при конечном P:
A = P / [P×s + (1-s)] P
т.е. ускорение пропорционально Р.
P при фиксированном s:
A = P / [P×s + (1-s)] =
= 1 / [s + (1-s)/P] 1/s
т.е. ускорение обратно
пропорционально s.
Вывод.
Прямое увеличение числа
процессоров НЕ приводит к пропорциональному ускорению!

28. Закон Амдала и его следствия (3)

Пример. Если 9/10 программы исполняется параллельно, а 1/10
последовательно, то ускорения более, чем в 10 раз, получить в
принципе невозможно вне зависимости от качества реализации
параллельной части кода и числа используемых процессоров (ясно, что
10 получается только в том случае, когда время исполнения
параллельной части равно 0).
Посмотрим на проблему с другой стороны: какую часть кода надо ускорить,
чтобы получить заданное ускорение?
Ответ дает Следствие из закона Амдала
Пусть система состоит из простых одинаковых универсальных устройств
(связных). При любом режиме работы ее ускорение не может превзойти
обратной величины от доли последовательных вычислений A<1/s.
Итак, для того чтобы ускорить выполнение программы в q раз, необходимо
ускорить не менее, чем в q раз не менее, чем (1-1/q)-ю часть программы.
Значит, если хочется ускорить программу в 100 раз по сравнению
последовательным вариантом, необходимо ускорить не меньше, чем в
100 раз не менее, чем на 99.99% кода, что фактически нереально.
Вывод. прежде, чем переделывать код для перехода на параллельный
компьютер, надо оценить заложенный в программе алгоритм. Если
доля последовательных вычислений велика, то на значительное
ускорение рассчитывать явно не приходится и нужно думать о замене
отдельных компонент алгоритма.

29. Что еще влияет на производительность вычислительных систем, кроме закона Амдала?


Особенности архитектуры конкретной машины
Процессоры разнородны по своей производительности.
Неравномерность загрузки (несбалансированна работа ФУ)
Передача данных требует времени (ограниченная пропускная
способность каналов связи)
Курьезный пример. Пусть имеем систему из двух простых ФУ – сумматор и
умножитель. Нужно посчитать сумму двух матриц, С=А+В. Умножитель,
простаивает, значит, реальная произв-сть = 1/2 пиковой. Запишем
задачу в виде С=А+В×1, формально реальная произв-сть приблизится
к пиковой, хотя объем полезной работы не изменится.
Пример изменения последовательного кода на параллельный
Строго последовательный алгоритм, т.к. на i-й итерации цикла нужен
результат (i-1)-й:
S = 0;
for( i = 0; i<n; i++)
S += a[i];
Если нет существенной разницы, в каком порядке складывать числа,
выберем иную схему сложения. Например, один из вариантов:
s1 = 0;
s2 = 0;
for(i = 0; i<n/2; i++)
for(i = n/2; i<n; i++)
s1 += a[i];
s2 += a[i];
S=s1+s2;
English     Русский Rules