Show simple item record

dc.contributor.advisorFriesen, Donald K.
dc.creatorLopez, Dian Rae
dc.description.abstractA task allocation algorithm in a parallel system assigns tasks to each processor with a goal of minimizing both execution and communication costs. Previous research shows the need for algorithms which can approximate this problem efficiently as well as the need for a model which incorporates more fully the communication costs between tasks. The bulk-synchronous parallel (BSP) model proposed by Valiant is shown as a viable model for the task allocation problem. It is shown that the problem is strongly NP-Complete and that no fully polynomial approximation scheme is possible for solving the general problem. Performance results are possible, however, for certain restricted problems. Using the BSP model, approximation algorithms are given for both restricted and the general task allocation problems. Algorithms and performance bounds are also given for the more practical problem of allocating tasks which form precedence graphs. By relaxing previous restrictions used in algorithms for this problem, a practical model was designed which can be implemented on the XPRAM BSP architecture.en
dc.format.extentx, 87 leavesen
dc.rightsThis thesis was part of a retrospective digitization project authorized by the Texas A&M University Libraries. Copyright remains vested with the author(s). It is the user's responsibility to secure permission from the copyright holder(s) for re-use of the work beyond the provision of Fair Use.en
dc.subjectMajor computer scienceen
dc.subject.classification1992 Dissertation L8631
dc.subject.lcshParallel processing (Electronic computers)en
dc.subject.lcshElectronic data processingen
dc.subject.lcshDistributed processingen
dc.subject.lcshComputer architectureen
dc.subject.lcshInteractive computer systemsen
dc.titleModels and algorithms for task allocation in a parallel environmenten
dc.typeThesisen A&M Universityen of Philosophyen Den
dc.contributor.committeeMemberDeuermeyer, Bryan L.
dc.contributor.committeeMemberKanevsky, Arkady
dc.contributor.committeeMemberKim, Junguk
dc.format.digitalOriginreformatted digitalen
dc.publisher.digitalTexas A&M University. Libraries

Files in this item


This item appears in the following Collection(s)

Show simple item record

This item and its contents are restricted. If this is your thesis or dissertation, you can make it open-access. This will allow all visitors to view the contents of the thesis.

Request Open Access