31 января 2013 г.

Задача с собеседования

...Пусть у нас есть некоторая процедура обработки сообщений. Процедура состоит из двух фаз: P1 и P2. Фазы строго последовательны — P2 не может начаться, пока не закончилась P1. У нас есть датацентр, в датацентре — стойка, в стойке — сервер, в сервере — 2 процессора.

Есть два варианта организации процесса обработки:
Дизайн 1 (тривиальный)
Мы просто задействуем одно-единственное ядро, которое последовательно для каждого сообщения выполняет P1 и P2. Второе ядро курит бамбук.
Дизайн 2
P1 вешаем на ядро 1, P2 на ядро 2, между ними организуем какой-то протокол передачи сообщений.
Вопрос — какой вариант будет быстрее? (== меньше времени на обработку одного сообщения, от начала P1 до конца P2)


...те же грабли, но вид сбоку: теперь нас интересует не скорость, а пропускная способность. У нас есть входящий поток сообщений, которые надо разгребать. Опять же, два варианта:
Дизайн 1 (тривиальный)
Каждое ядро обрабатывает половину входящих сообщений, при этом каждое ядро для доставшихся ему сообщений выполняет обе фазы обработки последовательно.
Дизайн 2
Все сообщения идут сначала на ядро 1, которое выполняет фазу P1, потом пересылаются на ядро 2, которое выполняет для них фазу P2

Вопрос — в каком варианте можно достичь бОльшей пропускной способности? (== количество сообщений, обрабатываемых за единицу времени)


Подсказка: правильно заданный вопрос, как обычно, содержит половину ответа. Правильно заданный вопрос, в данном случае, будет "какой дизайн и при каких условиях даст лучший результат?"

UPD: Я упустил отметить, что по замыслу объемы (сложности) фаз примерно равны. Т.е. среднее время выполнения P1 равно среднему времени выполнения P2.

UPD2: В комментариях уже есть хороший ответ, так что не подглядывайте!

17 комментариев:

  1. В случае 1.2 пока второе ядро делает P2 первое может делать другое P1?

    Или может вопрос только про обработку одного сообщения, а не очереди?

    P.S. В 2.2 предложение не закончено.

    ОтветитьУдалить
    Ответы
    1. В 1.2 первое ядро может начать обрабатывать следующее сообщение, конечно. Но как вам это помогает ускорить обработку конкретного сообщения?

      2.2 поправил, спасибо

      Удалить
    2. В случае очереди сообщений это может влиять на общее и среднее время обработки.

      Для одного конкретного сообщения будет быстрее 1.

      Для очереди:
      Tp1 - время обработки P1
      Tp2 - время обработки P2
      Ts - время пересылки сообщения(задачи)

      При Tp1 + Ts <= Tp2
      второй вариант лучше, потому что среднее время обработки одного сообщения и сумарное время обработки будет *не меньше*

      При Tp1 + Ts > Tp2
      во втором варианте среднее время обработки одного сообщения будет больше.
      сумарное время обработки при Ts < Tp2 когда нибудь в будущем станет меньше чем для первого варианта. (когда именно зависит от конкретных цифр и длины входа)

      Удалить
    3. 1. Я уточнил насчет объема задач P1/P2 -- они примерно равны.

      2. Да, если во "время обработки" включать время ожидании в очереди, то распараллеливание даст эффект. Но это уже мы, по-сути, переходим к пропускной способности -- "среднее время" это и есть 1/throughput. Я же специально обозначил, что меня интересует именно время обработки одного сообщения.

      При каких-то условиях может ли так случиться, что вариант 2 даст _меньшее_ время обработки одного сообщения?

      Удалить
    4. Нет, время обработки одного конкретного сообщения не может быть меньше Tp1 + Tp2, а для 1.2 не может быть меньше Tp1 + Ts + Tp2.

      Удалить
    5. Это вы про математику говорите -- тут конечно чудес не бывает. Я же спрашиваю про инженерию -- у нас чудеса случаются регулярно.

      Удалить
    6. Видимо еще нужно учитывать время переключения между задачами на одном ядре (Tps).
      И тогда, понятно дело, будет зависить от соотножения Tps и Ts.
      Тут могут влиять
      * всякие кеши
      * то, что по каким то причинам одно двухядерная реализация может какие то ресурсы получить в начале и переиспользовать для каждого сообщения, а одноядреной придется получать эти ресурсы в начале каждой задачи.
      * в случае двухядерной реализации, второе ядро может вместо посивного ожидания, готовиться к следующей задаче.

      Удалить
    7. Да, это я и подразумевал.

      Удалить
  2. В 2.1 сообщения делятся ровно по полам(например, в начале) или каждое ядро берет новое сообщение по мере необходимости(например, после завершения оброботки текущего)?

    ОтветитьУдалить
    Ответы
    1. Это не важно. Load balancing имеет смысл рассматривать когда время выполнения одной задачи "гуляет". В данном случае можно считать, что такого нет -- все сообщения обрабатываются одинаковое время.

      Удалить
  3. Меньше время обработки сообщения разве не даст большую пропускную способност?

    ОтветитьУдалить
    Ответы
    1. Между временем обработки одного сообщения, и количеством сообщений, обрабатываемым за единицу времени может быть довольно нетривиальная зависимость. Простейший пример -- если вы чисто последовательную задачу просто запустите на кластере из 1000 машин, то пропускная способность вырастет в 1000 раз, а вот время выполнения одной задачи останется тем же. Буквально в предыдущей статье была другая, более сложная и интересная ситуация из той же оперы.

      Поэтому я специально обозначаю в каждом вопросе какой именно критерий качества меня интересует

      Удалить
  4. В первом варианте пожалуй лучше крутиться на одном ядре. Не надо организовывать дополнительные протоколы/синхронизации, на которые тоже уйдет какое-то время.

    Во втором должно сильно зависеть от объема задач P1 и P2. Если они сильно разные (например, P1 сильно меньше P2), то одно из ядер (в нашем случае выполняющее P1) будет большую часть времени тупо простаивать.

    ОтветитьУдалить
    Ответы
    1. Да, хорошее замечание насчет объема фаз. Внесу уточнение в формулировку, спасибо. Я предполагаю, что P1 == P2, плюс-минус чуточку.

      А может быть такая ситуация, когда, несмотря на накладные расходы синхронизации, двухядерный вариант будет быстрее?

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

      Удалить
  5. Этот комментарий был удален автором.

    ОтветитьУдалить