Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Adaptive parallel interval branch and bound algorithms based on their performance for multicore architectures

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

This work studies how to adapt the number of threads of a parallel Interval Branch and Bound algorithm to the available computational resources based on its current performance. Basically, a thread can create a new thread that will process part of the ancestor workload. In this way, load balancing is inherent to the creation of threads. The applications in which we are interested use branch-and-bound algorithms which are highly irregular and therefore difficult to predict. The proposed methods can be used for more predictable algorithms as well. This research complements and does not substitute other devices that improve the exploitation of the system, such as dynamic scheduling policies or work-stealing. Several approaches are presented. They differ in the metrics used and in the need or not having to modify the Operating System (O.S.). The scenario for this research is just one multithreaded application running in a multicore architecture. Experimental results show that the appropriate number of running threads can be determined at run-time, avoiding having to statically establish the number of threads of an application. Thread creation decisions have to be made frequently to obtain better results, but are time-consuming. One of the presented models uses the existence of an idle processor to carry out these decisions, obtaining the desired results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aater Suleman M, Qureshi MK, Patt YN (2008) Feedback-driven threading: power-efficient and high-performance execution of multi-threaded workloads on CMPs. In: ASPLOS XIII: proceedings of the 13th international conference on architectural support for programming languages and operating systems, New York, NY, USA. ACM Press, New York, pp 277–286

    Chapter  Google Scholar 

  2. Casado LG, Martínez JA, García I, Hendrix EMT (2008) Branch-and-bound interval global optimization on shared memory multiprocessors. Optim Methods Softw 23(3):689–701

    Article  MathSciNet  MATH  Google Scholar 

  3. Dixon LCW, Szegö GP (1975) Towards global optimization, 1. North-Holland, Amsterdam

    Google Scholar 

  4. Duran A, Corbalán J, Ayguadé E (2008) An adaptive cut-off for task parallelism. In: SC ’08: proceedings of the 2008 ACM/IEEE conference on supercomputing, Piscataway, NJ, USA, 2008. IEEE Press, New York, pp 1–11

    Google Scholar 

  5. Frigo M, Leiserson CE, Randall KH (1998) The implementation of the Cilk-5 multithreaded language. In: PLDI ’98: proceedings of the ACM SIGPLAN 1998 conference on programming language design and implementation, New York, NY, USA, 1998. ACM Press, New York, pp 212–223

    Chapter  Google Scholar 

  6. Gendron B, Crainic TG (1994) Parallel branch-and-bound algorithms: survey and synthesis. Oper Res 42(6):1042–1066

    Article  MathSciNet  MATH  Google Scholar 

  7. Gustafson JL (1988) Reevaluating Amdahl’s law. Commun ACM 31(5):532–533

    Article  Google Scholar 

  8. Lee J, Park J-H, Kim H, Jung C, Lim D, Han SY (2010) Adaptive execution techniques of parallel programs for multiprocessors. J Parallel Distrib Comput 70(5):467–480

    Article  Google Scholar 

  9. Olivier SL, Prins JF (2009) Evaluating OpenMP 3.0 run time systems on unbalanced task graphs. In: IWOMP ’09: proceedings of the 5th international workshop on OpenMP, 2009. Springer, Berlin, Heidelberg, pp 63–78

    Google Scholar 

  10. OpenMP Architecture Review Board (2008). OpenMP application program interface, version 3.0. OpenMP

  11. Penry DA (2009) Multicore diversity: a software developer’s nightmare. SIGOPS Oper Syst Rev 43(2):100–101

    Article  Google Scholar 

  12. Reinders J (2007) Intel threading building blocks. O’Reilly, Sebastopol

    Google Scholar 

  13. Walster GW, Hansen ER, Sengupta S (1985) Test results for a global optimization algorithm. In: Boggs PT, Byrd RH, Schnabel RB (eds) Numerical optimization 1984. SIAM, Philadelphia, pp 272–287

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Architecture and Electronics, University of Almeria, Almeria, Spain

    J. F. Sanjuan-Estrada & L. G. Casado

  2. Department of Computer Architecture, University of Málaga, Málaga, Spain

    I. García

Authors
  1. J. F. Sanjuan-Estrada
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. L. G. Casado
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. I. García
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to L. G. Casado.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sanjuan-Estrada, J.F., Casado, L.G. & García, I. Adaptive parallel interval branch and bound algorithms based on their performance for multicore architectures. J Supercomput 58, 376–384 (2011). https://doi.org/10.1007/s11227-011-0594-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-011-0594-4

Keywords

Search

Navigation