High-Level Synthesis through metaheuristics and LUTs optimization in FPGA devices

Abstract

Operations scheduling and Lookup Table (LUT) based technology mapping are fundamental problems of mapping designs onto an electronic device, such as a Field Programmable Gate Array. We present an approach to apply two optimizations consecutively. As first optimization, we apply several metaheuristic algorithms for multi-objective optimization at the High-Level Synthesis stage. As a second optimization, we realize reductions of LUTs at the Logic Synthesis stage. Several circuit designs are represented in a Data Flow Graph (DFG) and the experiments are carried out on the standard Mediabench benchmark. In the first optimization, we compared NSGA-II, FEMO, HypE, IBEA, SPEA2 and WSGA. Results have an average improvement 14.06% in occupied Area and 7.01% in Power consumption. Then, optimized DFG schedules are converted into Very High Description Language code using the Xilinx ISE Design Suite tool. Later, in the second optimization, The IMap algorithm is used to obtain combinational area reductions. Results show that 60% of the circuits are improved in comparison with the Xilinx ISE Design Suite.

Keywords

Circuit optimization DFG FPGA MOEA VHDL

1. Introduction

The Field Programmable Gate Array (FPGA) is a semiconductor device containing logic blocks whose interconnection and functionality can be configured in situ using a High Description Language (HDL), Very High Description Language (VHDL) or Verilog. FPGAs are characterized as programmable or reconfigurable, and it is precisely this property that distinguishes them from other similar devices, like an Application-Specific Integrated Circuit (ASIC). Actually, FPGAs are used in countless scenarios; for example, robotics and household appliances [8,32]. The FPGAs contain Configurable Logic Blocks (CLB), Input/Output Blocks (IOB) and several types of connections: direct connections, general purpose connections and long distance lines. Optimizing the manner in which these connections are made it is possible to reduce the resources used by the FPGA device. This is a non trivial scientific problem to be treated [28].

Fig. 1.

Optimization proposals in the flow of circuit implementations in FPGAs devices.

Data path algorithms can be represented using a Data Flow Graph (DFG) [31]. Each node in DFG represents an operation that is to be executed in the algorithm. High-Level Synthesis (HLS), also known as Behavioral Synthesis, is the process of converting an algorithmic description into a synthesizable Register Transfer Level (RTL) netlist. RTL is synthesized in the device with an Electronic Design Automation (EDA) tool, like the Xilinx ISE Design Suite [37] or the Vivado Design Suite [38]. The high level description may be in the form of a DFG or a programming language such as C. The HLS design flow consists of three sub-tasks; namely, scheduling, allocation and mapping [22].

The main contribution of this research is the consecutive execution of two different optimization procedures in the same project. The first optimization consists of applying multi-objective metaheuristics for scheduling, allocation and mapping, and the second optimization consists of applying an iterative technology-mapping for LUTs optimization. First, the problem is translated into a DFG. We use 6 Multi-Objective Evolutionary Algorithms (MOEAs) from the Platform Independent Interface for Search Algorithms (PISA) [5,6]. Second, the optimized schedules were converted into VHDL code using the Xilinx ISE Design Suite. The Xilinx ISE Design Suite has no updates since 2013, but it is still a widely-used software to implement FPGAs manufactured before 2013. As future work, the Vivado Design Suite will be used.

In Fig. 1 the optimization proposals for the circuit flow implementations on FPGAs devices is shown. The first optimization is in the HLS stage and the second optimization is in the Logic Synthesis stage. Before the first optimization, designs are represented using the DFGs because it is easy to manipulated them from an iterative metaheuristic algorithm and state-of-the-art methodologies exist for estimating the objective functions of interest (Delay, Area and Power).

The remainder of the paper is organized as follows. In Section 2 some previous works of the two proposed optimizations are presented. In Section 3, the definition of DFG, the Mediabench benchmark, DFG schedules and quality estimators are described. The first optimization is presented in Section 4. The second optimization process is presented in Section 5. In Section 6, the results obtained are presented. Finally, we discuss our conclusions and future work in Section 7.

2. Related work

2.1. Previous work on High-Level Synthesis

The use of MOEAs for optimal scheduling, allocation, and mapping in HLS has been widely reported in the literature. A framework for applying MOEA and Particle Swarm Optimization (PSO) based approaches for simultaneous Area, Delay, and Power optimization in HLS of data paths is presented in [18]. A survey of MOEAs based methodologies for HLS is presented in [22]. Evolutionary Algorithms (EAs) being population based meta-heuristics are extremely effective in design space exploration. For example, a MOEAs based methodology for data path synthesis from a DFG for multi-objective Area and Delay optimizations is described in [22]. The authors propose a multi-chromosome encoding scheme for the DFG scheduling priority and functional unit constraints. An improved low power FPGA binding of data-paths from DFG with NSGA-II based selection is presented in [19]. An extensive treatment of applications of MOEAs in Very Large Scale Integration (VLSI) and embedded systems was presented in [4].

2.2. Previous work on LUTs optimization

In order to implement a logic circuit in a FPGA, it must be converted to an equivalent one composed only of physical elements present in the FPGA, by a process called technology mapping. In some FPGAs, the main element used to implement combinational circuits is the LUT. For LUT-based FPGAs, technology mapping converts a circuit made up of gates into a circuit composed of LUTs.

There are several algorithms for this task including CutMap [10], DAOMap [9] and ZMap [11]. The IMap algorithm [28] is used to perform technology mapping with the objective of minimizing the number of LUTs generating smaller solutions and faster runtimes in comparison with FlowMap, CutMap, DAOMap and ZMap.

These two areas of research exist separately: MOEAs for HLS and LUTs optimization. However, no research has been reported in the literature that applies both optimizations consecutively.

3. Background

3.1. Data Flow Graph

A DFG represents a design in HLS, an instruction set that must run sequentially or in parallel to achieve the required results [34]. Each graph node is a contiguous code region without branches and the edges between nodes indicate jumps in the program flow. The node function generates a new value on its outputs, depending of its inputs. Formally, a DFG is defined as $\begin{matrix} (1) & G = (V, E), \end{matrix}$ where $V = {v_{1}, \dots, v_{n}}$ is a finite set whose elements are nodes, and $E \subset V \times V$ is an asymmetrical relationship data flow, where elements are directed edges that represent data [20].

The nodes represent operations in a DFG. A directed edge $e_{i j}$ from $v_{i} \in V$ to $v_{j} \in V$ exist if the data produced by operation (represented by $v_{i}$ ) is consumed by operation (represented by $v_{j}$ ). Then $v_{i}$ is an immediate predecessor of $v_{j}$ . Similarly, $v_{j}$ is an immediate successor of $v_{i}$ .

3.2. Mediabench benchmark

