Michael Grand

Lilian Bossuet
email: lilian.bossuet@univ-st-etienne.fr

Guy Gogniat
email: guy.gogniat@univ-ubs.fr

Bertrand Le Gal

Jean-Philippe Delahaye
email: jean-philippe.delahaye@dga.defense.gouv.fr

Dominique Dallet

A Reconfigurable Multi-core Cryptoprocessor for Multi-channel Communication Systems

Keywords: Software Defined Radio, Crypto-processor, Multi-core

This paper presents a reconfigurable Multi-Core Crypto-Processor (MCCP) especially designed to secure multichannel and multi-standard communication systems. Such component meets many constraints like high throughput and flexibility. In contrast, a classical mono-core approach either provides limited throughput or does not allow simple management of multi-channel streams. Nevertheless, parallelism is not sufficient for a multi-standard radio. It is therefore essential to increase MCCP flexibility. To achieve these results, our work takes advantage of the Xilinx FPGA hardware reconfiguration. The proposed MCCP can reach a maximum throughput of 1.7 Gbps at 190 MHz with several AES cipher modes. It uses about 4000 slices on a Virtex 4 FPGA.

I. INTRODUCTION

Multiplicity of wireless communication standards (UMTS, WiFi, WiMax) needs highly flexible and interoperable communication systems. Software based solutions such as Software Defined Radio (SDR) are used to meet the flexibility constraint. Independently, most of radios have to propose cryptographic services such as confidentiality, integrity and authentication (secure-radio). Therefore, integration of cryptographic services into SDR devices is essential.

By using symmetric cipher and hash function, it is possible to propose such services. However, the use of cryptographic functions in secure systems tends to limit their overall throughput. The best performance is achieved by using dedicated hardware cryptographic accelerator to provide cryptographic services [START_REF] Lemsitzer | Multigigabit gcm-aes architecture optimized for fpgas[END_REF], [START_REF] Hodjat | Area-throughput trade-offs for fully pipelined 30 to 70 gbits/s aes processors[END_REF]. These cores can reach throughput of tens of gigabits per second using loop unrolling, pipelining and channel interleaving mechanisms. Although, these throughput efficient cores are useful for mono-standard communication systems, they do not provide the level of flexibility needed by multi-standard systems (due to their dedicated architecture). On the contrary, more flexible crypto-processors do not always provide a sufficient throughput for multi-channel applications [START_REF] Chodowiec | Very compact fpga implementation of aes algorithm[END_REF].

To overcome these issues, this paper presents a reconfigurable Multi-Core Crypto-Processor (MCCP) especially designed to provide both flexibility and high throughput in order to secure multi-standard and multi-channel communication streams. To achieve these results, the MCCP architecture is a trade-off between a throughput efficient design and a multimode design. Moreover, its modular and reconfigurable design (by using FPGA hardware reconfiguration) allows to use any 128-bit block cipher algorithm (e.g. AES, Twofish, Serpent, ...). In this paper, the AES algorithm is used as an illustration. This architecture, which provides a maximum throughput of 1.7 Gbps at 190 MHz on a Virtex4 FPGA, supports most of the block cipher modes of operation such as CTR, CCM, GCCM and CBC-MAC.

The paper is organized as follows: Section 2 introduces multi-channel and multi-standard issues to choose suitable computing architecture. Section 3 presents the top level architecture of the proposed MCCP. Sections 4 and 5 detail the lower layers of the MCCP architecture (i.e. Cryptographic Core and Cryptographic Unit). MCCP operation is explained in section 6 using some didactic examples, according to these examples section 7 provides experimental results. Section 8 discusses the implementation of MCCP operating system. Finally, section 9 concludes this paper.

II. CRYPTOGRAPHIC ARCHITECTURE DESIGN FOR INTENSIVE COMMUNICATION SYSTEMS

A. Design Constraints

The design of a multi-standard and multi-channel secure SDR faces two main constraints:

• A multi-standard secure SDR has to provide several cryptographic algorithms. • A multi-channel secure SDR device handles two or more communication channels at the same time. In consequence, designers have to choose a trade-off between flexibility, throughput performance and area cost. In this paper, a loosely coupled multi-core crypto-processor is presented as an alternative to mono-core crypto-processors and tightly coupled multi-core crypto-processors. This architecture is designed to improve the flexibility/performance trade-off of communication crypto-processors. The next part briefly describes previously published works dealing with hardware cryptographic architectures.

B. Previous Works

The best performance (in terms of throughput) are provided by pipelined cryptographic accelerators. In such cores, encryption algorithm is fully unrolled to produce an efficient pipelined design. For example, GCM (Galois Counter Mode [7]) is especially designed to take profit of pipelined cores. There are several works dealing with hardware implementations of AES-GCM core. [START_REF] Lemsitzer | Multigigabit gcm-aes architecture optimized for fpgas[END_REF], [START_REF] Satoh | High-speed pipelined hardware architecture for galois counter mode[END_REF], [START_REF] Wang | An architecture for the aes-gcm security standard[END_REF] are few examples of such implementations which allow throughput of tens of gigabits per second. But, this kind of architecture has several drawbacks.

Firstly, algorithm unrolling leads to high hardware resource consumption. Secondly, data dependencies in some block cipher modes (e.g. CCM for Counter with CBC-MAC Mode [6]) make unrolled implementations useless. Finally, complex designs are needed when multiplexed channels use different standards. In consequence, pipelined cores are better suited for mono-standard radio than for multi-standard ones.

In contrast, accelerators based on iterative architectures provide a maximum throughput for a minimum cost. In addition, iterative architectures are compliant with all block cipher modes of operation. However, their maximum throughput is still limited if compared to pipelined core throughput [START_REF] Chodowiec | Very compact fpga implementation of aes algorithm[END_REF]. To solve this problem, several multi-core accelerators have been developed. For example, [START_REF] Aziz | An fpga-based aes-ccm crypto core for ieee 802.11i architecture[END_REF], [START_REF] Vu | Fpga implementation aes for ccm mode encryption using xilinx spartan-ii[END_REF], [START_REF] López-Trejo | An fpga implementation of ccm mode using aes[END_REF] use two AES subcores in order to increase the CCM mode throughput. It is noteworthy that sub-cores are tightly coupled and therefore, they cannot work independently.

