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

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

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

В файле содержится информация о совокупности 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 Файловая система. Поиск в файловой системе. Принципы размещения и именования файлов в долговременной памяти. Шаблоны для описания групп файлов

Тип ответа:

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

Номер: 3133F6

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

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

Ответ: 264

Решение.

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

Начальный момент обозначим 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	20	нет	0	0 + 20 = 20
2	19	нет	0	0 + 19 = 19
3	22	8	max(47) = 47	47 + 22 = 69
4	23	нет	0	0 + 23 = 23
5	24	2	max(19) = 19	19 + 24 = 43
6	18	5; 7; 8; 14	max(43; 69; 47; 136) = 136	136 + 18 = 154
7	26	5	max(43) = 43	43 + 26 = 69
8	27	1	max(20) = 20	20 + 27 = 47
9	31	3; 4	max(69; 23) = 69	69 + 31 = 100
10	29	7	max(69) = 69	69 + 29 = 98
11	32	9	max(100) = 100	100 + 32 = 132
12	31	нет	0	0 + 31 = 31
13	32	11; 15	max(132; 134) = 134	134 + 32 = 166
14	38	10; 12	max(98; 31) = 98	98 + 38 = 136
15	34	9	max(100) = 100	100 + 34 = 134
16	43	13	max(166) = 166	166 + 43 = 209
17	55	14; 16	max(136; 209) = 209	209 + 55 = 264

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

Проверим нижнюю границу цепочкой обязательных зависимостей:
1 → 8 → 3 → 9 → 15 → 13 → 16 → 17.
Эти процессы должны выполняться последовательно, их суммарная длительность равна
20 + 27 + 22 + 31 + 34 + 32 + 43 + 55 = 264 мс.
Быстрее закончить все процессы невозможно. Полная таблица показывает расписание, достигающее этой границы.

Ответ: 264.

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

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

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

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