c++ ile asal sayı hesaplanırken donanımlar arası hesaplama süresi farkı.

[ckocagil]

Algoritmayi da yazmazsan oynamam.

Eratosten kalburu - Vikipedi

tr.wikipedia.org

 

[Mikro Step]

Ilk algoritma ile 10 milyona kadar asal sayilari tek cekirdekte 1406 ms de hesaplayan asm kod.
PC'de 30 yildir asm kodlamiyorum guzel bir kod degildir.

function asalmi_asm(n:integer):boolean;
label asal, degil, dongu, cik;
begin
        asm
            mov eax,n
            cmp eax,3
            jle asal
            and al,1
            je  degil

            mov edx, 0
            mov eax, n
            mov ecx, 3
            div ecx
            cmp edx, 0
            je  degil

            mov ebx,n
            mov ecx,5

dongu:      mov eax,ecx
            mul eax
            cmp edx,0
            jne asal
            cmp eax, ebx
            jg  asal

            mov edx, 0
            mov eax, ebx
            div ecx
            cmp edx, 0
            je  degil

            mov edx, 0
            mov eax, ebx
            push ecx
            add ecx, 2
            div ecx
            pop ecx
            cmp edx, 0
            je  degil
            add ecx, 6
            jmp dongu


asal:       or  ebx, 1
            jmp    cik
degil:      and  ebx, 0
cik:
        end;
end;

 

[taydin]

Hmm ilginç birşey gözlemledim benim 8 çekirdek işlemcide. 100 milyon prime hesaplatıyorum, 37 saniyede bitiyor. Sonra 4 tane thread oluşturup her birisini ayrı bir core'da çalıştırıyorum. Süre 9 saniyeye iniyor. Sonra 8 tane thread oluşturup her birisini ayrı bir core'da çalıştırıyorum, süre 8 saniyeye iniyor ... Bu nasıl olur anlamadım.

 

[Mikro Step]

Sayilar buyudukce asal sayi arastirmasi artiyor. Cekirdeklere verilen gorevlerde buyuk sayilarla gorevli cekirdek kan ter icinde kalirken diger cekirdekler islerini bitirip aylaklasiyordur.

Dolayisi ile soyle bir gorev dagilimi yapilabilir. (araliklari salladim)

1. cekirdek 1....90 milyon
2. cekirdek 90 milyon....92 milyon
2. cekirdek 92 milyon....95 milyon
...
...

 

[taydin]

Benim dağılım öyle değil. Her çekirdek farklı bir offset ile başlıyor.

0 çekirdek 0, 8, 16, 24 ...
1 çekirdek 1, 9, 17, 25 ...
2 çekirdek 2, 10, 18, 26 ...
*
*

şeklinde gidiyor. Yük dağılımı da kabaca eşit oluyor.

 

[taydin]

Bu arada şunu da belirteyim, 8 çekirdek, 16 thread var işlemcide. pthread kütüphanesi sadece logical core'dan anlıyor, yani 16 tane core görüyor. Ben de 1, 3, 5, 7, 9, 11, 13, 15 numaralı logical core'larda işlem yaptırıyorum, her birisi ayrı fiziki core da çalışmış oluyor.

 

[Mikro Step]

Peki her bir cekirdegin buldugu asal sayi miktari nedir? Acaba yaklasik esitmidir?

 

[taydin]

zamanın azaldığı 4 core durumunda şöyle

[ta@bonsai ~]$ g++ -O2 -lpthread a.cpp
[ta@bonsai ~]$ ./a.out
number of cores = 16
sayı gir: 100000000
0 count = 0
1 count = 1439970
0 count = 0
3 count = 1440544
0 count = 0
5 count = 1440534
0 count = 0
7 count = 1440406
time 9333 milisaniye
asal adedi = 5761454
[ta@bonsai ~]$

Asal adedi 1 eksik, o loop'un nerede başladığı nerede bittiği ile ilgili, önemli değil bizim için.

4 tane core %100 kullanılıyor

 

[taydin]

8 core için de durum şöyle

[ta@bonsai ~]$ ./a.out
number of cores = 16
sayı gir: 100000000
1 count = 720006
3 count = 720467
5 count = 720275
7 count = 720456
9 count = 719964
11 count = 720077
13 count = 720259
15 count = 719950
time 8478 milisaniye
asal adedi = 5761454
[ta@bonsai ~]$

 

[taydin]

Belki şöyle bir durum olabilir. 8 core %100 yüklenmiş, iş yapıyor, ama belleğe yazarken belki zaman paylaşımı (arbitration) gerekiyor olabilir.

 

[taydin]

Bu da orijinal kodun 100 milyon için performansı. program tek thread olduğu için Linux onu bir core'dan diğerine gezdiriyor

[ta@bonsai ~]$ g++ -O2 b.cpp
[ta@bonsai ~]$ ./a.out
sayı gir: 100000000
Asal sayılar:

İşlem süresi: 37411 milisaniye
sayi adedi: 5761455
[ta@bonsai ~]$

 

[Mehmet.b]

2³² denediniz mi?
Benim PC 16GB, ram yetmiyor.

 

[devreci]

10 milyon tanesi 1500ms kodda bir değişiklik yapınca 980 ms düştü

işlemci i5 3 nesil single core bechmark 1500 muş

 

[devreci]

100 milyona kadar saydırdım hadi yarış

32312 eklentisine bak

Bu da 1 milyara kadar:

32314 eklentisine bak

Algoritma farklı ama haberiniz olsun

işlemci nedir bu sys nedir ? exe var mı deneyeyim.

 

[taydin]

Problemi buldum. Hayret birşey yav. 0, 2, 4, 6, 8 olan core'lar ikinin katı şeklinde gidiyor ve hiç birisi de asal olamayacağı için çabucak iş bitiyor Asıl işi yapan tek sayıları işleyen çekirdekler.

Çift sayıları tamamen gözardı edip tek sayıları paylaştırmak lazım.

 

[taydin]

Tamam şimdi çift sayıları yok sayacak şekilde değiştirdim. Bir de daha çok C odaklı yeniden düzenledim. Şu anda 100 milyon için, 1 core ile 37 saniye çıkıyor, 8 core ile de 4.7 saniye çıkıyor

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>


#define CORES 8

typedef struct
{
    int id;
    int start;
    int limit;
    pthread_t thread;
    int count;

} THREAD_INFO;

static THREAD_INFO tinfo[] =
{
    {
        .id = 0,
        .start = 1,
    },
    {
        .id = 1,
        .start = 3,
    },
    {
        .id = 2,
        .start = 5,
    },
    {
        .id = 3,
        .start = 7,
    },
    {
        .id = 4,
        .start = 9,
    },
    {
        .id = 5,
        .start = 11,
    },
    {
        .id = 6,
        .start = 13,
    },
    {
        .id = 7,
        .start = 15,
    },
    {
        .id = 8,
        .start = 17,
    },
    {
        .id = 9,
        .start = 19,
    },
    {
        .id = 10,
        .start = 21,
    },
    {
        .id = 11,
        .start = 23,
    },
    {
        .id = 12,
        .start = 25,
    },
    {
        .id = 13,
        .start = 27,
    },
    {
        .id = 14,
        .start = 29,
    },
    {
        .id = 15,
        .start = 31,
    },
};


/***********************************************************************
 ***********************************************************************/
bool is_prime(int n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}

/***********************************************************************
 ***********************************************************************/
