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.
W niniejszej pracy przedstawiono zastosowanie metody podziału i ograniczeń B&B (ang. Branch and Bound) do problemu podziału funkcjonalności między sprzęt i oprogramowanie. Metoda B&B daje rozwiązanie optymalne, ma jednak wykładniczą złożoność obliczeniową. Przyspieszenie uzyskiwane jest na drodze eliminacji nierokujących gałęzi w przestrzeni poszukiwań, a jej kluczowym elementem jest definicja funkcji ograniczenia dolnego. W niniejszej pracy zaproponowano funkcję ograniczenia dolnego, która w prosty i dokładny sposób wyznacza minimalną wartość funkcji celu dla wszystkich podproblemów. Opisaną metodę wykorzystano do implementacji algorytmu kryptograficznego AES w układzie FPSLIC. Uzyskane wyniki potwierdziły tezę, że metoda B&B zastosowana do problemu podziału funkcjonalności między sprzęt i oprogramowanie umożliwia optymalizację wielokryterialną.
EN
This paper presents the application of Branch&Bound method for solution of hardware/software partitioning problem. The method produces optimal solution, but bas exponential computational complexity. Speedup of computation is obtained by bounding unfruitful branches in exploration space and the key element of this process is the definition of lower bound function. In ibis paper lower bound function is defined, which enables multiobjective hardware/software partitioning with constraints. The method described is used for implementation of cryptographic algorithm AES in FPSLIC device. Achieved results confirmed that using hardware/software codesing methodology assures obtaining the implementation of predictable parameters.
W pracy zaprezentowano problematykę kryptoanalizy implementacji sprzętowych bazującej na informacji z kanału bocznego. Opisano rodzaje ataków pasywnych ze szczególnym uwzględnieniem analizy czasowej i analizy poboru mocy. Przedstawiono podstawowe metody zapobiegania atakom. Zaproponowano metodę projektowania wykorzystującą wyrównywanie mocy w asynchronicznych układach kombinacyjnych oraz w układach synchronicznych. Dokonano implementacji algorytmu AES w układzie FPGA Xilinx Spartan II-E w wersji standardowej i zmodyfikowanej. Osiągnięte wyniki symulacji wykazały, że zaproponowana metoda projektowania skutecznie uniemożliwia wykonanie analizy mocy DPA.
EN
The paper presents cryptoanalysis issues of hardware implementations based on side channel information. Kinds of passive attacks are described, especially considering timing analysis and power analysis. Basic countermea-sures against known attacks are shown. New design method based on both asynchronous and synchronous power equalization is proposed. Algorithm AES is chosen for implementation on FPGA Xilinx Spartan II-E device using standard and modified design methodology. Simulation results show that proposed design methodology efficiently prevents from carring out differential power analysis.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.