Ответы на вопросы из коллекции "Теория и практика параллельных вычислений"

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

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

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

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

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

• решетка или полный граф
• гиперкуб
• звезда

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

• сразу же после копирования сообщения в системный буфер
• при получении от процесса-получателя подтверждения о начале приема отправленного сообщения
• при начале фактической передачи сообщения

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

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

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

• кривые Пеано, построенные на основании сети
• главная инерционная ось сети
• центр масс элементов сети

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

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

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

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

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

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

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

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

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

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

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

• парные и коллективные операции
• парные и групповые операции
• индивидуальные и коллективные операции

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

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

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

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

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

• гиперкуб
• кольцо
• линейка

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

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

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

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

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

• накопленные результаты выполненных экспериментов
• теоретические оценки, применяемые в системе ПараЛаб
• теоретические оценки, определенные пользователем системы

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

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

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

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

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

• полный граф
• кольцо
• гиперкуб

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• до момента, в момент или после момента начала отправки сообщения
• только в момент начала отправки сообщения
• только после момента начала отправки сообщения

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

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

Увеличение вершин:

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

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

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

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

• топология гиперкуб
• топология кольцо
• топологии дерево

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

• NCSA NT, Beowulf,
• SCI White, BlueGene
• AC3 Velocity, Thunder

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

• операции приема и передачи данных
• операции передачи данных и коллективные операции
• только коллективные операции

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

• декартовой топологии
• графа произвольного вида
• полный граф

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

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

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

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

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

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

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

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

Граф это:

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

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

• ленточное разделение данных
• диагональное разделение матрицы
• блочное разделение данных

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

• p2
• plog2 p
• log2 p

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

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

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

• передача данных от одного процессора другому процессору вычислительной системы
• операция широковещательной рассылки
• операция редукции данных

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

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

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

• Sp=p, Ep=1
• Sp=1, Ep=p
• Sp=p, Ep=p

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

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

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

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

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

• Sp=p, Ep=p
• Sp=p, Ep=1
• Sp=1, Ep=1

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

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

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

• 5/9
• 1/5
• 7/6

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

• сообщение принято процессом-получателем при помощи функции MPI_Recv
• сообщение находится в состоянии передачи
• операция передачи начала выполняться и пересылка сообщения будет рано или поздно будет выполнена

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

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

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

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

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

• ациклический ориентированный граф
• циклический ориентированный граф
• бинарное дерево

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

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

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

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

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

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

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

• все процессы используемого коммуникатора
• некоторые процессы используемого коммуникатора
• все процессы используемой группы процессов

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

• линейка
• решетка или полный граф
• гиперкуб

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

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

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

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

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

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

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

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

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

• тип задачи
• метод решения задачи
• объем исходных данных

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

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

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

• увеличение объема передаваемых данных
• увеличение граничных строк
• увеличение объема служебных передаваемых данных

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

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

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

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

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

• log2k уровней рекурсии
• k уровней рекурсии
• k/2 уровней рекурсии

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

• охватывающее дерево минимального веса
• охватывающее дерево с минимальной высотой
• охватывающее дерево с минимальным количеством вершин

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

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

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

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

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

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

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

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

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

• операция обобщенного сбора данных
• операции широковещательной рассылки и редукции данных
• операция циклического сдвига

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

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

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

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

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

• ленточная схема разделения данных
• блочная схема разделения данных
• данные дублируются между процессорами

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

• операции передачи сообщений типа «точка-точка»
• операции обобщенного сбора данных
• операция редукции данных

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

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

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

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

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

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

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

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

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

• агрегированное представление графа информационных зависимостей
• детализированное представление графа информационных зависимостей
• агрегированное представление графа " процессы – каналы"

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

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

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

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

Соседние вершины в кольцевой топологии отображаются кодом Грея:

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

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

• уплотнение дуг, удлинение дуг и увеличение вершин
• уплотнение дуг, увеличение дуг и удлинение вершин
• увеличение дуг, удлинение дуг и уплотнение вершин

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

• N log2N-этапной процедуры передачи данных
• N-этапной процедуры передачи данных
• N2-этапной процедуры передачи данных

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

• повышению потребности в памяти для хранения пересылаемых данных
• более быстрой пересылке данных
• более медленной пересылке данных

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

• 6
• 7
• 8

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

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

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

• топология гиперкуб
• топология полный граф
• топология линейка

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

• топологии дерево и тор
• топологии линейка, кольцо и полный граф
• топологии решетка и гиперкуб

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

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

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

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

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

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

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

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