The Mediabench benchmark [26,27] was used to perform and validate the experiments to optimize the DFG and then convert to VHDL code, which can be synthesizable in FPGA devices. The Mediabench benchmark was selected because it is widely used in the literature [4,18,19,22,36].

Mediabench has a base of 20 accessible circuits in .dot format with a directed graph structure. With an algorithm written in C language, the conversion from .dot format to a graphs format .graphml (standard graph format written in xml) was performed. Being the DFG in .graphml format already, they can be charted and analyzed with the yEd tool [39]. In addition, being the DFG in standard .xml format, it is possible to read it with the C language library pugixml [21].

The experiments were performed with 10 circuits of the benchmark and the features of each DFG (number of nodes, number of edges and number of operations) are detailed in Table 1.

Table 1
Features of the DFG Mediabench benchmark

DFG Nodes Edges Operations

HAL 11 8 4

MESA – Horner Bezier (MESA-HB) 18 16 4

Auto Regression Filter (ARF) 28 30 2

MPEG – Motion Vectors (MPEG-MV) 32 29 4

Elliptic Wave Filter (EWF) 34 47 2

Finite Input Response Filter 2 (FIR2) 40 39 4

Finite Input Response Filter 1 (FIR1) 44 43 4

JPEG – Smooth (JPEG-SD) 51 52 5

MESA – Feedback (MESA-FP) 53 50 6

EPIC – Collapse_pyr (EPIC) 56 73 7

DFG	Nodes	Edges	Operations
HAL	11	8	4
MESA – Horner Bezier (MESA-HB)	18	16	4
Auto Regression Filter (ARF)	28	30	2
MPEG – Motion Vectors (MPEG-MV)	32	29	4
Elliptic Wave Filter (EWF)	34	47	2
Finite Input Response Filter 2 (FIR2)	40	39	4
Finite Input Response Filter 1 (FIR1)	44	43	4
JPEG – Smooth (JPEG-SD)	51	52	5
MESA – Feedback (MESA-FP)	53	50	6
EPIC – Collapse_pyr (EPIC)	56	73	7

3.3. Problem encoding

For DFG scheduling it is necessary to have a way to encode. There are two main elements [18,19,22]:

Node priority field: used to encode a topologically sorted permuted list of tasks (nodes).

Module allocation field: consists of a list of integers specifying the maximum number of functional units of each type available for scheduling in every clock cycle.

In Fig. 2 a DFG example with the Node priority field is shown, that requires to first run node 3, then node 1, and so on until node 7. In the Module allocation field there are functional units (two multipliers and one adder). Note that in Fig. 3, the DFG is scheduled in clock cycles defined by the functional units availability, in accordance with the node dependencies in the DFG. In first clock cycle multiplication operations 3 and 1 should be executed. It can be seen that the operation 2 should be run on the second clock cycle because the operations 3 and 1 are occupied, the 2 functional units are available in multiplication restrictions of the Module allocation field. The following are basic schedulings that can be applied to the DFGs.

Fig. 2.

Example of a schedule for DFG.

Fig. 3.

Clock cycles for a DFG scheduling.

3.4. Basic schedulings

Basic schedulings represent the simplest ways to define the schedule. It is assumed that the number of functional units has been previously specified and the operations in the graph are sorted with respect to their data dependency. The resulting scheduling may not be optimal, but results obtained with As Soon As Posible (ASAP) and As Late As Posible (ALAP) are fastest. Three basic schedulings were implemented:

ASAP: The simplest type of scheduling occurs when we wish to optimize the overall latency of the computation and do not care about the number of resources required. This can be achieved by simply starting each operation in a DFG as soon as its predecessors have completed [12].

ALAP: It is a variant of ASAP, but postpones the execution of nodes without affecting the amount of total clock cycles needed to fully implement the DFG. Each node is executed in the clock cycle as late as possible.

Random: As the name suggests, it is a scheduling where nodes are assigned to functional units randomly, without violating the dependency in the DFG.

Implementations of ASAP and ALAP do not have Area restrictions. This means that they use the functional units necessary to carry out operations as soon as possible or as late as possible, respectively. For this reason, the two implementations consume many functional units (Area) and power consumption (Power). An example is shown in Fig. 4 [34], where ASAP in the first clock cycle needs 5 functional units and ALAP in the third clock cycle requires 4 functional units. These two designs always produce schedules with the fewest clock cycles possible to execute the entire DFG.

Fig. 4.

Example of basic scheduling, with ASAP and ALAP made on a DFG.

3.5. Quality estimators

Schedules are subject to three estimates to measure their quality and thus make comparisons. These estimates are proposed in [18,22,23].

Delay: The Delay or length L is the number of time steps or clock cycles needed to run the DFG scheduling. In the example of Fig. 3, the Delay is 4 because 4 clock cycles are sufficient to compute the DFG.

Area: The cost of Area (A) of a design is based on the total of Functional Units ( $FU$ ) plus the total of Registers (R) necessary to execute all nodes in the DFG, given by $\begin{matrix} (2) & A = FU + R . \end{matrix}$ The number of $FU$ is known from the schedule by adding all the values of the Module allocation field. R is obtained by determining the total number of registers necessary for the execution of the DFG using the Left Edge algorithm described in [16]. In Fig. 3 the occupied Area is 5, because $FU = 2$ and $R = 3$ .

Power: To estimate Power, first a compatibility graph is created. Where a node i is connected to another node j, if the operation of node j can be executed in the same FU of node i. To do this, they need to have the same kind of operation and their variables cannot overlap in time. An example of a compatibility graph is shown in Fig. 5, the example corresponds to the DFG of Fig. 3 [18].

The estimation Power (P) based on is given by $\begin{matrix} (3) & P = (\frac{n}{m_{1}}) + m_{2} + m_{3}, \end{matrix}$ where $m_{1}$ is total number of edges in the compatibility graph. The tuning parameter n, is chosen depending on the value of $m_{1}$ . The variable $m_{2}$ is an average of edge weights for the lowest $K %$ in the value range for each node, where K is a parameter. The variable $m_{3}$ is a generalization of $m_{2}$ with $K = 100 %$ . The variable K is defined as 60% for all of our experiments, but it may be varied according to the DFG.

Fig. 5.

Example of a compatibility graph.

4. First optimization process: High-Level Synthesis

The problem of finding an ideal scheduling, allocation and mapping is NP-hard [35]. Hence, metaheuristic algorithms are needed to solve it. First, tests are done to determine if the three performance measures define conflicting objectives.

4.1. HLS as a multi-objective problem

In order to evaluate whether the problem is multi-objective, it is necessary to use the payoff matrix [29]. The payoff matrix is a matrix that allows us to quantify the level of conflict between the objectives being considered. It is constructed from the solutions obtained after optimizing each objective independently. The payoff matrix is a square matrix where the diagonal is the ideal point, formed by the optimal values of each objectives. The payoff matrices of 10 DFGs of the benchmark are detailed in Table 2, where it can be seen that the three objective functions are opposed notably. Diagonals are marked in bold. We run 10 times each uni-objective algorithm: ASAP basic scheduling, uni-objective EA only optimizing Area and uni-objective EA only optimizing Power. We select the best solution for each objective. The basic scheduling ASAP always achieves the best value for the objective function Delay.

