hrcak mascot   Srce   HID

Izvorni znanstveni članak
https://doi.org/10.2498/cit.2003.02.06

A Method for Improving Efficiency of Static Program Graph Scheduling

Milan Ojsteršek
Aleksander Kvas

Puni tekst: engleski, pdf (60 KB) str. 135-141 preuzimanja: 335* citiraj
APA 6th Edition
Ojsteršek, M. i Kvas, A. (2003). A Method for Improving Efficiency of Static Program Graph Scheduling. Journal of computing and information technology, 11 (2), 135-141. https://doi.org/10.2498/cit.2003.02.06
MLA 8th Edition
Ojsteršek, Milan i Aleksander Kvas. "A Method for Improving Efficiency of Static Program Graph Scheduling." Journal of computing and information technology, vol. 11, br. 2, 2003, str. 135-141. https://doi.org/10.2498/cit.2003.02.06. Citirano 24.02.2021.
Chicago 17th Edition
Ojsteršek, Milan i Aleksander Kvas. "A Method for Improving Efficiency of Static Program Graph Scheduling." Journal of computing and information technology 11, br. 2 (2003): 135-141. https://doi.org/10.2498/cit.2003.02.06
Harvard
Ojsteršek, M., i Kvas, A. (2003). 'A Method for Improving Efficiency of Static Program Graph Scheduling', Journal of computing and information technology, 11(2), str. 135-141. https://doi.org/10.2498/cit.2003.02.06
Vancouver
Ojsteršek M, Kvas A. A Method for Improving Efficiency of Static Program Graph Scheduling. Journal of computing and information technology [Internet]. 2003 [pristupljeno 24.02.2021.];11(2):135-141. https://doi.org/10.2498/cit.2003.02.06
IEEE
M. Ojsteršek i A. Kvas, "A Method for Improving Efficiency of Static Program Graph Scheduling", Journal of computing and information technology, vol.11, br. 2, str. 135-141, 2003. [Online]. https://doi.org/10.2498/cit.2003.02.06

Sažetak
An efficient scheduling of a parallel program onto the processors is critical for achieving a high performance from a parallel computer system. The scheduling problem is known to be NP-hard and heuristic algorithms have been proposed to obtain optimal and sub optimal solutions. The partitioning algorithm partitions an application into tasks with appropriate grain size and represents them in the form of a directed acyclic graph (DAG). The nodes of the resulting DAG are then scheduled onto the processors of a parallel computer system. We can see that almost all coarse grained program graph nodes don't need all of their input operands at the beginning of their execution. Thereafter they can be scheduled a bit earlier. This type of program graph nodes triggering is called partial strict triggering. The missing operands will be requested later during the execution. Coarse grained program graph nodes send their output operand to all successors, as soon as they produce them. Successors of coarse grained program graph nodes will be scheduled earlier too, because they will receive their input operands sooner. An evaluation of improved CPM, VL and DSH scheduling algorithms is done in this paper. We have improved them with partial strict triggering of coarse grained program graph nodes.

Hrčak ID: 44759

URI
https://hrcak.srce.hr/44759

Posjeta: 499 *