A more flexible approach uses programmable cryptoprocessor architectures. Such architectures give priority to flexibility at the expense of throughput. Nevertheless, programmable architecture often exhibits a degree of parallelism in order to increase throughput. For example, Celator [START_REF] Fronte | Celator: A multi-algorithm cryptographic co-processor[END_REF] is a programmable crypto-processor composed of several Processing Elements (PE). Celator PEs are connected together to form a matrix like a block cipher state variable. According to PE configuration, cryptographic functions are applied on the value stored in each PE. Celator is able to compute AES, DES or SHA algorithms, providing for example a throughput of 46 Mbps at 190 MHz when computing AES-CBC algorithm.

An other example is Cryptonite [START_REF] Buchty | Cryptonite -a programmable crypto processor architecture for high-bandwidth applications[END_REF]. It is a programmable VLIW crypto-processor that supports AES, DES, MD5 and others cryptographic algorithms. Cryptonite is built around two clusters. Each cluster provides cryptographic functions used by block cipher algorithms. This implementation targets ASIC platform and reaches a throughput of 2.25 Gbps at 400 MHz for the AES-ECB algorithm.

Anyway, all these architectures exhibit tightly coupled parallelisms (i.e. pipelined architecture, VLIW architecture) that need the use of complex software to handle efficiently mutlichannel and multi-standard packet streams. In contrast, the Cryptomaniac architecture [START_REF] Wu | Cryptomaniac: a fast flexible architecture for secure communication[END_REF] has been especially designed to take into account multi-channel and multi-standard issues. Indeed, this processor is based on a loosely coupled multicrypto-processor architecture (crypto-processors can operate independently of each others) where a scheduler core dispatches incoming packets to several simple crypto-processors.

In this paper, a loosely coupled and reconfigurable multicryptoprocessor architecture is presented. Such architecture provides high performance by using dedicated programmable crypto-processors while it remains flexible by the use of FPGA hardware reconfiguration. Hence, performance/flexibility trade-off is improved compared to Cryptomaniac fixed architecture.

III. MULTI-CORE CRYPTO-PROCESSOR ARCHITECTURE

A. General Architecture

Our crypto-processor (Fig. 1) is built around one task scheduler and several programmable Cryptographic Cores. However, the proposed architecture targets FPGA platform to be as flexible as software components embedded in SDR. By this way, our Multi-Core Crypto-Processor (MCCP) can be updated for security or interoperability reasons. Also, MCCP can take profit of new FPGA partial reconfiguration capabilities to reduce resource consumption and increase its flexibility.

The MCCP is embedded in a much larger platform including one main controller and one communication controller which manages communications going through the radio [START_REF] Grand | A reconfigurable crypto sub system for the software communication architecture[END_REF]. MCCP does not generate session keys itself. Keys are generated by the main controller and stored into a dedicated memory. The MCCP is used as a red/black boundary and it provides all necessary cryptographic services needed by an SDR (e.g. secure SCA [START_REF]Security Supplement to the Software Communications Architecture Specification[END_REF]). MCCP architecture is scalable; the number of embedded crypto-core may vary. A four-core architecture has been implemented (Fig. 1). However, more or less than four cores may be implemented according to the communication system requirements.

Proposed MCCP embeds one Task Scheduler which distributes cryptographic tasks to Cryptographic Cores. The Task Scheduler is implemented using a simple 8-bit controller which executes the task scheduling software. It manages the Key Scheduler, the Cross Bar and the Cryptographic Cores. Task Scheduler receives its orders from a 32-bit Instruction Register and returns values to the communication controller through the 8-bit Return Register. Some signals (Start and Done) are used to synchronize instruction execution.

Each Cryptographic Core communicates with the communication controller through the Cross Bar, it enables the Task Scheduler to select a specific core for I/O access. The Key Scheduler generates round keys from the session key stored in the Key Memory. Before launching the key scheduling, the Task Scheduler loads the session key ID into the Key Scheduler which gets the right session key from the Key Memory. To improve system security, the Key Memory cannot be accessed in write mode by the MCCP. In addition, there is no way to get the secret session key directly from the MCCP data port.

Cryptographic Core architecture is further detailed in the Section 4, the next part deals with the MCCP control protocol.

B. MCCP Control Protocol

As it was explained above, the MCCP receives instructions from the communication controller through the control port. Current release of the MCCP takes a 32-bit instruction as input and returns an 8-bit value as output. Available instruction set MCCP executes an instruction in four, non interruptible, steps which are: 1) Write an instruction into the Instruction Register, 2) send a start signal, 3) wait for done signal to be triggered, 4) read returned value from the Return Register. The following list details the available instruction set:

C. Task Mapping

In the current release of our architecture, incoming packets are processed in their order of arrival as fast as possible. In consequence, no scheduling algorithm are involved in packet processing. Such behaviour allows to maximize the MCCP throughput at the expense of latency in packet processing. However, minimizing latency is essential for real time applications (e.g. voice and video transmission) so this issue will be studied in further works.

Currently, when the Task Scheduler receives either an EN-CRYPT or a DECRYPT instruction, an incoming packet is forwarded to the first idle core found. If no core is available, it returns an error flag. The improvement of the task mapping algorithm is discussed at the end of this paper.

IV. CRYPTOGRAPHIC CORE

A. Cryptographic Core Architecture

