Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Categories:

Велкам ту риал ворлд

У меня тут внезапно вылез real life вариант задачи swizard. Прямо в продакшене.

3 типа исполнительных устройств:
- A: 6 операций A1-A6
- B: одна операция B
- C: одна операция С

3 типа узлов разной стоимости: A, ABC, AC.

Исполнительные устройства независимы. Т.е. на узлах ABC и AC с более чем одним устройством загрузка одного из устройств не влияет на производительность других.

Все устройства исполняют загруженные в них команды параллельно.

Операции занимают случайное время (но со стационарным распределением). Большое количество операций "насыщает" устройство - т.е. загрузка большего количества операций перестаёт увеличивать скорость. Есть феномен "медленных" операций, не насыщающих устройство. Т.е. насыщение, условно, происходит после загрузки 10 быстрых операций или 100 медленных, причём
быстрота или медленность неизвестна до загрузки в операции в устройство. Представьте, например, что устройство B - это кластер, проверяющий зашифрованное число на простоту. Если идут одни чётные - упираемся во внутренний bandwidth устройства, а если одни произведения
двух близких простых сомножителей - упираемся в процессоры. Но т.к.ключ известен только устройству, мы перед загрузкой сами ничего проверить не можем.

Более того, устройство не умеет сообщать внутренние bandwidth и cpu usage, мы можем о них только догадываться, измеряя время. Например, грузим инструкции, засекаем время исполнения каждой. Если результат инструкции, загруженной 30 секунд назад, не получен - помечаем
инструкцию "медленной". Грузим ещё инструкции, пока "кол-во медленных * X + кол-во неизвестных < Y"

Представьте себе, что узлы - это микросхемы. Изготавливаются с повреждениями, но умеют отключать повреждённые участки. Продаются непроверенными. Соответственно, производительность устройств в узлах индивидуальна. Чипы можно купить, измерить и решить выбросить или оставить. Но оставлять только топовые чипы, а остальные выбрасывать - нерентабельно.

Теперь о вычислениях.

На входе у нас неограниченный поток однотипных задач T.

Представьте, что у нас T - это теоремы, а операции - это стратегии, сводящие одни теоремы к другим.

Общий воркфлоу такой:

Приходит теорема, мы скармливаем её стратегии A5. Она может либо сразу ответить, что типа противоречие, или выдать нам список лемм [A5R] ("A5 Result").

Лемма A1R сводится стратегией A2 к набору лемм [A2R]. И так далее.

Некоторые тривиальные стратегии Sx реализованы "софтварно". Они исполняются мгновенно без загрузки в узлы.

Формализуется композицией монад списка и исключений. Я просто списки для простоты буду использовать.

Всю схему тоже заебусь формализовывать, сделаю только hot path, показывающий использование всех устройств, но не всех инструкций:

S1 :: T -> ([S1R1], S1R2)
A5 :: S1R2 -> [A5R]
A1 :: A5R -> [A1R]
B :: A1R -> ()
C :: S1R1 -> [S1R1]

Тут ещё проблема, что имеющиеся у нас леммы нельзя доказывать в произвольном порядке.

Представьте что мы консультанты по строительству, T - это проект дома с адресом, а наша задача - определить, можно ли построить дом или нельзя. Практически всегда можно.

A - это юридический отдел. B - геологи, а C - занимаются коммуникациями.

Заказчик не готов платить за геологические работы, если окажутся проблемы с документами или невозможен подвод канализации.

Заниматься коммуникациями имеет смысл не тогда, когда готовы все документы для коммуникаций, а когда вообще все документы в порядке.

Т.е. каждый отдельный проект проходит последовательно 3 стадии: A -> C -> B.

Проводя аналогию со свизардом, надо параллельно вычислять много выражений. Выражения изначально ... + (... * ...) и по мере форшения аргументов проясняется их структура. Причём форшение само потребляет ресурсы, а не только аппликации. То есть, статический шедулинг невозможен.

И сложения можно начинать делать только тогда, когда все умножения закончились. Даже те, которые не являются зависимостями.

Отделу А надо выбирать между A5 S1R2 и A1 A5R в очереди. Если B загружен, а простаивает А - имеет смысл делать A5. Если наоборот - имеет смысл делать A1. Ещё надо контролировать количество проектов, застрявших на стадии A - т.е. отдавать приоритет доделыванию существующих проектов. При недогрузе B имеет смысл в первую очередь ставить A1 из проектов с почти готовой стадией A, а не рандомно.
Tags: fp, programming
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 22 comments