Here, we formally introduce the minimum area-cost acyclic common supergraph problem. Bunke et al. [4] have proven a variant of this problem NP-complete.

Problem: Minimum Area-Cost Acyclic Common Supergraph. Given a set of DAGs G = {G₁, G₂, ..., G_k}, construct a DAG G’ of minimal area cost such that G_i, 1 ≤ i ≤ k, is isomorphic to some subgraph of G’.

Graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) are isomorphic to one another if there is a one-to-one and onto mapping f : V₁ → V₂ such that (u₁, v₁) ∊ E₁ ⇔ (f(u₁), f(v₁)) ∊ E₂. Common supergraph problems are similar in principle to the NP-complete subgraph isomorphism problem [5].

Let X = 〈x₁, x₂, ..., x_m〉 and Y = 〈y₁, y₂, ..., y_n〉 be character strings. Z = 〈z₁, z₂, ..., z_k〉 is a subsequence of X if there is an increasing sequence 〈i₁, i₂, ..., i_k〉 of indices such that:

Equation 10.4. 

For example, if X = ABC, the subsequences of X are A, B, C, AB, AC, BC, and ABC.

If Z is a subsequence of X and Y, then Z is a common subsequence. Determining the longest common subsequence (LCSeq) of a pair of sequences of lengths m ≤ n has a solution with time complexity O(mn/logm) [6]. For example, If X = ABCBDA and Y = BDCABA, the LCSeq of X and Y is BCBA. A substring is defined to be a contiguous subsequence. The solution to the problem of determining the longest common substring (LCStr) of two strings has an O(m + n) time complexity [7]. X and Y in the preceding example have two LCStrs: AB and BD.

If a path is derived from a DAG, then each operation in the path represents a computation that must eventually be bound to a resource. The area of the necessary resource can therefore be associated with each operation in the path. To maximize area reduction by resource sharing along a set of paths, we use the maximum-area common subsequence (MACSeq) or substring (MACStr) of a set of sequences, as opposed to the LCSeq or LCStr. MACSeq and MACStr favor shorter sequences of high-area components (e.g., multipliers) rather than longer sequences of low-area components (e.g., logical operators), which could be found by LCSeq or LCStr. The algorithms for computing the LCSeq and LCStr are, in fact, degenerate cases of the MACSeq and MACStr, where all operations are assumed to have an area cost of 1.

Fig. 10.4 illustrates the preceding concepts.

Figure 10.4. Substring and subsequence matching example.

The heuristic proposed for common supergraph construction first decomposes each DAG into paths, from sources (vertices of in-degree 0) to sinks (vertices of out-degree 0); this process is called path-based resource sharing (PBRS). The sets of input-to-output paths for DAGs G₁ and G₂ in Fig. 10.1 are {DBA, CBA, CA} and {DBD, DBD, DCD, DCD, CCD}, respectively.

Let G = (V, E) be a DAG and P be the set of source-to-sink paths in G. In the worst case, |P| = O(2^|V|); it is possible to compute |P| (but not necessarily P) in polynomial time using a topological sort of G. Empirically, we have observed that |P| < 3|V| for the vast majority of DAGs in the Mediabench [8] application suite; however, |P| can become exponential in |V| if a DAG represents the unrolled body of a loop that has a large number of loop-carried dependencies. To accommodate larger DAGs, enumeration of all paths in P could be replaced by a pruning heuristic that limits |P| to a reasonable size.

An example is given to illustrate the behavior of a heuristic that solves the minimum area-cost acyclic common supergraph problem. The heuristic itself is presented in detailed pseudocode in the next section. Without loss of generality, a MACSeq implementation is used.

Fig. 10.5(a) shows three DAGs, G₁, G₂, and G₃, that are decomposed into sets of paths P₁, P₂, and P₃, respectively. The MACSeq of every pair of paths in P_i, P_j, i ≠ j, is computed. DBA is identified as the area-maximizing MACSeq of P₁, P₂, and P₃. DBA occurs only in P₁ and P₂, so G₁ and G₂ will be merged together initially. G’, the common supergraph of G₁ and G₂ produced by merging the vertices in the MACSeq, is shown in Fig. 10.5(b). These vertices are marked SHARED; all others are marked 1 or 2 according to the DAG of origin. This initial merging is called the global phase, because it determines which DAGs will be merged together each step. The local phase, which is described next, performs further resource sharing among the selected DAGs.

