Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, remark, Вы писали:

R>>кэш-памятью на самой ОП — бессмысленно. ОП — и есть свой кэш.

PD>Я имел в виду, что та кэш-память, которая сейчас у процессора (и у каждого своя, откуда проблемы ее синхронизации), должна быть одной на все процессоры. Аналогично тому, что все потоки процесса иимеют программно-реализованный кэш (к примеру, данных из БД ), а не каждый поток имеет этот кэш.

Это не возможно, т.к. во-первых, всё равно нужна будет синхронизация при работе с этим кэшем. Ты же защищаешь мьютексом свой кэш, который общий на все потоки. Т.е. возвращаемся туда, откуда вышли. Во-вторых, кэш *обязан* быть близко к процессору, в этом его первостипенное предназначение. А как разместить общий кэш близко ко всем ядрам — не понятно.
В принципе, кэш второго уровня зачастую как раз и делают разделяемым между всеми ядрами. Но кэш первого уровня остаётся приватным для ядра.



R>>Что такое "по своей сути" — сложно сказать...

PD>Что такое компьютер — тоже сложно сказать , но когда мы его видим перед собой, мы сразу понимаем, что это он. Дать определение нераспараллеливаемому алгоритму я так сразу не берусь, но для конкретного алгоритма порой вполне ясно, что распараллелить его можно только с помощью грубой силы. Итерационные алгоритмы, к примеру...

А чем "грубая сила" плоха? Взяли матрицу и подели по строкам (по столбцам, по блокам, в шахматном порядке), и рассчитываем параллельно.
Итерационный — это алгоритм, а в конечном итоге нам всегда надо решить задачу, а не алгоритм. А у задачи может быть несколько алгоритмов решения. Например, есть алгоритмы сортировки, наиболее оптимальные для последовательного вычисления, но при распараллеливании обычно берут немного более плохой с т.з. вычислительной сложности алгоритм, но который зато легко и "естественно" разделяется на независимые подзадачи.

Кстати, если интересно, пример *задачи*, которая не поддаётся распараллеливанию (текущими математическими методами) — посчитать:
(2^(2^t)) (mod n*p)
где n и p — произвольные большие простые числа, t — произвольное число
(т.н. MIT LCS35 Time Capsule Crypto-Puzzle)