реши задачу: Кеша заинтересовался распределёнными ...

Разбор задачи

Имеется очередь из 10 000 задач, каждая задача занимает ровно 6 секунд. Задачи выполняются на кластере, состоящем из некоторого набора процессоров. Важная особенность: программа заканчивает работу в тот момент, когда очередь опустела, то есть когда последняя задача была запущена (а не когда она завершилась). Таким образом:

1. Если у нас есть $M$ потоков (thread-ов), то они могут запускать задачи «волнами» каждые 6 секунд:

   • В момент времени $t=0$ запускаются (распределяются) задачи на все $M$ потоков (если задач не меньше $M$).
   • Пока потоки заняты, новых задач запустить нельзя (т.к. поток освободится только через 6 секунд).
   • Следующая «волна» запуска задач произойдёт в момент $t=6$ (когда все потоки освободятся разом), затем в $t=12$, и так далее.

2. Пусть требуется $k$ таких «волн» (шагов по 6 секунд), чтобы распределить все 10 000 задач. Тогда:

   • За каждую волну уходит ровно 6 секунд ожидания (до начала следующей).
   • Первая волна происходит в момент $t=0$.
   • Если после $k$-й волны в очереди задач не осталось, программа завершается сразу (не нужно ждать ещё 6 секунд).
   • Значит, итоговое время: $$T = 6 \times (k - 1),$$ где $k$ — минимальное число волн, чтобы успеть «выдать» все 10 000 задач.

3. За одну волну (когда потоки только что освободились) можно выдать максимум $M$ задач (по одной на каждый поток). Чтобы покрыть все 10 000 задач за $k$ волн, нужно:

   $$k \cdot M \;\ge\; 10\,000.$$

   Минимальное $k$, удовлетворя этому, есть

   $$k = \bigl\lceil \frac{10\,000}{M} \bigr\rceil.$$

   Тогда итоговое время:

   $$T = 6 \,\times\! \bigl(\bigl\lceil \tfrac{10\,000}{M}\bigr\rceil - 1\bigr).$$

Типы процессоров и их «выгода»

У нас есть три типа процессоров с разными характеристиками:

1. A

   • 8 ядер, 2 потока на ядро $\;\Rightarrow\;16$ потоков
   • Стоимость: 500
   • «Выгода» (число потоков на 1 денежную единицу): $16/500 = 0{,}032$.

2. B

   • 16 ядер, 2 потока на ядро $\;\Rightarrow\;32$ потока
   • Стоимость: 700
   • Выгода: $32/700 \approx 0{,}0457$.

3. C

   • 4 ядра, по 1 потоку $\;\Rightarrow\;4$ потока
   • Стоимость: 200
   • Выгода: $4/200 = 0{,}02$.

Наилучшее соотношение «потоки/стоимость» у процессора типа B (примерно 0.0457), затем идёт A, и хуже всего C.

Задача: выбрать некоторое количество процессоров (A, B, C) так, чтобы суммарная стоимость $\le 3000$, а суммарное число потоков $M$ было максимально (это даёт минимальное время $T$).

Поиск оптимальной комбинации

1. Попробуем взять максимум B, так как у них лучшее «потоки/стоимость»:

   • Стоимость одного B = 700.
   • За 3000 мы можем купить максимум $\lfloor 3000 / 700 \rfloor = 4$ штуки (это обойдётся в $4 \times 700 = 2800$).
   • Тогда останется 200 «свободных» денег ($3000 - 2800 = 200$).
   • На 200 можно взять ровно 1 процессор C (т.к. он стоит 200).
   • Итого:
     • $4$ процессора B $\;\Rightarrow\; 4 \times 32 = 128$ потоков
     • $1$ процессор C $\;\Rightarrow\; 4$ потока
     • Общее число потоков: $128 + 4 = 132$
     • Полная стоимость: $2800 + 200 = 3000$.

2. Проверим, не выйдет ли больше потоков, если комбинировать B и A и/или C как-то иначе:

   • Например, $5$ процессоров B стоили бы $5 \times 700 = 3500$ — это больше 3000, не подходит.
   • Другие комбинации приравниваются к тому же бюджету, но обычно дают меньше суммарных потоков, поскольку A и C менее выгодны по отношению к B.
   • Самостоятельно процессор A стоит 500, даёт 16 потоков. Чтобы обогнать комбинацию с B, нам пришлось бы докупать много A, но упираемся в цену.
   • Аналогично с C: он наиболее «дорогой» в пересчёте на потоки (4 потока за 200).

Таким образом, максимум потоков в пределах 3000 денег даёт комбинация:

4 процессора B + 1 процессор C = 132 потока, стоимость ровно 3000.

Вычисление времени

При $M = 132$ потоках нам нужно закрыть 10 000 задач по 6 с:

Тогда число «волн» $k = 76$. Итоговое время:

Ответ

Минимальное возможное время работы программы (при бюджете не более 3000) равно 450 секунд. При этом нужно ровно 3000 денег (дешевле уже не получится набрать столько потоков, чтобы уменьшить время).

450 3000