Параллельные вычисления при поиске простых чисел.

[mace]

берем кандидата (нечетного само собой), делим на все известные простые числа, меньшие чем половина кандидата.

А почему не корень кандидата?

[mace]

Зачем вычислять его каждый раз? Достаточно один раз запомнить его в переменной. А квадратный корень очень просто и быстро вычисляется бинарным поиском за логарифмическое время.

[unconnected]

Так и есть, выйгрышь значительный.
Знаца, 16 нитей, мой ноутбук:
умножаем (knownPrime*2<candidate): 58.101
делим (knownPrime<candidate/2): 107.577
корень (knownPrima<sqrt(candidate)): 0.825

на графиках использовалось умножение

[unconnected]

пример кода можно? я на С только лабораторные в институте делал, боевых навыков не имею

а так, сам в шоке, думал где выход из цикла несанкционированный — нет, все честно

[unconnected]

knownPrime<<1 < candidate: 47.925
knownPrime >1: 45.859

[unconnected]

имелось в виду

[unconnected]

имелось в виду:
knowPrime меньше candidate сдвиг в право на 1: 45.859

[xeon]

В C# операции вроде *2, 4, 8… и деление на степени двойки оптимизированы.
В IL-коде еще будут операции умножения, а вот уже в ассемблерном после JIT будут только сдвиги. Однако в результирующем ASM для деления и умножения будет больше mov-ов.

C#
var j = i / 2;
IL:
L_0004: ldloc.0
L_0005: ldc.i4.2
L_0006: div
L_0007: stloc.1
ASM:
0000003f mov eax,dword ptr [rsp+20h]
00000043 cdq
00000044 sub eax,edx
00000046 sar eax,1
00000048 mov dword ptr [rsp+2Ch],eax
0000004c mov eax,dword ptr [rsp+2Ch]
00000050 mov dword ptr [rsp+24h],eax

C#:
var k = i >> 1;
IL:
L_0008: ldloc.0
L_0009: ldc.i4.1
L_000a: shr
L_000b: stloc.2
ASM:
00000054 mov eax,dword ptr [rsp+20h]
00000058 sar eax,1
0000005a mov dword ptr [rsp+28h],eax

[7vies]

Судя по этому коду
00000043 cdq
00000044 sub eax,edx
00000046 sar eax,1
у вас переменная — со знаком, поэтому возникает этот дополнительный код если сравнивать просто со сдвигом.
Но вот этой вот магии мне всё равно не понять:
00000048 mov dword ptr [rsp+2Ch],eax
0000004c mov eax,dword ptr [rsp+2Ch]
00000050 mov dword ptr [rsp+24h],eax
Кагбэ temp = eax; eax = temp; result = eax;

[xeon]

Да, магия странная. Сейчас проверил на Int64 вместо Int32, т.к запускаю у себя под 64-битной ОС. Никуда эти странные mov-ы не исчезли. Можно еще на досуге посмотреть, как JIT от Mono себя ведет в подобной ситуации.

Int64 i = 10;
0000003a mov qword ptr [rsp+20h],0Ah

Int64 j = i / 2;
00000043 mov rax,qword ptr [rsp+20h]
00000048 cqo
0000004a sub rax,rdx
0000004d sar rax,1
00000050 mov qword ptr [rsp+38h],rax
00000055 mov rax,qword ptr [rsp+38h]
0000005a mov qword ptr [rsp+28h],rax

Int64 k = i >> 1;
0000005f mov rax,qword ptr [rsp+20h]
00000064 sar rax,1
00000067 mov qword ptr [rsp+30h],rax

[middle]

Во-первых, если вычислять числа последовательно или почти последовательно (т.е. если количество чисел, обрабатываемых последовательно одним выч. узлом, сильно меньше, чем сами числа), то при переходе от n на n+m (где m сильно меньше n) корень легко пересчитывается: единичка либо прибавляется, либо нет :)

Во-вторых, в качестве альтернативы можно сравнивать p<=sqrt(n), а можно p*p<=n, и тут тоже можно придумать всякие оптимизации… ;)

[middle]

Прошу прощения, неправильно написал. Должно быть «т.е. если разрывы между числами, обрабатываемыми одним выч. узлом, сильно меньше, чем сами числа».

[unconnected]

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

[mace]

Для больших чисел разница будет очень существенной.

[YasonBy]

Не думал, что мой ноутбук может серверную железяку переплюнуть.

Кто-то, Вы или я, неправильно понимает графики. ПО оси абсцисс — время, т.е. «меньше-лучше». Графики Opteron'а в обоих случаях выше других, т.е. при равном количестве нитей, оптерону требуется большее время. Где «переплюв»?

[steck]

ноутбук на коре дуо. Оптерон серверная железка.

[YasonBy]

Виноват, не знал… В таком случае, видимо, это означает (временный) конец холивора AMD vs. Intel…

[savant]

оптерон не n-ядерный похоже был. в параллельных вычислениях это играет свою роль.

[unconnected]

2-x ядерный, это то и удивительно

[YasonBy]

*По оси абсцисс…

[steck]

А сам код не выложите?

[unconnected]

если общественность интересует — выложу, выкладывать быдло код не хочется, а приводить его в порядок просто так — лень

[steck]

я бы погладел.
За былость не боитесь.

[unconnected]

ок. но в начале код в порядок все-таки приведу.

[Yfka]

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

[Yfka]

Сейчас я укажу на недостатки к которым бы серьёзные дядечки придрались обязательно. (В универе пожурили бы и поставили хор., а вот

в исследовательском отделе коммерческой компании во все дырки бы…)

1. Непонятно что именно исследовалось.
В первом абзаце написано «нити»:

в зависимости от количества нитей.

Тогда как в вариантах уже «процессы»:

Берем кандидата на простое число, отдаем его процессу, который его считает.

Берем кандидата,

кормим бездельничающему процессу

Т.е. нити или процессы? (Накладные расходы на создание процесса)
Рекомендация: писать об этом явно и недвусмысленно, всегда показывать исходники тестов.

2. Непонятно что именно исследовалось. И, кажись, сам автор этого не понял.
2.1. Исследовалась ли качество реализации .Net framework в зависимости от архитектуры процессора?
2.2. Исследовалась ли скорость переключения в различных версиях .Net framework? (На висте минимальная версия 3.0, а на сервере какая

стояла?)
Рекомендация: исследовать на одной версии виртуальной машины. (Сначала 3.0, например, потом 3.5)

3. Непонятно что именно исследовалось. Автор этого сам не знает, и отсюда непонятные результаты.

Очень обескуражили результаты на AMD. Не думал, что мой ноутбук может серверную железяку переплюнуть. Может, есть тут

знатоки железа — поделитесь, в чем может быть дело?

А, по-моему, исследовалась как раз реализация механизма переключения

в различных ОС.
В висте и получилось быстрее.
Рекомендация: исследовать на одной версии ОС.
Т.е. всё кроме исследуемого параметра должно быть одинаковым.

Заключение:
Автор — молодец, рекомендую продолжать, но только более вдумчиво.

[unconnected]

За развернутый комментарии спасибо.
исследовалось то, как кол-во нитей или процессов (т.к. нет устоявшегося перевода), которые Thread, влияют на скорость вычисления, если не изменять базовый алгоритм.
ВМ я указал — везде одинаковая .Net 3.5.
Сравнивалось два подхода, т.е. сравнивать нужно функции на первом и втором графике для каждой из машин.
Разные машины приведены в общем-то для расширения кругозора (все равно они в стойках стоят и на праздниках бездельничают)
В любом случае — сравнение не в пользу АМД — серверный процессор от Интела тоже участвовал :)

[eschava]

Thread это уж точно не процесс

[savant]

Thread — это всегда нить. Process обозначается словом «процесс». Путать эти понятия не стоит. Разницу я думаю вы и так знаете :)

[underwater]

Еще бы через CUDA прогнать

[JonyRock]

Темой моей курсовой работы было «Реализация многопоточности в .Net». Хочу выложить на хабр, но не хватает кармы…

[Sannis]

Для персонального блога хватает, а для коллективного вам ещё кто-нибудь подбросит плюс, я уверен :)

[JonyRock]

Спасибо автору за статью, спасибо Вам за карму. Планирую заняться после сессии.

[Gasoid]

------простые числа на питоне--------------
#!/usr/bin/env python
import threading

thr = 100
sim = 10000
s = 3
S = [1,2]
def simple(n) :
    for d in range(2,n) :
        if n%d :
            if d == n-1: S.append(n)
        else : break

while s < sim :
    if threading.activeCount() <= thr:
        threading.Thread(target=simple, name="t%i" % s, args=[s]).start()
        s += 1

print S

выполняется буквально несколько секунд на интеле 4 в debian
рад и удивлен))

[7vies]

Ну, несколько секунд для простых чисел до 10к — это как-то не очень быстро…

[Stebanoid]

def good_prime©:
    """Возвращает список простых чисел, найденный
методом "решето Сундарама" """
    #c=time.clock()
    D=C/2
    B=C/6
    A=set(range(D))
    for i in xrange(1,B+1):
        for j in xrange(i,(D+i)/(1+2*i)+1):
            A.discard(i+j+2*i*j)
    A=[ 2*x+1 for x in A ]
    #print time.clock()-c
    return A

А так? :)

[ptalus]

«Очень» оптимальная программа — много лишних итераций как в главном цикле, так и в функции.
1) в главном цикле можно перебирать только нечетные числа
2) в функции перебирать нечетные, от 3 до n/2 с шагом 2 ( d in range(3, n//2, 2) )

[ptalus]

комментарий к первой программе

[proxor]

Интересно было бы на Erlang посмотреть в такой же ситуации :) Не займетесь?

[middle]

В данном случае выигрыша не будет. Скорее всего, Erlang будет медленнее из-за динамической типизации.

[Halt]

А вот не скажите. Все зависит от реализации. К тому же «динамический язык» не значит «медленный язык». Скажем, меня жутко удивило, что Dolphin Smalltalk считал некоторые тесты (кажется простые числа там тоже были) сопоставимо а то и быстрее альтернатив.

Хотя сами разработчики Dolphin-а говорят (и я с ними согласен) что целочисленные тесты для таких дел это зло и не могут являться критерием скорости языка. В том смысле, что реальные данные появляются в реальных же, боевых задачах, где автоматическая оптимизация кода скажет свое слово.

[middle]

Конечно. Но реализация Erlang пока одна и мы все её знаем :)

[Halt]

Разумеется :) Я всего лишь попытался посмотреть с другой стороны

[dust]

На той же википедии (на заметку)

За нахождение простого числа из более чем 10⁸ десятичных цифр EFF назначила награду в 150000 долларов США.

[Doggy]

Ушел искать :)

[Dimchansky]

Код в студию!

[ExD]

Код не выложили, Parallel Extensions навряд ли юзали, так что ядро вы использовали скорее всего одно. Хотелось бы видеть также результаты после использования NGen'а. Конфигурации серверов не указаны(интересует конкретные процессоры и оперативная память). На другие косяки вам тоже указали. В общем очень скользкий тест, который стоит провести более честно;)