Table 2
Payoff matrices of 10 DFG of the Mediabench benchmark

DFG Objective functions ASAP-Delay Uni-objective EA-Area Uni-objective EA-Power

HAL Delay 4 6 6

Area 13 7 9

Power 5.933621 4.368365 3.895405

MESA-HB Delay 8 18 12

Area 11 6 7

Power 4.844874 4.608531 3.696173

ARF Delay 8 21 11

Area 18 10 14

Power 3.52241 3.166591 2.831112

MPEG-MV Delay 6 21 14

Area 31 11 13

Power 7.50114 3.993173 3.448706

EWF Delay 14 34 25

Area 20 10 12

Power 2.530418 2.514357 2.352566

FIR2 Delay 11 30 17

Area 33 18 21

Power 10.657209 5.600834 3.991618

FIR1 Delay 11 36 19

Area 45 24 26

Power 26.768005 9.639142 3.803355

JPEG-SD Delay 16 38 18

Area 37 20 28

Power 3.880019 3.490961 2.98825

MESA-FP Delay 7 36 14

Area 47 23 28

Power 7.131594 6.679447 4.218116

EPIC Delay 7 30 33

Area 48 16 19

Power 8.296047 6.893044 6.257889

DFG	Objective functions	ASAP-Delay	Uni-objective EA-Area	Uni-objective EA-Power
HAL	Delay	4	6	6
Area	13	7	9
Power	5.933621	4.368365	3.895405
MESA-HB	Delay	8	18	12
Area	11	6	7
Power	4.844874	4.608531	3.696173
ARF	Delay	8	21	11
Area	18	10	14
Power	3.52241	3.166591	2.831112
MPEG-MV	Delay	6	21	14
Area	31	11	13
Power	7.50114	3.993173	3.448706
EWF	Delay	14	34	25
Area	20	10	12
Power	2.530418	2.514357	2.352566
FIR2	Delay	11	30	17
Area	33	18	21
Power	10.657209	5.600834	3.991618
FIR1	Delay	11	36	19
Area	45	24	26
Power	26.768005	9.639142	3.803355
JPEG-SD	Delay	16	38	18
Area	37	20	28
Power	3.880019	3.490961	2.98825
MESA-FP	Delay	7	36	14
Area	47	23	28
Power	7.131594	6.679447	4.218116
EPIC	Delay	7	30	33
Area	48	16	19
Power	8.296047	6.893044	6.257889

Based on the results in Table 2, multi-objective algorithms for this problem are required. A MOEA achieves a balance of 2 o more objectives functions without preferring neither of them. A complete review of these techniques is beyond the scope of this work, the interested reader is referred to [4,13,24,33,40].

For the experiments of MOEAs the PISA [5,6] framework is used. This platform is based on separating the optimization process in two parts: the optimization problem and the selection process. We evaluate 6 different selection processes in PISA:

Nondominated Sorting Genetic Algorithm II (NSGA-II) [14,15].

Fair Evolutionary Multi-objective Optimizer (FEMO) [25].

Hypervolume based multi-objective Evolutionary algorithm (HypE) [3].

Indicator-Based multi-objective Evolutionary Algorithm (IBEA) [41].

Strength Pareto Evolutionary Algorithm 2 (SPEA2) [42].

Weight Sum vector Genetic Algorithm (WSGA) [22].

After performing the optimizations, the occupied Areas are calculated and compared by EDA tools such as the Xilinx ISE Design Suite, these tools are important because with them VHDL codes can be implemented in real devices. This is another contribution of this research, because in the state-of-the-art, implementations are usually not reported with EDA tools.

4.2. Quality indicators

When measuring the quality of multi-objective algorithms two aspects are generally taken into account: minimize the distance of the obtained solutions by the algorithm, regarding the optimal Pareto Front (PF) [33] of the problem; and maximize the spread of solutions on the front so the distribution is as uniform as possible. However, since the optimal PF in unknown, several quality indicators are used to measure the performance of the algorithms; these are:

Epsilon: It is the most used indicator because it measures the distance or difference between PF and approximate best known front, so it gives a clear and direct idea of performance. This indicator should be minimized and is based on a ratio of ε-dominance. There is a multiplicative version and a additive version of this indicator [43].

Hypervolume: This indicator, proposed in [3], measures the Hypervolume of one portion of space that is weakly dominated by a set approach A, and it is maximized. It measures the convergence and the diversity jointly. In order to calculate this value, the objective space must be defined by a reference point that dominates (at least weakly) all the points to be used.

R: This indicator can be used to evaluate and compare sets of approaches based on a set of utility functions. This indicator should be minimized. A utility function is defined as a representation from the set of target vectors n-dimensional to a set of real numbers [17].

5. Second optimization process: LUTs optimization

This section describes the second optimization, but first, it is necessary to convert the scheduled DFG to VHDL code. This is important because it allows comparing the estimates made on the DFG versus the actual estimates made by tools such as the Xilinx ISE Design Suite. The VHDL code is converted into Moore Finite States Machine (FSM) [30]. Already having the VHDL code optimized in a Moore FSM, these may be subjected to a second optimization phase, in the Logic Synthesis stage.

Fig. 6.

DFG example with two types of operations (adders and multipliers).

Fig. 7.

Example distribution of states for a DFG schedule.

5.1. VHDL code generation as a state machine from a Data Flow Graph

VHDL code generation takes place as follows. Once the DFG is read in format .graphml with pugixml, this generation is done in C code. VHDL code is automatically generated from the DFG schedule detailed in Section 3.3. For getting the VHDL code type Moore FSM, we included in the architecture definition the sentences CASE IS WHEN for each state of FSM. Each state is equivalent to a planned clock cycle, as it is shown by examples in Fig. 6 and Fig. 7; where R1, R2 and R3 represent records for storing the outputs of operations; A1, A2, M1, M2 and M3 represent functional units (of addition and multiplication); and a0, a1, a2, b0, b1, b2, c0, c1 and c2 are the node operations [19]. The state diagram for this example is shown in Fig. 8. If all states were executed, all output signals have definite values.

The results of each operation in the state are stored in registers, and are shared global variables. The inputs and outputs of the Entity – part of the VHDL code – are defined like data type unsigned of 4 bits and 5 bits, respectively, with the library IEEE.NUMERIC_STD, in order to carry out all necessary operations (adder, multiplier, exponential and so on). However, the number of bits of inputs and outputs can be defined differently. In addition, in the entity, reset and the clock are input ports. The VHDL architecture has two processes: one to change from one state to another, which only runs if there is a change in the inputs reset or clock; and another process, that has as sensitive list the signal representing the current state. This second process contains the combinational logic of all states.

