Главная / Программирование / Введение в методы параллельного программирования

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

Правильные ответы выделены зелёным цветом.
Все ответы: Учебное пособие содержит материал, для работы в области параллельного программирования.

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

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

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

(1) ленточная схема разделения данных

(2) блочная схема разделения данных

(3) данные дублируются между процессорами

Какая схема разделения данных используется при реализации параллельного алгоритма Гаусса?

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

(2) ленточная циклическая схема разделения данных

(3) блочная схема разделения данных

(4) данные дублируются между процессорами

Задача сортировки данных обычно формулируется как:

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

(2) задача разделения элементов набора значений на несколько частей

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

Граф это:

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

(2) множество линий (дуг), соединенных друг с другом

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

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

(1) ленточное разделение данных

(2) диагональное разделение матрицы

(3) блочное разделение данных

Вычислительный эксперимент в системе ПараЛаб – это:

(1) выполнение параллельной программы при использовании только одного процессора

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

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

В чем состоят необходимые условия для возможности организации параллельных вычислений:

(1) избыточность вычислительных устройств и независимость их функционирования

(2) организация режима разделения времени

(3) наличие сети передачи данных между процессорами

Модель вычислений – это:

(1) ациклический ориентированный граф

(2) бинарное дерево

(3) циклический ориентированный граф

Алгоритмы маршрутизации определяют:

(1) путь передачи данных от процессора-источника сообщения до процессора, к которому сообщение должно быть доставлено

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

(3) все возможные пути передачи данных между процессорами

Для организации параллельных вычислений в вычислительных системах с распределенной памятью необходимо:

(1) обеспечить информационное взаимодействие между процессорами

(2) выделить информационно независимые фрагменты вычислений, провести их программную реализацию, разместить полученные части программы на разных процессорах и затем организовать информационное взаимодействие между процессорами

(3) распределить исполняемые модули параллельной программы по узлам системы

Распределение подзадач между процессорами должно быть выполнено таким образом, чтобы:

(1) информационные связи между подзадачами были бы минимальными

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

(3) загруженность процессоров была бы минимальной

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

(1) поэлементное разделение матрицы

(2) ленточное разделение матрицы

(3) блочное разделение матрицы

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

(1) операция обобщенного сбора данных

(2) операция циклического сдвига

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

При выполнении параллельного алгоритма Гаусса основными коммуникационными операциями являются:

(1) операция обобщенного сбора данных

(2) операции широковещательной рассылки и редукции данных

(3) операция циклического сдвига

Базовая операция "сравнить и переставить" состоит из:

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

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

(3) обмена имеющимися на процессорах P_i и P_j значениями, сравнения этих значений на каждом из процессоров и разделения данных между процессорами

Задача поиска всех кратчайших путей обычно формулируется как:

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

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

(3) для данного графа найти максимальную среди минимальных длин путей между всеми парами вершин

При выполнении параллельного алгоритма, основанного на разделении данных на горизонтальные полосы, сбор данных полученных результатов выполняется при помощи:

(1) операции передачи сообщений типа "точка-точка"

(2) операции обобщенного сбора данных

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

В каком из режимов можно провести вычислительный эксперимент?

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

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

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

Какую компьютерную систему можно отнести к суперкомпьютерам:

(1) систему с максимально-достижимыми на данный момент времени показателями производительности

(2) компьютер, производительность которого превышает величины в 1 Tflops

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

Ускорение параллельных вычислений – это:

(1) отношение времени последовательного алгоритма ко времени параллельного решения задачи

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

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

Длительность времени передачи одного слова данных по одному каналу передачи данных определяется:

(1) полосой пропускания коммуникационных каналов в сети

(2) временем, необходимым для передачи служебных данных

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

Под параллельной программой в рамках MPI понимается:

(1) множество одновременно выполняемых процессов

(2) множество одновременно выполняемых потоков

(3) множество одновременно работающих процессоров

Граф "подзадачи – сообщения" представляет собой:

(1) агрегированное представление графа информационных зависимостей

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

(3) агрегированное представление графа " процессы – каналы"

При выполнении параллельного алгоритма, основанного на разделении матрицы на горизонтальные полосы, сбор данных результирующего вектора выполняется при помощи:

(1) операции передачи сообщений типа «точка-точка»

(2) операции обобщенного сбора данных

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

Для эффективного выполнения алгоритма Фокса необходимо, чтобы процессоры вычислительной системы были организованы в топологию:

(1) решетка или полный граф

(2) гиперкуб

(3) звезда

За основу организации параллельных вычислений при реализации метода сопряженных градиентов выбирается:

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

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

(3) распараллеливание операции скалярного произведения векторов

Трудоемкость алгоритма пузырьковой сортировки оценивается выражением:

(1)

(2)

(3)

Число итераций параллельного алгоритма Флойда равно:

(1) n

(2)

(3) n₂

Для параллельных алгоритмов для систем с общей памятью при проведении вычислительных экспериментов может наблюдаться сверхлинейное ускорение. Каковы возможные причины достижения этого эффекта?

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

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

(3) снижение времени передачи данных между потоками

При построении графических зависимостей для экспериментов, проведенных в режиме имитации, используются:

(1) накопленные результаты выполненных экспериментов

(2) теоретические оценки, применяемые в системе ПараЛаб

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

Под кластером обычно понимается:

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

(2) множество отдельных компьютеров, объединенных в локальную вычислительную сеть

(3) множество отдельных компьютеров, подключенных к сети Интернет

Каскадная схема используется для:

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

(2) вычисления суммы последовательности числовых значений

(3) вычисления всех частных сумм последовательности числовых значений

При использовании метода передачи сообщений:

(1) процессор-отправитель готовит весь объем данных для передачи, определяет процессор-получатель и запускает операцию пересылки данных, а процессор-получатель осуществляет прием полностью всех пересылаемых данных и только затем приступает к пересылке принятого сообщения далее по маршруту

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

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

Среди предусмотренных в составе MPI операций передачи сообщений различают:

(1) парные и коллективные операции

(2) парные и групповые операции

(3) индивидуальные и коллективные операции

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

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

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

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

