IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.12 DECEMBER 2015

2658

PAPER

Data-Transfer-Aware Design of an FPGA-Based HeterogeneousMulticore Platform with Custom Accelerators
Yasuhiro TAKEI† , Nonmember, Hasitha Muthumala WAIDYASOORIYA†a) , Masanori HARIYAMA† , Members,
and Michitaka KAMEYAMA† , Fellow

SUMMARY For an FPGA-based heterogeneous multicore platform,
we present the design methodology to reduce the total processing time considering data-transfer. The reconfigurability of recent FPGAs with hard
CPU cores allows us to realize a single-chip heterogeneous processor optimized for a given application. The major problem in designing such heterogeneous processors is data-transfer between CPU cores and accelerator
cores. The total processing time with data-transfers is modeled considering
the overlap of computation time and data-transfer time, and optimal design
parameters are searched for.
key words: heterogeneous multicore, FPGA, custom accelerators, reconfigurable architecture
Fig. 1

Architecture of a heterogeneous multicore processor.

1. Introduction
Applications used in low-power embedded processing tohigh performance computing have diﬀerent tasks such as
data-intensive tasks and control-intensive tasks. Therefore, the optimal architecture is diﬀerent from application
to application. Heterogeneous multicore architectures are
one promising way to execute such applications powereﬃciently. They use diﬀerent processor cores such as CPU
cores and accelerator cores as shown in Fig. 1. Examples
of such processors are [1] and [2], which contain multiple
CPU cores and accelerator cores. The CPU cores are suitable for control-intensive and complex computations, while
the accelerator cores for data-intensive and regular computations. When tasks of an application are allocated to the mostappropriate processor cores, all the cores work together toincrease the overall performances power-eﬃciently.
Current heterogeneous processors have a fixed amountof cores and each core has a fixed amount of processing
elements (PEs). Since there are many diﬀerent applications, some applications may work well in a particular heterogeneous processor, while some applications may not.
Moreover, large data transfer time between multiple coresis a serious problem. To solve these problems, we consider an FPGA-based heterogeneous multicore architecture
model. Recently, speed and power consumption of FPGAs
are greatly improved, and it would be very practical to use
the FPGA-based platform for real applications. FPGAs also
contain hard CPU cores as seen in Xilinx Zynq-7000 [3]and Altera Cyclone V SoC [4]. Therefore, CPU cores andManuscript received March 6, 2015.
Manuscript revised June 18, 2015.
†
The authors are with Tohoku University, Sendai-shi, 9808579 Japan.
a) E-mail: hasitha@ecei.tohoku.ac.jp
DOI: 10.1587/transfun.E98.A.2658

accelerator cores can be eﬃciently implemented on a single FPGA. Moreover, recent FPGAs are large enough tohold hundreds of processor cores. Our earlier work in [5],we have proposed an FPGA-based heterogeneous multicore
processor platform. However, the data transfer time between
the CPU core and accelerator cores is significantly high.
One popular method to reduce the data transfer time
is called double buﬀering, where two data buﬀers are used.
When one buﬀer is accessed for the computation, the data
are transferred to the other buﬀer. After the computation
is finished, the buﬀers are interchanged. However, this requires a large memory and only 50% is used for the computation. Since the internal (on-chip) memory is a scarce
resource in FPGA, it is desirable to use most of the memory
resources for the computation. Another method to reducethe data transfer time is to hide the data transfer between
one core with the computations of the other cores. Since
the recent FPGA-based processors contain many accelerator
cores due to the large number of LUTs, we use this method
to reduce the data transfer time. Since FPGA is reconfigurable, we can design the optimal architecture for diﬀerent
applications to reduce the processing time.
However, designing the optimal architecture that has
the smallest processing time for a given application is a difficult problem and it takes a large design time. To solve thisproblem, we propose a very basic architecture model thathas hard CPU cores and FPGA-based accelerator cores. The
architecture model is based on our previous work [5]. Unlike in [5], the proposed architecture model does not containa fixed number of accelerator cores, PEs or a fixed amountof internal memory modules. Instead we defined some design parameters such as the number of cores, the degree ofparallelism, etc. We optimize our architecture model for agiven application by choosing the optimal design parame-

c 2015 The Institute of Electronics, Information and Communication Engineers
Copyright TAKEI et al.: DATA-TRANSFER-AWARE DESIGN OF AN FPGA-BASED HETEROGENEOUS MULTICORE PLATFORM WITH CUSTOM ACCELERATORS

2659

ters. The optimal number of accelerator cores are chosen tohide the data transfer overhead.
In this paper, we propose a heterogeneous multicore
processor design methodology to reduce the total processing time under the resource constraint. We propose a parameterized architecture model and introduce an evaluation
methodology to find the optimal architecture for the design parameters. In the optimization problem, we focus
on window-based processing which has many applications
such as stereo matching [6], feature detection [7], scaleinvariant feature transformation (SIFT) [8], histogram oforiented gradients (HOG) [9], matrix processing, filtering,etc. The evaluation using filter computation as an example
demonstrates that the processing time estimated by the proposed design methodology has suﬃcient accuracy comparedto the actual measurement of the FPGA architecture. Moreover, the optimal architecture changes for diﬀerent applications, and it is possible to derive such architectures using the
proposed method.

Fig. 2

Proposed heterogeneous multi-core architecture.

