172 похожих чатов

Здравствуйте. У меня есть задача создания некого предметно-ориентированного фреймворка для инкрементальных

вычислений (условно, это можно отнести к классу задач типа salsa).

Есть набор условно чистых функций, которые вычисляют некоторые значения. В качестве входов функций могут служить выходы других таких же функций. Зависимости между функциями образуют DAG (циклические зависимости считаются ошибкой). Граф зависимостей определяется в процессе выполнения функции, то есть динамически. Если функция обращается к значению выхода другой функции, эта функция становится зависимой от той.

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

Вычисления, очевидно, имеет смысл распараллеливать, особенно в случае если граф достаточно ветвистый.

Я бы хотел, чтобы процесс вычислений был контролируемым. Чтобы его можно было приостанавливать. Более того, чтобы был приоретизирован пользовательский ввод (чтобы вычисления шли в фоне, когда пользовательского ввода нет).

Ещё отмечу, что речь идёт о вычислениях на одной машине, а не на класетер. Всеми данными владеет один процесс. И пользовательский ввод всегда контролируем (то есть ввод приходит явным образом).

Я совершенно теряюсь в том, как подойти к такой задаче. В частности:

1. Как эффективно организовать доступ к данным такого DAG графа, учитывая, что граф сам по себе единая точка синхронизации?

2. Имеет ли смысл заморачиваться с Rust futures, или для подобной задачи лучше собрать что-то на коленке? Отдельно отмечу, что мне хотелось бы получить решение, не зависящее от рантайма.

3. Может быть какие-нибудь общие рекомендации?

9 ответов

33 просмотра

Думаю для начала есть смысл сделать однопоточный вариант, что бы было видно, что именно можно распараллелить и что будет управлять работой потоков (ставить им задачи).

1. Берешь петграф, NodeId кладешь в хэшмап рядом по нужному тебе ключу, профит 2. Ты не получишь решение без рантайма, вопрос только возьмешь ты существующий или напишешь какой-то свой с нуля. 3. вероятно узлы графа должны не сами что-то вычислять. а только скидываь задачи в очередь на выполнение. а там рантайм может их в сколько угодно потоков резолвить и репортить назад. В таком случае не придется делаь какого-то умного квантования времени - самые приоритетные задачки на текущий момент будут выполняться. если они все по длительности примерно одинаковые, то этого будет достаточно. открытые вопросы: а) что делать с низкоприоритетными узлами которые никогда не вычисляются? Поднимать приоритет со временем? Вопрос б) что делать с приоритетной задачей которая зависит от другой приоритетной задачи? они складываются/умножаются? в) какйо приоритет задачи. от которой зависят. Х других приоритетных задач7

Ilya-Lakhin Автор вопроса
Αλεχ Zhukovsky
1. Берешь петграф, NodeId кладешь в хэшмап рядом п...

> 1. Берешь петграф, NodeId кладешь в хэшмап рядом по нужному тебе ключу, профит Собственно, это наверное для меня сейчас основной вопрос. Складывать просто в хешмап — получим единую точку синхронизации всего процесса параллельных вычислений. Если вычисления каждой отдельной ноды будут короткие, и чаще будут писать в хешмапу, чем читать, это приведёт будет бутылочным горлышком.

Ilya Lakhin
> 1. Берешь петграф, NodeId кладешь в хэшмап рядом...

Ты не должен хотеть часто перестраивать графк

Ilya-Lakhin Автор вопроса
Αλεχ Zhukovsky
зачем тебе писать в хэшмапу что-то

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

Оптимизация динамических графов вычислений? Хм. Похоже тянет на научную работу

Ilya-Lakhin Автор вопроса
red75prime
Оптимизация динамических графов вычислений? Хм. По...

Ну, ещё раз повторю, что я просил дать предварительные рекомендации. Если задача настолько сложная, и нет решений, близких к тому, что мне нужно, я готов пойти по тривиальному пути и сделать условно на коленке без распараллелирования и прочих оптимизаций.

Ilya Lakhin
Ну, ещё раз повторю, что я просил дать предварител...

вообще это единственно верный путь - делаем на коленке, измеряем перфоманс, делаем умную версию, понимаем что она работает медленее, берем наколеночное решение

Похожие вопросы

Обсуждают сегодня

Господа, а что сейчас вообще с рынком труда на делфи происходит? Какова ситуация?
Rꙮman Yankꙮvsky
29
А вообще, что может смущать в самой Julia - бы сказал, что нет единого стандартного подхода по многим моментам, поэтому многое выглядит как "хаки" и произвол. Короче говоря, с...
Viktor G.
2
30500 за редактор? )
Владимир
47
а через ESC-код ?
Alexey Kulakov
29
Гайс, вопрос для разносторонее развитых: читаю стрим с юарта, нада выделять с него фреймы с определенной структурой, если ли чо готовое, или долбаться с ринг буффером? нада у...
Vitaly
9
Чёт не понял, я ж правильной функцией воспользовался чтобы вывести отладочную информацию? но что-то она не ловится
notme
18
У меня есть функция где происходит это: write_bit(buffer, 1); write_bit(buffer, 0); write_bit(buffer, 1); write_bit(buffer, 1); write_bit(buffer, 1); w...
~
14
Добрый день! Скажите пожалуйста, а какие программы вы бы рекомендовали написать для того, чтобы научиться управлять памятью? Можно написать динамический массив, можно связный ...
Филипп
7
Недавно Google Project Zero нашёл багу в SQLite с помощью LLM, о чём достаточно было шумно в определённых интернетах, которые сопровождались рассказами, что скоро всех "ибешни...
Alex Sherbakov
5
длина пакета фиксированная, или меняется?
Okhsunrog
7
Карта сайта