quark.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdarg.h>
#include <string.h>
#include <limits.h>
#include <errno.h>
#include <pthread.h>
#include "icl_list.h"
#include "icl_hash.h"
#include "bsd_queue.h"
#include "bsd_tree.h"
#include "quark.h"
#include "quark_unpack_args.h"

Include dependency graph for quark.c:

Go to the source code of this file.

Classes
struct	quark_s
struct	Quark_sequence_s
struct	worker_s
struct	quark_task_s
struct	dependency_s
struct	scratch_s
struct	address_set_node_s
struct	ll_list_node_s
struct	completed_tasks_node_s
struct	task_priority_tree_node_s

Macros
#define	inline   __inline
#define	fopen(ppfile, name, mode)   *ppfile = fopen(name, mode)
#define	ULLONG_MAX   18446744073709551615ULL
#define	DIRECTION_MASK   0x07
#define	tasklevel_width_max_level   5000
#define	DEPCOLOR   "black"
#define	ANTIDEPCOLOR   "red"
#define	GATHERVDEPCOLOR   "green"
#define	DOT_DAG_FILENAME   "dot_dag_file.dot"
#define	dot_dag_level_update(parent_level, child_level, quark)
#define	dot_dag_print_edge(parentid, childid, color)

Typedefs
typedef struct worker_s	Worker
typedef struct quark_task_s	Task
typedef struct dependency_s	Dependency
typedef struct scratch_s	Scratch
typedef struct address_set_node_s	Address_Set_Node
typedef struct ll_list_node_s	ll_list_node_t
typedef struct ll_list_head_s	ll_list_head_t
typedef struct completed_tasks_node_s	completed_tasks_node_t
typedef struct completed_tasks_head_s	completed_tasks_head_t
typedef struct task_priority_tree_node_s	task_priority_tree_node_t
typedef struct task_priority_tree_head_s	task_priority_tree_head_t

Enumerations
enum	task_status {   NOTREADY, QUEUED, RUNNING, DONE,   CANCELLED }
enum	task_num { DGETRF, DTSTRF, DGESSM, DSSSM }
enum	bool { FALSE, TRUE }

Functions
int	quark_getenv_int (char *name, int defval)
	LIST_HEAD (ll_list_head_s, ll_list_node_s)
	TAILQ_HEAD (completed_tasks_head_s, completed_tasks_node_s)
	RB_HEAD (task_priority_tree_head_s, task_priority_tree_node_s)
static int	compare_task_priority_tree_nodes (task_priority_tree_node_t *n1, task_priority_tree_node_t *n2)
	RB_GENERATE (task_priority_tree_head_s, task_priority_tree_node_s, n_entry, compare_task_priority_tree_nodes)
static Task *	quark_task_new ()
static void	task_delete (Quark *quark, Task *task)
static Worker *	worker_new (Quark *quark, int rank)
static void	worker_delete (Worker *worker)
static int	quark_revolve_robin (Quark *quark)
static void	quark_insert_task_dependencies (Quark *quark, Task *task)
static void	quark_check_and_queue_ready_task (Quark *quark, Task *task)
static void	work_set_affinity_and_call_main_loop (Worker *worker)
static void	work_main_loop (Worker *worker)
static Scratch *	scratch_new (void *arg_ptr, int arg_size, icl_list_t *task_args_list_node_ptr)
static void	scratch_allocate (Task *task)
static void	scratch_deallocate (Task *task)
static void	address_set_node_delete (Quark *quark, Address_Set_Node *address_set_node)
static void	worker_remove_completed_task_enqueue_for_later_processing (Quark *quark, Task *task, int worker_rank)
static void	remove_completed_task_and_check_for_ready (Quark *quark, Task *task, int worker_rank)
static void	process_completed_tasks (Quark *quark)
int	quark_setaffinity (int rank)
void	quark_topology_init ()
void	quark_topology_finalize ()
int	quark_get_numthreads ()
int *	quark_get_affthreads ()
int	quark_yield ()
static int	pthread_mutex_lock_asn (pthread_mutex_t *mtx)
static int	pthread_mutex_trylock_asn (pthread_mutex_t *mtx)
static int	pthread_mutex_unlock_asn (pthread_mutex_t *mtx)
static int	pthread_mutex_lock_ready_list (pthread_mutex_t *mtx)
static int	pthread_mutex_trylock_ready_list (pthread_mutex_t *mtx)
static int	pthread_mutex_unlock_ready_list (pthread_mutex_t *mtx)
static int	pthread_mutex_lock_wrap (pthread_mutex_t *mtx)
static int	pthread_mutex_unlock_wrap (pthread_mutex_t *mtx)
static int	pthread_mutex_lock_completed_tasks (pthread_mutex_t *mtx)
static int	pthread_mutex_trylock_completed_tasks (pthread_mutex_t *mtx)
static int	pthread_mutex_unlock_completed_tasks (pthread_mutex_t *mtx)
static int	pthread_cond_wait_ready_list (pthread_cond_t *cond, pthread_mutex_t *mtx)
int	QUARK_Thread_Rank (Quark *quark)
void *	QUARK_Args_List (Quark *quark)
void *	QUARK_Args_Pop (void *args_list, void **last_arg)
static unsigned int	fnv_hash_function (void *key, int len)
static unsigned int	address_hash_function (void *address)
static int	address_key_compare (void *addr1, void *addr2)
static unsigned int	ullong_hash_function (void *key)
static int	ullong_key_compare (void *key1, void *key2)
static char *	arg_dup (char *arg, int size)
static Dependency *	dependency_new (void *addr, long long size, quark_direction_t dir, bool loc, Task *task, bool accumulator, bool gatherv, icl_list_t *task_args_list_node_ptr)
Quark *	QUARK_Setup (int num_threads)
Quark *	QUARK_New (int num_threads)
void	QUARK_Barrier (Quark *quark)
void	QUARK_Waitall (Quark *quark)
void	QUARK_Free (Quark *quark)
void	QUARK_Delete (Quark *quark)
Task *	quark_set_task_flags_in_task_structure (Quark *quark, Task *task, Quark_Task_Flags *task_flags)
Task *	QUARK_Task_Init (Quark *quark, void(*function)(Quark *), Quark_Task_Flags *task_flags)
void	QUARK_Task_Pack_Arg (Quark *quark, Task *task, int arg_size, void *arg_ptr, int arg_flags)
unsigned long long	QUARK_Insert_Task_Packed (Quark *quark, Task *task)
unsigned long long	QUARK_Insert_Task (Quark *quark, void(*function)(Quark *), Quark_Task_Flags *task_flags,...)
unsigned long long	QUARK_Execute_Task (Quark *quark, void(*function)(Quark *), Quark_Task_Flags *task_flags,...)
int	QUARK_Cancel_Task (Quark *quark, unsigned long long taskid)
static Address_Set_Node *	address_set_node_new (void *address, int size)
void	quark_avoid_war_dependencies (Quark *quark, Address_Set_Node *asn_old, Task *parent_task)
static void	address_set_node_initial_gatherv_check_and_launch (Quark *quark, Address_Set_Node *address_set_node, Dependency *completed_dep, int worker_rank)
static void	address_set_node_accumulator_find_prepend (Quark *quark, Address_Set_Node *address_set_node)
static void	address_set_node_initial_input_check_and_launch (Quark *quark, Address_Set_Node *address_set_node, Dependency *completed_dep, int worker_rank)
static void	address_set_node_initial_output_check_and_launch (Quark *quark, Address_Set_Node *address_set_node, Dependency *completed_dep, int worker_rank)
void	QUARK_Worker_Loop (Quark *quark, int thread_rank)
Quark_Sequence *	QUARK_Sequence_Create (Quark *quark)
int	QUARK_Sequence_Cancel (Quark *quark, Quark_Sequence *sequence)
Quark_Sequence *	QUARK_Sequence_Destroy (Quark *quark, Quark_Sequence *sequence)
int	QUARK_Sequence_Wait (Quark *quark, Quark_Sequence *sequence)
Quark_Sequence *	QUARK_Get_Sequence (Quark *quark)
char *	QUARK_Get_Task_Label (Quark *quark)
Quark_Task_Flags *	QUARK_Task_Flag_Set (Quark_Task_Flags *task_flags, int flag, intptr_t val)

Variables
static char *	quark_task_default_label = " "
static char *	quark_task_default_color = "white"
FILE *	dot_dag_file

---

Detailed Description

QUARK (QUeuing And Runtime for Kernels) provides a runtime enviornment for the dynamic execution of precedence-constrained tasks.

QUARK is a software package provided by Univ. of Tennessee, Univ. of California Berkeley and Univ. of Colorado Denver.

Version:

2.3.1

Author:

Asim YarKhan

Date:

2010-11-15

Definition in file quark.c.

---

Macro Definition Documentation

#define ANTIDEPCOLOR   "red"

Definition at line 294 of file quark.c.

#define DEPCOLOR   "black"

Definition at line 293 of file quark.c.

#define DIRECTION_MASK   0x07

Definition at line 91 of file quark.c.

#define DOT_DAG_FILENAME   "dot_dag_file.dot"

Definition at line 296 of file quark.c.

#define dot_dag_level_update	(		parent_level,
			child_level,
			quark
	)

Value:

if ( quark->dot_dag_enable ) {                                     \
        pthread_mutex_lock_wrap( &quark->dot_dag_mutex );                   \
        child_level = (parent_level+1 < child_level ? child_level : parent_level+1 );  \
        pthread_mutex_unlock_wrap( &quark->dot_dag_mutex ); }

Definition at line 298 of file quark.c.

#define dot_dag_print_edge	(		parentid,
			childid,
			color
	)

Value:

if ( quark->dot_dag_enable && parentid!=0 ) {                      \
        pthread_mutex_lock_wrap( &quark->dot_dag_mutex );                   \
        fprintf(dot_dag_file, "t%lld->t%lld [color=\"%s\"];\n", parentid, childid, color); \
        pthread_mutex_unlock_wrap( &quark->dot_dag_mutex );                 \
    }

Definition at line 303 of file quark.c.

#define fopen	(		ppfile,
			name,
			mode
	)		*ppfile = fopen(name, mode)

Definition at line 65 of file quark.c.

