Главная / Программирование / Основы распараллеливания программ

Основы распараллеливания программ - ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: В настоящее время развитие вычислительных систем испытывает третий кризис программного обеспечения. Первый кризис разразился в 60-70е годы прошлого века, когда программирование в машинных кодах и на языке ассемблера вошло в противоречие с возросшей производительностью компьютеров. Выходом стало появление языков высокого уровня. Второй кризис пришелся на 80-90е годы. Создание и поддержка сложных и надежных программных комплексов, содержащих несколько миллионов строк кода, написанных сотнями программистов, потребовали развития объектно-ориентированных языков и разработки инструментария для поддержки больших программных проектов. Третий кризис связан с невозможностью дальнейшего экстенсивного развития hardware и переходом к многоядерным архитектурам. Адекватного ответа на возникший кризис до сих пор не найдено. Одним из способов его преодоления является разработка параллельных программ.

Смотрите также:

Суперкомпьютерные технологии

Что такое суперкомпьютер по определению Кена Батчера?

(1) это устройство сводящее проблему вычислений к проблеме ввода/вывода

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

(3) это система, цена которой выше 1-2 млн долларов

Какие утверждения верны для графа алгоритма ?

(1) граф является ориентированным

(2) граф не может быть параметризованным

(3) граф может быть детерминированным или недетерминированным

(4) граф является ациклическим

Какой вектор направлений соответствует зависимости не связанной с циклами ?

(1) ( ≤ , ≤ )

(2) ( = , = )

(3) ( ≥ , ≥ )

(4) ( ≤ , ≥ )

Какая вычислительная сложность задачи, которая загрузит компьютер с производительностью 1 GFOP на 1 год работы?

(1) 10¹⁶ FLOP

(2) 10¹⁷ FLOP

(3) 10¹⁵ FLOP

(4) 10¹⁰ FLOP

Какие утверждения верны для графа алгоритма ?

(1) в графе могут быть циклы

(2) в графе могут быть кратные ребра

(3) в графе могут быть петли

(4) граф может быть мультиграфом

Какой вектор растояний соответствует следующей программе ? do i = 1,100 do j = 1,100 a(i,j) = a(i-1,j) enddo enddo

(1) (1,0)

(2) (-1,0)

(3) (0,-1)

(4) (0,1)

Что решило кризис software 60-70гг?

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

(2) появление более мощных ЭВМ

(3) появление языков программирования низкого уровня

(4) появление языков программирования высокого уровня

Как называются наборы вершин с одинаковыми номерами в строгой параллельной форме графа алгоритма ?

(1) этажами

(2) наборами параллельности

(3) уровнями

(4) ярусами

Какой вектор направлений соответствует следующей программе ? do i = 1,100 do j = 1,100 a(i,j) = a(i+5,j-1) enddo enddo

(1) ( ≥ , ≤ )

(2) ( ≤ , ≥ )

(3) ( ≤ , ≤ )

(4) ( ≥ , ≥ )

(5) ( ≤ , = )

(6) ( ≥ , = )

(7) ( = , ≤ )

(8) ( = , ≥ )

Какие факторы стали лимитирующими для дальнейшего выполнения закона Мура?

(1) появление многопроцессорных компьютеров

(2) ограниченность скорости передачи сигнала

(3) проблема теплоотвода

(4) исчезновение спроса на мощные одноядерные системы

Как называют вопрос выбора уровня декомпозиции до которого спускаться?

(1) вопрос параллельности

(2) вопрос гранулярности

(3) вопрос производительности

Какое сокращение соответствует стандартной одноядерной архитектуре?

(1) SISD

(2) SIMD

(3) MISD

(4) MIMD

Как называется перемешивание порядка исполнения атомарных операций для активностей исполняемых в псевдопаралельном режиме ?

(1) интерливинг

(2) перекрытие

(3) интроливинг

(4) макроливинг

Укажите вектора направлений допускают распараллеливание по внутреннему циклу

(1) ( ≥ , = )

(2) ( ≥ , ≤ )

(3) ( = , ≥ )

(4) ( = , ≤ )

(5) ( ≤ , ≥ )

Какие этапы присутствуют в создание однопоточной программы?

(1) постановка задачи

(2) построение математической модели

(3) выбор алгоритма

