|
|
| (не показана 1 промежуточная версия 1 участника) |
| Строка 1: |
Строка 1: |
| − | == Описание свойств и структуры алгоритма ==
| + | #перенаправление [[Обратная подстановка (вещественный вариант)]] |
| − | === Общее описание алгоритма ===
| |
| − | === Математическое описание ===
| |
| − | === Вычислительное ядро алгоритма ===
| |
| − | === Макроструктура алгоритма ===
| |
| − | === Описание схемы реализации последовательного алгоритма ===
| |
| − | === Последовательная сложность алгоритма ===
| |
| − | === Информационный граф ===
| |
| − | === Описание ресурса параллелизма алгоритма ===
| |
| − | === Описание входных и выходных данных ===
| |
| − | === Свойства алгоритма ===
| |
| − | == Программная реализация ==
| |
| − | === Особенности реализации последовательного алгоритма ===
| |
| − | === Описание локальности данных и вычислений ===
| |
| − | ==== Описание локальности алгоритма ====
| |
| − | ==== Описание локальности реализации алгоритма ====
| |
| − | ===== Описание структуры обращений в память и качественная оценка локальности =====
| |
| − | | |
| − | [[file:gauss back 1.PNG|thumb|center|700px|Рисунок 12.1. Обратный ход метода Гаусса решения СЛАУ. Общий профиль обращений в память]] | |
| − | | |
| − | На рисунке 12.1 представлен профиль обращений в память для обратного хода метода Гаусса решения СЛАУ. Хорошо видно, что профиль состоит из двух этапов, идущих друг за другом (граница между ними выделена оранжевой линией). Это соответствует двум циклам, из которых собственно состоит исходный код обратного хода метода Гаусса. Из самого рисунка это заметить достаточно сложно, но анализ исходного кода показывает, что профиль образуется из обращений к 4 массивам. Три из них выделены на рис. 12.1 зеленым; к четвертому относятся все остальные обращения. Сразу отметим, что в данном профиле общее число обращений всего в несколько раз больше числа задействованных элементов массивов (4500 против 1000), а в таких условиях сложно добиться высокой локальности.
| |
| − | | |
| − | Чтобы выяснить это, перейдем к подробному рассмотрению каждого из массивов в отдельности.
| |
| − | | |
| − | На рис. 12.2 представлен фрагмент 1. Оранжевой линей также проведено разделение 2 этапов. Видно, что второй этап устроен очень просто и представляет собой последовательный перебор в обратном порядке. Первый этап имеет итерационный характер, причем на каждой итерации отбрасывается элемент массива с наименьшим номером. Подобный профиль характеризуется высокой пространственной локальностью, поскольку элементы перебираются подряд; достаточно высокой временной локальностью, поскольку на каждой итерации происходит повторное обращение к тем же элементам.
| |
| − | | |
| − | [[file:gauss back 2.PNG|thumb|center|700px|Рисунок 12.2. Фрагмент 1 (профиль обращений к первому массиву)]]
| |
| − | | |
| − | На рис. 12.3 представлен фрагмент 2, показывающий обращения ко второму массиву. Сразу заметим, что данный фрагмент еще меньше предыдущего – здесь задействовано всего 600 обращений в память. По сути, данный фрагмент является аналогичным этапу 1 фрагмент 1, с единственной разницей – здесь итерации расположены в обратном порядке. Однако это изменение не оказывает особого влияния ни на пространственную, ни не временную локальность, поэтому данный фрагмент обладает теми же свойствами.
| |
| − | | |
| − | [[file:gauss back 3.PNG|thumb|center|700px|Рисунок 12.3. Фрагмент 2 (профиль обращений ко второму массиву)]]
| |
| − | | |
| − | Далее рассмотрим фрагмент 3 (рис. 12.4). Здесь также оранжевой линией проведено разделение между двумя этапами, и также на второй этап приходится совсем немного обращений. Обращения на первом этапе образуют аналог случайного доступа, достаточно часто встречающийся, например, в случае косвенной адресации. При этом в некоторый момент к определенному элементу происходит достаточно много обращений подряд, после чего этот элемент более не используется. Такой профиль обычно характеризуется низкой пространственной и временной локальностью, что, однако, в данном случае в достаточной степени нивелируется малым числом задействованных элементов.
| |
| − | | |
| − | [[file:gauss back 4.PNG|thumb|center|700px|Рисунок 12.4. Фрагмент 3 (профиль обращений к третьему массиву)]]
| |
| − | | |
| − | Далее перейдем к фрагменту, занимающему основную часть рис. 12.1. Данный профиль отображен на рис. 12.5. В первую очередь стоит отметить особенность данного профиля – здесь задействовано более 1000 элементов, в то время как в остальных профилям – порядка 30. При этом число обращений даже меньше, чем обращений к первому или третьему массиву.
| |
| − | | |
| − | Отметим также, что здесь большая часть обращений сосредоточена на втором этапе. Первый же этап является подобием первого этапа предыдущего массива (рис. 12.4) , за тем лишь исключением, что в данном профиле отсутствуют множественные обращения подряд к одному элементу перед тем, как элемент перестанет использоваться. С учетом того, что первый этап состоит всего из порядка 500 обращений, достаточно равномерно распределенных на отрезке в 1000 элементов, это говорит об очень низкой как пространственной, так и временной локальности.
| |
| − | | |
| − | Другой характер обращений можно наблюдать на втором этапе. Видно, что он обладает более высокой пространственной локальностью, так как обращения явно сгруппированы в кластеры, при этом кластеры обладают подобным строением. Однако структура самого кластера видно плохо, поэтому требуется дальнейшее приближение.
| |
| − | | |
| − | [[file:gauss back 5.PNG|thumb|center|700px|Рисунок 12.5. Фрагмент 4 (профиль обращений к четвертому массиву)]]
| |
| − | | |
| − | На рис. 12.6 показаны два кластера, выделенные на рис. 12.5 зеленым цветом. Такой масштаб позволяет сразу увидеть, что каждый кластер представляет собой последовательный перебор с небольшим шагом определенного набора элементов массива.
| |
| − | | |
| − | Следовательно, можно говорить о том, что второй этап фрагмента 4 обладает достаточно высокой пространственной локальностью (поскольку каждый кластер содержит последовательный перебор), но низкой временной локальностью (повторные обращения практически отсутствуют).
| |
| − | | |
| − | [[file:gauss back 6.PNG|thumb|center|500px|Рисунок 12.6. Два кластера из фрагмента 4]]
| |
| − | | |
| − | В целом по всему профилю можно сделать следующий вывод: первый три рассмотренных массива (особенно №1 и №2) обладают достаточно высокой локальностью, однако достаточно низкая пространственная и очень низкая временная локальность последнего массива в значительной степени снижают общую локальность всей программы.
| |
| − | | |
| − | ===== Количественная оценка локальности =====
| |
| − | | |
| − | Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
| |
| − | | |
| − | На рисунке 12.7 значения приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что, в соответствии с высказанным в предыдущем разделе предположением о негативном влиянии одного из массивов, данная программа показывает достаточно низкую производительность, заметно ниже, чем у прямого хода метода Гаусса.
| |
| − | | |
| − | [[file:gauss back daps ru.PNG|thumb|center|700px|Рисунок 12.7. Сравнение значений оценки daps]]
| |
| − | | |
| − | Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
| |
| − | | |
| − | На рисунке 12.8 значения приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, профиль обращений обладает низкой локальностью, лишь немногим лучше профиля программы со случайным доступом в память. Это повторяет выводы, сделанные на основе оценки daps.
| |
| − | | |
| − | [[file:gauss back cvg.PNG|thumb|center|700px|Рисунок 12.8. Сравнение значений оценки cvg]]
| |
| − | | |
| − | === Возможные способы и особенности реализации параллельного алгоритма ===
| |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − | ==== Описание масштабируемости алгоритма ====
| |
| − | ==== Описание масштабируемости реализации алгоритма ====
| |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − | === Выводы для классов архитектур ===
| |
| − | === Существующие реализации алгоритма ===
| |
