Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first previous next last
cannonical link button

http://yadda.icm.edu.pl:80/baztech/element/bwmeta1.element.baztech-article-BPG5-0031-0035

Czasopismo

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

Tytuł artykułu

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

Autorzy Strachacki, M. 
Treść / Zawartość
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  
Wydawca Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
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.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-BPG5-0031-0035
Identyfikatory