4568
Использование параллелизма процессора для повышения эффективности программ
Лабораторная работа
Информатика, кибернетика и программирование
Использование параллелизма процессора для повышения эффективности программ Цель работы: научить студента самостоятельно разрабатывать максимально эффективные программы. Материал для изучения. Рассмотрим задачу умножения двух n ...
Русский
2012-11-22
35.5 KB
6 чел.
Использование параллелизма процессора для повышения эффективности программ
Цель работы: научить студента самостоятельно разрабатывать максимально эффективные программы.
Материал для изучения.
Рассмотрим задачу умножения двух n n квадратных матриц: С = АВ.
Элементы матриц хранятся по строкам, а именно сначала хранятся элементы первой строки, затем второй и т.д.
Таким образом. Последовательнее элементы строки матрицы лежат друг за другом и доступ к ним будет максимально быстрым. Так как стратегия предвыборки элементов в кэш (т.е. чтение каждый раз целого блока оперативной памяти, равного по размеру строке кэша) себя полностью оправдывает. С другой стороны, последовательные элементы столбца матрицы лежат на расстоянии n* sizeof(double) байт друг от друга и доступ к ним будет максимально медленным (поскольку строка кэш-памяти существенно меньше расстояния между элементами).
Вычислим произведение матриц несколькими способами.
1. Стандартный способ. Цикл проведем по строкам матрицы.
для всех m = 1, 2,…,n
для всех i = 1, 2,…,n
вычислить
В цикле по j (вычисление суммы) элементы одной строки матрицы А (к которым быстрый доступ) будут использованы многократно (в цикле по i), элементы же столбцов матрицы В (к которым относительно медленный доступ) повторно (в цикле по i) не используются. Тем самым при доступе к элементам В кэш-память практически ничего не дает.
2. Цикл по столбцам матрицы.
для всех m = 1, 2,…,n
для всех i = 1, 2,…,n
вычислить
В цикле по j (вычисление суммы) элементы матрицы А повторно (в цикле по i) не используются. Элементы же столбцов матрицы В используются много кратно (в цикле по i). Кэш память ускоряет доступ к элементам А за счет предвыборки подряд идущих элементов, и ускоряет доступ к элементам В, если столбец целиком поместился в кэш память (тогда в цикле по i обращение к элементам В в оперативной памяти будет только на первом шаге). Отметим, что если размер кэш памяти недостаточен (например n велико), то этот способ может оказаться хуже предыдущего, т.к. ухудшился способ доступа к А и не получен выигрыш при доступе к В.
3. Третий метод.
Цикл проведем по N N, N=10 блокам матрицы С, внутри блока идем по столбцам.
для всех bm = 1, 1+N, 1+2N, … , bm < n
для всех bi = 1, 1+N, 1+2N, … , bi < n
для всех m= bm, bm+1, …, bm+N-1, m<n
для всех i=bi, bi+1, … , bi+N-1, i < n
вычислять
В этом случае большой выигрыш в скорости получаем в том случае если используемые в циклах по m, i, j N строк матрицы А и N столбцов матрицы В поместились в кэш память. Если n настолько велико что даже один столбец матрицы В не поместился целиком в кэш, то этот способ может оказаться хуже самого первого.
4. Зададим параметр N таким, что n делится на N нацело. Тогда всякая матрица М может быть представлена:
Где Mij NN матрица, k=n/N. Тогда каждый блок Cim произведения С=АВ матриц А и В может быть вычислен через блоки матриц А и В.
В вычислении произведения NN матрица матриц Aij и Bjm участвует только подмножество их N2 элементов матриц А и В . При небольшом N это подмножество полностью поместится в кэш-памяти и каждое слагаемое послежней суммы быдет вычислено максимально быстро.
5. В предыдущих вариантах преимущества кэш-памяти почти уже были исчерпаны. Для получения дальнейшего прироста производительности вспомним о конвейерной организации процессора (современные процессоры имеют конвейер инструкций, достаточно глубокий). Для его заполнения длина линейного участка программы должна быть как минимум больше глубины конвейера (желательно в несколько раз ). Во всех предыдущих вариантах в самом внутреннем цикле (по j) находится оператор языка, который, в зависимости от целевого процессора, транслируется компилятором в 7 … 12 инструкций (включая операторы обслуживания цикла). Для увеличения линейного участка программы в предыдущем варианте реализуем цикл следующим образом:
За один проход цикла по j будем вычислять сразу 4 элемента матрицы С ci,m, ci,m+1, ci+1,m, ci+1,m+1. Поскольку при их вычислении используются повторяющиеся элементы матриц А и В, то также появляются дополнительные резервы для ускорения работы за счет оптимизации компилятора и кэш памяти.
Задание к лабораторной работе.
1. Запрограммировать алгоритмы умножения матриц.
2. Повести эксперименты на ЭВМ с разными процессорами.
3. Построить таблицу соотношения скорости работы различных алгоритмов умножения матриц. (матрицы брать размерностью 10001000, 50005000, 1000010000 ). В таблицу заносить значения: отношения времени работы первого варианта к времени работы каждого из пяти вариантов.
4. Написать отчет.
5. Защитить у преподавателя.
Дополнительная литература:
Богачёв К.Ю. Основы параллельного программирования / К.Ю. Богачев. М.: БИНОМ. Лаборатория знаний, 2003. 342 с.
А также другие работы, которые могут Вас заинтересовать | |||
52799. | СЦЕНАРІЙ ЛІТЕРАТУРНО-МИСТЕЦЬКОГО ЗАХОДУ «ДЖЕРЕЛО ТВОРЧОСТІ» | 176.5 KB | |
Якою джерельною чистою мовою говориш ти сьогодні. 1ша ведуча Звичайно джерельною А ти взагалі бачив джерельце Ти бачив те маленьке диво чудо природи Як воно ніжне але таке сильне виплескує на землю воду потім утворює струмок напуває річку несе воду до моря А море живить океан океан життя океан творчості 2й ведучий Твоя розповідь нагадала мені як у нашому житті зявляється творча особистість як проходить її становлення як вона самореалізується. 2й ведучий Ласкаво просимо з нами побувати у мандрівці Разом з... | |||
52800. | Сценарій свята Останнього дзвоника | 96 KB | |
Ведучий 1: Увага Увага Увага Учень: День сьогодні такий незвичний Сонце встало умите в росі Скликав в школу нас дзвоник останній І зібрались на свято усі. Ведучий 2: Але стривайте Яке ж свято без випускників початкової школи Тож давайте запросимо їх на урочисту лінійку Ведучий 1: Злинь же музико в небо гучніше В добру пору лунай в добрий час Вище голови Йдіть веселіше Бо усі вже чекають на вас Звучить музика. Ведучий 2: Свято... | |||
52802. | Свято Першого дзвоника | 51 KB | |
Ведучий Знову свята радісні хвилини Безліч вересневих привітань. Ведучий Заходьте дружно та сміливо Маленькі школярі до нас. Ведучий Увага Зустрічайте 1 клас. Ведуча Нехай на нас чекають добрі зміни У наших свят традиція одна: Хай майорить над нами прапор України Стояти струнко Гімн держави пролуна Ведучий Школо До слухання Державного Гімну України стояти струнко. | |||
52805. | EASTER | 85.5 KB | |
Jesus Christ, the Son of God, was resurrected (воскрес) and the Cross is a very important symbol. The egg is a symbol of a new life. Easter eggs are mostly red and are very beautiful. People decorate eggs in many ways. | |||
52806. | Використання методу проектів на уроках біології | 2.75 MB | |
Учитель повинен розвивати в учнів навички які потрібні людині ХХІ століття: відповідальність та адаптивність критичне та системне мислення вміння працювати з інформацією та медіазасобами ставити та вирішувати проблеми направленість на саморозвиток творчість і допитливість та інші. Сьогодні більшість учнів мотивована на стійке незалежне цілеспрямоване і самостійне навчання. Метод проектів вимагає ретельної підготовки вчителя оскільки від того наскільки він зможе зацікавити учнів темою проекту буде залежати і результативність роботи... | |||
52807. | Менеджмент у підприємницькій діяльності | 2.44 MB | |
Мета: познайомити з функціями менеджменту складанням бізнесплану; розвиватися вміння практикуватися в прийнятті управлінських рішень організаційній структурі підприємства. Знаючи сильні і слабкі боки свого підприємства економіст може запропонувати найефективнішу стратегію розвитку. Наприклад розпочати кар'єру з позиції рядового бухгалтера і поступово дорости до фінансового директора підприємства. Аналізуючи дані бухобліку економіст шукає шляхи оптимізації бізнесу вираховує слабкі місця у роботі підприємства: фонд... | |||