(4) декомпозиция модели/алгоритма

(5) этап назначения задач исполнителям (assignment)

(6) дирижирование (orchestration)

(7) создание программы

(8) отображение программы на архитектуру (mapping)

Какое утверждение верно?

(1) выполнение условий Бернстайна - это необходимое условия детерминированности набора активностей

(2) выполнение условий Бернстайна - это достаточное условия детерминированности набора активностей

(3) выполнение условий Бернстайна - это необходимое и достаточной условия детерминированности набора активностей

Какие вектора направлений соответствуют антизависимости ?

(1) ( ≥ , ≤ )

(2) ( ≤ , ≥ )

(3) ( ≤ , ≤ )

(4) ( ≥ , ≥ )

(5) ( ≤ , = )

(6) ( ≥ , = )

(7) ( = , ≤ )

(8) ( = , ≥ )

Выберите верное определение math

(1)

(2)

(3)

Нарушению какого условия Бернстайна соответствует наличие истенной зависимости?

(1) нарушению первого условия Бернстайна

(2) нарушению второго условия Бернстайна

(3) нарушению третьего условия Бернстайна

Чему равно растояние зависимости в следующей программе ? do i = 2,n a(j) = b(j)+2 c(j) = a(j-1)*3 enddo

(1) 0

(2) -1

(3) 1

Пусть

это теоретическая нижняя оценка сложности задачи, в каком случае алгоритм для этой задачи со временем работы math

оптимален?

(1)

(2)

(3)

Какие зависимости соответствуют нарушению условий Бернстайна ?

(1) истинная зависимость

(2) зависимость по управлению

(3) зависимость по ресурсу

(4) зависимость по выходным данным

(5) антизависимость

Как называется прием, разделяющий цикл, который нельзя распараллелить, на 2 цикла, которые можно распаралеливать?

(1) репликация кода

(2) loop elignment

(3) loop distribution

В рамках какой модели оценивают алгоритмическую сложность последовательных алгоритмов?

(1) RISC

(2) RAM

(3) SISD

Какие случаи допускают эффективное распараллеливание ?

(1) растояние зависимости d=-1

(2) растояние зависимости d неопределено

(3) растояние зависимости d=0

Для чего организуется приватизация переменной ?

(1) для ускорения работы

(2) для устранения зависимости по скалярной переменной между итерациями цикла

(3) для устранения зависимости по элементам массива между итерациями цикла

Машины с какой архитектурой не используются на практике?

(1) CRCW

(2) ERCW

(3) CREW

(4) EREW

Что такое диофантовы уравнения ?

(1) уравнения с целыми коэффициентами

(2) уравнения с целыми коэффициентами у которых разыскиваются целые решения

(3) уравнения у которых разыскиваются целые решения

Как называется переменная, которая ,с ипользованием своего значения на прошлой итерации, перечитывается на каждой итерации цикла ?

(1) приватезированная

(2) индукционная

(3) редукционная

Чем отличаются многоядерная и многопроцессорная архитектуры?

(1) в многопроцессорной архитектуре общий кеш

(2) в многоядерной архитектуре общий кеш

(3) в многоядерной архитектуре общая оперативная память

(4) в многопроцессорной архитектуре общая оперативная память

Какие значения могут принимать координаты вектора направлений?

(1) целочисленные

(2) < , > , =

(3) 0,1,-1

Какая из переменных является редукционной ? do i = 1,n A = i+7 B = B*i c(i) = A + B +c(i) D = D + c(i) enddo

(1) A

(2) B

(3) c

(4) D

Что является вершинами в графе алгоритма?

(1) процессоры

(2) операции

(3) зависимости по данным

В каких векторах расстояний есть истинная зависимость хотя бы по одной координате ?

(1) (1,1)

(2) (1,-1)

(3) (-1,0)

Какими свойствами должны обладать редукционные операции ?

(1) дистрибутивность

(2) ассоциативность

(3) комутативность

Что такое суперкомпьютер по определению 1986 года?

(1) очень мощная ЭВМ производительностью 1 MFLOP (мегафлопс)

(2) очень мощная ЭВМ производительностью 10 MFLOP

(3) очень мощная ЭВМ производительностью 50 MFLOP

(4) очень мощная ЭВМ производительностью 300 MFLOP