2. Heterogeneous Multicore Architecture Model
The heterogeneous multicore architecture model is based on
the proposal in [5]. Figure 2 shows the overall architecture. It consists of FPGA-based custom accelerator cores, a
hard CPU core and an on-chip memory. An external memory is connected to the CPU core through the FPGA board.
The accelerator architecture used in this paper is based on
the FE-GA (flexible engine/generic ALU array) accelerator
proposed in [1]. FE-GA is a 16-bit coarse grain MIMD accelerator. It has a very simple architecture and simple interconnection network. Since the interconnection network is a
critical part in FPGA-based designs, FE-GA based MIMD
architecture is ideal for FPGAs. It is very easy to implement and easily scalable by changing the number of PEs
and memories. Moreover, it has been studied extensively formemory allocation [10], data transfers [11], context partitioning [12], etc and many eﬃcient techniques are proposed.
It is already been used to implement various applications inmany prior works, such as audio encoding [1], feature extraction [13], optical-flow extraction [14], etc. Therefore,
we choose FE-GA as a base for the MIMD accelerator usedin the proposed design.
Figure 3 shows the architecture of an MIMD accelerator core. It consists of a 2-dimensional array of PEs, local memory modules and address generation units (AGUs).
In order to simplify the interconnection network, only theleftmost PEs can directly retrieve data from local memory
modules, and only the rightmost PEs can directly write data
to local memory modules. PEs, AGUs and interconnection network are dynamically reconfigurable. A PE consistsof a 16-bit fixed-point ALU and a multiplier as shown in
Fig. 4. It is capable of doing operations such as addition,
accumulation, subtraction, comparison, absolute diﬀerencecomputation, multiplication, etc. Since the data path is fully
pipelined, it takes only one clock cycle to complete any operation.

Fig. 3

MIMD accelerator architecture.

Fig. 4

Architecture of a PE.

The address calculation in the proposed architecture is
explained in Fig. 5. In CPUs and GPUs, the address calculation and data processing are done on the same ALU as
shown in Fig. 5(a). To reduce the address processing time,
AGUs (address processing uints) are employed. The address calculation is done on AGUs in parallel to the dataprocessing which is done on ALUs as shown in Fig. 5(b).
Several address patterns and AGU architectures for image
processing have been discussed in previous works [15], [16].
Since accelerator cores use multiple AGUs to access multiple memory modules, a relatively large area is required.
However, considering the benefits of power-eﬃciency andhigh performance, it is worth spending resources on AGUs.
In this work, the address function proposed in previous
works [7], [10] is used. This address function is simple,
and the resource usage of AGUs is small.
To increase the performance of an FPGA-based hetero-IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.12 DECEMBER 2015

2660

Fig. 5

Timechart of the Address processing.

Fig. 7

Fig. 6

Image partition.

Number of accelerator cores and timechart.

geneous multicore platform, it is important to consider not
only the architecture of accelerator core but also the numberof accelerator cores. As shown in Fig. 6(a), if the number ofaccelerator cores is one, data-transfer and computation on
an accelerator core are done in serial. On the other hands, if
the number of accelerator cores is two as shown in Fig. 6(b),data-transfer to core 1 and computation on core 2 are done inparallel. Therefore, we can reduce the total processing timeby changing the numbers of cores and PEs per core while
keeping the total area of all cores is a constant. This techniques is used in many multicore processors such as GPUs[17], [18] and the Cell.B.E processor [19]. Since the number of cores and PEs per core are fixed in these processors,
the advantages of this technique are limited. On the other
hand, an FPGA-based architecture can reduce the total processing time eﬃciently by choosing the optimal number ofcores and PEs to hide most of the data transfer time.
3. Total Processing Time Minimization
3.1 Window-Based Processing Model
We use window-based processing as an example to minimize the total processing time of an FPGA-based multicore
platform. Window-based processing contains repeated access to the same data that belong to multiple overlapping
windows. Therefore, it is important to maximize the data
sharing, while allowing parallel processing. Such a data
sharing and scheduling scheme is proposed in [10], and weuse it on the proposed architecture. The work in [10] proposes an oﬀ-line scheduling scheme where a part of the data
are transferred to the accelerator core, and the computation is performed. During the computation, the data are nottransferred to the accelerator core. Similarly, during a datatransfer, the accelerator core pauses its computations. The
transferred data are stored in multiple local memory mod-Fig. 8

Window access in a partial image.

ules in the accelerator core in such a way that the data areaccessed in parallel. Therefore, no data collision occurs inside an accelerator core. Please refer [10] for detailed discussions on how the data access is done inside an accelerator core. In this paper, we generalize this oﬀ-line schedulingscheme for multiple accelerator cores. The data transfer to
one accelerator core starts only after the data transfers to
all the other cores are finished. Therefore, no data collisionoccurs between the data transfer from the CPU core to theaccelerator cores. Similar to [10], no data collision occurs
inside an accelerator core as well.
Figure 7 shows the window-based processing model
proposed in [10]. As shown in Fig. 7(a), an image is divided in to N partial partial images. The width and the heightof the partial image is given by PW and PH respectively.
The data between diﬀerent partial images are not shared. A
batch of WP partial images are processed in parallel. The
term WP is called the degree of window parallelism andN partial ≥ WP . The pixels in a window are accessed in pixelparallel column-serial manner as shown in Fig. 7(b). The
data in a column are accessed in parallel. This parallelism iscalled the pixel-parallelism and denoted by PP .
As shown in Fig. 8 a partial image contains multiple
scan areas. After the first scan area is accessed the next scanarea, which is one pixel bellow, is accessed. The data in scan
areas are accessed by sliding a window from left-to-right.
The diﬀerent scan areas of a partial image are processed sequentially in the accelerator cores as shown in
Fig. 9. The processing of a scan area is assigned to a sequence. In the first sequence, all the pixel data belong to
the scan area one are transferred. In the second sequence,
only the diﬀerence of the first and second scan areas is trans-

TAKEI et al.: DATA-TRANSFER-AWARE DESIGN OF AN FPGA-BASED HETEROGENEOUS MULTICORE PLATFORM WITH CUSTOM ACCELERATORS

2661

Fig. 10

Fig. 9

Data transfer between CPU cores and accelerator cores.

ber of PEs available is PE MAX .

Sequential processing of the scan areas.

