Znalazłem dwa źródła:

http://www.phys.ufl.edu/~coldwell/MultiplePrecision/
fpvsintmult.htm

https://stackoverflow.com/questions/21819682/is-inte
ger-multiplication-really-done-at-the-same-speed-as-
addition-on-a-modern

W jednym piszą, że to jest 20 cykli. W drugim 2-4 cykle (dla liczb 32-bitowych, dla
64-bitowych będzie dwa razy więcej?). Chcę zgrubnie oszacować liczbę cykli
przypadającą na dwa różne algorytmy. Na przykład:

https://prng.di.unimi.it/xoroshiro128plusplus.c

Ale w drugim algorytmie mam mnożenie dwóch uint64_t. I nie wiem ile cykli mniej
więcej przyjąć.

do góry

On 11/05/2023 16:28, o...@g...com wrote:
> Znalazłem dwa źródła:
>
> http://www.phys.ufl.edu/~coldwell/MultiplePrecision/
fpvsintmult.htm
>
> https://stackoverflow.com/questions/21819682/is-inte
ger-multiplication-really-done-at-the-same-speed-as-
addition-on-a-modern
>
> W jednym piszą, że to jest 20 cykli. W drugim 2-4 cykle (dla liczb 32-bitowych, dla
64-bitowych będzie dwa razy więcej?). Chcę zgrubnie oszacować liczbę cykli
przypadającą na dwa różne algorytmy. Na przykład:
>
> https://prng.di.unimi.it/xoroshiro128plusplus.c
>
> Ale w drugim algorytmie mam mnożenie dwóch uint64_t. I nie wiem ile cykli mniej
więcej przyjąć.


Być może to nieoczywiste, ale jaka architektura? Na amd64 mnożenie
liczb 64-bitowych (czyli o wielkości rejestru) będzie zapewne o wiele
szybsze, niż na systemach 32-bitowych, o 16-bitowych nie wspominając.

We floating point może bym nie szedł, bo może być utrata precyzji, no
i trzeba konwertować.

Tak czy siak, pierwszy link z wyszukiwarki zapytanej o "intel
instruction latencies", zakładając, że jednak chodzi o architekturę
x86/x64: www.agner.org/optimize/instruction_tables.pdf.
Wybieram losowo procesor Haskell: MUL: czas: 3-4 cykli,
przepustowość: 0,5-1 instrukcji na cykl.

Najlepiej pobierz dokument i wybierz stosowny procesor.


--
Pozdrawiam/Regards - Bogdan (GNU/Linux & FreeDOS)
Kurs asemblera x86 (DOS, GNU/Linux): http://bogdro.evai.pl
Grupy dyskusyjne o asm: pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
www.Xiph.org www.TorProject.org Soft(EN): http://bogdro.evai.pl/soft

do góry

sobota, 13 maja 2023 o 16:10:00 UTC+2 Bogdan napisał(a):
> On 11/05/2023 16:28, o...@g...com wrote:
> > Znalazłem dwa źródła:
> >
> > http://www.phys.ufl.edu/~coldwell/MultiplePrecision/
fpvsintmult.htm
> >
> > https://stackoverflow.com/questions/21819682/is-inte
ger-multiplication-really-done-at-the-same-speed-as-
addition-on-a-modern
> >
> > W jednym piszą, że to jest 20 cykli. W drugim 2-4 cykle (dla liczb 32-bitowych,
dla 64-bitowych będzie dwa razy więcej?). Chcę zgrubnie oszacować liczbę cykli
przypadającą na dwa różne algorytmy. Na przykład:
> >
> > https://prng.di.unimi.it/xoroshiro128plusplus.c
> >
> > Ale w drugim algorytmie mam mnożenie dwóch uint64_t. I nie wiem ile cykli mniej
więcej przyjąć.
> Być może to nieoczywiste, ale jaka architektura? Na amd64 mnożenie
> liczb 64-bitowych (czyli o wielkości rejestru) będzie zapewne o wiele
> szybsze, niż na systemach 32-bitowych, o 16-bitowych nie wspominając.
>
> We floating point może bym nie szedł, bo może być utrata precyzji, no
> i trzeba konwertować.
>
> Tak czy siak, pierwszy link z wyszukiwarki zapytanej o "intel
> instruction latencies", zakładając, że jednak chodzi o architekturę
> x86/x64: www.agner.org/optimize/instruction_tables.pdf.
> Wybieram losowo procesor Haskell: MUL: czas: 3-4 cykli,
> przepustowość: 0,5-1 instrukcji na cykl.
>
> Najlepiej pobierz dokument i wybierz stosowny procesor.
>
>
> --
> Pozdrawiam/Regards - Bogdan (GNU/Linux & FreeDOS)
> Kurs asemblera x86 (DOS, GNU/Linux): http://bogdro.evai.pl
> Grupy dyskusyjne o asm: pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
> www.Xiph.org www.TorProject.org Soft(EN): http://bogdro.evai.pl/soft

