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

G>Еще раз
G>

M>>Имхо, максимальная производительность будет там, где место параллелизма выбрано с умом.
M>>А для этого нужны оптимальные однопоточные реализации.

G>Связь между предложениями понять не могу.
G>Вполне логично что надо параллелить там где легко параллелится и будет наибольший эффект. Но зачем для этого оптимальные однопоточные реализации?

Потому что место, где происходит распараллеливание, обычно располагается в самом верху. А ниже точки распараллеливания используются оптимальные однопоточные реализации.

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

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

M>Прямо матра какая-то, самогипноз... Зачем параллелить генератор ходов в шахматах

затем что я говорил про свой опыт. отучайтесь говорить за всех

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

К>А может есть примеры, касающиеся не только распределения памяти? С ходу в мою голову приходят только проблемы с изменяемым состоянием для многопроцессорной обработки.
Увы, про это я ничего не знаю. Тут скорее вопрос построения алгоритмов, более пригодных для распараллеливания.
Ну и вообще вопросы high concurrency, типа того же обслуживания веб-реквестов, где собствнно многопроцессорность не шибко важна. А важно умение эффективно распараллеливать ожидание — ну там, как, к примеру, эрланг, который и на одном процессоре бегает кругами вокруг иных многопроцессорных.

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

BZ>затем что я говорил про свой опыт. отучайтесь говорить за всех

Ну так по умолчанию выражение

Понятие эффективности алгоритма сейчас меняется — эффективен тот, кого можно распараллелить. А если нельзя, то будь ты хоть семи пядей во лбу — через пару лет проиграешь

распространяется на все алгоритмы. Что в общем случае не так: есть ряд алгоритмов, которые никто и не будет пытаться параллелить в будущем, но при этом они будут эффективными. Что, собственно говоря, и вызвало протест, и я привел конкретные примеры, когда это неверно.

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

M>Потому что место, где происходит распараллеливание, обычно располагается в самом верху. А ниже точки распараллеливания используются оптимальные однопоточные реализации.

Ну, тут ещё бабка надвое сказала. Есть разные виды параллелизма: мелкозернистый и крупнозернистый, функциональный и по данным.
Например, при рендеринге мы имеем дело с мелкозернистым параллелизмом, под который заточены видеокарты. Да и вообще все алгоритмы, реализуемые на видеокартах распараллеливаются на уровне небольших порций данных и никаких оптимальных однопоточных реализаций там нет.
Аналогичные примеры можно привести и для центральных процессоров: алгоритмы использующие SSE, например. Тот же alpha blending можно распараллелить двумя способами: на низком уровне использовать SSE2, а на высоком раскидать части изображения по ядрам или узлам кластера.

Поэтому выделенное у тебя слово "обычно" не очень то и верно.

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

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

BZ>>затем что я говорил про свой опыт. отучайтесь говорить за всех

M>Ну так по умолчанию выражение

M>

Понятие эффективности алгоритма сейчас меняется — эффективен тот, кого можно распараллелить. А если нельзя, то будь ты хоть семи пядей во лбу — через пару лет проиграешь

M>распространяется на все алгоритмы. Что в общем случае не так: есть ряд алгоритмов, которые никто и не будет пытаться параллелить в будущем, но при этом они будут эффективными. Что, собственно говоря, и вызвало протест, и я привел конкретные примеры, когда это неверно.

А теперь докажи что алгоритм генерации ходов вообще можно распараллелить. Насколько я себе представляю количество ходов = 16 (кол-во фигур) * 8 (максимум клеток в одно направлении) * 4 (направления) = 512, реально раз в 5 меньше. При этом ходы для пешек не такие же, как для ферзя. Поэтому я слабо представляю как такое вообще можно распараллелить.

Параллелится то, что содержит одинаковые операции множества для разных элементов. Например проверка ходов, она выполняется одинаково для любой позиции.

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

BZ>>затем что я говорил про свой опыт. отучайтесь говорить за всех

M>Ну так по умолчанию выражение

M>

Понятие эффективности алгоритма сейчас меняется — эффективен тот, кого можно распараллелить. А если нельзя, то будь ты хоть семи пядей во лбу — через пару лет проиграешь

M>распространяется на все алгоритмы. Что в общем случае не так: есть ряд алгоритмов, которые никто и не будет пытаться параллелить в будущем, но при этом они будут эффективными. Что, собственно говоря, и вызвало протест, и я привел конкретные примеры, когда это неверно.

например, алгоритм поиска хода в шахматах?

ты просто манипулируешь терминами. суть твоего утверждения точно та же, что и у меня — сейчас распараллеливаемость алгоритма становится важнее, чем его однопоточная эффективность. и чем дальше, тем больше оно будет смещаться, поскольку распараллелить алгоритм скажем на 80 ядер — совсем иное дело, чем на 4. я к примеру знаю один алгоритм сжатия который сейчас из-за своей медлительности известен только узким спецам, а на 80 ядрах будет в самый раз

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

BZ>например, алгоритм поиска хода в шахматах?

Я говорил о генерации всех возможных ходов. Проще говоря, у нас есть шахматная позиция, надо сгенерировать список всех допустимых ходов. Ту сотню другую машинных инструкций, которые будут будут выполнятся линейно, нет никакой нужны параллелить даже при наличии 80 ядер. И даже более (насколько мне известно, Топалов во время матча с Анандом, брал в аренду 112-ядерный кластер с рыбой).

BZ>ты просто манипулируешь терминами. суть твоего утверждения точно та же, что и у меня — сейчас распараллеливаемость алгоритма становится важнее, чем его однопоточная эффективность. и чем дальше, тем больше оно будет смещаться, поскольку распараллелить алгоритм скажем на 80 ядер — совсем иное дело, чем на 4. я к примеру знаю один алгоритм сжатия который сейчас из-за своей медлительности известен только узким спецам, а на 80 ядрах будет в самый раз

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

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

N> Аналогичные примеры можно привести и для центральных процессоров: алгоритмы использующие SSE, например. Тот же alpha blending можно распараллелить двумя способами: на низком уровне использовать SSE2, а на высоком раскидать части изображения по ядрам или узлам кластера.
То есть использование на низком уровне SSE2 для тебя не является "однопоточной оптимизацией"? По-моему, ты согласен с точкой зрения, которую пытаешься опровергнуть
N>Поэтому выделенное у тебя слово "обычно" не очень то и верно.

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

G>А теперь докажи что алгоритм генерации ходов вообще можно распараллелить. Насколько я себе представляю количество ходов = 16 (кол-во фигур) * 8 (максимум клеток в одно направлении) * 4 (направления) = 512, реально раз в 5 меньше. При этом ходы для пешек не такие же, как для ферзя. Поэтому я слабо представляю как такое вообще можно распараллелить.

G>Параллелится то, что содержит одинаковые операции множества для разных элементов. Например проверка ходов, она выполняется одинаково для любой позиции.

Да очень просто, там идут последовательные циклы для каждой фигуры, их можно выполнять параллельно. Примерный код есть тут:

void GenerateMoves()
{
  GenerateKnightMoves();
  GenerateBishopMoves();
  GenerateRookMoves();
  GenerateQueenMoves();
  GenerateKingMoves();
  GeneratePawnMoves();
  GenerateCastles();
}

Ничто не мешает создать нам одновременно восемь потоков для каждого вида ходов. Ниже код, который выдран из Crafty, который показывает как оно в жизни:

/* modified 03/23/99 */
/*
 *******************************************************************************
 *                                                                             *
 *   GenerateCaptures() is used to generate capture and pawn promotion moves   *
 *   from the current position.                                                *
 *                                                                             *
 *   the destination square set is the set of squares occupied by opponent     *
 *   pieces, plus the set of squares on the 8th rank that pawns can advance to *
 *   and promote.                                                              *
 *                                                                             *
 *******************************************************************************
 */