Figure 10.5. Example illustrating the minimum area-cost acyclic common supergraph heuristic.

Let G₁’ and G₂’ be the respective subgraphs of G’ induced by vertices marked 1 and 2, respectively. As the local phase begins, G₁’ and G₂’are decomposed into sets of paths P₁’ and P₂’ whose MACSeq is C. The vertex labeled C in G₂’ may be merged with any of three vertices labeled C in G₁’. In this case, the pair of vertices of type C having a common successor, the vertex of type A, are merged together. Merging two vertices with a common successor or predecessor shares interconnect resources. No further resource sharing is possible during the local phase, since no vertices marked with integer value 2 remain. G₁ and G₂ are removed from the list of DAGs and are replaced with G’, which has been renamed G₁₂ in Fig. 10.5(c).

In Fig. 10.5(c), the set of DAGs now contains G₁₂ and G₃. The global phase decomposes these DAGs into sets of paths P₁₂ and P₃, respectively. The MACSeq that maximizes are reduction is BA. The local phase begins with a new DAG, G’, as shown in Fig. 10.5(d); one iteration of the local phase yields a MACSeq DD, and G’ is shown after resource sharing in Fig. 10.5(e). At this point, no further resource sharing is possible during the local phase. In Fig. 10.5(f), G’ = G₁₂₃ replaces G₁₂ and G₃ in the list of DAGs. Since only G₁₂₃ remains, the algorithm terminates. G₁₂₃, as shown in Fig. 10.5(f), is a common acyclic supergraph of G₁, G₂, and G₃ in Fig. 10.5(a).

The heuristic procedure used to generate G₁₂₃ does not guarantee optimality.

Pseudocode for the heuristic exemplified in the previous section is provided and summarized. A call graph, shown in Fig. 10.6, provides an overview. Pseudocode is given in Figs. 10.7–10.12. The starting point for the heuristic is a function called Construct_Common_Supergraph (Fig. 10.7). The input is a set of DAGs G = {G₁, G₂, ..., G_n}. When Construct_Common_Supergraph terminates, G will contain a single DAG that is a common supergraph of the set of DAGs originally in G.

Figure 10.6. Program call graph for the minimum area-cost acyclic common supergraph heuristic.

Figure 10.7. Minimum area-cost acyclic common supergraph construction heuristic.

Figure 10.8. Subroutine used to identify paths having the maximal MACSeq or MACStr.

Figure 10.9. Subroutine used during the global phase to select which DAGs to merge and along which paths to initially share vertices.

Figure 10.10. Applying PBRS to the DAGs along the paths selected by Select_DAGs_to_Merge.

Figure 10.11. The local phase, which comprises the core of the resource-sharing heuristic.

Figure 10.12. Assists Local_PBRS (Fig. 10.11) by determining which paths should be merged during each iteration.

The first step is to decompose each DAG G_i ∊ G into a set of input-to-output paths, P_i, as described in Section 10.4.1. The set P = {P₁, P₂, ..., P_n} stores the set of paths corresponding to each DAG. Lines 1–5 of Construct_Common_Supergraph (Fig. 10.7) build P.

Line 6 consists of a call to function Max_MACSeq/MACStr (Fig. 10.8), which computes the MACSeq/MACStr S_xy of each pair of paths p_x ∊ P_i, p_y ∊ P_j, 1 ≤ x ≤|P_i|, 1 ≤ y ≤|P_j|, 1 ≤ i = j ≠ ≤ n. Max_MACSeq/MACStr returns a subsequence/substring S_max, whose area, Area(S_max) is maximal. The loop in lines 7–17 of Fig. 10.7 performs resource sharing. During each iteration, a subset of DAGs G_max ⊆ G is identified (line 8). A common supergraph G’ of G_max is constructed (lines 9–12). The DAGs in G_max are removed from G and replaced with G’ (lines 13–15).

The outer while loop in Fig. 10.7 iterates until either one DAG is left in G or no further resource sharing is possible. Resource sharing is divided into two phases, global (lines 8–9) and local (lines 10–12). The global phase consists of a call to Select_DAGs_to_Merge (Fig. 10.9) and Global_PBRS (Fig. 10.10).