Для эффективного выполнения параллельного алгоритма умножения матрицы на вектор, основанного на блочном разделении матрицы, необходимо, чтобы процессоры вычислительной системы были объединены в топологию:

(1) решетка или полный граф

(2) гиперкуб

(3) звезда

Из представленных в лекции алгоритмов, лучшей масштабируемостью обладает:

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

(2) алгоритм, основанный на однотипном ленточном разделении матриц

(3) алгоритм Фокса и алгоритм Кэннона

Из представленных в лекции алгоритмов, лучшей масштабируемостью обладает:

(1) алгоритм Гаусса

(2) метод сопряженных градиентов

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

Параллельный вариант алгоритма Шелла состоит в следующем:

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

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

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

Охватывающим деревом (или остовом) неориентированного графа называется:

(1) подграф, который является деревом и содержит все вершины исходного графа

(2) бинарное дерево, содержащее все вершины исходного графа

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

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

(1) увеличение объема передаваемых данных

(2) увеличение граничных строк

(3) увеличение объема служебных передаваемых данных

Какие из перечисленных ниже классы задач поддерживает система имитационного моделирования ПараЛаб:

(1) обработка графов

(2) решение системы линейных уравнений

(3) интегрирование уравнений математической физики

В основе классификации вычислительных систем в систематике Флинна используются:

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

(2) понятия потоков команд и данных

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

Пусть есть задача вычисление суммы следующего вида math

. Пусть N = 8 и применяется каскадная схема, аналогичная схеме описанной в лекции для суммирования элементов вектора. Какая в этом случае минимально возможная высота дерева модели вычисления:

(1) 3

(2) 4

(3) 5

Для рассылки от одного процессора всем остальным процессорам сети при использовании топологии типа гиперкуб достаточно (N=log₂p):

(1) N-этапной процедуры передачи данных

(2) N log₂N-этапной процедуры передачи данных

(3) N²-этапной процедуры передачи данных

Все данные для передачи в качестве сообщения MPI описываются с помощью триады:

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

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

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

Выбор способа разделения вычислений на независимые части основывается:

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

(2) на результатах вычислительных экспериментов

(3) на анализе графа "процессы – каналы"

На основании результатов экспериментов, представленных в лекции, можно сказать, что наибольшее ускорение демонстрирует:

(1) алгоритм, основанный на разделении матрицы на горизонтальные полосы

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

(3) алгоритм, основанный на блочном разделении матрицы

Рассмотрим задачу перемножения матриц. Пусть размер перемножаемой матрицы 100x100. На вычислительной системе все операции сложения и умножения выполняются одинаковое время math

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы имеют тип double и занимают w = 8 байт. Если при распараллеливании использовать разделение матрицы на ленты, чему будет равно теоретическое ускорение при использовании 4 процессоров:

(1) 3,9

(2) 2,5

(3) ,8

Рассмотрим задачу поиска решения системы линейных уравнений. Пусть размер матрицы системы линейных уравнений 100x100. На вычислительной системе все операции сложения и умножения выполняются одинаковое время math

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы системы линейных уравнений имеют тип double и занимают w = 8 байт. Если при распараллеливании алгоритма Гаусса использовалось 4 процессора, то какое в этом случае достигается теоретическое ускорение:

(1) 3,1

(2) 1,5

(3) 0,18

Алгоритм быстрой сортировки основан на:

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

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

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

Количество выполняемых операций при определении номера ближайшей вершины до охватывающего дерева и корректировке расстояний после расширения МОД ограничивается сверху величиной:

(1)

(2)

(3)

На каких топологиях сети в системе ПараЛаб реализована быстрая сортировка:

(1) гиперкуб

(2) кольцо

(3) линейка

Типовые топологии сети передачи данных определяются:

(1) только с учетом возможности технической реализации

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

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

Пусть есть задача вычисления произведения всех элемента вектора math

. Пусть N = 6 и применяется каскадная схема с минимально возможной высотой дерева модели вычисления. Чему в этом случае равно ускорение при использовании неограниченного числа вычислительных элементов:

(1) 2

(2) 2,5

(3) 3

Уплотнение дуг это:

(1) максимальное количество дуг логической топологии, отображаемых в одну линию передачи физической топологии

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

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

Прием сообщения при помощи функции MPI_Recv может быть инициирован:

(1) до момента, в момент или после момента начала отправки сообщения

(2) только в момент начала отправки сообщения

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

Для локальной схемы передачи данных характерно:

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

(2) выполнение взаимодействий только с соседними подзадачами

(3) отсутствие взаимодействия между подзадачами

Рассмотрим задачу перемножения матрицы на вектор. Пусть размер перемножаемой матрицы 100x100. На вычислительной системе все операции сложения и умножения выполняются одинаковое время math

нсек. Латентности сети math

нсек. Пропускная способность сети 60 Мбайт/сек. Элементы матрицы имеют тип double и занимают w = 8 байт. Если при распараллеливании использовать разделение матрицы на строки чему будет равно теоретическое ускорение при использовании 2 процессоров:

(1) 3

(2) 1.5

(3) 1.98

Рассмотрим задачу перемножения матриц. Пусть размер перемножаемой матрицы 200x200. На вычислительной системе все операции сложения и умножения выполняются одинаковое время math

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы имеют тип double и занимают w = 8 байт. Если при распараллеливании использовать алгоритм Кеннона, чему будет равна теоретическая эффективность при использовании 4 процессоров:

(1) 0,1

(2) 0,6

(3) 0,9

Рассмотрим задачу поиска решения системы линейных уравнений. Пусть размер матрицы системы линейных уравнений 200x200. На вычислительной системе все операции сложения и умножения выполняются одинаковое время math

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы системы линейных уравнений имеют тип double и занимают w = 8 байт. Если при распараллеливании алгоритма сопряженных градиентов использовалось 4 процессора, то какая в этом случае достигается теоретическая эффективность:

(1) 0,9

(2) 0,5

(3) 0,1

Задача оптимального разделения графа состоит в разбиении вершин графа на непересекающиеся подмножества:

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

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

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

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

