Abstract Using Genetic Algorithm for High-Level Synthesis

Using Genetic Algorithm for High-Level Synthesis

Soheil Aminzadeh

School of Electrical and Computer Engineering, University of Tehran

Tehran, Iran

s.aminzadeh@ece.ut.ac.ir

Abstract

The main contribution of this paper is using bio-inspired algorithms for high-level synthesis. There are number of heuristic algorithms for digital circuit synthesis, which can solve scheduling and binding problems, but these algorithms are time consuming for large designs and they cannot consider several constraints simultaneously. In this paper three genetic algorithms (GA) are developed to solve scheduling, module binding and register allocation problems, and then a co-evolutionary strategy merges the result of these three solutions, targeting improvement of design parameters.

1. Introduction

Advances in VLSI technology and proceeding to deep sub-micron technologies, have complicated the synthesis parameters. Conventional synthesis algorithms were designed to optimize the area and delay of synthesized circuit. Today some new design parameters optimization such as power consumption and testability optimization are of importance.

High-level synthesis is concerned with the design and implementation of circuits from a behavioral description subject to a set of goals and constraints [1]. Two main tasks perform in high level synthesis, scheduling and mapping. Scheduling assigns operations to clock cycles and resources allocation or mapping is concerned with assigning operations and variables to hardware. During allocation, registers are allocated to store variables, operations assigned to functional units, and connections which are multiplexers, busses, or a combination of both, are used for interconnection [2]. As scheduling and mapping are co.-related problems, the methods which solve them sequentially may not always provide the optimal solutions. For optimal results, these two problems must be considered simultaneously. Several optimization techniques can be used for this purpose such as integer.-linear programming (ILP) formulation, simulated annealing, and stochastic evolution. These solutions may not be optimal and the runtime become unacceptable as the problem size increases [3].

Bio-inspired algorithms such as ant colony, neural network and genetic algorithms are the other approaches that can be used as synthesis techniques. This paper uses genetic algorithm to provide the ability of solving both problems concurrently. One of the advantages of genetic algorithm is reduction in the time to obtain optimal solution. It is also a general purpose solving method that can be used in a wide class of problems. Although genetic algorithm is not guarantee that always gives the optimum solution but it usually gives an approximately good solution in surprisingly short time.

Next part will be overview of some basic concepts such as, high-level synthesis and genetic algorithms. Section 3 introduces the proposed genetic-based scheduling, module binding, and registers allocation. Section 4 presents some experimental results, and finally the last section concludes the work.

2. Basic Concepts

2.1. High-Level Synthesis

The behavior of a circuit can be specified using a high-level hardware description language, and it should be translated into a suitable intermediate format, e.g. a flow graph. In the behavioral specification, a basic block is defined as a straight line sequence of statements that contains no branches [4]. Hence, a data flow graph (DFG) can be derived from the basic block where each node is associated with an operation and each arc is associated with a variable. Data dependency is implied by the direction of an arc. Figure 1(a) shows a simple example of a basic block with three statements, and figure 1(b) shows its corresponding DFG.

As mentioned before, there are two major tasks in high.-level synthesis, i.e. scheduling and allocation. Scheduling determines the execution order of operations, while allocation assigns hardware to perform the operations. In general, both scheduling and binding are https://www.wendangku.net/doc/0317632517.html,plete problems. Therefore, there are a number of

heuristics developed to obtain optimal or nearly optimal solutions by coping with each of them

separately.

(a) (b)

Figure 1. (a) Sample of behavioral code, (b)

Corresponding DFG

A. Scheduling

Scheduling assigns each operation to one or

more clock cycles, and specifies cycle-by-cycle

behavior of a circuit. The result of scheduling is

called scheduled DFG (SDFG). For an operation

o in DFG, o-earliest and o-latest denotes the

earliest and latest possible cycle time, which o

can executed in, respectively. The number of

predecessors in DFG determines the o-earliest,

but o-latest depends on user defined maximum

latency. Figure 2(a), shows a sample DFG,

suppose that each operation has one cycle delay

and the maximum desired latency is four clock

cycles. Table in figure 2(b) shows the earliest

and the latest time for scheduling of each

operation. As mentioned before, there are

