skip to main content
10.1145/2486092.2486116acmconferencesArticle/Chapter ViewAbstractPublication PagespadsConference Proceedingsconference-collections
research-article

Approximate parallel simulation of web search engines

Published:19 May 2013Publication History

ABSTRACT

Large scale Web search engines are complex and highly optimized systems devised to operate on dedicated clusters of processors. Any, even a small, gain in performance is beneficial to economical operation given the large amount of hardware resources deployed in the respective data centers. Performance is fully dependent on users behavior which is featured by unpredictable and drastic variations in trending topics and arrival rate intensity. In this context, discrete-event simulation is a powerful tool either to predict performance of new optimizations introduced in search engine components or to evaluate different scenarios under which alternative component configurations are able to process demanding workloads. These simulators must be fast, memory efficient and parallel to cope with the execution of millions of events in small running time on few processors. In this paper we propose achieving this objective at the expense of performing approximate parallel simulation.

References

  1. C. S. Badue, J. M. Almeida, V. Almeida, R. A. Baeza-Yates, B. A. Ribeiro-Neto, A. Ziviani, and N. Ziviani. Capacity planning for vertical search engines. CoRR, abs/1006.5059, 2010.Google ScholarGoogle Scholar
  2. C. Bonacic, C. Garc?a, M. Mar?n, M. Prieto-Mat?as, and F. Tirado. Building efficient multi-threaded search nodes. In CIKM, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. A. Boukerche and S. K. Das. Dynamic load balancing strategies for conservative parallel simulations. SIGSIM Simul. Dig., 27(1):20--28, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. A. Z. Broder, D. Carmel, M. Herscovici, A. Soffer, and J. Y. Zien. Efficient query evaluation using a two-level retrieval process. In CIKM, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. C. D. Carothers and R. M. Fujimoto. Efficient execution of time warp programs on heterogeneous, now platforms. TPDS, 11(3) 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. L.-l. Chen, Y.-s. Lu, Y.-p. Yao, S.-l. Peng, and L.-d. Wu. A well-balanced time warp system on multi-core environments. In PADS, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. V. Gil-Costa, J. Lobos, A. Inostrosa and M. Marin. Capacity planning for search engines: An approach based on coloured Petri nets. In ICATPN, 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. G. DAngelo and M. Bracuto. Distributed simulation of large-scale and detailed models. IJSPM, 5(2) 2009.Google ScholarGoogle Scholar
  9. B. Fitzpatrick. Distributed caching with memcached. J. of Linux, 2004:72--76, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. A. Freire, F. Cacheda, V. Formoso and V. Carneiro. Analysis of performance evaluation techniques for Large Scale Information Retrieval. In LSDS-IR, 2013.Google ScholarGoogle Scholar
  11. R. Fujimoto. Parallel discrete event simulation. Comm. ACM, 33(10):30--53, Oct. 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Q. Gan and T. Suel. Improved techniques for result caching in web search engines. In WWW, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. R. Geist, J. Hicks, M. Smotherman, and J. Westall. Parallel simulation of petri nets on desktop pc hardware. In WSC, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. D. W. Glazer and C. Tropper. On process migration and load balancing in time warp. TPDS, 4(3) 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. S. Jafer and G. A. Wainer. A performance evaluation of the conservative devs protocol in parallel simulation of devs-based models. In SpringSim (TMS-DEVS), 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. K. Jensen and L. Kristensen. Coloured Petri Nets. Springer-Verlag Berlin Heidelberg, 2009.Google ScholarGoogle ScholarCross RefCross Ref
  17. M. Knoke and G. Hommel. Dealing with global guards in a distributed simulation of colored petri nets. In DS-RT, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. M. Knoke, F. Kuhling, A. Zimmermann, and G. Hommel. Towards correct distributed simulation of high-level petri nets with fine-grained partitioning. In ISPA, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. J. Liu and R. Rong. Hierarchical composite synchronization. In PADS, 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Q. Liu and G. A. Wainer. Multicore acceleration of discrete event system specification systems. Simulation, 88(7) 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. M. L. Loper and R. Fujimoto. Exploiting temporal uncertainty in process-oriented distributed simulations. In WSC, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. M. Marin. Time Warp on BSP. In ESM, 1998.Google ScholarGoogle Scholar
  23. L. Mellon and D. West. Architectural optimizations to advanced distributed simulation. In WSC, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. M. Marzolla. LibCppSim: A SIMULA-like, Portable Process-Oriented Simulation Library in C++. In ESM, 2004.Google ScholarGoogle Scholar
  25. D. M. Nicol: Discrete-Event Simulation in Performance Evaluation. Performance Evaluation 2000: 443--457. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. K.S. Panesar and R.M. Fujimoto. Adaptive flow control in Time Warp. In PADS, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. L. G. Valiant. A bridging model for multi-core computing. J. Comput. Syst. Sci. 1(77), 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. L. G. Valiant. A bridging model for parallel computation. Comm. ACM, 33(8) 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. R. Vitali, A. Pellegrini, and F. Quaglia. Towards symmetric multi-threaded optimistic simulation kernels. In PADS, 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. BSPonMPI. http://bsponmpi.sourceforge.net/Google ScholarGoogle Scholar
  31. MPI. http://www.mcs.anl.gov/research/projects/mpi/Google ScholarGoogle Scholar
  32. OpenMP. http://openmp.org/Google ScholarGoogle Scholar
  33. CPN Tools. http://cpntools.org/Google ScholarGoogle Scholar

Index Terms

  1. Approximate parallel simulation of web search engines

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      SIGSIM PADS '13: Proceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation
      May 2013
      426 pages
      ISBN:9781450319201
      DOI:10.1145/2486092

      Copyright © 2013 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 19 May 2013

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      SIGSIM PADS '13 Paper Acceptance Rate29of75submissions,39%Overall Acceptance Rate398of779submissions,51%

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader