An efficient implementation of advanced encryption standard on the coarse-grained reconfigurable architecture
VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
An Efficient Implementation of Advanced Encryption
Standard on the Coarse-grained Reconfigurable Architecture
Hung K. Nguyen*, Xuan-Tu Tran
SIS Laboratory, VNU University of Engineering and Technology,
144 Xuan Thuy road, Cau Giay district, Hanoi, Vietnam
Abstract
The Advanced Encryption Standard (AES) is currently considered as one of the best symmetric-key block
ciphers. The hardware implementation of the AES for hand-held mobile devices or wireless sensor network
nodes is always required to meet the strict constraints in terms of performance, power and cost. Coarse-grained
reconfigurable architectures are recently proposed as the solution that provides high flexibility, high performance
and low power consumption for the next-generation embedded systems. This paper presents a flexible, high-
performance implementation of the AES algorithm on a coarse-grained reconfigurable architecture, called
MUSRA (Multimedia Specific Reconfigurable Architecture). First, we propose a hardware-software partitioning
method for mapping the AES algorithm onto the MUSRA. Second, the parallel and pipelining techniques are
considered thoughtfully to increase total computing throughput by efficiently utilizing the computing resources
of the MUSRA. Some optimizations at both loop transformation level and scheduling level are performed in
order to make better use of instruction-, loop- and task- level parallelism. The proposed implementation has been
evaluated by the cycle-accurate simulator of the MUSRA. Experimental results show that the MUSRA can be
reconfigured to support both encryption and decryption with all key lengths specified in the AES standard. The
performance of the AES algorithm on the MUSRA is better than that of the ADRES reconfigurable processor,
Xilinx Virtex-II, and the TI C64+ DSP.
Received 24 November 2015, revised 06 January 2015, accepted 13 January 2016
Keywords: Coarse-grained Reconfigurable Architecture (CGRA), Advanced Encryption Standard (AES), Reconfigurable
Computing, Parallel Processing.
1. Introduction*
network. The Advanced Encryption Standard
(AES), which has been standardized by the
National Institute of Standard and Technology
best symmetric-key block ciphers. With the
block size of 128 bits and the variable key
length of 128 bits, 192 bits or 256 bits, the AES
has been proved to be a robust cryptographic
algorithm against illegal access.
The hardware implementation of the AES
for modern embedded systems such as hand-
held mobile devices or wireless sensor network
(WSN) nodes always gives designers some
challenges such as reducing chip area and
The fast development of the communication
technology enables the information to be easily
shared globally via the internet, especially with
the Internet of Things (IoT). However, it also
raises the requirement about the secure of the
information, especially the sensitive data such
as password, bank account, personal
information, etc. One method to protect the
sensitive data is using symmetric-key block
cipher before and after sending it over the
________
* Corresponding author. E-mail.: [email protected]
10
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
11
power consumption, increasing application
performance, shortening time-to-market, and
simplifying the updating process. Besides, these
systems are often designed not only for a
specific application but also for multiple
applications. Such sharing of resources by
several applications makes the system cheaper
and more versatile. Application Specific
Integrated Circuits (ASICs), Digital Signal
Processors (DSPs), and Application-Specific
Instruction Set Processors (ASIPs), have been
used for implementing the mobile multimedia
systems. However, none of them meets all of
implementation of the AES algorithm by using
and usually targets at the applications at where
flexibility has a higher priority than the
implementation efficiency in terms of power
consumption, area, and performance. In contrast,
the ASIC implementation of the AES algorithm
performance and power consumption. However,
the drawback of ASIC is lower flexibility.
Moreover, the high price for designing and
manufacturing the chip masks is becoming
increasingly an important factor that limits the
application scope of ASIC. Recently, a very
promising solution is the reconfigurable
computing systems (e.g. Zynq-7000 [5],
heterogeneous processing resources such as
software programmable microprocessors (P),
hardwired IP (Intellectual Property) cores,
reconfigurable hardware architectures, etc. as
target application is first represented
intermediately as a series of tasks that depends
on each other by a Control and Data Flow
mapped onto the heterogeneous computational
and routing resources of the system. Especially,
computation-intensive kernel functions of the
application are mapped onto the reconfigurable
hardware so that they can achieve high
performance approximately equivalent to that
of ASIC while maintaining a degree of
flexibility close to that of DSP processors. By
hardware tasks to be mapped onto the same
hardware platform, thus reducing the area and
power consumption of the design [8].
Instruction
Memory
Data Memory
P
AMBA AHB
AHB/CGRA Interface
IP cores
DPLL
CGRA
Figure 1. System-level application model of CGRA.
The reconfigurable hardware is generally
classified into the Field Programmable Gate
Array (FPGA) and coarse-grained dynamically
reconfigurable architecture (CGRA). A typical
example of the FPGA-based reconfigurable
FPGAs support the fine-grained reconfigurable
fabric that can operate and be configured at bit-
level. FPGAs are extremely flexible due to their
higher reconfigurable capability. However, the
FPGAs consume more power and have more
delay and area overhead due to greater quantity
limits the capability to apply FPGA to mobile
devices. To overcome the limitation of the
FPGA-like fine-grained reconfigurable devices,
we developed and modeled a coarse-grained
dynamically reconfigurable architecture, called
MUSRA (Multimedia Specific Reconfigurable
performance, flexible platform for a domain of
applications in multimedia processing. In
contrast with FPGAs, the MUSRA aims at
reconfiguring and manipulating on the data at
word-level. The MUSRA was proposed to
exploit high data-level parallelism (DLP),
instruction-level parallelism (ILP) and TLP
(Task Level Parallelism) of the computation-
intensive loops of an application. The MUSRA
also supports the capability of dynamic
dynamically
reconfiguring
hardware,
reconfigurable computing systems allow many
12
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
reconfiguration by enabling the hardware
fabrics to be reconfigured into different
functions even if the system is working.
The MUSRA is composed of
a
Reconfigurable Computing Array (RCAs),
Input/Output FIFOs, Global Register File
(GRF), Data/Context memory subsystems, and
DMA (Direct Memory Access) controllers, etc.
(Figure 2). Data/Context memory subsystems
consist of storage blocks and DMA controllers
(i.e. CDMAC and DDMAC). The RCA is an
array of 88 RCs (Reconfigurable Cells) that
can be configured partially to implement
computation-intensive tasks. The input and
output FIFOs are the I/O buffers between the
data memory and the RCA. Each RC can get
the input data from the input FIFO or/and GRF,
and store the results back to the output FIFO.
These FIFOs are all 512-bit in width and 8-row
in depth, and can load/store sixty-four bytes or
thirty-two 16-bit words per cycle. Especially,
the input FIFO can broadcast data to every RC
that has been configured to receive the data
from the input FIFO. This mechanism aims at
exploiting the reusable data between several
iterations. The interconnection between two
neighboring rows of RCs is implemented by a
crossbar switch. Through the crossbar switch,
an RC can get results that come from an
arbitrary RC in the above row of it. The Parser
decodes the configuration information that has
been read from the Context Memory, and then
generates the control signals that ensure the
execution of RCA accurately and automatically.
RCA. Each RC includes a data-path that can
execute signed/unsigned fixed-point 8/16-bit
operations with two/three source operands, such
as arithmetic and logical operations, multiplier,
and multimedia application-specific operations
(e.g. barrel shift, shift and round, absolute
differences, etc.). Each RC also includes a local
register called LOR. This register can be used
either to adjust operating cycles of the pipeline
or to store coefficients when a loop is mapped
onto the RCA. A set of configuration registers,
which stores configuration information for the
RC, is called a layer. Each RC contains two
layers that can operate in the ping-pong fashion
to reduce the configuration time.
In this paper, we proposed a solution for
implementing the AES algorithm on the
platform of the MUSRA-based system. The
AES algorithm is firstly analyzed and optimized,
and then HW/SW (Hardware/Software)
partitioned and scheduled to be executed on the
MUSRA-based system. The experimental
results show that our proposal achieves the
throughput of 29.71 instructions per cycle in
average. Our implementation has been
compared to the similar works on ADRES
implementation is about 6.9 times, 2.2 times,
and 1.6 times better than that of TI C64+ DSP,
Xilinx Virtex-II, and ADRES, respectively.
The rest of the paper is organized as follows.
The MUSRA architecture and the AES
algorithm are presented in Section 2 and
Section 3, respectively. Section 4 presents the
mapping the AES algorithm onto the MUSRA-
based system. In Section 5, simulation results
and the evaluation of the AES algorithm on the
MUSRA-based system in terms of flexibility
and performance are reported and discussed.
Finally, conclusions are given in Section 6.
2. MUSRAArchitecture
2.1. Architecture Overview
AHB/CGRA Interface
DDMAC
Input DMA
IN_FIFO
GRF
Crossbar Switch
RC
00
RC
01
RC
07
CDMAC
Crossbar Switch
Context
Memory
Context
Parser
Data
Memory
RC
10
RC
11
RC
17
Crossbar Switch
RC
70
RC
71
RC
77
RCA
IN_FIFO
Output DMA
Figure 2. MUSRA architecture.
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
13
configuration of the MUSRA can take place
behind the execution of the RCA. As a result,
once the RCA finishes calculating with the
current context, it can be immediately changed
into the next context.
CLK
MUX
A_IN
MUX
B_IN
MUX
RESETN
Config. Data
Config.
C
REGs
B
A
LOR_input
ENABLE
R
Config._Addr
Config._ENB
Layer
C
0
DATAPATH
LOR
1
LOR_output
2.3. Execution Model
OUT_REG
PE_OUT
PE
LOR_OUT
It is a well-known rule of thumb that 90%
of the execution time of a program is spent by
LOOP constructs are generally identified as
kernel loops. Most of them have computation-
intensive and data-parallel characteristics with
high regularity, so they can be accelerated by
hardware circuits. The MUSRA architecture is
basically the such-loop-oriented one. By
mapping the body of the kernel loop onto the
RCA, the RCA just needs configuring one time
for executing multiple times, therefore it can
improve the efficiency of the application
execution. Executing model of the RCA is the
pipelined multi-instruction-multi-data (MIMD)
model. In this model, each RC can be configured
separately to a certain operation, and each row of
RCs corresponds to a stage of a pipeline. Multiple
iterations of a loop are possible to execute
simultaneously in the pipeline.
Figure 3. RC architecture.
The data processed by RCA are classified
into two types: variables are streamed into the
RCA through the input FIFO meanwhile
constants are fed into the RCA via either GRF
for scalar constants or LOR array for array
constants. The constant type is again classified
into global constants and local constants.
Global constants are determined at compile-
time therefore they are initialized in context
memory of the MUSRA at compile-time and
loaded into GRF/LORs while configuring the
RCA. Local constants (or immediate values) are
not determined at compile-time, but are the
results generated by other tasks at run-time,
therefore, they need to be loaded dynamically
into GRF/LCRs by configuration words.
2.2. Configuration Model
For purpose of mapping, a kernel loop is
first analyzed and loop transformed (e.g. loop
unrolling, loop pipelining, loop blocking, etc.)
in order to expose inherent parallelism and data
locality that are then exploited to maximize the
computation performance on the target
architecture. Next, the body of the loop is
represented by data-flow graphs (DFGs) as
mapped onto RCA by generating configuration
information, which relate to binding nodes to
the RCs and edges to the interconnections.
Finally, these DFGs are scheduled in order to
execute automatically on RCA by generating
the corresponding control parameters for the
CGRA’s controller. Once configured for a
certain loop, RCA operates as the hardware
dedicated for this loop. When all iterations of
loop have completed, this loop is removed from
the RCA, and the other loops are mapped onto
the RCA.
The configuration information for the
MUSRA is organized into the packets called
context. The context specifies a particular
operation of the RCA core (i.e. the operation of
each RC, the interconnection between RCs, the
input source, output location, etc.) as well as the
control parameters that control the operation of
the RCA core. The total length of a context is
128 32-bit words. An application is composed
of one or more contexts that are stored into the
context memory of the MUSRA.
The function of the MUSRA is
reconfigured dynamically in run-time according
to the required hardware tasks. To deal with the
huge
configuration
overhead
in
the
reconfigurable hardware, the proposed design
of the MUSRA supports a mechanism to pre-
load and pre-decode the configuration context
from the context memory to the configuration
layers in the RCA. By this method, the
14
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
x
y
z
InputFIFO
z
x
t
Stage1
Stage2
Stage3
Stage4
Stage4
×
PE
PE
PE
PE
PE
PE
PE
PE
PE
LOR
LOR
LOR
LOR
TD
TD
y
t
NI = 2
Input #1
Input #2
x
y
z
LOAD -
EXECUTION
+
&
-
LOR
Data broadcasted
directly to every RC
CLK1
CLK2
×
+
&
t
LOR
CLK3
EXECUTION
GRF(0)
35
CLK4
CLK5
TD
-
v
v
OUT_FIFO(0)
STORE-
EXECUTION
Output #1
A
0
1
v
PE
A
TD
w
CLK6
w
Output #2
w
OutputFIFO
OUT_FIFO(0)
NO = 2
(a)
(b)
Figure 4. (a) DFG representation of a simple loop body, and (b) its map onto RCA.
The execution of a loop is scheduled so that
can start computing as soon as the data of the
first input appears on the input of the RCA, so
LOAD phase and EXECUTION phase of the
same iteration can happen simultaneously. In
other words, our execution model allows
overlapping three phases LOAD, EXECUTION,
STORE of the same iteration as much as
RCA core in the MUSRA’s model is started by
LOAD-EXECUTION phase, and then is
EXECUTION phase, finally finished by
STORE-EXECUTION phase. On the other hand,
this model also allows the data of the next
iteration be LOADed simultaneously with the
data of the current iteration, so it maximizes not
only the level of overlapping between the
consecutive iterations but also the data reuse [10].
the different phases of successive iterations are
overlapped each other as much as possible.
Scheduling also needs to ensure that there are
not any conflicts between resources as multiple
phases take place simultaneously.
Parallel processing increases not only the
computation performance but also the pressure
on the data bandwidth. The system’s bandwidth
is necessary to ensure that data is always
available for all resources running concurrently
without the IDLE state. One way to increase
data availability is to exploit the data locality
that refers to capability of data reuse within a
locality has the potential to increase the
processing efficiency of the system because the
data can be cached in the internal memory for
reuse later, thus reducing stalled times due to
waiting for external memory accesses.
Moreover, the data reuse also has the potential
to minimize the number of access to external
memory, thus achieves a significant reduction
execution model exploits the overlapping data
between two successive iterations, so it can
enhance the performance and reduce the input
3. Advanced Encryption Standard
The overall structure of the Advanced
Encryption Standard (AES) algorithm, which
includes both encryption and decryption
process, at Electronic Codebook (EBC) mode is
cryptographic block cipher with a block length
of 128-bits, which means that the input data is
divided into 128-bit blocks and encrypted
independently through a sequence of rounds.
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
15
During the cipher process, the 128-bit input
block is arranged into a 4×4 matrix of bytes so
that the first four bytes of a 128-bit input block
are located at the first column in the 4×4 matrix;
the next four bytes are located at the second
column, and so on. At the output of the last
round, the 4×4 matrix of bytes is rearranged
into a 128-bit output block. This 4×4 matrix is
referred to as the state array in the context of
the AES algorithm. The AES standard supports
three types of key length, including 128, 196 or
256 bits. The number of rounds to be executed
in an AES encryption or decryption process is
dependent on the used key length as shown in
Eq.(1). The round keys are derived from the
original key thank to the key expansion unit.
Except for the last round, all rounds are
identical and including four steps as shown in
Figure 6. Notice that the last round (Round n)
does not have “Mix Columns” and “Inverse
Mix Columns” for the encryption and the
decryption, respectively. Also notice that the
sequence at where the steps are performed is
different for the encryption and the decryption.
4. Implementation
Motivated by the demand of higher
throughput and flexibility, as well as low power
consumption for the applications of video
conference, security IP camera, etc. in this
section we are going to describe our
optimization method for improving the
performance of the AES algorithm on the
architecture of the MUSRA-based system. In
the work, we have mapped both the AES
encryption and AES decryption with all options
of key length onto the MUSRA-based system.
However, for simplifying the presentation in
this section, we will focus on the AES
encryption and assume that the key length is
128 bits. We have started with the C-software
implementation of the AES algorithm and then
pay attention on analyzing the source code to
indentify computation-intensive loops of the C-
software. Besides, since no more parallel is
available in the application when processing a
single block, the loop transformation and
source-level transformation are applied to
kernel loops to improve parallelism. Next, the
kernel loops are represented intermediately by
DFGs and mapped onto RCA to increase the
total computing throughput. Finally, we
propose a scheduling scheme to manage the
dynamically reconfigurable operation of the
system. The scheduling scheme also takes
(1)
Key _ Length
n
+ 6
32
Encryption
Decryption
128-bit Plaintext
block
128/192/256-bit
Key
128-bit Plaintext
block
w0 – w3
w0 – w3
w4 – w7
w8 – w11
Add Round Key
Round 1
Round n
w4 – w7
Round (n – 1)
Round (n – 2)
w8 – w11
Round 2
w4n – w4n+3
w4n – w4n+3
Round n
Add Round Key
128-bit Ciphertext
block
128-bit Ciphertext
block
Figure 5. The overall structure of AES algorithm [1].
Inverse Mix Columns
Add Round Key
Substitute Bytes
Shift Rows
Round Key
charge
of
synchronizing
the
data
Inverse Substitute Bytes
Inverse Shift Rows
Mix Columns
Add Round Key
communication between tasks, and managing
the conflict between hardware resources.
Round Key
4.1.Hardware/Software Partition
The structure of the AES encryption
encryption program is represented by two FOR
loops that are denoted as block_loop and
(a) Encryption Round
(b) Decryption Round
Figure 6. The overall structure of a round.
16
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
1
2
3
4
5
6
7
8
9
KeyExpansion();
KeyExpansion();
// processing all blocks of the plain text input file for (block = 1; block =< Nb; block++)
for (block = 1; block =< Nb; block++)
{ // block_loop
AddRoundKey(0);
// first Nr-1 rounds
for (round = 1; round < Nr; ++round)
{// round_loop
{ // Hardware
AddRoundKey(0);
}
// first Nr-1 rounds
for (round = 1; round < Nr; ++round)
{
SubBytes();
for (block = 1; block =< Nb; block++)
10
ShiftRows();
{ // Software
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
MixColumns();
AddRoundKey(round);
}
// The last round
SubBytes();
ShiftRows();
AddRoundKey(Nr);
}
SubBytes();
ShiftRows();
}
for (block = 1; block =< Nb; block++)
{ // Hardware
MixColumns();
AddRoundKey(round);
}
}
// The last round
for (block = 1; block =< Nb; block++)
{// Software
SubBytes();
ShiftRows();
}
for (block = 1; block =< Nb; block++)
{// Hardware
AddRoundKey(Nr);
}
(a) Original Code
(b) Code after Loop transformations
Figure 7. C code for the AES encryption algorithm.
Each sample counts as 0.01 seconds.
%
cumulative self
self
total
time seconds
32.82 29.75
29.72 56.69
26.85 81.03
5.57 86.08
2.06 87.95
1.86 89.64
seconds
29.75
26.94
24.34
5.05
calls
us/call us/call
name
184549365 0.16
150994935 0.18
167772150 0.15
167772150 0.03
16777215
16777215
0.16
0.18
0.15
0.03
0.11
5.23
AddRoundKey
MixColumns
SubBytes
ShiftRows
BlockCopy
Cipher
1.87
1.69
0.11
0.10
0.82
90.38
0.74
main
0.00 90.38
0.00 90.38
0.00
0.00
40
1
0.00
0.00
0.00
0.00
getSBoxValue
KeyExpansion
Figure 8. Profiling result by using GNU profiler.
five functions in this program. Where,
KeyExpansion() implements the function of
Key Expansion unit; SubBytes(), ShiftRows(),
MixColumns(), and AddRoundKey() implement
steps of an encryption round. In order to
indentify which parts of the algorithm are
taking most of the execution time, the AES
encryption program has been profiled by the
result while encrypting an input file of 256MB
(equivalent to 16,777,215 blocks of 4×4 bytes)
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
17
Table 1. Optimizing MixColumns() function
Original Mixcolumns()
Transformed Mixcolumns()
y 0 ,c 2 * x 0 ,c 3 * x1,c x 2 ,c x 3 ,c
y 0 ,c 2 * ( x 0 ,c x1,c ) ( x1,c ( x 2 ,c x3 ,c ))
y1,c x 0 ,c 2 * x1,c 3 * x 2 ,c x3 ,c
y 2 ,c x 0 ,c x1,c 2 * x 2 ,c 3 * x3 ,c
y 3 ,c 3 * x 0 ,c x1,c x 2 ,c 2 * x3 ,c
y1,c 2 * ( x1,c x 2 ,c ) ( x 2 ,c ( x0 ,c x3 ,c ))
y 2 ,c 2 * ( x 2 ,c x3 ,c ) ( x3 ,c ( x0 ,c x1,c ))
y 3 ,c 2 * ( x3 ,c x 0 ,c ) ( x0 ,c ( x1,c x 2 ,c ))
x0
x1
x2
x3
0x07 0x01 0x1B
K0
K1
K2
K3
INPUT FIFO
GRF
31
x1
31
0
0
x0 x1
x2 x0 x2 x3
x3 x0
x2
x3
x1
Stage1
XOR
XOR
XOR
SLL
XOR
PE
PE
PE
PE
XOR
XOR
SLL
LOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
GRF(0)
GRF(0)
GRF(0)
GRF(0)
t0
t1
t2
t3
t0
t1
t2
SRL
t3
Stage2
XOR
XOR
SRL
AND
MUL
XOR
SRL
AND
MUL
XOR
SRL
AND
MUL
XOR
LOR
GRF(1)
LOR
GRF(1)
LOR
LOR
LOR
LOR
LOR
GRF(1)
LOR
GRF(1)
GRF(1)
GRF(1)
GRF(1)
GRF(1)
Stage3
Stage4
SLL
v1
SLL
AND
MUL
XOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
v3
GRF(2)
GRF(2)
GRF(2)
GRF(2)
v3
v0
v2
v0
v1
v2
PE
PE
PE
PE
LOR
LOR
LOR
LOR
LOR
GRF(4)
GRF(3)
GRF(5)
GRF(6)
Stage5
Stage6
XOR
XOR
XOR
XOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
LOR
w3
w0
PE
w1
PE
w2
PE
w3
w0
w1
w2
XOR
XOR
XOR
XOR
PE
LOR
LOR
LOR
LOR
y3
y0
y1
y2
y0
y1
y2
y3
OUTPUT FIFO
31
0
Figure 9. RCA configuration for computing both MixColumns() and AddRoundKey().
functions AddRoundKey(), MixColumns(), and
SubBytes() are the most time-consuming parts
of the program. In order to improve the
performance, these loops are transformed and
the computation-intensive loops must be
mapped onto the reconfigurable hardware for
parallel processing. Firstly, because 128-bit
blocks are encrypted independently, instead of
processing block-by-block we can invert these
loops to process round-by-round so that at each
round all of blocks will be processed before
changed to next round. In other words, while
going into a certain round, all blocks will be
processed instead of only block as in the
original code. As a result, the round_loop
covers the block_loop now. The loops continue
to be transformed and partitioned into some
rearranging, it is possible to reduce about 99%
of the total configuration time due to decrease
context swapping frequency. Finally, HW/SW
partition decides to map AddRoudKey() and
MixColumns() onto the MUSRA. Because the
computation of SubBytes() relates to look-up
table, whereas, ShiftRows() performs matrix
transpose, therefore, it is more efficient to map
these functions onto the a microprocessor.
Mapping AddRoundKey() onto MUSRA is
straightforward because it is simple to XOR
each bytes from the state matrix with a
corresponding round key byte. However, it is
more complex to map Mixcolumn() onto the
MUSRA. Some mathematical transformation
must be implemented so that the computation of
Mixcolumn() is mapped effectively onto the
18
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
optimizing Mixcolumn() function.
as the central processing unit (CPU) that takes
charge of managing and scheduling all activities
of the system. The external memory is used for
communicating data between tasks on the CPU
and tasks on the RCA. Cooperation between
RCA, CPU and DMAs are synchronized by the
interrupt mechanism. When the MUSRA
finishes the assigned task, it generates an
interrupt via IRQC (Interrupt Request
Controller) unit to signal the CPU, and returns
bus control to the CPU. In order to simulate, the
C-software of the AES algorithm is compiled
and loaded into the Instruction Memory of the
simulator. Meanwhile, the plaintext file is
copied into the Data Memory.
Figure 11 shows the timing diagram of
scheduling tasks on the different resources of
the MUSRA-based system. Execution and data-
flow of the MUSRA are reconfigured
dynamically under controlling of the CPU.
AddRoundKey() and the combination of
MixColum() and AddRoundKey() are mapped
onto the RCA and denoted as AddRoundKey() and
tasks including KeyExpansion() (i.e. Key Exp.)
and the combination of SubBytes() and ShiftRows()
(i.e. Sub_Shft()) are assigned to the CPU.
Notice that “ ” is bitwise XOR operation
and “*” symbol is multiplication operation in
GF(28), thereby:
and
3 * x 2 * x x
(2)
2 * x ( x 1) ((( x 7 ) & 0 x 01 ) * 0 x1b )
Figure 9 shows a solution for mapping both
MixColumn() and AddRoundKey() onto the
RCA of MUSRA with only one context. Each
column of the state matrix is fed into the RCA
via the Input FIFO, while constants (in Eq.(2))
and the corresponding round keys are pre-
loaded into the GRF. There are 36 operations
performed concurrently per cycle in a 6-stage
pipeline. As a result, there are seven columns
processed in parallel.
4.2.Scheduling
Instruction
Memory
Data
Memory
IRQC
CPU
AMBA BUS
After resetting, the operation of the system
is briefly described as follows:
AMBA/CGRA Interface
2
3
● Context Memory Initialization (i.e. CM
necessary control parameters and then grant bus
control to CDMAC in Context Memory (i.e.
context from the instruction memory to context
memory. At the same time, CPU executes Key
Exp. function.
1
DDMAC
Input DMA
CDMAC
IN_FIFO
GRF
3
Context
Memory
Context
Parser
Data
Memory
RCA
4
OUT_FIFO
● Context Parser Initialization (i.e. PAR
configuration words to the context parser.
● RCA Configuration and Data Memory
Initialization: After configured, parser reads
one proper context from the context memory,
decode it and configure RCA (i.e. Conf. process
DDMAC that will copy data from the external
data memory to the internal data memory (i.e.
used for writing the result back to the external
data memory.
Output DMA
CGRA
Figure 10. System-level cycle-accurate
simulator for MUSRA.
In this paper, we developed a system-level
cycle-accurate simulator for experimentally
evaluating and validating the implementation of
an application on the MUSRA. The simulator is
based on the LEON3 processor and the other IP
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
19
Processing
Resource
Encryption
CM
Init.
Key
Exp.
PAR DM
Init. Init.
Sub_Shf
(Nr)
R
Boot
Sub_Shf(1) Sub_Shf(2)
Copy to
CM
DMA
PARSER
RCA
Copy data to/from DM
Conf.
Conf.
Conf.
AddRounKey
(Nr)
AddRounKey(0)
Mix_Add(1)
Mix_Add(1)
Time (Cycles)
Figure 11. Timing diagram of scheduling sub-tasks on resources of RPU.
RCA Execution: RCA performs a certain
task (e.g. AddRoundKey(), Mix_Add(),…) right
after it has been configured.
MUSRA architecture. The C-model has been
developed in the Visual Studio IDE.
Tools
HW/SW
Partition
Configuration
Tool
HW
tasks
CONTEXT.txt
5. Experiment and Evaluation
Testbench
Initializing Context Memory
C++ code of application
This section presents the simulating of the
AES algorithm on the MUSRA platform that is
modeled at different abstraction levels. The
performance of the AES algorithm running on
the MUSRA is compared with that of the
DSP from Texas Instruments [3].
IN_DATA.txt
CONSTANT.txt
Initializing Data Memory and
GRF
// User application
main ()
{
//SW code here
Fetching Context and
Configuring RCA, DMAs
}
{
//code of HW task is removed
//extract and generate data for MUSRA
//grant parameter to MUSRA
Run RCA core:
(1) Write data to IN_FIFO
(2) Processing
(3) Write result to OUT_FIFO
}
{
OUT_DATA.txt
Screen
//Read data that are returned by HW
//SW code
Store data from OUT_FIFO
to Memory
}
Print data to file or screen
5.1.Simulation Environment
C-model of MUSRA
FIFO
DMA
RCA core
Context Parser
MUSRA Parameters
API processing file
The environment for developing and
verifying applications on the MUSRA has
been built at the different abstract levels [10].
Figure 12. C-model of MUSRA.
Firstly,
the
C-model
is
used
for
Secondly, a cycle-accurate RTL (Register
Transfer Level) model, which is written in
VHDL language, is used for evaluating the
performance of the algorithm on the proposed
the construction of the testbench model for
verifying the AES algorithm. Besides the RCA
described at RTL, some other function blocks
such as clock generator, address generator,
data memory, and context memory... are
described in the behavioral level. In order to
simulate, it also needs the input data files
includes "in_data.txt", "constant.txt" and
hardware/software partitioning and generating
configuration contexts. C-Model is a software
platform includes a set of C source files (.c, .h)
to define the parameters and the functional
model of the building blocks of MUSRA
(Figure 12). Besides, C-model also offers
several APIs for reading/writing data from/to a
text file (.txt) to initialize or store the contents
of the memory model of the C-model. The
configuration information for the MUSRA is
generated by the configuration Tools. Based on
the C-model, it is easy to build the testbench
programs to verify applications on the
20
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
"context.txt" - these was created by the C-
model of the MUSRA.
The TI C64+ DSP is one 64-bit digital
signal processor targeted at the cryptography
applications on embedded systems. The C-
software of the AES algorithm that is optimized
In_Data.txt
Constant.txt
for
64-bit
architecture
just
requires
approximately 32 million instructions in total to
complete the assigned task. The simulation
shows that TI C64+ DSP can execute average
2.09 instructions per cycle, and therefore it takes
about 15.2 million cycles to process its tasks.
architecture that tightly couples a VLIW
processing core with an array of 4×4
reconfigurable cells (RCs). The reconfigurable
RCs act as instruction issue slots of the VLIW
core. The ADRES takes 3.6 million
instructions in total to complete its task with
6.31 instructions per cycle in average.
ADDRESS
GENERATOR
DATA MEMORY
SUBSYSTEM MODEL
GRF model
32
bits
4*8 bits
7*8 bits
FIFO_WIRE_IN
(31 downto 0)
FIFO_WIRE_IN
GRF
CLK
GENERATOR
DUT: RCA8x8_DATAPATH
CONTEXT
MEMORY
SUBSYSTEM
MODEL
8 bits
FIFO_WIRE_OUT
PE_OUT(5)(0~3)
The Virtex-II (XC2V500) is a FPGA
device from Xilinx. The authors in [11]
proposed the SoC that includes a MicroBlaze
processor and the programmable logic of the
Xilinx Virtex-II for performing the AES
algorithm. Their implementation shows that it
requires about 250 cycles to encrypt or decrypt
one state block.
Figure 13. RTL model of the MUSRA.
Finally, the system-level cycle-accurate
hardware/software co-verifying and evaluating
the performance of the whole algorithm. Both
RTL model and the cycle-accurate simulator
were developed by using the ModelSim EDA
tool from Mentor Graphics.
To evaluate the performance of the
MUSRA, the C-software of the AES algorithm,
which was optimized for the MUSRA
architecture, is first executed on only the
to execute approximately 65.4 million
instructions in total. The reason is that the
proposed loop transformation increases the
length of the C-software. However, when this
C-software is executed on both of the LEON3
and the MUSRA, the total cycles is just 2.2
million, which is about 6.9 times, 2.2 times,
and 1.6 times better than that of the TI C64+
DSP, Xilinx Virtex-II, and the ADRES. Our
proposal achieves 29.71 instructions per cycle
in average. The implementation by using
Xilinx Virtex-II is slower than ours due to the
inherent fine-grained architecture of FPGAs.
There are two reasons that make our proposal
better than the ADRES. Firstly, the MUSRA
uses an 8×8 RCA compared with 4×4 one of
the ADRES. Secondly, the AES algorithm is
partitioned into hardware tasks and software
5.2.Simulation Results and Evaluation
Figure 14 shows the simulation results for
the case of mapping Mix_Add() (i.e. DFG in
Figure 9) on the MUSRA. After the latency of
seven cycles (from 100ns to 220ns), RCA can
calculate and output a column of four bytes
(including pe_out(5)(0) to pe_out(5)(0)) of the
status matrix every clock cycle.
At the system level, the simulations are
done for both encryption and decryption
process on an input file of 300KB with key
lengths of 128- and 256-bit. The simulation
result shows that it take about 2.2 and 2.89
million cycles to perform the algorithm AES
with 128- and 256-bit key lengths on the
MUSRA, respectively.
Table 2 summarizes the simulation results
of the AES encryption and decryption
algorithm with MUSRA, TI C64+ DSP, and
ADRES, Xilinx Virtex-II (XC2V500).
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
21
Figure 14. Simulation result with RTL model of MUSRA.
Table 2. Performance of the AES algorithm on different platforms (using 128-bit key length)
Total
Instructions
Total
Cycles
Instructions
per Cycle
Cycles
per Block
Platform
Processing Elements
2.09
TI C64+ DSP[3]
ADRES[6]
1 CPU + Coprocessor
1 CPU + 4×4 RCs
1 CPU + FPGA
1 CPU
32M
23.2M
N/A
15.2M
3.6M
N/A
N/A
6.31
N/A
Xilinx Virtex-II [11]
LEON3
N/A
1
250
65.4M
65.4M
65.6M
2.2M
3416
114
Our
proposal
LEON3+MUSRA
1 CPU + 8×8 RCs
29.71
G
tasks that are executed simultaneously on both
LEON3 and MUSRA. It is difficult to exploit
task-level parallelism on the ADRES due to
tightly coupling between the VLIW processor
with the RCA.
ADRES reconfigurable processor, Xilinx
Virtex-II, and the TI C64+ DSP. It is also easy
to reconfigure the MUSRA to support both the
encryption and decryption with all key lengths
specified in the AES standard.
In the future work, some aspects such as
hardware/software partitioning, DFG extracting,
and scheduling, etc., will continue to be
optimized according to the architecture of the
MUSRA to achieve a better performance. The
proposed implementation also will be validated
with the MUSRA prototype on FPGA platform.
6. Conclusions
In this paper, a detailed explanation for
mapping the AES algorithm onto the MUSRA
platform has been presented. Multi-level
parallelism was exploited in order to improve
the performance of the AES algorithm on the
MUSRA. We first analyzed the source code of
the AES algorithm and proposed the
optimization solution to expose the instruction-
level and the loop-level parallelism.
Hardware/software partition and scheduling
were also proposed to exploit the task-level
parallelism. Our implementation has been
simulated and verified by the cycle-accurate
simulator of the MUSRA. Experimental results
show that the performance of the AES
algorithm on MUSRA is better than that of the
Acknowledgement
This work has been supported by Vietnam
National University, Hanoi under Project No.
QG.16.33.
References
[1] NIST, “Announcing the advanced encryption
standard
(AES)”,
Federal
Information
Processing Standards Publication, n. 197,
22
H.K. Nguyen, X.T. Tran / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 2 (2016) 10-22
November 26, 2001.
[2] Christophe Bobda,
Reconfigurable Computing
[9] G. Theodoridis, D. Soudris and S. Vassiliadis, “A
Survey of Coarse-Grain Reconfigurable
“Introduction
to
–
Architectures,
Architectures and Cad Tools Basic Definitions,
Critical Design Issues and Existing Coarse-grain
Reconfigurable Systems”, Springer, 2008.
Algorithms, and Applications”, Springer, 2007.
doi: 10.1007/978-1-4020-6100-4.
[3] J. Jurely and H. Hakkarainen, “TI’s new ’C6x
DSP screams at 1.600 MIPS. Microprocessor
Report”, 1997.
[10] Hung K. Nguyen, Quang-Vinh Tran, and Xuan-
Tu Tran, “Data Locality Exploitation for Coarse-
grained Reconfigurable Architecture in
a
[4] V. Dao, A. Nguyen, V. Hoang and T. Tran, “An
ASIC Implementation of Low Area AES
Encryption Core for Wireless Networks”, in Proc.
Reconfigurable Network-on-Chip”, The 2014
International Conference on Integrated Circuits,
Design, and Verification (ICDV 2014).
International
Management
Conference
and
on
Computing,
[11] Z. Alaoui Ismaili and A. Moussa, “Self-Partial
and Dynamic Reconfiguration Implementation for
AES using FPGA”, IJCSI International Journal of
Computer Science Issues, Vol. 2, pp. 33-40, 2009.
Telecommunications
(ComManTel2015), pp. 99-112, December 2015.
[6] Garcia, A., Berekovic M., Aa T.V., “Mapping
of the AES cryptographic algorithm on a
Coarse-Grain reconfigurable array processor”,
International Conference on Application-
Specific Systems, Architectures and Processors
(ASAP 2008).
[7] João M. P. Cardoso, Pedro C. Diniz:
“Compilation Techniques for Reconfigurable
Architectures”, Springer, 2009.
[8] A. Shoa and S. Shirani, “Run-Time
Reconfigurable Systems for Digital Signal
Processing Applications: A Survey”, Journal of
VLSI Signal Processing, Vol. 39, pp.213–235,
Springer, 2005.
Transformations”,
ACM
Transactions
on
Programming Languages and Systems (TOPLAS),
Volume 18, Issue 4, July 1996, pp. 424 - 453.
[13] S. Sohoni, and R. Min, et al. “A study of memory
system performance of multimedia applications”.
SIGMETRICS Performance 2001, pp. 206–215.
[14] M. Zhu, L. Liu, S. Yin, et al., "A Cycle-Accurate
Simulator for a Reconfigurable Multi-Media
System," IEICE Transactions on Information and
Systems, Vol. 93, pp. 3202-3210, 2010.
[16] Gaisler Research, “GRLIB IP Core User’s Manual”,
Version 1.3.0-b4133, August 2013.
H
13 trang
19260
Free
Bạn đang xem tài liệu "An efficient implementation of advanced encryption standard on the coarse-grained reconfigurable architecture", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- an_efficient_implementation_of_advanced_encryption_standard.pdf
