Статья Автор: Деникина Н.В., Деникин А.В.

Вопрос 22. Параллельные вычисления

1 Суть задания

Файл .ods с процессами: ID, длительность (мс), зависимости (через «;»). 0 = независимый.

Независимые стартуют в 1-ю мс. Зависимый — на следующую мс после завершения всех предшественников.

Повышенный · ≈ 7 мин · 1 балл

2 Типы вопросов

Тип 1

⏱ Мин. время

Когда закончится последний?

Тип 2

📊 Одновременность

Длиннейший период ≥N разом.

Тип 3

🔢 Завершились к T

Конец ≤ T.

Тип 4

⚠️ Работают к T

Старт ≤ T, Конец > T.

Тип 5

🏁 Послед. запуск

Макс. Старт.

3 Исходные данные

8 процессов:

📂22.ods
  A B C
  ID Длит. Зависимости
2 1 3 0
3 2 5 0
4 3 2 1
5 4 4 1; 2
6 5 3 3
7 6 6 0
8 7 2 4; 5
9 8 3 6; 7

4 Разбиваем зависимости

1. Выделите столбец C → Данные → Текст по столбцам → разделитель «;»

2. Теперь зависимости в отдельных столбцах C и D.

5 Вносим формулы — по столбцам

Принцип: вводим формулу в строку 2 → копируем вниз на все строки. Всего 4 формулы, 4 столбца:

📊Рабочая таблица · щёлкайте по ячейкам
Шаг:
 
 
—fxЩёлкните по ячейке
  A B C D E F G H
  ID Длит. Зав.1 Зав.2 Кон.з.1 Кон.з.2 Старт Конец

6 Диаграмма Ганта — формулы

Не обязательна для Типов 1, 3–5. Нужна для Типа 2 (подбор сдвигов).

Если строите Ганту — в первой строке временную шкалу 1, 2, 3, … (в ячейках J1, K1, …). Далее одна формула в J2 и копируем на весь диапазон:

📋Формула Ганта (ячейка J2)
=ЕСЛИ(И($G2<=J$1; $H2>=J$1); 1; "")

$G2 — старт ($ фиксирует столбец G при копировании вправо). J$1 — номер мс из шкалы ($ фиксирует строку 1 при копировании вниз).

Логика: если текущая мс (J$1) находится между Стартом и Концом процесса → ставим 1, иначе пусто.

Скопируйте формулу вправо до нужной мс и вниз на все процессы. Добавьте условное форматирование (ячейки = 1 → цветная заливка).

В строке ниже всех процессов — подсчёт одновременных:

📋Формула подсчёта (ячейка J10, если 8 процессов)
=СЧЁТ(J2:J9)

Считает непустые ячейки в столбце — число активных процессов в данную мс. Скопируйте вправо.

📈Ганта нашего примера · щёлкайте по ячейкам
—fxЩёлкните по ячейке Ганта
 

7 Сдвиг для Типа 2 — как меняются формулы

Для задач на максимальную одновременность нужно сдвигать независимые процессы. Добавляем столбец I «Сдвиг» — заполняем нулями, потом подбираем:

⚙️Изменение формул при добавлении сдвига
Столбец Было (без сдвига) Стало (со сдвигом в столбце I)
I — Сдвиг (0 для зависимых, подбираем для независимых)
G (Старт) =МАКС(E2;F2)+1 =МАКС(E2;F2)+1+I2
H (Конец) =G2+B2-1 =G2+B2-1 (не меняется — зависит от G)
🎯Поиск решения

1. В строке подсчёта Ганты добавьте формулу длины непрерывной серии ≥ K процессов.

2. Данные → Поиск решения

3. Целевая: макс. длины серии. Изменяемые: ячейки сдвига (I) для независимых.

4. Ограничения: сдвиг ≥ 0, целое. Метод: Эволюционный.

★ Практика: подберите сдвиги

Задание: Найдите сдвиги для независимых процессов (P1, P2, P6), при которых максимальная непрерывная серия ≥ 3 одновременных процессов будет наибольшей.

Двигайте ползунки — Ганта обновляется в реальном времени. Строка Σ показывает число одновременных процессов, строка ≥3 считает длину серии.

🎛️Сдвиги независимых процессов
Серия ≥3: 0 мс
Ваш лучший: 0 мс
📈Ганта с учётом сдвигов
 

8 Все типы — на нашем примере

📊Выберите тип — таблица подсветит нужные ячейки
 
—fxЩёлкните по ячейке таблицы
  A B C D E F G H
  ID Длит. Зав.1 Зав.2 Кон.з.1 Кон.з.2 Старт Конец
 

9 Проверь себя — другой файл

7 процессов:

📂quiz.ods
  A B C D
  ID Длит. Зав.1 Зав.2
2 1 3 0  
3 2 2 0  
4 3 4 1  
5 4 3 2  
6 5 2 3 4
7 6 5 0  
8 7 1 5 6
 
 
📝Памятка

1. Зависимости → «Текст по столбцам» по «;».

2. E2: =ЕСНД(ВПР(C2;$A:$H;8;0);0) → скопировать F2 и вниз.

3. G2: =МАКС(E2;F2)+1 → вниз. H2: =G2+B2-1 → вниз.

4. Ответ Тип 1: =МАКС(H:H). Тип 2: + столбец Сдвиг + Ганта + Поиск решения.
Печать