Fig. 8.

State diagram for a DFG schedule.

5.2. Simulation with the Xilinx ISE Design Suite

After performing conversions into VHDL code, it is necessary to validate the syntax and logic with a corresponding EDA tool. In this case it was validated with the Xilinx ISE Design Suite (Version 14.7) [37]. Simulations of the 10 benchmark circuits were performed with the 3 basic schedules explained in Section 3.4. All simulations were performed on the FPGA Xilinx Spartan 3E XC3S500E device, and FG320 package.

5.3. Iterative technology-mapping algorithm

The technology mapping of the benchmark circuits was performed using the IMap algorithm [28]. This iterative algorithm is reviewed here. Some circuits in the benchmarks contain sequential logic. IMap was applied only to the combinational portion of these circuits.

5.4. Overview

IMap takes a circuit composed of simple gates and converts it into a circuit composed of LUTs. These circuits are represented as Directed Acyclic Graphs (DAG), defined as $G = (V, E)$ , where the set of nodes in the circuit is V and E is the set of directed edges. Each node $v \in V$ represents a Primary Input (PI), Primary Output (PO) or logic gate. Each edge $e \in E$ , with head $x = head (e), x \in V$ and tail $y = tail (e), y \in V$ , represents a signal in the circuit that is the output of x and an input of y [28]. In Fig. 9, IMap performs the mapping of a full adder circuit into LUTs.

Fig. 9.

Technology mapping with IMAP of combinational circuit full adder. (a) Original circuit. (b) Best cones. (c) Equivalent circuit with LUTs.

Forward traversal selects the best cone for every node. A following backward traversal selects a set of cones to cover the whole graph. Iteration is beneficial because every backward traversal influences the behavior of the next forward traversal. Finally the cones selected by the final backward traversal are converted into LUTs [28]. Following are more details on each step (Generation of K-feasible cones, Forward traversal, Backward traversal and Conversion of cones into LUTs).

5.5. Generation of K-feasible cones

The mapping of a circuit is done using cones. A cone $C_{v}$ is a subgraph composed of a root node v and some of its predecessors. Cones do not contain PI or PO nodes. Any node $u \in C_{v}$ has a path to v that lies entirely in $C_{v}$ . If the number of input nodes to a cone is less than or equal to K then it is K-feasible. Any K-feasible node can be implemented by a K-input LUT. Cones are generated by traversing the graph in topological order from PI to PO. At every node v, new cones are generated by combining the cones at the input nodes and adding node v. These new cones are then tested for K-feasibility and those that are not K-feasible are discarded [28].

5.6. Forward traversal

For each node the best cone is selected. This selection determines the quality of the mapping solution. Cones can be selected to either minimize depth or minimize Area. Selecting the cone that minimizes depth at each node leads to a mapping solution that is depth optimal. To minimize Area the Area flow metaheuristic is used. The Area flow of each cone is computed and the cone with the lowest Area flow is selected. However, the value of the Area flow depends on the number of output edges of the cone, which cannot be known until the backward traversal selects the cones to cover the whole graph. Therefore, an approximation that improves with the number of iterations is used [28]. All the benchmark circuits were mapped to minimize Area.

5.7. Backward traversal

The graph is traversed in reverse topological order from PO to PI. At each node the best cone selected by the preceding Forward traversal (see Section 5.6) is used. The nodes covered by a previously used cone are skipped so that only the nodes that are required to be visible are expanded. The cones selected by the backward traversal cover the whole graph and compose the mapping solution [28].

In Fig. 10 to Fig. 12 IMap is applied to a small example circuit. A mapping solution for this circuit with $K = 3$ is shown in Fig. 11 and another solution for $K = 4$ is presented in Fig. 12.

Fig. 10.

Original circuit. IMap applied to example circuit.

Fig. 11.

Example circuit to which IMap is applied, using $K = 3$ .

Fig. 12.

Example circuit to which IMap is applied, using $K = 4$ .

Fig. 13.

Conversion of a cone into a LUT.

5.8. Conversion of cones into LUTs

Each cone in the mapping solution is converted into a LUT that implements the functionality of the cone. These LUTs are defined by a string of hexadecimal digits which encode the truth table of each cone. An example of how this conversion is done is shown in Fig. 13.

6. Results

This section presents the experimental results. In the first optimization process, the comparative results of the MOEAs through quality indicators are presented. Subsequently the results achieved on the 3 objective functions are presented. Also, the Area estimates made in simulation with the Xilinx ISE Design Suite are presented. In the second optimization process, a comparison between the estimates made in simulation with the Xilinx ISE Design Suite and results of Area minimization in LUT-based FPGA technology mapping are presented.

6.1. Results of the first optimization process

The MOEAs experimental parameters are composed by the Table 3.

Table 3
The MOEAs experimental parameters

Parameter Value

Number of runs 10

Population size 50

Number of generations 50

Number of evaluations 2500

Objective functions 3

Selectors 6

Variators 1

Quality indicators 3

Crossover probability 0.9

Mutation probability 0.2

Parameter	Value
Number of runs	10
Population size	50
Number of generations	50
Number of evaluations	2500
Objective functions	3
Selectors	6
Variators	1
Quality indicators	3
Crossover probability	0.9
Mutation probability	0.2

Table 4

Results for the Epsilon indicator, showing the average value of all runs; bold indicates the best

DFG	NSGA-II	FEMO	HYPE	IBEA	SPEA2	WSGA
HAL	1.93E-01	1.89E-01	2.18E-01	2.42E-01	2.34E-01	5.28E-01
MESA-HB	2.56E-01	2.55E-01	2.68E-01	2.48E-01	2.48E-01	7.12E-01
ARF	1.66E-01	1.73E-01	1.99E-01	1.64E-01	1.61E-01	4.52E-01
MPEG-MV	2.00E-01	1.58E-01	1.51E-01	1.67E-01	1.44E-01	2.53E-01
EWF	1.76E-01	2.07E-01	2.33E-01	1.68E-01	1.96E-01	7.26E-01
FIR2	2.22E-01	1.79E-01	1.58E-01	1.73E-01	1.63E-01	3.13E-01
FIR1	2.06E-01	1.24E-01	9.37E-02	9.15E-02	1.63E-01	2.80E-01
JPEG-SD	2.02E-01	1.89E-01	2.90E-01	2.67E-01	2.67E-01	4.71E-01
MESA-PF	3.74E-01	1.90E-01	2.02E-01	2.26E-01	1.79E-01	3.50E-01
EPIC	1.63E-01	2.32E-01	2.16E-01	1.98E-01	1.87E-01	5.63E-01

Table 5

