Параллельное программирование

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

Номер 1

Определите сложность алгоритма решения задачи. Умножение матриц размерности n

Ответ:

(1) О(n²)

(2) О(n³)

(3) О(n⁴)

Номер 2

Определите сложность алгоритма решения задачи. Сложение n элементов массива способом "пирамиды"

Ответ:

(1) О(nlg₂n)

(2) О(n²)

(3) О(n)

Номер 3

Определите сложность алгоритма решения задачи. Перебор и решение комбинаций по т линейных уравнений из множества n таких уравнений, если известно, что функция C_n^m  растет быстрее, чем 2ⁿ, которая принимается за нижнюю оценку

Ответ:

(1) О(n²2ⁿ)

(2) О(n³)

(3) O(n2ⁿ)

Номер 4

Определите сложность алгоритма решения задачи. Цикл заполнения двоичного счетчика времени на регистре, содержащем n разрядов

Ответ:

(1) О(2ⁿ)

(2) О(n)

(3) O(nlg₂n)

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

Номер 1

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

Ответ:

(1) достоинства: отказоустойчивость, бесконфликтное централизованное управление обменом. Недостатки: малое количество РС (до 16), дополнительные затраты на центральный компьютер или сервер от которого зависит мощность всей сети

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

(3) достоинства: отказоустойчивость, бесконфликтное централизованное управление обменом. Недостатки: малое количество РС (до 16), дополнительные затраты на центральный компьютер или сервер от которого зависит мощность всей сети, малая удаленность РС от центрального компьютера

Номер 2

Рассмотрите основные топологии локальных вычислительных сетей. Какие достоинства и недостатки имеет топология "кольцо"?

Ответ:

(1) достоинства: количество РС может превышать 1000, сочетание централизованного обмена с децентрализованным, значительная протяженность линий связи. Недостатки: отказ одной РС может вывести из строя всю сеть, сложность подключения РС, обменом связаны только соседние РС

(2) достоинства: сочетание централизованного обмена с децентрализованным, значительная протяженность линий связи. Недостатки: отказ одной РС может вывести из строя всю сеть, количество РС не превышает 32, сложность подключения РС, обменом связаны только соседние РС

(3) достоинства: централизованное управление обменом, значительная протяженность линий связи, обменом связаны только соседние РС. Недостатки: отказ одной РС может вывести из строя всю сеть, количество РС не превышает 128, сложность подключения РС

Номер 3

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

Ответ:

(1) достоинства: отказоустойчивость, комплектация превышает 1000 РС, количество абонентов легко изменяется, дешевая среда передачи данных, децентрализованное управление обменом. Недостатки: значительные объемы трафика уменьшают пропускную способность обмена, затруднена локализация отказов

(2) достоинства: отказоустойчивость, комплектация превышает 1000 РС, количество абонентов легко изменяется, дешевая среда передачи данных, централизованное управление обменом. Недостатки: значительные объемы трафика уменьшают пропускную способность обмена, затруднена локализация отказов

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

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

Номер 1

Рассмотрите способы управления обменом в сети типа "шина". Возможно ли централизованное управление обменом?

Ответ:

(1) возможно, тогда физически сеть имеет "шинную" топологию, но логически – "звезда"

(2) централизованное управление обменом невозможно

(3) возможно при условии, что центральная РС посылает всем остальным, периферийным РС запросы, выясняя желание и разрешая передачу. После окончания передачи РС сообщает "центру", что он закончил, и "центр" продолжает опрос

Номер 2

Рассмотрите способы управления обменом в сети типа "шина". Какими особенностями обладает децентрализованный кодовый приоритетный арбитраж?

Ответ:

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

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

(3) при малой интенсивности обмена все абоненты равноправны, и вероятность конфликтов мала

Номер 3

Рассмотрите способы управления обменом в сети типа "шина". Какими особенностями обладает децентрализованный временной приоритетный арбитраж (метод доступа)?

Ответ:

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

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

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

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

Номер 1

Рассмотрите используемый в сети Ethernet метод  Множественного Доступа с Контролем Несущей и Обнаружением Столкновений (МДКН/ОС). Что собой представляет Контроль Несущей?

Ответ:

(1) во время работы РС постоянно проверяет среду передачи. Передающая среда может быть свободна, т.е. ни одна другая станция не передает данные; занята, т.е. идет передача данных другой станцией

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

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

Номер 2

Рассмотрите используемый в сети Ethernet метод  Множественного Доступа с Контролем Несущей и Обнаружением Столкновений (МДКН/ОС). Что понимается под Множественным Доступом?

Ответ:

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

(2) РС, обнаружив, что передающая среда свободна, запрашивает "центр" на начало обмена

(3) РС, обнаружив, что передающая среда занята, становится в очередь на обмен

Номер 3

Рассмотрите используемый в сети Ethernet метод  Множественного Доступа с Контролем Несущей и Обнаружением Столкновений (МДКН/ОС). В чем суть Обнаружения Столкновений (Коллизий)?

Ответ:

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

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

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

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

Номер 1

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

Ответ:

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

(2) возможность реализации SPMD-технологии

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

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

Номер 1

Представьте схему распределения области интегрирования системы дифференциальных уравнений между РС0 и РC1 локальной сети, если в счете решения в каждом узле участвуют решения в соседних узлах. Размер "сетки" - 6×5. Выделите узлы рассчитываемые, общие, узлы, в которых заданы граничные или начальные условия. f_ij=F(f_i-1,j, f_ij, f_i+1,j)

Ответ:

(1)

(2)

(3)

Номер 2

Представьте схему распределения области интегрирования системы дифференциальных уравнений между РС0 и РC1 локальной сети, если в счете решения в каждом узле участвуют решения в соседних узлах. Размер "сетки" - 6×5. Выделите узлы рассчитываемые, общие, узлы, в которых заданы граничные или начальные условия. f_ij=F(f_i-1,j, f_ij, f_i+1,j, f_i,j+1)

Ответ:

(1)

(2)

(3)

Номер 3

Представьте схему распределения области интегрирования системы дифференциальных уравнений между РС0 и РC1 локальной сети, если в счете решения в каждом узле участвуют решения в соседних узлах. Размер "сетки" - 6×5. Выделите узлы рассчитываемые, общие, узлы, в которых заданы граничные или начальные условия. f_ij=F(f_i-1,j, f_i,j-1, f_i,j+1, f_i+1,j)

Ответ:

(1)

(2)

(3)

Параллельное программирование - тест 3