Какие утверждения верны для графа алгоритма ?

(1) граф является неориентированным

(2) граф может быть параметризованным

(3) граф может быть детерминированным или недетерминированным

(4) граф является ациклическим

Какой вектор направлений соответствует антизависимости во внешнем цикле ?

(1) ( ≤ , = )

(2) ( = , = )

(3) ( ≥ , = )

(4) ( = , ≥ )

Какая вычислительная сложность задачи, которая загрузит компьютер с производительностью 1 GFOP на 10 дней работы?

(1) 10^12 FLOP

(2) 10^15 FLOP

(3) 10^17 FLOP

(4) 10^20 FLOP

Что понимают под параметризованностью графа алгоритма ?

(1) наличие весов у вершин графа

(2) зависимость графа от входных данных

(3) зависимость графа от размерности задачи

(4) наличие весов у ребер графа

Какой вектор растояний соответствует следующей программе ? do i = 1,100 do j = 1,100 a(i,j) = a(i,j-1) enddo enddo

(1) (1,0)

(2) (-1,0)

(3) (0,-1)

(4) (0,1)

Что решило кризис software 80-90гг?

(1) развитие языка ассемблер

(2) появление языков программирования высокого уровня

(3) развитие объектно-ориентированных языков

Какие утверждения верны ?

(1) глубина канонической параллельной формы минимальна

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

(3) каноническая параллельная форма единственна

Какой вектор направлений соответствует следующей программе ? do i = 1,100 do j = 1,100 a(i,j) = a(i+1,j+1) enddo enddo

(1) ( ≥ , ≤ )

(2) ( ≤ , ≥ )

(3) ( ≤ , ≤ )

(4) ( ≥ , ≥ )

(5) ( ≤ , = )

(6) ( ≥ , = )

(7) ( = , ≤ )

(8) ( = , ≥ )

Как формулируется новый закон Мура?

(1) производительность процессоров увеличивается в 2 раза каждые 1,5 года

(2) количество ядер на одном процессоре увеличивается в 2 раза каждые 1,5 года

(3) количество ядер на одном процессоре увеличивается в 1,5 раза каждые 2 года

(4) производительность процессоров увеличивается в 2 раза каждые 2 года

Что такое активность ?

(1) последовательность атомарых действий

(2) некоторая последовательность действий, направленная на реализацию определенной цели

(3) набор процессов

К какой архитектуре относится матричный суперкомпьютер ILLIAC IV?

(1) SISD

(2) SIMD

(3) MISD

(4) MIMD

Какой набор активностей называется детерминированным?

(1) тот, в котором нет входных данных

(2) тот, в котором результат работы всех активностей не зависит от интерливинга

(3) тот, в которм нет условных операторов

Укажите вектора расстояний, которые допускают распараллеливание по внутреннему циклу

(1) (1 , 0 )

(2) (1 , 1 )

(3) (0 , 1 )

(4) (0 , -1 )

Какие этапы появляются при переходе от создания однопоточной программы к созданию параллельной программы?

(1) постановка задачи

(2) построение математической модели

(3) выбор алгоритма

(4) декомпозиция модели/алгоритма

(5) этап назначения задач исполнителям (assignment)

(6) дирижирование (orchestration)

(7) создание программы

(8) отображение программы на архитектуру (mapping)

Какие утверждения являются условиями Бернстайна для активностей P и Q ?

(1)

(2)

(3)

(4)

(5)

(6)

(7)

Какие вектора направлений соответствуют истинной зависимости ?

(1) ( ≥ , ≤ )

(2) ( ≤ , ≥ )

(3) ( ≤ , ≤ )

(4) ( ≥ , ≥ )

(5) ( ≤ , = )

(6) ( ≥ , = )

(7) ( = , ≤ )

(8) ( = , ≥ )

Выберите верное определение math

(1)

(2)

(3)

Нарушению какого условия Бернстайна соответствует наличие антизависисмости?

(1) нарушению первого условия Бернстайна

(2) нарушению второго условия Бернстайна

(3) нарушению третьего условия Бернстайна

Какая зависимость присутствует в следующей программе ? do i = 2,n a(j) = b(j)+2 c(j) = a(j-1)*3 enddo

(1) зависимости нет

(2) истинная зависимость

(3) антизависимость

Выберите верные утверждения