int *GenerateCaptures(TREE * RESTRICT tree, int ply, int wtm, int *move)
{
  register BITBOARD target, piecebd, moves;
  register BITBOARD promotions, pcapturesl, pcapturesr;
  register int from, to, temp;

/*
 ************************************************************
 *                                                          *
 *   now, produce knight moves by cycling through the       *
 *   *_knight board to locate a [from] square and then      *
 *   cycling through knight_attacks[] to locate to squares  *
 *   that a knight on [from] attacks.                       *
 *                                                          *
 ************************************************************
 */
  if (wtm) {
    piecebd = WhiteKnights;
    while (piecebd) {
      from = LastOne(piecebd);
      moves = knight_attacks[from] & BlackPieces;
      temp = from + (knight << 12);
      while (moves) {
        to = LastOne(moves);
        *move++ = temp | (to << 6) | ((-PcOnSq(to)) << 15);
        Clear(to, moves);
      }
      Clear(from, piecebd);
    }
/*
 ************************************************************
 *                                                          *
 *   now, produce bishop moves by cycling through the       *
 *   *_bishop board to locate a [from] square and then      *
 *   generate the AttacksFrom() bitmap which supplies the   *
 *   list of valid <to> squares.                            *
 *                                                          *
 ************************************************************
 */
    piecebd = WhiteBishops;
    while (piecebd) {
      from = LastOne(piecebd);
      moves = AttacksBishop(from) & BlackPieces;
      temp = from + (bishop << 12);
      while (moves) {
        to = LastOne(moves);
        *move++ = temp | (to << 6) | ((-PcOnSq(to)) << 15);
        Clear(to, moves);
      }
      Clear(from, piecebd);
    }
/*
 ************************************************************
 *                                                          *
 *   now, produce rook moves by cycling through the         *
 *   *_rook board to locate a [from] square and then        *
 *   generate the AttacksFrom() bitmap which supplies the   *
 *   list of valid <to> squares.                            *
 *                                                          *
 ************************************************************
 */
    piecebd = WhiteRooks;
    while (piecebd) {
      from = LastOne(piecebd);
      moves = AttacksRook(from) & BlackPieces;
      temp = from + (rook << 12);
      while (moves) {
        to = LastOne(moves);
        *move++ = temp | (to << 6) | ((-PcOnSq(to)) << 15);
        Clear(to, moves);
      }
      Clear(from, piecebd);
    }
/*
 ************************************************************
 *                                                          *
 *   now, produce queen moves by cycling through the        *
 *   *_queen board to locate a [from] square and then       *
 *   generate the AttacksFrom() bitmap which supplies the   *
 *   list of valid <to> squares.                            *
 *                                                          *
 ************************************************************
 */
    piecebd = WhiteQueens;
    while (piecebd) {
      from = LastOne(piecebd);
      moves = AttacksQueen(from) & BlackPieces;
      temp = from + (queen << 12);
      while (moves) {
        to = LastOne(moves);
        *move++ = temp | (to << 6) | ((-PcOnSq(to)) << 15);
        Clear(to, moves);
      }
      Clear(from, piecebd);
    } 

................................... (и т. д.)

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

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

G>>А теперь докажи что алгоритм генерации ходов вообще можно распараллелить. Насколько я себе представляю количество ходов = 16 (кол-во фигур) * 8 (максимум клеток в одно направлении) * 4 (направления) = 512, реально раз в 5 меньше. При этом ходы для пешек не такие же, как для ферзя. Поэтому я слабо представляю как такое вообще можно распараллелить.

G>>Параллелится то, что содержит одинаковые операции множества для разных элементов. Например проверка ходов, она выполняется одинаково для любой позиции.

M>Да очень просто, там идут последовательные циклы для каждой фигуры, их можно выполнять параллельно.
Просто выполнять параллельно — это мало, куда складывать результаты, чтобы их потом можно было параллельно обрабатывать?

M>Ничто не мешает создать нам одновременно восемь потоков для каждого вида ходов. Ниже код, который выдран из Crafty, который показывает как оно в жизни:
Думаешь такой код просто распараллелить будет с учетом того что я выше написал?

Думаешь такое распараллеливание чему-то вообще поможет?

Здесь я говорю о многопоточном\многоядерном исполнении. Распараллеливание по данным, например с помощью SSE, (векторизация) помогает гораздо лучше ибо меньше накладных расходов несет.

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

M>>Да очень просто, там идут последовательные циклы для каждой фигуры, их можно выполнять параллельно.
G>Просто выполнять параллельно — это мало, куда складывать результаты, чтобы их потом можно было параллельно обрабатывать?

Да хоть в сокет записать и отправить. Кроме того, есть функциональные языки, которые сами могут определить, что можно выполнять параллельно, а что нельзя. Если им на вход дать такой алгоритм, то они вполне смогут его выполнять параллельно. Так что теоретическая возможность распараллелить алгоритм существует.

G>Думаешь такой код просто распараллелить будет с учетом того что я выше написал?
G>Думаешь такое распараллеливание чему-то вообще поможет?

Я изначально писал, что параллелить такой алгоритм плохая идея.

G>Здесь я говорю о многопоточном\многоядерном исполнении. Распараллеливание по данным, например с помощью SSE, (векторизация) помогает гораздо лучше ибо меньше накладных расходов несет.

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

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

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

M>>>Да очень просто, там идут последовательные циклы для каждой фигуры, их можно выполнять параллельно.
G>>Просто выполнять параллельно — это мало, куда складывать результаты, чтобы их потом можно было параллельно обрабатывать?

M>Да хоть в сокет записать и отправить.
Какой тогда толк от многопроцессорной обработки если выходной канал не позволяет выдавать данные со скоростью генерации данных?

M>Кроме того, есть функциональные языки, которые сами могут определить, что можно выполнять параллельно, а что нельзя. Если им на вход дать такой алгоритм, то они вполне смогут его выполнять параллельно.
Я немного разбираюсь в функциональных языках
а)они автоматически ничего не параллелят б)приведенный выше код вряд ли будет переписан с минимальными изменениями на ФЯ.