Architecture of Cryptographic Core is presented on figure 2. On this schematic, dashed lines represent control signals. Each Cryptographic Core communicates with the communication controller and other cores through two FIFOs (512 × 32bits) and one Shift Register (4×32bits). Cryptographic functions are implemented in the Cryptographic Unit and they can be used through the Cryptographic Unit Instruction Set Architecture. Cipher round keys are pre-computed and stored in the Key Cache. An 8-bit Controller generates instruction flow according to the selected block cipher mode. To save resources, it shares its double port instruction memory with its right neighbouring Cryptographic Core. Inter-Cryptographic Core ports are used to convey temporary data from a core to another. For example, in the case of the CCM mode, the MAC value returned by the CBC-MAC mode needs to be encrypted using the CTR mode. When CBC-MAC and CTR algorithms are computed on two different cores, the inter-Cryptographic Core ports is used to forward the MAC value from the CBC-MAC core to the CTR core.

B. Cryptographic Core 8-bit Controller Design

As said above, Cryptographic Core handles several block cipher operation modes leading to complex control state machines. A more flexible approach is to use a general purpose simple controller to generate instruction flows executed by each Cryptographic Unit. Use of such controller allows us to simplify execution of loop conditions for packet encryption/decryption. Because this controller does not perform heavy computations, we use an 8-bit controller providing a simple instruction set. It communicates with the Task Scheduler to receive orders and return execution results.

At prototyping step, a modified 8-bit Xilinx PicoBlaze controller [START_REF]Picoblaze user resources[END_REF] has been used. It embeds a 16 × 8-bit register and some arithmetic and logic operators. Each instruction takes two clock cycles to be executed and its instruction memory size is limited to 1024 × 18-bit instructions stored into one FPGA ram block. In addition, this controller supports interruption handling. To finish, a custom HALT instruction is used to put the controller into a sleep mode after an instruction is sent to the Cryptographic Unit. The controller wakes up when the Cryptographic Unit triggers the done signal.

C. Packet Processing

Incoming packets are processed in the following way: 1) The Task Scheduler sends an instruction to the 8-bit Controller through the shared memory and triggers a start signal. 2) The 8-bit Controller starts pre-computations needed by the selected algorithm and loads data from input FIFO once there are available. 3) Data are processed by blocks of 128 bits and filled into the output FIFO. 4) When all data have been processed, the 8-bit Controller sends a done signal to the Task Scheduler. In order to protect master processor from software attacks (e.g. eavesdropping, spoofing, splicing ), output FIFO is reinitialized if plaintext data does not match the authentication tag. Each FIFO can store a packet of 2048 bytes of data which is sufficient for most of communication protocols.

D. The Available Operation Modes

MCCP can execute GCM, CCM, CTR, CBC-MAC block cipher modes of operation. Available rules for implemented modes of operation are described below:

• Packets from a same channel can be concurrently processed with different Cryptographic Core. • Packets from different channels can be concurrently processed with different Cryptographic Core. • Any single packet can be processed on any single Cryptographic Core. • Using inter-core communication port, any single CCM packet can be processed with two Cryptographic Cores. Right mode of operation is selected by the Task Scheduler according to requested channel algorithm and available resources. As it is said above, a smartly designed Task Scheduler software must be implemented to use available resources in an efficient way. Further details are given in Section VIII.

V. RECONFIGURABLE CRYPTOGRAPHIC UNIT

A. Cryptographic Unit Architecture

Cryptographic Unit (Fig. 3) provides low level cryptographic primitives. It works sequentially on 128-bit words over a 32-bit datapath. For figure 3 example, a Cryptographic Unit embeds a 32-bit AES core, a GHASH core and some arithmetic and logic operators (XOR, adder, comparator). By this way, it can provide support for most block cipher encryption algorithms. In addition, Cryptographic Unit embeds an Instruction Decoder and 4 × 128 bits Bank Register. A 2-bit counter is also used in order to sequentially reach each four 32-bit sub-word of a Bank Register 128-bit word. A one bit register, S register, is used as a start flag.

On figure 3 example, AES and GHASH cores are both compact cores presented in some previously published works. AES core was developed using P. Chodowiec and K. Gaj work [START_REF] Chodowiec | Very compact fpga implementation of aes algorithm[END_REF] for FPGA devices. Because AES-CCM and AES-GCM modes only use encryption mode, AES decryption algorithm was not implemented. AES core is implemented using an iterative architecture and the SubBytes transformation [5] uses look up tables. Iterative architecture implies that AES computation time is key size dependant. Computation of one 128-bit block takes 44, 52 or 60 cycles when using respectively 128-bit, 192-bit or 256-bit key sizes.

GHASH core is based on digit-serial multiplier architecture described in [START_REF] Lemsitzer | Multigigabit gcm-aes architecture optimized for fpgas[END_REF]. Digit-serial multiplication is made using 3-bit digits and it is computed in 43 clock cycles. 32-bit Xor/Comparator processing core takes two 16-byte words as input. According to the selected operation mode, it computes either B = (A ⊕ B) • mask or set equ flag to 1 if previous result is null. Mask value is a 16-bit word which allows user to mask specific bytes of XOR result.

Inc Core allows 16-bit incrementation by 1, 2, 3 or 4 of a 128-bit word. Finally, 32-bit I/O core manages the communications between FIFOs and the Bank Register.

B. Cryptographic Unit Operation

Cryptographic Unit instructions are executed in seven clock cycles from start signal rising edge to done signal falling edge. For example, XOR execution steps are detailed below:

1) When Start signal goes high, instruction port value is sampled into the dedicated input register and the S register is set to 1 (i.e. start flag).

2) Decoder immediately decodes the loaded instruction and sends a start signal from the S register to the right processing core start input (i.e. ghash start init, ghash start finalize, ...). Also, decoder redirects right processing core output to the bank register input and grants read/write access to this core.

C. Instruction Set Architecture

Each Cryptographic Unit is controlled thanks to a specific instruction set which is detailed in Table 1. This instruction set provides I/O instructions and low level cryptographic functions such as AES encryption and GHASH algorithm. The 8-bit instructions are composed of a 4-bit operation code and two 2-bit addresses used to address the bank register.