#define GATHERVDEPCOLOR   "green"

Definition at line 295 of file quark.c.

#define inline   __inline

Definition at line 57 of file quark.c.

#define tasklevel_width_max_level   5000

Definition at line 115 of file quark.c.

#define ULLONG_MAX   18446744073709551615ULL

Definition at line 85 of file quark.c.

---

Typedef Documentation

typedef struct address_set_node_s Address_Set_Node

typedef struct completed_tasks_head_s completed_tasks_head_t

Definition at line 214 of file quark.c.

typedef struct completed_tasks_node_s completed_tasks_node_t

typedef struct dependency_s Dependency

typedef struct ll_list_head_s ll_list_head_t

Definition at line 206 of file quark.c.

typedef struct ll_list_node_s ll_list_node_t

typedef struct scratch_s Scratch

typedef struct quark_task_s Task

typedef struct task_priority_tree_head_s task_priority_tree_head_t

Definition at line 224 of file quark.c.

typedef struct task_priority_tree_node_s task_priority_tree_node_t

typedef struct worker_s Worker

---

Enumeration Type Documentation

enum bool

Enumerator:

FALSE
TRUE

Definition at line 94 of file quark.c.

{ FALSE, TRUE } bool;

enum task_num

Enumerator:

DGETRF
DTSTRF
DGESSM
DSSSM

Definition at line 93 of file quark.c.

{ DGETRF, DTSTRF, DGESSM, DSSSM } task_num;

enum task_status

Enumerator:

NOTREADY
QUEUED
RUNNING
DONE
CANCELLED

Definition at line 92 of file quark.c.

{ NOTREADY, QUEUED, RUNNING, DONE, CANCELLED } task_status;

---

Function Documentation

static unsigned int address_hash_function ( void *  address )

inlinestatic

Hash function to map addresses, cut into "long" size chunks, then XOR. The result will be matched to hash table size using mod in the hash table implementation

Definition at line 456 of file quark.c.

References fnv_hash_function().