(1) барьерная синхронизация

(2) асинхронный способ передачи данных

(3) синхронный способ передачи данных

В рамках системы ПараЛаб какие допускаются схемы выполнения вычислений при проведении экспериментов:

(1) пошаговый

(2) блочное выполнение итераций алгоритмов

(3) выполнение серии экспериментов

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

(1) топология гиперкуб

(2) топология линейка

(3) топология полный граф

Пусть в решаемой задаче последовательная часть составляет четыре единицы времени, а часть, допускающая линейное распараллеливание, шесть единицы времени. Если использовать закон Амдаля, сколько потребуется процессоров для достижения ускорения в два раза:

(1) 5

(2) 8

(3) 6

Двоичный код Грея используется для определения соответствия между:

(1) кольцевой топологией и гиперкубом

(2) тором и гиперкубом

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

В синхронном режиме передачи завершение функции отправки сообщения происходит:

(1) при получении от процесса-получателя подтверждения о начале приема отправленного сообщения, при этом отправленное сообщение или полностью принято процессом-получателем или находится в состоянии приема

(2) при старте передачи данных процессом-отправителем по сети

(3) при завершении копирования сообщения в системный буфер

Управление распределением нагрузки для процессоров необходимо:

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

(2) для вычислительных систем с общей памятью

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

нсек. Латентности сети math

нсек. Пропускная способность сети 60 Мбайт/сек. Элементы матрицы имеют тип double и занимают w = 8 байт. Если при распараллеливании использовать разделение матрицы блоки (количество блоков по строкам и по строкам равно и равно math

, где p – количество процессоров), чему будет равно теоретическая стоимость при использовании 4 процессоров:

(1) 200000000

(2) 02646984

(3) 419991256

При применении параллельных алгоритмов быстрой сортировки одним из основных моментов является:

(1) правильность выбора ведущего элемента

(2) исходная упорядоченность данных на процессорах

(3) близость процессоров физической структуры сети в топологии гиперкуба

Метод бинарного деления для решения задачи оптимального разделения графов заключается:

(1) в рекурсивном разбиении исходного графа на две равные части

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

(3) в рекурсивном разбиении на k² равных частей исходного графа, где k – число вершин графа

Для кластерных систем характерна:

(1) топология полный граф и пакетный способ передачи сообщений

(2) топология гиперкуб и пакетный способ передачи сообщений

(3) топология полный граф и способ передачи сообщений, основанный на сообщениях

Применение неблокирующего способа выполнения обменов позволяет:

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

(2) уменьшить нагрузку на коммуникационную сеть

(3) уменьшить нагрузку на процессоры системы

Для того чтобы выбрать ведущий элемент в параллельном алгоритме быстрой сортировки выполняются следующие действия:

(1) вычисляется среднее арифметическое элементов, расположенных на выбранном ведущем процессоре, полученное значение рассылается по всем процессорам системы

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

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

Метод покоординатного разбиения для решения задачи оптимального разделения графов отличается от метода бинарного деления тем, что:

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

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

(3) деление сети пополам происходит по наиболее короткой стороне

В коллективных операциях передачи данных обязаны принимать участие:

(1) все процессы используемого коммуникатора

(2) некоторые процессы используемого коммуникатора

(3) все процессы используемой группы процессов

В обобщенном алгоритме быстрой сортировки в дополнение к обычному методу быстрой сортировки предлагается:

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

(2) конкретный способ выбора ведущих процессоров

(3) оптимальным способом рассылки ведущего элемента остальным процессорам

Основное отличие комбинаторных алгоритмов от геометрических методов, применяемых для решения задачи оптимального разделения графов, заключается:

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

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

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

Операцию редукции данных MPI_Reduce можно описать:

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

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

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

Производным типом данных в MPI называется:

(1) описание набора значений предусмотренного в MPI типа, причем в общем случае описываемые значения не обязательно непрерывно располагаются в памяти

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

(3) описание набора значений базового алгоритмического языка в терминах самого этого языка

При векторном способе новый производный тип создается как:

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

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

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

MPI поддерживает топологии вида:

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

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

(3) только граф произвольного вида

Какая схема разделения данных используется при разработке параллельных алгоритмов Фокса и Кэннона?

(1) ленточная схема разделения данных

(2) блочная схема разделения данных

(3) данные дублируются между процессорами

При реализации параллельного алгоритма Гаусса рекомендуется использовать ленточную циклическую схему разделения данных, потому что

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

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

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

Внутренняя сортировка это:

(1) сортировка, при которой все упорядочиваемые данные могут быть размещены полностью в оперативной памяти ЭВМ

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

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

Взвешенный граф это:

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

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

(3) граф, разделенный на две части с равными весами

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

(1) проблема синхронизации параллельных решений

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

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

Для постановки задачи в системе ПараЛаб необходимо выбрать:

(1) тип задачи

(2) метод решения задачи

(3) объем исходных данных

Режим разделения времени:

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

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

(3) не может быть использован при организации параллельных вычислений

В модели вычислений вершинами графа являются:

(1) операции

(2) операнды

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

В методах покоординатной маршрутизации поиск путей передачи данных осуществляется:

(1) поочередно для каждой размерности топологии

(2) поочередно для каждой пары участвующих в обмене процессоров

(3) одновременно для всех размерностей топологии

Для распределения вычислений между процессорами в вычислительных системах с распределенной памятью необходимо:

(1) выделить информационно независимые фрагменты вычислений, провести их программную реализацию и затем разместить полученные части программы на разных процессорах

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

(3) распределить исполняемые модули параллельной программы по узлам системы

Масштабирование разрабатываемого параллельного алгоритма это процесс:

(1) укрупнения и детализации подзадач

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

(3) увеличение и уменьшение числа процессоров, на которое рассчитан алгоритм

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

(1) только ленточная схема разделения данных

(2) только блочная схема разделения данных

(3) ленточная и блочная схемы разделения данных

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

(1) операция широковещательной рассылки и циклический сдвиг

(2) обобщенная передача данных от одного процессора всем процессорам и обобщенный сбор