The local phase consists of repeated calls to Local_PBRS (Fig. 10.11). The global phase determines which DAGs should be merged together at each step; it also merges the selected DAGs along a MACSeq/MACStr that is common to at least one path in each. The result of the global phase is G’—a common supergraph of G_max but not necessarily of minimal cost. The local phase is responsible for refining G’ such that the area cost is reduced while maintaining the invariant that G’ remains an acyclic common supergraph of G_max.

Line 8 of Fig. 10.7 calls Select_DAGs_To_Merge (Fig. 10.9), which returns a pair (G_max, P_max), where G_max is a set of DAGs as described earlier, and P_max is set of paths, one for each DAG in G_max, having S_max as a subsequence or substring. Line 9 calls Global_PBRS (Fig. 10.10), which constructs an initial common subgraph, G’ of G_max. The loop in lines 10–12 repeatedly calls Local_PBRS (Fig. 10.10) to share additional resources within G’. Lines 13–15 remove the DAGs in G_max from G and replaces them with G’; line 16 recomputes S_max.

Construct_Common_Supergraph terminates when G contains one DAG or no further resource sharing is possible. Global_PBRS and Local_PBRS are described in detail next. G_max, P_max, and S_max are the input parameters to Global_PBRS (Fig. 10.10). The output is a DAG, G’ =(V’, E’), an acyclic common supergraph (not necessarily of minimal area-cost) of G_max. G’ is initialized (line 1) to be the DAG representation of S_max as a path; i.e., S_max = (V_max, E_max), V_max = {s_i|1 ≤ i ≤|S_max|}, and E_max = {(s_i, s_i+1)|1 ≤ i ≤|S_max|– 1}. Fig. 10.10 omits this detail.

DAG G_i = (V_i, E_i) ∊ G_max is processed in the loop spanning lines 3–18 of Fig. 10.10. Let S_i ⊆ V_i be the vertices corresponding to S_max in G’. Let G_i’ = (V_i’, E_i’), where V_i’ = V_i –S_i, and E_i’ = {(u, v)|u, v ∊ V_i’}. G_i’ is copied and added to G’. Edges are also added to connect G_i’ to S_max in G’. For each edge e ∊{(u, v)|u ∊ S_i, v ∊ V_i’}, edge (m_i, v) is added to E’, where m_iis the character in S_max matching u. Similarly, edge (u, n_i) is added to E’for every edge e ∊{(u, v)|u ∊ V_i’, v ∊ S_i}, where n_i is the character in S_max matching v, ensuring that G’ is an acyclic supergraph of G_i.

All vertices in V_max are marked SHARED; all vertices in V_i’ are marked with value i. Global_PBRS terminates once each DAG in G_max is processed. To pursue additional resource sharing, Local_PBRS (Fig. 10.11) is applied following Global_PBRS.

Vertex merging, if unregulated, may introduce cycles to G’. Since G’must also be a DAG, this cannot be permitted. This constraint is enforced by line 8 of Max_MAC_Seq/MACStr (Fig. 10.8). This constraint is only necessary during Local_PBRS. The calls to Max_MACSeq/MACStr from Construct_Common_Supergraph (Fig. 10.7) pass a null parameter in place of G’; consequently, the constraint is not enforced in this context.

The purpose of labeling vertices should also be clarified. At each step during the local phase, the vertices marked SHARED are no longer in play for merging. Merging two vertices in G’ that have different labels reduces the number of vertices while preserving G’s status as a common supergraph. A formal proof of this exists but has been omitted to save space. Likewise, if two vertices labeled i were merged together, then G_i’would no longer be a subgraph of G’.

Local_PBRS decomposes each DAG G_i’ ⊂ G’ into a set of input-to-output paths P_i’ (lines 3–8), where P’ = {P₁’, P₂’, ..., P_k’}. All vertices in all paths in P_i’ are assigned label i. Line 9 calls Max_MACSeq/MACStr Fig. 10.8) to produce S_max’, the MACSeq/MACStr of maximum weight that occurs in at least two paths, p_x’ ∊ P_i’ and p_y’ ∊ P_j’, i≠j. Line 10 calls Select Paths to Merge (Fig. 10.12), which identifies a set of paths—no more than one for each set of paths P_i’—that have S_max’ as a subsequence or substring; this set is called P_max’. Line 11 of Local_PBRS (Fig. 10.10) merges the vertices corresponding to the same character in S_max’, reducing the total number of operations comprising G’. This, in turn, reduces the cost of synthesizing G’.

