Описание локальности алгоритма: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
ASA (обсуждение | вклад) (Новая страница: «''Временна́я локальность''. Как хорошо видно из структуры графа алгоритма ([[1.7. Информаци…») |
|||
| Строка 2: | Строка 2: | ||
''Пространственная локальность''. Она различна для разных вариантов расположения циклов. Так, в случае хранения массива по столбцам (стандартного в Фортране) предпочтительна вторая схема; тогда вычисленный уже столбец L сразу используется, и затем к нему программа уже не обращается. В обратном же случае (что нехарактерно для Фортрана; однако его можно реализовать хранением верхнего треугольника матриц, а не нижнего) предпочтительна по тем же причинам первая схема: там скалярные произведения (внутренние циклы) выполняются над идущими подряд фрагментами памяти. | ''Пространственная локальность''. Она различна для разных вариантов расположения циклов. Так, в случае хранения массива по столбцам (стандартного в Фортране) предпочтительна вторая схема; тогда вычисленный уже столбец L сразу используется, и затем к нему программа уже не обращается. В обратном же случае (что нехарактерно для Фортрана; однако его можно реализовать хранением верхнего треугольника матриц, а не нижнего) предпочтительна по тем же причинам первая схема: там скалярные произведения (внутренние циклы) выполняются над идущими подряд фрагментами памяти. | ||
| + | |||
| + | [[Категория:Algowiki:Справка]] | ||
Текущая версия на 15:19, 8 июля 2016
Временна́я локальность. Как хорошо видно из структуры графа алгоритма (п.1.7), метод Холецкого обладает хорошей временной локальностью по основным циклам программы. Данные, необходимые для вычислений, передаются обычно или в рамках той же итерации цикла, или от соседней итерации.
Пространственная локальность. Она различна для разных вариантов расположения циклов. Так, в случае хранения массива по столбцам (стандартного в Фортране) предпочтительна вторая схема; тогда вычисленный уже столбец L сразу используется, и затем к нему программа уже не обращается. В обратном же случае (что нехарактерно для Фортрана; однако его можно реализовать хранением верхнего треугольника матриц, а не нижнего) предпочтительна по тем же причинам первая схема: там скалярные произведения (внутренние циклы) выполняются над идущими подряд фрагментами памяти.