(1)

(2)

(3)

Какие зависимости могут присутствовать при выполнении условий Бернстайна ?

(1) истинная зависимость

(2) зависимость по управлению

(3) зависимость по ресурсу

(4) зависимость по выходным данным

(5) антизависимость

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

(1) репликация кода

(2) loop alignment

(3) loop distribution

Сколько ядер в RAM модели?

(1) 3

(2) 2

(3) 1

Наличие каких зависимостей в цикле допускает эффективное распараллеливание?

(1) антизависимость

(2) истинная зависимость

(3) истенная зависимость с большим по модулю расстоянием зависимости

На какой архитектуре труднее организовать приватизацию переменной ?

(1) на архитектуре с разделяемой памятью

(2) на архитектуре с распределенной памятью

Какие модели параллельной архитектуры не позволяют одновременного чтения одной ячейки из памяти?

(1) CRCW

(2) ERCW

(3) CREW

(4) EREW

Разрешима ли система диофантовых уравнений общего вида ?

(1) да

(2) нет

(3) да, с помощью компьютера

Какая из переменных является индукционной ? do i = 1,n A = A+2*i B = i*i c(i) = A + B D = D + c(i) enddo

(1) A

(2) B

(3) c

(4) D

Может ли программа на 4-х ядерном процессоре работать медленнее чем на одноядерном?

(1) нет

(2) да

Чему равен вектор направлений для вектора расстояний G=(0,-1) ?

(1) (=, ≤ )

(2) (=, = )

(3) (=, ≥ )

Какая из переменных является редукционной ? do i = 1,n A = i*i*i B = B-i c(i) = A - B - c(i) D = D + c(i) enddo

(1) A

(2) B

(3) c

(4) D

Что является ребрами в графе алгоритма?

(1) входные данные

(2) операции

(3) зависимости по данным

В каких векторах расстояний есть антизависимость хотя бы по одной координате ?

(1) (1,1)

(2) (1,-1)

(3) (-1,0)

Какие операции могут быть рудукционными ?

(1) +

(2) min

(3) div

Что называют стоимостью (cost) работы параллельной программы?

(1) время работы

(2) время работы умножить на число процессоров

(3) время работы делить на число процессоров

(4) сумма времен работы каждого процессора

Какие утверждения верны для графа алгоритма ?

(1) граф является ориентированным

(2) граф всегда параметризован

(3) граф может быть детерминированным или недетерминированным

(4) граф может содержать циклы

Какой вектор направлений соответствует истинной зависимости во внешнем цикле ?

(1) ( ≥ , = )

(2) ( = , = )

(3) ( ≤ , = )

(4) ( = , ≤ )

Какова вычислительная сложность определения массы протона в квантовой хромодинамике?

(1) 10^12 FLOP

(2) 10^15 FLOP

(3) 10^17 FLOP

(4) 10^20 FLOP

Какое утверждение верно?

(1) строгая параллельная форма единственна

(2) в строгой параллельной форме номера всех вершин графа различны

(3) все вершины с номером 1 это вершины ввода

(4) все вершины ввода имеют номер 1

Какой вектор растояний соответствует следующей программе ? do i = 1,100 do j = 1,100 a(i,j) = a(i-1,j+1) enddo enddo

(1) (1,1)

(2) (-1,1)

(3) (1,-1)

(4) (-1,-1)

С чем связан кризис software 2005-20?? годов?

(1) со сменой парадигмы развития hardware

(2) с появлением параллельных программ

(3) с появлением многоядерных процессоров

Какие утверждения верны ?

(1) глубина канонической параллельной формы минимальна

(2) ширина канонической параллельной формы минимальна

(3) глубина канонической параллельной формы максимальна

(4) ширина канонической параллельной формы максимальна

Какой вектор направлений соответствует следующей программе ? do i = 1,100 do j = 1,100 a(i,j) = a(i-1,j+0) enddo enddo

(1) ( ≥ , ≤ )

(2) ( ≤ , ≥ )

(3) ( ≤ , ≤ )

(4) ( ≥ , ≥ )

(5) ( ≥ , = )

(6) ( ≤ , = )

(7) ( = , ≤ )

(8) (= , ≥ )

Как формулируется закон Мура?

(1) производительность процессоров увеличивается в 2 раза каждые 1,5 года

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