number of heuristic deterministic algorithms for

scheduling, such as ASAP (As Soon As

Possible), ALAP (As Late As Possible), List

Scheduling and Force-Directed Scheduling.

These algorithms are described completely in

[4].

B. Resource Allocation

Given a scheduled DFG, resource allocation

assigns hardware elements like registers to store

values, functional unit to perform operations, and

interconnections to carry signals, to produce a

register transfer level architecture [4].

A constructive algorithm proposed by Kurdahi

[4] showed that greedy Left Edge Algorithm

(LEA) originally used for the channel routing

problem can be applied to allocate the minimum

number of registers and functional units for an

acyclic SDFG. There are also number of graph

theoretic approaches to solve the resource

allocation problem, such as clique partitioning

and bipartite matching. Some of these problems

are originally NP-complete, but some

polynomial heuristic algorithms exist for solving

them approximately [4].

(a)

(b)

Figure 2. (a) Sample DFG, (b) earliest and latest possible

time for scheduling

2.2. Genetic Algorithm

This part, introduce genetic algorithm as an

evolutionary computation technique. Genetic

algorithm is a class of probabilistic optimization

algorithms, which are inspired by biological

evolution process, and use the concepts of

Natural selection and genetic inheritance of

Darwin (1859). These algorithms were

introduced first time by John Holland [5].

Genetic algorithm is particularly useful for hard

problems where little is known about the

underlying search space. Although genetic

algorithm is not guarantee that always gives the

optimum solution but it usually gives an

approximately good solution in a short time.

For solving problems using genetic algorithm, a

set of possible solutions are forming initial

chromosomes population. Specification of how

optimum of each solution is done by giving a

numerical amount, called fitness, to each

member of population. A Genetic algorithm

maintains a population of candidate solutions for

the problem at hand, and makes it evolve by

applying a set of stochastic operators [5]. Some

of these stochastic operators are described below.

?Selection: replicates the most

successful solutions found in

population at the rate proportional to

their relative quality.

?Recombination: decompose two

distinct solutions and then randomly

mixes their parts to form novel

solutions.

?Mutation: randomly perturbs a

candidate solution.

Genetic Algorithm Nature Optimization problem Environment

Feasible solutions Individuals living in that

environment

Solutions quality (fitness function) Individual’s degree of adaptation to its surrounding environment

A set of feasible solution A population of organisms

(species)

Stochastic operators Selection, recombination

and mutation in nature

evolutionary process

Iteratively applying a set of stochastic operators on a set of feasible solutions Evolutions of populations to suit their environment

Table 1. A Metaphor between genetic algorithm and nature

[5]

3. Using Genetic Algorithm in High-Level Synthesis

As pointed before, first step in solving a problem, using genetic algorithm, is modeling solutions with a population of chromosomes, and then defining fitness to each chromosome according to its closeness to optimum solution. Next step is applying stochastic operators to this population and creating new generations of chromosomes. It has proved that generations gradually converge to optimum solutions [5].

In this paper for solving synthesis problem with genetic algorithm, three genetic algorithms are implemented.

One of these genetic algorithms is used for DFG scheduling. In this genetic algorithm, chromosomes are integer arrays, such that the length of arrays is equal to the number of DFG nodes and S[i] = j means, the i th node is scheduled at j th cycle. The initial population for this problem is the number of chromosomes of genes. Each gene is a random integer value between ASAP and ALAP time of corresponding node.

In this problem, fitness evaluator gives better fitness to the chromosome with better latency, so the last generation contains numbers of SDFG1s, which are good from the latency point of view. Other genetic algorithms are used for hardware allocation for a given SDFG. One of them allocates functional units for each node and the other one, maps each variable of SDFG to a register. Chromosomes of both genetic algorithms are integer arrays. The lengths of module allocation chromosomes are equal to the number of nodes of SDFG, and this length in register allocation problem is equal to number of variables. In these problems fitness evaluator defines fitness of the chromosomes according to their area overhead, which means the lower the area overhead, the larger the fitness is.

The results of these three problems contain the number of possible synthesis results, which are all optimum from the point of view of delay and area overhead.

As mentioned before, the best synthesis result from the delay and area point of view may not be the best result for low power consumption, testability or other synthesis parameters.

