SOURCE ARCHIVE
EXTRACTED CONTENT
116,842 chars52 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 20, NO. 1, JANUARY 2012
FISH: Fast Instruction SyntHesis for Custom Processors Kubilay Atasu, Member, IEEE, Wayne Luk, Fellow, IEEE, Oskar Mencer, Member, IEEE, Can Özturan, and Günhan Dündar
Abstract—This paper presents Fast Instruction SyntHesis Combining programmability and efficiency, custom instruc-
(FISH), a system that supports automatic generation of custom tion processors are emerging as key building blocks in the instruction processors from high-level application descriptions design of complex SoCs. The typical approach extends a base to enable fast design space exploration. FISH is based on novel methods for automatically adapting the instruction set to match processor with custom functional units that implement appli- an application in a high-level language such as C or C . FISH cation-specific instructions [2]–[4]. A dedicated link between identifies custom instruction candidates using two approaches: the custom functional units and the base processor provides an
- by enumerating maximal convex subgraphs of application efficient communication interface. Reusing a preverified, pre- data flow graphs and 2) by integer linear programming (ILP). optimized base processor reduces design complexity and time The experiments, involving ten multimedia and cryptography benchmarks, show that our contributed algorithms are the fastest to market. Commercial examples include Tensilica Xtensa, among the state-of-the-art techniques. In most cases, enumera- ARC 700, Altera Nios II, MIPS Pro Series, Xilinx MicroBlaze, tion takes only milliseconds to execute. The longest enumeration Stretch S6000, and IBM’s PowerPC® 405. run-time observed is less than six seconds. ILP is usually slower Modern custom instruction processors comprise parallel, than enumeration, but provides us with a complementary solution deeply pipelined custom functional units including state regis- technique. Both enumeration and ILP allow the use of multiple different merit functions in the evaluation of data-flow subgraphs. ters, local memories, and wide data buses to local and global The experiments demonstrate that, using only modest additional memories and provide support for flexible instruction encoding hardware resources, up to 30-fold performance improvement can [5]. These features enable custom processors to reach a compu- be obtained with respect to a single-issue base processor. tational performance comparable to the performance of custom Index Terms—Custom processors, design automation, design op- register transfer-level blocks. On the other hand, such advances timization, graph theory, mathematical programming, subgraph necessitate improved design automation methodologies that enumeration, system-on-chip (SoC). can take advantage of the new capabilities. Techniques for the automated synthesis of custom instruc- I. INTRODUCTION tions from high-level application descriptions have received much attention in recent years. Typically, compiler infrastruc-
T HE complexity of system-on-chip (SoC) devices is in- tures are used to extract the source-level data flow graphs creasing continuously. The competitive end-market re- (DFGs), and data flow subgraphs are evaluated as custom quires the design of more versatile systems with more hardware instruction candidates. This is followed by the synthesis of the and software resources in shorter time. Today, a major problem customized hardware and software components (see Fig. 1). in SoC design is the limited designer productivity in comparison The traditional subgraph exploration approach restricts the with the growth in hardware complexity [1]. This phenomenon maximum number of input and output operands that custom necessitates new approaches in the design of complex SoCs. instructions can have to the available register file ports [6]–[13]. First, the new generation of SoCs should be sufficiently pro- Although these constraints can be prohibitive on some cus- grammable in order to amortize chip design costs. Second, there tomizable processors, most existing architectures—such as is a need for optimizations of the performance, area, and power Tensilica Xtensa—allow custom instructions to have more efficiency of SoC designs for specific applications. input and output operands than the available register file ports, typically through custom state registers that can tem- Manuscript received March 02, 2010; revised August 25, 2010, October 25, porarily hold some of the operands. Recent work has shown 2010; accepted October 25, 2010. Date of publication December 03, 2010; date that input/output constraints deteriorate solution quality for of current version December 14, 2011. This work was supported in part by UK architectures in which there is no explicit limit on the number EPSRC and IBM Research. of custom instruction operands [14]–[18]. Thus, there is a K. Atasu is with IBM Research—Zurich, CH-8803 Ruschlikon, Switzerland need for new algorithms that can eficiently explore custom (e-mail: kat@zurich.ibm.com). O. Mencer and W. Luk are with the Department of Computing, Imperial instruction candidates without imposing a limit on the number College London, SW7 2BZ London, U.K. (e-mail: o.mencer@imperial.ac.uk; of input/output operands. w.luk@imperial.ac.uk). This paper presents effective techniques for automating the C. Özturan is with the Department of Computer Engineering, Boğaziçi Uni- versity, 80815 Istanbul, Turkey (e-mail: ozturaca@boun.edu.tr). identification of custom instructions starting with application G. Dündar is with the Department of Electrical and Electronics Engineering, descriptions in C/C . In this work, only convex subgraphs of Boğaziçi University, 80815 Istanbul, Turkey (e-mail: dundar@boun.edu.tr). application DFGs that are maximal are considered, and, while Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. generating custom instruction candidates, no constraints are Digital Object Identifier 10.1109/TVLSI.2010.2090543 imposed on the number of input and output operands. Unlike
1063-8210/$26.00 © 2010 IEEE
ATASU et al.: FISH: FAST INSTRUCTION SYNTHESIS FOR CUSTOM PROCESSORS 53
Application Descriptions tial computational complexity. A downside is that, as the con-
straints on the number of input and output operands are relaxed,
enumeration becomes computationally expensive. On the other
hand, the ILP model of [13] efficiently handles DFGs with more
than a thousand nodes under any input and output constraint,
including the option of removing these constraints completely
[15], [18]. The reason is that the number of integer variables and
i the number of linear constraints used in ILP grow linearly with
the number of nodes and the number of edges in the DFG.
In [14], a pipelining algorithm that serializes the register file
accesses when the number of inputs and the number of out-
puts of the custom instructions exceed the available register file
ports, is described. This technique relies on [6], [9] for gener-
Fig. 1. Compiler infrastructures transform high-level application descriptions ating custom instructions, which have limited scalability. In ad- into source-level control and DFGs. Data flow subgraphs are evaluated as dition, pipelining is applied on the source-level DFGs, where custom instruction candidates. A high-level merit function ranks the subgraphs it is nearly impossible to estimate the critical path accurately based on estimations of hardware and software costs. and, therefore, to find an optimal pipeline. However, this work empirically shows that achievable speed-up grows monotoni- prior work, the techniques presented in this work do not rely on cally with the relaxation of the constraints on the number of enumeration of maximal independent sets or maximal cliques. input and output operands. Similar conclusions are made also This work extends the work in [19], which describes a maximal by [15]–[18], which employ more scalable algorithms for gen- convex subgraph enumeration algorithm with a proven upper erating custom instructions. bound on the size of the search space. The enumeration algo- Pothineni et al. [16] were the first ones to target the maximal rithm of [19] is explained in more depth, and additional search convex subgraph enumeration problem. Given a DFG, Poth- space reduction techniques are demonstrated. The enumeration ineni et al. first define an incompatibility graph, where the edges approach makes it possible to integrate any merit function for represent pair-wise incompatibilities between the nodes. A node ranking the subgraphs. In addition, a new ILP formulation pro- clustering step identifies group-wise incompatibilities and re- vides a second way of finding the maximal convex subgraphs duces the size of the incompatibility graph. The incompatibility that optimize a linearly expressed merit function. The main graph representation transforms the maximal convex subgraph contributions of this work are: enumeration problem into a maximal independent set enumer- 1) an upper bound on the number of maximal convex sub- ation problem. Pothineni et al. indicate that the complexity of graphs within a given DFG (Section IV); enumeration is , where represents the number of 2) an integer linear programming formulation for evaluating nodes in the incompatibility graph. Although Pothineni et al. maximal convex subgraphs (Section V); apply enumeration independently on the connected components 3) a maximal convex subgraph enumeration algorithm for of a DFG, the disconnected subgraphs within each connected custom instruction synthesis that includes novel clustering component are enumerated too. and search space reduction techniques (Section VI); In [17], the maximal independent set enumeration problem of 4) evaluation of multiple different merit functions in a design [16] is reformulated as a maximal clique enumeration problem, space exploration framework (Sections VII, VIII); and enumeration is applied at once to the whole graph. Addi- 5) illustration of the scalability of our algorithms on a set of tionally, [17] describes a heuristic algorithm for pipelining the benchmarks (Section IX), where we also demonstrate an enumerated subgraphs and serializing register file accesses at order of magnitude performance improvement with respect the source level. [17] includes a formal proof, which shows to a single-issue base processor (Sections X and XI). that under certain assumptions speed-up potential of a subgraph grows monotonically with its size. II. RELATED WORK In [26], the ILP model of [13] is extended to include a re- source-constrained scheduling model for serializing the register Heuristic clustering algorithms have long been used in au- file accesses. However, the resulting model scales quadratically tomated custom instruction synthesis [20]–[24]. However, the with the size of the DFGs versus the linear scaling of [13], [15], attention gradually shifts towards techniques for producing op- and [18]. As a result, the work of [26] fails to identify optimal timal solutions, such as subgraph enumeration [6]–[12] and ILP solutions on large DFGs, although the ILP models of [13], [15], [13], [15], [18], [25], [26]. Given a DFG with N nodes, the and [18] complete optimally in all practical cases. complexity of enumerating subgraphs with Vy, input and In [28], Li et al. describe an algorithm that constructs a search output operands is shown to be [27], which tree similar to the one described in [19]. The enhancements pro- grows exponentially with the number of inputs and outputs. posed in [28] include: 1) an adaptive branch ordering mecha- A common property of the aforementioned enumeration tech- nism; 2) migration of some of the computation from the leaves niques [6]–[12] is that explicit constraints are imposed on the of the search tree to the branches, where simpler bitwise oper- number of input and output operands of the subgraphs, which ations can be used; 3) an efficient mechanism to discard sub- are used to prune the search space and reduce the exponen- graphs that are not maximal or that are repeated.
54 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 20, NO. 1, JANUARY 2012
rn not containing forbidden nodes can be encoded. The following
(Oh, indexes are used in the rest of the text:
! | I: indices for nodes v; € V — Vy
1 J: indices for nodes v; € Vy.
NO, [ The following sections use the introduced notation.
Section IV shows that the number of maximal convex sub-
graphs is bounded by for a given DFG. Section V provides
an ILP model, which evaluates all maximal convex subgraphs.
D2 Section VI describes an efficient algorithm for enumerating
maximal convex subgraphs. A user defined merit function
Fig. 2. Subgraph that is not convex. vs is a forbidden node. ranks the subgraphs as part of enumeration or ILP.
Enumeration can integrate any software function to compute
. ILP accepts linearly expressed merit functions only.
Other related and complementary work includes: 1) use IV. UPPER BOUND ON THE SEARCH SPACE SIZE
of local memories for improving the performance of custom
instructions [25], [29]; 2) datapath merging [30] and com- Here, we prove that the number of maximal convex subgraphs
binational equivalence checking [31] techniques to improve in a given DFG E) is at most .
resource sharing; 3) synthesis of custom instructions targeting For each node v we introduce two binary variables:
field-programmable systems [32], [33], including support for indicates whether has an ancestor in = or not = ,
run-time reconfiguration [34], [35]; and 4) transparent integra- and d indicates whether has a descendant in = or not
tion of custom instructions with a general-purpose processsor = . Based on Corollary 1, the convexity property can be
[36]. formulated as follows:
III. PROBLEM FORMULATION , iel (1)
We assume that the source program is converted into an in- jel (2)
termediate representation (IR), where every statement in the IR Theorem 1: A maximal subgraph that satisfies (2), satisfies
is a branch, or an assignment operation. An application basic also (1).
block is represented as a DFG , where the nodes V' Proof: Assume that (2) holds for subgraph , i.e., no node
are statements within the basic block, and the edges E repre- in has both an ancestor and a descendant in . Assume also sent flow dependencies between nodes. The subset V that S is maximal, i.e., no additional node can be included in represents forbidden statements in G that cannot be included without violating (2). We are going to show that 5 also satisfies in custom instructions, either because of the limitations of the (1). custom processor architecture, or because of the limitations of Suppose that a node V — U violates (1), i.e., the custom datapath, or due to the choice of the processor de- has both an ancestor and a descendant in . First we prove that signer. Examples may include memory access, branch, division, including in does not violate (2). We note that, in a convex and floating-point instructions. solution, there exist three possible choices for each v; € , Definition 1: A custom instruction candidate is a subgraph which are given here. of , where the nodes of the subgraph are in — , and 1) has ancestors, but no descendants in . In this case, v; the edges of the subgraph are induced by the nodes . cannot be a descendant of . If were a descendant of Definition 2: A subgraph S is convex if there exists no path in would have descendants in , since has descendants G from a node u € V; to another node w € V; which involves in . Because is not a descendant of , including v; in a node v . does not violate (2). Corollary 1: A subgraph S is convex if and only if there ex- 2) has descendants, but no ancestors in . In this case, v; ists no node in V — V, having both an ancestor and a descendant cannot be an ancestor of . If were an ancestor of in . would have ancestors in , since has ancestors in . The convexity constraint is imposed on the subgraphs to en- Because is not an ancestor of , including v; in V; does sure that no cyclic dependency is introduced in 7 and that a fea- not violate (2). sible schedule can be achieved for the instruction stream. Fig. 2 3) has neither ancestors nor descendants in . In this depicts an example subgraph that is not convex. case, is neither an ancestor nor a descendant of . Oth- Definition 3: A convex subgraph S is maximal if it cannot be erwise would have ancestors or descendants in . Thus, grown further by including additional nodes from V — . including in does not violate (2). Every graph node € is associated with a binary variable We have shown that if there exists a € V — U , which indicates whether the node is included in the subgraph that violates (1), we can safely include it in without violating = 1 © € or not (z; = 0 « . The (2). However, this contradicts the maximality of . Thus, a € complement of is denoted by = 1 — . For € that violates (1) cannot exist for the maximal satisfying a; is simply set to be zero. In this way, up to subgraphs (2).
ATASU et al.: FISH: FAST INSTRUCTION SYNTHESIS FOR CUSTOM PROCESSORS 55
TABLE I
SOLUTIONS FOR THE DFG OF FIG. 3
® (=)
@ 0 ® ®
© © ©) CQ )
Fig. 3. vs and vs are forbidden nodes.
© © @)
Based on Theorem 1, there exist only three valid aj, Fig. 4. Pothineni’s incompatibility graph. The ancestors and the descendants
choices for a fi € : 1) a; = Ld; = ; 2) a; = 0,d; = ; of a forbidden node are defined as incompatible. and 3) = = . Every maximal convex subgraph is associated with at least one valid combination for . Given a valid combination for , an associated it is possible to enumerate all maximal convex subgraphs in the convex subgraph S that cannot be grown further by including DFG in only 2” steps. additional nodes from — can be found as follows. • A node ancestor € V cannot be included in S if it has an V. AN INTEGER LINEAR PROGRAMMING MODEL • A node v; € Vy for which = . V — cannot be included in S if it has a This section describes an ILP model that addresses the opti- • descendant for which a; = . mization problem described in Section III. The objective of ILP All of the remaining nodes in can be safely included is to maximize a linearly expressed merit function . in without violating (2). The following notation introduces the set of ancestors, and To enumerate all maximal convex subgraphs, it is sufficient to the set of descendants of the nodes in VV — Vj that are in Vj: evaluate two possible choices for each J (i.e., = 1,d; = or = = ). The third choice, where = = Anc(i eI) , can be disregarded because it does not contribute to finding = {j € J| There exists a path from v; to v;} a convex subgraph of maximal size. Each combination sel for J is associated with a single subgraph S that can be Desc(i € I) computed using the procedure described above. = {Jj € J| There exists a path from v; to v;} Theorem 2: There exists an upper bound of on the number of maximal convex subgraphs. Once and values are fixed for j € , the following Proof: Mathematical induction based on the number of for- formula computes whether a node is part of the bidden nodes in . m associated convex subgraph S of maximal size Fig. 3 depicts an example DFG where nodes and are the if — forbidden nodes. Because there are two forbidden nodes in the L re 0
graph, there exist only 22 = 4 possible combinations we need to (Merny 4 if Anc(i) # 0 A Desc(i) = 0
evaluate: 1) ancestors of and ancestors of take part in the ~~ Zi = (A a) if Anc(i) = 0 A Desc(i) # 0
solution ( = = 0 and = = ); 2) ancestors of 7
and descendants of take part in the solution ( = = 4 A a) . otherwise
and = = ); 3) descendants of and ancestors of (3)
take part in the solution ( = = 1 and = = ); According to (3), a node € V — can be included in the
and 4) descendants of and descendants of take part in the solution if it has no ancestors in solution ( and ). Table I shows the descendants in for which Vj for which = 0 and no = = = = = . Four different conditions solutions associated with each of these four choices. Note that are explicitly formulated: 1) has no ancestors and no descen- nodes and are included in the solutions associated with dants in ; 2) has ancestors but no descendants in ; 3) all possible combinations because they have neither ancestors has descendants but no ancestors in ; and 4) v; has both an- nor descendants among the forbidden nodes. cestors and descendants in . Fig. 4 shows the incompatibility graph generated by Poth- Equation (3) generates convex subgraphs only. For each ineni’s algorithm [16] for the DFG of Fig. 3. The incompatibility combination, ILP computes the values for all € , which graph contains seven nodes. According to Pothineni’s work, the explicitly define a convex subgraph. Out of all such subgraphs, worst case complexity of maximal convex subgraph enumera- ILP picks the one that maximizes M . An alternative model tion for this graph is . On the other hand, we have shown that for the same problem can be found in [37, ch. 5].
56 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 20, NO. 1, JANUARY 2012
VI. NOVEL ENUMERATION ALGORITHM (@)
We have shown in Section IV that, given a graph with
forbidden nodes, there exists an upper bound of on the & 0
number of maximal convex subgraphs. Therefore, the time
complexity of the maximal convex subgraph enumeration . AN Pe ,
algorithms should not have an exponential factor higher than . Here, we describe a novel enumeration algorithm that significantly improves the run-time efficiency using additional Fig. 5. Connectivity of forbidden nodes helps us reduce the search space. search space reduction techniques. Our improvements over an exhaustive search can be categorized into two groups:
- obtaining a more compact graph representation through in the clustering of the forbidden nodes also enhances the preprocessing and clustering and 2) building a search tree and clustering of the nodes that are not forbidden. applying constraint propagation to prune the search space. The result is the clustered graph , where A. Graph Compaction denotes the set of forbidden nodes. Reducing the number of for- bidden nodes in the clustered graph (i.e., ) immediately con- 1) Basic Preprocessing: The forbidden nodes not tributes to a reduction in the exponential complexity and reduces having any ancestors in V — and the forbidden nodes the time to compute (3) as well. On the other hand, reducing the not having any descendants in V — can be dropped from number of nodes that are not forbidden in the clustered graph consideration because such nodes have no effect on the compu- (i.e., ) does not affect the exponential complexity, but tation of the maximal convex subgraphs, as shown in (3). This again reduces the time to compute (3), which is in the inner loop basic optimization often eliminates a considerable number of of our enumeration algorithms. forbidden nodes and significantly reduces the size of the search Finally, we derive a tighter upper bound on the number of space. maximal convex subgraphs using the clustered graph . 2) Simple Clustering: Following the basic preprocessing Theorem 3: There exists an upper bound of on the
step, similar to the approaches of Pothineni et al. [16] and number of maximal convex subgraphs. Verma et al. [17], we apply a node-clustering step that reduces Proof: Mathematical induction based on the number of for- the size of the DFGs. In particular, if V — and bidden nodes in G . u Anc(i) = and = , the nodes and B. Building a Search Tree can be clustered without affecting the result of enumeration because (3) guarantees that and x; will always be equal. To demonstrate further ways of reducing the complexity, we Similarly, if two forbidden nodes € Vy have the same set construct a new graph from the clustered graph of ancestors and descendants that are in V — , (3) guarantees . G" is a simplified form of , and contains only the that the two forbidden nodes can be clustered into a single node forbidden nodes of . The edges of store the connectivity without affecting the result of enumeration. information between the forbidden nodes of . More formally, 3) Enhanced Clustering: The simple clustering approach we have VV = , and a directed edge is defined between two usually does not find any forbidden nodes that can be clustered. nodes of G” only if there is a path from to that does However, reducing the number of forbidden nodes is of utmost not go through another € in . Such a simplification value as the complexity of enumeration is exponential in the is introduced to clarify our search algorithm, which reduces the number of forbidden nodes, as stated by Theorem 2. Assume search space using only the connectivity information between that two forbidden nodes € have the same set of the forbidden nodes. descendants that are in V — . Setting = 0 disables inclu- Fig. 5 illustrates a simple graph . Setting = 0 disables sion of those nodes that are descendants of in the solution. inclusion of any node that is a descendant of in the solu- However, these nodes are the descendants of , too. We can set tion. In such a case, we can simply set d; = 0 for all forbidden d; = 0 whenever d; = , and vice versa even if the ancestors of nodes that are descendants of (i.e., = = = ). In and in V — differ. As a result, we need to evaluate only other words, we do not need to explore the combinations where two choices in such a case: = and = . = 0 and at least one of is not zero. In practice, Thus, we can simply cluster the forbidden nodes having the the number of possible combinations for € V” (where same set of descendants that are in V — . Similarly, it is also = ) is much smaller than . We exploit this property possible to cluster two forbidden nodes if they have the same to design a simple and efficient algorithm for maximal convex set of ancestors that are in V — . subgraph enumeration. In this work, we first apply the basic preprocessing step. Fig. 6 shows the pseudo-code of our algorithm. We first apply Second, we cluster forbidden nodes having the same set of a node clustering step on and obtain the clustered graph . descendants that are in V — . Third, we cluster the forbidden Next, we derive G from . After that, we order the nodes nodes having the same set of ancestors that are in V — , if of topologically such that if there exists a path from to they have not already been clustered by the second step. Finally, in is associated with a lower index value than . using the graph computed by the third step, we cluster the nodes Our enumeration algorithm uses this ordering while building that are not forbidden, i.e., v; € V — . The enhancement a search tree, i.e., the nodes with lower indexes have their d;
ATASU et al.: FISH: FAST INSTRUCTION SYNTHESIS FOR CUSTOM PROCESSORS 57
1: ALGORITHM: search(index, choice, graph, disabled)
2:3: Tocal disabled = disabled: oxox 1
index == size(graph)-1 then 0 0 1
4: currentif combination|index] = choice; . .
combination; 0
65: if M(current_combination)= current> M(best_combination) then 00xx [100d 1d
78 endif 000% of “
retumn; .
9 endif
10: if¢ choice == 0 thenlocal oii £1000" eilieii e
1010 "1100" 1110 1111
11:12: endlocalif disabled = disabled U descendants(index);
13: index=index+1; Fig. 7. Search tree is built by the enumeration algorithm for the shown in
14:15: search(index,iff 0, graph, local_disabled): Fig. 5. A branch at level of the search tree assigns a zero or one value to .
index ¢ local disabled then The leaves of the search tree represent the enumerated combinations. Only
16: search(index, 1, graph, local disabled); six out of 16 combinations are enumerated for this example. The dashed ellipses
17: end if show the pruned regions of the search tree.
18: ALGORITHM: enumerate()
19: Apply preprocessing and clustering on G to generate
20: Derive G from G';
21: Topologically sort the nodes of ordering and propagate the constraints of type = . A similar
2 current combination 0 approach is described in [28], where the nodes are ordered by
24: search(0, 0, 0): estimating the remaining search space size associated with the
25: search(0, 1, G”, 0); selection of each node, and by allowing the constraints of both
26: return best.combination; types, = 0 and = , to be propagated. A disadvantage
Fig. 6. Enumeration algorithm: the best solution is defined by M(S). “cur- of this approach is the additional processing time that is spent rent combination[index]” stores the value of . The parameter “choice” for the selection of the branch node before each call to the represents the direction of the branch. Setting “choice” equal to zero disables recursive search function. the descendants of “index” in . The disabled nodes call the recursive search function only once by setting the “choice” argument equal to zero. The algo- While setting the d; value for a , our approach ef- rithm backtracks when all the nodes in are evaluated. fectively divides into two parts: 1) nodes that are ancestors of and nodes that are neither ancestors nor descen- values assigned earlier. The search tree is built using a recur- dants of and 2) nodes that are descendants of and nodes sive search function, where each node can make a zero or one that are neither ancestors nor descendants of . A similar graph branch. A zero branch on node i sets to zero, and effectively division operation is presented also in [28]. A main difference disables setting the d values to one for the descendants of node between this work and [28] is that our algorithm computes (3) i in , all of which appear later in the topological ordering. at the leaves of the search tree, whereas [28] updates an inter- When the search algorithm backtracks and sets to one, the mediate graph data structure at each branch of the search tree disabled descendants must be enabled again. This feature can using cheaper bitwise operations. be implemented using a local array or a stack. The search algo- The algorithms described in [19] and, in this work, can enu- rithm produces combinations of values. Each such combina- merate convex subgraphs that are not maximal, and the same tion is associated with a convex subgraph that can be derived subgraph can be generated multiple times. However, the clus- using (3). In this work, we keep track of the best solution only, tering techniques described in this work significantly reduce the which maximizes a given metric function M . However, our amount of redundancy. On the other hand, [28] does not incor- approach can easily be adapted to store all of the enumerated porate any clustering techniques. It is reported in [28] that the subgraphs too. algorithm of [28] does not enumerate nonmaximal subgraphs. Fig. 7 shows the combinations identified during the execu- Moreover, [28] describes an efficient way of detecting and dis- tion trace of our enumeration algorithm on the graph of Fig. 5. carding repeated subgraphs. Note that such a step is not neces- We observe that only six out of 16 possible combinations had sary for our work since our technique does not need to store all to be enumerated. In fact, the worst case scenario of 2/V"| can the enumerated subgraphs. occur only if all forbidden nodes are disconnected from each other. This is illustrated in Fig. 3, where the two forbidden VII. MERIT FUNCTIONS FOR EVALUATING SUBGRAPHS nodes result in 22 combinations. On the other hand, when the In this work, the merit function is a parameter for de- forbidden nodes in the are simply cascaded, the number of sign space exploration, and can be specified by a designer. Basi- combinations enumerated by our algorithm grows only linearly cally, defines an ordering of the subgraphs. If the objec- with the number of nodes. As a result, the enumeration com- tive of optimization is to improve processor performance, M plexity depends primarily on the number of nodes in G” and should provide an estimation of the reduction in the schedule their connectivity. length of the application by moving subgraph S from software Our enumeration algorithm uses the topological ordering to hardware. In a different setup, M can integrate area and while building the search tree, i.e., the nodes that are higher in power consumption estimations as well. the topological ordering are handled first. The constraints of The software execution latency SW of a subgraph S can type = 0 are propagated to the lower levels to reduce the be estimated by statically scheduling S using the base processor search space. However, it is possible to use other orderings as instructions. The hardware execution latency HW can be well. As an example, it is also possible to invert the topological obtained by the hardware synthesis of S and by pipelining the
58 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 20, NO. 1, JANUARY 2012
Application Synopsys
in CICH+| Synthesis Area&
Delay
Front-end | Generation _| Frequency |__Selection | Estimation
! 1
Elcor MS) M(S)
Fig. 8. We adapt the CHIPS [18] tool chain with a novel enumeration algorithm and a new ILP model for Subgraph Generation. Our tools are integrated into the
Trimaran compiler infrastructure. Starting with C/C code, our tool chain automatically produces behavioral hardware descriptions of the generated subgraphs in
VHDL and the scheduling statistics after replacing selected subgraphs with custom instructions. User defined merit functions and can be integrated
into subgraph generation and subgraph selection for ranking the subgraphs. We advocate the use of a simpler in subgraph generation.
final circuit to achieve a target clock frequency. The commu- 2) optimizes the difference between maximum ac-
nication latency represents the additional cycles needed cumulated software latency and the sum of HW and
to transfer the input and output operands of between the base , where HW is estimated by computing the crit-
processor and the custom logic. If the goal is to improve the per- ical path of the source level data flow graph S using
formance of the processor, the objective of optimization can be values and by applying an unconstrained scheduling. We
formulated as maximizing the reduction in the schedule length note that is equivalent to the objective function def-
by moving the source level data flow subgraph S from software inition of [18]
to hardware as follows:
M(S) = SW(S)— HW(S) — C(S). My(8) = > — HW(S) — C(S). (5)
iel
Estimating SW , and accurately for each 3) Similar to optimizes the difference be-
subgraph S within the inner loop of any optimization algorithm tween maximum accumulated software latency and the
can be a very time-consuming process. Accurate estimation sum of and . However, is esti-
of requires integration of instruction scheduling al- mated by the actual synthesis of using Synopsys Design
gorithms under base processor resource constraints. Accurate Compiler. As a result, M3(S) provides a much more
estimation of HW requires taking into account the effects accurate estimation than M 5 and :
of hardware optimizations, such as word-length optimization,
arithmetic transformations, logic minimization, technology = — HWs(8) = C(8). (6)
mapping, and register retiming. Similarly, accurate estimation ier
of requires evaluation of the effects of optimal data
partitioning, including the use of local memories and custom
state registers, and optimal pipelining after the synthesis of . VIII. OVERALL APPROACH
In this work, to estimate SW , a software latency Z* The algorithms described in this work are integrated into
is associated with every graph node V — , which gives the Trimaran compiler.1 Fig. 8 illustrates the associated tool
the time in clock cycles that it takes to execute on the pipeline chain. Starting with an application specification in C/C , an of the base processor. To estimate HW , every graph node if-conversion pass selectively eliminates control dependencies V — is associated with a hardware latency , within an application and transforms multiple basic blocks into which is estimated by synthesizing individual operators using a single basic block with predicated instructions. This extends Synopsys Design Compiler and normalizing to the delay of a the scope of our algorithms, and enables us to identify coarser 32-bit adder. Given the number of register file read and write grain custom instructions. Synopsys synthesis provides area ports, is estimated by calculating the data transfer cycles and delay estimations for generated custom instructions and needed to retrieve the input operands of S before its computa- Trimaran scheduling statistics are used to estimate the number tion starts and the cycles needed to write back the results when of execution cycles with and without custom instructions. the computation of S ends. In this work, three different merit Given the DFG of a basic block, the subgraph generation functions are used for ranking subgraphs, given here. algorithm picks the subgraph with the maximum value 1) identifies S with the maximum accumulated as the most promising custom instruction candidate. This sub- software latency, and assumes that HW and graph can be found either by ILP (Section V) or by enumeration can later be optimized by a postprocessing step, which (Section VI). Additionally, different functions can be in- involves hardware optimizations to minimize the critical tegrated into subgraph generation. After the computation of the path length, and the use of local memories and custom first custom instruction candidate, the associated subgraph is state registers to minimize the communication overhead: collapsed into a single forbidden node in the DFG. Next, a new = 3 (si). (4) subgraph with the maximum M (S) value among the remaining 1 = Trimaran. [Online]. Available: http://www.trimaran.org
ATASU et al.: FISH: FAST INSTRUCTION SYNTHESIS FOR CUSTOM PROCESSORS 59
TABLE II
EFFECT OF CLUSTERING ON THE NUMBER OF FORBIDDEN NODES AND ON THE NUMBER OF REMAINING NODES IN THE LARGEST BASIC BLOCK
Benchmark
(ABSew | 43 | 2mm3i| 27 | 3% | % | % | ® |B |
EEGall | 90 | 0 2S 2 0 |
[DEA 10 0 | | 0 | 1 1
8 [ 8 0 8 0
§[ | 1 T To]
18 35
| T |
CT| 7 7 5 |
32 99 7 1 9 71 15 71 15 3
| | | | #6 2 | 2 2 9 |
| 8 | 6 | 2 6 3 10 |
8 3 35 | 3 | 3 | 6 | 3 10 6 |
nodes is picked as the second custom instruction candidate. The Our experiments are carried out on an Intel® Pentium
process continues until no more maximal convex subgraphs 4 3.2-GHz workstation with 1-GB main memory, running
composed of more than one node can be found. This process is Linux®. Our algorithms are developed in C/C++, and compiled
similar to the iterative subgraph generation algorithm described with gcc-3.4.3 using —O2 optimization option.
in [18]. The approach of generating the most promising sub- Table II shows the effect of preprocessing and clustering op-
graph first helps in reducing the overall search space, without tions on the number of forbidden nodes (i.e., ) and on the
sacrificing source-code coverage. However, such a strategy number of nodes that are not forbidden (i.e., — ) in the
precludes the possibility of including one DFG node in two clustered graph (i.e., ). The results for the largest basic block or more custom instructions, which could provide benefits in of each benchmark are shown. For an explanation of different multi-issue processors. The subgraph generation algorithm options, see Section VI-A. Note that the Basic Preprocessing applies enumeration or ILP multiple times in each basic block. option does not implement any clustering and that all of the Note that the number of iterations carried out on a basic block clustering options include the Basic Preprocessing. Addition- is usually only a few. The DFG shrinks significantly after each ally, the Partial Clustering option implements clustering of the iteration, which reduces the run-times of both enumeration and nodes that are not forbidden (i.e., — only). We observe ILP considerably. that the Basic Preprocessing option usually results in a signi fi- In this work, we have integrated only and into cant reduction in the number of forbidden nodes, and the Partial the subgraph generation algorithms as it is often impractical to Clustering option usually results in a significant compaction in include the hardware synthesis in the inner loop of an enumer- the number of nodes that are not forbidden. Note that [19] uses ation algorithm having an exponential worst-case complexity. the Partial Clustering option, whereas [28] implements the Basic On the other hand, the subgraph selection algorithm makes use Preprocessing option only. Another observation is that Simple of , which takes into account both the hardware synthesis Clustering, in practice, results in no improvement with respect results and the data transfer costs, and provides more accurate to Partial Clustering in terms of the number of forbidden nodes and realistic speed-up estimations. and of the number of nodes that are not forbidden. On the other The subgraph generation procedure is applied only to appli- hand, Enhanced Clustering can further optimize the number of cation basic blocks with positive execution frequency, and a uni- forbidden nodes and the number of nodes that are not forbidden. fied set of subgraphs is generated. Next, structurally equivalent Another important point to note is that, immediately after Partial subgraphs that can be implemented using the same hardware Clustering, the largest basic blocks of SHA and IDEA bench- are grouped. Given the frequency of execution of the sub- marks are reduced to only a single node that is not forbidden. graph , the amount of reduction in the schedule length of the Table III presents the run-time results for different clustering application by moving S from software to hardware is estimated and branch ordering options. “Enum-TO” uses the topological as x . Finally, a Knapsack model [22] is utilized ordering described in Section VI.B while choosing the next node to select the most promising set of subgraphs under area con- to branch, whereas “Enum-AO” uses the adaptive ordering pro- straints. An important point is that the area and the delay coef- posed in [28], which tries to pick those nodes that are estimated ficients used by the subgraph selection step are computed using to reduce the search space more strongly than the others. The actual Synopsys synthesis. setup time includes the time to do the basic preprocessing and the clustering, which increases while moving from Basic Pre- IX. RUN-TIME RESULTS processing towards Enhanced Clustering. Note that “Enum-TO” and “Enum-AO” only include the search time, and exclude the The memory access, branch, and division instructions are set-up time. The Simple Clustering option is not included in marked as forbidden instructions in our experiments. Our al- the table because it does not result in any improvement in the gorithms are applied to ten benchmarks from multimedia and search time with respect to the Partial Clustering option and cryptography domains [38], [39], including an optimized 32-bit has a setup time comparable to that of the Enhanced Clustering implementation of Advanced Encryption Standard (AES) en- option. We observe that the Partial Clustering option signifi- cryption and decryption [40], and a FIPS-compliant fully un- cantly decreases the search time with respect to Basic Prepro- rolled Data Encryption Standard (DES) implementation [41]. cessing, and the Enhanced Clustering option further reduces the
60 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 20, NO. 1, JANUARY 2012
TABLE III
RUN-TIME TO COMPUTE THE SUBGRAPH THAT MAXIMIZES MM, (S) IN THE LARGEST BASIC BLOCK (IN SECONDS)
Benchmark
[ Set-up T Enum-TO [ Enum-AO [ Set-up | Enum-TO | Enum-AO | Setup [ Enum-TO | Enum-AO |
000120
000265
0.00689 ||0.24333 | 0.22559 | 0.00890 | 0.13334 001202 | 0.02253 |
000735 ol 0.02288
| 0 01 0
000007 0| 000007 0 0 0
| 0.00025 | 0.00031 0.00012 | 0.00008 || 0.00013 || 0.00019 0.00001
000021 000027 0.00002 | 0.00005 0.00036
0.00005 0.00001 0.00001 000001
TABLE IV
RUN-TIME TO COMPUTE THE SUBGRAPH THAT MAXIMIZES IN THE LARGEST BASIC BLOCK (IN SECONDS). RUN-TIME RESULTS FOR A COMBINATION OF
OUR ENUMERATION ALGORITHM AND SELECTED OPTIMIZATIONS FROM [28] ARE GIVEN IN THE ENUM-CMB COLUMN
Atasu ct al. 19 | Li ct al. 28 | Bron-Kerbosch 42 | ILP (CPLEX) | ILP (Ipsolve) Enum-CMB
AES enc 21.550 25.209 3.6332 0.05642 0.4600 2.8031 1.1987
AES dec 12057 134.05 3.0706 0.23837 1.6080 15879 0.67775
DES 0.14224 0.03354 0.03785 5.4520 171.63 0.03456 0.01533
SHA 0.00735 0.00735 0.00735 0.13555 2.8680 0.00735 0.00735
IDEA 0.00007 0.00007 0.00008 0.00906 0.02800 | 0.00007 | 0.00007
djpeg 0.00021 0.00029 0.00035 0.00854 0.03200 0.00020 0.00020
g72lencode 0.00026 0.00027 0.00035 0.02472 0.10800 0.00026 0.00026
g721decode 0.00029 0.00030 0.00044 0.02475 0.11600 | 0.00030 | 0.00030
rawcaudio 0.00006 0.00006 0.00010 0.00911 0.02000 0.00005 0.00005
rawdaudio 0.00006 0.00006 0.00016 0.00709 0.01600 0.00005 0.00005
search time for AES encryption, AES decryption, DES, and known as one of the fastest and most scalable maximal clique
djpeg benchmarks. In the case of the g721encode, g721decode, enumeration algorithms. To provide a fair comparison between
rawcaudio and rawdaudio benchmarks, the setup time domi- different techniques, we keep track of only one subgraph that
nates the search time, and the Basic Preprocessing option is maximizes in each case.
usually the fastest. “Enum-AO” improves the run-time slightly Table IV shows that [28] significantly improves the run-time
only in the case of the Basic Preprocessing option and only for of “Enum-AO” combined with Basic Preprocessing option
AES encryption and DES. In the remaining cases, it increases although it generates the same search tree. The improvement
the run-time with respect to “Enum-TO”, owing to the addi- is due to the optimizations in the data structures that simplify
tional complexity introduced in picking the next node to branch. the computation of (3). We have also integrated the same
Table III shows that the fastest options are “Enum-TO” com- optimization into our algorithms and observed a considerable
bined with the Basic Preprocessing or the Enhanced Clustering improvement in our run-time results. The results for the com-
options. bined method are given in the column labeled as “Enum-CMB”
Table IV compares the run-time of our ILP approach in Table IV. Note that the results of this work for AES encryp- (Section V) and our enumeration algorithm (Section VI) with tion and AES decryption benchmarks are significantly better the run-time of the enumeration algorithms described in [19], than both [19] and [28] thanks to the Enhanced Clustering tech- [28], [42]. The enumeration results of this work, and of [19] nique introduced in this work, which reduces the exponential can be derived from Table III by summing up the associated complexity of enumeration. However, a combination of our setup and search times. Note that [19] combines “Enum-TO” algorithm with selected optimizations from [28] provides the and Partial Clustering options. Our work also uses “Enum-TO” best enumeration run-time results. instead of the more costly “Enum-AO” option. However, we Table IV results indicate that enumerating maximal cliques choose between Basic Preprocessing and Enhanced Clus- using the Bron–Kerbosch algorithm produces run-time results tering options depending on the graph characteristics. If the comparable to those produced by our algorithms. Although both number of forbidden nodes is smaller than eight after Basic techniques benefit from node clustering (Section VI.A), the En- Preprocessing, our algorithm skips Enhanced Clustering, and hanced Clustering technique presented in this work is only ap- effectively uses the Basic Preprocessing option. Otherwise, plicable if the search tree is constructed in the way described in Enhanced Clustering is used. Such an approach gives us the Section VI-B. As a result, the Simple Clustering option is used best run-time results. We have also included the run-time of the in combination with Bron–Kerbosch algorithm in our experi- ILP using both a commercial solver (CPLEX [43]) and a public ments as described in [16], [17]. Note that our search tree con- domain solver.2 To provide a comparison with [16], [17], we struction technique makes use of a graph (namely ) that is have implemented the Bron–Kerbosch algorithm [42], which is composed of clusters of forbidden nodes only, i.e., a graph with 2lpsolve. [Online]. Available: http://sourceforge.net/projects/lpsolve nodes. Our work derives the upper bound on the number of
ATASU et al.: FISH: FAST INSTRUCTION SYNTHESIS FOR CUSTOM PROCESSORS 61
TABLE V
SINGLE ENUMERATION RUN-TIME FOR RIJNDAEL [38] (IN SECONDS)
© [encrypt [BB 8 Fm | |
20155 189 092 0.0 | 0.02%
&& 4808| | 48 172 0.96 [ 1.22 0027 [ 0013 |
Fig. 9. Connectivity of forbidden nodes for the largest basic block of AES. TABLE VI
TOTAL RUN TIME (IN SECONDS). CPLEX IS USED AS THE ILP SOLVER
maximal convex subgraphs as . However, the independent | | [Enum 0
set and the clique enumeration algorithms described in [16], [17] enc 3
rely on a graph representation that is composed of clusters of | ‘AES dec 1001 2% 10251 0.50534 32561
pgs 1235 45 210.03 30.892 0.38020
nodes that are not forbidden, i.e., a graph with — nodes | SHA 1339 30 045155
(see, for example, Fig. 4). It is well known that the number of en | 0.32819 0.11164
maximal cliques of a graph with — nodes is bounded | | 892 85 1.2475 pty Freed
0.62377 0.03509
by [42]. Based on the numbers given in Table II, g721decode | 864 79 13006 | 0.74369 0.03379
the upper bound derived by our work is a tighter one. On the | rawcaudio 19 13 0.06766 0.03284 0.00284
other hand, the two techniques appear to be equally effective in rawdaudio 102 11 0.06569 0.02990 0.00267
reducing the search space. Table IV also demonstrates that, except for AES encryption times until all DFG nodes are covered. Such an approach and AES decryption, enumeration is several orders of mag- usually results in a very small run-time overhead. Often, a few nitude faster than the ILP-based approach. The advantage of iterations are sufficient for each basic block, and the enumer- using enumeration is more evident when lpsolve is used instead ation run-time drops significantly after the first iteration. For of CPLEX. In fact, CPLEX [43] can automatically recognize each of the three basic blocks evaluated, the total run-time constraint matrices that correspond to clique and independent observed is smaller than 0.04 s for the Enum column, taking set problems and includes efficient solvers for these problems. into account all of the iterations needed. We observe that in the case of AES encryption and AES Finally, Table VI shows the total run-time of our sub- decryption, ILP is faster than enumeration even if lpsolve is graph-generation algorithm for our initial ten benchmarks. For used. In these two cases, enumerating all possible maximal each benchmark, the total number of instructions and the total convex subgraphs does not appear to be the most efficient way number of basic blocks are also provided. The table shows the of finding the most promising subgraph. ILP solvers usually run-time of ILP, using both My and as metric func- apply an objective guided search strategy. Branch-and-bound tions, and CPLEX as the solver. We also provide the run-time of and branch-and-cut type algorithms used by the ILP solvers our enumeration algorithm using M; as the metric function. reduce the search space not only based on the constraints, but We observe that the use of reduces the run-time of the also based on the definition of the metric function, without ILP usually by half. However, in the case of DES, the run-time enumerating every feasible solution. improvement is around seven fold. Enumeration is slower than Fig. 9 illustrates why enumeration is relatively inefficient for ILP in the case of AES encryption and AES decryption, but it AES encryption. On the largest basic block of AES encryption, is three fold faster for SHA, and about an order of magnitude G" is composed of 33 nodes after node clustering. This graph is faster for the remaining seven benchmarks. composed of five disconnected groups of nodes, one of which is composed of only a single node. The remaining four groups are X. DESIGN SPACE EXPLORATION RESULTS identical, and each one independently requires evaluation of 31 This work assumes a single-issue baseline machine with possible combinations. In total, our enumeration algorithm predication support containing 32 32-bit general-purpose regis- evaluates 2 x ~ 2M combinations, which takes around ters and 32 single-bit predicate registers, based on the HPL-PD 2.8 sec to execute. On the other hand, CPLEX finds the optimal architecture [44]. Software latency of integer multiplication solution in only 0.056 s, providing us with a second and more instructions is defined to be two cycles, and software latency of efficient solution alternative. the rest of the integer operations is defined to be a single cycle. Table V provides additional comparisons between our enu- Custom instructions are synthesized to UMC’s 130 nm standard meration algorithms and those described in [19] and [28]. Note cell library using Synopsys Design Compiler. Note that custom that the four techniques evaluated in Table V build similar instructions can be pipelined in order not to increase the cycle search trees, and each one is adapted to compute a single time of the base processor, which is estimated to be around the subgraph that maximizes . Note also that the run-time critical path delay of a 32-bit carry propagate adder. results presented in [28] for rijndael are around 10 s, an order of Figs. 10 and 11 demonstrate the area and performance magnitude larger than those we present under the [28] column. tradeoffs for the DES, and IDEA benchmarks using Such a slowdown is mainly due to the overhead of storing all as the metric function in subgraph generation and as of the enumerated subgraphs and removing the redundant ones, the metric function in subgraph selection. The execution cycle which our algorithms avoid. Our algorithms store only the best count without using custom instructions is normalized to a subgraph during enumeration, and apply enumeration multiple hundred and the percent reduction in the execution cycles using
62 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 20, NO. 1, JANUARY 2012
100 DWH mea mea men
@ sh Fri 100%: owt en 42 0% 3 44 sor o% 8 1 oo E 7p Jo² 60 iy ht a We 2 H 50 ENˣ oe Zw ee age eee EE
edo Fig. 12. Reduction in the number of execution cycles. Additional register file
ports improve the results. Two columns are provided for each benchmark: the
AREA (RIPPLE CARRY ADDERS) column on the right shows the results of and the column on the left
Fig. 10. DES: effect of increasing the number of register file ports on the per- shows the results of . Area costs are shown in ripple carry adders. formance for a range of area constraints. the enumeration algorithm of Section VI compute equivalent re- sults for the same merit function definition . The stacked Fo! fant columns show the results computed for four register file read % and write port combinations: (2,1), (2,2), (4,2), and (4,4). At 2 44 the top of each column, the cell area for the associated custom I< w datapath is given in equivalent RCA area costs. For AES En- on cryption, AES Decryption, DES, g721encode, and g721decode benchmarks, the results of and of differ only 8 marginally. The maximum difference observed for these five benchmarks is less than one percent. For the remaining five 8 © benchmarks, the results of are better when the register file ports are limited to two read ports and one write port. How- ever, as the register file port constraints are relaxed, the results 2 [Ra Ne of and again become indistinguishable. For a register file with two read ports and one write port, we ob- 10 serve between two to seven percent difference for the SHA, CONSTRAINT AREA do 4a (RIPPLE72 80 88 or vm ies IDEA, djpeg, rawcaudio, and rawdaudio benchmarks. On the Fig. 11. CARRY ADDERS) other hand, for a register file with two read ports and two write IDEA: effect of increasing the number of register file ports on the performance for a range of area constraints. ports, the difference is again smaller than one percent for eight of the benchmarks. Only in the case of rawcaudio and raw- custom instructions is shown for a range of area constraints. caudio benchmarks is around two percent difference observed. Five register file read and write port combinations are evalu- Given a register file port constraint of (4,2) or (4,4), the dif- ated: (2,1), (2,2), (4,1), (4,2), and (4,4). The combination (2,1) ference in all cases is even less than one percent and, occasion- stands for a register file with two read ports and a single write ally, zero. For some benchmarks, such as SHA and g721encode, port. Increasing the number of read and write ports supported in some cases, finds better results than . We ob- by the register file decreases the communication cost of the serve that because takes into account the communication custom instructions (i.e., in the computation of ) cost , it is advantageous over when the register file and increases the speed-up. In the case of DES, we observe port constraints are tight. However, in general, the two metric that an area equivalent to 16 ripple carry adders (RCAs) is functions produce similar results. In particular, if a basic block sufficient to achieve the highest speed-up. In the case of IDEA, is sufficiently large, almost always computes the same a significant reduction in the execution cycles can be achieved subgraph computed by M; , i.e., the maximum convex sub- at a cost of 64 RCAs, and an additional area budget of 28 RCAs graph of the basic block. results in further reduction. Such stepwise behavior is mainly due to a few large and frequently executed custom instructions XI. EXAMPLES OF CUSTOM INSTRUCTIONS (i.e., subgraphs). Fig. 13 shows the most promising custom instruction our al- Fig. 12 shows the percent reduction in the execution cycles of gorithms automatically identify from the DES C code. Note our ten benchmarks using custom instructions. For each bench- that, in this case, and compute equivalent results. mark, two columns are provided. The column on the right shows The software implementation fully unrolls DES round transfor- the results found using in subgraph generation and the mations within a single basic block, which results in 822 base column on the left shows the results found using in sub- processor instructions. The custom instruction of Fig. 13 im- graph generation. Note that the ILP model of Section V and plements the combinational logic between the memory access
ATASU et al.: FISH: FAST INSTRUCTION SYNTHESIS FOR CUSTOM PROCESSORS 63
TABLE VII
ROUND I-1 RELATIVE LATENCY AND AREA COEFFICIENTS FOR VARIOUS OPERATORS
BASED ON SYNTHESIS RESULTS USING UMC’S 130-NM PROCESS
H1 0: :: 32-bit + 32-bit adder
32-bit * 32-bit multiplier 18.463
:
32-bit
d: 1B) 18 | 32-bit comparator (eq)
32-bit comparator (geq) 0552 | 0632
|
| TABLE VIII
| ESTIMATED VERSUS SYNTHESIZED LATENCY AND AREA RESULTS FOR THE
MOST PROMISING CUSTOM INSTRUCTIONS WHILE UNROLLING SHA
Ai [TF Caney | Sym | Bt Avea | Area |
SHA) 20%
5 5119 21.266
SHA 10
ROUND I+1 SHA (full) 292.037 82495 | 433981
Fig. 13. Most promising custom instruction for DES. Although the custom in- struction has eleven input and nine output operands, the use of local memories Table VII presents the synthesis results obtained for various reduces the communication cost C(S) to zero. source-level operations using Synopsys Design Compiler. The latency and area results given are normalized to the latency and layers of two consecutive DES rounds. Our algorithms automat- area results of a 32-bit adder. Note that estimates the ically identify 15 equivalent instances of this instruction in the latency of custom instructions as the latency of the same basic block. We note that X and Y represent the DES en- longest path length between the source and destination operands cryption state. Eight of the inputs of the custom instruction are of the source-level DFG subgraph S using the latency coef- static lookup table (LUT) entries (SBs), and two of the inputs ficients of Table VII. Recently, algorithms for pipelining (SK1, SK2) contain the DES round key. Accordingly, eight of source-level DFGs have also been described [14], [17], which the outputs contain the addresses of the LUT entries that should use similar estimation techniques. Table VIII shows that such be fetched for the next round. We observe that the size of the approaches can be highly inaccurate because the target hard- LUTs is rather small (256 bytes only). We could avoid all of the ware libraries and the optimizations applied by the synthesis related main memory accesses and address calculations by em- tools are not taken into account. Table VIII compares the syn- bedding the eight LUTs in local memories. Similarly, the DES thesized latency and area results of the custom in- scheduled key is only 32 bytes wide and can be embedded in structions for five SHA implementations with the estimated la- local memories, again eliminating a number of main memory tency and area results. Note that area estimations are accesses. Although the custom instruction has eleven input and computed by assuming a cumulative cost model and using the eight output operands, the use of local memories reduces its coefficients of Table VII. A large gap between the estimations communication cost to zero. These optimizations reduce and the synthesis results can be observed. This gap becomes the size of the core basic block of DES from 822 to 22 instruc- even larger as the main loop of SHA gets unrolled, and larger tions, which incorporate only five base processor instructions DFG subgraphs are identified. Assuming that the target cycle and three different types of custom instructions. Our synthesis time is around the delay of a 32-bit adder, the difference be- results show that each of these custom instructions has only a tween the estimated latency and the synthesized latency goes single cycle latency HW . The result is a 30-fold speed-up. up to 160 cycles for fully unrolled SHA. We conclude that es- Our second example is SHA. The most time-consuming part timating HW at the source level can be highly inaccurate, of SHA is the compression function, which is applied 80 times which also explains the similarity between and within a loop body. This loop body is often unrolled to improve results in Fig. 12. the software performance of SHA. In this work, we evaluate five Note that, although the custom instruction generated for DES different implementations: the first implementation does not un- example is highly reusable and has a low area overhead, the roll the main loop of SHA; the next three implementations have custom instructions generated for SHA have a high area over- their loops unrolled two, five, and ten times. The fifth implemen- head and almost no reuse potential. As illustrated in [18], it is in tation has the SHA main loop fully unrolled. In all five cases, fact possible to find more area-efficient custom processor con- our algorithms identify only a single maximal convex subgraph figurations for SHA, which also offer a reasonably good perfor- within the loop body. We observe that unrolling the loop body mance, by searching for smaller and more reusable subgraphs. results in the identification of larger DFG subgraphs. Such sub- Ideally, a combination of these two approaches should be evalu- graphs often translate into an increase in the latency and the area ated to identify the most promising area and performance trade- cost of custom instructions. offs for custom instruction processors.
64 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 20, NO. 1, JANUARY 2012
XII. CONCLUSION [4] R. E. Gonzalez, “Xtensa: A configurable and extensible processor,”
This paper presented FISH, a novel approach for improving IEEE Micro, vol. 20, no. 2, pp. 60–70, 2000.
the efficiency of automatically generated custom instruction [5] G. Martin, “Recent developments in configurable and extensible pro-
cessors,” in Proc. ASAP, Sep. 2006, pp. 39–44.
processors and the associated theoretical and practical results. [6] K. Atasu, L. Pozzi, and P. Ienne, “Automatic application-specific in-
FISH introduces fast custom instruction synthesis methods struction-set extensions under microarchitectural constraints,” in Proc.
based on a novel subgraph enumeration algorithm and an in- 40th DAC, Anaheim, CA, Jun. 2003, pp. 256–261.
[7] J. Cong, Y. Fan, G. Han, and Z. Zhang, “Application-specific instruc-
teger linear programming formulation. FISH evaluates maximal tion generation for configurable processor architectures,” in Proc.
convex subgraphs of source-level DFGs as custom instruction FPGA, Monterey, CA, Feb. 2004, pp. 183–189.
candidates. The use of multiple different merit functions for [8] P. Yu and T. Mitra, “Scalable custom instructions identification for in-
struction-set extensible processors,” in Proc. CASES, Sep. 2004, pp.
ranking custom instruction candidates is enabled within a de- 69–78.
sign space exploration framework. The run-time results show [9] L. Pozzi, K. Atasu, and P. Ienne, “Exact and approximate algorithms
that the search space reduction techniques described in this for the extension of embedded processor instruction sets,” IEEE Trans.
Comput-Aided Des. (CAD) Integr. Circuits Syst., vol. 25, no. 7, pp.
work result in the fastest enumeration algorithms among the 1209–1229, Jul. 2006.
state-of-the-art maximal convex subgraph enumeration algo- [10] P. Yu and T. Mitra, “Disjoint pattern enumeration for custom instruc-
rithms, including those based on maximal clique enumeration. tions identification,” in Proc. FPL, Aug. 2007, pp. 273–278.
[11] X. Chen, D. L. Maskell, and Y. Sun, “Fast identification of custom in-
In addition, FISH derives an upper bound on the number of structions for extensible processors,” IEEE Trans. Comput-Aided Des.
maximal convex subgraphs in a DFG and on the complexity of (CAD) Integr. Circuits Syst., vol. 26, no. 2, pp. 359–368, Feb. 2007.
enumeration that is tighter than the respective bound known for [12] G. Gutin, A. Johnstone, J. Reddington, E. Scott, and A. Yeo, “An al-
gorithm for finding input-output constrained convex sets in an acyclic
maximal clique enumeration. digraph,” in Proc. WG, 2008, pp. 206–217. In most of the cases, enumeration is faster than ILP. How- [13] K. Atasu, G. Dündar, and C. Özturan, “An integer linear programming ever, in those cases where enumeration is relatively inefficient, approach for identifying instruction-set extensions,” in Proc. CODES ISSS, Jersey City, NJ, Sep. 2005, pp. 172–177. ILP provides a fast alternative. Our experiments show that in [14] L. Pozzi and P. Ienne, “Exploiting pipelining to relax register-file port most of the cases a simple merit function, which estimates only constraints of instruction-set extensions,” in Proc. CASES, 2005, pp. the software costs of the subgraphs, can be as good as a more 2–10. [15] K. Atasu, R. G. Dimond, O. Mencer, W. Luk, C. Özturan, and G. complex merit function that also estimates the hardware exe- Dündar, “Optimizing instruction-set extensible processors under data cution latencies and the communication costs. In particular, in bandwidth constraints,” in Proc. DATE, Nice, France, Apr. 2007, pp. large basic blocks, the two merit functions compute the same 588–593. [16] N. Pothineni, A. Kumar, and K. Paul, “Application specific datapath subgraphs most of the time. We show that, for DES, combining with distributed I/O functional units,” in Proc. VLSI Design, Hyder- our subgraph generation and selection approach with a simple abad, India, Jan. 2007, pp. 551–558. postprocessing step results in a 30-fold speed-up with respect to [17] A. K. Verma, P. Brisk, and P. Ienne, “Rethinking custom ISE identifi- cation: A new processor-agnostic method,” in Proc. CASES, Salzburg, a single-issue base processor. Austria, Sep. 2007, pp. 125–134. Current and future work includes: 1) developing better [18] K. Atasu, C. Özturan, G. Dündar, O. Mencer, and W. Luk, “CHIPS: estimators for critical path computation that take into account Custom hardware instruction processor synthesis,” IEEE Trans. Comput.-Aided Des. (CAD) Integr. Circuits Syst., vol. 27, no. 3, pp. arithmetic optimizations, word-length optimizations, target 528–541, Mar. 2008. hardware libraries, and wire delays; 2) exploring data-layout [19] K. Atasu, O. Mencer, W. Luk, C. Özturan, and G. Dündar, “Fast custom and loop transformations and applying our techniques on instruction identification by convex subgraph enumeration,” in Proc. ASAP, Leuven, Belgium, Jul. 2008, pp. 1–6. larger code segments beyond predicated basic blocks; and 3) [20] J. Van Praet, G. Goossens, D. Lanneer, and H. De Man, “Instruction enhancing our tool chain to implement resource-constrained set definition and instruction selection for ASIPs,” in Proc. ISSS, 1994, scheduling algorithms for pipelining register file accesses [14], pp. 11–16. [21] R. Kastner, S. Ogrenci-Memik, E. Bozorgzadeh, and M. Sarrafzadeh, [17]. Possible further extensions include supporting design de- “Instruction generation for hybrid reconfigurable systems,” in Proc. velopment with power and energy constraints [45], integrating ICCAD, 2001, pp. 127–130. our design flow into synthesis tools for heterogeneous multi- [22] N. Clark, H. Zhong, and S. Mahlke, “Processor acceleration through automated instruction set customization,” in Proc. MICRO, 2003, pp. processor SoC devices [46], [47] and combining our algorithms 184–88. with fast synthesis techniques [48], [49] to enable dynamic [23] F. Sun, S. Ravi, A. Raghunathan, and N. K. Jha, “Custom-instruction hardware/software partitioning and run-time reconfiguration. synthesis for extensible-processor platforms,” IEEE Trans. Comput.- Aided (CAD) Integr. Circuits Syst., vol. 23, no. 2, pp. 216–228, Feb. 2004. ACKNOWLEDGMENT [24] P. Biswas, S. Banerjee, N. Dutt, L. Pozzi, and P. Ienne, “ISEGEN: Generation of high-quality instruction set extensions by iterative im- The authors would like to thank C. Bolliger, A.-M. Cromack, provement,” in Proc. DATE, Mar. 2005, pp. 1246–1251. and C. Hagleitner, IBM Research—Zurich, and the anonymous [25] R. Leupers, K. Karuri, S. Kraemer, and M. Pandey, “A design flow for reviewers for their valuable comments. configurable embedded processors based on optimized instruction set extension synthesis,” in Proc. DATE, Munich, Germany, Mar. 2006, pp. 581–586. REFERENCES [26] A. K. Verma, P. Brisk, and P. Ienne, “Fast, quasi-optimal, and pipelined instruction-set extensions,” in Proc. ASPDAC, Mar. 2008, [1] J. Henkel, “Closing the SoC design gap,” Computer, vol. 36, no. 9, pp. pp. 334–339. 119–121, Sep. 2003. [27] J. Reddington, G. Gutin, A. Johnstone, E. Scott, and A. Yeo, “Better [2] M. Gschwind, “Instruction set selection for ASIP design,” in Proc. than optimal: Fast identification of custom instruction candidates,” in CODES, 1999, pp. 7–11. Proc. CSE (2), 2009, pp. 17–24. [3] P. Faraboschi, G. Brown, J. A. Fisher, G. Desoli, and F. Homewood, [28] T. Li, Z. Sun, W. Jigang, and X. Lu, “Fast enumeration of maximal “Lx: A technology platform for customizable vliw embedded pro- valid subgraphs for custom-instruction identification,” in Proc. CASES, cessing,” in Proc. ISCA, 2000, pp. 203–213. 2009, pp. 29–36.
ATASU et al.: FISH: FAST INSTRUCTION SYNTHESIS FOR CUSTOM PROCESSORS 65
[29] P. Biswas, V. Choudhary, K. Atasu, L. Pozzi, P. Ienne, and N. Dutt, electronic design automation, and programmable accelerator engines for packet “Introduction of local memory elements in instruction set extensions,” processing algorithms. in Proc. DAC, 2004, pp. 729–734. Dr. Atasu was the recipient of a Best Paper Award at the Design Automation [30] N. Moreano, E. Borin, C. de Souza, and G. Araujo, “Efficient data- Conference in 2003 and the IEEE International Conference on Application-Spe- path merging for partially reconfigurable architectures,” IEEE Trans. cific Systems, Architectures, and Processors in 2008. Comput.-Aided Des. (CAD) Integr. Circuits Syst., vol. 24, no. 7, pp. 969–980, Jul. 2005. [31] N. Cheung, S. Parameswaran, J. Henkel, and J. Chan, “MINCE: Wayne Luk (S’85–M’89–SM’06–F’09) received the Matching instructions using combinational equivalence for extensible M.A., M.Sc., and D.Phil. degrees in engineering and processor,” in Proc. DATE, Feb. 2004, pp. 1020–1027. computing science from the University of Oxford, [32] A. Chattopadhyay, W. Ahmed, K. Karuri, D. Kammler, R. Leupers, Oxford, U.K., in 1984, 1985, and 1989, respectively. G. Ascheid, and H. Meyr, “Design space exploration of partially He is a Professor of Computer Engineering with re-configurable embedded processors,” in Proc. DATE, Apr. 2007, pp. the Department of Computing, Imperial College 319–324. London, London, U.K., and leads the Custom Com- [33] S.-K. Lam and T. Srikanthan, “Rapid design of area-efficient custom puting Group there. He is also a Visiting Professor instructions for reconfigurable embedded processing,” J. Syst. Archi- with Stanford University, Stanford, CA. His research tecture, vol. 55, no. 1, pp. 1–14, 2009. « interests include theory and practice of customizing [34] S. P. Seng, W. Luk, and P. Y. K. Cheung, “Run-time adaptive flexible hardware and software for specific application instruction processors,” in Proc. FPL, Sep. 2002, pp. 545–555. domains, such as graphics and image processing, multimedia, and communi- [35] L. Bauer, M. Shafique, S. Kramer, and J. Henkel, “RISPP: Rotating cations. Much of his current work involves high-level compilation techniques instruction set processing platform,” in Proc. DAC, Jun. 2007, pp. and tools for parallel computers and embedded systems, particularly those 791–796. containing reconfigurable devices such as field-programmable gate arrays. [36] N. Clark, J. Blome, M. Chu, S. Mahlke, S. Biles, and K. Flautner, “An architecture framework for transparent instruction set customization in embedded processors,” in Proc. ISCA, Washington, DC, 2005, pp. Oskar Mencer (M’09) received the B.S. degree in 272–283. computer engineering from The Technion, Haifa, [37] K. Atasu, “Hardware/software partitioning for custom instruction | Israel, in 1994, and the M.S. and Ph.D. degrees in processors” Ph.D. dissertation, Dept. Comput. Eng., Bogazici Univ., electrical engineering from Stanford University, Istanbul, Turkey, 2007 [Online]. Available: http://www.doc.ic.ac.uk/ Stanford, CA, in 1997 and 2000, respectively. ~atasu/Kubilay_Atasu_PhD_Thesis.pdf He founded MAXELER Technologies, in 2003, [38] M. Guthaus et al., “MiBench: A Free, Commercially Representative after three years as a member of Technical Staff in Embedded Benchmark Suite,” Univ. of Michigan, Ann Arbor [Online]. the Computing Sciences Research Center, Bell Labs. Available: http://www.eecs.umich.edu/mibench/ Since 2004, he has been a full-time member of the [39] C. Lee et al., “MediaBench: A tool for evaluating and synthesizing academic staff in the Department of Computing, multimedia and communications systems,” in Proc. MICRO, Dec. Imperial College London, London, U.K., and leads 1997, pp. 330–335. the computer architecture research group there. His research interests include [40] K. Atasu, M. Macchetti, and L. Breveglieri, “Efficient AES implemen- computer architecture, computer arithmetic, very large scale integration tations for ARM based platforms,” in Proc. SAC, 2004, pp. 841–845. (VLSI) micro-architecture, VLSI computer-aided design (CAD), and recon- [41] “XySSL—DES and Triple-DES Source Code,” [Online]. Available: figurable (custom) computing. More specifically, he is interested in exploring http://xyssl.org/ application-specific representation of computation at the algorithm level, the [42] C. Bron and J. Kerbosch, “Algorithm 457: Finding all cliques of an architecture level, and the arithmetic level. undirected graph,” Commun. ACM, vol. 16, no. 9, pp. 575–577, 1973. [43] ILOG CPLEX Optimization Software. ILOG. [Online]. Available: http://www.ilog.com/products/cplex/ Can Özturan received the Ph.D. degree in computer [44] V. Kathail et al., HPL-PD Architecture Specification, Version 1.0 HP science from Rensselaer Polytechnic Institue, Troy, Labs Tech. Rep. HPL-93-80R1, 1993. NY, in 1995. [45] Y. Fei, S. Ravi, A. Raghunathan, and N. K. Jha, “A hybrid energy- After working as a Post-Doctoral Staff Scientist estimation technique for extensible processors,” IEEE Trans. Comput.- 4 with the Institute for Computer Applications in Sci- Aided Des. (CAD) Integr. Circuits Syst., vol. 23, no. 5, pp. 652–664, ence and Engineering (ICASE), NASA Langley Re- May 2004. search Center, he joined the Department of Computer [46] F. Sun, S. Ravi, A. Raghunathan, and N. K. Jha, “Application-specific Engineering, Boğaziçi University, Istanbul, Turkey, heterogeneous multiprocessor synthesis using extensible processors,” as a Faculty Member in 1996. His research interests IEEE Trans. Comput.-Aided Des. (CAD) Integr. Circuits Syst., vol. 25, are parallel processing, scientific computing, graph no. 9, pp. 1589–1602, Sep. 2006. algorithms, and grid computing. [47] S. L. Shee and S. Parameswaran, “Design methodology for pipelined heterogeneous multiprocessor system,” in Proc. DAC, Jun. 2007, pp. 811–816. Günhan Dündar was born in Istanbul, Turkey, in [48] R. Lysecky, F. Vahid, and S. X.-D. Tan, “Dynamic FPGA routing for 1969. He received the B.S. and M.S. degrees from just-in-time FPGA compilation,” in Proc. DAC, 2004, pp. 954–959. Boğaziçi University, Istanbul, Turkey, in 1989 and [49] R. Lysecky and F. Vahid, “Design and implementation of a MicroB- 1991, respectively, and the Ph.D. degree from Rens- laze-based warp processor,” ACM Trans. Embed. Comput. Syst., vol. = selaer Polytechnic Institute, Troy, NY, in 1993, all in 8, no. 3, pp. 1–22, 2009. electrical engineering. Since 1994, he has been with Department of Kubilay Atasu (S’03–M’08) received the B.Sc. N Electrical and Electronics Eng. Boğaziçi University, degree in computer engineering from Boğaziçi Istanbul, Turkey, where he is currently a Professor. University, Istanbul, Turkey, in 2000, the M.Eng. During 1994, he was with the Turkish Navy at the degree in embedded systems design from University \ Naval Academy and, during 2003, he was with of Lugano, Lugano, Switzerland, in 2002, and the EPFL, Switzerland, both on leave from Boğaziçi University. He has authored Ph.D. degree in computer engineering from Boğaziçi or coauthored more than 100 publications in international journals and con- University, Istanbul, Turkey, in 2007. ferences. His research interests include analog IC design, electronic design From 2005 to 2008, he was a Research Associate automation, and neural networks. with the Department of Computing, Imperial College London, London, U.K. Since 2008, he has been with Systems Department, IBM Research—Zurich, Ruschlikon, Switzerland. His research interests include custom processors,