static unsigned int get_millis(void)
{
    struct timeval tv;
    gettimeofday(&tv, 0);

    return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

/***********************************************************************
 ***********************************************************************/
static void* worker_thread(void* args)
{
    THREAD_INFO* ti = reinterpret_cast<THREAD_INFO*>(args);

    printf("%d enter\n", ti->id);

    cpu_set_t cpuset;
    CPU_ZERO(&cpuset);
    CPU_SET(ti->id, &cpuset);

    pthread_t thread = pthread_self();
    if (pthread_setaffinity_np(thread, sizeof(cpuset), &cpuset) == 0)
    {
        for (int i = ti->start; i <= ti->limit; i += (2 * CORES))
        {
            if (is_prime(i))
            {
                ++ti->count;
            }
        }
    }
    else
    {
        printf("%d pthread_setaffinity_np failed\n", ti->id);
    }

    printf("%d exit\n", ti->id);

    return 0;
}

/***********************************************************************
 ***********************************************************************/
int main()
{
    int limit;

    printf("limit? ");
    if (scanf("%d", &limit) != 1)
    {
        exit(1);
    }

    for (int i = 0; i < CORES; ++i)
    {
        THREAD_INFO* ti = &tinfo[i];

        ti->limit = limit;

        pthread_create(&ti->thread, 0, worker_thread, ti);
    }

    unsigned int start_time = get_millis();

    int prime_count = 0;
    for (int i = 0; i < CORES; ++i)
    {
        THREAD_INFO* ti = &tinfo[i];

        pthread_join(ti->thread, 0);

        printf("%d count = %d\n", ti->id, ti->count);
        prime_count += ti->count;
    }

    unsigned int end_time = get_millis();

    printf("time diff = %u\n", end_time - start_time);

    printf("total prime count = %d\n", prime_count);

    return 0;
}

 

[taydin]

ilk 8 tane core fiziksek core'lara karşılık geliyor.

[ta@bonsai ~]$ g++ -O2 -lpthread a.cpp
[ta@bonsai ~]$ ./a.out
limit? 100000000
0 enter
1 enter
2 enter
4 enter
3 enter
5 enter
6 enter
7 enter
1 exit
4 exit
0 exit
0 count = 720006
1 count = 720467
7 exit
5 exit
3 exit
6 exit
2 exit
2 count = 720275
3 count = 720456
4 count = 719964
5 count = 720077
6 count = 720259
7 count = 719950
time diff = 4756
total prime count = 5761454
[ta@bonsai ~]$

 

[taydin]

Eğer 16 core ile denersem biraz daha bir kazanç elde ediliyor, süre 4.3 saniyeye düşüyor

[ta@bonsai ~]$ g++ -O2 -lpthread a.cpp
[ta@bonsai ~]$ ./a.out
limit? 100000000
0 enter
1 enter
2 enter
3 enter
4 enter
5 enter
6 enter
7 enter
8 enter
9 enter
10 enter
11 enter
12 enter
13 enter
15 enter
14 enter
3 exit
2 exit
6 exit
4 exit
1 exit
10 exit
12 exit
8 exit
14 exit
0 exit
0 count = 360035
1 count = 360315
2 count = 360321
3 count = 360048
4 count = 359902
5 exit
5 count = 360077
6 count = 360259
9 exit
15 exit
11 exit
13 exit
7 exit
7 count = 359962
8 count = 359971
9 count = 360152
10 count = 359954
11 count = 360408
12 count = 360062
13 count = 360000
14 count = 360000
15 count = 359988
time diff = 4339
total prime count = 5761454
[ta@bonsai ~]$

 

[VincentVega]

Eratosten kalburu - Vikipedi

tr.wikipedia.org

Bu algoritmadan yola çıkarak. Golang ve C bir arada kodladım.
C kısmında sayısal algoritmayı yaptım.
Golang içinde ise C import ile C kodunu golang ile paralelledim.

Sonuç :
2 Milyar sayıyı 6.16 saniyede bitirmiş oldu.

1 milyar sayı için sonuç yaklaşık 2 saniye

 

[ShadowMan]

Merhaba, c++ ile 0 dan başlayarak kullanıcının girdiği sayıya kadar olan asal sayıları hesaplayan bir kod yazdım bu kodu yazmamın amacı pi zero 2w cihazım için işlemci overclock stabilitesini sağlamak için gerekli konfigürasyonu yapmaktı. Ancak merak ettiğim ve deneyip şaşırdığım bir durum gözlemledim. Arduino ide ile derlediğim ve pi pico da çalıştırdığımda 100 bin e kadar olan asal sayıları hesaplama süresi 768 milisaniye iken pi zero 2w de ise 106 milisaniye (cpu frekansı 1350 over voltage 4) buraya kadar bir sorun yok zero 2w haliyle daha hızlı ancak kodu ryzen 5 3500u işlemcili bilgisayarımda çalıştırdığımda ise sonuç şaşırtıcı bir şekilde 1233 milisaniye olarak çıktı o sırada işlemci yük altında değil normal bir şekilde çalışıyor bu sonucun işlemci alu'su ile veya komut setleri farkı ile ilişkisi var mıdır?

(algoritma olarak kod aynı sadece biri terminalde diğeri seri ekranda)

pico için yazdığım kod:

#include <Arduino.h>

bool asalmi(int n) {
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}

void setup() {
    Serial.begin(9600);
    while (!Serial) {
      ;
    }

    Serial.println("sayı gir:");
    while (!Serial.available()) {
        ;
    }
    int limit = Serial.parseInt();
    unsigned long start_time = millis();

 
    Serial.println("Asal sayılar:");
    for (int i = 2; i <= limit; ++i) {
        if (asalmi(i)) {
            Serial.print(i);
            Serial.print(" ");
        }
    }
    Serial.println();

    unsigned long end_time = millis();
    unsigned long duration = end_time - start_time;
    Serial.print("İşlem süresi: ");
    Serial.print(duration);
    Serial.println(" milisaniye");
}

void loop() {}

#include <iostream>
#include <chrono>

bool asalmi(int n) {
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}

int main() {
    int limit;


    std::cout << "sayı gir: ";
    std::cin >> limit;

    auto start_time = std::chrono::steady_clock::now();


    std::cout << "Asal sayılar:" << std::endl;
    for (int i = 2; i <= limit; ++i) {
        if (asalmi(i)) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;


    auto end_time = std::chrono::steady_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time);
    std::cout << "İşlem süresi: " << duration.count() << " milisaniye" << std::endl;

    return 0;
}

Şimdi 100 bin'e kadar olan asal sayilar c++ ı derleyip ubuntu ile test ettim 22 ms sürdü. Js ile 15 ms js gene hızlı çıktı python ise 17.8 ms... Yorumlanan bir dilin derlenen bir dile göre hızlı olduğu durumu ilk defa gördüm. Ancak bu hız bizi yanıltmasın bence çünkü belliki linux'ta da windows'ta da kullanıcı işlemleri için özellikle browser'lara öncelik tanıyor olabilir.