Block Scheduling of Iterative Algorithms and Graph-Level Priority Scheduling in a Simulated Data-Flow Multiprocessor
Ημερομηνία
1993ISSN
1045-9219Source
IEEE Transactions on Parallel and Distributed SystemsVolume
4Issue
4Pages
398-413Google Scholar check
Keyword(s):
Metadata
Εμφάνιση πλήρους εγγραφήςΕπιτομή
While data-flow principles permit the utilization of large-scale multiprocessor systems with high programmability and good efficiency, they also introduce much overhead at runtime. In this paper, we have studied an important class of PDE solvers, namely iterative methods for solving linear systems. Although these methods are inherently highly sequential, we have found that much parallelism could be exploited in a dataflow system by scheduling the iterative part of the algorithms in blocks and by looking ahead across several iterations. This approach is general and will apply to other iterative and loop-based problems. It is also demonstrated by simulation means, that relying solely on data-driven scheduling of parallel and unrolled loops results in low resource utilization and poor performance. A graph-level priority scheduling mechanism has been developed that drastically improves resource utilization and yields higher performance. © 1993 IEEE
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Article
PADS: An approach to modeling resource demand and supply for the formal analysis of hierarchical scheduling
Philippou, Anna; Lee, I.; Sokolsky, O. (2012)As real-time embedded systems become more complex, resource partitioning is increasingly used to guarantee real-time performance. Recently, several compositional frameworks of resource partitioning have been proposed using ...
-
Conference Object
Scheduling workflows with budget constraints
Sakellariou, R.; Zhao, H.; Tsiakkouri, E.; Dikaiakos, Marios D. (Springer Science and Business Media, LLC, 2007)Grids are emerging as a promising solution for resource and computation demanding applications. However, the heterogeneity of resources in Grid computing, complicates resource management and scheduling of applications. In ...
-
Conference Object
Dynamic transmission scheduling for packet radio networks
Panayiotou, Christos G.; Cassandras, C. G. (1998)