1 Организация вычислительной системы ЛЕКЦИЯ 2 Калинина А.П.

2 1. Введение. Основные понятия и определения 1.1. Базовые определения (архитектура ЭВМ, архитектура набора команд, организация вычислительной системы, архитектура высокопроизводительной системы) 1.2. Обоснование данной последовательности изложения материала 1.3. Рекомендуемые курсы, доступные в интернете

Базовые определения Архитектура ЭВМ (компьютера) - это совокупность архитектуры набора команд и организации вычислительной системы Архитектура ЭВМ (компьютера) - это совокупность архитектуры набора команд и организации вычислительной системы Архитектура набора команд (система команд) – граница между аппаратурой и программным обеспечением, представляющая собой ту часть системы, которая видна программисту или разработчику компиляторов Архитектура набора команд (система команд) – граница между аппаратурой и программным обеспечением, представляющая собой ту часть системы, которая видна программисту или разработчику компиляторов Заметим, что архитектура компьютера определяет концептуальную структуру и функциональное поведение, но не отражает такие проблемы, как передача потоков даннных внутри процессора, конструктивные особенности логических схем и специфика технологии производства Заметим, что архитектура компьютера определяет концептуальную структуру и функциональное поведение, но не отражает такие проблемы, как передача потоков даннных внутри процессора, конструктивные особенности логических схем и специфика технологии производства 1. Введение. Основные понятия и определения

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

5 Пример организации вычислительной системы с общей памятью(1) 1.1. Базовые определения

6 Пример организации вычислительной системы с общей памятью (2) Intel® Core Duo Processor 1.1. Базовые определения EXE Core FP Unit EXE Core FP Unit L2 Cache L1 Cache System Bus (667MHz, 5333MB/s) System Bus (667MHz, 5333MB/s)

Базовые определения 1. Введение. Основные понятия и определения

Обоснование данной последовательности изложения материала Данный курс, в первую очередь, рассчитан на тех, кто Данный курс, в первую очередь, рассчитан на тех, кто имеет самые общие представления и об операционных, и об архитектурных платформах, но, тем не менее, нуждается в высокопроизводительных вычислениях Поэтому первая задача, которую мы должны решить в пределах данного курса – это ответить на вопрос – а почему мы должны изучать и архитектурную, и операционную платформу? Поэтому первая задача, которую мы должны решить в пределах данного курса – это ответить на вопрос – а почему мы должны изучать и архитектурную, и операционную платформу? Наиболее быстро это можно сделать, дав простейшие представления об организации вычислительной системы и аппаратных ограничениях, и, разумеется, показав на ярких практических примерах, как это проявляется в жизни Наиболее быстро это можно сделать, дав простейшие представления об организации вычислительной системы и аппаратных ограничениях, и, разумеется, показав на ярких практических примерах, как это проявляется в жизни кроме того, ведь курс называется – «практическое параллельное программирование...» кроме того, ведь курс называется – «практическое параллельное программирование...»

Рекомендуемые курсы, доступные в интернете «Архитектуры и топологии многопроцессорных систем» Богданов А.В., Станкова Е.Н., Мареев В.В., Корхов В.В. «Архитектуры и топологии многопроцессорных систем» Богданов А.В., Станкова Е.Н., Мареев В.В., Корхов В.В. «Архитектура и организация ЭВМ» Гуров В.В., Чуканов В.В. / «Архитектура и организация ЭВМ» Гуров В.В., Чуканов В.В. / / / «Архитектурно – ориентированная оптимизация программ» Долгов Ю.В., Шкурко Д.В. lab.nsu.ru/index.php?file=spec «Архитектурно – ориентированная оптимизация программ» Долгов Ю.В., Шкурко Д.В. lab.nsu.ru/index.php?file=spechttp:// lab.nsu.ru/index.php?file=spechttp:// lab.nsu.ru/index.php?file=spec 1. Введение. Основные понятия и определения