Interesuje mnie głównie architektura 64-bitowa, ale też GPU. Co do tabeli - te 3-4
cykle to jest dla liczb 32-bitowych? Mam zakładać, że dla 64-bitowych będzie to samo,
czy dwa razy więcej?

do góry

Ok, widzę, że dla 64-bitowych liczb to też jest 4-5 cykli.

do góry

Swoją drogą mierzę sobie względną szybkość generatorów PRNG za pomocą:

https://quick-bench.com

Jedyne sensowne zestawienie, po zliczeniu przez mnie ręcznie liczby cykli na operacje
(wynik 22 do 13), które wykonują algorytmy, dostaję, gdy włączam optim=None. Jeżeli
zaś włączę OFast xoroshiro dostaje takiego przyspieszenia, że wyprzedza drugi PRNG,
według tego benchmarku.

W samym xoroshiro liczę operację:

const uint64_t s0 = s[0];

jako jeden cykl, bo następuje wywołanie zmiennej z tablicy. Ale nie jestem pewien,
czy to tak należy szacować.

do góry

On 13/05/2023 19:43, o...@g...com wrote:
> Swoją drogą mierzę sobie względną szybkość generatorów PRNG za pomocą:
>
> https://quick-bench.com
>
> Jedyne sensowne zestawienie, po zliczeniu przez mnie ręcznie liczby cykli na
operacje (wynik 22 do 13), które wykonują algorytmy, dostaję, gdy włączam optim=None.
Jeżeli zaś włączę OFast xoroshiro dostaje takiego przyspieszenia, że wyprzedza drugi
PRNG, według tego benchmarku.
>
> W samym xoroshiro liczę operację:
>
> const uint64_t s0 = s[0];
>
> jako jeden cykl, bo następuje wywołanie zmiennej z tablicy. Ale nie jestem pewien,
czy to tak należy szacować.


To zależy od poziomu optymalizacji.
Bez optymalizacji na samo to wziąłbym 1 cykl na kopię z pamięci do
rejestru i 1 na kopię z rejestru do innej pamięci. Ale wspomniany
dokument podaje np. 3 cykle na kopiowanie do pamięci, więc nawet to
nie jest takie oczywiste.
Z optymalizacją jest szansa, że "s0" siedzi w rejestrze, więc
wystarczy pewnie 1 cykl na załadowanie.
Oczywiście, jeśli s[0] jest ułożone na równym adresie.
Oczywiście, jeśli s[0] siedzi w cache, bo jeśli nie, to w najgorszym
przypadku mogą być może dziesiątki, jak nie setki cykli na pobranie z
głównej pamięci.
I pewnie jeszcze różne inne warunki, więc tabelki tabelkami, ale
najlepiej albo pomierzyć (RDTSC), albo użyć narzędzi mówiących, co ile
potrwa (kiedyś było np. jakieś VTune Analyzer).

--
Pozdrawiam/Regards - Bogdan (GNU/Linux & FreeDOS)
Kurs asemblera x86 (DOS, GNU/Linux): http://bogdro.evai.pl
Grupy dyskusyjne o asm: pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
www.Xiph.org www.TorProject.org Soft(EN): http://bogdro.evai.pl/soft