Results for the Hypervolume indicator, showing the average value of all runs; bold indicates the best

DFG	NSGA-II	FEMO	HYPE	IBEA	SPEA2	WSGA
HAL	6.98E-02	8.96E-02	1.01E-01	8.17E-02	8.68E-02	5.86E-01
MESA-HB	1.55E-01	1.82E-01	2.15E-01	1.37E-01	1.45E-01	6.08E-01
ARF	1.51E-01	1.41E-01	2.32E-01	1.33E-01	1.25E-01	5.38E-01
MPEG-MV	2.92E-01	1.87E-01	2.36E-01	2.78E-01	1.72E-01	3.57E-01
EWF	1.14E-01	1.72E-01	1.86E-01	1.11E-01	1.38E-01	6.61E-01
FIR2	3.92E-01	3.04E-01	2.48E-01	2.79E-01	2.37E-01	4.12E-01
FIR1	3.46E-01	1.86E-01	1.26E-01	1.49E-01	2.71E-01	3.98E-01
JPEG-SD	2.30E-01	2.80E-01	3.32E-01	3.68E-01	2.86E-01	6.06E-01
MESA-PF	6.07E-01	3.03E-01	2.47E-01	2.82E-01	2.20E-01	3.97E-01
EPIC	2.17E-01	2.54E-01	2.60E-01	2.54E-01	1.89E-01	6.47E-01

Table 4, Table 5 and Table 6 show the quality indicators of 6 MOEAs with 10 DFG of the Mediabench benchmark. In bold is the best result for each problem.

It can be seen that the WSGA metaheuristic achieves results with less quality, according to three quality indicators. Although, SPEA2 and NSGA-II achieve results with slightly higher quality than the other metaheuristics. SPEA2 and NSGA-II achieve the best results eight times and eleven respectively.

The NSGA-II algorithm has a better performance than the WSGA algorithm, this behavior is similar to the results reported in [18].

On the other hand, results of Table 4, Table 5 and Table 6 are not compared with [18], because quality indicators (Epsilon, Hypervolume and R) are not reported in [18].

As a second set of results to be analyzed we report the values of the objective functions in the PF found. The objective functions average of all individuals of the PF is calculated. For this, the six MOEAs are compared with the 3 basic scheduling algorithms. Next tables show the performance of 6 MOEAs with 10 DFG of the Mediabench benchmark. Table 7 shows the average of the Delay objective function, Table 8 shows the average of the Area objective function and Table 9 shows the average of the Power objective function. Table 10 show the improvement for each problem of Area and Power with respect to the basic scheduling algorithms. In each table, the best result is indicated in bold.

In the case of Delay, there is not improvement by any of the metaheuristics, this is because the basic scheduling algorithms, ASAP and ALAP, always give the minimum clock cycles possible. However, an average improvement of 14.06% is obtained in terms of the Area and 7.01% in terms of Power.

Analyzing the diversity of the obtained solutions, the PF found by NSGA-II has higher diversity than the other algorithms. In Fig. 14, NSGA-II for one of the problems (EWF) is shown.

Table 6

Results for the R indicator, showing the average value of all runs; bold indicates the best

DFG	NSGA-II	FEMO	HYPE	IBEA	SPEA2	WSGA
HAL	1.20E-02	1.39E-02	1.64E-02	1.46E-02	1.36E-02	1.58E-01
MESA-HB	2.79E-02	3.19E-02	3.96E-02	2.41E-02	2.81E-02	2.09E-01
ARF	1.81E-02	1.69E-02	3.44E-02	1.73E-02	1.62E-02	1.28E-01
MPEG-MV	4.48E-02	2.63E-02	3.57E-02	4.32E-02	2.45E-02	6.18E-02
EWF	1.66E-02	2.29E-02	2.94E-02	1.80E-02	1.74E-02	2.17E-01
FIR2	7.26E-02	5.09E-02	3.52E-02	4.05E-02	3.92E-02	8.38E-02
FIR1	5.78E-02	2.55E-02	1.68E-02	1.88E-02	4.15E-02	7.27E-02
JPEG-SD	4.01E-02	4.97E-02	5.36E-02	6.88E-02	5.11E-02	1.54E-01
MESA-PF	1.25E-01	5.14E-02	4.17E-02	4.86E-02	3.16E-02	7.81E-02
EPIC	3.19E-02	4.03E-02	4.05E-02	3.71E-02	2.55E-02	1.84E-01

Table 7

Results for the Delay objective function, showing the average value of all PF individuals; bold indicates the best

DFG	ASAP	ALAP	Random	NSGA-II	FEMO	HYPE	IBEA	SPEA2	WSGA
HAL	4	4	6	6	6	6	6	6	4
MESA-HB	8	8	11	12	12	12	11	11	8
ARF	8	8	13	11	11	11	12	10	11
MPEG-MV	6	6	11	12	13	12	11	9	10
EWF	14	14	27	25	23	25	22	24	15
FIR2	11	11	16	16	14	18	14	16	14
FIR1	11	11	16	20	19	15	15	13	15
JPEG-SD	16	16	26	22	21	22	18	21	18
MESA-PF	7	7	19	13	11	11	14	16	10
EPIC	7	7	25	32	22	27	26	22	15

Table 8

Results for the Area objective function, showing the average value of all PF individuals; bold indicates the best

DFG	ASAP	ALAP	Random	NSGA-II	FEMO	HYPE	IBEA	SPEA2	WSGA
HAL	13	11	10	9	9	9	9	9	10
MESA-HB	11	10	9	7	7	7	8	8	9
ARF	18	18	14	14	14	12	11	13	11
MPEG-MV	31	19	22	16	14	13	15	16	14
EWF	20	22	18	18	17	18	17	18	19
FIR2	33	11	20	13	12	13	13	16	13
FIR1	45	16	25	16	14	17	19	17	17
JPEG-SD	37	16	27	16	18	17	20	18	18
MESA-PF	47	29	27	26	25	24	27	23	26
EPIC	48	49	40	32	31	33	32	38	35

Table 9

Results for the Power objective function, showing the average value of all PF individuals; bold indicates the best

DFG	ASAP	ALAP	Random	NSGA-II	FEMO	HYPE	IBEA	SPEA2	WSGA
HAL	5.933621	4.374913	5.460294	3.895405	3.895405	3.895405	3.895405	3.895405	4.374913
MESA-HB	4.844874	4.006735	4.392948	3.696173	3.696173	3.696173	3.714496	3.714496	4.05562
ARF	3.52241	3.263797	3.420271	2.829935	2.829619	2.898128	2.852638	2.880905	2.916196
MPEG-MV	7.50114	3.884491	6.410952	3.591475	3.471666	3.473344	3.516199	3.663037	3.665145
EWF	2.530418	2.671332	2.649668	2.352566	2.36479	2.360603	2.362924	2.357652	2.462942
FIR2	10.657209	3.848329	5.017662	4.064565	3.910508	4.121267	4.129263	4.209605	4.170036
FIR1	26.768005	3.874286	7.296348	4.367241	3.928351	4.053657	4.263425	4.299739	4.1565
JPEG-SD	3.880019	2.912878	3.496817	3.058184	3.081919	3.059664	3.055507	3.038939	3.107276
MESA-PF	7.131594	4.544863	6.547613	4.62266	4.210181	4.591817	4.666459	4.700996	4.779345
EPIC	8.296047	11.229858	7.411012	6.446939	6.443783	6.514232	6.528847	6.494955	7.335435