The use of start instructions (i.e. SGFM and SAES) and finalize instructions (i.e. FGFM and FAES) enables AES and GHASH algorithms to be computed in background while others instructions (e.g. INC, XOR, ...) are executed. Such mechanism allows to save computation time and therefore improves throughput.

LOAD @A

Loads a 128-bit word into the A register.

LOADH @A

Loads the computed H constant into the GHASH core.

SGFM @A

Computes one iteration of the GHASH algorithm.

FGFM @A

Stores the result of the GHASH algorithm into the A register.

SAES @A

Encrypts the value stored in the A register.

FAES @A

Stores the results of the SAES computation into the A register.

INC @A, I

Increments by I the 16 less significant bits of the A register, where I is a 2-bit natural. XOR @A, @B Computes B = (A XOR B) AND mask. EQU @A, @B Sets the equ flag to 1 if A = B and 0 else.

TABLE I THE CRYPTOGRAPHIC UNIT ISA

VI. IMPLEMENTATION OF CRYPTOGRAPHIC ALGORITHMS

A. General Implementation Rules

Cryptographic algorithms executed by proposed MCCP are implemented with Xilinx PicoBlaze assembler language which is used to generate the Cryptographic Unit instruction flow. Cryptographic Unit instruction is executed in three steps: firstly, the Cryptographic Unit instruction is fetched in the controller, secondly the instruction is written in the Cryptographic Unit instruction port and finally the controller waits for execution completion. Performances can be enhanced by pre-fetching the Cryptographic Unit instruction before algorithm execution.

Fetching and pre-fetching steps are made using a LOAD instruction which loads an 8-bit value into the controller bank register. Execution step is made using an OUTPUT instruction which writes an 8-bit value from the bank register to the controller output port. The 8-bit Controller write strobe signal is connected to the Cryptographic Unit start input. To finish, a HALT instruction is used to put the controller in sleep mode until the end of the execution step. Because all the Cryptographic Unit instructions, except FAES and FGFM, have a fixed execution time, a HALT instruction may be replaced by two NOP instructions. In this case, the controller does not wait for the predictable done signal and one clock cycle can be saved.

B. Implementation of Block Cipher Modes of Operation

Cryptographic tasks attribution is made in the following way. Firstly, the Task Scheduler selects the cores which will execute the task and generates the needed round keys, then it sends channel and packet parameters to the core (including the algorithm ID, the authenticated only field size, the plaintext field size and the tag length for authenticated channel), finally the Task Scheduler sends a start signal to the cores.

Once an ENCRYPT/DECRYPT instruction has been taken into account, the communication controller sends data into the cores input fifos. Data must be sent in a specific way to be correctly interpreted by the cores. At first, algorithm IV must be filed into the FIFO, then packet data must be filed. To finish, communication controller must append a message authentication tag. Cryptographic Unit only embeds basic operators in addition to AES and GHASH cores, therefore it cannot be used to format the plain text according to the specifications of block cipher modes of operation. In consequence, the communication controller must format data prior to send them to the cryptographic cores.

FIFO buffers can store up to 128 plaintext blocks, so cryptographic algorithm main loops are critical parts of their implementations. Listing 1 shows an example of a piece of code used by cryptographic cores to compute the GCM algorithm main loop. This listing shows how instructions are placed between SAES and SGFM instruction in order to save clock cycles. In this example, OR instructions are used as NOP instructions. To finish, algorithm performances and other results are detailed in the following section. At lowest level, overall throughput is limited by AES core computation time which depends on AES key size. But, at higher level, throughput is limited by the main loops of block cipher modes. The computation time of these loops may be used to calculate a theoretical maximum throughput for each algorithm. Loop computation times, in cycles, for 128-bit AES-GCM and AES-CCM are equal to:

T GCM loop = T CT R = T SAES + T F AES = 49 T CCM loop 2cores = T CBC = T SAES + T F AES + T XOR = 55 T CCM loop 1core = T CT R + T CBC = 104
Height cycles must be added to these values for 192-bit keys and height more cycles must be added for 256-bit keys. Then, pre and post loop computations must be taken into account in order to obtain a realistic throughput. It is noticeable that actual throughput depends on packet size, higher throughputs are obtained from larger packets. Table II summarizes these results. For each table II column, the first number denotes the theoretical throughput calculated from loops computation time, while the second number corresponds to the processing time of a 2 KB packet.

Table II shows that AES-CCM 4 × 1 cores (4 packets on 4 different cores) provides better throughput than AES-CCM 2 × 2 cores (2 packets on 4 cores). This means that packet processing on one core is more efficient than packet processing on two cores. However, latency of the first solution is almost two times greater than latency of the second solution. As a consequence, designers should make scheduling choices according to system needs in terms of latency and/or throughput.

Table III compares architecture performances (i.e. functionalities, area, and throughput) of literature approaches to the proposed one. This table shows that our architecture provides better performances, at the same frequency, than other programmable architectures, while it is still competitive when it is compared to non programmable architectures. In consequence, MCCP architecture seems to provide a good trade-off between flexibility and throughput. The next section presents some preliminary results about MCCP partial reconfiguration.

B. MCCP Partial Re-configuration Preliminary Results

Even if design methodology is not yet mature, most of newest FPGA (Xilinx and Altera) are partially reconfigurable. MCCP flexibility can be further improved through partial reconfiguration of the Cryptographic Unit. At the time of writing this paper, we implemented partial reconfiguration on a Xilinx Virtex 4 FPGA. Implemented cryptographic algorithms are the AES encryption algorithm and the Whirlpool hashing algorithm. The reconfigurable area embeds 1280 slices and 16 BRAM. Table IV Reconfiguration time results show that caching of bitstream is needed to obtain the best performances. In addition, magnitude of the reconfiguration times does not allow to consider real-time partial reconfiguration. However, partial reconfiguration may be used for occasional reconfigurations. For example, in a first time, a key exchange algorithm may be loaded into the Cryptographic Unit then, in a second time, a data encryption algorithm may be loaded. In addition, the reconfiguration of one part of the FPGA does not prevent others parts to work. This is valuable in the case of on-line hardware updates for example.