do góry

niedziela, 14 maja 2023 o 11:28:17 UTC+2 Bogdan napisał(a):
> On 13/05/2023 19:43, o...@g...com wrote:
> > Swoją drogą mierzę sobie względną szybkość generatorów PRNG za pomocą:
> >
> > https://quick-bench.com
> >
> > Jedyne sensowne zestawienie, po zliczeniu przez mnie ręcznie liczby cykli na
operacje (wynik 22 do 13), które wykonują algorytmy, dostaję, gdy włączam optim=None.
Jeżeli zaś włączę OFast xoroshiro dostaje takiego przyspieszenia, że wyprzedza drugi
PRNG, według tego benchmarku.
> >
> > W samym xoroshiro liczę operację:
> >
> > const uint64_t s0 = s[0];
> >
> > jako jeden cykl, bo następuje wywołanie zmiennej z tablicy. Ale nie jestem
pewien, czy to tak należy szacować.
> To zależy od poziomu optymalizacji.
> Bez optymalizacji na samo to wziąłbym 1 cykl na kopię z pamięci do
> rejestru i 1 na kopię z rejestru do innej pamięci. Ale wspomniany
> dokument podaje np. 3 cykle na kopiowanie do pamięci, więc nawet to
> nie jest takie oczywiste.
> Z optymalizacją jest szansa, że "s0" siedzi w rejestrze, więc
> wystarczy pewnie 1 cykl na załadowanie.
> Oczywiście, jeśli s[0] jest ułożone na równym adresie.
> Oczywiście, jeśli s[0] siedzi w cache, bo jeśli nie, to w najgorszym
> przypadku mogą być może dziesiątki, jak nie setki cykli na pobranie z
> głównej pamięci.
> I pewnie jeszcze różne inne warunki, więc tabelki tabelkami, ale
> najlepiej albo pomierzyć (RDTSC), albo użyć narzędzi mówiących, co ile
> potrwa (kiedyś było np. jakieś VTune Analyzer).
> --
> Pozdrawiam/Regards - Bogdan (GNU/Linux & FreeDOS)
> Kurs asemblera x86 (DOS, GNU/Linux): http://bogdro.evai.pl
> Grupy dyskusyjne o asm: pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
> www.Xiph.org www.TorProject.org Soft(EN): http://bogdro.evai.pl/soft

Ok, czyli liczę to raczej prawidłowo. Przykładowe szacunki:

class xoroshiro256plus {

uint64_t s[4] = { 5, 11, 13, 99 };

static uint64_t rotl(const uint64_t x, int k)
{
return (x << k) | (x >> (64 - k));
}

public:
uint64_t next() noexcept
{
const uint64_t result = s[0] + s[3]; // 3 cycles

const uint64_t t = s[1] << 17; // 2 cycles

s[2] ^= s[0]; // 4 cycles
s[3] ^= s[1]; // 4 cycles
s[1] ^= s[2]; // 4 cycles
s[0] ^= s[3]; // 4 cycles

s[2] ^= t; // 2 cycles

s[3] = rotl(s[3], 45); // 6 cycles

return result;
}
};

//Xoroshiro256+ ma 29 cykli.

do góry

niedziela, 14 maja 2023 o 11:28:17 UTC+2 Bogdan napisał(a):
> On 13/05/2023 19:43, o...@g...com wrote:
> > Swoją drogą mierzę sobie względną szybkość generatorów PRNG za pomocą:
> >
> > https://quick-bench.com
> >
> > Jedyne sensowne zestawienie, po zliczeniu przez mnie ręcznie liczby cykli na
operacje (wynik 22 do 13), które wykonują algorytmy, dostaję, gdy włączam optim=None.
Jeżeli zaś włączę OFast xoroshiro dostaje takiego przyspieszenia, że wyprzedza drugi
PRNG, według tego benchmarku.
> >
> > W samym xoroshiro liczę operację:
> >
> > const uint64_t s0 = s[0];
> >
> > jako jeden cykl, bo następuje wywołanie zmiennej z tablicy. Ale nie jestem
pewien, czy to tak należy szacować.
> To zależy od poziomu optymalizacji.
> Bez optymalizacji na samo to wziąłbym 1 cykl na kopię z pamięci do
> rejestru i 1 na kopię z rejestru do innej pamięci.