10 2. Организация вычислительной системы 2.1. Главная характеристика многопроцессорной системы – производительность. Пиковая и реальная производительность 2.2. Способы измерения реальной производительности (самостоятельно) 2.3. Два из наиболее важных факторов, влияющих на производительность, с точки зрения аппаратных ограничений 2.4. Взаимодействие элементов кэш-памяти и кэш памяти с оперативной памятью 2.5. Аппаратные ограничения и рекомендации по выбору параллельного алгоритма (с точки зрения аппаратных ограничений) для систем с общей памятью 2.6. Демонстрационные примеры о действии аппаратных ограничений

Главная характеристика многопроцессорной системы – производительность. Пиковая и реальная производительность Главной отличительной особенностью многопроцессорной вычислительной системы является ее производительность, т.е. количество операций, производимых системой за единицу времени. Различают два типа производительности: Пиковую (число процессоров умножить на производительность одного ) Пиковую (число процессоров умножить на производительность одного ) Реальную (по системе тестов) Реальную (по системе тестов) Пиковую производительность оценивают в число команд, выполняемых компьютером за единицу времени. Единицей измерения, как правило, является MIPS (Million Instructions Per Second) число команд, выполняемых компьютером за единицу времени. Единицей измерения, как правило, является MIPS (Million Instructions Per Second) (Floating point operations per second) – число операций с плавающей точкой, производимых компьютером за одну секунду. (Floating point operations per second) – число операций с плавающей точкой, производимых компьютером за одну секунду.

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

13 Латентность при обращении к различным иерархическим уровням памяти. Пример: Origin2000 memory hierarchy Level Latency (cycles) Latency (cycles) register register0 primary cache primary cache2..3 secondary cache secondary cache8…10 local main memory & TLB hit 75 remote main memory & TLB hit 250 main memory & TLB miss 2000 page fault 10^6

14 Сравнение характеристик различных классов памяти Класс памяти Доступ в наносекундах Объем в килобайтах Кэш процессора 3 32 Кэш 2-ого уровня Основная память Дисковая (вторичная память)

Взаимодействие элементов кэш-памяти и кэш памяти с оперативной памятью Внутренняя структура аппаратной кэш-памяти обычно достаточно сложна: она представляет собой иерархию модулей, в которой каждый следующий модуль является более вместительным, но функционирует медленнее, чем предыдущий». Важно отметить, что передача данных между различными уровнями кэша и между кэшем и оперативной памятью производится не отдельными байтами или машинными словами, а так называемыми строками кэша. «Размер строки кэша (оперативная память-кэш), как правило, составляет 32 или 64 байта. Пакетная передача» (burst transfer) этого типа поддерживается аппаратно и обусловлена вторым типичным свойством программного обеспечения – пространственной локализацией доступа, то есть значительной вероятностью обращения по последовательным адресам.

Аппаратные ограничения и рекомендации по выбору параллельного алгоритма (с точки зрения аппаратных ограничений) для систем с общей памятью

Аппаратные ограничения и рекомендации по выбору параллельного алгоритма (с точки зрения аппаратных ограничений) для систем с общей памятью

Аппаратные ограничения и рекомендации по выбору параллельного алгоритма (с точки зрения аппаратных ограничений) для систем с общей памятью Заметим, что элемент структуры, ответственный за объединение отдельных единиц в единое целое, будет всегда одним из «узких мест» (не обязательно единственным). Для многопроцессорной системы с общей памятью, где объединение осуществляется посредством шины, аппаратным ограничением на производительность будет пропускная способность шины. Д ля многоядерной системы затраты на организацию передачи пропорциональны минимальному времени обращения из первого кэша во второй (порядка десяти циклов процессора) и зависят от размера второго кэша.

Демонстрационные примеры о действии аппаратных ограничений Пример на демонстрацию иерархической организации памяти – нелинейное возрастание времени работы программы в зависимости от линейной сложности задачи Уменьшение ускорения параллельной программы при увеличении потока данных через шину и объема данных, загружаемых в кэш (OpenMP)

Пример на демонстрацию иерархической организации памяти – нелинейное возрастание времени работы программы в зависимости от линейной сложности задачи for (j=1; j limit) { Weight_PathMin = treeData.max+limit; if (Weight_PathMin > limit) { replace_number = treeData.Weight[i]; } }

Пример на демонстрацию иерархической организации памяти – нелинейное возрастание времени работы программы в зависимости от линейной сложности задачи

22 Диагностика эффективности работы с памятью – VTune Performance Analyzer, Sampling Analysis

