Intel Parallel Programming Professional (Introduction)

Упражнение 1:

Номер 1

Реализуйте параллельный метод встречной прогонки, оцените его трудоемкость. Сравните теоретическое ускорение параллельного метода с практическим.

Ответ:

(1) метод встречной прогонки плохо параллелится, ускорение отсутсвует

(2) метод встречной прогонки хорошо параллелится для любых задач

(3) метод встречной прогонки хорошо параллелится, но только в случае задач небольшого размера

Номер 2

Сформулируйте три варианта LU-разложения (по столбцу, по строке, компактная схема). Какой из алгоритмов предпочтителен при реализации?

Ответ:

(1) по столбцу, так как так как при вычислении j-го столбца используются все элементы строк от j-й до n-й, а доступ к строке матрицы в языке С организован эффективно

(2) по строке, так как при вычислении i-й строки используются все элементы столбцов от 1-го до i-го, а доступ к столбцу матрицы в языке С организован эффективно

(3) компактная схема, так как она обладает меньше трудоемкостью

Упражнение 2:

Номер 1

	Реализуйте метод Гаусса без выбора ведущего элемента. Экспериментально оцените погрешность. Сравните полученную погрешность с погрешностью, которая получается при выборе ведущего элемента по столбцу.

Ответ:

(1) погрешности одинаковые и сопоставимы с ошибкой округления

(2) погрешность метода Гаусса с выбором ведущего элемента меньше, чем обычного метода

(3) погрешность обычного метода Гаусса меньше, чем метода с выбором ведущего элемента

Номер 2

Реализуйте метод Гаусса без выбора ведущего элемента. Экспериментально оцените погрешность. Сравните полученную погрешность с погрешностью, которая получается при выборе ведущего элемента по столбцу и по строке.

Ответ:

(1) погрешности одинаковые и сопоставимы с ошибкой округления

(2) погрешность обычного метода Гаусса меньше, чем метода с выбором ведущего элемента

(3) погрешность метода Гаусса с выбором ведущего элемента меньше, чем обычного метода

Упражнение 3:

Номер 1

Сформулируйте блочный алгоритм LU-разложения. Будет ли он эффективнее обычного алгоритма.

Ответ:

(1) нет, в силу одинаковой трудоемкости методы одинаково эффективны

(2) нет, обычный алгоритм эффективнее в силу меньшей трудоемкости

(3) да, блочный алгоритм эффективнее в силу меньшей трудоемкости

(4) да, блочный алгоритм эффективнее при одинаковой трудоемкости в силу правильного использования кэш-памяти

Номер 2

Сформулируйте три варианта разложения Холецкого (строчный, столбцовый, с изменением подматрицы). Какой из алгоритмов предпочтителен при реализации?

Ответ:

(1) строчный, так как при вычислении i-й строки используются все элементы столбцов от 1-го до i-го, а доступ к столбцу матрицы в языке С организован эффективно

(2) столбцовый, так как при вычислении j-го столбца используются все элементы строк от j-й до n-й, а доступ к строке матрицы в языке С организован эффективно

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

Упражнение 4:

Номер 1

Сформулируйте блочный алгоритм разложения Холецкого. Будет ли он эффективнее обычного алгоритма?

Ответ:

(1) нет, в силу одинаковой трудоемкости методы одинаково эффективны

(2) нет, обычный алгоритм эффективнее в силу меньшей трудоемкости

(3) да, блочный алгоритм эффективнее при одинаковой трудоемкости в силу правильного использования кэш-памяти

(4) да, блочный алгоритм эффективнее в силу меньшей трудоемкости

Номер 2

Сформулируйте метод верхней релаксации. Как вы оцениваете свойства метода с точки зрения его возможного распараллеливания?

Ответ:

(1) метод обладает отличными свойствами для распараллеливания, зависимости данных нет

(2) метод обладает хорошими свойствами для распараллеливания, есть зависимость по данным только между итерациями

(3) метод плохо параллелится в силу зависимости данных не только между итерациями, но и в рамках одной итерации

Номер 3

Можно ли применять метод сопряженных градиентов в качестве прямого метода решения системы линейных уравнений? Обоснуйте свой ответ.

Ответ:

(1) да, можно применять для любых систем

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

(3) нет, применять нельзя ни для каких систем

Intel Parallel Programming Professional (Introduction) - тест 7