#c #c #linux-kernel #parallel-processing #tbb
#c #c #linux-ядро #параллельная обработка #tbb
Вопрос:
Я знаю TBB , что (блоки построения потоков) утверждают, что имеют сложный движок, но с алгоритмической точки зрения:
Если бы у нас была (скажем, в Linux) рабочая очередь, в которой есть N рабочие потоки (потоки POSIX, N это количество ядер) и синхронизированная по мьютексу очередь задач, каждый рабочий поток затем берет задачу из очереди в режиме ожидания, а также некоторые вызовы синхронизации, что еще можно было бы TBB предложить, не считая хорошего C синтаксиса? Я не вижу лучшего алгоритма, чем жадное распределение задач по ядрам.
Комментарии:
1. «Я не вижу лучшего алгоритма, чем жадное распределение задач по ядрам». — обязательно используйте библиотеку
2. Пожалуйста, не могли бы вы набросать несколько алгоритмов, которые могут работать лучше?
3. У TBB, похоже, есть документация. Вы могли бы начать здесь или здесь
Ответ №1:
Как человек, разработавший свой собственный планировщик, который крадет работу, я могу сказать следующее:
- Не пишите свой собственный планировщик (и здесь учитывается рабочая очередь).
- Вы либо сделаете это неэффективно, либо сделаете неправильно.
На самом деле, написать правильный планировщик не так уж сложно. К сожалению, это сложно, если вы хотите сделать это эффективно. Эффективный планировщик эффективно исключает использование блокировок (за исключением, возможно, очень специфических, четко оговоренных ситуаций), а межпоточная связь без блокировок — это сплошная боль.
Как анекдот, я на самом деле реализовал один планировщик, в котором мне, по сути, пришлось копировать существующий алгоритм в код, и мне все равно удалось ввести в код практически любое условие гонки, которое только можно вообразить. Отладка этого кода представляла собой смесь
- написание огромных запутанных тестовых примеров (просто для выявления случайных сбоев, которые происходили только в < 1% запусков),
- часами напролет просто пялиться на код, пытаясь вычислить ошибку, применяя логику
- отслеживание каждой отдельной строки в отладчике (который при возникновении ошибки вылетел бы без трассировки стека), отслеживание состояния всех переменных во всех потоках вручную, просто чтобы убедиться, что фактическое состояние программы соответствует ожидаемому состоянию
- сокращение кода в несколько раз по существу до нуля и перестройка, закомментирование отдельных строк или пар строк, чтобы увидеть эффект (огромное комбинаторное пространство), и
- натыкаясь на стены, головой вперед.
Комментарии:
1. Я предлагаю вам прислушаться к этой рекомендации. Полностью. Обсуждения нет. На самом деле нет.
2. 1 отличная работа. Я только что посмотрел Google tech talk с Хансом Боемом, который добавил дополнительный вес тому, насколько сложным может быть правильное использование параллелизма (например, он сказал, что долгое время (и, возможно, по сей день) было неясно, действительно ли возможно правильно реализовать Java).).
Ответ №2:
Не зная точной реализации TBB, я не могу сказать, что именно он предлагает, но поскольку вы сказали «что может он предложить»…
Среди прочих,
- Он мог бы предлагать постановку в очередь без блокировки и снятие с очереди вместо одного системного вызова и переключения контекста для каждой задачи. Это сложнее реализовать, чем кажется.
- Кроме того, он мог бы предлагать блокировку рабочих потоков, если очередь пуста. Это, опять же, сложнее реализовать, чем кажется.
- Это может привести к краже работы.
- Он мог бы предлагать назначение задач LIFO потоку таким же образом, как работают порты завершения Windows (повышая эффективность кэша).
- Это может быть без ошибок. Это, опять же, реализовать сложнее, чем вы думаете.