Zastosowanie metody podziału i ograniczeń w wielokryterialnym problemie podziału HW/SW do implementacji algorytmów kryptograficznych

• Autorzy: Strachacki, M.

Warianty tytułu

EN

The application of Branch&Bound method in multiobjective HW/SW partitioning problem for implementation of cryptographic algorithmims

• Języki publikacji: PL

Abstrakty

PL

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.

Słowa kluczowe

PL

metoda podziału i ograniczeń B&B; funkcja ograniczenia dolnego; algorytm kryptograficzny AES; platforma implementacyjna

EN

application of Branch&Bound method; multiobjective hardware/software partitioning; cryptographic algorithm AES

• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2007
• Tom: T. 14
• Strony: 593-600
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Strachacki, M.

• Katedra Systemów Mikroelektronicznych, Politechnika Gdańska

Bibliografia

• [1] Clausen J.: Branch and Bound Algorithm - Principles and Examples, Department of Computer Science, University of Copenhagen, Denmark, March 12, 1999.
• [2] Dutkiewicz L: Algorytmy Decyzyjne, materiały do wykładu, Katedra Automatyki Akademii Górniczo-Hutniczej, Kraków 2007.
• [3] Jigang W., Thambipillai S.: A Branch-and-Bound Algorithm for Hardware/Software Partitioning, Centre for High Performance Embedded Systems, Nanyang Technological University, Singapore, IEEE 2004.
• [4] Jędruch W.: Sztuczna inteligencja, materiały do wykładu, Katedra Systemów Automatyki Politechniki Gdańskiej, Gdańsk 1999.
• [5] Axelsson J.: A Hardware/Software Codesign Approach to System-Level Design of Real-Time Applications, Dept. of Computer and Information Science Linkoping University, 1997.
• [6] Azzedine A., Diguet J., Pillippe J.: Large Exploration for HW/SW partitioning of Multirate and Aperiodic Real-Time Systems, Universite de Bretagne SUD; Lester Lab; Lorient 2003.
• [7] Atmel Corporation: Starter Kit. FPSLICTM Programmable SLI A TSTK94, Atme12002.
• [8] Atmel Corporation: AT94K Series Field Programmable System Level Integrated Circuit, Atmel 2001.
• [9] Daemen J., Rijmen V.: AES Proposal: Rijndael, First AES Conference, Ventura, California, August 1998.
• [10] Strachacki M.: Analiza i realizacja w układach FPGA algortmów szyfrowania Rijndael, Serpent i Twofish, praca magisterska, Katedra Architektury Systemów Komputerowych Politechniki Gdańskiej, Gdańsk 2001.
• [11] Strachacki M.: Realizacja algorytmów szyfrowania symetrycznego w układach FPGA Xilinx Virtex II, VI Krajowa Konferencja Naukowa Reprogramowalne Układy Cyfrowe RUC'2003, Szczecin, 8-9 maja 2003, pp 171-178.
• [12] Dembek L, Strachacki M.: Heterogeniczna realizacja algorytmu AES w układzie SoC FPSLIC z zastosowaniem technik projektowania sprzętowo-programowego, III Krajowa Konferencja Naukowo-Techniczna Technologie Informacyjne TI'2005, Gdańsk, maj 2005, pp 787-794.