From 61bd7df99d32b8c489383568afc53117ab1fa81f Mon Sep 17 00:00:00 2001 From: Brett Weiland Date: Mon, 23 Jan 2023 11:49:25 -0600 Subject: commented some syncronization code, declared functions for plans of reorganizing code --- mthread.cpp | 36 +++++++++++++++++++++++++++++++++++- mthread.hpp | 5 ++++- 2 files changed, 39 insertions(+), 2 deletions(-) diff --git a/mthread.cpp b/mthread.cpp index 796055e..269155d 100644 --- a/mthread.cpp +++ b/mthread.cpp @@ -46,7 +46,27 @@ void mthread::join() { if((my_thread) && (my_thread->joinable())) my_thread->join(); } +//TODO make final +//looks for work +void mthread::find_work() { +} + +//makes sure no one is asking for work from us +void mthread::check_work_request() { +} + +//renders area +void mthread::render_area() { //TODO rename +} + +//alternates states of finding work work and rendering +void mthread::run() { + for(;;) { + } +} + +//TODO move syncronization to another function for extensibility void mthread::render() { uint32_t image_width = image.width(); unsigned int iter; @@ -80,6 +100,7 @@ void mthread::render() { progress++; status.status_lock.lock(); status.row_load = y_max - on_y; + //check if anyone's asking us to divide if(status.div_syn) { status.div_error = status.row_load <= min_lines; @@ -130,32 +151,45 @@ void mthread::render() { status.share_finished = true; status.status_lock.unlock(); + //first we look over all workers to see which are canidates to ask for work while(status.searching) { workers_finished = 0; + //TODO do we really need this whole for loop? for(worker = 0; worker < worker_cnt; worker++) { + //lock other worker so we can request from them peer_status = &workers[worker]->status; peer_status->status_lock.lock(); + //if they're done, we remember that to see if we exit if((peer_status->share_finished) && (worker != id)) { workers_finished++; } + //if they're us, currently looking for work, + //or don't have enough work for us to complete, then skip + if((worker == id) || (peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { loads[worker] = 0; peer_status->status_lock.unlock(); continue; } + //finally, if they're valid, write them down loads[worker] = peer_status->row_load; peer_status->status_lock.unlock(); } + //exit if all workers are finished if(workers_finished >= worker_cnt - 1) { return; } + //then we look over and pick our canidates for(;;) { + //find the worker who has the biggest workload worker = distance(loads, max_element(loads, &loads[worker_cnt])); - if(!loads[worker]) break; + if(!loads[worker]) break; //we have found a worker; distance is 0 peer_status = &workers[worker]->status; peer_status->status_lock.lock(); + //check to see if canidate is valid. + //TODO do we really need to check the first time? if((peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { loads[worker] = 0; peer_status->status_lock.unlock(); diff --git a/mthread.hpp b/mthread.hpp index c70647e..f59732c 100644 --- a/mthread.hpp +++ b/mthread.hpp @@ -61,9 +61,12 @@ class mthread { uint32_t x_min, x_max, y_min, y_max; uint32_t on_x, on_y; unsigned int divisions; - void render(); int state; struct mthread_divinfo divide(); + + void render(); //TODO + void render_area(); + void run(); }; -- cgit v1.2.3 From 3b97e627caa6883391bd1e9f3c31172e10bf7404 Mon Sep 17 00:00:00 2001 From: Brett Weiland Date: Mon, 23 Jan 2023 14:43:30 -0600 Subject: finished functions to achieve polymorphism --- docs/p4.pdf | Bin 5197678 -> 5197666 bytes mthread.cpp | 292 ++++++++++++++++++++++++++++-------------------------------- mthread.hpp | 4 +- mthread_old | 269 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 407 insertions(+), 158 deletions(-) create mode 100644 mthread_old diff --git a/docs/p4.pdf b/docs/p4.pdf index 86c225c..4b0bff8 100644 Binary files a/docs/p4.pdf and b/docs/p4.pdf differ diff --git a/mthread.cpp b/mthread.cpp index 269155d..4af25ff 100644 --- a/mthread.cpp +++ b/mthread.cpp @@ -30,7 +30,7 @@ mthread::mthread( void mthread::dispatch() { if((my_thread) && (my_thread->joinable())) delete my_thread; - my_thread = new thread([this] {render();}); + my_thread = new thread([this] {run();}); } @@ -46,185 +46,163 @@ void mthread::join() { if((my_thread) && (my_thread->joinable())) my_thread->join(); } -//TODO make final -//looks for work -void mthread::find_work() { -} - -//makes sure no one is asking for work from us -void mthread::check_work_request() { -} - -//renders area -void mthread::render_area() { //TODO rename -} - -//alternates states of finding work work and rendering -void mthread::run() { - for(;;) { - } -} - - -//TODO move syncronization to another function for extensibility -void mthread::render() { - uint32_t image_width = image.width(); - unsigned int iter; +bool mthread::find_work() { unsigned int worker, workers_finished; uint32_t loads[worker_cnt]; - double pixel_value; - complex c, a; struct mthread_status *peer_status; struct mthread_divinfo divinfo; - + workers_finished = 0; unique_lock ack; - unique_lock syn_ack; - - status.status_lock.lock(); - status.searching = false; - status.share_finished = false; - status.div_syn = false; - status.div_error = false; + status.status_lock.lock(); + status.searching = true; + status.share_finished = true; status.status_lock.unlock(); + //TODO do we really need this whole for loop? + for(worker = 0; worker < worker_cnt; worker++) { + //lock other worker so we can request from them + peer_status = &workers[worker]->status; + peer_status->status_lock.lock(); - y_min = 0; - y_max = image.height(); + //if they're done, we remember that to see if we exit + if((peer_status->share_finished) && (worker != id)) { + workers_finished++; + } + //if they're us, currently looking for work, + //or don't have enough work for us to complete, then skip + + if((worker == id) || + (peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { + loads[worker] = 0; + peer_status->status_lock.unlock(); + continue; + } + //finally, if they're valid, write them down + loads[worker] = peer_status->row_load; + peer_status->status_lock.unlock(); + } + //exit if all workers are finished + if(workers_finished >= worker_cnt - 1) { + return false; + } + //then we look over and pick our canidates + for(;;) { + //find the worker who has the biggest workload + worker = distance(loads, max_element(loads, &loads[worker_cnt])); + if(!loads[worker]) break; //we have found a worker; distance is 0 + peer_status = &workers[worker]->status; + peer_status->status_lock.lock(); + //check to see if canidate is valid. + //TODO do we really need to check the first time? + if((peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { + loads[worker] = 0; + peer_status->status_lock.unlock(); + continue; + } + ack = unique_lock(peer_status->ack_lk); + peer_status->div_syn = true; + peer_status->status_lock.unlock(); + peer_status->msg_notify.wait(ack); + ack.unlock(); + if(peer_status->div_error) { + loads[worker] = 0; + peer_status->status_lock.lock(); + peer_status->div_error = false; + peer_status->div_syn = false; + peer_status->status_lock.unlock(); + continue; + } + divinfo = workers[worker]->divide(); + peer_status->syn_ack_lk.unlock(); + peer_status->msg_notify.notify_all(); + y_min = divinfo.y_min; + y_max = divinfo.y_max; + x_min = divinfo.x_min; + x_max = divinfo.x_max; + status.status_lock.lock(); + status.searching = false; + status.status_lock.unlock(); + break; + } + return true; +} +//makes sure no one is asking for work from us +void mthread::check_work_request() { + unique_lock syn_ack; - for(;;) { - //thread is actively rendering - for(on_y = y_min; on_y < y_max; on_y++) { - progress++; - status.status_lock.lock(); + status.status_lock.lock(); + status.row_load = y_max - on_y; + //check if anyone's asking us to divide + if(status.div_syn) { + status.div_error = status.row_load <= min_lines; + if(status.div_error) { + status.ack_lk.unlock(); + status.msg_notify.notify_all(); + } + else { + syn_ack = unique_lock(status.syn_ack_lk); + status.ack_lk.unlock(); + status.msg_notify.notify_all(); + status.msg_notify.wait(syn_ack); status.row_load = y_max - on_y; - //check if anyone's asking us to divide - if(status.div_syn) { - - status.div_error = status.row_load <= min_lines; - - if(status.div_error) { - status.ack_lk.unlock(); - status.msg_notify.notify_all(); - } - else { - syn_ack = unique_lock(status.syn_ack_lk); - status.ack_lk.unlock(); - status.msg_notify.notify_all(); - status.msg_notify.wait(syn_ack); - status.row_load = y_max - on_y; - syn_ack.unlock(); - //new x/y min/max is ajusted by other thread, we can continue as normal. - } - } - status.status_lock.unlock(); - - for(on_x = x_min; on_x < x_max; on_x++) { - c = (step * complex(on_x,on_y)) + c_min; - a = 0; - for(iter = 0; iter < max_iter; iter++) { - if(abs(a) >= inf_cutoff) break; - a = a*a + c; - } - if(iter >= max_iter) { - iter = 0; - vmap[(on_y * image_width) + on_x] = 0; - } - else { - pixel_value = (iter + 1) - (log((log(pow(abs(a), 2.0)) / 2.0) / log(2.0))); - vmap[(on_y * image_width) + on_x] = pixel_value; - histogram[(int)pixel_value]++; - } - } + syn_ack.unlock(); + //new x/y min/max is ajusted by other thread, we can continue as normal. } + } + status.status_lock.unlock(); +} +//renders area +void mthread::render_area() { + uint32_t image_width = image.width(); + unsigned int iter; + complex c, a; //TODO comment + double pixel_value; - //thread is now searching for work - - /** 2022 comment: - * this state should have been moved to a seperate function to allow rendering methods to differ - * from inherited mthreads without needing to reimpliment searching **/ - status.status_lock.lock(); - status.searching = true; - status.share_finished = true; - status.status_lock.unlock(); - - //first we look over all workers to see which are canidates to ask for work - while(status.searching) { - workers_finished = 0; - //TODO do we really need this whole for loop? - for(worker = 0; worker < worker_cnt; worker++) { - //lock other worker so we can request from them - peer_status = &workers[worker]->status; - peer_status->status_lock.lock(); - - //if they're done, we remember that to see if we exit - if((peer_status->share_finished) && (worker != id)) { - workers_finished++; - } - //if they're us, currently looking for work, - //or don't have enough work for us to complete, then skip - - if((worker == id) || - (peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { - loads[worker] = 0; - peer_status->status_lock.unlock(); - continue; - } - //finally, if they're valid, write them down - loads[worker] = peer_status->row_load; - peer_status->status_lock.unlock(); + for(on_y = y_min; on_y < y_max; on_y++) { + progress++; + check_work_request(); + for(on_x = x_min; on_x < x_max; on_x++) { + c = (step * complex(on_x,on_y)) + c_min; + a = 0; + for(iter = 0; iter < max_iter; iter++) { + if(abs(a) >= inf_cutoff) break; + a = a*a + c; } - //exit if all workers are finished - if(workers_finished >= worker_cnt - 1) { - return; + if(iter >= max_iter) { + iter = 0; + vmap[(on_y * image_width) + on_x] = 0; } - //then we look over and pick our canidates - for(;;) { - //find the worker who has the biggest workload - worker = distance(loads, max_element(loads, &loads[worker_cnt])); - if(!loads[worker]) break; //we have found a worker; distance is 0 - peer_status = &workers[worker]->status; - peer_status->status_lock.lock(); - //check to see if canidate is valid. - //TODO do we really need to check the first time? - if((peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { - loads[worker] = 0; - peer_status->status_lock.unlock(); - continue; - } - ack = unique_lock(peer_status->ack_lk); - peer_status->div_syn = true; - peer_status->status_lock.unlock(); - peer_status->msg_notify.wait(ack); - ack.unlock(); - if(peer_status->div_error) { - loads[worker] = 0; - peer_status->status_lock.lock(); - peer_status->div_error = false; - peer_status->div_syn = false; - peer_status->status_lock.unlock(); - continue; - } - - divinfo = workers[worker]->divide(); - peer_status->syn_ack_lk.unlock(); - peer_status->msg_notify.notify_all(); - y_min = divinfo.y_min; - y_max = divinfo.y_max; - x_min = divinfo.x_min; - x_max = divinfo.x_max; - status.status_lock.lock(); - status.searching = false; - status.status_lock.unlock(); - break; + else { + pixel_value = (iter + 1) - (log((log(pow(abs(a), 2.0)) / 2.0) / log(2.0))); + vmap[(on_y * image_width) + on_x] = pixel_value; + histogram[(int)pixel_value]++; } } } } +//alternates states of finding work work and rendering +void mthread::run() { + status.status_lock.lock(); //TODO move to initilizer + status.searching = false; + status.share_finished = false; + status.div_syn = false; + status.div_error = false; + status.status_lock.unlock(); + + do { + render_area(); + } while (find_work()); + +} + + +//TODO move syncronization to another function for extensibility + struct mthread_divinfo mthread::divide() { struct mthread_divinfo ret; ret.x_min = x_min; diff --git a/mthread.hpp b/mthread.hpp index f59732c..953d021 100644 --- a/mthread.hpp +++ b/mthread.hpp @@ -64,9 +64,11 @@ class mthread { int state; struct mthread_divinfo divide(); - void render(); //TODO void render_area(); + void run(); + bool find_work(); + void check_work_request(); }; diff --git a/mthread_old b/mthread_old new file mode 100644 index 0000000..9f7df9f --- /dev/null +++ b/mthread_old @@ -0,0 +1,269 @@ +#include "mthread.hpp" +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +mthread::mthread( + unsigned int x_mn, unsigned int x_mx, complex c_min, complex c_max, + unsigned int inf_cutoff, unsigned int max_iter, png& image, double *g_vmap, unsigned int *g_histogram, + mthread **worker_list, unsigned int id, unsigned int jobs, atomic& progress) + : x_min_orig(x_mn), x_max_orig(x_mx), + c_min(c_min), c_max(c_max), + inf_cutoff(inf_cutoff), max_iter(max_iter), image(image), id(id), worker_cnt(jobs), progress(progress){ + + workers = worker_list; + x_min = x_mn; + x_max = x_mx; + y_min = 0; + y_max = image.height(); + vmap = g_vmap; + histogram = g_histogram; + step = (c_max - c_min) / complex(image.height(), image.width()); + my_thread = NULL; + +status.status_lock.lock(); + status.searching = false; + status.share_finished = false; + status.div_syn = false; + status.div_error = false; + status.status_lock.unlock(); +} + +void mthread::dispatch() { + if((my_thread) && (my_thread->joinable())) delete my_thread; + my_thread = new thread([this] {render();}); +} + + +mthread::~mthread() { + if((my_thread) && (my_thread->joinable())) { + my_thread->join(); + delete my_thread; + } +} + + +void mthread::join() { + if((my_thread) && (my_thread->joinable())) my_thread->join(); +} + +//TODO make final +//looks for work +void mthread::find_work() { +} + +//makes sure no one is asking for work from us +void mthread::check_work_request() { + unique_lock ack; + unique_lock syn_ack; + + status.status_lock.lock(); + status.row_load = y_max - on_y; + //check if anyone's asking us to divide + if(status.div_syn) { + status.div_error = status.row_load <= min_lines; + if(status.div_error) { + status.ack_lk.unlock(); + status.msg_notify.notify_all(); + } + else { + syn_ack = unique_lock(status.syn_ack_lk); + status.ack_lk.unlock(); + status.msg_notify.notify_all(); + status.msg_notify.wait(syn_ack); + status.row_load = y_max - on_y; + syn_ack.unlock(); + //new x/y min/max is ajusted by other thread, we can continue as normal. + } + } + status.status_lock.unlock(); +} + +//renders area +void mthread::render_area() { //TODO rename +} + +//alternates states of finding work work and rendering +void mthread::run() { + for(;;) { + } +} + + +//TODO move syncronization to another function for extensibility +void mthread::render() { + uint32_t image_width = image.width(); + unsigned int iter; + unsigned int worker, workers_finished; + uint32_t loads[worker_cnt]; + double pixel_value; + complex c, a; + struct mthread_status *peer_status; + struct mthread_divinfo divinfo; + + unique_lock ack; + unique_lock syn_ack; + + + status.status_lock.lock(); + status.searching = false; + status.share_finished = false; + status.div_syn = false; + status.div_error = false; + status.status_lock.unlock(); + + + y_min = 0; + y_max = image.height(); + + + + for(;;) { + //thread is actively rendering + for(on_y = y_min; on_y < y_max; on_y++) { + progress++; + check_work_request(); + /** + status.status_lock.lock(); + status.row_load = y_max - on_y; + //check if anyone's asking us to divide + if(status.div_syn) { + status.div_error = status.row_load <= min_lines; + if(status.div_error) { + status.ack_lk.unlock(); + status.msg_notify.notify_all(); + } + else { + syn_ack = unique_lock(status.syn_ack_lk); + status.ack_lk.unlock(); + status.msg_notify.notify_all(); + status.msg_notify.wait(syn_ack); + status.row_load = y_max - on_y; + syn_ack.unlock(); + //new x/y min/max is ajusted by other thread, we can continue as normal. + } + } + status.status_lock.unlock(); + **/ + + for(on_x = x_min; on_x < x_max; on_x++) { + c = (step * complex(on_x,on_y)) + c_min; + a = 0; + for(iter = 0; iter < max_iter; iter++) { + if(abs(a) >= inf_cutoff) break; + a = a*a + c; + } + if(iter >= max_iter) { + iter = 0; + vmap[(on_y * image_width) + on_x] = 0; + } + else { + pixel_value = (iter + 1) - (log((log(pow(abs(a), 2.0)) / 2.0) / log(2.0))); + vmap[(on_y * image_width) + on_x] = pixel_value; + histogram[(int)pixel_value]++; + } + } + } + + + //thread is now searching for work + + /** 2022 comment: + * this state should have been moved to a seperate function to allow rendering methods to differ + * from inherited mthreads without needing to reimpliment searching **/ + status.status_lock.lock(); + status.searching = true; + status.share_finished = true; + status.status_lock.unlock(); + + //first we look over all workers to see which are canidates to ask for work + while(status.searching) { + workers_finished = 0; + //TODO do we really need this whole for loop? + for(worker = 0; worker < worker_cnt; worker++) { + //lock other worker so we can request from them + peer_status = &workers[worker]->status; + peer_status->status_lock.lock(); + + //if they're done, we remember that to see if we exit + if((peer_status->share_finished) && (worker != id)) { + workers_finished++; + } + //if they're us, currently looking for work, + //or don't have enough work for us to complete, then skip + + if((worker == id) || + (peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { + loads[worker] = 0; + peer_status->status_lock.unlock(); + continue; + } + //finally, if they're valid, write them down + loads[worker] = peer_status->row_load; + peer_status->status_lock.unlock(); + } + //exit if all workers are finished + if(workers_finished >= worker_cnt - 1) { + return; + } + //then we look over and pick our canidates + for(;;) { + //find the worker who has the biggest workload + worker = distance(loads, max_element(loads, &loads[worker_cnt])); + if(!loads[worker]) break; //we have found a worker; distance is 0 + peer_status = &workers[worker]->status; + peer_status->status_lock.lock(); + //check to see if canidate is valid. + //TODO do we really need to check the first time? + if((peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { + loads[worker] = 0; + peer_status->status_lock.unlock(); + continue; + } + ack = unique_lock(peer_status->ack_lk); + peer_status->div_syn = true; + peer_status->status_lock.unlock(); + peer_status->msg_notify.wait(ack); + ack.unlock(); + if(peer_status->div_error) { + loads[worker] = 0; + peer_status->status_lock.lock(); + peer_status->div_error = false; + peer_status->div_syn = false; + peer_status->status_lock.unlock(); + continue; + } + + divinfo = workers[worker]->divide(); + peer_status->syn_ack_lk.unlock(); + peer_status->msg_notify.notify_all(); + y_min = divinfo.y_min; + y_max = divinfo.y_max; + x_min = divinfo.x_min; + x_max = divinfo.x_max; + status.status_lock.lock(); + status.searching = false; + status.status_lock.unlock(); + break; + } + } + } +} + +struct mthread_divinfo mthread::divide() { + struct mthread_divinfo ret; + ret.x_min = x_min; + ret.x_max = x_max; + ret.y_min = ((y_max - on_y) / 2) + on_y; + ret.y_max = y_max; + y_min = on_y; + y_max = ret.y_min; + status.div_syn = false; + return ret; +} -- cgit v1.2.3 From e6cf67d4ed4ade12c7c830da388194492b07c3e3 Mon Sep 17 00:00:00 2001 From: Brett Weiland Date: Mon, 23 Jan 2023 17:41:33 -0600 Subject: finished mthread polymorphisim, moving onto revamping syncronization --- mthread.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/mthread.cpp b/mthread.cpp index 4af25ff..89d79bd 100644 --- a/mthread.cpp +++ b/mthread.cpp @@ -90,7 +90,7 @@ bool mthread::find_work() { for(;;) { //find the worker who has the biggest workload worker = distance(loads, max_element(loads, &loads[worker_cnt])); - if(!loads[worker]) break; //we have found a worker; distance is 0 + if(!loads[worker]) return true; //we have found a worker; distance is 0 peer_status = &workers[worker]->status; peer_status->status_lock.lock(); //check to see if canidate is valid. @@ -124,7 +124,7 @@ bool mthread::find_work() { status.status_lock.lock(); status.searching = false; status.status_lock.unlock(); - break; + return true; } return true; } -- cgit v1.2.3 From 713d467385959ac4299e685fffcad7ffff788758 Mon Sep 17 00:00:00 2001 From: Brett Weiland Date: Mon, 23 Jan 2023 18:40:29 -0600 Subject: made mthread class polymorphic, finished commenting --- README.md | 10 +-- docs/p4.pdf | Bin 5197666 -> 5197819 bytes mthread.cpp | 50 +++++++---- mthread.hpp | 4 +- mthread_old | 269 ------------------------------------------------------------ 5 files changed, 39 insertions(+), 294 deletions(-) delete mode 100644 mthread_old diff --git a/README.md b/README.md index f654e3f..b9d29f2 100644 --- a/README.md +++ b/README.md @@ -1,15 +1,9 @@ # Building -Just run make. Depends on libpng. +For Linux, just run make. Depends on libpng. # Info -This project was my final for CS200 at JCCC. It uses multiple threads to draw the mandelbrot. When one thread is finished, it will communicate with other threads to split the load; work delegation is the main showcase of this project. +This project was my final for CS200 at JCCC. It uses multiple threads to draw the mandelbrot. When one thread is finished, it will communicate with other threads to split the load; work delegation is the main showcase of this project. Additionally, The class used to render is polymorphic, as new rendering methods can be implimented without reimplimenting code such as work delegation and synchronization. # Writeup For the writeup portion of this project I did last year, please visit [here](https://git.bpcspace.com/brett/Mandelbrot-CS200/src/branch/master/docs/p4.pdf). Here you will be able to see demos, as well as flowcharts and pseudo code for some of the functionallity. - -# Problems -Due to the fact I had to complete this project in just a few days, there are a few problems I'd fix if I were to do it again. - -The largest issue is that the thread worker class is not extensible. I have rendering in the same function as thread communication; you should not need to reimpliment the syncronization aspects of the thread just to change how it renders. -Additionally, I'm not sure if there was a simpler way to prevent race conditions then to manually create a mutex when modifying multiple variables. diff --git a/docs/p4.pdf b/docs/p4.pdf index 4b0bff8..f99b5b5 100644 Binary files a/docs/p4.pdf and b/docs/p4.pdf differ diff --git a/mthread.cpp b/mthread.cpp index 89d79bd..7d1b31f 100644 --- a/mthread.cpp +++ b/mthread.cpp @@ -26,6 +26,7 @@ mthread::mthread( histogram = g_histogram; step = (c_max - c_min) / complex(image.height(), image.width()); my_thread = NULL; + status.status_lock.lock(); } void mthread::dispatch() { @@ -59,7 +60,6 @@ bool mthread::find_work() { status.share_finished = true; status.status_lock.unlock(); - //TODO do we really need this whole for loop? for(worker = 0; worker < worker_cnt; worker++) { //lock other worker so we can request from them peer_status = &workers[worker]->status; @@ -69,15 +69,22 @@ bool mthread::find_work() { if((peer_status->share_finished) && (worker != id)) { workers_finished++; } - //if they're us, currently looking for work, - //or don't have enough work for us to complete, then skip + /** The reason why we have this bit in code twice is to prevent race conditions. + * To add the potential canidate worker to our list to be sorted, + * we need to make sure it's not currently being divided (true if div_syn is set). + * Since we'll need to check the same later + * when we actually request to split it's workload, + * we might as well narrow it down and check everything else. + * **/ if((worker == id) || - (peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { + (peer_status->searching) || (peer_status->div_syn) || + (peer_status->row_load < min_lines)) { loads[worker] = 0; peer_status->status_lock.unlock(); continue; } + //finally, if they're valid, write them down loads[worker] = peer_status->row_load; peer_status->status_lock.unlock(); @@ -93,18 +100,23 @@ bool mthread::find_work() { if(!loads[worker]) return true; //we have found a worker; distance is 0 peer_status = &workers[worker]->status; peer_status->status_lock.lock(); - //check to see if canidate is valid. - //TODO do we really need to check the first time? - if((peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { + + //re-check to see if canidate is valid (may have changed since added and sorted). + //If you're wondering why we're doing this bit again, see comment before first time. + if((peer_status->searching) || (peer_status->div_syn) || + (peer_status->row_load < min_lines)) { loads[worker] = 0; peer_status->status_lock.unlock(); continue; } + //ack: ask peer to devide ack = unique_lock(peer_status->ack_lk); peer_status->div_syn = true; peer_status->status_lock.unlock(); + //when they reset it, they've acknowlaged and have set appropriate messages peer_status->msg_notify.wait(ack); ack.unlock(); + //area is too small to divide reliably if(peer_status->div_error) { loads[worker] = 0; peer_status->status_lock.lock(); @@ -114,13 +126,20 @@ bool mthread::find_work() { continue; } + //otherwise, we modify their struct for them to split their workload divinfo = workers[worker]->divide(); peer_status->syn_ack_lk.unlock(); + + //tell them we're done modifying peer_status->msg_notify.notify_all(); + + //set our own stuff y_min = divinfo.y_min; y_max = divinfo.y_max; x_min = divinfo.x_min; x_max = divinfo.x_max; + + //update our status status.status_lock.lock(); status.searching = false; status.status_lock.unlock(); @@ -159,25 +178,28 @@ void mthread::check_work_request() { void mthread::render_area() { uint32_t image_width = image.width(); unsigned int iter; - complex c, a; //TODO comment + complex c, z; double pixel_value; + /** pixel is drawn based on if/how many itertions it takes to get to infinity + * while computing z^2+c. **/ + for(on_y = y_min; on_y < y_max; on_y++) { progress++; check_work_request(); for(on_x = x_min; on_x < x_max; on_x++) { c = (step * complex(on_x,on_y)) + c_min; - a = 0; + z = 0; for(iter = 0; iter < max_iter; iter++) { - if(abs(a) >= inf_cutoff) break; - a = a*a + c; + if(abs(z) >= inf_cutoff) break; + z = z*z + c; } if(iter >= max_iter) { iter = 0; vmap[(on_y * image_width) + on_x] = 0; } else { - pixel_value = (iter + 1) - (log((log(pow(abs(a), 2.0)) / 2.0) / log(2.0))); + pixel_value = (iter + 1) - (log((log(pow(abs(z), 2.0)) / 2.0) / log(2.0))); vmap[(on_y * image_width) + on_x] = pixel_value; histogram[(int)pixel_value]++; } @@ -187,7 +209,7 @@ void mthread::render_area() { //alternates states of finding work work and rendering void mthread::run() { - status.status_lock.lock(); //TODO move to initilizer + //locks in initilizer status.searching = false; status.share_finished = false; status.div_syn = false; @@ -201,8 +223,6 @@ void mthread::run() { } -//TODO move syncronization to another function for extensibility - struct mthread_divinfo mthread::divide() { struct mthread_divinfo ret; ret.x_min = x_min; diff --git a/mthread.hpp b/mthread.hpp index 953d021..bd1853e 100644 --- a/mthread.hpp +++ b/mthread.hpp @@ -33,7 +33,7 @@ class mthread { std::complex c_min, std::complex c_max, unsigned int inf_cutoff, unsigned int max_iter, png& image, double *g_vmap, unsigned int *g_histogram, mthread **worker_list, unsigned int id, unsigned int jobs, std::atomic& progress); - ~mthread(); + virtual ~mthread(); //virtual in case a modified renderer needs to allocate memory void join(); void dispatch(); @@ -64,7 +64,7 @@ class mthread { int state; struct mthread_divinfo divide(); - void render_area(); + virtual void render_area(); void run(); bool find_work(); diff --git a/mthread_old b/mthread_old deleted file mode 100644 index 9f7df9f..0000000 --- a/mthread_old +++ /dev/null @@ -1,269 +0,0 @@ -#include "mthread.hpp" -#include -#include -#include -#include -#include -#include -#include -#include -using namespace std; - -mthread::mthread( - unsigned int x_mn, unsigned int x_mx, complex c_min, complex c_max, - unsigned int inf_cutoff, unsigned int max_iter, png& image, double *g_vmap, unsigned int *g_histogram, - mthread **worker_list, unsigned int id, unsigned int jobs, atomic& progress) - : x_min_orig(x_mn), x_max_orig(x_mx), - c_min(c_min), c_max(c_max), - inf_cutoff(inf_cutoff), max_iter(max_iter), image(image), id(id), worker_cnt(jobs), progress(progress){ - - workers = worker_list; - x_min = x_mn; - x_max = x_mx; - y_min = 0; - y_max = image.height(); - vmap = g_vmap; - histogram = g_histogram; - step = (c_max - c_min) / complex(image.height(), image.width()); - my_thread = NULL; - -status.status_lock.lock(); - status.searching = false; - status.share_finished = false; - status.div_syn = false; - status.div_error = false; - status.status_lock.unlock(); -} - -void mthread::dispatch() { - if((my_thread) && (my_thread->joinable())) delete my_thread; - my_thread = new thread([this] {render();}); -} - - -mthread::~mthread() { - if((my_thread) && (my_thread->joinable())) { - my_thread->join(); - delete my_thread; - } -} - - -void mthread::join() { - if((my_thread) && (my_thread->joinable())) my_thread->join(); -} - -//TODO make final -//looks for work -void mthread::find_work() { -} - -//makes sure no one is asking for work from us -void mthread::check_work_request() { - unique_lock ack; - unique_lock syn_ack; - - status.status_lock.lock(); - status.row_load = y_max - on_y; - //check if anyone's asking us to divide - if(status.div_syn) { - status.div_error = status.row_load <= min_lines; - if(status.div_error) { - status.ack_lk.unlock(); - status.msg_notify.notify_all(); - } - else { - syn_ack = unique_lock(status.syn_ack_lk); - status.ack_lk.unlock(); - status.msg_notify.notify_all(); - status.msg_notify.wait(syn_ack); - status.row_load = y_max - on_y; - syn_ack.unlock(); - //new x/y min/max is ajusted by other thread, we can continue as normal. - } - } - status.status_lock.unlock(); -} - -//renders area -void mthread::render_area() { //TODO rename -} - -//alternates states of finding work work and rendering -void mthread::run() { - for(;;) { - } -} - - -//TODO move syncronization to another function for extensibility -void mthread::render() { - uint32_t image_width = image.width(); - unsigned int iter; - unsigned int worker, workers_finished; - uint32_t loads[worker_cnt]; - double pixel_value; - complex c, a; - struct mthread_status *peer_status; - struct mthread_divinfo divinfo; - - unique_lock ack; - unique_lock syn_ack; - - - status.status_lock.lock(); - status.searching = false; - status.share_finished = false; - status.div_syn = false; - status.div_error = false; - status.status_lock.unlock(); - - - y_min = 0; - y_max = image.height(); - - - - for(;;) { - //thread is actively rendering - for(on_y = y_min; on_y < y_max; on_y++) { - progress++; - check_work_request(); - /** - status.status_lock.lock(); - status.row_load = y_max - on_y; - //check if anyone's asking us to divide - if(status.div_syn) { - status.div_error = status.row_load <= min_lines; - if(status.div_error) { - status.ack_lk.unlock(); - status.msg_notify.notify_all(); - } - else { - syn_ack = unique_lock(status.syn_ack_lk); - status.ack_lk.unlock(); - status.msg_notify.notify_all(); - status.msg_notify.wait(syn_ack); - status.row_load = y_max - on_y; - syn_ack.unlock(); - //new x/y min/max is ajusted by other thread, we can continue as normal. - } - } - status.status_lock.unlock(); - **/ - - for(on_x = x_min; on_x < x_max; on_x++) { - c = (step * complex(on_x,on_y)) + c_min; - a = 0; - for(iter = 0; iter < max_iter; iter++) { - if(abs(a) >= inf_cutoff) break; - a = a*a + c; - } - if(iter >= max_iter) { - iter = 0; - vmap[(on_y * image_width) + on_x] = 0; - } - else { - pixel_value = (iter + 1) - (log((log(pow(abs(a), 2.0)) / 2.0) / log(2.0))); - vmap[(on_y * image_width) + on_x] = pixel_value; - histogram[(int)pixel_value]++; - } - } - } - - - //thread is now searching for work - - /** 2022 comment: - * this state should have been moved to a seperate function to allow rendering methods to differ - * from inherited mthreads without needing to reimpliment searching **/ - status.status_lock.lock(); - status.searching = true; - status.share_finished = true; - status.status_lock.unlock(); - - //first we look over all workers to see which are canidates to ask for work - while(status.searching) { - workers_finished = 0; - //TODO do we really need this whole for loop? - for(worker = 0; worker < worker_cnt; worker++) { - //lock other worker so we can request from them - peer_status = &workers[worker]->status; - peer_status->status_lock.lock(); - - //if they're done, we remember that to see if we exit - if((peer_status->share_finished) && (worker != id)) { - workers_finished++; - } - //if they're us, currently looking for work, - //or don't have enough work for us to complete, then skip - - if((worker == id) || - (peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { - loads[worker] = 0; - peer_status->status_lock.unlock(); - continue; - } - //finally, if they're valid, write them down - loads[worker] = peer_status->row_load; - peer_status->status_lock.unlock(); - } - //exit if all workers are finished - if(workers_finished >= worker_cnt - 1) { - return; - } - //then we look over and pick our canidates - for(;;) { - //find the worker who has the biggest workload - worker = distance(loads, max_element(loads, &loads[worker_cnt])); - if(!loads[worker]) break; //we have found a worker; distance is 0 - peer_status = &workers[worker]->status; - peer_status->status_lock.lock(); - //check to see if canidate is valid. - //TODO do we really need to check the first time? - if((peer_status->searching) || (peer_status->div_syn) || (peer_status->row_load < min_lines)) { - loads[worker] = 0; - peer_status->status_lock.unlock(); - continue; - } - ack = unique_lock(peer_status->ack_lk); - peer_status->div_syn = true; - peer_status->status_lock.unlock(); - peer_status->msg_notify.wait(ack); - ack.unlock(); - if(peer_status->div_error) { - loads[worker] = 0; - peer_status->status_lock.lock(); - peer_status->div_error = false; - peer_status->div_syn = false; - peer_status->status_lock.unlock(); - continue; - } - - divinfo = workers[worker]->divide(); - peer_status->syn_ack_lk.unlock(); - peer_status->msg_notify.notify_all(); - y_min = divinfo.y_min; - y_max = divinfo.y_max; - x_min = divinfo.x_min; - x_max = divinfo.x_max; - status.status_lock.lock(); - status.searching = false; - status.status_lock.unlock(); - break; - } - } - } -} - -struct mthread_divinfo mthread::divide() { - struct mthread_divinfo ret; - ret.x_min = x_min; - ret.x_max = x_max; - ret.y_min = ((y_max - on_y) / 2) + on_y; - ret.y_max = y_max; - y_min = on_y; - y_max = ret.y_min; - status.div_syn = false; - return ret; -} -- cgit v1.2.3