(3) передача данных от одного процессора другому процессору вычислительной системы

На каждой итерации прямого хода алгоритма Гаусса для нахождения ведущей строки используется

(1) операция широковещательной рассылки

(2) передача данных от одного процессора другому процессору вычислительной системы

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

Базовая операция "сравнить и переставить" обычно используется в:

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

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

(3) в равной мере как в последовательных, так и параллельных алгоритмах сортировки

Сложность последовательного алгоритма Флойда имеет порядок:

(1) n³

(2) n²

(3) n²log₂ n

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

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

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

(3) использование схемы с чередованием четных и нечетных строк сетки

Эксперименты в режиме имитации возможно проводить:

(1) в активном окне с приостановкой вычислений после каждой итерации применяемого алгоритма

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

(3) одновременно во всех окнах вычислительных экспериментов

К числу суперкомпьютеров относятся:

(1) NCSA NT, Beowulf,

(2) SCI White, BlueGene

(3) AC3 Velocity, Thunder

Эффективность параллельных вычислений – это:

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

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

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

Время начальной подготовки (tн) характеризует:

(1) длительность подготовки сообщения для передачи, поиска маршрута в сети и т. п

(2) длительность передачи служебных данных

(3) время передачи одного слова данных по одному каналу передачи данных

Процессы параллельной программой в рамках MPI:

(1) могут выполняться на разных процессорах, на одном процессоре могут располагаться несколько процессов

(2) могут выполняться только на разных процессах

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

Рассмотрение графа "подзадачи – сообщения" концентрирует внимание на вопросах:

(1) выделения подзадач одинаковой вычислительной сложности

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

(3) детализированного представления графа информационных зависимостей

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

(1) операция широковещательной рассылки

(2) операция передачи данных от всех процессоров всем процессорам

(3) передача данных от одного процессора другому процессору вычислительной системы

Для эффективного выполнения параллельного алгоритма умножения матриц, основанного на ленточной схеме разделения данных, необходимо, чтобы процессоры вычислительной системы были организованы в топологию:

(1) гиперкуб

(2) линейка

(3) кольцо

При реализации параллельного алгоритма для метода сопряженных градиентов вычисления над векторами дублируются на всех процессорах для того, чтобы:

(1) уменьшить количество пересылок данных

(2) обеспечить контроль правильности вычислений

(3) уменьшить сложность разработки параллельной программы

Трудоемкость параллельного алгоритма чет-нечетной сортировки оценивается выражением:

(1)

(2)

(3)

Один из возможных способов агрегации вычислений для увеличения эффективности параллельного алгоритма Флойда состоит:

(1) в горизонтальном разбиении обрабатываемой матрицы

(2) в диагональном разбиении обрабатываемой матрицы

(3) в поэлементном разбиении обрабатываемой матрицы

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

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

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

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

При построении графических зависимостей для экспериментов, проведенных в режиме удаленного доступа к параллельной вычислительной системы, используется:

(1) накопленные результаты выполненных экспериментов

(2) теоретические оценки, применяемые в системе ПараЛаб

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

К основным преимуществам кластерных вычислительных систем относится:

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

(2) возможность модернизации и расширения аппаратного обеспечения

(3) построение из типовых элементов аппаратного и программного обеспечения

В модифицированной каскадной схеме:

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

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

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

В методе передачи пакетов:

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

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

Под коммуникатором в MPI понимается:

(1) специально создаваемый служебный объект, объединяющий в своем составе группу процессов и ряд дополнительных параметров, используемых при выполнении операций передачи данных

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

(3) пару процессов, в рамках которой происходит информационное взаимодействие

Для снижения сложности моделирования и анализа параллельных методов операции передачи и приема данных считаются выполняющимися:

(1) без задержек при передаче, но с возможными блокировками при приеме

(2) без задержек, как при передаче, так и при приеме данных

(3) с блокировками, как при передаче, так и при приеме данных

Для эффективного выполнения параллельного алгоритма умножения матрицы на вектор, основанного на разделении матрицы на горизонтальные полосы, необходимо, чтобы процессоры вычислительной системы были объединены в топологию:

(1) линейка

(2) гиперкуб или полный граф

(3) кольцо

С ростом числа процессоров, наибольшее ускорение демонстрирует:

(1) алгоритм Фокса

(2) алгоритм Кэннона

(3) алгоритм, основанный на ленточном разделении данных

(4) алгоритмы Фокса и Кэннона

С ростом числа процессоров, наибольшее ускорение демонстрирует:

(1) алгоритм Гаусса

(2) метод сопряженных градиентов

(3) ускорение алгоритмов совпадает

Основными отличиями параллельного алгоритма Шелла от метода чет-нечетной перестановки являются:

(1) взаимодействием процессоров, являющихся соседними в структуре гиперкуба на первом этапе

(2) взаимодействием процессоров, являющихся соседними в структуре полного графа на первом этапе

(3) взаимодействием процессоров, являющихся соседними в структуре гиперкуба, на втором этапе

Минимально охватывающим деревом называется:

(1) охватывающее дерево минимального веса

(2) охватывающее дерево с минимальной высотой

(3) охватывающее дерево с минимальным количеством вершин

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

(1) состязание (гонка) вычислений

(2) сериализация

(3) синхронизация

Какие топологий сети не поддерживает система имитационного моделирования ПараЛаб:

(1) звезда

(2) гиперкуб

(3) полный граф

Под мультипроцессором понимается:

(1) многопроцессорная вычислительная система с общей разделяемой памятью

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

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

Пусть есть задача вычисления произведения всех элемента вектора math

. Пусть N = 10 и применяется каскадная схема, аналогичная схеме описанной в лекции для суммирования элементов вектора. Какая в этом случае минимально возможная высота дерева модели вычисления:

(1) 4

(2) 5

(3) 6

Задача редукции определяется в общем виде как:

(1) процедура множественной рассылки, в ходе выполнения которой процессоры выполняют обработку получаемых данных, что сокращает объем пересылаемых сообщений

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

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

Процессы, между которыми выполняется передача данных:

(1) обязательно должны принадлежать одному коммуникатору

