From 273e902c50ef94966815a92c2af5ab8c5b2d77ce Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 20 Apr 2012 21:20:21 -0400 Subject: Untested donee selection heuristic for IKGLP. --- include/litmus/ikglp_lock.h | 2 +- litmus/ikglp_lock.c | 239 +++++++++++++++++++++++++++++++++++++++----- 2 files changed, 216 insertions(+), 25 deletions(-) diff --git a/include/litmus/ikglp_lock.h b/include/litmus/ikglp_lock.h index 3fa23251b539..2558a382446c 100644 --- a/include/litmus/ikglp_lock.h +++ b/include/litmus/ikglp_lock.h @@ -119,7 +119,7 @@ struct ikglp_affinity_ops { struct fifo_queue* (*advise_enqueue)(struct ikglp_affinity* aff, struct task_struct* t); // select FIFO ikglp_wait_state_t* (*advise_steal)(struct ikglp_affinity* aff); // select steal from FIFO - ikglp_donee_heap_node_t* (*advise_donee_selection)(struct ikglp_affinity* aff); // select a donee + ikglp_donee_heap_node_t* (*advise_donee_selection)(struct ikglp_affinity* aff, struct task_struct* t); // select a donee ikglp_wait_state_t* (*advise_doner_to_fq)(struct ikglp_affinity* aff, struct fifo_queue* dst); // select a donor to move to PQ void (*notify_enqueue)(struct ikglp_affinity* aff, struct fifo_queue* fq, struct task_struct* t); // fifo enqueue diff --git a/litmus/ikglp_lock.c b/litmus/ikglp_lock.c index 0e07841b86ba..9ae71422d813 100644 --- a/litmus/ikglp_lock.c +++ b/litmus/ikglp_lock.c @@ -742,7 +742,7 @@ static void ikglp_enqueue_on_donor(struct ikglp_semaphore *sem, // Select a donee #ifdef CONFIG_LITMUS_AFFINITY_LOCKING donee_node = (sem->aff_obs) ? - sem->aff_obs->ops->advise_donee_selection(sem->aff_obs) : + sem->aff_obs->ops->advise_donee_selection(sem->aff_obs, t) : binheap_top_entry(&sem->donees, ikglp_donee_heap_node_t, node); #else donee_node = binheap_top_entry(&sem->donees, ikglp_donee_heap_node_t, node); @@ -1833,24 +1833,22 @@ static int gpu_replica_to_resource(struct ikglp_affinity* aff, struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct task_struct* t) { // advise_enqueue must be smart as not not break IKGLP rules: - // * Total number of waiters cannot exceed ceil(m/k)*k. + // * No queue can be greater than ceil(m/k) in length. We may return + // such a queue, but IKGLP will be smart enough as to send requests + // to donors or PQ. // * Cannot let a queue idle if there exist waiting PQ/donors // -- needed to guarantee parallel progress of waiters. // - // Locking protocol is smart enough to noticed that a queue we return is - // full and send new requests to Donors/PQ. - // // We may be able to relax some of these constraints, but this will have to // be carefully evaluated. + // + // Huristic strategy: Find the shortest queue that is not full. - struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock); - - /* struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock); lt_t min_len; int min_nr_users; struct ikglp_queue_info *shortest; - struct ikglp_queue *to_enqueue; + struct fifo_queue *to_enqueue; int i; int affinity_gpu; @@ -1877,17 +1875,20 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t min_len = shortest->estimated_len + get_gpu_estimate(t, MIG_LOCAL); min_nr_users = *(shortest->nr_cur_users); - TRACE_CUR("cs is %llu on queue %d: est len = %llu\n", + TRACE_CUR("cs is %llu on queue %d (count = %d): est len = %llu\n", get_gpu_estimate(t, MIG_LOCAL), ikglp_get_idx(sem, shortest->q), + shortest->q->count, min_len); for(i = 0; i < sem->nr_replicas; ++i) { - if(&aff->q_info[i] != shortest) { + if((&aff->q_info[i] != shortest) && + (aff->q_info[i].q->count < sem->max_fifo_len)) { lt_t est_len = - aff->q_info[i].estimated_len + - get_gpu_estimate(t, gpu_migration_distance(tsk_rt(t)->last_gpu, replica_to_gpu(aff, i))); + aff->q_info[i].estimated_len + + get_gpu_estimate(t, gpu_migration_distance(tsk_rt(t)->last_gpu, + replica_to_gpu(aff, i))); // queue is smaller, or they're equal and the other has a smaller number // of total users. @@ -1901,21 +1902,34 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t min_nr_users = *(aff->q_info[i].nr_cur_users); } - TRACE_CUR("cs is %llu on queue %d: est len = %llu\n", - get_gpu_estimate(t, gpu_migration_distance(tsk_rt(t)->last_gpu, replica_to_gpu(aff, i))), + TRACE_CUR("cs is %llu on queue %d (count = %d): est len = %llu\n", + get_gpu_estimate(t, + gpu_migration_distance(tsk_rt(t)->last_gpu, + replica_to_gpu(aff, i))), ikglp_get_idx(sem, aff->q_info[i].q), + aff->q_info[i].q->count, est_len); } + else { + TRACE_CUR("queue %d is too long. ineligible for enqueue.\n", + ikglp_get_idx(sem, aff->q_info[i].q)); + } + } + + if(shortest->q->count >= sem->max_fifo_len) { + TRACE_CUR("selected fq %d is too long, but returning it anyway.\n", + ikglp_get_idx(sem, shortest->q)); } to_enqueue = shortest->q; - TRACE_CUR("enqueue on fq %d (non-aff wanted fq %d)\n", + TRACE_CUR("enqueue on fq %d (count = %d) (non-aff wanted fq %d)\n", ikglp_get_idx(sem, to_enqueue), - ikglp_get_idx(sem, sem->shortest_queue)); + to_enqueue->count, + ikglp_get_idx(sem, sem->shortest_fifo_queue)); return to_enqueue; - */ - return(sem->shortest_fifo_queue); + + //return(sem->shortest_fifo_queue); } ikglp_wait_state_t* gpu_ikglp_advise_steal(struct ikglp_affinity* aff) @@ -1928,12 +1942,189 @@ ikglp_wait_state_t* gpu_ikglp_advise_steal(struct ikglp_affinity* aff) return ikglp_find_hp_waiter_to_steal(sem); } -ikglp_donee_heap_node_t* gpu_ikglp_advise_donee_selection(struct ikglp_affinity* aff) + +static inline int has_donor(wait_queue_t* fq_wait) +{ + ikglp_wait_state_t *wait = container_of(fq_wait, ikglp_wait_state_t, fq_node); + return(wait->donee_heap_node.donor_info != NULL); +} + +static ikglp_donee_heap_node_t* pick_donee(struct ikglp_affinity* aff, + struct fifo_queue* fq, + int* dist_from_head) { - // TODO: MAKE THIS SMARTER struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock); - ikglp_donee_heap_node_t *donee = binheap_top_entry(&sem->donees, ikglp_donee_heap_node_t, node); - return(donee); + struct task_struct *donee; + ikglp_donee_heap_node_t *donee_node; + + if(fq->owner && fq->donee_heap_node.donor_info != NULL) { + donee = fq->owner; + donee_node = &(fq->donee_heap_node); + *dist_from_head = 0; + + BUG_ON(donee != donee_node->task); + + TRACE_CUR("picked owner of fq %d as donee\n", + ikglp_get_idx(sem, fq)); + + goto out; + } + else if(waitqueue_active(&fq->wait)) { + struct list_head *pos; + + *dist_from_head = 1; + + // iterating from the start of the queue is nice since this means + // the donee will be closer to obtaining a resource. + list_for_each(pos, &fq->wait.task_list) { + wait_queue_t *fq_wait = list_entry(pos, wait_queue_t, task_list); + if(!has_donor(fq_wait)) { + ikglp_wait_state_t *wait = container_of(fq_wait, ikglp_wait_state_t, fq_node); + donee = (struct task_struct*) fq_wait->private; + donee_node = &wait->donee_heap_node; + + BUG_ON(donee != donee_node->task); + + TRACE_CUR("picked waiter in fq %d as donee\n", + ikglp_get_idx(sem, fq)); + + goto out; + } + ++(*dist_from_head); + } + + WARN_ON(1); + } + + donee = NULL; + donee_node = NULL; + *dist_from_head = sem->max_fifo_len + 1; + + TRACE_CUR("Found no one to be donee in fq %d!\n", ikglp_get_idx(sem, fq)); + +out: + + TRACE_CUR("Candidate donee for fq %d is %s/%d (dist_from_head = %d)\n", + ikglp_get_idx(sem, fq), + (donee) ? (donee)->comm : "nil", + (donee) ? (donee)->pid : -1, + *dist_from_head); + + return donee_node; +} + +ikglp_donee_heap_node_t* gpu_ikglp_advise_donee_selection( + struct ikglp_affinity* aff, + struct task_struct* donor) +{ + // Huristic strategy: Find the highest-priority donee that is waiting on + // a queue closest to our affinity. The donee CANNOT already have a donor + // (exception: donee is the lowest-prio task in the donee heap). + // + // Further strategy: amongst elible donees waiting for the same GPU, pick + // the one closest to the head of the FIFO queue (including owners). + // + struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock); + ikglp_donee_heap_node_t *donee_node; + gpu_migration_dist_t distance; + int start, i, j; + + ikglp_donee_heap_node_t *default_donee; + ikglp_wait_state_t *default_donee_donor_info; + + if(tsk_rt(donor)->last_gpu < 0) { + // no affinity. just return the min prio, like standard IKGLP + // TODO: Find something closer to the head of the queue?? + donee_node = binheap_top_entry(&sem->donees, + ikglp_donee_heap_node_t, + node); + goto out; + } + + + // Temporarily break any donation relation the default donee (the lowest + // prio task in the FIFO queues) to make it eligible for selection below. + // + // NOTE: The original donor relation *must* be restored, even if we select + // the default donee throug affinity-aware selection, before returning + // from this function so we don't screw up our heap ordering. + // The standard IKGLP algorithm will steal the donor relationship if needed. + default_donee = binheap_top_entry(&sem->donees, ikglp_donee_heap_node_t, node); + default_donee_donor_info = default_donee->donor_info; // back-up donor relation + default_donee->donor_info = NULL; // temporarily break any donor relation. + + // initialize our search + donee_node = NULL; + distance = MIG_NONE; + + // begin search with affinity GPU. + start = gpu_to_base_replica(aff, tsk_rt(donor)->last_gpu); + i = start; + do { // "for each gpu" / "for each aff->nr_rsrc" + gpu_migration_dist_t temp_distance = gpu_migration_distance(start, i); + + // only interested in queues that will improve our distance + if(temp_distance < distance || donee_node == NULL) { + int dist_from_head = sem->max_fifo_len + 1; + + TRACE_CUR("searching for donor on GPU %d", i); + + // visit each queue and pick a donee. bail as soon as we find + // one for this class. + + for(j = 0; j < aff->nr_simult; ++j) { + int temp_dist_from_head; + ikglp_donee_heap_node_t *temp_donee_node; + struct fifo_queue *fq; + + fq = &(sem->fifo_queues[i + j*aff->nr_rsrc]); + temp_donee_node = pick_donee(aff, fq, &temp_dist_from_head); + + if(temp_dist_from_head < dist_from_head) + { + // we check all the FQs for this GPU to spread priorities + // out across the queues. does this decrease jitter? + donee_node = temp_donee_node; + dist_from_head = temp_dist_from_head; + } + } + + if(dist_from_head != sem->max_fifo_len + 1) { + TRACE_CUR("found donee %s/%d and is the %d-th waiter.\n", + donee_node->task->comm, donee_node->task->pid, + dist_from_head); + } + else { + TRACE_CUR("found no eligible donors from GPU %d\n", i); + } + } + else { + TRACE_CUR("skipping GPU %d (distance = %d, best donor " + "distance = %d)\n", i, temp_distance, distance); + } + + i = (i+1 < aff->nr_rsrc) ? i+1 : 0; // increment with wrap-around + } while (i != start); + + + // restore old donor info state. + default_donee->donor_info = default_donee_donor_info; + + if(!donee_node) { + TRACE_CUR("Could not find a donee. We have to steal one.\n"); + WARN_ON(default_donee->donor_info == NULL); + + donee_node = default_donee; + } + +out: + + TRACE_CUR("Selected donee %s/%d from GPU %d for %s/%d with affinity for GPU %d\n", + donee_node->task->comm, donee_node->task->pid, + replica_to_gpu(aff, ikglp_get_idx(sem, donee_node->fq)), + donor->comm, donor->pid, tsk_rt(donor)->last_gpu); + + return(donee_node); } ikglp_wait_state_t* gpu_ikglp_advise_doner_to_fq(struct ikglp_affinity* aff, struct fifo_queue* fq) @@ -2147,7 +2338,7 @@ ikglp_wait_state_t* simple_gpu_ikglp_advise_steal(struct ikglp_affinity* aff) return ikglp_find_hp_waiter_to_steal(sem); } -ikglp_donee_heap_node_t* simple_gpu_ikglp_advise_donee_selection(struct ikglp_affinity* aff) +ikglp_donee_heap_node_t* simple_gpu_ikglp_advise_donee_selection(struct ikglp_affinity* aff, struct task_struct* donor) { struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock); ikglp_donee_heap_node_t *donee = binheap_top_entry(&sem->donees, ikglp_donee_heap_node_t, node); -- cgit v1.2.2