Table 10

Improvement of Area and Power respect basic scheduling algorithms

DFG	Area improvement	Power improvement
HAL	10.00%	10.96%
MESA-HB	22.22%	7.75%
ARF	21.43%	13.30%
MPEG-MV	31.58%	10.63%
EWF	5.56%	7.03%
FIR2	0.00%	0.00%
FIR1	12.50%	0.00%
JPEG-SD	0.00%	0.00%
MESA-PF	14.82%	7.36%
EPIC	22.50%	13.05%
Average	14.06%	7.01%

In Fig. 15 is shown the runtimes for the EWF problem in Intel Xeon CPU 2.80 GHz and RAM memory of 8.00 Gb.

The schedules are converted into VHDL code, these codes were estimated in terms of Area with the Xilinx ISE Design Suite. Comparisons of the six MOEAs were performed with the three basic scheduling algorithms, in order to measure whether the improvements achieved with the DFG estimates are similar to those calculated by the Xilinx ISE Design Suite. Table 11 shows the results regarding the Area occupied given by Slice Registers (FlipFlops + Latches). No data is presented in the case of ALAP with MESA-HB because the Xilinx ISE Design Suite marks an error. Bold is the best result for each problem.

An average improvement of 14.95% is obtained in Area. The reduction achieved with DFG estimators is similar to what is calculated by the Xilinx ISE Design Suite. Each PF contains a set of individuals and it is necessary that one of them is selected to be submitted to the next optimization stage. For this reason, an individual was randomly selected from each PF.

6.2. Results of the second optimization process

The optimized VHDL code was implemented with the Xilinx ISE Design Suite. The resulting netlist is exported to edif format and imported into Matlab with the help of the BYU EDIF tool [7]. The circuit is converted into simple gates and simplified using the ABC tool [1]. Circuit exchange between ABC and Matlab is performed using the aiger format [2]. Then technology mapping with IMap is performed and the mapping solution is exported to edif format. Finally, edif format is imported to the Xilinx ISE Design Suite for further testing. In Fig. 16 an example of a simulation with the Xilinx ISE Design Suite is observed corresponding to the MESA-FP problem with IBEA. Then, in Fig. 17 is presented the simulation of IBEA optimized and LUT optimized in the same problem. It can seen that both have the same behavior.

Fig. 14.

Example of PF obtained by NSGA-II for EWF problem.

Fig. 15.

Time (in seconds) measurements for the EWF circuit (34 nodes).

Table 11

Results of Area Slice Registers (FlipFlops + Latches)

DFG	ASAP	ALAP	Random	NSGA-II	FEMO	HYPE	IBEA	SPEA2	WSGA	Improvement
HAL	27	26	21	18	18	18	18	18	24	14.29%
MESA-HB	28	–	26	21	21	21	23	23	27	19.23%
ARF	41	45	41	35	35	37	37	37	37	14.63%
MPEG-MV	68	53	68	43	36	37	43	39	38	32.08%
EWF	48	59	46	38	38	37	38	48	48	19.57%
FIR2	41	25	51	40	35	45	40	40	39	0.00%
FIR1	63	45	61	60	52	51	55	56	52	0.00%
JPEG-SD	82	47	79	53	60	52	52	60	57	0.00%
MESA-PF	87	63	86	72	53	62	65	63	71	15.87%
EPIC	101	107	65	47	56	51	43	53	67	33.85%

Fig. 16.

Simulation of IBEA optimized MESA-FP circuit.

Fig. 17.

Simulation of IBEA optimized and LUT optimized MESA-FP circuit.

Next, we present results of applying the LUTs optimization on 10 benchmark problems in Table 12, Table 13, Table 14, Table 15, Table 16, Table 17, Table 18, Table 19, Table 20 and Table 21. Bold values means a decreased amount of LUTs relative to the original circuit. In each table, a different problem is presented. Each row of the tables represents a circuit in VHDL code generated automatically after the first optimization process, corresponding to the six MOEAs applied. The original and the optimized columns represent the amount of LUTs estimated for each circuit by the Xilinx ISE Design Suite. The other two columns represent the difference of the LUTs amount and the average improvement of the circuit optimized with respect to the original version (without LUTs optimization).

The results show that the process obtains a 60% reduction of total circuits with LUTs occupied, compared with the results obtained with the Xilinx ISE Design Suite.

7. Conclusions and future work

Applying two consecutive optimizations in circuit design for FPGA devices can be advantageous. As a first optimization, we apply several MOEAs for the HLS stage. As the second optimization, we realize reductions of LUTs in Logic Synthesis stage using the IMap algorithm. In the first optimization, it is feasible to use MOEAs to find better schedules than the basic schedules. With an average improvement of 14.06% in terms of Area occupied and 7.01% in terms of Power consumption. Furthermore, it was observed that the quality of obtained solutions for each metaheuristic algorithm is similar. Although it is important to note SPEA2 and NSGA-II are better in comparison with the rest of the algorithms. The WSGA algorithm has a weak selection process (uni-objective) and does not achieves the quality of the other algorithms. In the second optimization, the results of Area minimization in LUT-based FPGA technology mapping was positive. Results obtained a 60% of the circuits with reduction in the amount of LUTs occupied, compared with the Xilinx ISE Design Suite. The ARF problem is an example of the effectiveness of applying both optimizations consecutively. Initially, when ARF is optimized by the MOEA-FEMO, 14.63% reduction in terms of Slice Registers (FlipFlops + Latches) is obtained. Then, when ARF is optimized by the IMap algorithm, 6.99% reduction in terms of LUTs is obtained.

In future work, we want to measure the search operators (crossover and mutation) to determine if they are suitable for such problems or if better search operators can be applied. Also, parallelization of the optimizations should reduce runtimes. Besides, we are interested to review other approaches for estimating the objective functions. In addition, we want to do the experiments with the Xilinx Vivado Design Suite and we want to evaluate our approach on several FPGA devices.

Table 12

LUTs optimization on HAL problem

DFG/MOEA	Original	Optimized	Difference	Improvement
HAL/FEMO	74	73	−1	1.35%
HAL/HypE	74	73	−1	1.35%
HAL/IBEA	74	73	−1	1.35%
HAL/NSGA-II	74	72	−2	2.70%
HAL/SPEA2	74	73	−1	1.35%
HAL/WSGA	58	61	3	−5.17%

