Главная / Суперкомпьютерные технологии / Введение в параллельные алгоритмы

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

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

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

Программирование

Алгоритмы и дискретные структуры

Вычислительные системы с общей памятью:

(1) масштабируются лучше систем с распределенной памятью

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

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

Хороший параллельный алгоритм:

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

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

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

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

(1) O(n*log(n))

(2) O(n^2)

(3) O(n)

Верно ли что:

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

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

(3) из того, что оценки времен выполнения двух алгоритмов A1 и A2 находятся в отношении O(A1)< O(A2) следует, что время выполнения первого алгоритма будет меньше, чем время выполнения второго алгоритма

Чему равен период генератора u[i+1]=(5* u[i]+7) mod 16, i>0:

(1) 16

(2) 7

(3) зависит от значения u[0]

Применение метода геометрического параллелизма при интегрировании функции с заданной точностью в общем случае приводит:

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

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

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

Использование послойной схемы при решении заполненных систем линейных уравнений позволяет:

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

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

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

Семафоры необходимы:

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

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

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

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

(1) разработки параллельного алгоритма

(2) запуска задачи на счет

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

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

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

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

(3) зависит от числа элементов в сортируемом массиве

Число шагов выполнения компараторов сортировки-слияния при использовании нечетно-четного слияния Бэтчера на p процессорах оценивается как:

(1) 0.5*(log2(p))²

(2) p*log2(p)

(3) log2(p)

Чему равен период генератора x^k mod (x²+1), x>1?

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

Метод коллективного решения для интегрировании функции с заданной точностью:

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

(2) эффективен, если отрезок интегрирования достаточно велик

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

Применение метода встречной прогонки на двух процессорах обеспечивает эффективность:

(1) близкую к 100%

(2) близкую к 66%

(3) близкую к 50%

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

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

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

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

Метод геометрического параллелизма является:

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

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

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

Что такое пирамида:

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

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

(3) бинарное дерево в котором левый потомок любого узла не ниже правого потомка

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

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

(2) поразрядных сортировок

(3) любых сортировок

Чему равно u[33], если u[i+1]=(1 * u[i]+3) mod 5 при u[0]=3:

(1) 2

(2) 1

(3) 0

Метод глобального стека является:

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

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

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

Алгоритм метода Гаусса:

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

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

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

Ускорение большее, чем число используемых процессоров:

(1) недостижимо

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

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

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

(1) латентностью каналов межпроцессорной связи

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

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

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

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

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

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

Отметьте сети, правильно сортирующие любой массив из 4-х элементов с помощью компараторов слияния (a,b) выполняющих сравнение-перестановку элементов с номерами a и b:

(1) (0-1), (0-2), (1-2), (1-3), (2-3)

(2) (0-1), (2-3), (1-3), (1-2), (0-2)

(3) (0-1), (2-3), (0-2), (1-3), (1-2)

Чему равно x¹⁰ mod (x²+x+1):

(1) х

(2) x+1

(3) x²

Алгоритм глобального стека предполагает:

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

(2) наличие управляющего процессора

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

Диффузная балансировка загрузки:

(1) применима при решении СЛАУ методом Гаусса

(2) применима при последовательном решении множества систем линейных уравнений (СЛАУ), например, при моделировании диффузионных процессов

(3) применима при решении СЛАУ методом прогонки

С помощью алгоритма сдваивания можно найти сумму элементов массива:

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

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

(3) нельзя найти сумму элементов массива

Метод конвейерного параллелизма:

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

(2) эффективен при решении слабосвязанных задач

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

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

(1) 1 000 000

(2) 6 000 000

(3) 1 000 000 000 000

Какое минимальное количество параллельных шагов необходимо для сортировки с помощью сети (0-1), (2-3), (1-2), (0-1), (2-3), (1-2):

(1) 3

(2) 4

(3) 6

Отметьте за какое время можно ли вычислить значение любого u[k]=(a* u[k-1]+c) mod M.

(1) за время, пропорциональное k

(2) за время, равное времени вычисления u[100]

(3) за время, пропорциональное log(k)

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

(1) глобальный стек пуст

(2) вычислены локальные суммы

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

