Warianty tytułu
Speedup of branch and bound method for hw/sw partitioning
Języki publikacji
Abstrakty
Niniejsza praca przedstawia analizę wrażliwości metody podziału i ograniczeń B&B (ang. branch and bound) używanej do podziału funkcjonalności na sprzęt i oprogramowanie. Zbadano teoretyczny wpływ wszystkich parametrów B&B na czas obliczeń. Wyniki eksperymentów ujawniły, że najwrażliwszymi parametrami są: funkcja ograniczenia dolnego, reguła wyboru podproblemu, reguła podziału oraz rozwiązanie początkowe. Aby skrócić czas obliczeń metody B&B należy odpowiednio zoptymalizować parametry przy użyciu algorytmu symulowane-go wyżarzania. Testy wykazały, że dla rozmiaru problemu n = 30 uzyskano średnio 130-krotne przyspieszenie obliczeń. Opisana optymalizacja hybrydowa jest najwydajniejszą z metod dotychczas zaprezentowanych w literaturze.
This paper presents sensitivity analysis of branch and bound (B&B) method used for hardware/software partitioning task. The impact of all B&B parameters on computation time is theoretically analyzed and results of experiments are presented. Results show that most sensitive parameters are a lower bound function, a selection rule, a branching rule and an initial solution. To shorten B&B computation time these parameters have to be set properly and additional preoptimization step should be applied. This pre-optimization step uses simulated annealing to set parameters in limited time. Results of experiments show that the computation time speedup x 130 is achieved on average. This hybrid optimization is the most efficient presented so far.
Rocznik
Tom
Strony
55-60
Opis fizyczny
Bibliogr. 5 poz., rys., tab.
Twórcy
autor
- Politechnika Gdańska, Katedra Systemów Mikroelektronicznych, Gdańsk ul. Narutowicza 11/12
Bibliografia
- [1] Clausen J.: Branch and Bound Algorithms - Principles and Examples, Lecture Notes, University of Copenhagen, Copenhagen, Denmark, March 12, 1999.
- [2] Dutkiewicz L.: Algorytmy Decyzyjne, Materiały do wykładu, Akademia Górniczo-Hutnicza, Kraków, Poland, March 21, 2007.
- [3] Bihn N. N., Imai M., Shiomi A., Hikichi N.: A hardware/software partitioning algorithm for designing pipelined ASIPs with least gale counts, in Proceedings of the 33rd Design Automation Conference (DAC'2003), pp. 527-532, Las Vegas, Nevada, June 3-7, 1996.
- [4] Axelsson J.: A Hardware/Software Codesign Approach to System-Level Design of Real-Time Applications, in Proceedings of Swedish National Real-time Systems Conference (SNART' 1997), Lund, Sweden, August 21-22, 1997.
- [5] INFORMS Computing Society: Mathematical Programming Glossary: Branch and Bound, 2006.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BPG5-0031-0035