To jest to samo co niejakie load/store time? Jeżeli w algorytmie mam:

k = k + x;

To dobrze rozumiem, że mam liczyć to jako 4 cykle? Bo jeden cykl na pobranie k, drugi
cykl na pobranie x, trzeci cykl na dodawanie i czwarty cykl na przypisanie wyniku do
k?

do góry

On 14/05/2023 16:00, o...@g...com wrote:
> niedziela, 14 maja 2023 o 11:28:17 UTC+2 Bogdan napisał(a):
>> On 13/05/2023 19:43, o...@g...com wrote:
>>> Swoją drogą mierzę sobie względną szybkość generatorów PRNG za pomocą:
>>>
>>> https://quick-bench.com
>>>
>>> Jedyne sensowne zestawienie, po zliczeniu przez mnie ręcznie liczby cykli na
operacje (wynik 22 do 13), które wykonują algorytmy, dostaję, gdy włączam optim=None.
Jeżeli zaś włączę OFast xoroshiro dostaje takiego przyspieszenia, że wyprzedza drugi
PRNG, według tego benchmarku.
>>>
>>> W samym xoroshiro liczę operację:
>>>
>>> const uint64_t s0 = s[0];
>>>
>>> jako jeden cykl, bo następuje wywołanie zmiennej z tablicy. Ale nie jestem
pewien, czy to tak należy szacować.
>> To zależy od poziomu optymalizacji.
>> Bez optymalizacji na samo to wziąłbym 1 cykl na kopię z pamięci do
>> rejestru i 1 na kopię z rejestru do innej pamięci. Ale wspomniany
>> dokument podaje np. 3 cykle na kopiowanie do pamięci, więc nawet to
>> nie jest takie oczywiste.
>> Z optymalizacją jest szansa, że "s0" siedzi w rejestrze, więc
>> wystarczy pewnie 1 cykl na załadowanie.
>> Oczywiście, jeśli s[0] jest ułożone na równym adresie.
>> Oczywiście, jeśli s[0] siedzi w cache, bo jeśli nie, to w najgorszym
>> przypadku mogą być może dziesiątki, jak nie setki cykli na pobranie z
>> głównej pamięci.
>> I pewnie jeszcze różne inne warunki, więc tabelki tabelkami, ale
>> najlepiej albo pomierzyć (RDTSC), albo użyć narzędzi mówiących, co ile
>> potrwa (kiedyś było np. jakieś VTune Analyzer).
>> --
>> Pozdrawiam/Regards - Bogdan (GNU/Linux & FreeDOS)
>> Kurs asemblera x86 (DOS, GNU/Linux): http://bogdro.evai.pl
>> Grupy dyskusyjne o asm: pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
>> www.Xiph.org www.TorProject.org Soft(EN): http://bogdro.evai.pl/soft
>
> Ok, czyli liczę to raczej prawidłowo. Przykładowe szacunki:
>
> class xoroshiro256plus {
>
> uint64_t s[4] = { 5, 11, 13, 99 };
>
> static uint64_t rotl(const uint64_t x, int k)
> {
> return (x << k) | (x >> (64 - k));
> }
>
> public:
> uint64_t next() noexcept
> {
> const uint64_t result = s[0] + s[3]; // 3 cycles
>
> const uint64_t t = s[1] << 17; // 2 cycles
>
> s[2] ^= s[0]; // 4 cycles
> s[3] ^= s[1]; // 4 cycles
> s[1] ^= s[2]; // 4 cycles
> s[0] ^= s[3]; // 4 cycles
>
> s[2] ^= t; // 2 cycles
>
> s[3] = rotl(s[3], 45); // 6 cycles
>
> return result;
> }
> };
>
> //Xoroshiro256+ ma 29 cykli.


