In this paper we propose an adaptive scheduling approach designed to improve the performance of parallel applications in Computational Grid environments. A primary contribution of our work is that our design is modular and provides a separation of the scheduler itself from the application-specific components needed for the scheduling process. As part of the scheduler, we have also developed a search procedure which effectively and efficiently identifies desirable schedules. As test cases for our approach, we selected two applications from the class of iterative, mesh-based applications. For each of the test applications, we developed data mappers and performance models. We used a prototype of our approach in conjunction with these application-specific components to perform validation experiments in production Grid environments. Our results show that our scheduler provides significantly better application performance than conventional scheduling strategies. We also show that our scheduler gracefully handles degraded levels of availability of application and Grid resource information. Finally, we demonstrate that the overheads introduced by our methodology are reasonable. This work evolved in the context of the Grid Application Development Software Project (GrADS). Our scheduling approach is designed to be easily integrated with other GrADS program development tools.

Pre-2018 CSE ID: CS2002-0708

Computational Grids lend themselves well to parameter sweep applications,which consist of independent tasks, each of which calculates results for a separate point in parameter space. However, it is possible for a parameter space to become so large as to pose prohibitive system requirements. In these cases, user-directed steering promises to reduce overall computation time. In this paper, we address an interesting challenge posed by these user-directed searches: how should compute resources be allocated to application tasks as the overall computation is being steered by the user? We present a model for user-directed searches, and then propose a number of resource allocation strategies and evaluate them in simulation. We find that prioritizing the assignments of tasks to compute resources throughout the search can lead to substantial performance improvements. We present experimental results obtained with software developed as part of the Virtual Instrument project, and discuss the impact of our findings on future Virtual Instrument implementations.

Pre-2018 CSE ID: CS2002-0720

The computational Grid provides a promising platform for the efficient execution of parameter sweep applications over very large parameter spaces. Scheduling such applications is challenging because target resources are heterogeneous, because their load and availability varies dynamically, and because tasks may share common data files. In this paper, we propose a scheduling algorithm for parameter sweep applications on the Grid. We consider standard heuristics for task/host assignment (Max-min, Min-min, Sufferage), and we propose an extension of Sufferage called XSufferage. Using simulation, we demonstrate 3 results: 1) that XSufferage can take advantage of file sharing to achieve better performance than the other heuristics under a wide variety of load conditions, 2) that it is possible to characterize the environments under which different heuristics perform best, and 3) that it is possible to characterize the performance of different heuristics under the (realistic) assumption of varying accuracy of performance estimations.

Pre-2018 CSE ID: CS1999-0632

Computational Grids are becoming an increasingly important and powerful platform for the execution of large-scale, resource-intensive applications. However, it remains a challenge for applications to tap the potential of Grid resources in order to achieve performance. In this paper, we illustrate how applications can leverage Grids to achieve performance through coallocation. We describe our experiences developing a scheduling strategy for a real-life parallel tomography application targeted to Grids which contain both workstations and parallel supercomputers. Our strategy uses dynamic information exported by a supercomputer's batch scheduler to simultaneously schedule on workstations and immediately available supercomputer nodes. This strategy is of great practical interest because it combines resources available to the typical research lab: time-shared workstations and CPU time in remote space-shared supercomputers. We show that this strategy improves the performance of the parallel tomography application compared to traditional scheduling strategies, which target the application to either type of resource alone.

Pre-2018 CSE ID: CS2000-0642