Resource sharing along the paths in P_max’ is achieved via vertex merging. Here, we describe how to merge two vertices, v_i and v_j, into a single vertex, v_ij; merging more than two vertices is handled similarly. Initially, v_i and v_j and all incident edges are removed from the DAG. For every edge (u, v_i) or (u, v_j), an edge (u, v_ij) is added to the DAG; likewise for every edge (v_i, v) or (v_j, v), an edge (v_ij, v) is added as well. In other words, the incoming and outgoing neighbors of v_ij are the unions of the respective incoming and outgoing neighbors of v_i and v_j.

The vertices that have been merged are marked SHARED in line 12 of Local_PBRS, thereby eliminating them from further consideration during the local phase. Eventually, either all vertices will be marked as SHARED, or the result of Max_MACSeq/MACStr will be the empty string. This completes the local phase of Construct_Common_Supergraph (Fig. 10.7). The global and local phases then repeat until no further resource sharing is possible.

In Fig. 10.13(a), a unary operator U, assumed to be part of a supergraph, has three inputs. One multiplexer is inserted; its one output is connected to the input of U, and the three inputs to U are redirected to be inputs to the multiplexer. If the unary operator has only one input, then the multiplexer is obviously unnecessary. Now, let • be a binary noncommutative operator, i.e., a • b ≠ b • a. Each input to • must be labeled as to whether it is the left or right operand, as illustrated in Fig. 10.13(b). The left and right inputs are treated as implicit unary operators.

Figure 10.13. Multiplexer insertion for unary (a) and binary noncommutative (b) operators.

A binary commutative operator ο exhibits the property that a ο b = bοa, for all inputs a and b. The problem for binary commutative operators is illustrated by an example shown in Fig. 10.14. Eight DFGs are shown, along with an acyclic common supergraph. All of the DFGs share a binary commutative operator ο, that is represented by a vertex, also labeled ο, in the common supergraph. Consider DFG G₁ in Fig. 10.14, where ο has two predecessors labeled X and Y. Since ο is commutative, X and Y must be connected to multiplexers on the left and right inputs respectively, or vice versa. If they are both connected to the left input, but not the right, then it would be impossible to compute XοY. The trivial solution would be to connect X and Y to both multiplexers; however, this should be avoided in order to minimize, area, delay, and interconnect.

Figure 10.14. Eight DAGs and common acyclic supergraph sharing a binary commutative operator O.

The number of inputs connected to the left and right multiplexer should be approximately equal, if possible, since the larger of the two multiplexers will become the critical path through operator ο. S(k) = ⌈log₂ k⌉ is the number of selection bits for a multiplexer with k inputs. The area and delay of a multiplexer are monotonically increasing functions of S(k).

Fig. 10.15 shows two datapaths with multiplexers inserted corresponding to the common supergraph shown in Fig. 10.14. The datapath in Fig. 10.15(a) has two multiplexers with 3 and 5 inputs, respectively; the datapath in Fig. 10.15(b) has two multiplexers, both with 4 inputs. S(3) = S(4) = 2, and S(5) = 3. Therefore, the area and critical delay through the datapath in Fig. 10.15(a) will both be greater than the datapath in Fig. 10.15(b). Fig. 10.15(b) is thus the preferable solution.

Figure 10.15. Two solutions for multiplexer insertion for the supergraph in Fig. 10.14.

Balancing the assignment of inputs to the two multiplexers can be modeled as an instance of the maximum-cost induced bipartite subgraph problem, which is NP-complete [5]; a formal proof has been omitted. An undirected unweighted graph G_o =(V_o, E_o) is constructed to represent the input constraints on binary commutative operator ο. V_o is the set of predecessors of ο in the acyclic common supergraph.

