Paralelné algoritmy
Teória
Model
Model - program
Čas O(lg N).
Práca O(N).
Iný pohľad
zrataj_prefix_sum(A):
for i = 0...n/2 pardo:
B[i] = A[2*i]+A[2*i+1]
B = zrataj_prefix_sum(B)
for i = 0...n/2 pardo:
A[2*i+1] = B[i]
A[2*i] = B[i]-A[2*i+1]
Zveriny - hladanie minima
for i,j = 0..n pardo:
B[i,j] = A[i] < A[j]
for i = 0..n pardo:
M[i] = false
for i = 0..n pardo:
for j = 0..n pardo:
M[i] = B[i,j]
Čas: O(1)
Práca: O(N^2)
Parelelné algoritmy
Realita
Krutá realita
Ako na to?
Thready po starom
#include <cstdio>
#include <pthread.h>
using namespace std;
void* thread_func(void *args) {
printf("hello\n");
}
int main() {
pthread_t thread;
pthread_create(&thread, NULL, thread_func, NULL);
printf("main\n");
pthread_join(thread, NULL);
}
Thready po starom - argumenty
struct Data {
int x, y;
};
void* thread_func(void *args) {
Data d = *((Data*)args); // DAFUQ??
printf("%d %d\n", d.x, d.y);
}
int main() {
pthread_t thread;
Data d;
d.x = 47; d.y = 42;
pthread_create(&thread, NULL, thread_func, &d);
printf("main\n");
pthread_join(thread, NULL);
}
Thready boost
#include <boost/thread.hpp>
#include <cstdio>
void worker(int cislo) {
printf("worker %d\n", cislo);
}
int main() {
boost::thread thread(worker, 47);
printf("main\n");
thread.join();
}
Thready - ďalší príklad
void worker(vector<int>* x) {
for (int i = 0; i < 100000; i++)
x->push_back(i);
}
int main() {
vector<int> x;
boost::thread thread(worker, &x);
boost::thread thread2(worker, &x);
printf("main\n");
thread.join();
thread2.join();
printf("%d\n", x.size());
}
Výsledok
*** glibc detected *** ./a.out: double free or corruption (fasttop): 0x00007f81c00008e0 ***
======= Backtrace: =========
/lib/libc.so.6(+0x78e66)[0x7f81c5660e66]
./a.out[0x406296]
./a.out[0x405e7a]
======= Memory map: ========
0060b000-0060c000 rw-p 0000b000 08:07 3934059 /home/drobcek/kspstuff/2012klacno/paralerne/a.out
023a5000-023c6000 rw-p 00000000 00:00 0 [heap]
7f81c49c3000-7f81c49c4000 ---p 00000000 00:00 0
7f81c49c4000-7f81c51c4000 rw-p 00000000 00:00 0
...
Aborted
Čo sa stalo
Riešenie - odporúča 9 z 10 farmárov
void worker(vector<int>* x, bool* pisem) {
for (int i = 0; i < 100000; i++) {
while (*pisem);
*pisem = true;
x->push_back(i);
*pisem = false;
}
}
int main() {
vector<int> x; bool pisem = false;
boost::thread thread(worker, &x, &pisem);
boost::thread thread2(worker, &x, &pisem);
printf("main\n");
thread.join(); thread2.join();
printf("%d\n", x.size());
}
Výsledok - 10 pokusov
6-krát - segmentation fault
3-krát - dlhý škaredý error
1-krát - 178338
Ako farmár...
Poriadne riešenie
void worker(vector<int>* x, boost::mutex* x_mutex) {
for (int i = 0; i < 1000000; i++) {
x_mutex->lock();
x->push_back(i);
x_mutex->unlock();
}
}
int main() {
vector<int> x;
boost::mutex x_mutex;
boost::thread thread(worker, &x, &x_mutex);
boost::thread thread2(worker, &x, &x_mutex);
printf("main\n");
thread.join(); thread2.join();
printf("%d\n", x.size());
}
Trochu viac farmárčiny
void worker1(vector<int>* x, vector<int>* y,
boost::mutex* x_mutex, boost::mutex* y_mutex) {
for (int i = 0; i < 1000000; i++) {
x_mutex->lock(); y_mutex->lock();
x->push_back(i); y->push_back(2*i);
y_mutex->unlock(); x_mutex->unlock();
}
}
void worker2(vector<int>* x, vector<int>* y,
boost::mutex* x_mutex, boost::mutex* y_mutex) {
for (int i = 0; i < 1000000; i++) {
y_mutex->lock(); x_mutex->lock();
x->push_back(i); y->push_back(2*i);
x_mutex->unlock(); y_mutex->unlock();
}
}
Producent - konzument
void konzument(queue<Item*>* fr, mutex* mutex) {
while(true) {
Item *x = NULL;
mutex->lock();
if (!fr->empty()) { x = fr->front(); fr->pop(); }
mutex->unlock();
if (x) Spracuj(x);
}
}
void producent(queue<Item*>* fr, mutex*x mutex) {
while(true) {
Item* x = vyprodukuj();
mutex->lock(); fr->push(x); mutex->unlock();
}
}
Konzument maká aj keď nemusí...
Producent - konzument poriadne
int get_data(queue<int>* fr, mutex* mutex, condition_variable* cond) {
unique_lock<boost::mutex> lock(*mutex);
while(fr->empty()) {
cond->wait(lock);
}
int ret = fr->front(); fr->pop(); return ret;
}
void konzument(queue<int>* fr, mutex* mutex, condition_variable* cond) {
while(true) {
int x = get_data(fr, mutex, cond); printf("%d\n", x);
}
}
void producent(queue<int>* fr, mutex* mutex, condition_variable* cond) {
while(true) {
int x = rand()%1000;
mutex->lock(); fr->push(x); cond->notify_all(); mutex->unlock();
}
}
Načo to je dobré
Hotovo.