Укрупнение заданий, единовременно передаваемых на обработку в методе коллективного решения:

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

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

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

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

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

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

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

Вычислительные системы с распределенной памятью:

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

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

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

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

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

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

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

Алгоритму сортировки слиянием в наихудшем случае наиболее точно соответствует оценка числа операций:

(1) O(n*log(n))

(2) O(n)

(3) O(log(n))

Верно ли что:

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

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

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

Чему равен период генератора u[i+1]=(3* u[i]+2) mod 8, i>0:

(1) 7

(2) 8

(3) зависит от значения u[0]

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

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

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

(3) при интегрировании любой достаточно сложной функции

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

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

(2) необходимости решения на одном процессоре системы из 2*p уравнений

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

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

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

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

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

Динамическая балансировка загрузки требует:

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

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

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

При сортировке слиянием массива из N элементов:

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

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

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

Общее время сортировки n элементов методом нечетно-четного слияния Бэтчера на p процессорах оценивается как:

(1) (n/p)*( log2(n/p) + 0.5*(log2(p))² )

(2) (n/p)*( log2(n/p) + log2(p) )

(3) (n/p)*log2(n/p) + p*log2(p)

Чему равен период генератора x^k mod (x²+x+1):

(1) 3

(2) 4

(3) 2

Общий объем передаваемых управляющим процессором данных:

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

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

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

Применение метода встречной прогонки на p процессорах при числе уравнений равном p² обеспечивает эффективность:

(1) порядка 99%

(2) порядка 33%

(3) порядка 66 %

Совмещение вычислений и операций передачи данных:

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

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

(3) невозможно

Для построения стены Фокса:

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

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

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

Что такое сбалансированное бинарное дерево:

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

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

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

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

(1) в 4 раза

(2) в 2 раза

(3) не сократится

Чему равно u[34], если u[i+1]=(5 * u[i]+1) mod 32 при u[0]=0

(1) 16

(2) 6

(3) 15

Использование локальных стеков:

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

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

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

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

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

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

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

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

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

(2) к сокращению времени решения задачи на многопроцессорной системе

(3) не влияют на время выполнения

Метод коллективного решения применим:

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

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

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

Сверхлинейное ускорение возможно за счет:

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

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

(3) невозможно

(1) (0-1), (1-3), (2-3), (0-1), (1-3), (2-3)

(2) (0-1), (2-3), (1-2), (0-1), (2-3), (1-2)

(3) (1-2), (0-2), (1-3), (1-2), (0-2), (1-3)

Чему равно x³² mod (x⁴+x+1):

(1) 1

(2) x

(3) x²

Если в алгоритме глобального стека размер локальных стеков сделать равным 1, то:

(1) работа завершится с ошибкой из-за переполнения глобального стека

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

(3) полученный ответ будет не верным

Диффузная балансировка загрузки:

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

(2) обеспечивает сокращение времени решения задачи

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

Максимальное число процессоров, эффективное использование которых возможно при построении стены Фокса методом конвейерного параллелизма, не превышает:

(1) ширины стены (числа кирпичей в её основании)

(2) высоты стены

(3) общего числа кирпичей в стене

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

(1) 1 000 000

(2) 6 000 000

(3) 1 000 000 000 000

Какое минимальное количество параллельных шагов необходимо для сортировки с помощью сети (0-1), (1-2), (2-3), (0-1), (1-2), (0-1):

(1) 3

(2) 5

(3) 6

Справедливо ли, что:

(1) точки, имеющие координаты x[i]=(a* u[2*i]+c) mod M и y[i]=(a* u[2*i+1]+c) mod M, расположены на небольшом, по сравнению с M, количестве параллельных прямых

(2) период линейно-конгруэнтного генератора { u[i]=(a* u[2*i]+c) mod M } всегда меньше M

(3) период генератора { x^k mod G(x) }, где G(x) – полином степени k может иметь период 2^k

К накладным расходам, снижающим эффективность параллельных алгоритмов, относятся:

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

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

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

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

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

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

(3) возможность формирование последовательности, длина которой превышает 2³² элементов

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

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

(2) калькуляторы

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