VIII. DISCUSSION

Like with classical MPSoC, to allow maximum throughput, incoming data streams have to be assigned to idle Cryptographic Cores. Similarly, Cryptographic Cores have to be released after a stream has ended. The assignment procedure has also to cover loading of the correct Cryptographic Core program and Cryptographic Unit configuration. Besides simple assignment of streams to idle Cryptographic Cores, it must also be possible to priorize certain streams over others to allow some sort of quality-of-service. Nevertheless, system security has to be continually enforced. As a consequence, significant works have to be done to develop secure operating system able to manage stream assignment and MCCP reconfiguration.

IX. CONCLUSION AND FUTURE WORKS

This work shows that the multi-core architecture presented in this paper provides a good trade-off between flexibility and throughput. Flexibility and performances are obtained by using a hybrid design where low level cryptographic primitives are implemented in hardware while high level block cipher modes are implemented in software. Its 1.7 Gbps throughput makes it particularly suitable for medium rate multi-channel communication systems. Proposed MCCP supports CTR, CBC-MAC, CCM and GCM block cipher modes which are commonly used in communication systems. AES core may be easily replaced by any other 128-bit block cipher (such as Twofish) according to the user needs. It is noticeable that partial reconfiguration, may be used to do this task.

In future works, task scheduling will be improved and partial reconfiguration will be fully implemented to obtain a highly flexible and efficient architecture.

Fig. 1 .

 1 Fig. 1. The MCCP Architecture

Fig. 2 .

 2 Fig. 2. Cryptographic Core Architecture

Fig. 3 .

 3 Fig. 3. The Cryptographic Unit Architecture

3 )

 3 Processing core sends an Ack signal which validates that Start signal has been taken into account by resetting the S register. 4) Processing cores rd and/or wr signals go high while data are processed. A high level on rd or wr signals automatically increments the 2-bit counter in order to sequentially reach each 32-bit sub-word of a Bank Register word. The accessed words are selected by the two address fields of the instruction register. 5) Once computations are finished a done signal is sent bythe processing core to the 8-bit Controller. Some instructions have a more complex behaviour, the following part deals with the Cryptographic Unit instructions and their particularities.

  details the measured preliminary results.

	Core	AES Encryption (with KS)	Whirlpool
	Slices (BRAM)	351 (4)	1153 (4)
	Bitstream Size (kB)	89	97
	Reconfiguration Time (from compact flash) (ms)	380	416
	Reconfiguration Time (from RAM) (ms)	63	69
	TABLE IV
	PARTIAL RECONFIGURATION RESULTS

ACKNOWLEDGEMENT

This work is in part supported by the French DGA (General Armaments Directorate) and by the University of Bordeaux. The views expressed in this paper are those of the authors and cannot be regarded as stating an official position of the DGA or the French DoD.


Julien Bénabès
email: julien.benabes@irccyn.ec-nantes.fr

Fouad Bennis
email: fouad.bennis@irccyn.ec-nantes.fr

Emilie Poirson
email: emilie.poirson@irccyn.ec-nantes.fr

Yannick Ravaut
email: yannick.ravaut@fr.thalesgroup.com

Virtual Concept_P33 -1-Copyright of IDMME -Virtual Concept A NEW APPROACH FOR SPECIFYING AND SOLVING LAYOUT PROBLEMS

Keywords: design optimization, layout problems, user interaction. 1-Introduction

Component and facility layout plays an important role in the design and usability of many engineering products and systems as mechanical design, process plan, management and architecture including ship compartment layout. Generally, layout problems are formulated and solved on a case by case basis and, as far as we know, there is no general method to specify the similarities and characteristics of each problem. Then, this paper proposes an innovative generic approach in order to describe, formulate and solve layout problems. This approach suggests in particular a new classification of layout components, introducing the concept of "virtual" component. Moreover, in order to propose to the designer an optimal spatial arrangement in a reasonable time, this paper presents an interactive optimization strategy for solving layout problems.

Firstly, the problem description defines the dimension of the layout problem (one, two or three dimensions) and identifies the layout components, meaning the container and the components that have to be placed into the container. Secondly, this description and all the expert's requirements have to be translated into design variables, constraints and objectives in order to change the layout problem into an optimization problem. Then, during the optimization process, the solving strategy continuously interacts with the formulation problem in order to compute the design constraints and the objectives. The optimization strategy can also include an interactive tool which allows the designer to interact with the process. Moreover, in order to visualize and modify the solutions, layout components are modelled according to the problem dimension. This paper describes these three parts which make up a layout problem. Sections 2 and 3 are respectively dedicated to the description and the formulation of layout problems. Section 3 also provides a definition of the complexity of layout problems. The optimization strategies are described in section 5. Section 6 concludes this paper.

Moreover, in order to illustrate the concepts developed in this paper, a real-world layout problem is solved. This problem deals with the optimal spatial arrangement of facilities inside a shelter. Several components have to be located in the shelter, including electrical and energetic cabinets, desks and electrical boxes. The CAD model of the shelter is presented in the figure 2.

2-Layout problem description

The layout problem description is the first step of the global layout solving process. This step is usually defined by the engineering experts who well know the global performances of the product or the system. The layout problem description includes the description of the container, the components and the expert's requirements. This section describes in particular the method used to describe layout components.

-Layout components attributes

This subsection defines some attributes used to classify layout components.

-"Material" and "Virtual" components

In layout problems, one finds at least one container and multiple components which have to be placed into the container. In some specific real-word layout problems, as the pallet loading problem, there can be more than one container. Layout components can be very different according to their shape, their size and their functional properties. For example, let us focus on the application studied in this paper. Let us consider that this problem can be conceptualized in two dimensions, because the cabinets are the full height of the shelter and prevent a superposition of elements. Its description is represented in the figure 3. The cabinet 1 and the space in front of it (considering as the space of accessibility of the cabinet), represented by a dotted rectangle in the previous figure, are two components of this layout problem but can not be considered with the same way because of their different properties. In fact, these two components can be separated in "material" and "virtual" components, defined as:

the material component: it has a mass and it can not overlap with an other material component. Layout components are generally considered as material components in layout literature [GF1,SC1], -the virtual component: it has no mass and can overlap with some material or virtual components, according to the designer's requirements. The passages, described in the layout problem presented in [START_REF] Han | An improved genetic algorithm for facility layout problems having inner structure walls and passages[END_REF], can be considered as virtual components.

The example of the cabinet 1 shows that virtual components can be used to describe the space of accessibility of a material component, especially in the facility layout problems. In fact, the space of accessibility of a cabinet is defined as the required space to insert some materials into the cabinet.

As far as we know, the concepts of material and virtual components have not yet been used in layout design literature. However, they can have a significant impact on the description and the formulation of layout problems. For example, in the layout problem of the shelter, two material components can not overlap, whereas two virtual components (two spaces of accessibility) can overlap, considering that operations of materials loading are not simultaneous made.

-Components with variable shape and variable configuration

The previous section shows that components can be Copyright IDMME -Virtual Concept classified in two categories. Moreover, the layout problem of the shelter suggests that components can be sub-classified according to the following definitions:

component with variable shape: the global shape and especially the dimensions of the component can change during the layout optimization process. In general, the dimensions of the component with variable shape are considered as design variables in the optimization problem, -component with variable configuration: the configuration of the component changes during the optimization process but it's not optimized. In the layout problem of the shelter, the desk 1 is a component with variable configuration because it can fall back. Then, we consider that it can overlap with the space of accessibility of the cabinet 1, -invariable component: the global shape and the configuration of the component do not change during the layout optimization process. For example, the cabinets are invariable components.

-Layout components typology

As far as we know, there is no general typology of layout components. However, the layout components attributes, described previously, allow us to generate a general typology of these components. This typology is composed of six categories of layout components. For each category, an example is added according to the application studied in this paper:

- Actually, this new classification of layout components can be used in order to propose a new typology of layout problems.

3-Layout problem formulation

The formulation of layout problems can use single or multiobjective optimization. The designer can make an early decision by using an aggregation function in order to transform a multi-objective problem into a single one. This approach is only effective when all data and information on the aggregation are available or if the designer is familiar with the specific layout problem. In this paper, we use multi-objective optimization. The decision on the preferences between objective functions is delayed so that the designer can use the Pareto-front in order to select the most appropriate solution.

After providing some information about multi-objective optimization, this section describes the method which allows the designer to formulate a multi-objective optimization problem. The complexity of layout problems is also explained in this section.

3.1 -The layout problem: a multi-objective optimization problem

The general formulation of a multi-objective problem can be written as follow:

⎪ ⎩ ⎪ ⎨ ⎧ ≤ = = = = nd : s.t argmin argmin variables design the find a 0 ) ( 0 ) ( )) ( ),..., ( ), ( ( ) ( ) ,..., , ( : 2 1 2 1 x x x x x x x x * * h g f f f F x x x P porblem m n (1)
where m is the number of objective functions and n the number of design variables.

In this approach, the designer has to simultaneously optimize two or more conflicting objectives subject to constraints. In fact, the expert has to compare two solutions represented by two vectors of objectives

) ,..., , ( 2 1 mU U U U f f f F = and ) ,..., , ( 2 1 mV V V V f f f F =
where iU F is the i th component of the vector of objectives F for the design variable U . We consider that U dominates V (Pareto dominance) if U is as good as V for all the objectives and U is better than V for at least one objective. Mathematically, this can be formulated by:

⎪ ⎩ ⎪ ⎨ ⎧ < ∈ ∃ ≤ ∈ ∀ jV jU iV iU f f n j f f n i ] ,..., 1 [ ] ,..., 1 [ (2)
Multi-objective optimization searches for the set of nondominated points (assimilated to Pareto-optimal points in the next sections of this paper) in the objective space given by efficient solutions. The figure 4 represents the Pareto front for an optimization problem defined by two objectives (min f1, min f2), where U dominates V . The equation 1 shows that, in order to formulate an optimization problem, the designer needs three elements: the optimization variables, the design constraints and the objectives.

The design variables

Design variables are the parameters which can be modified by the designer in order to perform the global performances of the product or system. Their value will be fixed at the end of the optimization process. In most of real-world layout problems, the design variables are the variables which locate the components. For example, in the application studied in this paper, each component is defined by three optimization variables ) , , ( α Y X : X and Y are continued variables that represent the coordinates of the center of gravity of a component and α is a discrete variable that defines the rotation angle along the Z axis.

Actually, the number of design variables per component defines the degree of freedom of the component. Some variables can be fixed in order to reduce the number of optimization variables. The opportunities of finding solutions in a reasonable time are then maximized. Besides, in some applications, the designer includes the dimensions of some components in optimization variables. These components are defined in section 2.1.2 as components with variable shape.

The design constraints and the objectives

Firstly, it is important to mention that constraints and the objectives can be exchanged according to designer's requirements. Then, in the next subsection, the word "objective" can be used instead of "constraint".

Two categories of design constraints are mainly considered: the geometric and functional constraints. In layout problems, the geometric constraints allow the detection of interference between two components. In fact, overlap between components has to be minimized in order to drive the current design into a feasible region. Since this collision detection is performed at each iteration of the solving algorithm, it is important to choose the appropriate geometric representation of the components and the efficient algorithm in order to reduce the calculation time. One can find in [START_REF] Lin | Collision detection between geometric models: A survey[END_REF], a general survey of the main detection collision methods.

In the layout problem of the shelter, four non-overlap constraints are defined in order to detect the interferences between components:

-non-overlap constraint between material components (C1), -non-overlap constraint between material and virtual components (C2), -non-overlap constraint between components and the exterior of the shelter (C3), -non-overlap constraint between cabinets and the space below the air-conditioner (represented by a hatched rectangle in the figure 3) (C4).

Actually, if the design constraints and objectives of a layout problem are only geometric constraints, the application is generally compared to cutting and packing problems (C&P) [START_REF] Dyckhoff | A typology of cutting and packing problems[END_REF][START_REF] Wascher | An improved typology of cutting and packing problems[END_REF].

On the other hand, one can define functional constraints which formulate the different expert's requirements and guarantee the functioning of the product or the system. Functional constraints are multiple in a layout problem: mass distribution, minimum or maximum distance between components, alignment of components, accessibility... In the layout problem of the shelter, three objectives are specified:

-one objective to balance the masses inside the shelter (by minimizing the distance between the center of gravity of the components and the geometric center of the shelter), -one objective to maximize the distance between the energetic and electrical networks (by maximizing the distance between the cabinets 2 and 3, the box 2 and the cabinet 1), -one objective to minimize the distance between the box 2 and one of the walls of the shelter, in order to establish a connection with exterior.

-The layout problem: a complex problem

Because of the great complexity of most real-world layout problems, the decision of an acceptable layout is a hard and critical task. In fact, the search of a "feasible" design, it means a design which respects all the design constraints, is time consuming because layout optimization problems are usually non-linear and NP-hard problems. It means that the problem is intrinsically harder than those which can be solved by a nondeterministic Turing machine in polynomial time. However, the concept of complexity of layout problems is a vague notion and, as far as we know, one can not find a general definition of the complexity (hardness) of layout design. Then, according to the description and the formulation of problems, this subsection defines this concept of complexity, by dividing it in three categories:

the complexity linked to the geometry of components: because of the irregular shape of some layout components, the interference calculation between two elements is time consuming. This complexity is a computational complexity, -the complexity linked to the layout problem density: the problem density is the ratio between the space occupied by the components and the total volume of the container. The bigger the problem density, the more difficult the search of a "feasible" design. If we only consider the material components in the layout problem of the shelter, the layout problem density is equal to 51,3%. It is more difficult to estimate the real density of this problem by also considering the virtual components.

the complexity linked to the problem formulation:

actually, more numerous the constraints and objectives, more complex the search of a feasible design, because of the parcelling of the design space. In order to pass to a feasible region to an other one, the designer can not use traditional gradient-based optimization approaches. He has to use stochastic algorithms as genetic algorithms. The calculation time then increases because

Virtual Concept_P33

-5-

Copyright IDMME -Virtual Concept
the problem is more complex. This formulation complexity is illustrated in figure 5 with a simple layout problem.

The layout problem, represented in the figure 5, consists of searching the optimal location of the component 2 in the black rectangular container whose dimensions are defined by H along Y and L along X . Let us consider a fixed component 1 located in the center of the container. The coordinates of the center of gravity of the component i is defined as ) , ( Each problem described in the figure 5 has a non-overlap constraint between the two components and only one objective: maximize the distance between the component 2 and the bottom left corner of the container. Actually, the problem 3 is more complex than the problem 2 which is more complex than the problem 1 because: -Problem 1: no functional constraint is defined. The design space (region of feasible solutions) is defined as only one region represented in blue hatched area. -Problem 2: one functional constraint is added

( D y y x x d ≥ - + - = 2 2 1 2 2 1 12 ) ( ) (
). The design space is then divided in two parts.

-Problem 3: one other functional constraint is added (

h y y ≥ -2 1
). Each feasible region of the problem 2 is divided in two parts. The design space is then composed of 4 regions, so that the search of the optimal solutions is more complex. This example is a simple layout problem with only one container and two components. However the layout problems can be very complex when the number of components and design requirements increases.

4-Optimization strategies for solving layout problems

This section presents a survey of the main approaches used for solving layout problems and proposes in particular an interactive generic strategy based on the genetic algorithm.

-A survey of solving approaches

One finds multiple search algorithms to solve layout optimization problems in two or three dimensions. Traditional optimization approaches for three dimensional layout problems are described by Cagan et al. [START_REF] Cagan | A survey of computational approaches to the three-dimensional layout problems[END_REF]. They use genetic algorithms [START_REF] Yi | Vehicle configuration design with a packing genetic algorithm[END_REF], simulated-annealing algorithms [START_REF] Szykman | Constrained threedimensional component layout using simulated annealing[END_REF] or extended pattern search algorithms [START_REF] Su | An extended pattern search algorithm for three-dimensional component layout[END_REF]. Most search algorithms are developed for a specific problem and they provide an effective optimization strategy for it. Therefore, they are not generic and can not be adapted to a lot of layout problems.

However, one can find other techniques which are more generic. For example, let us focus on the method described by Jacquenot et al. in [START_REF] Jacquenot | 2d multi-objective placement algorithm for free-form components[END_REF]. The design strategy uses a Genetic Algorithm coupled with a Separation Algorithm. The structure of the algorithm is very closed to a generational genetic algorithm. The separation algorithm is nested in the genetic algorithm, and modifies the component positions so that the solution proposed respect placement constraints. Actually, before evaluating a solution, the algorithm checks if placement constraints are satisfied. If so, the different objectives of the solution are evaluated and the algorithm moves to the next solution. Otherwise, the separation algorithm is run and modifies the solution so that placement constraints are respected. The solution is then evaluated.

Applications of the proposed method can be found in engineering domains, where placement problems have no particular specificity and can not be treated with classical methods.

-User interaction in layout design

In general, the development of an engineering object is considered as a single process involving multi-criteria identification of the mathematical model followed by multicriteria optimization of the object design on the basis of this mathematical model. The process of statement-solution of engineering design problems without the interference of the design is impossible. For solving the design problem, the designer almost always has to correct either the mathematical model, the dimension of the vectors of design variables and criteria, the design variable ranges, and so on. The direct participation of the designer in the construction of the feasible design and non-formal analysis are the essential stage of the search for the optimal design. This paper presents an innovative interactive strategy for solving layout problems. The strategy, based on the generic method developed by Jacquenot et al. [START_REF] Jacquenot | 2d multi-objective placement algorithm for free-form components[END_REF], uses steps,

Copyright IDMME -Virtual Concept whose two interactive stages:

-the first step consists of randomly initializing some designs and then optimizing it by the separation algorithm, considering only the geometrical non-overlap of components, -in the second step, the designer interacts with the population generated by the separation algorithm by locally selecting and modifying some solution according to his personal judgment. The two first steps consists of generating a customized initial population for the genetic algorithm, -the third step consists of generating, by the genetic algorithm, a set of non-dominated solutions. The algorithm is stopped after a fixed number of iterations.

The genetic algorithm used in this paper is described by Deb et al. [START_REF] Deb | Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization[END_REF]. -In the last step, the designer visualizes and locally modifies some solutions by using an interactive numerical environment. Then, the designer can improve the global performances of the solutions and take into account his personal judgment in order to make a final decision.

The figure 6 represents the four steps of this interactive optimization strategy. Two illustrations of the separation process and the second user interaction process are added in the figure 6.

Moreover, other user interaction steps could be directly inserted in the multi-objective optimizer, according the designer requirements:

-qualitative fitness or user perceptions could be inserted into design process [START_REF] Poirson | Integration of user-perceptions in the design process: application to musical instrument optimisation[END_REF]. In some layout problems, all constraints and objectives can not be easily formulated as simple mathematical expressions. It means that these constraints and objectives could be replaced by subjective criteria, defined by the designer in order to characterize the design. For example, this qualitative fitness could be represented by a mark and considered by the algorithm as a design objective. Brintrup This subsection presents the results, obtained by the interactive optimization process described in the previous subsection, for the layout problem of the shelter. Firstly, the separation algorithm has been randomly initialized with 500 designs that didn't respect non-overlap constraints. Then, these designs have been optimized by the separation algorithm. By interacting directly with them and by relaxing the design constraints (until 150 cm 2 ), the

Copyright IDMME -Virtual Concept designer has selected 78 different optimized designs. This population then has been completed with 162 individuals randomly generated in order to create the first population of the genetic algorithm (240 individuals) and to guarantee the diversity of individuals.

Then, the Multi-Objective Genetic Algorithm has searched optimal solutions by considering the design constraints and all the objectives of the problem. Then, after one hundred of generations, a set of 14 feasible (meaning that respect the design constraints) variants have been computed.

In fact, design j is a new variant if it differs from the design i by at least one of the following criteria:

-one of the components of the layout has been displaced from at least Δ mm along one of the axis X and Y (Δ is fixed to 500mm in this simulation), -one of the components has been rotated, -the minimum difference between the objective values of the two designs is bigger than a limit, fixed to 10 cm.

The numerical values, used to specify these three criteria, are subjective data. Then, these data have to be defined by the designer, who is the only person who is able to differentiate two solutions.

Among the 14 variants, 7 are Pareto-optimal designs but did not dominate the initial solution created by the expert engineers. This initial solution is an intuitive solution which has been generated only by considering geometric aspects. The initial solution neither dominates the designs computed by the algorithm.

Consequently, it means that the designer is the only person who can make the final design choices. In order to make a decision, the optimization strategy described in this paper proposes to use an interactive graphical and numerical environment. The main objective of this interactivity with the designer is to improve the global performances of the optimal solutions generated by the algorithm, by inserting, in the decision making, the personal judgment of the designer. Actually, the designer explores these 7 nondominated variants, compares their objective values and selects one solution. Then, he interacts with this solution. By locally changing the location of some components of the shelter, as it is shown in the second illustration of the figure 6, the designer improves the global performances of the design. In fact, the solution modified by the designer is better than the initial solution, according to the formulated objectives.

5-Conclusion

The paper proposes an innovative approach to help the designer to describe, formulate and solve a layout optimization problem. It includes a new classification of layout components by introducing the concept of material and virtual components. Moreover, this paper proposes an interactive generic strategy for solving layout problems and emphasizes the fact that user interaction is an important step of the global layout optimization problem.

6-Acknowledgment

Figure 1 :

 1 Figure 1: schematic representation of a layout problem.

Figure 2 :

 2 Figure 2: overall view of the shelter.

Figure 3 :

 3 Figure 3: description of the shelter in 2D.

  the Invariable Material Components (IMC): the cabinets, the electrical boxes and the desk 2, -the Material Components with Variable Shape (MCVS): there are no MCVS in the layout problem of the shelter. However, if the dimensions of the cabinets were not fixed, the cabinets would be considered as MCVS): the desk 1, -the Invariable Virtual Components (IVC): the spaces of accessibility of the cabinets, -the Virtual Components with Variable Shape (VCVS): there are no VCVS in the layout problem of the shelter. In the architectural layout problem described in [MC2], the dimensions of each room are optimized. Then, the rooms are considered as VCVS, -the Virtual Component with Variable Configuration (VCVC): the space of accessibility of the desk 1.

Figure 4 :

 4 Figure 4: Pareto front of a multi-objective problem.

Figure 5 :

 5 Figure 5: example of formulation complexity.

Figure 6 :

 6 Figure 6: Interactive solving strategy for layout problems.

  et al. have already developed an interactive genetic algorithm based framework for handling qualitative criteria in design optimization [BR1], -the designer could interact with design variables during the optimization process. Stopping the optimizer would allow the designer to firstly analyze a specific solution, secondly locally modify the design configuration and then decide to keep this modified design in the next generation of the genetic algorithm. We can find in [MP1] a significant contribution to this concept applied to the design optimization of architectural layouts. 4.3 -Results obtained for the layout problem of the shelter

The authors would like to acknowledge Thales Communications for the application study.