From dd7f66806e66d9637b070841c2a7c914671db969 Mon Sep 17 00:00:00 2001 From: Bjoern Brandenburg Date: Wed, 16 May 2012 18:30:30 +0200 Subject: C++: Break out the FMLP+ code into own file Part of refactoring sharedres.cpp. --- native/src/sharedres.cpp | 373 +++-------------------------------------------- 1 file changed, 19 insertions(+), 354 deletions(-) (limited to 'native/src/sharedres.cpp') diff --git a/native/src/sharedres.cpp b/native/src/sharedres.cpp index a3b4ed9..259e5a7 100644 --- a/native/src/sharedres.cpp +++ b/native/src/sharedres.cpp @@ -128,32 +128,7 @@ void split_by_resource(const ResourceSharingInfo& info, Resources& resources) } } -static void all_from_cluster(const Cluster& cluster, ContentionSet& cs) -{ - foreach(cluster, it) - { - const TaskInfo* tsk = *it; - - foreach(tsk->get_requests(), jt) - { - const RequestBound& req = *jt; - cs.push_back(&req); - } - } -} - -static void all_per_cluster(const Clusters& clusters, - AllPerCluster& all) -{ - foreach(clusters, it) - { - all.push_back(ContentionSet()); - all_from_cluster(*it, all.back()); - } -} - - -static void split_by_resource(const Cluster& cluster, Resources& resources) +void split_by_resource(const Cluster& cluster, Resources& resources) { foreach(cluster, it) @@ -173,8 +148,8 @@ static void split_by_resource(const Cluster& cluster, Resources& resources) } } -static void split_by_resource(const Clusters& clusters, - ClusterResources& resources) +void split_by_resource(const Clusters& clusters, + ClusterResources& resources) { foreach(clusters, it) { @@ -258,45 +233,19 @@ void sort_by_request_length(ClusterResources& resources) apply_foreach(resources, sort_by_request_length); } -typedef std::vector TaskContention; typedef std::vector ClusterContention; -// have one contention set per task -static void derive_task_contention(const Cluster& cluster, - TaskContention& requests) -{ - requests.reserve(cluster.size()); - - foreach(cluster, it) - { - const TaskInfo* tsk = *it; - - requests.push_back(ContentionSet()); - - foreach(tsk->get_requests(), jt) - { - const RequestBound& req = *jt; - - requests.back().push_back(&req); - } - } -} - -static void derive_task_contention(const Clusters& clusters, - ClusterContention& contention) -{ - map_ref(clusters, contention, TaskContention, derive_task_contention); -} +typedef std::vector TaskContention; -static Interference bound_blocking(const ContentionSet& cont, - unsigned long interval, - unsigned int max_total_requests, - unsigned int max_requests_per_source, - const TaskInfo* exclude_tsk, - // Note: the following parameter excludes - // *high-priority* tasks. Used to exclude local higher-priority tasks. - // Default: all tasks can block (suitable for remote blocking). - unsigned int min_priority = 0) +Interference bound_blocking(const ContentionSet& cont, + unsigned long interval, + unsigned int max_total_requests, + unsigned int max_requests_per_source, + const TaskInfo* exclude_tsk, + // Note: the following parameter excludes + // *high-priority* tasks. Used to exclude local higher-priority tasks. + // Default: all tasks can block (suitable for remote blocking). + unsigned int min_priority /* default == 0 */) { Interference inter; unsigned int remaining; @@ -370,12 +319,12 @@ static void add_blocking(LimitedContentionSet &lcs, } } -static Interference bound_blocking(const ContentionSet& cont, - unsigned long interval, - unsigned int max_total_requests, - unsigned int max_requests_per_source, - bool exclude_whole_cluster, - const TaskInfo* exclude_tsk) +Interference bound_blocking(const ContentionSet& cont, + unsigned long interval, + unsigned int max_total_requests, + unsigned int max_requests_per_source, + bool exclude_whole_cluster, + const TaskInfo* exclude_tsk) { Interference inter; unsigned int remaining; @@ -1434,287 +1383,3 @@ BlockingBounds* task_fair_rw_bounds(const ResourceSharingInfo& info, } -/* this analysis corresponds to the FMLP+ in the dissertation */ - -static void pfmlp_count_direct_blocking(const TaskInfo* tsk, - const ClusterResources& resources, - std::vector& counts) -{ - unsigned int interval = tsk->get_response(); - - - // for each resource requested by tsk - foreach(tsk->get_requests(), jt) - { - const RequestBound& req = *jt; - unsigned long issued = req.get_num_requests(); - unsigned int res_id = req.get_resource_id(); - - unsigned int i; - - // for each cluster - for (i = 0; i < resources.size(); i++) - { - // count interference... direct blocking will be counted later - // make sure that cluster acceses res_id at all - if (resources[i].size() > res_id) - // yes it does---how often can it block? - counts[i] += bound_blocking(resources[i][res_id], - interval, - UNLIMITED, // no total limit - issued, // once per request - tsk); - } - } -} - -typedef std::vector AccessCounts; -typedef std::vector PerClusterAccessCounts; - -// How many times does a task issue requests that can -// conflict with tasks in a remote cluster. Indexed by cluster id. -typedef std::vector IssuedRequests; -// Issued requests for each task. Indexed by task id. -typedef std::vector PerTaskIssuedCounts; - -static void derive_access_counts(const ContentionSet &cluster_contention, - AccessCounts &counts) -{ - foreach(cluster_contention, it) - { - const RequestBound *req = *it; - unsigned int res_id = req->get_resource_id(); - - while (counts.size() <= res_id) - counts.push_back(0); - - counts[res_id] += req->get_num_requests(); - } -} - -static void count_accesses_for_task(const TaskInfo& tsk, - const PerClusterAccessCounts& acc_counts, - IssuedRequests& ireqs) -{ - foreach(acc_counts, it) - { - const AccessCounts &ac = *it; - unsigned int count = 0; - - // Check for each request of the task to see - // if it conflicts with the cluster. - foreach(tsk.get_requests(), jt) - { - const RequestBound &req = *jt; - unsigned int res_id = req.get_resource_id(); - if (ac.size() > res_id && ac[res_id] > 0) - { - // cluster acceses res_id as well - count += req.get_num_requests(); - } - } - ireqs.push_back(count); - } -} - -static void derive_access_counts(const AllPerCluster &per_cluster, - const ResourceSharingInfo &info, - PerTaskIssuedCounts &issued_reqs) -{ - PerClusterAccessCounts counts; - - /* which resources are accessed by each cluster? */ - map_ref(per_cluster, counts, AccessCounts, derive_access_counts); - - issued_reqs.reserve(info.get_tasks().size()); - - foreach(info.get_tasks(), it) - { - issued_reqs.push_back(IssuedRequests()); - count_accesses_for_task(*it, counts, issued_reqs.back()); - } -} - -static Interference pfmlp_bound_remote_blocking(const TaskInfo* tsk, - const IssuedRequests &icounts, - const std::vector& counts, - const ClusterContention& contention) -{ - unsigned int i; - - unsigned long interval = tsk->get_response(); - Interference blocking; - - // for each cluster - for (i = 0; i < contention.size(); i++) - { - // Each task can either directly or indirectly block tsk - // each time that tsk is directly blocked, but no more than - // once per request issued by tsk. - unsigned int max_per_task = std::min(counts[i].count, icounts[i]); - - // skip local cluster and independent clusters - if (i == tsk->get_cluster() || !max_per_task) - continue; - - Interference b; - - // for each task in cluster - foreach(contention[i], it) - { - - // count longest critical sections - b += bound_blocking(*it, - interval, - max_per_task, - UNLIMITED, // no limit per source - tsk); - } - - blocking += b; - } - return blocking; -} - -static Interference pfmlp_bound_np_blocking(const TaskInfo* tsk, - const std::vector& counts, - const AllPerCluster& per_cluster) -{ - unsigned int i; - - unsigned long interval = tsk->get_response(); - Interference blocking; - - // for each cluster - for (i = 0; i < per_cluster.size(); i++) - { - // skip local cluster, this is only remote - if (i == tsk->get_cluster()) - continue; - - // could be the same task each time tsk is directly blocked - unsigned int max_direct = counts[i].count; - Interference b; - - // count longest critical sections - b += bound_blocking(per_cluster[i], - interval, - max_direct, - max_direct, - tsk); - blocking += b; - } - return blocking; -} - -static Interference pfmlp_bound_local_blocking(const TaskInfo* tsk, - const std::vector& counts, - const ClusterContention& contention) -{ - // Locally, we have to account two things. - // 1) Direct blocking from lower-priority tasks. - // 2) Boost blocking from lower-priority tasks. - // (Higher-priority requests are not counted as blocking.) - // Since lower-priority jobs are boosted while - // they directly block, 1) is subsumed by 2). - // Lower-priority tasks cannot issue requests while a higher-priority - // job executes. Therefore, at most one blocking request - // is issued prior to the release of the job under analysis, - // and one prior to each time that the job under analysis resumes. - - Interference blocking; - Interference num_db = std::accumulate(counts.begin(), counts.end(), - Interference()); - unsigned int num_arrivals = std::min(tsk->get_num_arrivals(), - num_db.count + 1); - unsigned long interval = tsk->get_response(); - - const TaskContention& cont = contention[tsk->get_cluster()]; - - // for each task in cluster - foreach(cont, it) - { - // count longest critical sections - blocking += bound_blocking(*it, - interval, - num_arrivals, - UNLIMITED, // no limit per source - tsk, - tsk->get_priority()); - } - - return blocking; -} - -BlockingBounds* part_fmlp_bounds(const ResourceSharingInfo& info, bool preemptive) -{ - // split everything by partition - Clusters clusters; - - split_by_cluster(info, clusters); - - // split each partition by resource - ClusterResources resources; - split_by_resource(clusters, resources); - - // find interference on a per-task basis - ClusterContention contention; - derive_task_contention(clusters, contention); - - // sort each contention set by request length - sort_by_request_length(contention); - - // find total interference on a per-cluster basis - AllPerCluster per_cluster; - PerTaskIssuedCounts access_counts; - - all_per_cluster(clusters, per_cluster); - sort_by_request_length(per_cluster); - - derive_access_counts(per_cluster, info, access_counts); - - // We need to find two blocking sources. Direct blocking (i.e., jobs - // that are enqueued prior to the job under analysis) and boost - // blocking, which occurs when the job under analysis is delayed - // because some other job is priority-boosted. Boost blocking can be - // local and transitive from remote CPUs. To compute this correctly, - // we need to count how many times some job on a remote CPU can directly - // block the job under analysis. So we first compute direct blocking - // and count on which CPUs a job can be blocked. - - unsigned int i; - - // direct blocking results - BlockingBounds* _results = new BlockingBounds(info); - BlockingBounds& results = *_results; - - for (i = 0; i < info.get_tasks().size(); i++) - { - const TaskInfo& tsk = info.get_tasks()[i]; - std::vector counts(resources.size()); - Interference remote, local; - - // Determine counts. - pfmlp_count_direct_blocking(&tsk, resources, counts); - - // Find longest remote requests. - remote = pfmlp_bound_remote_blocking(&tsk, access_counts[i], counts, - contention); - - // Add in local boost blocking. - local = pfmlp_bound_local_blocking(&tsk, counts, contention); - - if (!preemptive) - { - // Charge for additional delays due to remot non-preemptive - // sections. - remote += pfmlp_bound_np_blocking(&tsk, counts, per_cluster); - } - results[i] = remote + local; - results.set_remote_blocking(i, remote); - results.set_local_blocking(i, local); - } - - return _results; -} - -- cgit v1.2.2