Jak już pisałem - to może zależeć od konkretnego modelu procesora...
Nie tylko od tego, że jest 64-bitowy. I od poziomu optymalizacji.

result = s[0] + s[3];
// jeśli result idzie do pamięci
// mov + mov + add + mov = 2+2+1+3
// mov + add + mov = 2+6+3
// jeśli result idzie do rejestru
// mov + mov + add = 2+2+1
// mov + add = 2+6

const uint64_t t = s[1] << 17;
// jeśli t idzie do pamięci
// mov + shl + mov = 2+1+3
// jeśli t idzie do rejestru
// mov + shl = 2+1

I tak dalej...

--
Pozdrawiam/Regards - Bogdan (GNU/Linux & FreeDOS)
Kurs asemblera x86 (DOS, GNU/Linux): http://bogdro.evai.pl
Grupy dyskusyjne o asm: pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
www.Xiph.org www.TorProject.org Soft(EN): http://bogdro.evai.pl/soft

do góry

On 14/05/2023 16:39, o...@g...com wrote:
> niedziela, 14 maja 2023 o 11:28:17 UTC+2 Bogdan napisał(a):
>> On 13/05/2023 19:43, o...@g...com wrote:
>>> Swoją drogą mierzę sobie względną szybkość generatorów PRNG za pomocą:
>>>
>>> https://quick-bench.com
>>>
>>> Jedyne sensowne zestawienie, po zliczeniu przez mnie ręcznie liczby cykli na
operacje (wynik 22 do 13), które wykonują algorytmy, dostaję, gdy włączam optim=None.
Jeżeli zaś włączę OFast xoroshiro dostaje takiego przyspieszenia, że wyprzedza drugi
PRNG, według tego benchmarku.
>>>
>>> W samym xoroshiro liczę operację:
>>>
>>> const uint64_t s0 = s[0];
>>>
>>> jako jeden cykl, bo następuje wywołanie zmiennej z tablicy. Ale nie jestem
pewien, czy to tak należy szacować.
>> To zależy od poziomu optymalizacji.
>> Bez optymalizacji na samo to wziąłbym 1 cykl na kopię z pamięci do
>> rejestru i 1 na kopię z rejestru do innej pamięci.
>
> To jest to samo co niejakie load/store time? Jeżeli w algorytmie mam:
>
> k = k + x;
>
> To dobrze rozumiem, że mam liczyć to jako 4 cykle? Bo jeden cykl na pobranie k,
drugi cykl na pobranie x, trzeci cykl na dodawanie i czwarty cykl na przypisanie
wyniku do k?


Zależy od konkretnego modelu procesora i od poziomu optymalizacji. I
od rozmiaru zmiennych, i od cache, i od ułożenia w pamięci.
Jeśli 'k' jest 64-bitowe, to:

1) MOV 'k' z pamięci do rejestru = 2, MOV 'x' z pamięci do rejestru =
2, ADD = 1, potem ewentualne czekanie na wynik, potem MOV nowej
wartości do pamięci = 3.

2) MOV 'x' z pamięci do rejestru = 2, ADD 'x' do 'k' w pamięci z
rejestru = 6.

Najlepiej mierzyć fizycznie, co jest najszybsze.
Jak mierzenie jest trudne, to można chociaż zobaczyć, jakie
instrukcje kompilator generuje (z różnymi poziomami optymalizacji i
wyboru architektury docelowej) i dopiero mając je, wziąć tabele czasów
instrukcji i liczyć.

--
Pozdrawiam/Regards - Bogdan (GNU/Linux & FreeDOS)
Kurs asemblera x86 (DOS, GNU/Linux): http://bogdro.evai.pl
Grupy dyskusyjne o asm: pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
www.Xiph.org www.TorProject.org Soft(EN): http://bogdro.evai.pl/soft

do góry