Сокращение времени выполнения программы на многопроцессорной системе может быть обусловлено:

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

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

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

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

(1) O(n*log(n))

(2) O(n^2)

(3) O(n)

Верно ли что:

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

(2) для построения сети сортировки Бетчера необходима многопроцессорная система

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

Чему равен период генератора (5*u[i]+2) mod 8:

(1) 9

(2) 8

(3) 7

(4) 6

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

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

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

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

Использование упреждающей рассылки элементов ведущей строки на p процессоров:

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

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

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

Буферизация при асинхронной передаче данных необходима для:

(1) сокращения общего времени взаимных ожиданий

(2) уменьшения объемов используемой памяти

(3) сокращения времени передачи сообщений

Статическая балансировка загрузки применима:

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

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

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

При упорядочивании массива из N элементов с помощью пирамидальной сортировки:

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

(2) число операций в худшем случае пропорционально N*log(N)

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

Число операций выполняемых одним компаратором сортировки-слияния на одном процессоре оценивается как:

(1) (n/p)

(2) 2*(n/p)

(3) (n/p)*log2(n/p)

Чему равен период генератора x^k mod (x⁴+x+1):

(1) 16

(2) 4

(3) 15

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

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

(2) к выполнению большого объема лишних вычислений

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

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

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

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

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

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

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

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

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

Максимальное число процессоров, эффективное использование которых возможно при построении стены Фокса методом геометрического параллелизма, не превышает:

(1) ширины стены (числа кирпичей в её основании)

(2) высоты стены

(3) общего числа кирпичей в стене

Что такое упорядоченная пирамида:

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

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

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

Эффективность параллельного алгоритма сортировки n элементов на p процессорах с помощью сетей нечетно-четного слияния Бэтчера в предположении нулевой латентности и нулевого времени на передачу данных равна:

(1) близка к 100%

(2) оценивается как log n/(log p)²

(3) оценивается как 1/(log p)

Чему равно u[134], если u[i+1]=(2 * u[i]+2) mod 16 при u[0]=6

(1) 6

(2) 14

(3) правильного ответа нет

Отказ от рекурсивного вызова процедур интегрирования на отрезке позволяет:

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

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

(3) уменьшить максимальную глубину стека хранимых заданий

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

(1) N

(2) N²

(3) log(N)

Суперкомпьютеры предназначены:

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

(2) для обработки больших объемов данных

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

Метод коллективного решения:

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

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

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

Верно ли, что:

(1) время выполнения пирамидальной сортировки массива из n элементов на вычислительной системе с неограниченной памятью пропорционально n*log(n) при наличии ограниченной кеш памяти

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

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

(1) (1-2), (0-2), (1-3), (0-2), (1-3) , (1-2)

(2) (0-1), (1-2), (2-3), (0-1), (1-2), (0-1)

(3) (0-1),(1-2),(2-3),(0-3),(0-1),(1-2)

Чему равно x¹² mod (x²+1):

(1) 1

(2) x

(3) x²

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

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

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

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

Диффузная балансировка загрузки:

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

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

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

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

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

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

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

(4) зависит от особенностей конкретной задачи

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

Метод конвейерного параллелизма:

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

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

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

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

(1) 1 000 000

(2) 6 000 000

(3) 1 000 000 000 000

Какое минимальное количество параллельных шагов необходимо для сортировки с помощью сети (0-1), (2-3), (0-2), (1-3), (1-2):

(1) 3

(2) 4

(3) 5

За какое время можно вычислить значение любого { xⁱ mod G(x) }, где G(x) – полином степени k?

(1) за время, равное времени вычисления x¹⁰⁰ mod G(x)

(2) за время, пропорциональное i

(3) за время, пропорциональное log(i)

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

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

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

(3) полученный ответ будет неверным

Дублирование вычислений:

(1) снижает эффективность параллельного алгоритма

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

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

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

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

(2) для тестирования последовательности с помощью батареи тестов Diehard необходима многопроцессорная система

(3) одна и та же последовательность может быть сформирована с помощью каждого из трех методов: 1) M-последовательностей, 2) генератора на сдвиговом регистре, 3) генератора на основе примитивных полиномов