Table 13

LUTs optimization on MESA-HB problem

DFG/MOEA	Original	Optimized	Difference	Improvement
MESA-HB/FEMO	119	111	$- 8$	6.72%
MESA-HB/HypE	119	113	$- 6$	5.04%
MESA-HB/IBEA	127	121	$- 6$	4.72%
MESA-HB/NSGA-II	119	111	$- 8$	6.72%
MESA-HB/SPEA2	127	121	$- 6$	4.72%
MESA-HB/WSGA	120	115	$- 5$	4.17%

Table 14

LUTs optimization on ARF problem

DFG/MOEA	Original	Optimized	Difference	Improvement
ARF/FEMO	186	173	−13	6.99%
ARF/HypE	195	189	−6	3.08%
ARF/IBEA	200	186	−14	7.00%
ARF/NSGA-II	188	185	−3	1.60%
ARF/SPEA2	163	159	−4	2.45%
ARF/WSGA	192	191	−1	0.52%

Table 15

LUTs optimization on MPEG-MV problem

DFG/MOEA	Original	Optimized	Difference	Improvement
MPEG-MV/FEMO	188	197	9	$- 4.79 %$
MPEG-MV/HypE	192	200	8	$- 4.17 %$
MPEG-MV/IBEA	212	215	3	$- 1.42 %$
MPEG-MV/NSGA-II	194	208	14	$- 7.22 %$
MPEG-MV/SPEA2	196	204	8	$- 4.08 %$
MPEG-MV/WSGA	198	200	2	$- 1.01 %$

Table 16

LUTs optimization on EWF problem

DFG/MOEA	Original	Optimized	Difference	Improvement
EWF/FEMO	247	256	9	$- 3.64 %$
EWF/HypE	239	241	2	$- 0.84 %$
EWF/IBEA	250	253	3	$- 1.20 %$
EWF/NSGA-II	230	238	8	$- 3.48 %$
EWF/SPEA2	253	259	6	$- 2.37 %$
EWF/WSGA	242	251	9	$- 3.72 %$

Table 17

LUTs optimization on FIR2 problem

DFG/MOEA	Original	Optimized	Difference	Improvement
FIR2/FEMO	151	156	5	−3.31%
FIR2/HypE	201	199	−2	1.00%
FIR2/IBEA	181	177	−4	2.21%
FIR2/NSGA-II	199	203	4	−2.01%
FIR2/SPEA2	196	191	−5	2.55%
FIR2/WSGA	197	196	−1	0.51%

Table 18

LUTs optimization on FIR1 problem

DFG/MOEA	Original	Optimized	Difference	Improvement
FIR1/FEMO	232	219	−13	5.60%
FIR1/HypE	190	181	−9	4.74%
FIR1/IBEA	216	201	−15	6.94%
FIR1/NSGA-II	220	213	−7	3.18%
FIR1/SPEA2	220	217	−3	1.36%
FIR1/WSGA	242	234	−8	3.31%

Table 19

LUTs optimization on JPEG-SD problem

DFG/MOEA	Original	Optimized	Difference	Improvement
JPEG-SD/FEMO	281	290	9	−3.20%
JPEG-SD/HypE	319	327	8	−2.51%
JPEG-SD/IBEA	286	299	13	−4.55%
JPEG-SD/NSGA-II	329	325	−4	1.22%
JPEG-SD/SPEA2	297	292	−5	1.68%
JPEG-SD/WSGA	288	290	2	−0.69%

Table 20

LUTs optimization on MESA-PF problem

DFG/MOEA	Original	Optimized	Difference	Improvement
MESA-FP/FEMO	296	307	11	−3.72%
MESA-FP/HypE	283	276	−7	2.47%
MESA-FP/IBEA	340	323	−17	5.00%
MESA-FP/NSGA-II	324	308	−16	4.94%
MESA-FP/SPEA2	290	286	−4	1.38%
MESA-FP/WSGA	325	309	−16	4.92%

Table 21

LUTs optimization on EPIC problem

DFG/MOEA	Original	Optimized	Difference	Improvement
EPIC/FEMO	360	338	−22	6.11%
EPIC/HypE	320	332	12	−3.75%
EPIC/IBEA	334	332	−2	0.60%
EPIC/NSGA-II	343	367	24	−7.00%
EPIC/SPEA2	347	364	17	−4.90%
EPIC/WSGA	327	328	1	−0.31%

Footnotes

Acknowledgements

The authors acknowledge the support of CONACYT, PRODEP with the project ITTIJ-PTC-007, Tecnológico Nacional de México with the project 5861.16-P and CONACYT with the project No. 9444, Aprendizaje evolutivo a gran escala, Fronteras de la Ciencia 2015-2.

References

ABC: A system for sequential synthesis and verification, available in http://people.eecs.berkeley.edu/~alanmi/abc/ (consulted on 06-19-2016).

AIGER, available in http://fmv.jku.at/aiger/ (consulted on 06-19-2016).

Bader, Hypervolume-based search for multiobjective optimization: Theory and methods, PhD thesis, ETH, Zurich, Switzerland, 2010.

M.C.

Bhuvaneswari, Application of Evolutionary Algorithms for Multi-Objective Optimization in VLSI and Embedded Systems, 1th edn, Springer India, 2015.

Bleuler,

Laumanns,

Thiele and

Zitzler, PISA, available in http://www.tik.ee.ethz.ch/sop/pisa/ (consulted on 05-31-2016).

Bleuler,

Laumanns,

Thiele and

Zitzler, PISA – A platform and programming language independent interface for search algorithms, in: Evolutionary Multi-Criterion Optimization (EMO 2003),

C.M.

Fonseca,

P.J.

Fleming,

Zitzler,

Deb and

Thiele, eds, Lecture Notes in Computer Science, Springer, Berlin, 2003, pp. 494–508. doi:10.1007/3-540-36970-8_35.

BYU EDIF tools, available in https://sourceforge.net/projects/byuediftools/ (consulted on 06-19-2016).

Ceballos,

Juan and

Ferney, Prototipo de ascensor en VHDL, Technical report, Escuela Colombiana de Carreras Industriales, Colombia, 2014.

Chen and

Cong, DAOMap: A depth-optimal area optimization mapping algorithm for FPGA designs, in: Proc. IEEE Int. Conf. Comput, 2004, pp. 752–759.

10.

Cong and

Y.-Y.

Hwang, Simultaneous depth and area minimization in LUT-based FGPA mapping, in: Proc. ACM Int. Symp. FPGAs, 1995, pp. 68–74.

11.

Cong,

Peck and

Ding, RASP: A general logic synthesis system for SRAM-based FPGAs, in: Proc. ACM Int. Symp. FPGAs, 1996, pp. 137–143.

