Извини, что не ответил вовремя. Забыл...
R>Это не возможно, т.к. во-первых, всё равно нужна будет синхронизация при работе с этим кэшем. Ты же защищаешь мьютексом свой кэш, который общий на все потоки. Т.е. возвращаемся туда, откуда вышли.
Начал над этим замечанием думать, и вот что мне не совсем ясно.
Предположим, два процессора строго одновременно пытаются модифицировать одну и ту же ячейку ОП. Для простоты будем считать, что кэша нет вообще. Что будет ?
Насколько я понимаю (поправьте, если я не прав), память в любой момент может изменять только одно значение. Т.е. эти запросы от процессоров как-то сериализуются на памяти (на шине ?) В итоге будет вначале выполнено одно присваивание, а потом второе. Результат, конечно, непредсказуем. Так или нет ? Во всяком случае, об аппаратных мютексах на память я ничего не слышал
Если так, то при наличии кэша ничего не меняется. Процессор A пытается записать в память. Это приведет либо к изменению значения в кэше (если там этот адрес уже был), либо к изгнанию кого-то из кэша и записи нового (если не было). Процессор B делает то же самое. Кэш-память (в моем варианте, то есть одна на все процессоры) сериализует эти запросы, результат непредсказуем, ну и что ? Забота синхронизации хоть на ОП. хоть на кэше — дело софта, а не процессора.
>Во-вторых, кэш *обязан* быть близко к процессору, в этом его первостипенное предназначение. А как разместить общий кэш близко ко всем ядрам — не понятно.
Близко — в чем ? В миллиметрах ? Так вроде скорости света пока что хватает ...
R>>>Что такое "по своей сути" — сложно сказать...
PD>>Что такое компьютер — тоже сложно сказать , но когда мы его видим перед собой, мы сразу понимаем, что это он. Дать определение нераспараллеливаемому алгоритму я так сразу не берусь, но для конкретного алгоритма порой вполне ясно, что распараллелить его можно только с помощью грубой силы. Итерационные алгоритмы, к примеру...
R>А чем "грубая сила" плоха? Взяли матрицу и подели по строкам (по столбцам, по блокам, в шахматном порядке), и рассчитываем параллельно. R>Итерационный — это алгоритм, а в конечном итоге нам всегда надо решить задачу, а не алгоритм. А у задачи может быть несколько алгоритмов решения. Например, есть алгоритмы сортировки, наиболее оптимальные для последовательного вычисления, но при распараллеливании обычно берут немного более плохой с т.з. вычислительной сложности алгоритм, но который зато легко и "естественно" разделяется на независимые подзадачи.
R>Кстати, если интересно, пример *задачи*, которая не поддаётся распараллеливанию (текущими математическими методами) — посчитать: R>(2^(2^t)) (mod n*p) R>где n и p — произвольные большие простые числа, t — произвольное число R>(т.н. MIT LCS35 Time Capsule Crypto-Puzzle)
R>
With best regards
Pavel Dvorkin
Re[6]: Многопоточность сегодня - не от хорошей жизни
>>Во-вторых, кэш *обязан* быть близко к процессору, в этом его первостипенное предназначение. А как разместить общий кэш близко ко всем ядрам — не понятно. PD>Близко — в чем ? В миллиметрах ? Так вроде скорости света пока что хватает ...
Не хватает. Несложный подсчёт показывает что за 1 такт 3-гц процессора свет проходит расстояние в 10 см. Это свет и это в вакууме. В реальных условиях скорость распространения сигналов внутри микросхем на порядок меньше скорости света. Так что даже вынесение кэш памяти на несколько миллиметров от процессора очень существенно влияет на тайминги.
R>Интересна как раз "нижняя половина", которая непосредственно "трогает" данные, а не "верхняя половина", которая просто передаёт указатель.
Что значит "трогает данные"? в современном TCP стеке данные вообще никто не трогает, кроме копирования в буфера AFD при ненулевом значении SO_SNDBUF.
Данные трогает только чип сетевой карты, он же и контрольные суммы считает.
R>Возможно, это как раз даст возможность более правильно направлять прерывания по нужным ядрам. Правда, что конкретно это значит — непонятно. И на уровне TCP соединений, всё равно эта штука не сможет разруливать прерывания от сетевой карты...
Можно будет только привязать карту к одному ядру в плане прерываний. Когда от карты приходит прерывание — про принятый пакет никто ничего не знает, и никто не в силах правильно определить процессор, на который прерывание надо бросить, на основании содержимого пакета.
R>Хороший: ОС сделает всю работу, включая копирование/отправку непосредственно в сетевую карту, на пользовательской нити.
Копировать уже ничего не надо, если SO_SNDBUF в нуле стоит. В этой ситуации send() есть то же самое, что TDI_SEND, а TDI_SEND при правильном состоянии TCP позовет из себя NdisSend и далее MiniportSend.
R>Ты не в курсе, как это происходит в реальности при блокирующем send()?
SO_SNDBUF в виндах реализован (в AFD) вот как:
— есть счетчик числа байт, ныне находящихся внутри TDI транспорта, и еще не переданных.
— перед каждым TDI_SEND счетчик увеличивается, в send completion — уменьшается.
— если этот счетчик меньше значению SO_SNDBUF, то при приходе сверху send IRP аллоцируется временный буфер, копируются туда данные, этот временный буфер уезжает вниз в TDI_SEND со вторым IRPом, а send завершается немедленно. Send completion для TDI_SEND уменьшает счетчик и убивает буфер. Все.
— если же счетчик >= SO_SNDBUF, то тогда никаких временных буферов не делается, и каждый send исполняется как TDI_SEND, не помню только, на этом же IRPе или второй аллоцируется.
TDI_SEND у нас верхний край к TCP, между TCP и AFD. Внутри TCP никакие данные никогда никуда не копируются. Если учесть это в сочетании с тем, что могут потребоваться ретрансмиты — то становится ясно, что TDI_SEND может быть завершен только тогда, когда на эту порцию данных пришли все ACKи (ретрансмиты делаются из буфера в самом же TDI_SEND IRP). Что и делается.
Мы получаем вот что: если поставить SO_SNDBUF в нуль, то каждый send() есть TDI_SEND, и возвращает управление только после того, как придут все ACKи на эту порцию. Это накладывает связанные с производительностью ограничения на то, как можно звать send() при этом, но зато нет ни одного копирования данных от user buffer до DMA сетевой карты.
Здравствуйте, Maxim S. Shatskih, Вы писали:
R>>Интересна как раз "нижняя половина", которая непосредственно "трогает" данные, а не "верхняя половина", которая просто передаёт указатель.
MSS>Что значит "трогает данные"? в современном TCP стеке данные вообще никто не трогает, кроме копирования в буфера AFD при ненулевом значении SO_SNDBUF.
MSS>Данные трогает только чип сетевой карты, он же и контрольные суммы считает.
А если отвлечься от всяких IRP и SNDBUF, мой вопрос вообще имеет смысл?
Сейчас насколько распространена поддержка полного tcp offloading включая подсчёт/проверку контрольной суммы? Я, честно говоря, считал, что сейчас лишь небольшой процент (из не дешёвых) сетевых карт поддерживает полный tcp offloading. А если он сейчас является нормой, и процессор не трогает данные, то может и нет смысла думать, о чём я думаю?
Под "трогать" данные я подразумеваю, полное последовательное чтение данных, в результате которого значительная их часть остаётся в кэше ядра, которое это делало. Отсюда и желание воспользоваться тем, что данные находятся в кэше, размещая их обработку на том же ядре.
R>Сейчас насколько распространена поддержка полного tcp offloading включая подсчёт/проверку контрольной суммы?
Контрольные суммы — это далеко не полный TCP offloading, это как раз его простейшая версия.
R>Я, честно говоря, считал, что сейчас лишь небольшой процент (из не дешёвых) сетевых карт поддерживает полный tcp offloading.
Контрольные суммы умеют считать любые гигабитные чипы, даже интеловская карточка образца 2005 года за 850 рублей
Вот полный оффлоадинг, который есть оффлоадинг стейт-машин — это у нас Chimney, это у нас только появилось в Висте.
R>А если он сейчас является нормой, и процессор не трогает данные, то может и нет смысла думать, о чём я думаю?
Не знаю.
Занимайтесь LoveCraftом, а не WarCraftом!
Re[6]: Многопоточность сегодня - не от хорошей жизни
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, remark, Вы писали:
PD>Извини, что не ответил вовремя. Забыл...
R>>Это не возможно, т.к. во-первых, всё равно нужна будет синхронизация при работе с этим кэшем. Ты же защищаешь мьютексом свой кэш, который общий на все потоки. Т.е. возвращаемся туда, откуда вышли.
PD>Начал над этим замечанием думать, и вот что мне не совсем ясно.
PD>Предположим, два процессора строго одновременно пытаются модифицировать одну и ту же ячейку ОП. Для простоты будем считать, что кэша нет вообще. Что будет ? PD>Насколько я понимаю (поправьте, если я не прав), память в любой момент может изменять только одно значение. Т.е. эти запросы от процессоров как-то сериализуются на памяти (на шине ?) В итоге будет вначале выполнено одно присваивание, а потом второе. Результат, конечно, непредсказуем. Так или нет ? Во всяком случае, об аппаратных мютексах на память я ничего не слышал
Да. Всё правильно. Шина доступа к памяти сериализует все запросы. Т.к. в один момент времени по ней может быть передан только один запрос.
PD>Если так, то при наличии кэша ничего не меняется. Процессор A пытается записать в память. Это приведет либо к изменению значения в кэше (если там этот адрес уже был), либо к изгнанию кого-то из кэша и записи нового (если не было). Процессор B делает то же самое. Кэш-память (в моем варианте, то есть одна на все процессоры) сериализует эти запросы, результат непредсказуем, ну и что ? Забота синхронизации хоть на ОП. хоть на кэше — дело софта, а не процессора.
Ключевые слова — "сериализует" и "синхронизации". Это очень плохие слова для производительности и масштабируемости.
В целом такой подход имеет смысл и место. Кэш третьего уровня зачастую так и делают — один на все процессоры/ядра. В скором будущем можно ожидать появления кэшей третьего уровня, встроенных в массовые процессоры. В них тоже скорее всего будет применяться тот же подход.
Однако с кэшем второго уровня ситуация становится сложнее. Для него уже полная централизация и синхронизация могут быть губительными. Сейчас кэш второго уровня делают либо один на ядро, либо один на два ядра. В принципе в полуэкспериментальных процессорах, типа Tile64, применяют следующий подход. Каждое ядро имеет свой физический кэш второго уровня, но все они объединены в один большой логический кэш, который доступен всем ядрам. Но опять же это не отменяет необходимости в протоколах когерентности кэшей и on-chip network.
Касательно кэша первого уровня нет никаких намёков и желаний объединять их. Кэш первого уровня остаётся полностью приватным для ядра. Благодаря этому он обеспечивает латентность доступа порядка нескольких тактов.
Не упускай из вида так же тот момент, что работу с разделяемыми переменными всё же можно назвать не основной работой для ядра. Основная работа всё же остаётся работа с локальными данными. И именно тут надо обеспечивать максимальную производительность. Разделяемый кэш как раз и даёт эту ассиметрию. Работа с локальными данными быстрее на порядок, но работа с разделяемыми данными становится медленнее.
Если тебе интересна эта тема, то за более детальной можешь обращаться сюда: comp.arch
>>Во-вторых, кэш *обязан* быть близко к процессору, в этом его первостипенное предназначение. А как разместить общий кэш близко ко всем ядрам — не понятно.
PD>Близко — в чем ? В миллиметрах ? Так вроде скорости света пока что хватает ...
Да, в миллиметрах. Как это не странно.
Но так же он обязан быть близко логически. Т.е. он должен быть достаточно сильно интергрирован с ядром, и находиться в его единоличном распоряжении (ну или по крайней мере в распоряжении небольшого числа ядер).
Эти два момента дают возможность кэшу работать на частоте сравнимой с частотой ядра.
Здравствуйте, remark, Вы писали:
R>Да, этим грешит большинство библиотек. R>Хотя вот насколько помню в OCI (Oracle call interface) в самую первую функцию инициализации можно передать указатели на функции аллокации/освобождения памяти. Приятно.
Такие монолитные монстры, как Oracle могут себе это позволить.
Здравствуйте, remark, Вы писали:
R>Естественно могут иметь место и частные случаи. Например, приложение по обработке изображений или CAD/CAM/CAE/CASE. Тут скорее всего имеет смысл эффективно распараллеливать только одну основную функцию, например, обработку изображения, или рассчёт параметров модели (все остальные функции — графический интерфейс, фоновые задачи — по прежнему могут быть реализованы по старым принципам). Тут сейчас ситуация обстоит немного лучше. Тут (и только тут) на помощь могут придти такие средства как OpenMP, RapidMind, Intel TBB, Java Fork/Join и тд.: R>www.openmp.org R>www.rapidmind.com R>osstbb.intel.com R>gee.cs.oswego.edu/dl/papers/fj.pdf
[изначально я запостил это в cpp.applied, но думаю, что место этому здесь]
Что такое Fork/Join. И с чем его едят.
Fork/Join сейчас является одной из самых распространённых методик для построения параллельных алгоритмов. Так же его называют параллельным Divide&Conquer (разделяй и властвуй).
Идея следующая. Большая задача разделяется на несколько меньших. Потом эти ещё деляться на меньшие. И так до тех пор, пока задача не становится тривиальной, тогда она решается последовательным методом. Этот этап называется Fork. Далее [опционально] идёт процесс "свёртки", когда решения маленьких задач объединяются некоторым образом пока не получится решение самой верхней задачи. Этот этап называется Join. Решения всех подзадач (в т.ч. и разбиений на меньшие задачи) происходит параллельно. В принципе для решения некоторых задач этап Join не требуется. Например, для параллельного QuickSort — тут мы просто рекурсивно делим массив на всё меньшие и меньшие диапазоны, пока не дойдём до тривиального случая из 1 элемента. Хотя в некотором смысле Join нужен и тут, т.к. нам всё равно надо дождаться пока не закончится обработка всех подзадач.
Что поглядеть. Не буду ходить очень далеко в прошлое или вдаваться в теорию.
Cilk
Расширение для языка С. Реализовано в виде препроцессора и небольшого ран-тайм. Появилось в первой половине 90-х, активно развивалось до 2000, сейчас находится в стабильной версии. Одна из самых эффективных библиотек для параллельного программирования.
Самый любимый алгоритм, который реализовывают и на котором меряются пиписьками, создатели параллельных систем — рассчёт N-ого числа Фибоначи методом грубой силы. Вот пример на Cilk:
cilk int fib (int n)
{
if (n<2)
return n;
else
{
int x, y;
x = spawn fib (n-1); // fork
y = spawn fib (n-2); // fork
sync; // joinreturn (x+y);
}
}
cilk int main (int argc, char *argv[])
{
int n, result;
n = atoi(argv[1]);
result = spawn fib(n); // fork
sync; // join
printf ("Result: %d\n", result);
return 0;
}
Собственно Fork/Join схема — это единственная схема, возможная в Cilk. Т.е. авторы сделали ставку исключительно на эту модель.
Сейчас на основе Cilk разработан JCilk (соотв. для Java) и Cilk++ (для С++). JCilk
Java Fork/Join Framework
Разработана Doug Lea (который сделал dlmalloc). АФАИК Является пропоузалом для включения в спецификацию Ява (возможно уже включён — не слежу). Единственный вид параллелизма — тоже только Fork/Join.
class Fib extends FJTask {
static final int threshold = 13;
volatile int number; // arg/result
Fib(int n) { number = n; }
int getAnswer() {
if (!isDone())
throw new IllegalStateException();
return number;
}
public void run() {
int n = number;
if (n <= threshold) // granularity ctl
number = seqFib(n);
else {
Fib f1 = new Fib(n − 1); // fork
Fib f2 = new Fib(n − 2); // fork
coInvoke(f1, f2);
number = f1.number + f2.number; // join
}
}
public static void main(String[] args) {
try {
int groupSize = 2; // for example
FJTaskRunnerGroup group =
new FJTaskRunnerGroup(groupSize);
Fib f = new Fib(35); // for example
group.invoke(f);
int result = f.getAnswer();
System.out.println("Answer: " + result);
}
catch (InterruptedException ex) {}
}
int seqFib(int n) {
if (n <= 1) return n;
else return seqFib(n−1) + seqFib(n−2);
}
}
Task Parallel Library (Parallel Extensions to .NET)
Это соотв. параллельные расширения для .NET. Тут уже возможена не только Fork/Join схема, но параллельность по данным и общая параллельность по задачам.
К сожалению примера Фибаначи не прилагается, но выглядел бы он примерно так же. Вот коротенький пример:
override int Sum()
{
if (depth < 10) return SeqSum();
Task<int> l = new Task<int>( left.Sum ); // forkint r = right.Sum();
return (r + l.Value); // join
}
Intel Threading Building Blocks
Опять библиотека для С++. Опен сорц. Так же как и Task Parallel Library помимо Fork/Join так же предоставляет параллельность по данным и общая параллельность по задачам.
Вот пример суммирования значений в дереве с помощью Fork/Join:
class SimpleSumTask: public tbb::task {
Value* const sum;
TreeNode* root;
public:
SimpleSumTask( TreeNode* root_, Value* sum_ ) : root(root_), sum(sum_) {}
task* execute() {
if( root->node_count<1000 ) { // trivial case
*sum = SerialSumTree(root);
} else {
Value x, y;
int count = 1;
tbb::task_list list;
if( root->left ) {
++count;
list.push_back( *new( allocate_child() ) SimpleSumTask(root->left,&x) );
}
if( root->right ) {
++count;
list.push_back( *new( allocate_child() ) SimpleSumTask(root->right,&y) );
}
// Argument to set_ref_count is one more than size of the list,
// because spawn_and_wait_for_all expects an augmented ref_count.
set_ref_count(count);
spawn_and_wait_for_all(list); // fork&join
*sum = root->value;
if( root->left ) *sum += x;
if( root->right ) *sum += y;
}
return NULL;
}
};
Value SimpleParallelSumTree( TreeNode* root ) {
Value sum;
SimpleSumTask& a = *new(tbb::task::allocate_root()) SimpleSumTask(root,&sum);
tbb::task::spawn_root_and_wait(a); // fork&joinreturn sum;
}
Несмотря на то, что Task Parallel Library и Intel Threading Building Blocks предоставляют так же возможность создания алгоритмов с параллелизмом по данным и с общим параллелизмом по задачам, фактически это просто надстройки над Fork/Join. Параллелизм по данным реализуется как одноразовый неявный Fork нескольких подзадач и потом неявный Join. Параллельность по задачам — это просто Fork без Join.
Надеюсь вопросов, что такое Fork/Join больше не осталось
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, remark, Вы писали:
R>>Cilk R>>Java Fork/Join Framework R>>Task Parallel Library (Parallel Extensions to .NET) R>>Intel Threading Building Blocks
E>Складывается впечатление, что JoCaml из этой же оперы.
Вообще, ты знаешь, у меня складывается впечатление, что есть 2 разные вещи. Первая — то, что я назвал Fork/Join. Вторая — Join-calculus.
Первая — это Cilk и все его последователи. Что формально он из себя представляет хорошо описал Doug Lea:
...problems are solved by
(recursively) splitting them into subtasks that are solved in
parallel, waiting for them to complete, and then composing
results.
...
Fork/join algorithms are parallel versions of familiar divide−
and−conquer algorithms, taking the typical form:
Result solve(Problem problem) {
if (problem is small)
directly solve problem
else {
split problem into independent parts
fork new subtasks to solve each part
join all subtasks
compose result from subresults
}
}
Вторая — это "Си Омега", Jo&Caml и иже с ними.
Проблема в том, что я, как инженер, очень туго понимаю такие вещи: http://moscova.inria.fr/~maranget/papers/pat/pat002.html
Возможно они говоят о и том же, я просто не могу понять о чём они вообще говорят. Но что-то мне подсказывает, что это немного другое.
Что то в таком духе. Описываем функцию. Описываем для неё условия "срабатывания" (т.е. когда она должна быть вызвана). Условия записываются в виде набора сообщений, которые должны поступить, сообщения можно объединять по "и", по "или", по "вслед за", по "перед" и т.д. Когда приходит заданная "последовательность" сообщений автоматически вызывается функция, в которую передаются пришедшие сообщения.
Т.е. первый вариант — это параллельный divide-and-conquer, второй — параллельный pattern-matching.
Первый — больше подходит для описания вычислительных алгоритмов. Второй — для описания асинхронных распределенных систем.
У меня пока складывается такое впечатление. Присутствие слова "Join" и там и там, конечно, немного путает...
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, AndrewVK, Вы писали:
ZEN>>>Но всё это костыли. Если всё рабочее окружение отправить в своп, а при загрузке компьютера оотуда всё доставать в оперативку... AVK>>В Windows это называется hibernate. К сожалению, при современных объемах оперативки и скоростях винтов это не очень быстро. CC>На 3 гб и обычном SATA2 венике hibernate занимает секунд 5
600 МБ/сек CC>ВСЯ память будет записана только если она ВСЯ занята. CC>Обычно пишется только реально занятые участки минус кэш
Здравствуйте, VEAPUK, Вы писали:
CC>>На 3 гб и обычном SATA2 венике hibernate занимает секунд 5 VEA>600 МБ/сек
Читаем внимательно: CC>>ВСЯ память будет записана только если она ВСЯ занята. CC>>Обычно пишется только реально занятые участки минус кэш
Все 3 гига будут записаны только если они все заняты
Поэтому в большинстве случаев получается быстрее
Здравствуйте, CreatorCray, Вы писали:
CC>На 3 гб и обычном SATA2 венике hibernate занимает секунд 5 CC>ВСЯ память будет записана только если она ВСЯ занята. CC>Обычно пишется только реально занятые участки минус кэш
И еще, вдобавок, сжимают при записи. А дампы памяти сжимаются весьма неплохо.
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, VEAPUK, Вы писали:
CC>>>На 3 гб и обычном SATA2 венике hibernate занимает секунд 5 VEA>>600 МБ/сек CC>Читаем внимательно: CC>CC>>ВСЯ память будет записана только если она ВСЯ занята. CC>CC>>Обычно пишется только реально занятые участки минус кэш CC>Все 3 гига будут записаны только если они все заняты CC>Поэтому в большинстве случаев получается быстрее
Я прекрасно вижу, но реальная скорость записи на блины 150Мб/сек — предел для САТА2 7200, если ошибаюсь, то поправьте.
Итого, в среднем, из 3 гб занято 750 Мб — денег девать не куда?
Здравствуйте, VEAPUK, Вы писали:
VEA>Я прекрасно вижу, но реальная скорость записи на блины 150Мб/сек — предел для САТА2 7200, если ошибаюсь, то поправьте. VEA>Итого, в среднем, из 3 гб занято 750 Мб — денег девать не куда?
Вопрос не понятен.
Впрочем могу предположить...
Ты имел в виду зачем 3 гига если занято на момент хибернейта около 750?
Элементарно!
3 гига нужно для быстрой работы тяжелых прог, которые память хавают как бесплатную. Существенную часть времени эта память не используется на 100%. Но и брался такой объем именно для ускорения тяжелых процессов.
у меня на компе такие процессы запускаются где то на 40-50% активного времени. Т.е. запустили — отработало — закрыли. Отрабатывать должно достаточно быстро не теряя время на своппинг.
В хибернейт рабочий комп я выпихиваю обычно с открытыми MSVC и проч девелоперскими тулами. которые хавают уже не так много + там Janus, Maxthon с кучкой открытых страниц и т.п.
Так что обычная ситуация.
естественно сервера, на которых крутятся подобные прожорливые проги (живой пример: Sharepoint2007 + MSSQL2005 — 3 гига им схавать это как семечки, даже тесновато бывает) вообще почти никогда в хибернейт не уходят — у них режим работы 24/7
в дополнение: еще к тому же все замапленные секции (например образы EXE и DLL) тоже не будут писаться в хиберфайл
пишется грубо говоря "working set" и "private bytes" процессов.
Правило 1.
Думайте параллельно. Решение всех проблем ищите в параллелизме. Обретите понимание того, где действительно есть параллелизм и организуйте свое мышление таким образом, что бы смогли без труда выявить такие фрагменты системы. Прежде чем использовать другие приемы и реализации, склоняйтесь к максимально эффективному решению, основанному на параллельном видении проблемы. Учитесь «думать параллельно».
Правило 2.
Программируйте, используя абстракции. При написании исходного кода сфокусируйтесь на параллельности выполнения процессов, но избегайте непосредственного управления потоками или ядрами процессора. Такие библиотеки, как OpenMP и Intel Threading Building Blocks это все примеры использования абстракций. Не используйте объекты потоков напрямую (pthreads, Windows Threads, Boost threads и пр.) Потоки и MPI это механизмы параллелизма языков программирования. Они предлагают максимум гибкости, однако требуют чрезвычайно много времени для написания, отладки и поддержания. Ваше внимание должно быть сосредоточено на более высоком уровне видения решаемой проблемы, чем уровень управления ядрами и потоками.
Правило 3.
Программируйте в терминах задач, а не потоков вычисления. Оставьте вопрос привязывания задач к потокам или ядрам процессоров как отдельную изолированную операцию в вашей программе, абстрагируя механизм управления вычислительными потоками. Создавайте максимально обособленные реализации решаемых в вашей программе задач, которые потенциально могут автоматически выполняться на различных ядрах процессора (как, к примеру, цикл OpenMP). В процессе формулирования реализуемых в программе отдельных подзадач, создавайте их ровно столько, сколько вам действительно нужно, избегая, разумеется, избыточного разделения.
Правило 4.
Проектируйте вашу систему таким образом, чтобы была возможность не использовать параллелизм вовсе. Для того, что бы проще выполнять отладку, создавайте программу, которую можно было бы запустить без параллельного выполнения задач. В таком случае у вас будет возможность при отладке программы сначала запустить ее с параллельными вычислениями, а затем без таковых и проверить результаты обоих запусков на наличие ошибок и слабых мест. Отладка отдельных частей программы проще, когда в ней нет параллельно работающих фрагментов. Это связано с тем, что основная масса существующих инструментов отладки в большей степени не ориентированы на работу с многопоточным кодом. Когда вам известно, что проблемы возникают только в том случае, когда части системы выполняются параллельно, то наверняка выявить причину этого вам будет проще. Если проигнорировать данное правило и не предусмотреть возможности работы программы в однопоточном режиме, вы можете потратить очень много вермени на выявление причины существующих в программе ошибок. После этого у вас наверняка появится желание добавить в программу возможность ее выполнения в однопоточном режиме, но это уже не принесет такой эффективности, как если бы такая возможность присутствовала изначально. Вам просто необходимо избегать создание параллельных программ, которые для работы обязательно требуют параллельности выполнения. MPI программы часто нарушают это правило, что отчасти является причиной того, что подобные программы сложно отладить.
Правило 5.
Избегайте использования блокировок (lock). Просто скажите блокировкам «нет». Блокировки замедляют программы, снижают их масштабируемость и являются источниками ошибок в параллельном программировании. Делайте неявную синхронизацию решения для вашей программы. Когда вам все-таки требуется явная синхронизация, используйте атомарные операции. Используйте блокировки только как последнее средство. Тщательно спроектируйте вашу систему таким образом, что бы использование блокировок в вашей программе не понадобилось.
Правило 6.
Используйте средства и библиотеки, предназначенные для того, что бы помочь реализации параллельных вычислений. Даже не прикасайтесь к устаревшему инструментарию. Будьте критичны к тому, поддерживает ли данное средство параллелизм и если да, то насколько хорошо. Большинство существующих подобных инструментов достаточно слабы в этом вопросе и не полностью поддерживают параллельные процессы. Ищите потокобезопасные библиотеки или же такие, которые спроектированы специально для применения в многопоточной среде.
Правило 7.
Используйте масштабируемые механизмы выделения памяти. Поточные программы требуют использования масштабируемых механизмов выделения памяти. Точка. Существует много решений, которые лучше чем malloc(). Использование таких механимов увеличивает скорость работы программы, устраняя узкие места, связанные с перераспределением памяти и способствуют лучшему использованию системного кеша.
Правило 8.
Проектируйте масштабируемость программы с учетом увеличения нагрузки. Со временем количество выполняемой вашей программой работы, возможно, потребуется увеличить. Учтите это на этапе проектирования. Уделите большое внимание вопросам масшабируемости еще на начальном этапе, и ваша программа сможет делать больше работы при увеличении числа ядер процессора. Каждый год мы вынуждаем компьютеры делать все больше и больше работы. Затратив больше времени вопросам масштабируемости на начальном этапе, вы получите огромную выгоду при возрастании нагрузок в будущем.
В вот ещё один вариант "8-ми правил" от Клея Брешерса (тоже из Интел): 8 Simple Rules for Designing Threaded Applications
Немного более развёрнуто и детально. Частично советы пересекаются, что и логично.
Здравствуйте, remark, Вы писали:
R>Да, было такое в DDJ в прошлом сентябре: R>http://www.ddj.com/hpc-high-performance-computing/201804248 R>Статья, конечно, больше в стиле вопросов, нежели ответов. Т.к. после каждого пункта хочется спросить "А как?"
Особенно хочется спросить, "А как?" на совет
Avoid using locks. Simply say "no" to locks. Locks slow programs, reduce their scalability, and are the source of bugs in parallel programs
"For every complex problem, there is a solution that is simple, neat,
and wrong."
Прошу прощения за подъем старой темы, но наткнулся на интересный пост одного из разработчиков JRuby. В нем описывается, как на небольшом бенчмарке обнаружилось, что приложение с двумя нитями на Java 5 работает значительно быстрее, чем оно же на Java 6. Проявляется это на двухядерном процессоре из-за эффекта "Cache Line Ping-Pong":
...Это ведет нас к причине плохой производительности на упомянутом выше бенчмарке. Джон Роуз помог мне с помощью дизассемблирования результирующего нативного кода этого бенчмарка для Java 5 и Java 6. Оказалось, что Java 5 размещает два статических поля в разных quadword-ах (16 байтах), а Java 6 -- в одном quadword-е. Эта оптимизация позволяет лучше использовать кэш, т.к. расположенные сразу одно за другим поля почти наверняка будут разделять одну cache line (eao197: здесь у меня не хватило знаний для подходящего русскоязычного термина). Но это так же имеет и другой эффект.
"Cache line ping-pong" проявляется, когда две нити, работающие с разными кешами, нуждаются в чтении и записи одной и той же области памяти. Поскольку две нити должны видеть изменения друг друга, cache line оказывается занятой переключениями между двумя кешами, что обычно ведет к сбросу кеша или обновлению кеша из основной памяти.
Основная память медленная, помните? Поэтому из-за "cache line ping-pong" добавление нитей в этом бенчмарке в действительности приводит к замедлению...
В качестве выводов автор в очередной раз говорит, что нельзя использовать статические данные в многопоточных программах, так же как плохо вообще разделять какие-либо данные между потоками. Ну это и понятно (не понятно, однако, насколько та же Java приспособлена к другим подходам в многопоточности). Интересен другой вывод:
One man's optimization is another man's deoptimization — Java 6 is significantly faster than Java 5, presumably because of optimizations like this. But every optimization has a tradeoff, and this one caught me by surprise.
Как раз этот-то эффект и заинтересовал меня в упомянутом посте.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>Прошу прощения за подъем старой темы, но наткнулся на интересный пост одного из разработчиков JRuby. В нем описывается, как на небольшом бенчмарке обнаружилось, что приложение с двумя нитями на Java 5 работает значительно быстрее, чем оно же на Java 6. Проявляется это на двухядерном процессоре из-за эффекта "Cache Line Ping-Pong":
[...] E>В качестве выводов автор в очередной раз говорит, что нельзя использовать статические данные в многопоточных программах, так же как плохо вообще разделять какие-либо данные между потоками. Ну это и понятно (не понятно, однако, насколько та же Java приспособлена к другим подходам в многопоточности). Интересен другой вывод: E>
E>One man's optimization is another man's deoptimization — Java 6 is significantly faster than Java 5, presumably because of optimizations like this. But every optimization has a tradeoff, and this one caught me by surprise.
E>Как раз этот-то эффект и заинтересовал меня в упомянутом посте.
Не слушай его, он ламер... по крайней мере, что касается многопоточности
Don't use statics — Gilad Bracha probably said it best in his article "Cutting out Static":
Static variables are bad for for concurrency. Of course, any shared state is bad for concurrency, but static state is one more subtle time bomb that can catch you by surprise.
Не верно. Статические переменные не имеют никакого отношения к делу. За задницу может поймать абсолютно любая переменная, даже переменная самого-самого маленького класса, если не уделять этому вопросу внимания. Значение имеет только то, какие потоки и как используют эту переменную. В приведённом примере, насколько я вижу, статическая переменная используется исключительно, что бы упростить доступ к ней из функции потока. Если бы она была не статическая, а переменная-член класса, и ссылка на этот класс передавалась бы в потоки, это ну ровным счётом ничего бы не изменило.
Значительно большее влияние может иметь, например, неаккуратно размешённая переменная-член producer-consumer очереди, чем статическая переменная центрального класса приложения. Эти вопросы совершенно перпендикулярны.
One man's optimization is another man's deoptimization — Java 6 is significantly faster than Java 5, presumably because of optimizations like this. But every optimization has a tradeoff, and this one caught me by surprise.
Совершенно не верно. Все компиляторы оптимизируют под однопоточное выполнение. Это известно. Это традиционно. Это по-умолчанию.
Видимо они работают с процессорами SUN, что у них кэш линия всего 16 байт. А что будет если мы работаем на процессоре Pentium4, где кэш линия на чтение 128 байт? Компилятор должен размещать каждую переменную в своих 128 байтах, тем самым увеличивая потребление памяти в 32 раза? Верно? Нет, конечно не верно. Компилятор пакует все данные максимально плотно, *пока пользователь явно не укажет иного*.
Фактически в программе изначально была допушена ошибка (я думаю, что в контексте разговора о производительности, законно называть это ошибкой). На одном компиляторе это "работало", на другом перестало работать. Попытка как-то приплести сюда компилятор, и свалить вину на него, это просто ламерство. Никакой ошибки и никакого трейдоффа в компиляторе нет.
Это всё равно что возмущаться, что на одном компиляторе С++ этот код работал, а на другом "плохом" компиляторе неожиданно сломался:
i = i++ + ++i;
И назвать это трейдоффом оптимизируещего компилятора.
Компилятору надо явно сказать, если ты надеешься на какое-то конкретное размещение данных. Например, как я организую размещение данных в С++:
class producer_consumer_fifo_queue
{
//...
// producer data
node* volatile head;
char cacheline_pad [128];
// consumer data
node* tail;
};
Или даже так:
class producer_part_of_fifo_queue
{
//...
node* volatile head;
};
class consumer_part_of_fifo_queue
{
//...
node* tail;
void connect_producer(producer_part_of_fifo_queue& producer);
};
Это — всегда корректное, контролируемое мной размещение данных. Я уверен, что если не первый, то второй вариант точно можно сделать и в Java.
То, что автора это застало врасплох... ну что ж... все мы учимся... в следующий раз не застанет...
2. Don't share state unless you absolutely have to — This is perhaps a lesson we all believe we know, but until you're bitten by something sneaky like this you may not realize the what bad habits you have.
Это, в принципе, верно. Точнее так, это может быть и верно и не верно. В зависимости от того, что вкладывал в эти слова автор, и как мы его поняли.
Я бы выразил это так: всегда явно контролируйте и продумывайте — где, как и какие данные разделяются. Само по себе разделение может быть даже полезным.
Чем отличается одна система из N компонентов, то N раздельных систем? Тем, что одна система всегда должна разделять каким-либо образом какие-то данные внутри себя. Иначе она распадается на N раздельных систем. Чем отличается многопоточная программа от программы, состоящей из нескольких процессов, объединенных сокетами/пайпами/файлами? Тем, что в многопоточной программе можно эффективно разделять данные. Я не говорю, что это разделение всегда само сабой окажется эффективным, скорее даже наоборот, но тем не менее добиться этого можно.
Тут надо рассмотреть 2 типа данных: неизменяемые (или редко-изменяемые данные) и часто изменяемые данные.
Что касается неизменяемых (или редко-изменяемых) данных, то тут мы в шоколаде. Подумай, например, о кэше данных из БД размером в несколько сот МБ. Его разделять не только можно, но и нужно. И такое разделение очень эффективно и с т.з. временной сложности, т.е. никаких дополнительных пенальти по времени. Для редко изменяемых данных необходим какой-то механизм, позволяющий платить только во время изменения, а всё остальное время работать с данными как с неизменяемыми.
С часто-изменяемыми данными сложнее. В принципе, да, лучше минимизировать их разделение. Но сильно мало, всё равно не получится, т.к. в любом случае это будет подсистема аллокации памяти, подсистема контроля времени-жизни объектов, очереди для передачи сообщений, либо разделяемые коллекции данных. А так же такие врожденно центролизованные подсистемы, как, например, логирование. Поэтому тут более правильно было бы сказать, не минимизируйте разделение данных, а грамотно, аккуратно и эффективно организуйте это разделение (после того как Вы убрали заведомо ненужное разделение).
з.ы. cache line обычно передоится как... кэш линия, ну или строка кэша