Here we propose a co-evolutionary algorithm to merge the results of evolutionary problems to each other, targeting improvement of synthesis parameters. This algorithm gets a number of the results of scheduling and hardware allocation, which are all suboptimum. Co-Evolutionary algorithms choose one of each that maximizes Equation 1.

F = ∑λi(pi)αi (Equation 1)

Where pi is a synthesis parameter. With the proper choice of λis and αis, the proper weight can be provided for pi, according to the synthesis target.

4. Experimental Results

This section reports the results of our experiments on effect of changing some of genetic algorithm parameters such as mutation rate and crossover rate on the synthesis result. Our results based on “UTS” [6] a new synthesis tool, which is designed and implemented by students of University of Tehran.

UTS is implemented in JAVA platform. It builds DFG from Verilog input files and then it performs scheduling and binding with selected algorithms. Some of the heuristic algorithms for scheduling and binding are implemented in UTS.

It also contains a built-in GA package which can be used to solve the optimization problems.

1 Scheduled Data Flow Graph

Mutation: Standard mutation operators randomly modify the individual genes in the chromosome to produce genes with a different value [2]. UTS GA Package implements such a mutation. In our experiment the mutation is

performed in each five generations period, which means in after each five generations a random number of chromosomes between 0 to 30% of the population can be mutate.

Crossover : Conventional evolutionary crossover combines the characteristics of two parent chromosomes to produce child chromosomes with different, hopefully better characteristics. The crossover operation can be performed in three models. In the first model, one gene is selected from two chromosomes randomly and values are exchanged. In the second model, two chromosomes from a randomly selected position are combined. In the third model, values of all peer.to.peer genes in two chromosomes are exchanged. In fact, to ensure randomness of the operation, first, the chromosomes of the population are shuffled and then crossover operator is performed on every two chromosomes of population. UTS GA package one point crossover is implemented (second model) and in each generation, a random number of chromosomes, between 0 and 40% of population are selected to perform crossover. Selection: UTS performs fitness proportionate selection with roulette wheel method. It means that individual i has a probability

to be chosen. Figure 3 shows this method. ∑j

j f i f )(/

)(

Figure 3. roulette wheel method for selection in UTS

Figure 4, 5, and 6, shows the diagrams of population average fitness for scheduling, module binding and register binding in some of

the run samples of genetic algorithms.

Figure 4. Convergence of average fitness for GA

scheduling

Figure 5. Convergence of average fitness for GA module

binding

Figure 6. Convergence of average fitness for GA registers

Allocation

Figure 6 shows that register binding was trapped in a local optimum but a mutation reclaim it and then it converged to actual global optimum.

5. Conclusion and Future Work

This paper introduced genetic algorithm and gives a new approach to use this technique in high-level synthesis. It also offers the use of co-evolutionary strategy to improve other parameter of synthesis.

Researchers at University of Tehran are working on improvement of other parameters of synthesis, such as testability.

Acknowledgement

Especial thanks to Dr. Saeed Safari for helpful discussion and comments on this work.

References

[1] M. C. McFarland, A. C. Parker, and R. Camposano, “The High.Level Synthesis of Digital Systems,” Proc. of the IEEE, vol. 78, No. 2, pp.310.318, Feb 1990.

[2] A. Banaiyan, H. Esmaeelzadeh, and S. Safari, “Co.Evolutionary Scheduling and Mapping for High.Level Test Synthesis”, IEEE ICEIS’06, Islamabad, Pakistan, pp. 269.273, Apr. 2006.

[3] S. Devadas and A. Richard Newton, “Algorithms for hardware allocation in data path synthesis,” IEEE Transactions on Computer.Aided Design, pp. 768.781, 1989.

[4] Mike Tien, Chien Lee, High Level Test Synthesis of Digital VLSI Circuits, Artech House Press, 1997.

[5] “Introduction to Genetic Algorithms”, available on http://ece.ut.ac.ir/classpages/

[6] University of Tehran Synthesis Tool (Version 0.9) design and implement by Soheil Aminzadeh in University of Tehran, Tehran.Iran (s.aminzadeh@ece.ut.ac.ir )