WP × PP × (log2 PP + 1) ≤ PEmax
ferred. The rest of the data are shared. Moreover, the newdata are overwritten to the memory addresses with obsolete
data which are not required for further processing. Thismethod minimizes the data-transfer time since there is nodata-duplication, and also optimizes the memory capacity.
The width and the height of a scan area are equal to thepartial image width PW and the window height WH respectively. Therefore, in one partial image, there are S (PH −WH +1)
scan areas.
In the above explained window-based processing
model, the following relationships exists. The degree ofpixel-parallelism (PP ) must satisfy the relationship given by
Eq. (1), where, C M is a natural number and WH is the window height.
PP × C M = WH

(1)

The number of accelerator cores (NC ) and the degree ofwindow-parallelism (WP ) must satisfy the relationship given
by Eq. (2), where, NW is the number of windows processedin parallel in one accelerator core.
WP = NC × NW

(2)

The parallelism of operations are constrained by the
resources available in the FPGA. The MIMD architecture
model explained in Fig. 3 contains columns of PEs where
each column has n PEs. Only the first column is connectedto the memory while the rest of the columns use the computation results of their previous columns. If we consider
direct mapping, DFGs of most window-based applications
have a tree-like structure. To implement this structure, weneed n × (log2 n + 1) number of PEs, where n and (log2 n + 1)
are correspond to the depth and height of the tree. Therefore, we can have (log2 n + 1) columns of PEs in the MIMD
architecture. This kind of architecture models proposed inmany works such as [1]. In window-based processing, thepixel parallelism PP equals to the number of PEs in the firstcolumn. Therefore, the number of PEs required to process atthe degree of pixel parallelism equals to PP × (log2 (PP ) + 1).
Since WP partial images are processed in parallel, the resource constraint is given by Eq. (3), where maximum num-(3)

Moreover, to implement window parallelism, the scan areasof WP partial images must be stored in the FPGA internal
memory. This constraint is given in Eq. (4)WP × (WH × PW ) ≤ I Mmax

(4)where, I Mmax is the maximum amount of internal memoryin the FPGA. Form Eqs. (3) and (4), we can see that thedegree of parallelism WP × PP is limited by the amount of
PEs and internal memory of the FPGA.
3.2 Processing Time Estimation
In this section, we explain the formulation of the processing time minimization problem. The processing of each sequence (a scan area) in Fig. 9 is divided into the following
three phases.
Phase 1 Data-transfer from the CPU cores to theaccelerator cores
Phase 2 Computation on the accelerator cores
Phase 3 Data-transfer from the accelerator cores to the
CPU cores.
In this section, we discuss the processing time estimation ofeach phase and the total processing time.
3.2.1 Data-Transfer Time from CPU Cores to Accelerator
Cores (Phase 1)
The data are transferred from the CPU core to the accelerator core through the AXI (Advanced eXtensible Interface) bus connected to the ARM processor. The bus widthof the accelerator core’s input memory and the word widthof the input data are given by BB and BCA . If BB ≥ BCA ,we can transfer several data in parallel. On the other hand,
if BB < BCA , one word is divided in to several segments
and transfer each segment in a serial manner. Therefore, thenumber of words transferred from CPU core to accelerator
core at a time (NCA ) is given by Eq. (5).
⎧ B 
B⎪⎪
when BB ≥ BCA⎨ BCA
NCA = ⎪
(5)
⎪ 1/ BCA⎩
when B < B
BB

B

CA

IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.12 DECEMBER 2015

2662

The data transfer between CPU cores and accelerator
cores is shown in Fig. 10. The frequencies of the external
memory, CPU cores and accelerator cores may not be thesame. Even though frequencies does not match, CPU coresand the data bus has necessary hardware such as memory
controllers, data buﬀers, etc for an eﬃcient data transfer.
However, we cannot determine the transfer speed by using
the parameters such as bus width, frequencies, etc. Therefore, we measure the data transfer time between CPU andaccelerator cores using sample data. The term α is the average time per word-transfer from CPU cores to accelerator
cores.
The amount of words transferred in sequence S 1 is different from those in the other sequences. In sequence S 1 ,the amount of words transferred from a CPU core to an accelerator core is PW × WH as shown in Fig. 9. Data-transfer
time from a CPU core to an accelerator core in the sequence
S 1 (tCA1 ) is given by
tCA1 = α ×

NW× PW × W H
NCA

NW× PW .
NCA(7)

We estimate the computation time (tcomp ) in each sequenceon the accelerator core. The architecture of the accelerator isfully pipelined. After the pipeline is filled, the computation
is done in every clock cycles. As shown in Fig. 8, the sizeof the window is WH × WW . Each scan area includes (PW −WW + 1) windows. When processing a window, PP pixels
are calculated in parallel as shown in Fig. 7(b). Therefore,
tcomp is given by
1
W H × WW
×× (PW − WW + 1) + t pipefAPP

tAC = β ×

NW
× (PW − WW + 1)
NAC

(10)

where β is the average time per word-transfer from accelerator core to CPU cores.

We process WP partial images in parallel, and the processing
time required for this is given by t partial . Figure 11 shows
the time chart of the processing in an accelerator core. The
time tinit consists of the initial data-transfer time from theCPU cores to the accelerator cores and the computation timein the sequence S 1 . These initial data-transfers to diﬀerent
cores cannot be done in parallel since there is only one busthat has a limited bandwidth. Therefore, tinit is given bytinit = tCA1 × NC + tcomp(11)

During tmid , ttrans and tcomp are repeated as shown in
Fig. 11. The time ttrans shown in Fig. 11 is defined by
Eq. (12)3.2.2 Computation Time (Phase 2)

tcomp =

The amount of words transferred from an accelerator core
to a CPU core is (PW − WW + 1) in each sequence. Datatransfer time from an accelerator core to a CPU core in eachsequence (tAC ) is given by

3.2.4 Estimation of the Total Processing Time
(6)

