| This research shows that with the aid of the compiler, a runtime system can automatically exploit detailed application-specific information with reasonably low overhead to provide better scheduling. Many applications, which could take advantage of parallelism, such as adaptive PDE solvers, sparse matrix problems, particle simulations, heuristic searches, combinatorial optimization problems, etc., exhibit dynamic data-dependent behaviors and sometimes have highly irregular program structures. Available resources may change between different program runs. In these cases, hardware resources must be scheduled dynamically.;A new system architecture for runtime resource management, Compiler-Directed Runtime Resource Management, has been designed to allow the use of detailed application-specific information in runtime scheduling without the programmer's involvement. Under this system architecture, a runtime resource management system for distributed memory multiprocessors, RTRMS, and a new scheduling algorithm, Expedite, has been created, implemented and studied. Experimental results show that Expedite consistently outperforms three other commonly used heuristics, showing an average performance gain (in terms of relative speedup) from 10% to more than 50%. Expedite is also shown to be competitive with the best manual placements and the best placement generated by repeated refinement techniques. Such superiority is unaffected by higher communication costs. As a runtime scheduling algorithm, Expedite is able to adapt scheduling to changing system environments and still produces good schedules. Furthermore, by estimating the inherent processor parallelism and load-balancing requirements in the program, Expedite is able to allocate a near-optimal number of processors without compromising the scheduling performance.;The RTRMS runtime overheads in the Compiler-Directed Runtime Resource Management have been quantitatively analyzed and modeled. The overhead rate averages about 3000 CPU cycles per block. Based on the empirical overhead model, the worst case performance degradation due to runtime overhead can be quickly computed and used to guide the scheduling strategy.;The overhead analysis showed that block granularity and parallelism are two major factors in determining the overall performance gain. Without any code reordering optimization, it is suggested that a block granularity of more than 750K CPU cycles or 1500 times the communication/context switching costs should be used to guarantee an overall performance gain when Expedite is used. |
