Please use this identifier to cite or link to this item: http://localhost:8081/xmlui/handle/123456789/9532
Title: PARALLEL SCHEDULING OF PRECEDENCE CONSTRAINT TASKS IN MULTIPROCESSOR SYSTEMS
Authors: Deharia, Krishnakant
Keywords: ELECTRONICS AND COMPUTER ENGINEERING;PARALLEL SCHEDULING;PRECEDENCE CONSTRAINT TASKS;MULTIPROCESSOR SYSTEMS
Issue Date: 2000
Abstract: Existing heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a smaller or potentially better solution, is to parallelize the scheduling algorithm. This can he done by partitioning the task graphs and concurrently generating partial schedule for the partitioned parts, which are then concatenated to obtain the filial schedule. The problem, however, is nontrivial as there exist dependencies among the nodes of a task graph, which must be preserved for generating a valid schedule. Moreover, the time clock , for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this thesis, a parallel algorithm is simulated that is guided by a systematic partitioning of the task graph to per form scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation crud communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. The algorithm exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size.....
URI: http://hdl.handle.net/123456789/9532
Other Identifiers: M.Tech
Research Supervisor/ Guide: Kumar, Padam
metadata.dc.type: M.Tech Dessertation
Appears in Collections:MASTERS' DISSERTATIONS (E & C)

Files in This Item:
File Description SizeFormat 
ECD248490.pdf3.63 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.