Computational Grids lend themselves well to parameter sweep applications, in which independent tasks calculate results for points in a parameter space. However, it is possible for a parameter space to become so large as to pose prohibitive system requirements. In these cases, user-guided searchespromise to reduce overall computation time. In this paper, we address an interesting challenge posed by these user-directed searches: how should computing resources be allocated to application tasks as the overall computation is being guided by the user? We present a model for user-guided searches, and then propose a number of resource allocation strategies and evaluate them in simulation. We find that prioritizing the assignments of tasks to computing resources throughout the search can lead to substantial performance improvements.
Get full access to this article
View all access options for this article.
References
1.
Abramson, D., Sosic, R., Giddy, J., and Hall, B., 1995. Nimrod: A tool for performing parametrized simulations using distributed workstations . In Proceedings of the 4th IEEE Symposium on High Performance Distributed Computing.
2.
Aldous, D., and Vazirani, U., 1994. Go with the winners’ algorithms . In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science.
3.
Altschul, S., Gish, W., Miller, W., Myers, E., and Lipman, D., 1990. Basic local alignment search tool . Journal of Molecular Biology215: 403–410 .
4.
Back, T., 1996. Evolutionary Algorithms in Theory and Practice, Oxford University Press, Oxford .
5.
Baluja, S., 1995. An empirical comparison of seven iterative and evolutionary function optimization heuristics. Technical report, Carnegie Mellon University .
6.
Baluja, S., and Caruana, R., 1995. Removing the genetics from the standard genetic algorithm . In Proceedings of the 12th International Conference on Machine Learning.
7.
Basney, J., Livny, M., and Mazzanti, P., 2000. Harnessing the capacity of computational Grids for high energy physics . In Conference on Computing in High Energy and Nuclear Physics.
8.
Beynon, M., Ferreira, R., Kurc, T.M., Sussman, A., and Saltz, J.H., 2000. DataCutter: Middleware for filtering very large scientific datasets on archival storage systems . In IEEE Symposium on Mass Storage Systems, pp. 119–134 .
9.
Casanova, H., 2001. Simgrid: A Toolkit for the simulation of application scheduling . In Proceedings of the IEEE/ACM International Symposium on Cluster Computing and the Grid.
10.
Casanova, H., Bartol, T., Berman, F., Birnbaum, A., Dongarra, J., Ellisman, M., Faerman, M., Gockay, E., Miller, M., Obertelli, G., Pomerantz, S., Sejnowski, T., Stiles, J., and Wolski, R., 2002. The Virtual Instrument: Support for Grid-enabled scientific simulations. Technical Report CS2002-0707, Department of Computer Science and Engineering, University of California, San Diego, CA .
11.
Casanova, H., Bartol, T., Stiles, J., and Berman, F., 2001. Distributing MCell simulations on the Grid . The International Journal of High Performance Computing Applications14(3): 243–257 .
12.
Casanova, H., Obertelli, G., Berman, F., and Wolski, R., 2000a. The AppLeS parameter sweep template: User-level middleware for the Grid . In Proceedings of Supercomputing.
13.
Casanova, H., Legrand, A., Zagorodnov, D., and Berman, F., 2000b. Heuristics for scheduling parameter sweep applications in Grid environments . In Proceedings of the 9th Heterogeneous Computing Workshop (HCW’00), pp. 349–363 .
14.
Digalakis, J., and Margaritis, K., 2002. An experimental study of benchmarking functions for evolutionary algorithms . International Journal of Computer Mathematics79(4): 403–416 .
15.
Durbin, R., Eddy, S., Krogh, A., and Mitchison, G.J., 1998. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, A tutorial introduction to hidden Markov models and other probabilistic modelling approaches in computational sequence analysis, Cambridge University Press, Cambridge .
16.
Faerman, M., 2003. Resource Allocation for Guided Parameter Search Applications on High Performance Parallel Computing Environments. PhD thesis, University of California, San Diego, CA.
17.
Faerman, M., Birnbaum, A., Casanova, H., and Berman, F., 2002. Resource allocation for steerable parallel parameter searches . In Proceedings of the 3rd International Workshop on Grid Computing, Lecture Notes in Computer Science Vol. 2536, Springer-Verlag, Berlin, pp. 157–168 .
18.
Feitelson, D.G., and Jette, M.A., 1997. Improved utilization and responsiveness with gang scheduling. In D. G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Springer Verlag, Berlin , pp. 238–261.
19.
Feitelson, D.G., Rudolph, L., Schwiegelshohn, U., Sevcik, K.C., and Wong, P., 1997. Theory and practice in parallel job scheduling. In D. G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Springer-Verlag, Berlin , pp. 1–34.
20.
Geist, G., Kohl, J., and Papadopoulos, P., 1997. CUMULVS: Providing fault tolerance, visualization, and steering of parallel applications . The International Journal of Supercomputer Applications and High Performance Computing11(3): 224–235 .
21.
Griewank, A.O., 1981. Generalized decent for global optimization . Journal of Optimization Theory and Applications34(1): 11–39 .
22.
Hagerup, T., 1997. Allocating independent tasks to parallel processors: an experimental study . Journal of Parallel and Distributed Computing47: 185–197 .
23.
Hart, W.E., 1994. Adaptive Global Optimization with Local Search. PhD thesis, University of California, San Diego, CA.
24.
Hart, W.E., and Belew, R.K., 1996. Optimization with genetic algorithm hybrids that use local search. In Adaptive Individuals in Evolving Populations, Models and Algorithms, Addison-Wesley, Reading, MA , pp. 483–494.
25.
Higham, N.J., 1993. The accuracy of floating point summation . SIAM Journal on Scientific Computing14(4): 783–799 .
26.
Houck, C.R., Joines, J.A., Kay, M.G., and Wilson, J.R., 1997. Empirical investigation of the benefits of partial lamarckianism . Evolutionary Computation5(1): 31–60 .
27.
Kuncheva, L., 2002. Switching between selection and fusion in combining classifiers: An experiment . IEEE Transactions on Systems, Man and Cybernetics–Part B: Cybernetics32(2): 146–156 .
28.
Land, M.W.S., 1998. Evolutionary Algorithms with Local Search for Combinatorial. PhD thesis, University of California, San Diego, CA.
29.
Leary, R.H., and Doye, J.P.K., 1999. Tetrahedral global minimum for the 98-atom Lennard–Jones cluster . Physical Review E60(6): R6320–R6322 .
30.
Majumdar, A., 2000. Parallel performance study of Monte Carlo photon transport code on shared-, distributed-, and distributed-shared-memory architectures . In Proceedings of the 14th Parallel and Distributed Processing Symposium, IPDPS’00,pp. 93–99 .
31.
Mathias, K.E., and Whitley, D., 1994a. Initial performance comparisons for the delta coding algorithm . In International Conference on Evolutionary Computation, pp. 433–438 .
32.
Mathias, K.E., and Whitley, D., 1994b. Transforming the search space with gray coding . In International Conference on Evolutionary Computation, pp. 513–518 .
33.
Michalewicz, Z., and Fogel, D., 2000. How to Solve It: Modern Heuristics, Springer, Berlin .
34.
Milano, M., Schmidhuber, J., and Koumoutsakos, P., 2001. Active Learning with Adaptive Grids, Lecture Notes in Computer Science Vol. 2130, p. 436-436.
35.
Natrajan, A., Crowley, M., Wilkins-Diehr, N., Humphrey, M., Fox, A., and Grimshaw, A., 2001. Studying protein folding on the Grid: Experiences using CHARM on NPACI resources under legion . In Proceedings of the 10th IEEE International Symposium on High-Performance Distributed Computing (HPDC-10).
36.
Parker, S., and Johnson, C., 1995. SCIRun: a scientific programming environment for computational steering . In Proceedings of the 1995 ACM/IEEE Supercomputing Conference.
37.
Potter, M.A., 1997. The Design and Analysis of a Computational Model of Cooperative Coevolution. PhD thesis, George Mason University, Fairfax, VA.
38.
Rastrigin, L.A., 1974. Systems of Extremal Control, Nauka, Moscow (in Russian).
39.
Rogers, S., and Ywak, D., 1991. Steady and unsteady solutions of the incompressible Navier–Stokes equations . AIAA Journal29(4): 603610-603610 .
40.
Rosenbrock, H.H., 1960. An automatic method for finding the greatest or least value of a function . The Computer Journal(3): 175–184 .
41.
Salomon, R., 1996. Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions: A survey of some theoretical and practical aspects of genetic algorithms . BioSystems39: 263–278 .
42.
Stiles, J.R., and Bartol, T.M., 2001. Monte Carlo methods for simulating realistic synaptic microphysiology using MCell. In Computational Neuroscience–Realistic Modeling for Experimentalists, chapter 4, CRC Press, Boca Raton, FL . MCell online information available at http://www.mcell.cnl.salk.edu.
43.
Torn, A., and Zilinskas, A., 1989. Global Optimization, Lecture Notes in Computer Science Vol. 350, Springer-Verlag, Berlin .
44.
Tsutsui, S., Pelikan, M., and Goldberg, D.E., 2001. Evolutionary algorithm using marginal histogram in continuous domain. In Optimization by Building and Using Probabilistic Models (OBUPM) 2001, San Francisco, CA , pp. 230–233.
45.
van den Bergh, F., and Engelbrecht, A.P., 2001. Effects of swarm size on cooperative particle swarm optimizers . In L. Spector et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), San Francisco, CA, Morgan Kaufmann, San Mateo, CA, pp. 892–899 .
46.
van Laarhoven, P., and Aarts, E., 1987. Simulated Annealing: Theory and Applications, Reidel, Dordrecht .
47.
Vetter, J., and Schwan, K., 1995. Progress: a toolkit for interactive program steering . In Proceedings of the 1995 International Conference on Parallel Processing.
48.
Voigt, H., and Lange, J., 1998. Local evolutionary search enhancement by random memorizing . In Proceedings of the 1998 IEEE World Congress on Computational Intelligence–The 1998 IEEE International Conference on Evolutionary Computation(ICEC’98), IEEE Press, Piscataway, NJ.
49.
Waldspurger, C., 1995. Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management. PhD thesis, Massachusetts Institute of Technology.
50.
Waldspurger, C.A., and Weihl, W.E., 1995. Lottery scheduling: flexible proportional-share resource management . In Proceedings of the 1st Symposium on Operating Systems Design and Implementation.
51.
Yarrow, M., McCann, K., Biswas, R., and Van der Wijngaart, R., 2000. An advanced user interface approach for complex parameter study process specification on the information power Grid . In Proceedings of GRID 2000, Bangalore, India.