(3) производительность процессоров увеличивается в 3 раза каждые 2 года

(4) производительность процессоров увеличивается в 2 раза каждые 2 года

Что такое атомарная операция ?

(1) операция, которую нельзя прерывать

(2) операция над атомами

(3) операция ввода-вывода

(4) базовая арифметическая операция

Какая архитектура получила наибольшее распространение среди суперкомпьютеров?

(1) SISD

(2) SIMD

(3) MISD

(4) MIMD

Какой набор активностей называется недетерминированным?

(1) тот, результат работы которого зависит от входных данных

(2) тот, в котором результат работы активностей зависит от интерливинга

(3) тот, в котором есть условные операторы

Укажите какие вектора направлений допускают распараллеливание по внешнему циклу

(1) ( ≥ , = )

(2) ( ≥ , ≥ )

(3) ( = , ≥ )

(4) ( = , ≤ )

Какие этапы общие для создания однопоточной и параллельной программ?

(1) постановка задачи

(2) построение математической модели

(3) выбор алгоритма

(4) декомпозиция модели/алгоритма

(5) этап назначения задач исполнителям (assignment)

(6) дирижирование (orchestration)

(7) создание программы

(8) отображение программы на архитектуру (mapping)

Нарушению какого условия Бернстайна соответствует наличие зависимости по выходным данным?

(1) нарушению первого условия Бернстайна

(2) нарушению второго условия Бернстайна

(3) нарушению третьего условия Бернстайна

Какие вектора расстояний соответствуют истинной зависимости ?

(1) (-2, 1)

(2) (2, -2)

(3) (1, 1)

(4) (-3, -1)

(5) (1, 0)

(6) (-1, 0)

(7) (0, 2)

(8) (0, -5)

Выберите верное определение math

(1)

(2)

(3)

Какая из зависимостей сложнее всего распаралеливается ?

(1) зависисмость по выходным данным

(2) истинная зависимость

(3) антизависимость

Чему равно растояние зависимости в следующей программе ? do i = 1,n a(j) = b(j)+2 c(j) = a(j+1)*3 enddo

(1) 1

(2) -1

(3) 0

В рамках какой модели оценивают алгоритмическую сложность параллельных алгоритмов?

(1) MIMD

(2) RAM

(3) PRAM

С какой зависимостью в цикле можно справиться, раскопировав данные на каждый процессор?

(1) истинная зависимость

(2) зависимость по выходным данным

(3) антизависимость

На какой архитектуре легче организовать приватизацию переменной ?

(1) на архитектуре с разделяемой памятью

(2) на архитектуре с распределенной памятью

Какие модели параллельной архитектуры позволяют одновременную запись в одну ячейку памяти?

(1) CRCW

(2) ERCW

(3) CREW

(4) EREW

Как называются уравнения с целыми коэффициентами у которых разыскиваются целые решения?

(1) диофантовы

(2) пифогоровы

(3) эвклидовы

Какая из переменных является индукционной ? do i = 1,n A = i+7 B = B*i c(i) = A + B +c(i) D = D + c(i) enddo

(1) A

(2) B

(3) c

(4) D

Каково максимальное ускорение для системы с N процессорами?

(1) N^2

(2) N/2

(3) N

Чему равен вектор направлений для вектора расстояний G=(0,1) ?

(1) (=, ≤ )

(2) (=, = )

(3) (=, ≥ )

Какая из переменных является редукционной ? do i = 1,n A = A+c(i) B = B*i c(i) = A + B +c(i) D = D + 2 enddo

(1) A

(2) B

(3) c

(4) D

Сколько существует различных графов алгоритма для сложения 4-х чисел?

(1) 2

(2) 4

(3) 15

Какие вектора расстояний соответствуют следующему вектору направлений (≥,≤) ?

(1) (1,-1)

(2) (-1,1)

(3) (-3,4)

(4) (2,10)

(5) (3,0)

Какие операции могут быть рудукционными ?

(1) -

(2) max

(3) mod

Какая зависимость присутствует для следующих операций S1: x = a/b и S2: y = c/b?

(1) истинная зависимость

(2) зависимость по управлению

(3) зависимость по выходным данным

(4) антизависимость

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

(1) репликация кода

(2) loop elignment

(3) loop distribution