HTML

flugi szakblogja

Megjegyzések programozásról, jelfeldolgozásról, beszédtechnológiáról

Keresés

Friss topikok

  • LoverCase: kösz! (2012.03.23. 20:41) rekurzív szálszaporítás gyorsít?
  • tormanator: Mért érték, CPU 200 Mflopp, GPU 11 Gflopp , ez 55x sebesség, de középkategóriánál mért értékek. Az... (2011.09.11. 11:27) OpenCL
  • Tom Benko: @flugi_: Ebből is látszik, hogy a sudo a legveszélyesebb parancs. (2011.03.10. 20:09) Az egyszerűség dícsérete
  • xsasha: Kíváncsi vagyok, mi lesz a véleményed erről a beírásról. :-) Szóval az én elméletem szerint az ag... (2011.02.28. 17:30) Programozás és intuitivitás

Linkblog

Archívum

Feedek

XML

rekurzív szálszaporítás gyorsít?

2011.02.13. 00:03 flugi_

Egyik alkalommal előadásra készülve írtam egy klasszikus rekurzív visszalépéses keresést a 8 királynőre. Az OpenMP elhozta a kényelmes párhuzamosságot, így kipróbáltam a párhuzamosítását a rekurzív lépésnek. Ez azt jelenti, hogy a függvény több szálat indít arra, hogy a következő lépéslehetőségeket kiértékelje, amik szintén több szálat indítanak, stb, stb. Józan paraszti ésszel erre gondolva azt várja az ember, hogy a sokezer szál óriási overheadet okoz, és meghal, vagy belassul az egész folyamat.

Ehhez képest a program gyorsult, kb 1.6x sebességnövekedést mértem egy 32 bites Atomon, ami nem is igazi kétmagos, csak hyperthreadinges. Két lehetséges magyarázatot tudok elképzelni

  • Az OpenMP runtime okos, és nem csinál overheadet, hanem csak egy kis létszámú szálcsoportot enged egyszerre futni, a többit altatja. Ebben az esetben ez egy kellemes technikai trükk.
  • A feladat jellegéből adódóan a jó választások lehetősége a rekurzió mélységével csökken, és ez egyfajta önszabályozást valósít meg az egyébként limitálatlan szálszámok esetében is. Ebben az esetben ez egy izgalmas jelenség egy feladatcsoportról.

Ha lesz komment, talán rakok ide forrást is, játszani.

Facebook Tumblr Tweet Pinterest Tetszik
0

3 komment

Ajánlott bejegyzések:

A bejegyzés trackback címe:

https://flugiszaki.blog.hu/api/trackback/id/tr242657012

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

LoverCase 2012.03.20. 12:56:47

épp ilyesmiről tanulgatok. így több mint egy évvel később, ki tudnád rakni a forrást? már ha megtalálod persze. köszi
Válasz erre 

flugi_ · http://fundi.blog.hu/ 2012.03.22. 23:01:04

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

inline bool kiralyno(int x1, int y1, int x2, int y2) {
return x1==x2 || y1==y2 || abs(x1+y2)==abs(x2+y1) || abs(x1+y1)==abs(x2+y2);
}

int cc=0;

bool utesben(vector<int>& v) {
cc++;
int s=v.size();
bool res=false;
for (int i=0;i<s;i++) {
for (int j=i+1;j<s;j++) {
res |= kiralyno(i,v[i],j,v[j]);
}
}
return res;
}

void talalat(vector<int>& v) {
cout << cc << " lepesbol: ";
for (int i=0;i<v.size();i++) cout << v[i] << " ";
cout << endl;
}

void keres(vector<int> v, int a, int kir) {
if (utesben(v)) return;
if (v.size()==kir) {
talalat(v);
}
//Még nem elég hosszú, de eddig jó
v.push_back(0);
#pragma omp parallel for
for (int i=0;i<kir;i++) {
v[a]=i;
keres(v,a+1,kir);
}
}

int main() {
vector<int> v;
keres(v,0,12);

}
Válasz erre 
süti beállítások módosítása