Note that NW is the number of windows processed in an accelerator core as described in Eq. (2). In other sequence (S 2
to S (PH −WH +1) ), the amount of words transferred from a CPU
core to an accelerator core is PW . Data-transfer time from a
CPU core to an accelerator core in each sequence (tCA2 ) is
given bytCA2 = α ×described in Sect. 3.2.1. The number of words transferredfrom accelerator cores to CPU cores at a time (NAC ) is given
by Eq. (9) where, BAC is the word width of the output dataof the accelerator cores.
⎧ B 
B⎪⎪
when BB ≥ BAC⎨ BAC
NAC = ⎪
(9)
⎪
B
AC
⎩ 1/
when BB < BAC
BB(8)

where fA is the clock frequency, and t pipe is the pipeline latency of the accelerator core. Note that the address generation time does not appear in Eq. (8) since the address processing time is completely overlapped with the data processing time. This is because the address and data processing aredone in AGUs and PEs respectively in parallel.
3.2.3 Data-Transfer Time from Accelerator Cores to CPU
Cores (Phase 3)
We estimate the data-transfer time (tAC ) from accelerator
cores to CPU cores in each sequence by the same methodttrans = tAC + tCA2 + tctrl(12)where, tAC is the data-transfer time from accelerator cores
to CPU core, tCA2 is the data-transfer time from CPU coresto accelerator cores and tctrl is the control overhead due tostarting and stopping the accelerator cores. To estimate tmid ,we have to consider the overlap between the data-transfers
and the computations. This overlap can be classified into
following two cases.
Case A1: The computation time of one core partially hides
the data-transfers of the other cores as shown in
Fig. 12(a). This is represented by tcomp < (NC − 1) ×
ttrans . During tmid , the time period (NC × ttrans ) is repeated (PH − WH ) times since there are PH − WH + 1
sequences as explained in Sect. 3.1 and (PH − WH ) of
those sequences belong to tmid .
Case A2: The computation time completely hides the datatransfer time of the other cores as shown in Fig. 12(b).
This is represented by tcomp ≥ (NC − 1) × ttrans . Similar
to the case A1, the time period (tcomp +ttrans ) is repeated(PH − WH ) times during tmid . According to these two
types, tmid is given by Eq. (13).

TAKEI et al.: DATA-TRANSFER-AWARE DESIGN OF AN FPGA-BASED HETEROGENEOUS MULTICORE PLATFORM WITH CUSTOM ACCELERATORS

2663

Fig. 11

Fig. 12

Timechart of the processing in the accelerator cores.

The data-transfers and the computations during tmid⎧⎪
NC × ttrans × (PH − WH )
⎪
⎪
⎪
⎪
⎪
when
tcomp < (NC − 1) × ttrans
⎪
⎪
⎪
⎪
⎪
(Case1 A1)⎪⎪⎨
tmid = ⎪⎪⎪⎪⎪(ttrans + tcomp ) × (PH − WH )
⎪
⎪
⎪
⎪
⎪
when tcomp ≥ (NC − 1) × ttrans⎪⎪⎪⎩(Case A2)

Fig. 13(13)

The time t f inal is the data-transfer time from the accelerator cores to the CPU cores in the sequence S (PH −WH +1) .
During t f inal , the data-transfers form the accelerator cores to
the CPU cores (tAC ) overlap with the computations as shownin Fig. 13. This can be classified into three cases.
Case B1
Case B2
Case B3

Overlap with data-transfer and computation in t f inal .

tcomp ≥ (NC − 1) × ttrans(NC − 1) × tAC ≤ tcomp < (NC − 1) × ttranstcomp < (NC − 1) × tAC

In case B1, tAC is smaller than ttrans , so that tcomp of one corehides tAC of all the other cores as shown in Fig. 13(a). When
tcomp < (NC − 1) × ttrans , tcomp can be either “greater than orequals to (NC − 1) × tAC ” or “smaller than (NC − 1) × tAC ”.
In case 2, tcomp of one core completely hides the tAC of theother cores as shown in Fig. 13(b). In case 3, tcomp of one
core partially hides the tAC of the other cores as shown in
Fig. 13(c). According to these three cases, t f inal is given by
Eq. (14).
⎧⎪(NC − 1) × ttrans + tAC
⎪
⎪
⎪
⎪
⎪
when tcomp ≥ (NC − 1) × ttrans
⎪
⎪
⎪
⎪
⎪
(Case B1)
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
tAC + tcomp
⎪
⎪
⎪
⎪
⎪
⎨ when (NC − 1) × tAC ≤ tcomp
t f inal = ⎪(14)⎪< (NC − 1) × ttrans
⎪
⎪
⎪
⎪
⎪
⎪
(Case B2)
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
NC × tAC
⎪
⎪
⎪
⎪
⎪
when
tcomp < (NC − 1) × tAC⎪⎪⎪⎩(Case B3)

IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.12 DECEMBER 2015

2664

The processing time required for WP partial images(t partial ) is given byt partial = tinit + tmid + t f inal

(15)

The total processing time denoted by T image is thetime required to process a whole image. As explained in
Sect. 3.1, an image is divided into N partial partial images, and
WP partial images are processed in parallel. Equation (15)gives the processing time of WP partial images. After processing WP partial images, another WP partial images areprocessed. Therefore the total processing time required toprocess a whole image is given by
N partial
T image = t partial ×
WP

Fig. 14

Implemented architecture.

(16)

Note that, for smaller images where N partial = WP , T image
equals t partial .
Using Eqs. (11), (13), (14) and (15), we can see thatthe total processing time is derived from the combination of
the design parameters, WP , PP , NC , NW , PW and PH . These
parameters define the architecture of the FPGA-based heterogeneous multicore platform and its scheduling. Therefore, it is very important to find the optimal combination ofdesign parameters that minimize the total processing time.
The design parameter optimization is discussed in Sect. 4.

Table 1 Estimated time vs. measured time.
Window
Estimated Measured
Error
size
time(ms)time(ms)(%)
12 × 12
46.93
46.51
0.51
16 × 16
60.38
60.07
0.91
18 × 18
70.50
70.51
0.02
24 × 24
115.89115.870.01

