A8AC39 — Параллельные вычисления: ответ и решение

Впишите правильный ответ.

Рисунок из условия ФИПИ Задание выполняется с использованием прилагаемых файлов.

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены
с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Типовой пример организации данных в файле:

ID процесса B	Время выполнения процесса B (мс)	ID процесса(-ов) A
1	4	0
2	3	0
3	1	1; 2
4	7	3

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

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Скачать файл задания (ODS, ФИПИ)

СВОЙСТВА ЗАДАНИЯ

КЭС:

1.1 Основные тенденции развития компьютерных технологий. Параллельные вычисления. Многопроцессорные системы. Распределённые вычислительные системы и обработка больших данных

1.2 Принципы построения и аппаратные компоненты компьютерных сетей. Сетевые протоколы. Сеть Интернет. Адресация в сети Интернет. Протоколы стека TCP/IP. Система доменных имён. Разделение IP-сети на подсети с помощью масок подсетей

1.3 Файловая система. Поиск в файловой системе. Принципы размещения и именования файлов в долговременной памяти. Шаблоны для описания групп файлов

Тип ответа:

Краткий ответ

Номер: A8AC39

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINFA8AC39

Ответ: 215

Решение.

В приложенной таблице 18 процессов. Первый столбец содержит их идентификаторы, второй — длительности в миллисекундах, третий — идентификаторы всех необходимых предшественников. Ноль в третьем столбце означает отсутствие предшественников. Типовой пример из условия не заменяет данные файла.

Начальный момент обозначим 0. Пусть d(B) — длительность процесса B, S(B) — время его начала, F(B) — время окончания. Процесс занимает промежуток от S(B) включительно до F(B) не включительно. Его результат доступен уже в момент F(B); следующий процесс может начаться в этот же момент.

Для самого раннего допустимого запуска используем правила:
S(B) = 0, если предшественников нет;
S(B) = max(F(A)), где максимум берётся по всем предшественникам A;
F(B) = S(B) + d(B).
Длительности разных предшественников не складываем: они могут работать параллельно. Но ждать требуется завершения каждого, поэтому выбираем самое позднее окончание. Строки вычисляем после их предшественников, даже если в файле они расположены в другом порядке.

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

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

ID	d	Предшественники	S	F = S + d
1	23	нет	0	0 + 23 = 23
2	22	нет	0	0 + 22 = 22
3	20	7	max(71) = 71	71 + 20 = 91
4	25	нет	0	0 + 25 = 25
5	28	2	max(22) = 22	22 + 28 = 50
6	27	5; 7; 8; 14	max(50; 71; 45; 166) = 166	166 + 27 = 193
7	21	5	max(50) = 50	50 + 21 = 71
8	22	1	max(23) = 23	23 + 22 = 45
9	21	3; 4	max(91; 25) = 91	91 + 21 = 112
10	27	7	max(71) = 71	71 + 27 = 98
11	20	9	max(112) = 112	112 + 20 = 132
12	26	нет	0	0 + 26 = 26
13	24	10; 12	max(98; 26) = 98	98 + 24 = 122
14	27	11; 15	max(132; 139) = 139	139 + 27 = 166
15	27	9	max(112) = 112	112 + 27 = 139
16	28	14; 17	max(166; 187) = 187	187 + 28 = 215
17	21	13; 14	max(122; 166) = 166	166 + 21 = 187
18	25	13	max(122) = 122	122 + 25 = 147

Вся система заканчивает работу, когда выполнен последний процесс. Следовательно, T = max(F(B)) = 215 мс.

Проверим нижнюю границу цепочкой обязательных зависимостей:
2 → 5 → 7 → 3 → 9 → 15 → 14 → 17 → 16.
Эти процессы должны выполняться последовательно, их суммарная длительность равна
22 + 28 + 21 + 20 + 21 + 27 + 27 + 21 + 28 = 215 мс.
Быстрее закончить все процессы невозможно. Полная таблица показывает расписание, достигающее этой границы.

Ответ: 215.

Задание EGEINFA8AC39: Параллельные вычисления

Решение задания EGEINFA8AC39

Помочь улучшить сайт

Комментарии к решению