Про задачку на собеседовании.
(я всё равно могу придумать ещё парочку-троечку, так что от меня не убудет сильно)
Я предупрежу, что я взял задачу из моей предметной области, но мы рассматривали с её помощью способы рассуждений о параллелизации вычислений. Я просто знал о как минимум двух вариантах распараллеливания (разной эффективности) и хотел посмотреть, как много мой визави может достичь.
Задача была про моделирование системы (схемы) методом дискретных событий (discrete event modeling).
Как это выглядит.
У нас есть колесо времени - очередь событий, сортированных по времени. На каждом этапе из колеса выбираются все события, которые должны произойти на данный момент, этакая пачка, или фронт. События представляют собой изменения значений проводов, которые подключены ко входам вентилей. Мы изменяем входы, а потом запускаем на работу все вентили, у которых вход изменился.
Вентили отрабатывают, и если их выходы будут меняться, то они добавляют события в колесо времени. Поскольку у вентилей нет нулевой задержки срабатывания (это просто не физично), то добавлять можно отложенно.
Итак, у нас есть бутылочное горлышко - колесо времени. Оно ответственно за запуск вентилей.
Тем не менее, если у нас часто случается, что в очередной момент времени фронт содержит много событий, которые задействуют много вентилей, то мы можем распараллелить выполнение фронта. Мы раздадим на процессоры сбалансированные блоки вентилей и они выполнят моделирование своих частей и положат в соответствующие подочереди свои части событий.
Это очень простой вариант, надо сказать, и до него додуматься легко. Собственно, мой собеседник додумался до него практически самостоятельно, думая о моделировании, как об обходе вширь графа схемы. Я уверен, что он придумал это сам, так как это неправильный подход к моделированию. ;)
Итак, у нас явно будет некоторое ускорение на многоядерной машине. Но всё ещё остаётся бутылочное горлышко - упорядочение событий мы всё ещё делаем последовательно.
Тут начинает играть знание о предметной области. Но и про это мы тоже поговорили, когда я приводил пример RS-триггера.
Логическое И уменьшает частоту изменений выхода относительно частот изменений входов. Если хотя бы на одном входе 0, то выход не поменяется. Поэтому вероятность перехода в новое состояние на выходе Логического И меньше, чем любая из вероятностей перехода входов.
Это означает, что в схеме весьма вероятны провода, частота изменений которых будет меньше других проводов. Что, если мы разрежем схему по таким проводам? Получится, что обмен информацией между такими частями схемы будет низок, у внутри таких частей - высок. Мы можем моделировать участки схемы, проверяя изменения проводов между участками схемы редко.
В принципе, мы можем вообще выполнять моделирование схемы, считая, что провода между участками не меняются.
Мы будем использовать спекулятивные вычисления.
То есть, мы работаем, работаем, потом, по истечении времени моделирования без проверок, проверяем, изменился ли провод. Если изменился, то мы все согласованно откатываемся на минимальное время изменения любого из проводов и продолжаем моделирование.
Если у нас откаты из-за изменений происходят слишком часто, то надо уменьшить время моделирования без проверок. Если откатов не было - увеличить. Таким образом мы балансируем накладные расходы. Такие вычисления можно производить независимо, и это очень ценно.
Ещё эффективность зависит от разбиения схемы - действительно ли провода между участками изменяют своё состояние достаточно редко. Но это уже отдельная тема - эффективность параллелизации.
Мой собеседник сам додумался до необходимости посмотреть на вероятности изменений выходов. До спекулятивного выполнения не додумался, но придумал ещё один промежуточный способ, в котором процессора отвечали за свои участки, но колесо времени было одно.
Надеюсь, любопытство удовлетворил.
Если кто будет использовать эту задачку в собеседовании, прошу обязательно сказать, что моделируем схемы с логическими вентилями, что моделируем с использованием колеса времени. А то мой будущий коллега сосредоточился на том, что схемы это графы и чуть не упустил важное. Хотя это ему всё равно помогло. ;)
Я предупрежу, что я взял задачу из моей предметной области, но мы рассматривали с её помощью способы рассуждений о параллелизации вычислений. Я просто знал о как минимум двух вариантах распараллеливания (разной эффективности) и хотел посмотреть, как много мой визави может достичь.
Задача была про моделирование системы (схемы) методом дискретных событий (discrete event modeling).
Как это выглядит.
У нас есть колесо времени - очередь событий, сортированных по времени. На каждом этапе из колеса выбираются все события, которые должны произойти на данный момент, этакая пачка, или фронт. События представляют собой изменения значений проводов, которые подключены ко входам вентилей. Мы изменяем входы, а потом запускаем на работу все вентили, у которых вход изменился.
Вентили отрабатывают, и если их выходы будут меняться, то они добавляют события в колесо времени. Поскольку у вентилей нет нулевой задержки срабатывания (это просто не физично), то добавлять можно отложенно.
Итак, у нас есть бутылочное горлышко - колесо времени. Оно ответственно за запуск вентилей.
Тем не менее, если у нас часто случается, что в очередной момент времени фронт содержит много событий, которые задействуют много вентилей, то мы можем распараллелить выполнение фронта. Мы раздадим на процессоры сбалансированные блоки вентилей и они выполнят моделирование своих частей и положат в соответствующие подочереди свои части событий.
Это очень простой вариант, надо сказать, и до него додуматься легко. Собственно, мой собеседник додумался до него практически самостоятельно, думая о моделировании, как об обходе вширь графа схемы. Я уверен, что он придумал это сам, так как это неправильный подход к моделированию. ;)
Итак, у нас явно будет некоторое ускорение на многоядерной машине. Но всё ещё остаётся бутылочное горлышко - упорядочение событий мы всё ещё делаем последовательно.
Тут начинает играть знание о предметной области. Но и про это мы тоже поговорили, когда я приводил пример RS-триггера.
Логическое И уменьшает частоту изменений выхода относительно частот изменений входов. Если хотя бы на одном входе 0, то выход не поменяется. Поэтому вероятность перехода в новое состояние на выходе Логического И меньше, чем любая из вероятностей перехода входов.
Это означает, что в схеме весьма вероятны провода, частота изменений которых будет меньше других проводов. Что, если мы разрежем схему по таким проводам? Получится, что обмен информацией между такими частями схемы будет низок, у внутри таких частей - высок. Мы можем моделировать участки схемы, проверяя изменения проводов между участками схемы редко.
В принципе, мы можем вообще выполнять моделирование схемы, считая, что провода между участками не меняются.
Мы будем использовать спекулятивные вычисления.
То есть, мы работаем, работаем, потом, по истечении времени моделирования без проверок, проверяем, изменился ли провод. Если изменился, то мы все согласованно откатываемся на минимальное время изменения любого из проводов и продолжаем моделирование.
Если у нас откаты из-за изменений происходят слишком часто, то надо уменьшить время моделирования без проверок. Если откатов не было - увеличить. Таким образом мы балансируем накладные расходы. Такие вычисления можно производить независимо, и это очень ценно.
Ещё эффективность зависит от разбиения схемы - действительно ли провода между участками изменяют своё состояние достаточно редко. Но это уже отдельная тема - эффективность параллелизации.
Мой собеседник сам додумался до необходимости посмотреть на вероятности изменений выходов. До спекулятивного выполнения не додумался, но придумал ещё один промежуточный способ, в котором процессора отвечали за свои участки, но колесо времени было одно.
Надеюсь, любопытство удовлетворил.
Если кто будет использовать эту задачку в собеседовании, прошу обязательно сказать, что моделируем схемы с логическими вентилями, что моделируем с использованием колеса времени. А то мой будущий коллега сосредоточился на том, что схемы это графы и чуть не упустил важное. Хотя это ему всё равно помогло. ;)