4. Evaluation
We use Xilinx Zynq-7000 EPP ZC702 board [20] for theevaluation. Zynq integrates a dual Cortex-A9 CPU coresand FPGA equivalent to Atrix-7 on a single chip. In addition, the evaluation kit has a DDR3 SDRAM for an external memory. The proposed heterogeneous platform is designed using Xilinx PlanAhead 14.2. The CPU core is programmed using C language on Xilinx EDK 14.2. Figure 14
shows the implemented architecture. There are accelerator
cores, one Cortex-A9 hard CPU core, the AXI4 bus and a
DDR3 SDRAM for the external memory. The processing
time of the proposed heterogeneous platform is measured
by the AXI Timer IP. The clock frequency of the CPU coreis 667 MHz.
To estimate the data-transfer time of the proposed heterogeneous platform given by Eq. (15), we measured thevalues α, β and tctrl in Eqs. (6), (10) and (12) respectively.
We measured data-transfer times between the external memory and memory modules of accelerator cores. From experimental results, the values of α, β and tctrl are measured to
be 186.06 (ns), 213.02 (ns) and 430.00 (ns) respectively, themaximum clock frequency of the accelerator cores is measured to be 100 MHz. Table 1 shows the diﬀerence between
the estimated processing time and the measured processing
time for diﬀerent windows sizes. The estimated processing
time is calculated using Eq. (15) for a given set of design
parameters. We implement the architecture described by thesame set of parameters on FPGA and measure the processing time. This is called the measured processing time. According to the results, the error rate calculated using Eq. (17)Fig. 15Filter computation of a VGA image.

is less than 1%. This small error percentage shows that theestimated processing time is suﬃciently accurate to optimize the processor architecture.
Error =

|Measured − Estimated|
× 100(%)
Measured(17)

4.1 Exploration of the Design Parameter Space to Find the
Minimum Total Processing TimeIn this section, we show how the design parameter space is
explored to obtain the optimal ones that give the minimum
processing time for filter computation. The specifications of
the filter computation are given in Fig. 15. We assume thatthe maximum degree of parallelism (WP × PP ) is limited to
16 by the resource constraints in Eqs. (3) and (4). Basedon the specifications, the scope of the design parameters are
determined as shown in Fig. 15(b). We estimate the total
processing time for all the combinations of the design parameters in order to find the optimal parameters that gives
the minimum processing time.
Figure 16 shows an example of problem formulation
for a given set of design parameters. The design parameters

TAKEI et al.: DATA-TRANSFER-AWARE DESIGN OF AN FPGA-BASED HETEROGENEOUS MULTICORE PLATFORM WITH CUSTOM ACCELERATORS

2665

In the proposed method, we can design a reasonably good
FPGA-based heterogeneous processor architecture by justsearching for the optimal design parameters. Even using
exhaustive search, the optimal design parameters are foundin a very short time. Therefore, we can reduce the FPGA
architecture design eﬀort and time dramatically by the proposed method. When exploring the design parameter space,
we consider all possible situations that belongs two diﬀerent
cases shown in Fig. 12. For example, in the last column ofTable 2, tcomp = 0.4020 and (NC − 1) × ttrans = 0.994. Therefore, tcomp < (NC − 1) × ttrans so that this design belongs tocase A1, which is shown in Fig. 12(a).

Fig. 16

Problem formulation for a given set of design parameters.

Fig. 17

Processing time estimation.

are shown in Fig. 16(a). According to the parameters PW
and PH , we partition the image into 16 partial images asshown in Fig. 16(b). Since the number of cores (NC ) is 4,
we assign four diﬀerent partial images to each core. The
scan areas of a partial image is shown in Fig. 16(c). Since
NW = 4, one core processes four scan areas belongs to four
diﬀerent partial images in parallel.
Figure 17 shows the time chart of processing. As explained in Sect. 3.2, the total processing time is the summation of tinit , tmid and ttotal . Each term is calculated using
Eqs. (11), (13) and (14) respectively. During tinit , the firstscan area belongs to a partial image is transferred to the accelerator cores. Since the bus-width (BB ) is 32 bits and the
input data width BCA is 8 bits, The data of four windows aretransferred to the accelerator core in parallel. However, theoutput data width BAC is 16 bits so that only the processing results of only two windows are transferred in parallel
during tmid and t f inal . During tmid , the data transfers and thecomputations of scan areas 2 to 117 are done. During t f inal ,the remaining computations and the output data transfer corresponds to the last scan area is done.
We estimated the total processing time for all combinations of design parameters by doing an exhaustive search.
The search could be done in few minutes on an Intel CPU
at 3.2 GHz. Table 2 shows the processing time for some ofthose combinations. The total processing time is minimized
when WP = 16, PP = 1, NC = 4, NW = 4, PW = 94 and
PH = 246. Usually, it would take several days of designing and compilation time to design an FPGA architecture.

4.2 Evaluation of the Optimized Design for Diﬀerent Filter Sizes
Table 3 shows the optimized design parameters for diﬀerent
filter sizes. Note that the window size equals to the filter
size. We assume that the maximum degree of parallelism is
16 due to the resource constraints. According to the results,
optimized design parameters vary with diﬀerent filter sizes.
That means, the partitioning, scheduling and the hardware
design are diﬀerent according to the specifications of theapplication. However, in conventional heterogeneous multicore architectures such as [1], we cannot optimize the design
parameters since the number of accelerator cores, the number PEs, etc are fixed. Therefore, the proposed FPGA-based
heterogeneous platform has a high degree of flexibility, andcan be optimized for diﬀerent applications.
The optimized design (decided by the design parameters) in Table 3 belongs to either the case A1 in Fig. 12(a) or
the case A2 in Fig. 12(b). This shows that considering bothcases is important to obtain the optimal design. Although
not shown in Table 3, each of the above cases are further divided in to another three cases, B1∼B3 as shown in Fig. 13.
When exploring the design parameter space, we consideredthese cases also.
Tables 4 and 5 shows the optimized design parameterswhen the maximum degree of parallelism is 32 and 64 respectively. When the degree of parallelism increases, thecomputation time reduces. As a result, the data transfer time
could be larger than the computation time. Therefore, mostof the optimized designs belong to the case A1 where thedata transfer time is not fully hidden by the computationtime.
For some optimized designs, the degree of parallelism
is smaller than the maximum value. For example, when thewindow size is 8 × 8 in Table 5, the maximum degree ofparallelism allowed is 64. However, the degree of window
and pixel parallelisms in the optimized design are 8 and 2
respectively. This give a total degree of parallelism of 16
which is just 25% of the maximum available. In this case,the computation time is much smaller than the data transfer
time due to the parallel computations. Therefore, the total processing time is decided by the data transfer time asshown in Fig. 12(a), so that reducing the computation timefurther does not make any impact on the total processing

IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.12 DECEMBER 2015

2666
Table 2 Estimated processing time for diﬀerent design parameters. All diﬀerent combinations ofdesign parameters are searched to find the optimal parameters that minimize the total processing time.

Degree ofwindow
parallelism
WP
1
4
4
4
16
16
16
16
16
16

Design Parameters
Degree of
Number Windows
pixel
of
per a
parallelism
cores
core
PP
NC
NW
4
1
1
2
1
4
2
4
1
2
2
2
1
1
16
1
2
8
1
4
4
1
4
4
1
8
2
1
16
1

Type of the design
Partial
image
width
PW
640
328
172
172
94
94
172
94
94
172

Partialimage
height
PH
480
248
480
480
248
248
132
248
248
132

tcomp
(ms)

ttrans(ms)

Type0.40010.40070.20100.20100.20240.20230.40200.20230.40200.40200.25310.18680.06630.06630.1981
0.09930.09550.04990.06630.0663

Case A2
Case A2
Case A2
Case A2
Case A2
Case A2
Case A2
Case A2
Case A1
Case A1

Total
processing
time
(ms)
305.80137.98127.02125.61
94.70
71.83
61.02
60.38*
67.47
134.14*The smallest total processing time.
Table 3is 16.

Optimized design parameters for diﬀerent filter sizes. The maximum degree of parallelism

Windowsize
WH = WW

Window
parallelism
WP

Pixel
parallelism
PP

8
9
10
12
13
15
16
17
18
20
24

16
16
16
16
16
16
16
16
16
16
16

1
1
1
1
1
1
1
1
1
1
1

Table 4is 32.

Design Parameters
NumberWindows
of coresper a core
NC
NW
2
2
2
4
4
4
4
4
8
8
8

8
8
8
4
4
4
4
4
2
2
2

Partial image
width height
PW
PH
166
166
167
169
169
93
94
94
95
58
62

126
126
127
129
129
247
248
248
249
480
480

Total
processing
time (ms)Typeof thedesign

46.24
45.88
46.20
46.93
46.62
54.50
60.38
65.53
70.50
83.97
115.89Case A1
Case A1
Case A1
Case A1
Case A1
Case A2
Case A2
Case A2
Case A2
Case A2
Case A2

Optimized design parameters for diﬀerent filter sizes. The maximum degree of parallelism

Windowsize
WH = WW

Window
parallelism
WP

Pixel
parallelism
PP

8
9
10
12
13
15
16
17
18
20
24

8
16
8
16
16
32
32
32
32
32
32

2
1
2
1
1
1
1
1
1
1
1

Design Parameters
NumberWindows
of coresper a core
NC
NW
2
2
2
4
4
2
4
4
4
8
8

time.
Table 6 shows the comparison of the total processing
time of the proposed method against the method given in[10]. The window-based processing model used in bothmethods are the same. However, the work in [10] does
not consider the overlap of data transfers with the computation. In [10], the total processing time is calculated simply

4
8
4
4
4
16
8
8
8
4
4

Partial image
width height
PW
PH
166
166
167
169
169
93
94
94
95
97
62

244
126
245
129
129
131
132
132
133
135
252

Total
processing
time (ms)Typeof thedesign

45.58
45.88
45.53
46.93
46.62
49.00
49.53
49.05
49.55
50.75
61.60

Case A1
Case A1
Case A1
Case A1
Case A1
Case A1
Case A1
Case A1
Case A1
Case A1
Case A2

by adding the total computation time, the total data transfer
time and the total control time together. It uses one large
accelerator core that can process the data in parallel using
multiple PEs. The comparison is done for three diﬀerent
resource constraints. The maximum degree of parallelism(WP × PP ) is calculated to be 16, 32 and 64 in each of thethree constraints.

TAKEI et al.: DATA-TRANSFER-AWARE DESIGN OF AN FPGA-BASED HETEROGENEOUS MULTICORE PLATFORM WITH CUSTOM ACCELERATORS

2667
Table 5is 64.

Optimized design parameters for diﬀerent filter sizes. The maximum degree of parallelism

Windowsize
WH = WW

Window
parallelism
WP

Pixel
parallelism
PP

8
9
10
12
13
15
16
17
18
20
24

8
16
8
16
16
32
16
32
16
16
64

2
1
2
2
1
1
2
1
2
2
1

Table 6

Design Parameters
NumberWindows
of coresper a core
NC
NW
2
2
2
2
4
2
4
4
4
4
4

4
8
4
8
4
16
4
8
4
4
16

Partial image
width height
PW
PH
166
166
167
169
169
93
172
94
173
97
62

244
126
245
129
129
131
132
132
133
250
480

Total
processing
time (ms)Typeof thedesign

45.58
45.88
45.53
46.93
46.62
49.00
47.33
49.05
47.35
49.75
57.43

Case A1
Case A1
Case A1
Case A1
Case A1
Case A1
Case A1
Case A1
Case A1
Case A2
Case A1

Total processing time reduction of the proposed method compared to [10].

Maximum
degree ofparallelism

Windowsize
WH = WW

Computation
time (ms)Work in [10]Control
Data transfer
time (ms)time (ms)

Total processing
time (ms)This work
Total processing
time (ms)Reduction
Percentage
(%)

16

