Show simple item record

dc.contributor.advisorRodríguez, Domingo
dc.contributor.authorde la Torre-Quintana, Luis F.
dc.description.abstractSeveral problems in science and engineering admit algorithmic solutions that demand a large amount of computing time. Among these applications are genotype sequencing, gene sequence comparison, protein folding, quantum chemistry, computational uid dynamics, and Earth simulation. In most of these cases, a single computer does not provide enough computing power to satisfy these needs, and therefore, the design of parallel methods is of crucial importance. It has been observe in practice that many of these algorithmic solutions acquire the form of a master-worker algorithm. Due to their availability and low cost, heterogeneous networks of computers are becoming a popular alternative for these implementations. One problem, frequently faced by implementers is how to divide and distribute the parallel segments of computing tasks among the computers. This is the essence of the so-called task scheduling problem. Efficiently managing the computations is a difficult and challenging problem. This efficiency depends on the number of rounds of computation, the sizes of the data chunks sent in a round, and the number and the activation sequence of the participating workers. In this dissertation variants and extensions of ideas related to the scheduling of master-worker tasks on heterogeneous star networks are introduced. Some of these ideas were previously discussed in the form of theoretical frameworks for steadystate scheduling or as a divisible load theory. This dissertation combines some elements of these previous works to construct a new framework, and from it, an efficient algorithm (SCOW) for identifying a deterministic scheduler for clusters of workers. SCOW produces the parameters of a periodic user-level scheduler for a single-program multiple-data implementation of a master-worker parallel solution. SCOW minimizes the job make-span under either maximal production per period, or perfect worker utilization. The eficiency of the scheduler identified by SCOW is demonstrated through comparison with other schedulers, including those derived from the above mentioned theoretical frameworks. As shown in the simulation an actual computer runs, the scheduler identified by SCOW outperform in most cases those produced by the previous frameworks.en_US
dc.description.sponsorshipThis work was supported in part by NIH grant MARC PAR-03-026.en_US
dc.subjectScheduling tasksen_US
dc.titleScheduling divisible tasks under production or  utilization constraints  en_US
dc.rights.licenseAll rights reserveden_US
dc.rights.holder(c) 2009 Luis Fernando de la Torre Quintanaen_US
dc.contributor.committeeLu, Kejie
dc.contributor.committeeRodriguez, Manuel
dc.contributor.committeeSeguel, Jaime
dc.contributor.representativeSharma, Anand D. and Information Sciences and Engineeringen_US
dc.contributor.collegeCollege of Engineeringen_US
dc.contributor.departmentDepartment of Electrical and Computer Engineeringen_US

Files in this item


This item appears in the following Collection(s)

  • Theses & Dissertations
    Items included under this collection are theses, dissertations, and project reports submitted as a requirement for completing a graduate degree at UPR-Mayagüez.

Show simple item record

All rights reserved
Except where otherwise noted, this item's license is described as All Rights Reserved