M>Так что теоретическая возможность распараллелить алгоритм существует.
А меня не теоретическая возможность интересует, а именно практическая распараллеливаемость таких алгоритмов. Ты утверждаешь что генерацию ходов можно распараллелить — приведи пример параллельной генерации, чтобы её результаты можно было потреблять не менее параллельно. А потом посмотрим дает ли она вообще что-нибудь по сравнению с непараллельной версией (есть ли реальный параллелизм). Учитывая верхнюю границу числа ходов = 500 я в этом сильно сомневаюсь.

G>>Думаешь такой код просто распараллелить будет с учетом того что я выше написал?
G>>Думаешь такое распараллеливание чему-то вообще поможет?
M>Я изначально писал, что параллелить такой алгоритм плохая идея.

Ты написал что его можно параллелить (так чтобы был эффект), а я в этом сильно сомневаюсь.
Вычисление факториала тоже можно "параллелить", запуская в разных потоках рекурсию.

Я не зря привел ссылку на Закон Амдала.
Так указан коэффициент α, который показывает возможность распараллеливания. Если задача по природе имеет большое значение α, то как ни старайся, а распараллелить не удастся. Для тех задач где α меньше наиболее эффективными решениями являются параллельные.

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

M>Я говорил о генерации всех возможных ходов.

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

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

кстати, дальнейший ответ на вопрос Курилки — особенно важное значение приобретают алгоритмы, реализуемые на GPU

BZ>кстати, дальнейший ответ на вопрос Курилки — особенно важное значение приобретают алгоритмы, реализуемые на GPU

Многоядерные GPU уже более-менне давно есть. Что-то движется в плане их использования/алгоритмов и т.п.? Это я так, для общего развития, чтобы в КСВ было чем блеснуть

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

M>Многоядерные GPU уже более-менне давно есть. Что-то движется в плане их использования/алгоритмов и т.п.? Это я так, для общего развития, чтобы в КСВ было чем блеснуть

Ну вот на той же страничке nVidia Cuda Showcase в разделе Filter by Application Type можно глянут в каких примерно областях на данный момент применяют расчеты на GPU.

У AMD/ATI списочек примеров применений сильно перекликается с тем что у nVidia (кликни [ Collapse All ] чтобы быстро окинуть взглядом)