Abstract

The macro-dataflow model of execution has been used in scheduling heuristics for directed acyclic graphs. Since this model was developed for the scheduling of parallel applications on distributed computing systems, it is inadequate when applied to the multicore shared-memory computers prevalent in the market today. The pulled-macro-dataflow model is put forth as an alternative to the macro-dataflow model, having been designed specifically to accurately describe the memory bandwidth limitations and request-driven nature of communications characteristic of today's machines. The performance of the common scheduling heuristics DSC and CASS-II are evaluated under the pulled-macro-dataflow model and it is shown that their poor performance motivates the development of a new scheduling heuristic. The Concurrent Tournament Reducer (ConTouR) is developed as a scheduling heuristic which operates well with the pulled-macro-dataflow model. ConTouR is compared to the existing heuristics Load Balancing and Communication Minimization in scheduling two programs. For both programs, the other reducers are shown to outperform ConTouR.

Degree

MS

College and Department

Ira A. Fulton College of Engineering and Technology; Electrical and Computer Engineering

Rights

http://lib.byu.edu/about/copyright/

Date Submitted

2011-09-13

Document Type

Thesis

Handle

http://hdl.lib.byu.edu/1877/etd4772

Keywords

pulled-macro-dataflow model, macro-dataflow model, scheduling, reduction heuristic, ConTouR

Share

COinS