8
10
15
20
24

12.00
18.60
41.05
71.60
101.53

0.20
0.20
0.20
0.20
0.20

44.21
44.01
43.50
43.00
42.59

56.42
62.81
84.75
114.79144.32

46.24
46.20
54.50
83.97
115.89

18.04
26.45
35.69
26.85
19.70

32

8
10
15
20
22
24

6.02
9.32
20.54
35.81
43.00
50.78

0.20
0.20
0.20
0.20
0.20
0.20

44.21
44.01
43.50
43.00
42.79
42.59

50.43
53.53
64.24
79.00
85.99
93.57

45.58
45.53
49.00
50.73
54.10
61.60

9.63
14.94
23.72
35.79
37.09
34.17

64

8
10
15
20
24

3.02
4.67
10.28
17.92
25.40

0.20
0.20
0.20
0.20
0.20

44.21
44.01
43.50
43.00
42.59

47.44
48.88
53.98
61.11
68.19

45.58
45.53
49.00
49.75
57.43

3.92
6.86
9.23
18.59
15.78

According to the results in Table 6, the total processing
time is reduced up to 37% using the proposed method. The
computation amount increases with the window size. For
small window sizes, the computation time is smaller compared to the data transfer time so that most of the data transfer time is not hidden. For larger window sizes, the computation time is larger compared to the data transfer time due
to large computation amount. In this case, the data transfer
time is hidden, so that the total processing time is decided
by the computation time. Therefore, the largest total processing time reduction is achieved when the computation
time nearly equals the data transfer time. When we increase
the degree of parallelism, the computation time decreases.
However, both the data amount and the number of parallel data transfers are unchanged (the maximum amount ofparallel data transfers is already reached), so that the datatransfer time remains the same. Nevertheless, the total processing time is reduced in both methods due to the reductionof the computation time.
According to the results in Table 6, the total processing time in the proposed method is smaller than that in [10].
Even in the extreme cases where one of the data transfer

time or the computation time is negligibly smaller compared to the other, the total processing time of the proposed
method would be at least equals to [10]. During the design
parameter exploration, the method in [10] is also one of overthousand combinations considered by the proposed method.
Therefore the proposed method would never get worse thanthat in [10].
5. Conclusion
We have proposed a design methodology for FPGA-based
heterogeneous multi-core platform with custom accelerator
cores. The proposed approach optimizes the total processing time by considering this overlap of data-transfers andcomputations. According to the evaluation, the processing
time estimation has a suﬃcient accuracy, so that the architecture of the FPGA-based heterogeneous platform can be
optimized. FDTD (finite-diﬀerence time-domain) computation, which is basically a stencil computation, has alreadybeen implemented in FPGAs [21], [22]. Therefore, we believe that the proposed architecture model could be optimized for such applications grid-based HPC (high perfor-

IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.12 DECEMBER 20152668

mance computing) applications such as stencil computation[23] in future works.
Acknowledgment
This work is supported by MEXT KAKENHI Grant Number 24300013.
References[1] H. Shikano, M. Ito, M. Onouchi, T. Todaka, T. Tsunoda, T. Kodama,
K. Uchiyama, T. Odaka, T. Kamei, E. Nagahama, M. Kusaoke, Y.
Nitta, Y. Wada, K. Kimura, and H. Kasahara, “Heterogeneous multicore architecture that enables 54x AAC-LC stereo encoding,” IEEE
J. Solid-State Circuits, vol.43, no.4, pp.902–910, 2008.
[2] H. Kondo, M. Nakajima, N. Masui, S. Otani, N. Okumura, Y. Takata,
T. Nasu, H. Takata, T. Higuchi, M. Sakugawa, H. Fujiwara, K.
Ishida, K. Ishimi, S. Kaneko, T. Itoh, M. Sato, O. Yamamoto, andK. Arimoto, “Design and implementation of a configurable heterogeneous multicore SoC with nine CPUs and two matrix processors,”
IEEE J. Solid-State Circuits, vol.43, no.4, pp.892–901, 2008.
[3] S. Dutta, V. Rajagopolan, B. Taylor and R. Wittig, “Xilinx Zynq
embedded processing platform” A Symp. High Performance Chips(HOT Chips 23), 2011.
[4] https://www.altera.com/products/soc/portfolio/cyclone-v-soc/overvi
ew.html[5] Y. Takei, H.M. Waidyasooriya, M. Hariyama, and M. Kameyama,“Evaluation of an FPGA-based heterogeneous multicore platform
with SIMD/MIMD custom accelerators,” IEICE Trans. Fundamentals, vol.E96-A, no.12, pp.2576–2586, 2013.
[6] M. Hariyama, H. Sasaki, and M. Kameyama, “Architecture ofa stereo matching VLSI processor based on hierarchically parallel memory access,” IEICE Trans. Inf. & Syst., vol.E88-D, no.7,
pp.1486–1491, 2005.
[7] H.M. Waidyasooriya, Y. Ohbayashi, M. Hariyama, and M.
Kameyama, “Memory-access-driven context partitioning for window-based image processing on heterogeneous multicore processors,” IEICE Trans. Inf. & Syst., vol.E95-D, no.2, pp.354–363,
2012.
[8] D.G. Lowe, “Object recognition from local scale-invariant features,”Proc. Seventh IEEE International Conference on Computer Vision,
vol.2, pp.1150–1157, 1999.
[9] N. Dalal and B. Triggs, “Histograms of oriented gradients for humandetection,” 2005 IEEE Computer Society Conference on Computer
Vision and Pattern Recognition (CVPR’05), vol.1, pp.886–893,
2005.
[10] H.M. Waidyasooriya, Y. Ohbayashi, M. Hariyama, and M.
Kameyama, “Memory allocation exploiting temporal locality for
reducing data-transfer bottlenecks in heterogeneous multicore processors,” IEEE Trans. Circuits Syst. Video Technol., vol.21, no.10,
pp.1453–1466, 2011.
[11] Y. Hiramatsu, H.M. Waidyasooriya, M. Hariyama, T. Nojiri, K.
Uchiyama, and M. Kameyama, “Acceleration of block matching on a low-power heterogeneous multi-core processor based on
DTU data-transfer with data re-allocation,” IEICE Trans. Electron.,
vol.E95-C, no.12, pp.1872–1882, 2012.
[12] H.M. Waidyasooriya, Y. Ohbayashi, M. Hariyama, and M.
Kameyama, “Memory-access-driven context partitioning for window-based image processing on heterogeneous multicore processors,” IEICE Trans. Inf. & Syst., vol.E95-D, no.2, pp.354–363,
2012.
[13] H.M. Waidyasooriya, D. Okumura, M. Hariyama, and M.
Kameyama, “Task allocation with algorithm transformation for reducing data-transfer bottlenecks in heterogeneous multi-core processors: A case study of HOG descriptor computation,” IEICE
Trans. Fundamentals, vol.E93-A, no.12, pp.2570–2580, 2010.