(2) обязательно должны принадлежать двум коммуникаторам

(3) не обязаны принадлежать одному коммуникатору

При выборе способа разделения вычислений при прочих равных условиях нужно отдавать предпочтение:

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

(2) частым операциям передачи сообщений большего размера

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

С ростом числа процессоров, согласно теоретической оценке, наибольшее ускорение демонстрирует:

(1) алгоритм, основанный на разделении матрицы на горизонтальные полосы

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

(3) алгоритм, основанный на блочном разделении матрицы

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы имеют тип double и занимают w = 8 байт. Если при распараллеливании использовать алгоритм Фокса, чему будет равно теоретическое ускорение при использовании 4 процессоров:

(1) 1,8

(2) 2,1

(3) 3,6

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы системы линейных уравнений имеют тип double и занимают w = 8 байт. Если при распараллеливании алгоритма Гауса использовалось 4 процессора, то какая в этом случае достигается теоретическая эффективность:

(1) 0,9

(2) 0,5

(3) 0,06

При надлежащем выборе ведущих элементов в алгоритме быстрой сортировки исходный массив данных оказывается упорядоченным после выполнения:

(1) log₂ n итераций

(2) n² итераций

(3) n log₂ n итераций

Показатели ускорения и эффективности параллельного алгоритма Прима имеют вид (без учета затрат на передачу данных):

(1) S_p=p, E_p=1

(2) S_p=1, E_p=1

(3) S_p=p, E_p=p

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

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

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

(3) выбор способа обработки локальных данных процессора

На каких топологиях сети в системе ПараЛаб реализованы алгоритмы перемножения матриц:

(1) полный граф

(2) кольцо

(3) гиперкуб

Среди рассмотренных в лекции типовых топологий приведены:

(1) топологии линейка, кольцо и полный граф

(2) топологии решетка и гиперкуб

(3) топологии дерево и тор

Пусть есть задача вычисления суммы следующего вида math

. Пусть N = 8 и применяется каскадная схема с минимально возможной высотой дерева модели вычисления. Чему в этом случае равна эффективность при использовании восьми вычислительных элементов:

(1) 5/7

(2) 1/2

(3) 2

Способы логического представления (отображения) топологий характеризуются следующими тремя основными характеристиками:

(1) уплотнение дуг, удлинение дуг и увеличение вершин

(2) увеличение дуг, удлинение дуг и уплотнение вершин

(3) уплотнение дуг, увеличение дуг и удлинение вершин

Функция MPI_Recv:

(1) блокирует процесс-получатель до момента фактического получения сообщения

(2) принимает сообщение в фоновом режиме, процесс в это время может продолжать вычисления

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

При асинхронном способе взаимодействия участники взаимодействия:

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

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

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

нсек. Латентности сети math

нсек. Пропускная способность сети 60 Мбайт/сек. Элементы матрицы имеют тип double и занимают w = 8 байт. Если при распараллеливании использовать разделение матрицы на строки чему будет равно теоретическая эффективность при использовании 4 процессоров:

(1) 5

(2) 3,97

(3) 2

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы имеют тип double и в системе занимают w = 8 байт. Если при распараллеливании использовать разделение матрицы на ленты, чему будет равна теоретическая эффективность при использовании 4 процессоров:

(1) 0,21

(2) 0,56

(3) 0,77

Рассмотрим задачу поиска решения системы линейных уравнений. Пусть размер матрицы системы линейных уравнений 20x20. На вычислительной системе все операции сложения и умножения выполняются одинаковое время math

нсек. Латентности сети math

нсек. Пропускная способность сети math

(1) 110000

(2) 2301122

(3) 1453075

Равновесность подмножеств вершин в задаче оптимального разделения графа:

(1) может не соответствовать минимальности весов граничных ребер

(2) всегда соответствует минимальности весов граничных ребер

(3) никогда не соответствует минимальности весов граничных ребер

Какие достоинства имеет синхронный механизм передачи сообщений?

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

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

(3) синхронные механизмы передачи, как правило, более надежны

В рамках системы ПараЛаб какие присутствуют средства для детального изучения и исследования параллельных алгоритмов решения сложных вычислительных задач:

(1) пошаговый режим исполнения задач

(2) одновременный запуск нескольких экспериментов

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

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

(1) топология гиперкуб

(2) топология кольцо

(3) топологии дерево

Пусть в решаемой задаче последовательная часть составляет четыре единицы времени, а часть, допускающая линейное распараллеливание, шесть единицы времени. Если использовать закона Густавсона-Барсиса, сколько потребуется процессоров для достижения ускорения в два раза (результат округлите в большую сторону):

(1) 6

(2) 7

(3) 8

Соседние вершины в нумерации кода Грея имеют:

(1) одну различающуюся битовую позицию

(2) не более двух различающихся битовых позиций

(3) ровно N различающихся битовых позиций

В буферизованном режиме функция отправки сообщения завершается:

(1) сразу же после копирования сообщения в системный буфер

(2) при получении от процесса-получателя подтверждения о начале приема отправленного сообщения

(3) при начале фактической передачи сообщения

Основным показателем успешности выполнения этапа распределения подзадач между процессорами является:

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

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

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

Оптимальная стратегия выбора ведущего элемента при применении параллельных алгоритмов быстрой сортировки состоит в выборе такого значения ведущего элемента, при котором:

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

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

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

Для разбиения графа на k частей в методе бинарного деления для решения задачи оптимального разделения графов необходимо:

(1) log₂k уровней рекурсии

(2) k уровней рекурсии

(3) k/2 уровней рекурсии

В модели Хокни используются параметры:

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

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

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

Завершение вызова функции неблокирующего обмена приводит:

(1) к инициации запрошенной операции передачи, но ничего не говорит о завершенности обмена

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

(3) к фактическому выполнению обмена

Один из этапов параллельного алгоритма быстрой сортировки состоит том, что:

(1) каждый процессор разделяет имеющийся блок данных на две части с использованием ведущего элемента

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

(3) каждый процессор разделяет имеющийся блок данных на N частей и объединяет свои части с частями блоков данных процессоров, соседних в структуре гиперкуба

На одном из этапов метода покоординатного разбиения для решения задачи оптимального разделения графов:

(1) вычисляются центры масс элементов сети

(2) вычисляется центр графа

(3) вычисляется середина сети

Коллективные операции MPI:

(1) могут быть реализованы при помощи парных операций, однако такое решение, скорее всего, будет не эффективным

(2) принципиально не могут быть реализованы при помощи парных операций

(3) могут быть реализованных при помощи парных операций, но не в полном объеме

При выполнении алгоритма обобщенной быстрой сортировки в качестве ведущего элемента обычно выбирается:

(1) средний элемент блока данных какого-либо процессора системы (например, первого процессора)

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

(3) средний элемент среди средних элементов блоков данных процессоров системы

В отличие от геометрических схем комбинаторные методы решения задачи оптимального разделения графов не принимают во внимание:

(1) информацию о близости расположения элементов сети друг относительно друга

(2) информацию о весах графа, построенного для исходной сети

(3) информацию о связности элементов сети друг относительно друга

Обобщенная передача данных от всех процессов всем процессам может быть описана как:

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

(2) операция, при которой происходит передача одинаковых данных от всех процессов всем процессам

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

Сигнатурой производного типа в MPI именуется:

(1) часть карты типа с указанием только типов значений

(2) часть карты типа с указанием только смещений для входящих в тип элементов

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

При индексном способе новый производный тип создается как:

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

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

(3) непрерывная последовательно элементов исходного типа

В декартовой топологии множество процессов представляется в виде:

(1) прямоугольной решетки

(2) графа произвольного вида

(3) полного графа

При разработке параллельного алгоритма умножения матриц, основанного на ленточной схеме разделения данных, может быть использован подход:

(1) обе матрицы разделены на вертикальные полосы

(2) обе матрицы разделены на горизонтальные полосы

(3) одна из матриц разделена на горизонтальные полосы, а вторая – на вертикальные полосы

Какое расположение вектора правых частей и вектора неизвестных используется при реализации параллельного алгоритма Гаусса:

(1) оба вектора скопированы на все процессоры вычислительной системы

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

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

(4) оба вектора разделены между процессорами вычислительной системы

Нижняя оценка необходимого количества операций для упорядочивания набора из n значений определяется выражением:

(1)

(2)

(3)

Матрица смежности это:

(1) матрица, значения элементов которой обозначают веса соответствующих дуг графа

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

(3) матрица, знаки бесконечности которой обозначают наличие соответствующей дуги в графе

При разработке параллельных алгоритмов решения дифференциальных уравнений в частных производных за основу выбирается разделение данных, потому что:

(1) при проведении реальных расчетов приходится иметь дело с данными, которые не могут быть полностью помещены в память одного процессора

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

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

К числу параметров вычислительной системы в системе ПараЛаб относятся:

(1) топология,

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

(3) характеристики протокола передачи данных

Распределенные вычислительные системы:

(1) могут быть использованы для параллельных вычислений только для программ с низкой интенсивностью потоков межпроцессорных передач данных

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

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

В модели вычислений дуги графа определяют:

(1) зависимость операций по операндам

(2) распределение операций между процессорами

(3) наличие каналов передачи данных между процессорами

Метод покоординатной маршрутизации в приложении к топологии типа гиперкуб состоит:

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

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

(3) циклической передаче данных процессорам, номера которых отличаются не более чем на 2 от номера процессора, на котором сообщение располагается в данный момент времени, и процессом-получателем

Минимально необходимый набор операций для организации информационного взаимодействия между процессорами в вычислительных системах с распределенной памятью включает в себя только:

(1) операции приема и передачи данных

(2) операции передачи данных и коллективные операции

(3) только коллективные операции

Качество разрабатываемых параллельных методов определяется:

(1) значениями показателей ускорения, эффективности и масштабируемости

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

(3) только значением ускорения

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

(1) при проведении реальных расчетов приходится иметь дело с матрицами, которые не могут быть полностью помещены в память одного процессора

(2) для разных элементов матриц применяются разные вычислительные алгоритмы

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

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

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

(2) операция редукции данных

(3) циклический сдвиг

На каждой итерации обратного хода метода Гаусса используется

(1) операция широковещательной рассылки

(2) передача данных от одного процессора другому процессору вычислительной системы

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

Базовая операция "сравнить и разделить" отличается от операции "сравнить и переставить":

(1) наличием нескольких процессоров, выполняющих операцию сравнения и обмена значениями

(2) выбором ведущего элемента

(3) тем, что она не содержит операций обменов данными между процессами

Показатели ускорения и эффективности параллельного алгоритма Флойда имеют вид (без учета затрат на передачу данных):

(1) S_p=p, E_p=1

(2) S_p=p, E_p=p

(3) S_p=1, E_p=p

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

(1) равномерное распределение узлов сетки между потоками

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

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

При проведении серии экспериментов системой ПараЛаб может автоматически варьироваться:

(1) количество процессоров

(2) метод решения задачи

(3) объем исходных данных задачи

Суперкомпьютеры:

(1) занимают весь список TOP500 самых высокопроизводительных систем

(2) всегда состоят из множества отдельных компьютеров, объединенных в сеть, для которых при помощи специальных аппаратно-программных средств обеспечивается возможность унифицированного управления, надежного функционирования и эффективного использования

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

Стоимость вычислений - это:

(1) произведение времени параллельного решения задачи на число используемых процессоров

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

(3) произведение времени последовательного алгоритма на число используемых процессоров

Основной набор параметров, описывающих время передачи данных, состоит из следующего набора величин:

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

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

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

Номер процесса в рамках MPI именуется:

(1) рангом процесса

(2) идентификатором процесса

(3) дескриптором процесса

Граф "процессы – каналы" используется:

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

(2) для описания параллельного алгоритма на этапе проектирования

(3) для детализированного представления графа информационных зависимостей

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

(1) операция передачи сообщений типа «точка-точка»

(2) операция обобщенной редукции данных

(3) операция циклического сдвига

