{"id":{"repo_id":"sask","oai_identifier":"oai:harvest.usask.ca:10388/etd-11012011-110443"},"canonical_url":"https://search.dev.ndltd.org/etd/sask/oai:harvest.usask.ca:10388/etd-11012011-110443","repository":{"repo_id":"sask","name":"University of Saskatchewan","base_url":"https://harvest.usask.ca/server/oai/request"},"display":{"title":"Affinity scheduling of unbalanced workloads","abstract":"Shared memory multiprocessor systems are becoming increasingly important and common. Multiprocessor environments are significantly different from uniproces­sor environments, raising new scheduling issues that need to be considered. A funda­mental scheduling issue arises in situations in which a unit of work may be processed more efficiently on one processor than on any other, due to factors such as the rate at which the required data can be accessed from the given processor. The unit of work is said to have an "affinity" for the given processor, in such a case. The scheduling issue that has to be considered is the trade off between the goals of respecting proces­sor affinities (so as to obtain improved efficiencies in execution) and of dynamically assigning each unit of work to whichever processor happens to be, at the time, least loaded (so as to obtain better load balance and decreased processor idle times). A specific context in which the above scheduling issue arises is that of shared memory multiprocessors with large, per-processor caches or cached main memories. The shared-memory programming paradigm of such machines permits the dynamic scheduling of work. The data required by a unit of work may, however, often reside' mostly in the cache of one particular processor, to which that unit of work thus has affinity. In this thesis, the design of "affinity scheduling" algorithms, in which both affinity and load balancing considerations play major roles in the scheduling policy, is explored. Two new affinity scheduling algorithms are proposed for a context in which the units of work have widely varying execution times. An experimental study of these algorithms finds them to be superior to the previously proposed algorithms 'in this context.'","abstract_html":"Shared memory multiprocessor systems are becoming increasingly important and common. Multiprocessor environments are significantly different from uniproces­sor environments, raising new scheduling issues that need to be considered. A funda­mental scheduling issue arises in situations in which a unit of work may be processed more efficiently on one processor than on any other, due to factors such as the rate at which the required data can be accessed from the given processor. The unit of work is said to have an "affinity" for the given processor, in such a case. The scheduling issue that has to be considered is the trade off between the goals of respecting proces­sor affinities (so as to obtain improved efficiencies in execution) and of dynamically assigning each unit of work to whichever processor happens to be, at the time, least loaded (so as to obtain better load balance and decreased processor idle times). A specific context in which the above scheduling issue arises is that of shared memory multiprocessors with large, per-processor caches or cached main memories. The shared-memory programming paradigm of such machines permits the dynamic scheduling of work. The data required by a unit of work may, however, often reside' mostly in the cache of one particular processor, to which that unit of work thus has affinity. In this thesis, the design of "affinity scheduling" algorithms, in which both affinity and load balancing considerations play major roles in the scheduling policy, is explored. Two new affinity scheduling algorithms are proposed for a context in which the units of work have widely varying execution times. An experimental study of these algorithms finds them to be superior to the previously proposed algorithms 'in this context.'","abstract_has_math":false,"creators":["Subramaniam, Srikant"],"institution":"University of Saskatchewan","degree_name":"Master of Science (M.Sc.)","degree_level":"Masters","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":["Eager, Derek","Williamson, Carey","Keil, Mark","Irudayaraj, Joseph"],"year":1993,"date_issued":"1993","date_published":"1993","updated_at":"2026-07-24T04:27:06Z","subjects":[],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/10388/etd-11012011-110443","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Eager, Derek","Williamson, Carey","Keil, Mark","Irudayaraj, Joseph"]},{"key":"dc:creator","label":"Author","values":["Subramaniam, Srikant"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2011-11-01T11:04:43Z","2013-01-04T05:07:33Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2012-11-01T08:00:00Z","2013-01-04T05:07:33Z"]},{"key":"dc:date.issued","label":"Date","values":["1993"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (M.Sc.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Saskatchewan"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10388/etd-11012011-110443"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Shared memory multiprocessor systems are becoming increasingly important and common. Multiprocessor environments are significantly different from uniproces­sor environments, raising new scheduling issues that need to be considered. A funda­mental scheduling issue arises in situations in which a unit of work may be processed more efficiently on one processor than on any other, due to factors such as the rate at which the required data can be accessed from the given processor. The unit of work is said to have an "affinity" for the given processor, in such a case. The scheduling issue that has to be considered is the trade off between the goals of respecting proces­sor affinities (so as to obtain improved efficiencies in execution) and of dynamically assigning each unit of work to whichever processor happens to be, at the time, least loaded (so as to obtain better load balance and decreased processor idle times). A specific context in which the above scheduling issue arises is that of shared memory multiprocessors with large, per-processor caches or cached main memories. The shared-memory programming paradigm of such machines permits the dynamic scheduling of work. The data required by a unit of work may, however, often reside' mostly in the cache of one particular processor, to which that unit of work thus has affinity. In this thesis, the design of "affinity scheduling" algorithms, in which both affinity and load balancing considerations play major roles in the scheduling policy, is explored. Two new affinity scheduling algorithms are proposed for a context in which the units of work have widely varying execution times. An experimental study of these algorithms finds them to be superior to the previously proposed algorithms 'in this context.'"]},{"key":"dc:title","label":"Title","values":["Affinity scheduling of unbalanced workloads"]}]}],"canonical_facts":{"dc:contributor.committeemember":["Eager, Derek","Williamson, Carey","Keil, Mark","Irudayaraj, Joseph"],"dc:creator":["Subramaniam, Srikant"],"dc:date.accessioned":["2011-11-01T11:04:43Z","2013-01-04T05:07:33Z"],"dc:date.available":["2012-11-01T08:00:00Z","2013-01-04T05:07:33Z"],"dc:date.issued":["1993"],"dc:description.abstract":["Shared memory multiprocessor systems are becoming increasingly important and common. Multiprocessor environments are significantly different from uniproces­sor environments, raising new scheduling issues that need to be considered. A funda­mental scheduling issue arises in situations in which a unit of work may be processed more efficiently on one processor than on any other, due to factors such as the rate at which the required data can be accessed from the given processor. The unit of work is said to have an "affinity" for the given processor, in such a case. The scheduling issue that has to be considered is the trade off between the goals of respecting proces­sor affinities (so as to obtain improved efficiencies in execution) and of dynamically assigning each unit of work to whichever processor happens to be, at the time, least loaded (so as to obtain better load balance and decreased processor idle times). A specific context in which the above scheduling issue arises is that of shared memory multiprocessors with large, per-processor caches or cached main memories. The shared-memory programming paradigm of such machines permits the dynamic scheduling of work. The data required by a unit of work may, however, often reside' mostly in the cache of one particular processor, to which that unit of work thus has affinity. In this thesis, the design of "affinity scheduling" algorithms, in which both affinity and load balancing considerations play major roles in the scheduling policy, is explored. Two new affinity scheduling algorithms are proposed for a context in which the units of work have widely varying execution times. An experimental study of these algorithms finds them to be superior to the previously proposed algorithms 'in this context.'"],"dc:identifier.uri":["https://hdl.handle.net/10388/etd-11012011-110443"],"dc:language.iso":["en_US"],"dc:title":["Affinity scheduling of unbalanced workloads"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science (M.Sc.)"],"thesis:institution_name":["University of Saskatchewan"]},"updated_at":"2026-07-24T04:27:06Z"}