Przyspieszanie metody podziału i ograniczeń dla problemu podziału funkcjonalności na sprzęt i oprogramowanie

• Autorzy: Strachacki, M.

Warianty tytułu

EN

Speedup of branch and bound method for hw/sw partitioning

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

metoda podziału i ograniczeń; parametry metody podziału i ograniczeń; analiza wrażliwości

EN

branch and bound method; sensitivity analysis; B&B parameters

• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2008
• Tom: T. 15
• Strony: 55-60
• Opis fizyczny: Bibliogr. 5 poz., rys., tab.

Twórcy

autor

Strachacki, M.

• 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.