[14] H.M. Waidyasooriya, M. Hariyama, and M. Kameyama, “Acceleration of optical-flow extraction using dynamically reconfigurable
ALU arrays,” International Conference on Engineering of Reconfigurable Systems and Algorithms, pp.291–294, 2009.
[15] Y. Kobayashi, M. Hariyama, and M. Kameyama, “Memory allocation for multi-resolution image processing,” IEICE Trans. Inf. &Syst., vol.E91-D, no.10, pp.2386–2397, 2008.
[16] H.M. Waidyasooriya, M. Hariyama, and M. Kameyama, “Memory
allocation for window-based image processing on multiple memory
modules with simple addressing functions,” IEICE Trans. Fundamentals, vol.E94-A, no.1, pp.342–351, 2011.
[17] H.-N. Ta and S. Lee, “High-performance computing model for 3D
camera system,” 2011 IEEE International Conference on Robotics
and Biomimetics, pp.354–359, 2011.
[18] K. Iwai, T. Kurokawa, and N. Nisikawa, “AES encryption implementation on CUDA GPU and its analysis,” 2010 First International
Conference on Networking and Computing, pp.209–214, 2010.
[19] T. Chen, Z. Sura, K. O’Brien and J.K. O’Brien, “Optimizing theuse of static buﬀers for DMA on a CELL chip,” Proc. 19th Int.
Conf. Languages and Compilers for Parallel Computing, vol.4382,
pp.314–329, 2006.
[20] http://www.xilinx.com/support/documentation/boards and kits/zc70
2 zvik/ug850-zc702-eval-bd.pdf[21] J.P. Durbano, F.E. Ortiz, J.R. Humphrey, P.F. Curt, and D.W. Prather,“FPGA-based acceleration of the 3D finite-diﬀerence time-domain
method,” 12th Annual IEEE Symposium on Field-Programmable
Custom Computing Machines, pp.156–163, 2004.
[22] H.M. Waidyasooriya, Y. Takei, M. Hariyama, and M. Kameyama,“Low-power heterogeneous platform for high performance computing and its application to 2D-FDTD computation,” Proc. International Conference on Engineering of Reconfigurable Systems andAlgorithms (ERSA), pp.147–150, 2012.
[23] K. Datta, M. Murphy, V. Volkov, S. Williams, J. Carter, L. Oliker, D.
Patterson, J. Shalf, and K. Yelick, “Stencil computation optimization
and auto-tuning on state-of-the-art multicore architectures,” International Conference for High Performance Computing, Networking,Storage and Analysis, pp.1–12, 2008.

Yasuhiro Takei
received the B.E. degree inelectronic engineering in Information Sciences,
M.S. degree in Information Sciences from Tohoku University, Sendai, Japan, in 2011 and2013 respectively. He is currently a Ph.D. student in Graduate School of Information Sciences, Tohoku University. His research interests include heterogeneous multicore processor
architectures.

Hasitha Muthumala Waidyasooriya
received the B.E. degree in Information Engineering, M.S. degree in Information Sciences
and Ph.D. in Information Sciences from Tohoku
University, Japan, in 2006, 2008 and 2010 respectively. He is currently an Assistant Professor with the Graduate School of Information
Sciences, Tohoku University. His research interests include reconfigurable computing, processor architectures for big-data processing andhigh-level design methodology for VLSIs.

TAKEI et al.: DATA-TRANSFER-AWARE DESIGN OF AN FPGA-BASED HETEROGENEOUS MULTICORE PLATFORM WITH CUSTOM ACCELERATORS

2669

Masanori Hariyama
received the B.E. degree in electronic engineering, the M.S. degree
in information sciences, and the Ph.D. degree
in information sciences from Tohoku University,
Sendai, Japan, in 1992, 1994, and 1997, respectively. He is currently an Associate Professor
with the Graduate School of Information Sciences, Tohoku University. His research interests
include real-world applications such as robotics
and medical applications, big data applications
such as bio-informatics, high-performance computing, VLSI computing for real-world application, high-level design
methodology for VLSIs, and reconfigurable computing.

Michitaka Kameyama
received the B.E.,
M.E. and D.E. degrees in Electronic Engineering from Tohoku University, Sendai, Japan, in
1973, 1975, and 1978, respectively. He is currently a Professor in the Graduate School ofInformation Sciences, Tohoku University. His
general research interests are intelligent integrated systems for real-world applications androbotics, advanced VLSI architecture, and newconcept VLSI including multiple-valued VLSI
computing. Dr. Kameyama received the Outstanding Paper Awards at the 1984, 1985, 1987 and 1989 IEEE International Symposiums on Multiple-Valued Logic, the Technically Excellent
Award from the Society of Instrument and Control Engineers of Japan in
1986, the Outstanding Transactions Paper Award from the IEICE in 1989,
the Technically Excellent Award from the Robotics Society of Japan in
1990, and the Special Award at the 9th LSI Design of the Year in 2002.
Dr. Kameyama is an IEEE Fellow.