{
    int len = sizeof(void *);
    unsigned int hashval = fnv_hash_function( &address, len );
    return hashval;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int address_key_compare ( void *  addr1, void *  addr2  )

inlinestatic

Adress compare function for hash table

Definition at line 466 of file quark.c.

{
    return (addr1 == addr2);
}

Here is the caller graph for this function:

static void address_set_node_accumulator_find_prepend ( Quark *  quark, Address_Set_Node *  address_set_node  )

static

Called by a worker each time a task is removed from an address set node. Sweeps through a sequence of ACCUMULATOR tasks from the beginning and prepends one at the beginning if only one (chained) dependency remaining. This does not actually lauch the prepended task, it depends on another function to do that. Assumes address_set_mutex is locked.

Definition at line 1450 of file quark.c.

References dependency_s::accumulator, dependency_s::address_set_waiting_deps_node_ptr, icl_list_s::data, FALSE, icl_list_delete(), icl_list_first(), icl_list_next(), icl_list_prepend(), quark_task_s::num_dependencies_remaining, dependency_s::task, and address_set_node_s::waiting_deps.

{
    icl_list_t *dep_node = NULL;
    icl_list_t *first_dep_node = NULL;
    icl_list_t *first_ready_dep_node = NULL;
    icl_list_t *last_ready_dep_node = NULL;
    icl_list_t *last_dep_node = NULL;
    icl_list_t *swap_node = NULL;
    int acc_dep_count = 0;

    /* FOR each ACCUMULATOR task waiting at the beginning of address_set_node  */
    for (dep_node = icl_list_first(address_set_node->waiting_deps);
         dep_node != NULL;
         dep_node = icl_list_next( address_set_node->waiting_deps, dep_node )) {
        Dependency *dependency = (Dependency *)dep_node->data;
        /* IF not an ACCUMULATOR dependency - break */
        if (dependency->accumulator == FALSE) break;
        Task *task = dependency->task;
        /* Scan through list keeping first, first_ready, last_ready, last */
        if (first_dep_node==NULL) first_dep_node = dep_node;
        if ( task->num_dependencies_remaining==1 ) {
            if (first_ready_dep_node==NULL) first_ready_dep_node = dep_node;
            last_ready_dep_node = dep_node;
        }
        last_dep_node = dep_node; /* TODO */
        acc_dep_count++;
    }

    /* Choose and move chosen ready node to the front of the list */
    /* Heuristic: Flip-flop between first-ready and last-ready.
     * Tested (always first, always last, flip-flop first/last) but
     * there was always a bad scenario.  If perfect loop orders are
     * provided (e.g. Choleky inversion test) then this will not make
     * performance worse.  If bad loops are provided, this will
     * improve performance, though not to the point of perfect
     * loops.  */
    if (acc_dep_count % 2 == 0 ) {
        if ( last_ready_dep_node!=NULL ) swap_node = last_ready_dep_node;
    } else {
        if ( first_ready_dep_node != NULL ) swap_node = first_ready_dep_node;
    }
    if ( swap_node != NULL ) {
        Dependency *dependency = (Dependency *)swap_node->data;
        /* Move to front of the address_set_node waiting_deps list (if not already there) */
        if ( swap_node!=icl_list_first(address_set_node->waiting_deps) ) {
                icl_list_t *tmp_swap_node = icl_list_prepend( address_set_node->waiting_deps, dependency );
                dependency->address_set_waiting_deps_node_ptr = tmp_swap_node;
                icl_list_delete( address_set_node->waiting_deps, swap_node, NULL );
        }
        /* Lock the dependency in place by setting ACC to false now */
        dependency->accumulator = FALSE;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void address_set_node_delete ( Quark *  quark, Address_Set_Node *  address_set_node  )

static

Clean and free address set node structures.

Definition at line 1230 of file quark.c.

References address_set_node_s::address, quark_s::address_set, address_set_node_s::delete_data_at_address_when_node_is_deleted, quark_s::dot_dag_enable, icl_hash_delete(), icl_list_destroy(), TRUE, and address_set_node_s::waiting_deps.

{
    /* Free data if it was allocted as a WAR data copy */
    if ( address_set_node->delete_data_at_address_when_node_is_deleted == TRUE ) {
        free( address_set_node->address );
    }
    /* Do not free this structure if we are generating DAGs.  The
     * structure contains information about the last task to write the
     * data used to make DAG edges */
    if ( quark->dot_dag_enable )
        return;

    /* Remove any data structures in the waiting_deps list */
    if ( address_set_node->waiting_deps != NULL )
        icl_list_destroy( address_set_node->waiting_deps, NULL );
    /* Delete and free the hash table entry if this was NOT a WAR create entry */
    icl_hash_delete( quark->address_set, address_set_node->address, NULL, NULL );
    /* Remove the data structure */
    free( address_set_node );
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void address_set_node_initial_gatherv_check_and_launch ( Quark *  quark, Address_Set_Node *  address_set_node, Dependency *  completed_dep, int  worker_rank  )

static

Called by a worker each time a task is removed from an address set node. Sweeps through a sequence of GATHERV dependencies from the beginning, and enables them all. Assumes address_set_mutex is locked.

Definition at line 1413 of file quark.c.

References icl_list_s::data, dependency_s::direction, dot_dag_level_update, dot_dag_print_edge, FALSE, dependency_s::gatherv, GATHERVDEPCOLOR, icl_list_first(), icl_list_next(), INOUT, quark_task_s::num_dependencies_remaining, OUTPUT, quark_check_and_queue_ready_task(), dependency_s::ready, dependency_s::task, quark_task_s::taskid, quark_task_s::tasklevel, TRUE, and address_set_node_s::waiting_deps.

{
    icl_list_t *next_dep_node;
    Task *completed_task = completed_dep->task;
    for ( next_dep_node=icl_list_first(address_set_node->waiting_deps);
          next_dep_node!=NULL && next_dep_node->data != NULL;
          next_dep_node=icl_list_next(address_set_node->waiting_deps, next_dep_node) ) {
        Dependency *next_dep = (Dependency *)next_dep_node->data;
        /* Break when we run out of GATHERV output dependencies */
        if ( next_dep->gatherv==FALSE ) break;
        if ( next_dep->direction!=OUTPUT && next_dep->direction!=INOUT ) break;
        Task *next_task = next_dep->task;
        /* Update next_dep ready status */
        if ( next_dep->ready == FALSE ) {
            /* Record the locality information with the task data structure */
            //if ( next_dep->locality ) next_task->locality_preserving_dep = worker_rank;
            /* Mark the next dependency as ready since we have GATHERV flag */
            next_dep->ready = TRUE;
            dot_dag_print_edge( completed_task->taskid, next_task->taskid, GATHERVDEPCOLOR );
            dot_dag_level_update( completed_task->tasklevel, next_task->tasklevel, quark );
            next_task->num_dependencies_remaining--;
            /* If the dep status became true check related task, and put onto ready queues */
            quark_check_and_queue_ready_task( quark, next_task );
        }

    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void address_set_node_initial_input_check_and_launch ( Quark *  quark, Address_Set_Node *  address_set_node, Dependency *  completed_dep, int  worker_rank  )

static

Called by a worker each time a task is removed from an address set node. Sweeps through a sequence of initial INPUT dependencies on an address, and launches any that are ready to go. Assumes address_set_mutex is locked.

Definition at line 1512 of file quark.c.

References ANTIDEPCOLOR, icl_list_s::data, DEPCOLOR, dependency_s::direction, quark_s::dot_dag_enable, dot_dag_level_update, dot_dag_print_edge, FALSE, icl_list_first(), icl_list_next(), INOUT, INPUT, OUTPUT, quark_check_and_queue_ready_task(), dependency_s::ready, dependency_s::task, quark_task_s::taskid, quark_task_s::tasklevel, TRUE, and address_set_node_s::waiting_deps.

{
    icl_list_t *next_dep_node;
    Task *completed_task = completed_dep->task;
    for ( next_dep_node=icl_list_first(address_set_node->waiting_deps);
          next_dep_node!=NULL && next_dep_node->data != NULL;
          next_dep_node=icl_list_next(address_set_node->waiting_deps, next_dep_node) ) {
        Dependency *next_dep = (Dependency *)next_dep_node->data;
        Task *next_task = next_dep->task;
        /* Break when we hit an output dependency */
        if ( (next_dep->direction==OUTPUT || next_dep->direction==INOUT) ) {
            if ( completed_dep->direction == INPUT ) {
                /* Print DAG connections for antidependencies */
                dot_dag_print_edge( completed_task->taskid, next_task->taskid, ANTIDEPCOLOR );
                dot_dag_level_update( completed_task->tasklevel, next_task->tasklevel, quark );
            }
            break;
        }
        /* Update next_dep ready status; this logic assumes the breaks at the bottom */
        if ( next_dep->direction==INPUT && next_dep->ready == FALSE ) {
            /* Record the locality information with the task data structure */
            //if ( next_dep->locality ) next_task->locality_thread_id = worker_rank;
            /* If next_dep is INPUT, mark the next dependency as ready */
            next_dep->ready = TRUE;
            /* Only OUTPUT->INPUT edges get here */
            dot_dag_print_edge( completed_task->taskid, next_task->taskid, DEPCOLOR );
            dot_dag_level_update( completed_task->tasklevel, next_task->tasklevel, quark );
            next_task->num_dependencies_remaining--;
            /* If the dep status became true check related task, and put onto ready queues */
            quark_check_and_queue_ready_task( quark, next_task );
        }

        /* if we are generating the DAG, keep looping till an output
         * dependency (in order to print all WAR edges) */
        if (! quark->dot_dag_enable ) {
            /* If current original dependency (dep) was INPUT, we only need to
             * activate next INPUT/OUTPUT/INOUT dep, others should already be
             * handled; if original dep was OUTPUT/INOUT, need to keep
             * going till next OUTPUT/INOUT */
            if ( completed_dep->direction == INPUT ) break;
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void address_set_node_initial_output_check_and_launch ( Quark *  quark, Address_Set_Node *  address_set_node, Dependency *  completed_dep, int  worker_rank  )

static

Called by a worker each time a task is removed from an address set node. Checks any initial OUTPUT/INOUT dependencies on an address, and launches any tasks that are ready to go. Assumes address_set_mutex is locked.

Definition at line 1564 of file quark.c.

References icl_list_s::data, DEPCOLOR, dependency_s::direction, dot_dag_level_update, dot_dag_print_edge, FALSE, icl_list_first(), INOUT, OUTPUT, quark_check_and_queue_ready_task(), dependency_s::ready, dependency_s::task, quark_task_s::taskid, quark_task_s::tasklevel, TRUE, and address_set_node_s::waiting_deps.

{
    icl_list_t *next_dep_node;
    next_dep_node = icl_list_first(address_set_node->waiting_deps);
    if ( next_dep_node!=NULL && next_dep_node->data!=NULL ) {
        Dependency *next_dep = (Dependency *)next_dep_node->data;
        Task *next_task = next_dep->task;
        if ( (next_dep->direction==OUTPUT || next_dep->direction==INOUT) ) {
            /* Process OUTPUT next_deps, if at beginning of address_set_list waiting_deps starts  */
            if ( next_dep->ready == FALSE ) {
                /* Record the locality information with the task data structure */
                //if ( next_dep->locality ) next_task->locality_thread_id = worker_rank;
                /* If next_dep is output, mark the next dep as ready only if it is at the front */
                next_dep->ready = TRUE;
                Task *completed_task = completed_dep->task;
                if ( completed_dep->direction==OUTPUT || completed_dep->direction==INOUT )
                    dot_dag_print_edge( completed_task->taskid, next_task->taskid, DEPCOLOR );
                /*  else                      */ /* Handled in initial_input_check_and_launch */
                /*     dot_dag_print_edge( completed_task->taskid, next_task->taskid, ANTIDEPCOLOR ); */
                dot_dag_level_update( completed_task->tasklevel, next_task->tasklevel, quark );
                next_task->num_dependencies_remaining--;
                quark_check_and_queue_ready_task( quark, next_task );
            }
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static Address_Set_Node* address_set_node_new ( void *  address, int  size  )

static

Allocate and initialize address_set_node structure. These are inserted into the hash table.

Definition at line 1206 of file quark.c.

References address_set_node_s::address, address_set_node_s::delete_data_at_address_when_node_is_deleted, FALSE, icl_list_new(), address_set_node_s::last_reader_or_writer_taskid, address_set_node_s::last_reader_or_writer_tasklevel, address_set_node_s::last_thread, address_set_node_s::last_writer_taskid, address_set_node_s::last_writer_tasklevel, address_set_node_s::num_waiting_inout, address_set_node_s::num_waiting_input, address_set_node_s::num_waiting_output, address_set_node_s::size, and address_set_node_s::waiting_deps.

{
    Address_Set_Node *address_set_node = (Address_Set_Node *)malloc(sizeof(Address_Set_Node));
    assert( address_set_node != NULL );
    address_set_node->address = address;
    address_set_node->size = size;
    address_set_node->last_thread = -1;
    address_set_node->waiting_deps = icl_list_new();
    assert( address_set_node->waiting_deps != NULL );
    address_set_node->num_waiting_input = 0;
    address_set_node->num_waiting_output = 0;
    address_set_node->num_waiting_inout = 0;
    address_set_node->delete_data_at_address_when_node_is_deleted = FALSE;
    address_set_node->last_writer_taskid = 0;
    address_set_node->last_writer_tasklevel = 0;
    address_set_node->last_reader_or_writer_taskid = 0;
    address_set_node->last_reader_or_writer_tasklevel = 0;
    return address_set_node;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static char* arg_dup ( char *  arg, int  size  )

inlinestatic

Duplicate the argument, allocating a memory buffer for it

Definition at line 509 of file quark.c.

{
    char *argbuf = (char *) malloc(size);
    assert( argbuf != NULL );
    memcpy(argbuf, arg, size);
    return argbuf;
}

Here is the caller graph for this function:

static int compare_task_priority_tree_nodes ( task_priority_tree_node_t *  n1, task_priority_tree_node_t *  n2  )

static

Definition at line 225 of file quark.c.

{
    return n2->priority - n1->priority;
}

static Dependency* dependency_new ( void *  addr, long long  size, quark_direction_t  dir, bool  loc, Task *  task, bool  accumulator, bool  gatherv, icl_list_t *  task_args_list_node_ptr  )

inlinestatic

Allocate and initialize a dependency structure

Definition at line 521 of file quark.c.

References dependency_s::accumulator, dependency_s::address, dependency_s::address_set_node_ptr, dependency_s::address_set_waiting_deps_node_ptr, dependency_s::direction, FALSE, dependency_s::gatherv, INOUT, dependency_s::locality, quark_task_s::locality_preserving_dep, OUTPUT, dependency_s::ready, dependency_s::size, dependency_s::task, dependency_s::task_args_list_node_ptr, and dependency_s::task_dependency_list_node_ptr.

{
    Dependency *dep = (Dependency *) malloc(sizeof(Dependency));
    assert(dep != NULL);
    dep->task = task;
    dep->address = addr;
    dep->size = size;
    dep->direction = dir;
    dep->locality = loc;
    dep->accumulator = accumulator;
    dep->gatherv = gatherv;
    dep->address_set_node_ptr = NULL; /* convenience ptr, filled later */
    dep->address_set_waiting_deps_node_ptr = NULL; /* convenience ptr, filled later */
    dep->task_args_list_node_ptr = task_args_list_node_ptr; /* convenience ptr for WAR address updating */
    dep->task_dependency_list_node_ptr = NULL; /* convenience ptr */
    dep->ready = FALSE;
    /* For the task, track the dependency to be use to do locality
     * preservation; by default, use first output dependency.  */
    if ( dep->locality )
        task->locality_preserving_dep = dep;
    else if ( (task->locality_preserving_dep == NULL) && ( dep->direction==OUTPUT || dep->direction==INOUT) )
        task->locality_preserving_dep = dep;
    return dep;
}

Here is the caller graph for this function:

static unsigned int fnv_hash_function ( void *  key, int  len  )

inlinestatic

Well known hash function: Fowler/Noll/Vo - 32 bit version

Definition at line 440 of file quark.c.

{
    unsigned char *p = key;
    unsigned int h = 2166136261u;
    int i;
    for ( i = 0; i < len; i++ )
        h = ( h * 16777619 ) ^ p[i];
    return h;
}

Here is the caller graph for this function:

LIST_HEAD	(	ll_list_head_s	,
		ll_list_node_s
	)

static void process_completed_tasks ( Quark *  quark )

static

Handle the queue of completed tasks.

Definition at line 2032 of file quark.c.

References quark_s::address_set_mutex, quark_s::completed_tasks, quark_s::completed_tasks_mutex, pthread_mutex_trylock_asn(), pthread_mutex_trylock_completed_tasks(), pthread_mutex_unlock_asn(), pthread_mutex_unlock_completed_tasks(), remove_completed_task_and_check_for_ready(), TAILQ_FIRST, TAILQ_REMOVE, completed_tasks_node_s::task, and completed_tasks_node_s::workerid.

{
    completed_tasks_node_t *node = NULL;
    do {
        node = NULL;
        if ( pthread_mutex_trylock_asn( &quark->address_set_mutex ) == 0 ) {
            if ( pthread_mutex_trylock_completed_tasks( &quark->completed_tasks_mutex ) == 0 ) {
                node = TAILQ_FIRST(quark->completed_tasks);
                if ( node!= NULL ) TAILQ_REMOVE( quark->completed_tasks, node, entries );
                pthread_mutex_unlock_completed_tasks( &quark->completed_tasks_mutex );
            }
            if ( node != NULL ) {
                remove_completed_task_and_check_for_ready( quark, node->task, node->workerid );
                free( node );
            }
            pthread_mutex_unlock_asn( &quark->address_set_mutex );
        }
    } while ( node != NULL );
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_cond_wait_ready_list ( pthread_cond_t *  cond, pthread_mutex_t *  mtx  )

inlinestatic

Definition at line 284 of file quark.c.

References pthread_cond_wait().

{ return pthread_cond_wait( cond, mtx ); }

Here is the call graph for this function:

static int pthread_mutex_lock_asn ( pthread_mutex_t *  mtx )

inlinestatic

Mutex wrappers for tracing/timing purposes. Makes it easier to profile the costs of these pthreads routines.

Definition at line 269 of file quark.c.

References pthread_mutex_lock().

{ return pthread_mutex_lock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_mutex_lock_completed_tasks ( pthread_mutex_t *  mtx )

inlinestatic

Definition at line 280 of file quark.c.

References pthread_mutex_lock().

{ return pthread_mutex_lock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_mutex_lock_ready_list ( pthread_mutex_t *  mtx )

inlinestatic

Definition at line 273 of file quark.c.

References pthread_mutex_lock().

{ return pthread_mutex_lock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_mutex_lock_wrap ( pthread_mutex_t *  mtx )

inlinestatic

Definition at line 277 of file quark.c.

References pthread_mutex_lock().

{ return pthread_mutex_lock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_mutex_trylock_asn ( pthread_mutex_t *  mtx )

inlinestatic

Definition at line 270 of file quark.c.

References pthread_mutex_trylock().

{ return pthread_mutex_trylock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_mutex_trylock_completed_tasks ( pthread_mutex_t *  mtx )

inlinestatic

Definition at line 281 of file quark.c.

References pthread_mutex_trylock().

{ return pthread_mutex_trylock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_mutex_trylock_ready_list ( pthread_mutex_t *  mtx )

inlinestatic

Definition at line 274 of file quark.c.

References pthread_mutex_trylock().

{ return pthread_mutex_trylock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_mutex_unlock_asn ( pthread_mutex_t *  mtx )

inlinestatic

Definition at line 271 of file quark.c.

References pthread_mutex_unlock().

{ return pthread_mutex_unlock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_mutex_unlock_completed_tasks ( pthread_mutex_t *  mtx )

inlinestatic

Definition at line 282 of file quark.c.

References pthread_mutex_unlock().

{ return pthread_mutex_unlock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_mutex_unlock_ready_list ( pthread_mutex_t *  mtx )

inlinestatic

Definition at line 275 of file quark.c.

References pthread_mutex_unlock().

{ return pthread_mutex_unlock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

static int pthread_mutex_unlock_wrap ( pthread_mutex_t *  mtx )

inlinestatic

Definition at line 278 of file quark.c.

References pthread_mutex_unlock().

{ return pthread_mutex_unlock( mtx ); }

Here is the call graph for this function:

Here is the caller graph for this function:

void quark_avoid_war_dependencies	(	Quark *	quark,
		Address_Set_Node *	asn_old,
		Task *	parent_task
	)

Routine to avoid false (WAR write-after-read) dependencies by making copies of the data. Check if there are suffient INPUTS in the beginning of a address dependency followed by a OUTPUT or an INOUT (data<-RRRRW). If so, make a copy of the data, adjust the pointers of the read dependencies to point to the new copy (copy<-RRRR and data<-W) and send to workers if the tasks are ready. The copy can be automacally freed when all the reads are done. The write can proceed at once. The address_set_mutex is already locked when this is called.

Definition at line 1314 of file quark.c.

References dependency_s::address, address_set_node_s::address, quark_s::address_set, address_set_node_new(), dependency_s::address_set_node_ptr, dependency_s::address_set_waiting_deps_node_ptr, icl_list_s::data, address_set_node_s::delete_data_at_address_when_node_is_deleted, DEPCOLOR, dependency_s::direction, DONE, dot_dag_level_update, dot_dag_print_edge, FALSE, icl_hash_insert(), icl_list_append(), icl_list_delete(), icl_list_first(), icl_list_next(), INOUT, INPUT, quark_s::low_water_mark, NOTREADY, quark_task_s::num_dependencies_remaining, quark_s::num_queued_tasks, quark_s::num_tasks, quark_s::num_threads, address_set_node_s::num_waiting_input, OUTPUT, quark_check_and_queue_ready_task(), quark_getenv_int(), dependency_s::ready, address_set_node_s::size, quark_task_s::status, dependency_s::task, dependency_s::task_args_list_node_ptr, quark_task_s::taskid, quark_task_s::tasklevel, TRUE, address_set_node_s::waiting_deps, and quark_s::war_dependencies_enable.

{
    /* Figure out if there are enough input dependencies to make this worthwhile */
    int count_initial_input_deps = 0;
    bool output_dep_reached = FALSE;
    double avg_queued_tasks_per_thread = (double)quark->num_queued_tasks/(double)quark->num_threads;
    double avg_tasks_per_thread = (double)quark->num_tasks/(double)quark->num_threads;
    int min_input_deps;
    icl_list_t *dep_node_old;

    /* Quick return if this is not enabled */
    if ( !quark->war_dependencies_enable ) return;

    /* TODO This stuff is still under development.... */
    if ( avg_queued_tasks_per_thread < 0.4 ) min_input_deps = 1;
    else if ( avg_queued_tasks_per_thread < 0.75 ) min_input_deps = 6;
    else if ( avg_queued_tasks_per_thread < 0.90 ) min_input_deps = 7;
    else if ( avg_queued_tasks_per_thread < 1.20 ) min_input_deps = 10;
    else if ( avg_queued_tasks_per_thread > 1.80 ) min_input_deps = 2000;
    else if ( avg_tasks_per_thread < (double)quark->low_water_mark/(double)quark->num_threads/2 ) min_input_deps = 2000;
    else min_input_deps = (int)(7 + 27 * avg_queued_tasks_per_thread);

    /* Override computed value using environment variable */
    min_input_deps = quark_getenv_int( "QUARK_AVOID_WAR_WHEN_NUM_WAITING_READS", min_input_deps );

    /* Shortcut return if there are not enough input tasks */
    if ( asn_old->num_waiting_input < min_input_deps ) return;

    /* Scan thru initial deps, make sure they are inputs and that there
     * are enough of them to make data copying worthwhile */
    for (dep_node_old=icl_list_first(asn_old->waiting_deps);
         dep_node_old!=NULL;
         dep_node_old=icl_list_next(asn_old->waiting_deps, dep_node_old)) {
        Dependency *dep = (Dependency *)dep_node_old->data;
        Task *task = dep->task;
        if ( dep->direction==INPUT && task->status==NOTREADY  ) {
            count_initial_input_deps++;
        } else if ( (dep->direction==OUTPUT || dep->direction==INOUT) && task->status!=DONE ) {
            output_dep_reached = TRUE;
            break;
        }
    }

    /* if ( count_initial_input_deps>=quark->min_input_deps_to_avoid_war_dependencies && output_dep_reached ) { */
    if ( count_initial_input_deps>=min_input_deps && output_dep_reached ) {
        icl_list_t *dep_node_asn_old;
        Address_Set_Node *asn_new;
        /* Allocate and copy data */
        void *datacopy = malloc( asn_old->size );
        assert(datacopy!=NULL);
        /* TODO track the allocated memory in datacopies */
        /* quark->mem_allocated_to_war_dependency_data += asn_old->size; */
        memcpy( datacopy, asn_old->address, asn_old->size );
        /* Create address set node, attach to hash, and set it to clean up when done */
        asn_new = address_set_node_new( datacopy, asn_old->size );
        asn_new->delete_data_at_address_when_node_is_deleted = TRUE;
        icl_hash_insert( quark->address_set, asn_new->address, asn_new );
        /* Update task dependences to point to this new data */
        /* Grab input deps from the old list, copy to new list, delete, then repeat */
        for ( dep_node_asn_old=icl_list_first(asn_old->waiting_deps);
              dep_node_asn_old!=NULL;  ) {
            icl_list_t *dep_node_asn_old_to_be_deleted = NULL;
            Dependency *dep = (Dependency *)dep_node_asn_old->data;
            Task *task = dep->task;
            if ( dep->direction==INPUT && task->status==NOTREADY ) {
                dep_node_asn_old_to_be_deleted = dep_node_asn_old;
                icl_list_t *dep_node_new = icl_list_append( asn_new->waiting_deps, dep );
                asn_new->num_waiting_input++;
                /* In the args list, set the arg pointer to the new datacopy address */
                *(void **)dep->task_args_list_node_ptr->data = datacopy;
                dep->address = asn_new->address;
                dep->address_set_node_ptr = asn_new;
                dep->address_set_waiting_deps_node_ptr = dep_node_new;
                if (dep->ready == FALSE) { /* dep->ready will always be FALSE */
                    dep->ready = TRUE;
                    dot_dag_print_edge( parent_task->taskid, task->taskid, DEPCOLOR );
                    dot_dag_level_update( parent_task->tasklevel, task->tasklevel, quark );
                    task->num_dependencies_remaining--;
                    quark_check_and_queue_ready_task( quark, task );
                }
            } else if ( (dep->direction==OUTPUT || dep->direction==INOUT) && task->status!=DONE ) {
                /* Once we return from this routine, this dep dependency will be processed */
                break;
            }
            dep_node_asn_old = icl_list_next(asn_old->waiting_deps, dep_node_asn_old);
            if (dep_node_asn_old_to_be_deleted!=NULL) {
                icl_list_delete(asn_old->waiting_deps, dep_node_asn_old_to_be_deleted, NULL);
            }
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void quark_check_and_queue_ready_task ( Quark *  quark, Task *  task  )

static

Queue ready tasks on a worker node, either using locality information or a round robin scheme. The address_set_mutex should be set when calling this, since we touch the task data structure (task->status) and update the quark->num_queued_tasks.

Definition at line 1258 of file quark.c.

References dependency_s::address_set_node_ptr, DONE, address_set_node_s::last_thread, quark_task_s::locality_preserving_dep, quark_task_s::lock_to_thread, quark_task_s::num_dependencies_remaining, quark_s::num_queued_tasks, quark_s::num_queued_tasks_cond, quark_s::num_threads, quark_task_s::priority, task_priority_tree_node_s::priority, pthread_cond_broadcast(), pthread_mutex_lock_ready_list(), pthread_mutex_unlock_ready_list(), quark_revolve_robin(), QUEUED, RB_INSERT, worker_s::ready_list, worker_s::ready_list_mutex, worker_s::ready_list_size, RUNNING, quark_task_s::status, task_priority_tree_node_s::task, and quark_s::worker.

{
    int worker_thread_id = -1;
    Worker *worker = NULL;
    int assigned_thread_count = 0;

    if ( task->num_dependencies_remaining > 0 || task->status == QUEUED || task->status == RUNNING || task->status == DONE) return;
    task->status = QUEUED;
    /* Assign task to thread.  Locked tasks get sent to appropriate
     * thread.  Locality tasks should have be correctly placed.  Tasks
     * without either should have the original round robin thread
     * assignment */
    if ( task->lock_to_thread >= 0) {
        worker_thread_id = task->lock_to_thread % quark->num_threads;
    } else if ( task->locality_preserving_dep != NULL ) {
        int last_thread = task->locality_preserving_dep->address_set_node_ptr->last_thread;
        if ( last_thread >= 0 ) worker_thread_id = last_thread;
    }
    if ( worker_thread_id < 0 ) worker_thread_id = quark_revolve_robin(quark);

    /* Handle tasks that need multiple threads */
    while ( assigned_thread_count < task->task_thread_count) {

        worker = quark->worker[worker_thread_id];
        /* Create a new entry for the ready list */
        task_priority_tree_node_t *new_task_tree_node = malloc(sizeof(task_priority_tree_node_t));
        assert( new_task_tree_node != NULL );
        new_task_tree_node->priority = task->priority;
        new_task_tree_node->task = task;
        /* Insert new entry into the ready list */
        pthread_mutex_lock_ready_list(&worker->ready_list_mutex);
        RB_INSERT( task_priority_tree_head_s, worker->ready_list, new_task_tree_node );
        worker->ready_list_size++;
        pthread_mutex_unlock_ready_list(&worker->ready_list_mutex);
        pthread_cond_broadcast( &quark->num_queued_tasks_cond );
        quark->num_queued_tasks++;

        assigned_thread_count++;
        /* TODO Abort when too many threads requested */
        if ( assigned_thread_count < task->task_thread_count )
            worker_thread_id = (worker_thread_id+1) % quark->num_threads;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int* quark_get_affthreads

(

)

Definition at line 245 of file quarkos.c.

References CONTEXT_THREADS_MAX, QUARK_CLEANENV, and QUARK_GETENV.

                             {
    char *envstr = NULL;
    int i;
    
    int *coresbind = (int *)malloc(CONTEXT_THREADS_MAX*sizeof(int));
    /* Env variable does not exist, we search the system number of core */
    QUARK_GETENV("QUARK_AFF_THREADS", envstr);
    if ( envstr == NULL) {
        for (i = 0; i < CONTEXT_THREADS_MAX; i++)
            coresbind[i] = i % sys_corenbr;
    }
    else {
        char *endptr;
        int   wrap = 0;
        int   nbr  = 0;
        long int val;

        /* We use the content of the QUARK_AFF_THREADS env. variable */
        for (i = 0; i < CONTEXT_THREADS_MAX; i++) {
            if (!wrap) {
                val = strtol(envstr, &endptr, 10);
                if (endptr != envstr) {
                    coresbind[i] = (int)val;
                    envstr = endptr;
                }
                else {
                    /* there must be at least one entry */
                    if (i < 1) {
                        //quark_error("quark_get_affthreads", "QUARK_AFF_THREADS should have at least one entry => everything will be bind on core 0");
                        fprintf(stderr, "quark_get_affthreads: QUARK_AFF_THREADS should have at least one entry => everything will be bind on core 0");
                        coresbind[i] = 0;
                        i++;
                    }

                    /* there is no more values in the string                                 */
                    /* the next threads are binded with a round robin policy over this array */
                    wrap = 1;
                    nbr = i;

                    coresbind[i] = coresbind[0];
                }
            }
            else {
                coresbind[i] = coresbind[i % nbr];
            }
        }
    }
    QUARK_CLEANENV(envstr);
    /* return QUARK_SUCCESS; */
    return coresbind;
}

Here is the caller graph for this function:

int quark_get_numthreads

(

)

---

Check for an integer in an environment variable, returning the integer value or a provided default value

Definition at line 222 of file quarkos.c.

References QUARK_CLEANENV, QUARK_GETENV, and sys_corenbr.

{
    char    *envstr  = NULL;
    char    *endptr;
    long int thrdnbr = -1;
    extern int errno;

    /* Env variable does not exist, we search the system number of core */
    QUARK_GETENV("QUARK_NUM_THREADS", envstr);
    if ( envstr == NULL ) {
        thrdnbr = sys_corenbr;
    } else {
        /* Convert to long, checking for errors */
        thrdnbr = strtol(envstr, &endptr, 10);
        if ((errno == ERANGE) || ((thrdnbr==0) && (endptr==envstr))) {
            QUARK_CLEANENV(envstr);
            return -1;
        }
    }
    QUARK_CLEANENV(envstr);
    return (int)thrdnbr;
}

Here is the caller graph for this function:

int quark_getenv_int	(	char *	name,
		int	defval
	)

---

Definition at line 300 of file quarkos.c.

References QUARK_CLEANENV, and QUARK_GETENV.

{
    char    *envstr  = NULL;
    char    *endptr;
    long int longval = -1;
    extern int errno;

    QUARK_GETENV(name, envstr);
    if ( envstr == NULL ) {
        longval = defval;
    } else {
        /* Convert to long, checking for errors */
        longval = strtol(envstr, &endptr, 10);
        if ((errno == ERANGE) || ((longval==0) && (endptr==envstr))) {
            longval = defval;
        }
    }
    QUARK_CLEANENV(envstr);
    return (int)longval;
}

Here is the caller graph for this function:

static void quark_insert_task_dependencies ( Quark *  quark, Task *  task  )

static

Called by the master insert task dependencies into the hash table. Any tasks that are ready to run are queued. The address_set_mutex must be locked before calling this routine.

Definition at line 1597 of file quark.c.

References dependency_s::address, quark_s::address_set, address_set_node_new(), dependency_s::address_set_node_ptr, dependency_s::address_set_waiting_deps_node_ptr, icl_list_s::data, DEPCOLOR, quark_task_s::dependency_list, dependency_s::direction, dot_dag_level_update, dot_dag_print_edge, FALSE, icl_hash_find(), icl_hash_insert(), icl_list_append(), icl_list_delete(), icl_list_first(), icl_list_next(), icl_list_prev(), INOUT, INPUT, quark_task_s::num_dependencies_remaining, OUTPUT, quark_avoid_war_dependencies(), dependency_s::ready, dependency_s::size, dependency_s::task, dependency_s::task_dependency_list_node_ptr, quark_task_s::taskid, quark_task_s::tasklevel, and TRUE.

{
    icl_list_t *task_dep_p = NULL; /* task dependency list pointer */

    /* For each task dependency list pointer */
    for (task_dep_p = icl_list_first(task->dependency_list);
         task_dep_p != NULL;
         task_dep_p = icl_list_next(task->dependency_list, task_dep_p)) {
        Dependency *dep = (Dependency *) task_dep_p->data;
        /* Lookup address in address_set hash */
        Address_Set_Node *address_set_node = (Address_Set_Node *)icl_hash_find( quark->address_set, dep->address );
        /* If not found, create a new address set node and add it to the hash */
        if ( address_set_node == NULL ) {
            address_set_node = address_set_node_new( dep->address, dep->size );
            icl_hash_insert( quark->address_set, address_set_node->address, address_set_node );
        }
        /* Convenience shortcut pointer so that we don't have to hash again */
        dep->address_set_node_ptr = address_set_node;
        /* Add the dependency to the list of waiting dependencies on this address set node */
        icl_list_t *curr_dep_node = icl_list_append( address_set_node->waiting_deps, dep );
        /* Convenience shortcut pointer so we don't have to scan the waiting dependencies */
        dep->address_set_waiting_deps_node_ptr = curr_dep_node;
        /* Track num of waiting input, output and inout to be used to check false dependency resolution */
        if (dep->direction == INPUT) address_set_node->num_waiting_input++;
        else if (dep->direction == OUTPUT) address_set_node->num_waiting_output++;
        else if (dep->direction == INOUT) address_set_node->num_waiting_inout++;

        /* Handle the case that the a single task make multiple dependencies on the same data address */
        /* e.g. func( A11:IN, A11:INOUT, A11:OUT, A11:IN, A22:OUT )  */
        icl_list_t *prev_dep_node = icl_list_prev( address_set_node->waiting_deps, curr_dep_node);
        if ( prev_dep_node != NULL ) {
            Dependency *prev_dep = (Dependency *)prev_dep_node->data;
            Task *prev_task = prev_dep->task;
            if ( prev_task->taskid == task->taskid ) {
                /* The curr dependency will updated using the ordering INPUT < OUTPUT < INOUT  */
                /* When the scheduler checks the front of the dependency list, it will find the correct dep setting */
                dep->direction = (dep->direction > prev_dep->direction ? INOUT : prev_dep->direction );
                if ( prev_dep->ready == FALSE ) {
                    prev_dep->ready = TRUE;
                    task->num_dependencies_remaining--;
                }
                /* Remove the redundent dependency from waiting deps and from the task */
                icl_list_delete( address_set_node->waiting_deps, prev_dep_node, NULL );
                icl_list_delete( task->dependency_list, prev_dep->task_dependency_list_node_ptr, NULL );
                /* Update the prev_dep_node ptr since it has changed */
                prev_dep_node = icl_list_prev( address_set_node->waiting_deps, curr_dep_node);
            }
        }

        /* This will avoid WAR dependencies if possible: if enabled, and
         * the current dependency is a write, and there were only reads
         * earlier (input>1, output+inout=1) */
        if ( ((dep->direction==OUTPUT || dep->direction==INOUT)) &&
             ((address_set_node->num_waiting_output + address_set_node->num_waiting_inout) == 1) ) {
            quark_avoid_war_dependencies( quark, address_set_node, task );
        }

        /* The following code decides whether the dep is ready or not */
        if ( dep->direction==INOUT || dep->direction==OUTPUT ) {
            /* If output, and previous dep exists, then ready=false */
            if ( prev_dep_node != NULL ) {
                dep->ready = FALSE;
            } else {
                dep->ready = TRUE;
                dot_dag_print_edge( address_set_node->last_reader_or_writer_taskid, task->taskid, DEPCOLOR );
                dot_dag_level_update( address_set_node->last_reader_or_writer_tasklevel, task->tasklevel, quark );
                task->num_dependencies_remaining--;
            }
        } else if ( dep->direction == INPUT ) {
            if ( prev_dep_node != NULL ) {
                /* If input, and previous dep is a read that is ready, then ready=true */
                Dependency *prev_dep = (Dependency *)prev_dep_node->data;
                if ( prev_dep->direction==INPUT && prev_dep->ready==TRUE ) {
                    dep->ready = TRUE;
                    dot_dag_print_edge( address_set_node->last_writer_taskid, task->taskid, DEPCOLOR );
                    dot_dag_level_update( address_set_node->last_writer_tasklevel, task->tasklevel, quark );
                    task->num_dependencies_remaining--;
                } else {
                    dep->ready = FALSE;
                }
            } else {
                /* Input, but no previous node (is first), so ready   */
                dep->ready = TRUE;
                dot_dag_print_edge( address_set_node->last_writer_taskid, task->taskid, DEPCOLOR );
                dot_dag_level_update( address_set_node->last_writer_tasklevel, task->tasklevel, quark );
                task->num_dependencies_remaining--;
            }
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int quark_revolve_robin ( Quark *  quark )

inlinestatic

Rotate the next worker queue that will get a task assigned to it. The master (0) never gets round-robin tasks assigned to it.

Definition at line 495 of file quark.c.

References quark_s::list_robin, and quark_s::num_threads.

{
    quark->list_robin++;
    if (quark->list_robin == quark->num_threads)
        quark->list_robin = 0;
    if (quark->list_robin==0 && quark->num_threads>1)
        quark->list_robin = 1;
    return quark->list_robin;
}

Here is the caller graph for this function:

Task* quark_set_task_flags_in_task_structure	(	Quark *	quark,
		Task *	task,
		Quark_Task_Flags *	task_flags
	)

Use the task_flags data structure to set various items in the task (priority, lock_to_thread, color, labels, etc )

Definition at line 868 of file quark.c.

References quark_s::dot_dag_enable, quark_task_s::lock_to_thread, quark_task_s::priority, quark_task_s::sequence, quark_task_flags_s::task_color, quark_task_s::task_color, quark_task_flags_s::task_label, quark_task_s::task_label, quark_task_flags_s::task_lock_to_thread, quark_task_flags_s::task_priority, quark_task_flags_s::task_sequence, quark_task_flags_s::task_thread_count, and quark_task_s::task_thread_count.

{
    if ( task_flags ) {
        if ( task_flags->task_priority ) task->priority = task_flags->task_priority;
        if ( task_flags->task_lock_to_thread >= 0 ) task->lock_to_thread = task_flags->task_lock_to_thread;
        if ( task_flags->task_color && quark->dot_dag_enable ) task->task_color = strdup(task_flags->task_color);
        if ( task_flags->task_label && quark->dot_dag_enable ) task->task_label = strdup(task_flags->task_label);
        if ( task_flags->task_sequence ) task->sequence = task_flags->task_sequence;
        if ( task_flags->task_thread_count > 1 ) task->task_thread_count = task_flags->task_thread_count;
    }
    return task;
}

Here is the caller graph for this function:

int quark_setaffinity

(

int

rank

)

This routine will set affinity for the calling thread that has rank 'rank'. Ranks start with 0.

If there are multiple instances of QUARK then affinity will be wrong: all ranks 0 will be pinned to core 0.

Also, affinity is not resotred when QUARK_Finalize() is called.

Definition at line 125 of file quarkos.c.

References QUARK_ERR_NOT_SUPPORTED, QUARK_ERR_UNEXPECTED, and QUARK_SUCCESS.

                                {
#ifndef QUARK_AFFINITY_DISABLE
#if (defined QUARK_OS_LINUX)
    {
        cpu_set_t set;
        CPU_ZERO( &set );
        CPU_SET( rank, &set );

#if (defined HAVE_OLD_SCHED_SETAFFINITY)
        if( sched_setaffinity( 0, &set ) < 0 )
#else /* HAVE_OLD_SCHED_SETAFFINITY */
        if( sched_setaffinity( 0, sizeof(set), &set) < 0 )
#endif /* HAVE_OLD_SCHED_SETAFFINITY */
            {
                return QUARK_ERR_UNEXPECTED;
            }

        return QUARK_SUCCESS;
    }
#elif (defined QUARK_OS_MACOS)
    {
        thread_affinity_policy_data_t ap;
        int                           ret;

        ap.affinity_tag = 1; /* non-null affinity tag */
        ret = thread_policy_set( mach_thread_self(),
                                 THREAD_AFFINITY_POLICY,
                                 (integer_t*) &ap,
                                 THREAD_AFFINITY_POLICY_COUNT
            );
        if(ret != 0)
            return QUARK_ERR_UNEXPECTED;

        return QUARK_SUCCESS;
    }
#elif (defined QUARK_OS_WINDOWS)
    {
        DWORD mask = 1 << rank;

        if( SetThreadAffinityMask(GetCurrentThread(), mask) == 0)
            return QUARK_ERR_UNEXPECTED;

        return QUARK_SUCCESS;
    }
#elif (defined QUARK_OS_AIX)
    {
        tid_t self_ktid = thread_self ();
        bindprocessor(BINDTHREAD, self_ktid, rank);
        return QUARK_SUCCESS;
    }
#else
    return QUARK_ERR_NOT_SUPPORTED;
#endif
#endif /* QUARK_AFFINITY_DISABLE */
    return QUARK_ERR_NOT_SUPPORTED;
}

Here is the caller graph for this function:

static Task * quark_task_new ( )

static

Local function prototypes, declared static so they are not available outside the scope of this file.

Initialize the task data structure

Definition at line 314 of file quark.c.

References quark_task_s::args_list, quark_task_s::dependency_list, quark_task_s::function, icl_list_new(), quark_task_s::locality_preserving_dep, quark_task_s::lock_to_thread, NOTREADY, quark_task_s::num_dependencies, quark_task_s::num_dependencies_remaining, quark_task_s::priority, pthread_mutex_init(), quark_task_s::ptr_to_task_in_sequence, quark_task_default_color, quark_task_default_label, QUARK_TASK_MIN_PRIORITY, quark_task_s::scratch_list, quark_task_s::sequence, quark_task_s::status, quark_task_s::task_color, quark_task_s::task_label, quark_task_s::task_mutex, quark_task_s::task_thread_count, quark_task_s::taskid, quark_task_s::tasklevel, and ULLONG_MAX.

{
    static unsigned long long taskid = 1;
    Task *task = (Task *)malloc(sizeof(Task));
    assert(task != NULL);
    task->function = NULL;
    task->num_dependencies = 0;
    task->num_dependencies_remaining = 0;
    task->args_list = icl_list_new();
    assert(task->args_list != NULL);
    task->dependency_list = icl_list_new();
    assert(task->dependency_list != NULL);
    task->locality_preserving_dep = NULL;
    task->status = NOTREADY;
    task->scratch_list = icl_list_new();
    assert( task->scratch_list != NULL);
    assert( taskid < ULLONG_MAX );
    task->taskid = taskid++;
    task->tasklevel = 0;
    pthread_mutex_init(&task->task_mutex, NULL);
    task->ptr_to_task_in_sequence = NULL;
    task->sequence = NULL;
    task->priority = QUARK_TASK_MIN_PRIORITY;
    task->task_label = quark_task_default_label;
    task->task_color = quark_task_default_color;
    task->lock_to_thread = -1;
    task->task_thread_count = 1;
    return task;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int QUARK_Thread_Rank

(

Quark *

quark

)

Return the rank of a thread

Definition at line 377 of file quark.c.

References quark_s::num_threads, pthread_equal(), pthread_self(), worker_s::thread_id, and quark_s::worker.

{
    pthread_t self_id = pthread_self();
    int  i;
    for (i=0; i<quark->num_threads; i++)
        if (pthread_equal(quark->worker[i]->thread_id, self_id))
            return i;
    return -1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void quark_topology_finalize

(

)

Definition at line 114 of file quarkos.c.

{}

Here is the caller graph for this function:

void quark_topology_init

(

)

Definition at line 78 of file quarkos.c.

References pthread_mutex_lock(), and pthread_mutex_unlock().

                          {
    pthread_mutex_lock(&mutextopo);
    if ( !topo_initialized ) {
#if (defined QUARK_OS_LINUX) || (defined QUARK_OS_AIX)

        sys_corenbr = sysconf(_SC_NPROCESSORS_ONLN);

#elif (defined QUARK_OS_MACOS)

        int mib[4];
        int cpu;
        size_t len = sizeof(cpu);

        /* set the mib for hw.ncpu */
        mib[0] = CTL_HW;
        mib[1] = HW_AVAILCPU;

        /* get the number of CPUs from the system */
        sysctl(mib, 2, &cpu, &len, NULL, 0);
        if( cpu < 1 ) {
            mib[1] = HW_NCPU;
            sysctl( mib, 2, &cpu, &len, NULL, 0 );
        }
        if( cpu < 1 ) {
            cpu = 1;
        }
        sys_corenbr = cpu;
#elif (defined QUARK_OS_WINDOWS)
        SYSTEM_INFO sysinfo;
        GetSystemInfo(&sysinfo);
        sys_corenbr = sysinfo.dwNumberOfProcessors;
#endif
    }
    pthread_mutex_unlock(&mutextopo);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int quark_yield

(

)

---

A thread can unlock the CPU if it has nothing to do to let another thread of less priority running for example for I/O.

Definition at line 187 of file quarkos.c.

References QUARK_ERR_NOT_SUPPORTED.

                  {
#if (defined QUARK_OS_LINUX) || (defined QUARK_OS_MACOS) || (defined QUARK_OS_AIX)
    return sched_yield();
#elif QUARK_OS_WINDOWS
    return SleepEx(0,0);
#else
    return QUARK_ERR_NOT_SUPPORTED;
#endif
}

RB_GENERATE	(	task_priority_tree_head_s	,
		task_priority_tree_node_s	,
		n_entry	,
		compare_task_priority_tree_nodes
	)

RB_HEAD	(	task_priority_tree_head_s	,
		task_priority_tree_node_s
	)

static void remove_completed_task_and_check_for_ready ( Quark *  quark, Task *  task, int  worker_rank  )

static

Handle a single completed task, finding its children and putting the children that are ready to go (all dependencies satisfied) into worker ready queues.

Definition at line 2058 of file quark.c.

References address_set_node_accumulator_find_prepend(), address_set_node_delete(), address_set_node_initial_gatherv_check_and_launch(), address_set_node_initial_input_check_and_launch(), address_set_node_initial_output_check_and_launch(), dependency_s::address_set_node_ptr, dependency_s::address_set_waiting_deps_node_ptr, icl_list_s::data, quark_task_s::dependency_list, dependency_s::direction, quark_s::dot_dag_enable, quark_s::dot_dag_mutex, icl_list_delete(), icl_list_first(), icl_list_next(), INOUT, INPUT, address_set_node_s::last_thread, quark_s::num_queued_tasks, OUTPUT, pthread_mutex_lock_wrap(), pthread_mutex_unlock_wrap(), quark_avoid_war_dependencies(), quark_task_s::task_color, task_delete(), quark_task_s::task_label, quark_task_s::taskid, quark_task_s::tasklevel, quark_s::tasklevel_width, and quark_s::war_dependencies_enable.

{
    if ( quark->dot_dag_enable ) {
        pthread_mutex_lock_wrap( &quark->dot_dag_mutex );
        if (task->tasklevel < 1) task->tasklevel=1;
        fprintf(dot_dag_file, "t%lld [fillcolor=\"%s\",label=\"%s\",style=filled];\n", task->taskid, task->task_color, task->task_label);
        /* Track the width of each task level */
        quark->tasklevel_width[task->tasklevel]++;
        /* fprintf(dot_dag_file, "// critical-path depth %ld \n", task->tasklevel ); */
        fprintf(dot_dag_file, "{rank=same;%lld;t%lld};\n", task->tasklevel, task->taskid );
        pthread_mutex_unlock_wrap( &quark->dot_dag_mutex );
    }

    /* For each dependency in the task that was completed */
    icl_list_t *dep_node;
    for (dep_node = icl_list_first(task->dependency_list);
         dep_node != NULL &&  dep_node->data!=NULL;
         dep_node = icl_list_next(task->dependency_list, dep_node)) {
        Dependency  *dep = (Dependency *)dep_node->data;
        Address_Set_Node *address_set_node = dep->address_set_node_ptr;

        /* Mark the address/data as having been written by worker_rank  */
        if ( dep->direction==OUTPUT || dep->direction==INOUT )
            address_set_node->last_thread = worker_rank;
        if ( quark->dot_dag_enable ) {
            if ( dep->direction==OUTPUT || dep->direction==INOUT ) {
                /* Track last writer and level, needed when this structure becomes empty */
                address_set_node->last_writer_taskid = task->taskid;
                address_set_node->last_writer_tasklevel = task->tasklevel;
            }
            address_set_node->last_reader_or_writer_taskid = task->taskid;
            address_set_node->last_reader_or_writer_tasklevel = task->tasklevel;
        }
        /* Check the address set node to avoid WAR dependencies; if
         * just completed a write, and at least one more write
         * (sum>=2) is pending */
        if ( (quark->war_dependencies_enable) &&
             (dep->direction==OUTPUT || dep->direction==INOUT) &&
             ((address_set_node->num_waiting_output + address_set_node->num_waiting_inout) >= 2) ) {
            quark_avoid_war_dependencies( quark, address_set_node, task );
        }
        /* Remove competed dependency from address_set_node waiting_deps list */
        icl_list_delete( address_set_node->waiting_deps, dep->address_set_waiting_deps_node_ptr, NULL );
        /* Check initial INPUT next_deps attached to address_set_node */
        address_set_node_initial_input_check_and_launch( quark, address_set_node, dep, worker_rank );
       /* Handle any initial GATHERV dependencies */
       address_set_node_initial_gatherv_check_and_launch(quark, address_set_node, dep, worker_rank);
        /* Prepend any initial accumulater dependency that is ready to go */
        address_set_node_accumulator_find_prepend( quark, address_set_node );
        /* Check initial OUTPUT/INOUT deps waiting on address_set_node  */
        address_set_node_initial_output_check_and_launch( quark, address_set_node, dep, worker_rank );
        /* Keep track of the waiting dependency counts for this address */
        if (dep->direction == INPUT) address_set_node->num_waiting_input--;
        else if (dep->direction == OUTPUT) address_set_node->num_waiting_output--;
        else if (dep->direction == INOUT) address_set_node->num_waiting_inout--;

        /* If this address_set_node has no more waiting_deps, remove it */
        if ( icl_list_first(address_set_node->waiting_deps) == NULL )
            address_set_node_delete( quark, address_set_node );
    }

    task_delete(quark, task);
    quark->num_queued_tasks--;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void scratch_allocate ( Task *  task )

static

Allocate any needed scratch space;

Definition at line 605 of file quark.c.

References icl_list_s::data, icl_list_first(), icl_list_next(), scratch_s::ptr, quark_task_s::scratch_list, scratch_s::size, and scratch_s::task_args_list_node_ptr.

{
    icl_list_t *scr_node;
    for (scr_node = icl_list_first( task->scratch_list );
         scr_node != NULL && scr_node->data != NULL;
         scr_node = icl_list_next(task->scratch_list, scr_node)) {
        Scratch *scratch = (Scratch *)scr_node->data;
        if ( scratch->ptr == NULL ) {
            /* Since ptr is null, space is to be allocted and attached */
            assert( scratch->size > 0 );
            void *scratchspace = malloc( scratch->size );
            assert( scratchspace != NULL );
            *(void **)scratch->task_args_list_node_ptr->data = scratchspace;
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void scratch_deallocate ( Task *  task )

static

Deallocate any scratch space.

Definition at line 626 of file quark.c.

References icl_list_s::data, icl_list_first(), icl_list_next(), scratch_s::ptr, quark_task_s::scratch_list, and scratch_s::task_args_list_node_ptr.

{
    icl_list_t *scr_node;
    for (scr_node = icl_list_first( task->scratch_list );
         scr_node != NULL && scr_node->data!=NULL;
         scr_node = icl_list_next(task->scratch_list, scr_node)) {
        Scratch *scratch = (Scratch *)scr_node->data;
        if ( scratch->ptr == NULL ) {
            /* If scratch had to be allocated, free it */
            free(*(void **)scratch->task_args_list_node_ptr->data);
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static Scratch * scratch_new ( void *  arg_ptr, int  arg_size, icl_list_t *  task_args_list_node_ptr  )

static

The task requires scratch workspace, which will be allocated if needed. This records the scratch requirements.

Definition at line 591 of file quark.c.

References scratch_s::ptr, scratch_s::size, and scratch_s::task_args_list_node_ptr.

{
    Scratch *scratch = (Scratch *)malloc(sizeof(Scratch));
    assert(scratch != NULL);
    scratch->ptr = arg_ptr;
    scratch->size = arg_size;
    scratch->task_args_list_node_ptr = task_args_list_node_ptr;
    return(scratch);
}

Here is the caller graph for this function:

TAILQ_HEAD	(	completed_tasks_head_s	,
		completed_tasks_node_s
	)

static void task_delete ( Quark *  quark, Task *  task  )

static

Free the task data structure

Definition at line 348 of file quark.c.

References quark_task_s::args_list, quark_task_s::dependency_list, icl_hash_delete(), icl_list_destroy(), LIST_REMOVE, quark_s::num_tasks, pthread_mutex_destroy(), pthread_mutex_lock_wrap(), pthread_mutex_unlock_wrap(), quark_task_s::ptr_to_task_in_sequence, quark_task_s::scratch_list, quark_task_s::sequence, Quark_sequence_s::sequence_mutex, quark_task_s::task_color, quark_task_s::task_label, quark_task_s::task_mutex, quark_s::task_set, quark_s::task_set_mutex, and quark_task_s::taskid.

{
    pthread_mutex_lock_wrap( &quark->task_set_mutex );
    icl_hash_delete( quark->task_set, &task->taskid, NULL, NULL );
    pthread_mutex_lock_wrap( &task->task_mutex );
    pthread_mutex_unlock_wrap( &quark->task_set_mutex );
    icl_list_destroy(task->args_list, free);
    icl_list_destroy(task->dependency_list, free);
    icl_list_destroy(task->scratch_list, free);
    if ( task->ptr_to_task_in_sequence != NULL ) {
        pthread_mutex_lock_wrap( &task->sequence->sequence_mutex );
        LIST_REMOVE( task->ptr_to_task_in_sequence, entries );
        pthread_mutex_unlock_wrap( &task->sequence->sequence_mutex );
        free( task->ptr_to_task_in_sequence );
    }
    if (task->task_color!=NULL && task->task_color!=quark_task_default_color) free(task->task_color);
    if (task->task_label!=NULL && task->task_label!=quark_task_default_label) free(task->task_label);
    pthread_mutex_unlock_wrap( &task->task_mutex );
    pthread_mutex_destroy( &task->task_mutex );
    free( task );
    // TODO pthread_mutex_lock_asn( &quark->address_set_mutex );
    quark->num_tasks--;
    // TODO pthread_mutex_unlock_asn( &quark->address_set_mutex );
}

Here is the call graph for this function:

Here is the caller graph for this function:

static unsigned int ullong_hash_function ( void *  key )

inlinestatic

Hash function for unsigned long longs (used for taskid)

Definition at line 475 of file quark.c.

References fnv_hash_function().

{
    int len = sizeof(unsigned long long);
    unsigned int hashval = fnv_hash_function( key, len );
    return hashval;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int ullong_key_compare ( void *  key1, void *  key2  )

inlinestatic

Compare unsigned long longs for hash keys (used for taskid)

Definition at line 485 of file quark.c.

{
    return ( *(unsigned long long*)key1 == *(unsigned long long*)key2 );
}

Here is the caller graph for this function:

static void work_main_loop ( Worker *  worker )

static

Called by the workers (and master) to continue executing tasks until some exit condition is reached.

Definition at line 1732 of file quark.c.

References quark_s::all_tasks_queued, CANCELLED, worker_s::current_task_ptr, DONE, worker_s::executing_task, FALSE, worker_s::finalize, quark_task_s::function, quark_task_s::lock_to_thread, quark_s::num_queued_tasks, quark_s::num_threads, process_completed_tasks(), pthread_mutex_lock_wrap(), pthread_mutex_trylock_ready_list(), pthread_mutex_unlock_ready_list(), pthread_mutex_unlock_wrap(), worker_s::quark_ptr, QUARK_Thread_Rank(), quark_s::queue_before_computing, RB_MAX, RB_MIN, RB_REMOVE, worker_s::ready_list, worker_s::ready_list_mutex, worker_s::ready_list_size, RUNNING, scratch_allocate(), scratch_deallocate(), quark_s::start, quark_task_s::status, task_priority_tree_node_s::task, quark_task_s::task_mutex, TRUE, quark_s::worker, and worker_remove_completed_task_enqueue_for_later_processing().

{
    Quark *quark = worker->quark_ptr;
    Worker *worker_victim = NULL;
    task_priority_tree_node_t *task_priority_tree_node = NULL;
    Task *task = NULL;
    int ready_list_victim = -1;

    /* Busy wait while not ready */
    do {} while ( !quark->start );
    int worker_rank = QUARK_Thread_Rank(quark);

    /* Queue all tasks before running; this line for debugging use */
    /* while ( !quark->all_tasks_queued ) { if (worker_rank==0) return; else {} } */
    if ( quark->queue_before_computing )
        while ( !quark->all_tasks_queued ) { if (worker_rank==0) return; else {} }
    /* Master never does work; this line for debugging use  */
    /* if (worker_rank == 0) return; */

    while ( !worker->finalize ) {
        /* Repeatedly try to find a task, first trying my own ready list,
         * then trying to steal from someone else */
        task = NULL;
        ready_list_victim = worker_rank;
        /* Loop while looking for tasks */
        while ( task==NULL && !worker->finalize ) {

            /* Process all completed tasks before doing work */
            if ( worker_rank==0 || worker_rank%10==1 ) process_completed_tasks(quark);

            worker_victim = quark->worker[ready_list_victim];
            task_priority_tree_node = NULL;
            assert ( worker_victim->ready_list_size >= 0 );
            if ( worker_victim->ready_list_size != 0 ) {
                /* Only lock if there is likely to be an item in the ready list */
                if ( pthread_mutex_trylock_ready_list( &worker_victim->ready_list_mutex ) == 0) {
                    /* if (pthread_mutex_lock_ready_list(&worker_victim->ready_list_mutex)==0) { */
                    /* Check front of my own queue, back of everyone else's queue */
                    if ( worker_rank == ready_list_victim )
                        task_priority_tree_node = RB_MIN( task_priority_tree_head_s, worker_victim->ready_list );
                    else if ( worker_rank!=ready_list_victim && worker_victim->executing_task==TRUE )
                        task_priority_tree_node = RB_MAX( task_priority_tree_head_s, worker_victim->ready_list );
                    else
                        task_priority_tree_node = NULL;
                    /* Access task, checking to make sure it is not pinned to a thread */
                    if ( task_priority_tree_node != NULL ) {
                        task = task_priority_tree_node->task;
                        /* If task should be locked to a thread, and this is not that thread, set task to NULL and continue */
                        if ( task->lock_to_thread>=0 && task->lock_to_thread!=worker_rank) {
                            task = NULL;
                        } else {
                            /* If task found, remove it from the ready list */
                            RB_REMOVE( task_priority_tree_head_s, worker_victim->ready_list, task_priority_tree_node );
                            free( task_priority_tree_node );
                            worker_victim->ready_list_size--;
                        }
                    }
                    pthread_mutex_unlock_ready_list( &worker_victim->ready_list_mutex );
                }
            }
            /* If no task found */
            if (task == NULL) {
                /* Choose the next victim queue */
                ready_list_victim = (ready_list_victim + 1) % quark->num_threads;
                /* Break for master when a scan of all queues is finished and no tasks were found */
                if ( worker_rank==0 && ready_list_victim==0 ) break;
                /* If there are no tasks, wait for a task to be introduced, then check own queue first */
                if ( quark->num_queued_tasks==0 && !worker->finalize && worker_rank!=0 )  {
                    do { assert( quark->num_queued_tasks >= 0); } while ( quark->num_queued_tasks==0 && !worker->finalize ) ;
                    ready_list_victim = worker_rank;
                }
            }
        }
        /* EXECUTE THE TASK IF FOUND */
        if ( task!=NULL ) {
            //if ( quark->num_tasks != 1 ) { printf("quark->num_tasks %d %d %d\n", quark->num_tasks, quark->low_water_mark, quark->high_water_mark ); abort(); }
            pthread_mutex_lock_wrap( &task->task_mutex );
            if ( task->function == NULL ) {
                /* This can occur if the task is cancelled */
                task->status = CANCELLED;
                pthread_mutex_unlock_wrap( &task->task_mutex );
            } else {
                /* Call the task */
                worker->executing_task = TRUE;
                task->status = RUNNING;
                pthread_mutex_unlock_wrap( &task->task_mutex );
                scratch_allocate( task );
                worker->current_task_ptr = task;
                task->function( quark );
                scratch_deallocate( task );
                task->status = DONE;
                worker->executing_task = FALSE;
            }
            /* Remove the task from the address hash */
            /* Original solution */
            //pthread_mutex_lock_asn(&quark->address_set_mutex);
            //worker_remove_completed_task_and_check_for_ready(quark, task, worker_rank);
            //pthread_mutex_unlock_asn(&quark->address_set_mutex);
            /* New version */
            worker_remove_completed_task_enqueue_for_later_processing(quark, task, worker_rank);
        }
        /* Break if master */
        if ( worker_rank==0 && ready_list_victim==0 ) break;
    }
    /* Worker has exited loop; ready for next time this worker is activated */
    worker->finalize = FALSE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void work_set_affinity_and_call_main_loop ( Worker *  worker )

static

Called when spawning the worker thread to set affinity to specific core and then call the main work loop. This function is used internally, when the scheduler spawns and manages the threads. If an external driver is using the scheduler (e.g. PLASMA) then it does the thread management and any affinity must be set in the external driver.

Definition at line 1718 of file quark.c.

References quark_s::coresbind, worker_s::quark_ptr, quark_setaffinity(), QUARK_Thread_Rank(), work_main_loop(), and quark_s::worker.

{
    Quark *quark = worker->quark_ptr;
    int thread_rank = QUARK_Thread_Rank(quark);
    quark_setaffinity( quark->coresbind[thread_rank] ) ;
    work_main_loop( quark->worker[thread_rank] );
    return;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void worker_delete ( Worker *  worker )

static

Cleanup and free worker data structures

Definition at line 572 of file quark.c.

References pthread_mutex_destroy(), RB_MIN, RB_NEXT, RB_REMOVE, worker_s::ready_list, and worker_s::ready_list_mutex.

{
    task_priority_tree_node_t *node, *nxt;
    /* Destroy the workers priority queue, if there is still anything there */
    for ( node = RB_MIN( task_priority_tree_head_s, worker->ready_list ); node != NULL; node = nxt) {
        nxt = RB_NEXT( task_priority_tree_head_s, worker->ready_list, node );
        RB_REMOVE( task_priority_tree_head_s, worker->ready_list, node );
        free(node);
    }
    free( worker->ready_list );
    pthread_mutex_destroy(&worker->ready_list_mutex);
    free(worker);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static Worker * worker_new ( Quark *  quark, int  rank  )

static

Allocate and initialize a worker structure

Definition at line 550 of file quark.c.

References worker_s::current_task_ptr, worker_s::executing_task, FALSE, worker_s::finalize, pthread_mutex_init(), pthread_self(), worker_s::quark_ptr, RB_INIT, worker_s::ready_list, worker_s::ready_list_mutex, worker_s::ready_list_size, and worker_s::thread_id.

{
    Worker *worker = (Worker *) malloc(sizeof(Worker));
    assert(worker != NULL);
    worker->thread_id = pthread_self();
    worker->ready_list = malloc(sizeof(task_priority_tree_head_t));
    assert(worker->ready_list != NULL);
    RB_INIT( worker->ready_list );
    worker->ready_list_size = 0;
    pthread_mutex_init(&worker->ready_list_mutex, NULL);
    /* convenience pointer to the real args for the task  */
    worker->current_task_ptr = NULL;
    worker->quark_ptr = quark;
    worker->finalize = FALSE;
    worker->executing_task = FALSE;
    return worker;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void worker_remove_completed_task_enqueue_for_later_processing ( Quark *  quark, Task *  task, int  worker_rank  )

static

When a task is completed, queue it for further handling by another process.

Definition at line 2012 of file quark.c.

References quark_s::completed_tasks, quark_s::completed_tasks_mutex, pthread_mutex_lock_completed_tasks(), pthread_mutex_lock_wrap(), pthread_mutex_unlock_completed_tasks(), pthread_mutex_unlock_wrap(), TAILQ_INSERT_TAIL, completed_tasks_node_s::task, quark_task_s::task_mutex, quark_task_s::task_thread_count, and completed_tasks_node_s::workerid.

{
    int threads_remaining_for_this_task = -1;
    pthread_mutex_lock_wrap( &task->task_mutex );
    threads_remaining_for_this_task = --task->task_thread_count;
    pthread_mutex_unlock_wrap( &task->task_mutex );
    if ( threads_remaining_for_this_task == 0 ) {
        completed_tasks_node_t *node = malloc(sizeof(completed_tasks_node_t));
        node->task = task;
        node->workerid = worker_rank;
        pthread_mutex_lock_completed_tasks( &quark->completed_tasks_mutex );
        TAILQ_INSERT_TAIL( quark->completed_tasks, node, entries );
        pthread_mutex_unlock_completed_tasks( &quark->completed_tasks_mutex );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

---

Variable Documentation

FILE* dot_dag_file

Definition at line 297 of file quark.c.

char* quark_task_default_color = "white"

static

Definition at line 292 of file quark.c.

char* quark_task_default_label = " "

static

Definition at line 291 of file quark.c.