Для эффективного выполнения алгоритма Кэннона необходимо, чтобы процессоры вычислительной системы были организованы в топологию:

(1) линейка

(2) решетка или полный граф

(3) гиперкуб

За основу организации параллельных вычислений при реализации метода сопряженных градиентов выбирается параллельное выполнение операции умножения матрицы на вектор, потому что:

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

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

(3) операция умножения матрицы на вектор может быть эффективно распараллелена

Общее число итераций параллельного алгоритма чет-нечетной сортировки при использовании p процессоров равно:

(1) p

(2) plog₂ p

(3) p²

При горизонтальном разбиении матрицы исходных данных на каждой итерации алгоритма Флойда потребуется передавать между подзадачами:

(1) только элементы одной из строк матрицы

(2) только элементы одного из столбцов матрицы

(3) только элементы, лежащие на главной диагонали матрицы

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

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

(2) увеличение времени передачи данных между процессорами

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

При анализе результатов проведенных экспериментов пользователю предоставляется возможность:

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

(2) изменять масштаб отображения графиков

(3) изменять вид зависимости, отображенной на листе графиков

Кластерные вычислительные системы:

(1) составляют большинство в списке TOP500 самых высокопроизводительных систем

(2) не входят в список TOP500 самых высокопроизводительных систем

(3) представлены небольшим числом систем в списке TOP500 самых высокопроизводительных систем

При вычислении общей суммы последовательности числовых значений стоимостно-оптимальным алгоритмом является:

(1) модифицированная каскадная схема

(2) обычная каскадная схема

(3) обе схемы каскадных вычислений

Метод передачи пакетов в большинстве случаев приводит к:

(1) более быстрой пересылке данных

(2) более медленной пересылке данных

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

Указание используемого коммуникатора является:

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

(2) необязательным для некоторых операций передачи данных в MPI

(3) обязательным для некоторых операций передачи данных в MPI

Под процессом понимают:

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

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

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

Для эффективного выполнения параллельного алгоритма умножения матрицы на вектор, основанного на разделении матрицы на вертикальные полосы, необходимо, чтобы процессоры вычислительной системы были объединены в топологию:

(1) звезда

(2) решетка

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

Какие алгоритмы обладают наилучшими теоретическими показателями ускорения и эффективности (в случае, когда не учитываются затраты на передачу данных между процессорами):

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

(2) алгоритм Фокса

(3) алгоритм Кэннона

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

Общее наименьшее количество итераций параллельного алгоритма Шелла равно:

(1) log₂ p

(2) p²

(3) plog₂ p

Задача нахождения МОД формулируется как:

(1) задача нахождения охватывающего дерева с минимальным весом

(2) задача нахождения охватывающего дерева с минимальной высотой

(3) задача нахождения охватывающего дерева с минимальным количеством вершин

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

(1) организацией обмена данных большого объема между процессорами при помощи передачи коротких сообщений

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

(3) достигаемой степенью локализации вычислений

Какие режимы передачи данных поддерживает система имитационного моделирования ПараЛаб:

(1) передачи пакетов

(2) передачи сообщений

(3) побайтная передача данных

Под мультикомпьютером понимается:

(1) многопроцессорная вычислительная система с распределенной памятью

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

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

Пусть есть задача вычисление суммы следующего вида math

. Пусть N = 4 и применяется каскадная схема, аналогичная схеме описанной в лекции для суммирования элементов вектора. Какая в этом случае минимально возможная высота дерева модели вычисления:

(1) 3

(2) 4

(3) 5

Циклический q-сдвиг, это операция, при которой:

(1) каждый процессор math

, передает данные процессору с номером (i+q)mod p

(2) ведущий процессор math

, передает данные процессору с номером (i+q+k)mod p, math

(3) каждый процессор math

, передает данные процессору с номером i+q mod p

Завершение функции MPI_Send означает, что:

(1) операция передачи начала выполняться и пересылка сообщения будет рано или поздно будет выполнена

(2) сообщение находится в состоянии передачи

(3) сообщение принято процессом-получателем при помощи функции MPI_Recv

Разработка параллельных алгоритмов включает в себя этапы:

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

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

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

(1) алгоритм, основанный на ленточном разделении матрицы

(2) алгоритм, основанный на блочном разделении матрицы

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

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы имеют тип double и в системе занимают w = 8 байт. Если при распараллеливании использовать алгоритм Кеннона, чему будет равно теоретическое ускорение при использовании 4 процессоров:

(1) 2,5

(2) 1,5

(3) 1,17

Рассмотрим задачу поиска решения системы линейных уравнений. Размер матрицы системы линейных уравнений 10x10. На вычислительной системе все операции сложения и умножения выполняются одинаковое время math

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы системы линейных уравнений имеют тип double и в системе занимают w = 8 байт. Если при распараллеливании алгоритма Гауса использовалось 4 процессора, то какая в этом случае достигается теоретическая стоимость параллельного алгоритма:

(1) 1387870

(2) 2102751

(3) 1453075

В худшем случае трудоемкость быстрой сортировки оценивается выражением:

(1)

(2)

(3)

Трудоемкость нахождения МОД характеризуется:

(1) квадратичной зависимостью от числа вершин графа

(2) кубической зависимостью от числа вершин графа

(3) квадратичной зависимостью от числа ребер графа

В рассматриваемой учебной задаче по решению задачи Дирихле при использовании разделенной памяти, какие возможны способы разделения данных?

(1) ленточная схема

(2) блочное разбиение

(3) диагональное разбиение

На каких топологиях сети в системе ПараЛаб не реализованы алгоритмы обработки графов:

(1) полный граф

(2) решетка

(3) кольцо

К числу характеристик топологии сети передачи данных относятся:

(1) диаметр и стоимость

(2) связность и ширина бинарного деления

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

Пусть есть задача вычисления суммы следующего вида math

. Пусть N = 6 и применяется каскадная схема с минимально возможной высотой дерева модели вычисления. Чему в этом случае равна стоимость вычислений при использовании восьми вычислительных элементов:

(1) 32

(2) 16

(3) 8

Увеличение вершин:

(1) отношение количества вершин в логической и физической топологиях

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

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

Прием сообщений при помощи функции MPI_Recv может быть осуществлен:

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

(2) от любого адресата, однако, тег сообщения должен быть указан однозначно

(3) от однозначно определяемого адресата с заданным тегом

В статической схеме передачи данных:

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

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

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

нсек. Латентности сети math

нсек. Пропускная способность сети 60 Мбайт/сек. Элементы матрицы имеют тип double и занимают w = 8 байт. Если при распараллеливании использовать разделение матрицы на строки чему будет равно теоретическая стоимость при использовании 2 процессоров:

(1) 200000000

(2) 01313412

(3) 221313412

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы имеют тип double и занимают w = 8 байт. Если при распараллеливании использовать алгоритм Фокса, чему будет равна теоретическая эффективность при использовании 4 процессоров:

(1) 0,55

(2) 0,77

(3) 0,98

нсек. Латентности сети math

нсек. Пропускная способность сети math

Mбайт/сек. Элементы матрицы системы линейных уравнений имеют тип double и занимают w = 8 байт. Если при распараллеливании алгоритма сопряженных градиентов использовалось 4 процессора, то какое в этом случае достигается теоретическое ускорение:

(1) 3,1

(2) 1,5

(3) 0,3

Задача разделения вычислительной сети, на которую разбивается область обрабатываемых данных, между процессорами может быть сведена:

(1) к проблеме оптимального разделения графа

(2) к задаче поиска всех кратчайших путей

(3) к задаче нахождения минимального охватывающего дерева

Какие достоинства и недостатки имеет асинхронный механизм передачи сообщений?

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

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

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

Помимо выполнения экспериментов в режиме имитации, в системе ПараЛаб предусмотрена возможность проведения реальных экспериментов в режиме удаленного доступа к вычислительному кластеру. Какие возможны операции после выполнения реальных параллельных вычислений:

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

(2) осуществить настройку параметров удаленного кластера

(3) настроить параметры моделей, используемых в системе ПараЛаб

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

(1) топология полное двоичное дерево

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

(3) топология полный граф

Пусть в решаемой задаче последовательная часть составляет четыре единицы времени, а часть, допускающая линейное распараллеливание, шесть единицы времени. Если использовать закон Амдаля, какая достигается эффективность, если используются три вычислительных элемента:

(1) 1/5

(2) 7/6

(3) 5/9

Соседние вершины в кольцевой топологии отображаются кодом Грея:

(1) на соседние процессоры в гиперкубе

(2) процессоры, находящиеся на расстоянии не более чем 2 единицы в гиперкубе

(3) на соседние процессоры в торе

Режим передачи по готовности может быть использован только если:

(1) операция приема сообщения уже инициирована

(2) при достаточном малом размере сообщения, менее размера системного буфера

(3) операция приема сообщения гарантированно будет запущена позднее момента начала передачи сообщения

Этап распределения подзадач между процессорами является избыточным, если:

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

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

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

Пусть перед программистом поставлена задача перемножения матрицы на вектор. Размер перемножаемой матрицы 100x100. На вычислительной системе все операции сложения и умножения выполняются одинаковое время math

нсек. Латентности сети math

нсек. Пропускная способность сети 60 Мбайт/сек. Элементы матрицы имеют тип double и в системе занимают w = 8 байт. Если при распараллеливании использовать разделение матрицы на блоки (количество блоков по строкам и по строкам равно и равно math

, где p – количество процессоров), чему будет равно теоретическая эффективность при использовании 4 процессоров:

(1) 0,04

(2) 0,48

(3) 0.9

Три схемы распараллеливания алгоритма быстрой сортировки различаются:

(1) стратегией выбора ведущего элемента

(2) способом рассылки ведущего элемента остальным процессорам

(3) стратегией выбора ведущего процесса

Для разбиения графа на k частей в методе бинарного деления для решения задачи оптимального разделения графов необходимо выполнить:

(1) k-1 деление графа пополам

(2) k/2 делений графа пополам

(3) log₂k делений графа пополам

Топология полный граф сети кластерной вычислительной системы может иметь ограничения на:

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

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

(3) количество процессоров в сети

Функция блокирующего ожидания завершения одного обмена в MPI называется:

(1) MPI_Wait

(2) MPI_Waitall

(3) MPI_Waitone

В результате выполнения одной итерации параллельного алгоритма быстрой сортировки исходное множество процессоров разделяется на:

(1) два подмножества процессоров по p/2 процессоров в каждом и, таким образом, исходный N-мерный гиперкуб также оказывается разделенным на два гиперкуба размерности N-1

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

(3) два подмножества процессоров по p/2 процессоров в каждом и, таким образом, исходный N-мерный гиперкуб также оказывается разделенным на два гиперкуба размерности N/2

Для определения угла поворота в рекурсивном инерционном методе деления пополам при решении задачи оптимального разделения графов, используется:

(1) главная инерционная ось сети

(2) кривые Пеано, построенные на основании сети

(3) центр масс элементов сети

Под коллективными операциями в MPI понимаются:

(1) операции передачи данными, в которых принимают участие все процессы используемого коммуникатора

(2) операции над группами процессов

(3) операции над коммуникаторами

Для поддержки упорядоченности в ходе выполнения алгоритма обобщенной быстрой сортировки процессоры должны выполнять:

(1) операцию слияния частей блоков, получаемых после обмена данных между процессорами

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

(3) операцию выбора среднего элемента после слияния частей блоков

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

(1) более сбалансированное разбиение и меньшее информационное взаимодействие полученных подсетей

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

(3) более быстрое решение поставленной задачи

Операция широковещательной рассылки данных это:

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

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

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

Протяженность производного типа в MPI это:

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

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

(3) смещение первого байта значений рассматриваемого типа

H-векторный и H-индексный способы создания данных отличаются от векторного и индексного способов тем, что:

(1) интервалы между блоками задаются в байтах, а не в элементах исходного типа данных

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

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

Топология типа тор в MPI является частным видом топологии типа:

(1) декартовой топологии

(2) графа произвольного вида

(3) полный граф