23 Задание Открыть проект «Поиск кратчайших путей на графе» и измерить ускорение каждой из параллельых схем: «деление через итерацию», (а) - аргументы в командной строке (каждый поток обрабатывает весь массив, через шину передается двойной объем массивов) «тебе половина, мне половина массива», (в) – аргументы в командной строке (каждый поток обрабатывает половину массива, через шину передается тот же объем массива, что и в последовательной программе) Последовательная программа – аргументы в командной строке

24 Параллельная схема: вызывающая функция omp_set_num_threads (num_threads); //определяется число потоков #pragma omp parallel private(id) //создается параллельный регион { id = omp_get_thread_num(); //определяется номер потока Search_Path (id, Nomer_nmin, MinimPath, treeData.Path, treeData.Short_Path, treeData.Weight_Weight, treeData.Weight_Parents, treeData.N, num_threads);//вызов функции с параметром – номером потока }

25 Параллельная схема: вариант «пополам» в вызываемой функции N_Section = n/num_threads; Initial = myID*N_Section; Final = (myID + 1)*N_Section; if(Initial == 0) { Initial = 1; } if(myID == (num_threads - 1)) { Final = n; } for (l = Initial; l < Final; l++) // cycle of the New Path evaluation { ……… //обработка элементов массивов с номерами [i] } //__the end of cycle of the new Path evaluation

26 Параллельная схема: вариант «четные» - «нечетные» в вызываемой функции Initial = myID+1; Final = n; Metka = Initial; for (i = Initial; i < Final; i+=num_threads) { …… //обработка элементов массивов с номерами [i] }

Уменьшение ускорения параллельной программы при увеличении потока данных через шину и объема данных, загружаемых в кэш (OpenMP) Выбор схемы распараллеливания

Уменьшение ускорения параллельной программы при увеличении потока данных через шину и объема данных, загружаемых в кэш (OpenMP) Ускорение параллельной программы Влияние типа параллельной схемы на эффективность компиляции Необходимо выполнить запуски («Debug» и «Release»)со следующими значениями аргументов в командной строке: последовательный вариант 4: 1) параллельные варианты: 2) (схема (в) ) 3) (схема (а) ) 4) ) )

Уменьшение ускорения параллельной программы при увеличении потока данных через шину и объема данных, загружаемых в кэш (OpenMP) Передача данных процессорам в схеме «пополам»

Уменьшение ускорения параллельной программы при увеличении потока данных через шину и объема данных, загружаемых в кэш (OpenMP) Передача данных процессорам в схеме «четные» - «нечетные»

Уменьшение ускорения параллельной программы при увеличении потока данных через шину и объема данных, загружаемых в кэш (OpenMP) Видно, что в случае схемы «четные»-«нечетные» объем информации, передаваемой через шину, в два раза больше. Это связано с тем, что массивы в языке СИ располагаются в памяти «по строкам». Следовательно, для схемы «четные»- «нечетные» можно ожидать меньшего ускорения параллельной программы, что мы и наблюдаем

Уменьшение ускорения параллельной программы при увеличении потока данных через шину и объема данных, загружаемых в кэш (OpenMP) Ускорение

Уменьшение ускорения параллельной программы при увеличении потока данных через шину и объема данных, загружаемых в кэш (OpenMP) Ускорение Заметим, что схема «четные»-«нечетные» (3) практически не оптимизируется компилятором – он «видит зависимости по данным»!

34 ЛИТЕРАТУРА 1. И. Одинцов Профессиональное программирование. Системный подход. – «БХВ-Петербург» – 610 с Джин Бэкон, Тим Харрис Операционные системы. Параллельные и распределенные системы. – bhv «Питер» – 799 с. 3. «Архитектуры и топологии многопроцессорных систем» Богданов А.В., Станкова Е.Н., Мареев В.В., Корхов В.В «Архитектура и организация ЭВМ» Гуров В.В., Чуканов В.В «Архитектурно – ориентированная оптимизация программ» Долгов Ю.В., Шкурко Д.В. lab.nsu.ru/index.php?file=spec lab.nsu.ru/index.php?file=spechttp:// lab.nsu.ru/index.php?file=spec