X-Git-Url: https://git.ucc.asn.au/?a=blobdiff_plain;f=course%2Fsemester2%2Fpprog%2Fassignment1%2Fmthread%2Fnbody.c;h=de9b8aaac241e4453025acdcafcc4ccf67528d64;hb=df06a43b2727b939ee572a1ddaa39e707aff030a;hp=cd0656af23f53fe84bcf48a734dc20ed0d5b5fd8;hpb=19cb61f75ddda901224f7ce2bae0d3934f67d9ee;p=matches%2Fhonours.git diff --git a/course/semester2/pprog/assignment1/mthread/nbody.c b/course/semester2/pprog/assignment1/mthread/nbody.c index cd0656af..de9b8aaa 100644 --- a/course/semester2/pprog/assignment1/mthread/nbody.c +++ b/course/semester2/pprog/assignment1/mthread/nbody.c @@ -1,213 +1,123 @@ /** * @file nbody.c - * @author Sam Moore (20503628) 2012 - * @purpose N-Body simulator - Definition of simulation functions; single threaded version + * @purpose Implentation of multi-threaded N-Body simulator using pthreads + * @author Sam Moore (20503628) - 2012 */ -#include -#include -#include -#include -#include -#include -#include -#include - -#include "nbody.h" - -//Stuff to do with worker threads -// The worker threads (if used) are spawned by the computation thread, not the main thread -// The main thread (which handles initialisation, graphics, user input, cleanup and exit) does not need to know about these. -#if NUM_THREADS > 1 - - pthread_t worker_thread[NUM_THREADS]; //Worker threads responsible for Force and Position updates - System sub_system[NUM_THREADS]; //Array of System's used to divide up the main "universe" System for worker threads - pthread_mutex_t mutex_workers; - pthread_cond_t workers_done_cv; - unsigned worker_count; -#endif +#include "nbody.h" // Declarations +#include "../single-thread/nbody.c" // Include all functions from the single threaded version -/** - * Prints the body on screen - */ -void Body_Print(Body * a) -{ - printf("Body %p M=%f X=%f Y=%f Z=%f Fx=%f Fy=%f Fz=%f Vx=%f Vy=%f Vz=%f\n", - (void*)a, a->mass, a->x[0], a->x[1], a->x[2], a->F[0], a->F[1], a->F[2], a->v[0], a->v[1], a->v[2]); -} +#include "graphics.h" // For declaration of Graphics_Run only -/** - * Computing forces - */ -void Body_Force(Body * a, System * s) -{ - double distance; - double con; - double gd; +// --- Variable declarations --- // - for (unsigned i = 0; i < DIMENSIONS; ++i) - a->F[i] = 0; +pthread_t compute_thread; // The thread responsible for computations; it spawns worker threads + +pthread_t * worker_thread = NULL; //Array of worker threads responsible for Force and Position updates +System * sub_system = NULL; //Array of Systems used to divide up the main "universe" System for worker threads +System * nested_sub_system = NULL; //Array of Systems for division of "universe" for the nested worker threads - for (unsigned index = 0; index < s->N; ++index) - { - Body * b = s->body+index; - if (b == a) - continue; - - distance = 0.0; - for (unsigned i = 0; i < DIMENSIONS; ++i) - distance += square(b->x[i] - a->x[i]); - distance = sqrt(distance); - con = G * a->mass * b->mass / square(distance); - gd = con / distance; - for (unsigned i = 0; i < DIMENSIONS; ++i) - a->F[i] += gd * (b->x[i] - a->x[i]); - } -} +pthread_mutex_t mutex_runstate; // Mutex around the runstate -/** - * Compute velocities - */ -void Body_Velocity(Body * a) -{ - for (unsigned i = 0; i < DIMENSIONS; ++i) - a->v[i] += a->F[i] / a->mass * DELTA_T; -} -/** - * Compute positions - */ -void Body_Position(Body * a) -{ - for (unsigned i = 0; i < DIMENSIONS; ++i) - a->x[i] += a->v[i] * DELTA_T; -} -/** - * Compute forces on each object in System s1 due to all bodies in System s2 - */ -void System_Forces(System * s1, System * s2) -{ - //printf("Compute forces for %p - %d bodies...\n", (void*)s1, s1->N); - for (unsigned i = 0; i < s1->N; ++i) - { - Body_Force(s1->body+i, s2); - Body_Velocity(s1->body+i); - } - //printf("Compute positions for %p - Done!\n", (void*)s1); -} +pthread_attr_t attr; //thread attribute for the workers. -/** - * Compute positions of all objects in System - */ -void System_Positions(System * s) -{ - //printf("Compute positions for %p - %d bodies...\n", (void*)s, s->N); - for (unsigned i = 0; i < s->N; ++i) - Body_Position(s->body+i); - //printf("Compute positions for %p - Done!\n", (void*)s); -} +Barrier force_barrier; // I laughed at this variable name. A bit sad really. +Barrier position_barrier; +Barrier graphics_barrier; -/* - * This function reads an input file. You can change it if you choose a - * different file format +/** + * @function Compute_Thread + * @purpose Thread - Continuously computes steps for a system of bodies. Seperate from graphics functions. + * Spawns worker threads to divide up computation. + * @param arg - Can be cast to the System for which computations are performed (ie: &universe) */ -#define LINE_SIZE BUFSIZ -void System_Init(System * s, char *fileName) +void * Compute_Thread(void * arg) { - char line[LINE_SIZE]; - char * token; - FILE * file; - file = fopen(fileName, "rt"); - s->N = atoi(fgets(line, LINE_SIZE, file)); - s->body = (Body*) calloc((size_t)s->N, sizeof(Body)); + System * s = (System*)(arg); //cast argument to a System* + - //printf("----------------------Initial field-------------------------------\n"); + // If no number of threads provided, use the default value, unless someone changed that to a stupid value + if (options.num_threads <= 0) + options.num_threads = (DEFAULT_WORKING_THREADS > 1) ? DEFAULT_WORKING_THREADS : 1; - for (unsigned i = 0; i < s->N; ++i) + if (options.nested_threads <= 0) + options.nested_threads = 1; + + // Do a sanity check; there is no point spawning more threads than bodies. + if (options.num_threads > s->N) { - if (fgets(line, LINE_SIZE, file) != NULL) - { - Body * a = s->body+i; - token = strtok(line, ",; "); - a->mass = atof(token); - - for (unsigned j = 0; j < DIMENSIONS; ++j) - { - token = strtok(NULL, ",; "); - a->x[j] = atof(token); - } - for (unsigned j = 0; j < DIMENSIONS; ++j) - { - token = strtok(NULL, ",; "); - a->v[j] = atof(token); - } - //Body_Print(a); - } + fprintf(stderr, + "Warning: Using %u threads instead of %u specified, because there are only %u bodies to simulate!\n", + s->N, options.num_threads, s->N); + options.num_threads = s->N; } - - //printf("--------------------------------------------------------------\n"); - fclose(file); -} - -/** - * Cleans up the universe by freeing all memory - */ -void Universe_Cleanup() -{ - free(universe.body); + pthread_attr_init(&attr); + pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED); //Needs to be detached, so that memory can be reused. -} + if (options.num_threads > 1) // Allocate worker threads and sub systems, as long as there would be more than 1 + { + worker_thread = Allocate_Threads(options.num_threads); + sub_system = Split_System(&universe, options.num_threads); -/** - * Thread - Continuously computes steps for a system of bodies - */ -void * Compute_Thread(void * arg) -{ + if (options.nested_threads > 1) + nested_sub_system = Split_System(&universe, options.nested_threads); - System * s = (System*)(arg); //cast argument to a System* - // First set up the "sub_system" array - #if NUM_THREADS > 1 - unsigned bodies_per_system = (s->N) / NUM_THREADS; - unsigned remainder = (s->N) % NUM_THREADS; - for (unsigned i = 0; i < NUM_THREADS; ++i) + #ifdef PERSISTENT_THREADS + for (unsigned i = 0; i < options.num_threads; ++i) { - sub_system[i].body = (s->body)+(i*bodies_per_system); - sub_system[i].N = bodies_per_system; - if (i == NUM_THREADS - 1) - sub_system[i].N += remainder; + if (pthread_create(worker_thread+i, & attr, Worker_Thread, (void*)(sub_system+i)) != 0) + { + perror("In compute thread, couldn't create worker thread"); + QuitProgram(true); + pthread_exit(NULL); + } } + #endif //PERSISTENT_THREADS - pthread_attr_t attr; //thread attribute for the workers - pthread_attr_init(&attr); - pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED); - - #endif - while (true) - { - if (runstate != RUN) pthread_exit(NULL); //Check whether the main thread wants to exit - + } + #ifdef PERSISTENT_THREADS + else + { + while (!ExitCondition()) + { + if (options.verbosity != 0 && universe.steps % options.verbosity == 1) + DisplayStatistics(); - - #if NUM_THREADS <= 1 - //No worker threads; do everything in this thread + // Just do everything in this thread System_Forces(s, s); System_Positions(s); - #else + } + QuitProgram(false); + pthread_exit(NULL); + } - + #else + // The main computation loop + while (!ExitCondition()) + { + if (options.verbosity != 0 && universe.steps % options.verbosity == 1) + DisplayStatistics(); + + if (options.num_threads <= 1) + { + // Just do everything in this thread + System_Forces(s, s); + System_Positions(s); + continue; + } - worker_count = NUM_THREADS; //All threads working //Compute forces - for (unsigned i = 0; i < NUM_THREADS; ++i) + for (unsigned i = 0; i < options.num_threads; ++i) { if (pthread_create(worker_thread+i, &attr, Force_Thread, (void*)(sub_system+i)) != 0) { @@ -215,20 +125,21 @@ void * Compute_Thread(void * arg) QuitProgram(true); pthread_exit(NULL); } + } + Barrier_Wait(&force_barrier); - //Wait for forces to be computed - pthread_mutex_lock(&mutex_workers); - while (worker_count > 0) - pthread_cond_wait(&workers_done_cv, &mutex_workers); - pthread_mutex_unlock(&mutex_workers); - - worker_count = NUM_THREADS; //All threads working + //All the forces are now computed + + if (options.draw_graphics && options.pedantic_graphics) + { + Barrier_Wait(&graphics_barrier); + } //Compute positions - for (unsigned i = 0; i < NUM_THREADS; ++i) + for (unsigned i = 0; i < options.num_threads; ++i) { if (pthread_create(worker_thread+i, &attr, Position_Thread, (void*)(sub_system+i)) != 0) { @@ -239,59 +150,331 @@ void * Compute_Thread(void * arg) } //Wait for positions to be computed - pthread_mutex_lock(&mutex_workers); - while (worker_count > 0) - pthread_cond_wait(&workers_done_cv, &mutex_workers); - pthread_mutex_unlock(&mutex_workers); + Barrier_Wait(&position_barrier); + + + //Update number of steps computed + universe.steps += 1; - #endif + + + } + QuitProgram(false); + #endif //PERSISTENT_THREADS + return NULL; } -void * Force_Thread(void * s) +/** + * @function BeforeDraw + * @purpose Called in graphics thread before the draw loop + * When --pedantic-graphics enabled, will wait for position computations to finish before drawing + * Otherwise does nothing + */ +void BeforeDraw() +{ + if (options.verbosity != 0 && universe.steps % options.verbosity == 0) + DisplayStatistics(); + //printf("BEFORE DRAW\n"); + if (!options.pedantic_graphics) + return; + + Barrier_Wait(&position_barrier); + + + Barrier_Enter(&graphics_barrier); +} + +/** + * @function AfterDraw + * @purpose Called in graphics thread after the draw loop + * When --pedantic-graphics is supplied, will signal computation thread that drawing is finished + * So that positions can be safely altered + * Otherwise does nothing + */ +void AfterDraw() { + universe.steps += 1; + if (!options.pedantic_graphics) + return; + Barrier_Leave(&graphics_barrier); - System_Forces((System*)s, &universe); - pthread_mutex_lock(&mutex_workers); - worker_count -= 1; - if (worker_count == 0) +} + +#ifdef PERSISTENT_THREADS + +/** + * @function Worker_Thread + * @purpose Thread - Calculate stuff + */ +void * Worker_Thread(void * arg) +{ + System * s = (System*)(arg); + + + pthread_t * nested_workers = NULL; + System_ForcePair * system_pairs = NULL; + System * nested_position = NULL; + + Barrier nested_barrier; + Barrier_Init(&nested_barrier); + + printf("options.nested_threads == %d\n", (int)(options.nested_threads)); + + if (options.nested_threads != 1) { - pthread_cond_signal(&workers_done_cv); + + system_pairs = (System_ForcePair*)(calloc(options.nested_threads, sizeof(System_ForcePair))); + if (system_pairs == NULL) // Handle tedious error cases + { + perror("Couldn't allocate array of system pairs"); + QuitProgram(true); + pthread_exit(NULL); + } + nested_workers = Allocate_Threads(options.nested_threads); + nested_position = + + for (unsigned i = 0; i < options.nested_threads; ++i) + { + system_pairs[i].A = s; + system_pairs[i].B = nested_sub_system+i; + } } - pthread_mutex_unlock(&mutex_workers); + + while (!ExitCondition()) + { + + if (options.nested_threads == 1) + { + Barrier_Enter(&force_barrier); + System_Forces(s, &universe); + Barrier_Leave(&force_barrier); + } + else + { + for (unsigned i = 0; i < options.nested_threads; ++i) + { + if (pthread_create(nested_workers+i, &attr, Force_Thread, (void*)(system_pairs+i)) != 0) + { + perror("In worker thread, couldn't create nested worker thread (force)"); + QuitProgram(true); + free(nested_workers); + pthread_exit(NULL); + } + } + } + //printf("Computed forces for %p\n", arg); + Barrier_Wait(&force_barrier); + //printf("Computed ALL forces\n"); + + if (options.draw_graphics && options.pedantic_graphics) + Barrier_Wait(&graphics_barrier); + + Barrier_Enter(&position_barrier); + + System_Positions(s); + + Barrier_Leave(&position_barrier); + //printf("Computed positions for %p\n", arg); + Barrier_Wait(&position_barrier); + //printf("Computed ALL positions\n"); + } + printf("Worker thread exits\n"); + QuitProgram(false); + pthread_exit(NULL); +} + +#endif //PERSISTENT_THREADS + +/** + * @function Force_Thread + * @purpose Thread - Calculates the forces on objects in a System + * @param s - Can be cast to the System* + */ +void * Force_Thread(void * s) +{ + System_ForcePair * pair = (System_ForcePair*)s; + Barrier_Enter(&force_barrier); + + System_Forces(pair->A, pair->B); //Simple wrapper + + Barrier_Leave(&force_barrier); + return NULL; } + +/** + * @function Position_Thread + * @purpose Thread - Calculates the positions of objects in a System + * @param s - Can be cast to the System* + */ void * Position_Thread(void * s) { - - System_Positions((System*)s); - pthread_mutex_lock(&mutex_workers); - worker_count -= 1; - if (worker_count == 0) - { - pthread_cond_signal(&workers_done_cv); - } - pthread_mutex_unlock(&mutex_workers); + Barrier_Enter(&position_barrier); + System_Positions((System*)s); // Simple wrapper + Barrier_Leave(&position_barrier); return NULL; } /** - * Child threads can call this to signal the main thread to quit the program - * The main thread also uses this to tell child threads that the program is quitting - * Note that the function doesn't call exit(), that is done by the main thread + * @function QuitProgram + * @purpose This function can either be called by the main thread in order to signal other threads + * that it wants to exit. The main thread then calls pthread_join before exiting. + * It can also be called by a child thread to request the main thread to exit. + * It is only used this way if there is an unrecovarable error (ie: Can't allocate memory in a child thread) */ void QuitProgram(bool error) { - - pthread_mutex_lock(&mutex_runstate); - if (error) + if (runstate == QUIT || runstate == QUIT_ERROR) + return; //Don't do anything if already quitting + pthread_mutex_lock(&mutex_runstate); // aquire mutex + if (error) // set the runstate runstate = QUIT_ERROR; else runstate = QUIT; - pthread_mutex_unlock(&mutex_runstate); + pthread_mutex_unlock(&mutex_runstate); //release mutex } +/** + * @function Thread_Cleanup + * @purpose Will be called in the main thread when exit() is called + * Automatically tells all other threads to quit (if they haven't already been told) + * Then waits for them to finish. + * Also frees memory associated with the worker threads. + */ +void Thread_Cleanup(void) +{ + if (runstate == RUN) // If this is true, as far as child threads are concerned, the simulation is still running + QuitProgram(false); // So call QuitProgram which will set runstate, and cause child threads to exit + pthread_join(compute_thread, NULL); + free(worker_thread); + free(sub_system); +} + + +/** + * @function Simulation_Run + * @purpose Initialise and start the simulation. Will be called in the main thread. + * Replaces the single-threaded macro that does nothing, and sets up the compute thread + * @param argc - Number of arguments - Passed to Graphics_Run if needed + * @param argv - Argument strings - Passed to Graphics_Run if needed + */ +void Simulation_Run(int argc, char ** argv) +{ + atexit(Thread_Cleanup); + + Barrier_Init(&force_barrier); + Barrier_Init(&position_barrier); + Barrier_Init(&graphics_barrier); + + + if (options.draw_graphics) + { + // The graphics are enabled, so create a thread to do computations + // Graphics are done in the main loop + //printf("Graphics are enabled\n"); + #ifdef PERSISTENT_THREADS + Compute_Thread((void*)(&universe)); + #else + if (pthread_create(&compute_thread, NULL, Compute_Thread, (void*)&universe) != 0) + { + perror("Error creating compute thread"); + exit(EXIT_FAILURE); + } + #endif //PERSISTENT_THREADS + //printf("Run compute thread\n"); + Graphics_Run(argc, argv); + } + else + + Compute_Thread((void*)(&universe)); // Graphics are disabled, so do computations in the main thread +} + + + +void Barrier_Init(Barrier * b) +{ + b->threads_busy = 0; +} + +void Barrier_Enter(Barrier * b) +{ + pthread_mutex_lock(&(b->mutex)); + b->threads_busy += 1; + pthread_mutex_unlock(&(b->mutex)); +} +void Barrier_Leave(Barrier * b) +{ + pthread_mutex_lock(&(b->mutex)); + b->threads_busy -= 1; + if (b->threads_busy == 0) + { + pthread_cond_signal(&(b->threads_done_cv)); + } + pthread_mutex_unlock(&(b->mutex)); +} + +void Barrier_Wait(Barrier * b) +{ + pthread_mutex_lock(&(b->mutex)); + while (b->threads_busy > 0) + pthread_cond_wait(&(b->threads_done_cv), &(b->mutex)); + pthread_mutex_unlock(&(b->mutex)); +} + +/** + * @function Split_System + * @purpose Helper to divide one system into an array of systems + * Each sub system will have N = (s->N / n) bodies in it + * @param s - The original system (typically &universe) + * @param n - The number of sub systems in the array + * + * WARNING: It is the caller's responsibility to free() the returned array + */ +System * Split_System(System * s, unsigned n) +{ + System * result = (System*)(calloc(n, sizeof(System))); + if (result == NULL) + { + perror("Couldn't create array of sub systems"); + QuitProgram(true); + pthread_exit(NULL); + } + + unsigned n_per_system = (s->N) / n; + unsigned remainder = (s->N) % n; + + for (unsigned i = 0; i < n; ++i) + { + result[i].N = n_per_system; + if (i == n-1) + result[i].N += remainder; + result[i].body = (s->body) + (n_per_system * i); + result[i].steps = 0; + } + return result; +} + +/** + * @function Allocate_Threads + * @purpose Helper function to allocate an array of pthread_t objects + * Handles all the pointless, er, "important" error checking that should be done + * @param n - Number of threads in the array + * + * WARNING: Remember to free() the array!!! + */ +pthread_t * Allocate_Threads(unsigned n) +{ + pthread_t * result = (pthread_t*)(calloc(n, sizeof(pthread_t))); + if (result == NULL) + { + perror("Unable to allocate memory for threads"); + QuitProgram(true); + pthread_exit(NULL); + } + return result; +}