КОДЕКС
Парадигмы общения в потоках
Как я могу поговорить с другими моими друзьями по ветке?
Сегодня компьютеры стали быстрее и эффективнее. Один из главных секретов производительности компьютера - многопоточность.
По сути, идея состоит в том, что я могу одновременно выполнять несколько программ (потоков). Просто подумайте об идеальном мире, в котором вы можете смотреть онлайн-шоу, пока заканчиваете свои дела на работе.
Сейчас все отлично, потому что у нас есть потенциал для удвоения производительности или даже больше, но что вы будете делать, если для одной из наших программ требуются некоторые частичные результаты, рассчитанные другой программой?
Ответ заключается в том, что потокам необходимо знать, как общаться между собой. Эффективно. Обычно продолжительность параллельного алгоритма складывается из двух терминов: время вычисления и время связи.
В идеале время вычислений должно быть обратно пропорционально количеству потоков, но параллельная производительность зависит от гранулярности: как работа распределяется между потоками и как они взаимодействуют друг с другом. Я ожидаю, что у каждого потока будет одинаковый объем работы.
Коммуникационные парадигмы
Для многопоточности существует два основных стиля общения. Общая память и Передача сообщений.
Общая память
Все потоки имеют доступ к одной и той же памяти. Они работают с разными фрагментами данных, но могут использовать результаты других, если они им нужны. Выполнение потоков должно быть синхронным, особенно когда для следующего шага вычислений одному потоку нужны данные из другого потока. Вы можете узнать больше о массовой синхронной параллельной системе. Другой проблемой может быть доступ к той же ячейке памяти.
Передача сообщений
В этом случае каждый поток может отправлять и получать сообщения. Они используют очередь, в которой хранят сообщение, пока оно не будет обработано. Если мы хотим получить двунаправленную связь между потоками, рекомендуется использовать две очереди. Длина очереди должна соответствовать рабочей нагрузке.
Пример рабочего баланса
Предположим, у вас есть 100 потоков (T0, T1, T2,…, T99), и мы хотим определить простые числа в диапазоне [1, 100 000]. Как я могу это решить?
Во-первых, я должен попытаться создать функцию, которая должна сообщать мне, является ли число простым или нет.
bool isPrime(int n) {
bool prime = true;
if (n == 0 || n == 1) {
prime = false;
}
else {
for (int i = 2; i <= n / 2; ++i) {
if (n % i == 0) {
prime = false;
break;
}
}
}
return prime;
}
Как мы можем сопоставить числа от 1 до 100 000 нашим 100 потокам?
Каждый поток должен решить блок из 1000 чисел.
Отображение 1: T0 вычисляет числа из [1, 1000], T1 - [1001, 2000] и т. Д.
Отображение 2: мы даем каждому потоку по одному номеру в порядке. В первой итерации числа из [1, 100], во второй итерации [101, 200] и т. Д. Поток T1 вычислит [1, 101, 201,…].
Какое отображение лучше?
Второе сопоставление лучше, потому что все потоки имеют числа из одного и того же диапазона значений, а рабочая нагрузка сбалансирована. В первом случае у T0 меньше дел, числа из [1,1000] и T99 имеют большие числа [90 001, 100 000].
Заключение
Параллельная производительность достигается не только за счет количества потоков, вам необходимо знать свое приложение и найти модель потоковой передачи, которая наилучшим образом соответствует вашим требованиям.