An edge (u_o, v_o) is added to E_o if both u_o and v_o are predecessors of ο in at least one of the original DFGs. G_o for Fig. 10.14, is shown in Fig. 10.16(a). DFG G₁ from Fig. 10.14 contributes edge (X, Y) to G_o; G₂ contributes (V, Y); G₃ contributes (U, X); and so forth. Edge (u_o, v_o) indicates that u_o and v_o must be connected to the left and right multiplexers, or vice versa. Without loss of generality, if u_o is connected to both multiplexers, then v_o can trivially be assigned to either.

Figure 10.16. Graph G_o(a), corresponding to Fig. 10.14; induced bipartite subgraphs (b) and (c) corresponding to the solutions in Fig. 10.15(a) and (b), respectively.

A solution to the multiplexer insertion problem for ο is a partition of V_o into three sets (V_L, V_R, V_LR): those connected to the left multiplexer (V_L), those connected to the right multiplexer (V_R), and those connected to both multiplexers (V_LR). For every pair of vertices u_L, v_L ∊ V_L, there can be no edge (u_L, v_L) in E_o since an edge in E_o indicates that u_L and v_L must be connected to separate multiplexers; the same holds for V_R. The subgraph of G_o induced by V_L ∪ V_R is therefore bipartite. Fig. 10.16(b) and (c) respectively show the bipartite subgraphs of G_o in Fig. 10.16(a) that correspond to the datapaths in Fig. 10.15(a) and (b).

The total number of inputs to the left/right multiplexers are In_L = |V_L| + |V_LR| and In_R = |V_R| + |V_LR|. Since V_LR contributes to In_L and In_R, and all vertices not in V_LR must belong to either V_L or V_R, a good strategy is to maximize V_L ∪ V_R. This is effectively the same as solving the maximum-cost induced bipartite subgraph problem on G_o.

To minimize the aggregate area of both multiplexers, S(In_L)+ S(In_R) should be minimized rather than V_L ∪ V_R. To minimize the delay through ο, max{S(In_L), S(In_R)} could be minimized instead. To compute a bipartite subgraph, we use a simple linear-time breadth-first search heuristic [9]. We have opted for speed rather than solution quality because this problem must be solved repeatedly for each binary commutative operator in the supergraph.

The process of synthesizing a pipelined datapath from a common supergraph with multiplexers is straightforward. One resource is allocated to the datapath for each vertex in the supergraph. Pipeline registers are placed on the output of each resource as well. For each resource with a multiplexer on its input, there are two possibilities: (1) chain the multiplexer together with its resource, possibly increasing cycle time; and (2) place a register on the output of the multiplexer, thereby increasing the number of cycles required to execute the instruction. Option (1) is generally preferable if the multiplexers are small; if the multiplexers are large, option (2) may be preferable. Additionally, multiplexers may need to be inserted for the output(s) of the datapath.

Pipelining a datapath may increase the latency of an individual custom instruction, since all instructions will take the same number of cycles to go through the pipeline; however, a new custom instruction can be issued to the pipeline every clock cycle. The performance benefit arises due to increased overall throughput. To illustrate, Fig. 10.17 shows two DFGs, G₁ and G₂, a supergraph with multiplexers, G’, and a pipelined datapath, D. The latencies of the DFGs are 2 and 3 cycles, respectively (assuming a 1-cycle latency per operator); the latency of the pipelined datapath is 4 cycles.

Figure 10.17. Illustration of pipelined datapath synthesis.

High-level synthesis for a custom datapath for a set of DFGs and a common supergraph is quite similar to the synthesis process for a single DFG. First, a set of computational resources is allocated for the set of DFGs. The multiplexers that have been inserted into the datapath can be treated as part of the resource(s) to which they are respectively connected.

Second, each DFG is scheduled on the set of resources. The process of binding DFG operations to resources is derived from the common supergraph representation. Suppose that vertices v₁ and v₂ in DFGs G₁ and G₂ both map to common supergraph vertex v’. Then v₁ and v₂ will be bound to the same resource r’ during the scheduling stage. This binding modification can be implemented independently of the heuristic used to perform scheduling.

The register allocation stage of synthesis should also be modified to enable resource sharing. The traditional left edge algorithm [10] should be applied to each scheduled DFG. Since the DFGs share a common set of resources, the only necessary modification is to ensure that no redundant registers are inserted as registers allocated for subsequent DFGs. Finally, separate control sequences must be generated for each DFG. The result is a multioperational datapath that implements the functionality of the custom instructions represented by the set of DFGs.