12.

De Micheli, Synthesis and Optimization of Digital Circuits, Electrical and Computer Engineering Series, McGraw-Hill, 1994.

13.

Deb, Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, New York, 2001.

14.

Deb,

Pratap,

Agarwal and

Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6 (2002), 182–197. doi:10.1109/4235.996017.

15.

Deb and

Srinivas, Multiobjective optimization using nondominated sorting in genetic algorithms, Evolutionary Computation 2 (1994), 221–248. doi:10.1162/evco.1994.2.3.221.

16.

Gerez, Algorithms for VLSI Design Automation, Wiley, New York, 2000.

17.

M.P.

Hansen and

Jaszkiewicz, Evaluating the quality of approximations to the non-dominated set, Technical report, Technical University of Denmark, 1999.

18.

D.S.

Harish Ram,

M.C.

Bhuvaneswari and

S.S.

Prabhu, A novel framework for applying multiobjective GA and PSO based approaches for simultaneous area, delay, and power optimization in high level synthesis of datapaths, VLSI Design Journal 2012 (2012), Article ID 273276.

19.

D.S.

Harish Ram,

M.C.

Bhuvaneswari and

Umadevi, Improved low power FPGA binding of datapaths from data flow graphs with NSGA II-based schedule selection, Advances in Electrical and Computer Engineering 13 (2013), 85–92.

20.

Jerraya,

Kission,

Ding and

Rahmouni, Behavioral Synthesis and Component Reuse with VHDL, Kluwer Academic Publishers, New York, 1997.

21.

Kapoulkine, Pugixml 1.7, available in http://pugixml.org (consulted on 05-31-2016).

22.

Krishnan and

Katkoori, A genetic algorithm for the design space exploration of datapaths during high-level synthesis, IEEE Transactions on Evolutionary Computation 10(3) (2006), 213–229. doi:10.1109/TEVC.2005.860764.

23.

F.J.

Kurdahi and

A.C.

Parker, REAL: A program for register allocation, in: 24th Conference on Design Automation, 1987, pp. 210–215.

24.

Laguna and

Delgado, Introducción a los metaheurísticos, Technical report, Valencia University, Spain, 2007.

25.

Laumanns,

Thiele,

Zitzler,

Welzl and

Deb, Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem, in: Parallel Problem Solving from Nature – PPSN VII, 2002.

26.

Lee,

Potkonjak and

Mangione-Smith, Benchmark Mediabench, available in http://express.ece.ucsb.edu/benchmark/ (consulted on 05-31-2016).

27.

Lee,

Potkonjak and

Mangione-Smith, Mediabench: A tool for evaluating and synthesizing multimedia and communications systems, in: International Symposium on Microarchitecture, 1997, pp. 330–335.

28.

Manohararajah,

S.D.

Brown and

Vranesic, Heuristics for area minimization in LUT-based FPGA technology mapping, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25 (2006), 2331–2340. doi:10.1109/TCAD.2006.882119.

29.

J.C.

Molina Gómez, Problema de optimización de rutas de vehículos con aspectos medioambientales, Master’s thesis, Universidad de Sevilla, 2013.

30.

E.F.

Moore, Gedanken-Experiments on Sequential Machines, Annals of Mathematics Studies, Princeton University Press, 1956.

31.

Quan, Introduction to data flow graphs and their scheduling sources, available in http://web.cecs.pdx.edu/~mperkows/temp/JULY/data-flow-graph.pdf (consulted on 05-31-2016).

32.

Shahir and

Zakaria, Design and implementation of elevator controller on a FPGA, Technical report, University Technical Malaysia Melaka, Malaysia, 2012.

33.

E.-G.

Talbi, Metaheuristics, 1th edn, Wiley, 2009.

34.

J.H.

Tapia, Herramienta de síntesis de alto nivel para sistemas digitales, Master’s thesis, Centro de Investigación y Estudios Avanzados del I.P.N., 2013.

35.

D.E.

Thomas,

E.D.

Lagnese,

J.A.

Nestor,

J.V.

Rajan,

R.L.

Blackburn and

R.A.

Walker, Algorithmic and Register-Transfer Level Synthesis: The System Architect’s Workbench, Kluwer Academic Publishers, Norwell, MA, 1989.

36.

Wang,

Gong,

DeRenzi and

Kastner, Ant colony optimizations for resource- and timing-constrained operation scheduling, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 16 (2007), 1010–1029. doi:10.1109/TCAD.2006.885829.

37.

Xilinx ISE Design Suite, available in http://www.xilinx.com/products/design-tools/ise-design-suite.html (consulted on 05-31-2016).

38.

Xilinx Vivado Design Suite, available in http://www.xilinx.com/products/design-tools/vivado.html (consulted on 05-31-2016).

39.

yEd graph editor, available in http://www.yworks.com/products/yed (consulted on 05-31-2016).

40.

Zitzler,

Deb and

Thiele, Comparison of multiobjective evolutionary algorithms: Empirical results, Evolutionary Computation 8 (2000), 173–195. doi:10.1162/106365600568202.

41.

Zitzler and

Künzli, Indicator-based selection in multiobjective search, in: Parallel Problem Solving from Nature – PPSN VIII, 2004, pp. 832–842.

42.

Zitzler,

Laumanns and

Thiele, SPEA2: Improving the strength Pareto evolutionary algorithm, Technical report, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland, 2001.

43.

Zitzler,

Thiele,

Laumanns,

C.M.

Fonseca and

V.G.

da Fonseca, Performance assessment of multiobjective optimizers: An analysis and review, IEEE Transactions on Evolutionary Computation 7 (2003), 117–132. doi:10.1109/TEVC.2003.810758.

High-Level Synthesis through metaheuristics and LUTs optimization in FPGA devices

Abstract

Keywords

1. Introduction

2.1. Previous work on High-Level Synthesis

2.2. Previous work on LUTs optimization

3. Background

3.1. Data Flow Graph

3.2. Mediabench benchmark

4.1. HLS as a multi-objective problem

5. Second optimization process: LUTs optimization

5.3. Iterative technology-mapping algorithm

5.4. Overview

5.6. Forward traversal

5.7. Backward traversal

6. Results

6.1. Results of the first optimization process

Table 3 The MOEAs experimental parameters Parameter Value Number of runs 10 Population size 50 Number of generations 50 Number of evaluations 2500 Objective functions 3 Selectors 6 Variators 1 Quality indicators 3 Crossover probability 0.9 Mutation probability 0.2

Footnotes

Acknowledgements

References

Table 3
The MOEAs experimental parameters

Parameter Value

Number of runs 10

Population size 50

Number of generations 50

Number of evaluations 2500

Objective functions 3

Selectors 6

Variators 1

Quality indicators 3

Crossover probability 0.9

Mutation probability 0.2