EXPERIMENTAL METHODOLOGIES FOR LARGE-SCALE SYSTEMS: A SURVEY
Abstract
The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes it extremely difficult to build analytical models that allow for a satisfying prediction. Hence, it raises the question on how to validate algorithms if a realistic analytic analysis is not possible any longer. As for some many other sciences, the one answer is experimental validation. Nevertheless, experimentation in Computer Science is a difficult subject that today still opens more questions than it solves: What may an experiment validate? What is a "good experiment"? How to build an experimental environment that allows for "good experiments"? etc. In this paper we will provide some hints on this subject and show how some tools can help in performing "good experiments", mainly in the context of parallel and distributed computing. More precisely we will focus on four main experimental methodologies, namely in-situ (real-scale) experiments (with an emphasis on PlanetLab and Grid'5000), Emulation (with an emphasis on Wrekavoc) benchmarking and simulation (with an emphasis on SimGRID and GridSim). We will provide a comparison of these tools and methodologies from a quantitative but also qualitative point of view.
References
- Commun. ACM 32(1), 9 (1989), DOI: 10.1145/63238.63239. Crossref, ISI, Google Scholar
- Commun. ACM 23(10), 543 (1980), DOI: 10.1145/359015.359016. Crossref, ISI, Google Scholar
-
J. S. Marron , F. Hernández-Campos and F. D. Smith , Mice and elephants visualization of internet traffic , Proceedings of 15th Conference on Computational Statistics , eds.W. Härdle and B. Rónz ( Physika Verlag , Heidelberg , 2002 ) . Google Scholar - Paul Luckowicz, Walter F. Tichy, Ernst A. Heinz, and Lutz Prechelet. Experimental evaluation in computer science: a quantitative study. Technical Report iratr-1994-17, University of Karlshrue, Germany, 1994 . Google Scholar
- Computer 31(5), 32 (1998), DOI: 10.1109/2.675631. Crossref, Google Scholar
- Computer 31(5), 23 (1998), DOI: 10.1109/2.675630. Crossref, ISI, Google Scholar
- Commun. ACM 48(4), 27 (2005), DOI: 10.1145/1053291.1053309. Crossref, Google Scholar
- Commun. ACM 24(11), 725 (1981), DOI: 10.1145/358790.358791. Crossref, ISI, Google Scholar
- Dror G. Feitelson. Experimental Computer Science: The Need for a Cultural Change. Internet version: http://www.cs.huji.ac.il/~feit/papers/exp05.pdf, December 2006 . Google Scholar
- D. D.Johnson. A theoretician's guide to the experimental analysis of algorithms, 2001. AT&T Labs Research. Available from http://www.research.att.com/~dsj/papers/experguide.ps . Google Scholar
- Algorille Team, Algorithms for the Grid. INRIA Research proposal, July 2006. Available at http://www.loria.fr/equipes/algorille/algorille2.pdf . Google Scholar
-
Franck Cappello and Daniel Etiemble , MPI versus MPI+OpenMP on IBM SP for the NAS benchmarks , Proceedings of the 2000 ACM/IEEE conference on Supercomputing ( 2000 ) . Google Scholar -
Dan Tsafrir and Dror G. Feitelson , Instability in parallel job scheduling simulation: the role of workload urries , 20th International Parallel and Distributed Processing Symposium (IPDPS 2006) ( 2006 ) . Google Scholar - IEEE/ACM Transactions on Networking 3(3), 226. Crossref, ISI, Google Scholar
- The DAS-3 project: http://www.starplane.org/das3/ . Google Scholar
- The Grid 5000 project: http://www.grid5000.org/ . Google Scholar
- International Journal of High Performance Computing Applications 20(4), 481 (2006), DOI: 10.1177/1094342006070078. Crossref, ISI, Google Scholar
- Planet lab: http://www.planet-lab.org/ . Google Scholar
- The xen virtual machine monitor: http://www.cl.cam.ac.uk/research/srg/netos/xen/ . Google Scholar
- Qemu: open source processor emulator http://www.qemu.org/ . Google Scholar
- CLADE 52 (2004). Google Scholar
-
L.-C. Canon and E. Jeannot , Wrekavoc a Tool for Emulating Heterogeneity , 15th IEEE Heterogeneous Computing Workshop (HCW'06) ( 2006 ) . Google Scholar - International Journal of High Performance Computing Applications 5(3), 63 (1991), DOI: 10.1177/109434209100500306. Crossref, ISI, Google Scholar
Ewa Deelman , Pegasus: Mapping scientific work-flows onto the grid, European Across Grids Conference (2004) pp. 11–20. Google Scholar- ACM Transactions on Modeling and Computer Simulation 7, 78 (1997), DOI: 10.1145/244804.244807. Crossref, Google Scholar
George F. Riley , The Georgia Tech Network Simulator, ACM SIGCOMM workshop on Models, Methods and Tools for Reproducible Network Research (2003) pp. 5–12. Google Scholar- Rajkumar Buyya and M. Manzur Murshed. GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing. CoRR, cs.DC/0203019, 2002 . Google Scholar
-
Henri Casanova , Arnaud Legrand and Martin Quinson , SimGrid: a Generic Framework for Large-Scale Distributed Experiments , 10th IEEE International Conference on Computer Modeling and Simulation ( 2008 ) . Google Scholar Elliot Jaé , Danny Bickson and Scott Kirkpatrick , Everlab: a production platform for research in network experimentation and computation, LISA'07: Proceedings of the 21st conference on Large Installation System Administration Conference (2007) pp. 1–11. Google Scholar- The RAMP project: Research Accelerator for Multiple Processors . Google Scholar
- SIGOPS Oper. Syst. Rev. 36(SI), 271 (2002), DOI: 10.1145/844128.844154. Crossref, Google Scholar
Brian White , An integrated experimental environment for distributed systems and networks, Proc. of the Fifth Symposium on Operating Systems Design and Implementation (USENIX Association, Boston, MA, 2002) pp. 255–270. Google Scholar- iproute2+tc notes: http://snafu.freedom.org/linux2.2/iproute-notes.html . Google Scholar
- SIGCOMM Comput. Commun. Rev. 27(1), 31 (1997), DOI: 10.1145/251007.251012. Crossref, Google Scholar
- Multiagent and Grid Systems 3(3), 281 (2007). Crossref, Google Scholar
- Softw., Pract. Exper. 34(7), 653 (2004), DOI: 10.1002/spe.585. Crossref, ISI, Google Scholar
- Computing in Science and Engineering 1(1), 42 (1999). Crossref, ISI, Google Scholar
-
Stephen Naicken and Anirban Basu , Barnaby Livingston, and Sethalat Rodhetbhai. Towards yet another peer-to-peer simulator , Proc. Fourth International Working Conference Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs '06) ( 2006 ) . Google Scholar Pedro García , Planetsim: A new overlay network simulation framework, Software Engineering and Middleware, SEM 2004,LNCS 3437 (Linz, Austria, 2005) pp. 123–137. Google Scholar- Márk Jelasity, Alberto Montresor, Gian Paolo Jesi, and Spyros Voulgaris. PeerSim. http://peersim.sourceforge.net/ . Google Scholar
- International J. of High Performance Computing Applications 17(4), (2003). Google Scholar
Wim Depoorter , Scalability of grid simulators: An evaluation, Euro-Par '08: Proceedings of the 14th international Euro-Par conference on Parallel Processing (Springer-Verlag, Berlin, Heidelberg, 2008) pp. 544–553. Google Scholar-
Kayo Fujiwara and Henri Casanova , Speed and Accuracy of Network Simulation in the SimGrid Framework , Workshop on Network Simulation Tools (NSTools) ( 2007 ) . Google Scholar


