Elena Dubrova

Structural Testing Based on Minimum Kernels

Structural testing techniques, such as statement and branch coverage, play an important role in improving dependability of software systems. However, finding a set of tests which guarantees high coverage is a time-consuming task. In this paper we present a technique for structural testing based on kernel computation. A kernel satisfies the property that any set of tests which executes all vertices (edges) of the kernel executes all vertices (edges) of the program's flowgraph. We present a linear-time algorithm for computing minimum kernels based on pre-and postdominator relations of a flowgraph.

Introduction

Software testing is the process of executing a program with the intent of finding errors [START_REF] Beizer | Software Testing Techniques[END_REF]. Testing is a major consideration in software development. In many organizations, more time is devoted to testing than to any other phase of software development. On complex projects, test developers might be twice or three times as many as code developers on a project team.

Thorough software testing is required for improving dependability of real-time computing applications using software-embedded systems. A number of serious accidents in the past has been caused by incomplete software testing, including the Therac-25 radiation overdoses [START_REF] Leveson | An investigation of the Therac-25 accidents[END_REF], the crash of the British destroyer Sheffield [START_REF] Lin | Sheffield hickups caused by software[END_REF], the accidents of Ariane 5 [START_REF] Lions | Ariane 5 flight 501 failure[END_REF] and Airbus A320-211 [START_REF]Report on the accident to Airbus A320-211 aircraft in Warsaw[END_REF].

There are two types of software testing: functional and structural. Functional testing (also called behavioral testing, black-box testing, closed-box testing), compares test program behavior against its specification. Structural testing (also called white-box testing, glass-box testing) checks the internal structure of a program for errors. For example, suppose we test a program which adds two integers. The goal of functional testing is to verify whether the implemented operation is indeed addition instead of e.g. multiplication. Structural testing does not question the functionally of the program, but checks whether the internal structure is consistent. A strength of the structural approach is that the entire software implementation is taken into account during testing, which facilitates error detection even when the software specification is vague or incomplete.

The effectiveness of structural testing is normally expressed in terms of test coverage metrics, which measure the fraction of code exercised by test cases. Common test coverage metrics are statement, branch, and path coverage [START_REF] Beizer | Software Testing Techniques[END_REF]. Statement coverage requires that the program under test is run with enough test cases, so that all its statements are executed at least once. Decision coverage requires that all branches of the program are executed at least once. Path coverage requires that each of the possible paths through the program is followed. Path coverage is the most reliable metric, however, it is not applicable to large systems, since the number of paths is exponential to the number of branches.

In this paper we present a technique for structural testing which finds a part of program's flowgraph, called kernel, with the property that any set of tests which executes all vertices (edges) of the kernel executes all vertices (edges) of the flowgraph. We present an linear-time algorithm for computing kernels of a minimum size based on pre-and post-dominator relations of a flowgraph.

A related previous work is an algorithm presented in [START_REF]Dominators, super blocks, and program coverage[END_REF]. First, it constructs pre-and post-dominator trees of the program's flowgraph. Then, both trees are combined and the resulting graph is reduced by merging its strongly connected components and eliminating composite edges implied by dominator transitivity. The obtained super block dominator graph represents kernels of the flowgraph.

The main difference between the presented algorithm and the algorithm [START_REF]Dominators, super blocks, and program coverage[END_REF] is that we compute only one minimum kernel for a given flowgraph instead of all possible ones, which clearly can be done with less computational effort. The presented O(|V | + |E|) algorithm computes minimum kernels directly from pre-and post-dominator trees of a flowgraph with |V | vertices and |E| edges, without constructing the super block dominator graph. We prove that the resulting kernel is minimum. No proof of minimality is given in [START_REF]Dominators, super blocks, and program coverage[END_REF].

Other related works include: Bertolino and Marre's algorithm [START_REF] Bertolino | Automatic generation of path covers based on the control flow analysis of computer programs[END_REF] for finding path covers in a flowgraph, in which unconstrained arcs are analogous to the leaves of the dominator tree; Ball's [START_REF] Ball | What's in a region?: or computing control dependence regions in near-linear time for reducible control flow[END_REF] and Podgurski's [START_REF] Podgurski | Forward control dependence, chain equivalence, and their preservation by reordering transformations[END_REF] techniques for computing control dependence regions in a flowgraph, which are similar to the super blocks of [START_REF]Dominators, super blocks, and program coverage[END_REF]; Agarwal's algorithm [START_REF]Efficient coverage testing using global dominator graphs[END_REF], whi addresses the coverage problem at an interprocedural level.

The paper is organized as follows. Section 2 gives an overview of coverage techniques. Section 3 states the preliminaries. In Section 4, kernels are introduced. Section 5 presents an algorithm for computing minimum kernels. Section 6 shows use of kernels in branch coverage. Section 7 concludes the paper.

Statement and Branch Coverage

In this section, we give a brief overview of statement and branch coverage techniques.

Statement Coverage

Statement coverage (also called line coverage, segment coverage [START_REF] Ntafos | A comparison of some structural testing strategies[END_REF], C1 [START_REF] Beizer | Software Testing Techniques[END_REF]) examines whether each executable statement of a program is followed during a test. An extension of statement coverage is basic block coverage, in which each sequence of non-branching statements is treated as one statement unit.

The main advantage of statement coverage is that it can be applied directly to object code and does not require processing source code. The disadvantages are:

• Statement coverage is insensitive to some control structures, logical AND and OR operators, and switch labels.

• Statement coverage only checks whether the loop body was executed or not. It does not report whether loops reach their termination condition. In C, C++, and Java programs, this limitation affects loops that contain break statements.

As an example of the insensitivity of statement coverage to some control structures, consider the following code:

x = 0; if (condition) x = x + 1; y = 10/x;
If there is no test case which causes condition to evaluate false, the error in this code will not be detected in spite of 100% statement coverage. The error will appear only if condition evaluates false for some test case. Since if-statements are common in programs, this problem is a serious drawback of statement coverage.

Branch Coverage

Branch coverage (also referred to as decision coverage, all-edges coverage [START_REF] Roper | Software Testing[END_REF], C2 [START_REF] Beizer | Software Testing Techniques[END_REF]) requires that each branch of a program is executed at least once during a test. Boolean expressions of if-or while-statements are checked to be evaluated to both true and false. The entire Boolean expression is treated as one predicate regardless of whether it contains logical AND and OR operators. Switch statements, exception handlers, and interrupt handlers are treated similarly. Decision coverage includes statement coverage since executing every branch leads to executing every statement.

An advantage of branch coverage is its relative simplicity. It allows overcoming many problems of statement coverage. However, it might miss some errors as demonstrated by the following example:

if (condition1) x = 0; else x = 2; if (condition2) y = 10*x; else y = 10/x;
The 100% branch coverage can be achieved by two test cases which cause both condition1 and condition2 to evaluate true, and both condition1 and condition2 to evaluate false. However, the error which occurs when condition1 evaluates true and condition2 evaluates false will not be detected by these two tests. The error in the example above can be detected by exercising every path through the program. However, since the number of paths is exponential to the number of branches, testing every path is not possible for large systems. For example, if one test case takes 0.1 × 10 -5 seconds to execute, then testing all paths of a program containing 30 ifstatements will take 18 minutes and testing all paths of a program with 60 if-statements will take 366 centuries.

Branch coverage differs from basic path coverage, which requires each basis path in the program flowgraph to be executed during a test [START_REF] Watson | Structured testing: Analysis and extensions[END_REF]. Basis paths are a minimal subset of paths that can generate all possible paths by linear combination. The number of basic paths is called the cyclomatic number of the flowgraph.

Preliminaries

A flowgraph is a directed graph G = (V, E, entry, exit), where V is the set of vertices representing basic blocks of the program, E ⊆ V × V is the set of edges connecting the vertices, and entry and exit are two distinguished vertices of V . Every vertex in V is reachable from entry vertex, and exit is reachable from every vertex in V .

Figure 2 shows the flowgraph of the C program in Figure 1, where bl, b2,...,b17 are blocks whose contents are not relevant for our purposes.

A vertex v pre-dominates another vertex u, if every path from entry to u contains v. A vertex v post-dominates another vertex u, if every path from u to exit contains v.

By Pre(v) and Post(v) we denote sets of all nodes which pre-dominate and post-dominate v, respectively. E.g. in Figure 2, Pre(5) = {1, 2, 3, 4} and Post(5) = {9, 10, 17}.

Many properties are common for pre-and postdominators. Further in the paper, we use the word dominator to refer to cases which apply to both relationships.

Vertex v is the immediate dominator of u, if v dominates u and every other dominator of u dominates v. Every vertex v ∈ V except entry (exit) has a unique immediate predominator (post-dominator), idom(v) [START_REF] Lowry | Object code optimization[END_REF]. For example, in Figure 2, vertex 4 is the immediate pre-dominator of 5, and vertex 9 is the immediate post-dominator of 5. The edges (idom(v), v) form a directed tree rooted at entry for predominators and at exit for post-dominators. Figures 3 and4 show the pre-and post-dominator trees of the flowgraph in Figure 2.

The problem of finding dominators was first considered in late 60's by Lorry and Medlock [START_REF] Lowry | Object code optimization[END_REF]. They presented an O(|V | 4 ) algorithm for finding all immediate dominators in a flowgraph. Successive improvements of this algorithm were done by Aho and Ullman [START_REF] Aho | The Theory of Parsing, Translating, and Compiling[END_REF], Purdom and Moore [START_REF] Purdom | Immediate predominators in a directed graph[END_REF], Tarjan [START_REF] Tarjan | Finding dominators in a directed graphs[END_REF], and Lengauer and Tarjan's [START_REF] Lengauer | A fast algorithm for finding dominators in a flowgraph[END_REF]. Lengauer and Tarjan's algorithm [START_REF] Lengauer | A fast algorithm for finding dominators in a flowgraph[END_REF] is a nearly-linear algorithm with the complexity O(|E|α(|E|, |V |)), where α is the standard functional inverse of the Ackermann function. Linear algorithms for finding dominators were presented by Harel [START_REF] Harrel | A linear time algorithm for finding dominators in flow graphs and related problems[END_REF], Alstrup et al. [START_REF] Alstrup | Dominators in linear time[END_REF], and Buchsbaum et al. [START_REF] Buchsbaum | A new, simpler linear-time dominators algorithm[END_REF].

Statement Coverage Using Kernels

In this section we present a technique for finding a subset of the program's flowgraph vertices, called kernel, with the property that any set of tests which executes all vertices of the kernel executes all vertices of the flowgraph. A 100% statement coverage can be achieved by constructing a set of tests for the kernel.

Definition 1 A vertex v ∈ V of the flowgraph is covered by a test case t if the basic block of the program representing v is reached at least once during the execution of t.

The following Lemma is the basic property of our technique, as well as the technique presented in [START_REF]Dominators, super blocks, and program coverage[END_REF].

Lemma 1 If a test case t covers u ∈ V , then it covers any post-dominator of u as well: (t covers u) ∧ (v ∈ Post(u)) ⇒ (t covers v).

Proof: If v post-dominates u, then every path from u to exit contains v. Therefore, if u is reached at least once during the execution of t, then v is reached, too. Figure 3: Pre-dominator tree of the flowgraph in Figure 2; shaded vertices are leaves of the tree in Figure 4.

Definition 2 A kernel K of a flowgraph G is a subset of vertices of G which satisfies the property that any set of tests which executes all vertices of the kernel executes all vertices of G.

Let L post (L pre ) denote the set of leaf vertices of the post-(pre-)dominator tree of G. The set L D post ⊂ L post contains vertices of L post which pre-dominate some vertex of L post :

L D post = {v | (v ∈ L post ) ∧ (v ∈ Pre(u) for some u ∈ L post )}.
Similarly, the subset L D pre ⊂ L pre contains all vertices of L pre which post-dominate some vertex of L pre :

L D pre = {v | (v ∈ L pre ) ∧ (v ∈ Post(u) for some u ∈ L pre )}.
Assume that the program execution terminates normally on all test cases supplied. Then the following statement holds.

Theorem 1 The set L post -L D

post is a minimum kernel.

Proof: Lemma 1 shows that, if a vertex of a flowgraph is covered by a test case t, then all its post-dominators are also covered by t. Therefore, in order to cover all vertices of a flowgraph, it is sufficient to cover all leaves L post in its post-dominator tree, i.e. L post is a kernel. L D post contains all vertices of L post which pre-dominate some vertex of L post . If v is a pre-dominator of u, and u is covered by t, then v is also covered by t, since every path from entry to u contains v as well. Thus, any set of tests which covers L post -L D post , covers L post as well. Since L post is a kernel, L post -L D post is a kernel, too. Next, we prove that the set L post -L D post is a minimum kernel. Suppose that there exists another kernel, K , such Figure 4: Post-dominator tree of the flowgraph in Figure 2; shaded vertices are leaves of the tree in Figure 3.

that |K | < |L post -L D post |. If v ∈ K and v ∈ L post , then v ∈ Post(u)
for some u ∈ L post . Since every path from u to exit contains v, if u is reached at least once during the execution of some test case, then v is reached, too. Therefore, K remains a kernel if we replace v by u.

Suppose we replaced all v ∈ K such that v ∈ L post by u ∈ L post such that v ∈ Post(u). Now, K ⊆ L post . If there exists w ∈ L post -K such that, for all u ∈ K , w ∈ Pre(u) then there exists at least one path from entry to each u which does not contain w. This means that there exists a test set, formed by the set of paths path(u) where path(u) is the path to u which does not contain w, that covers K but not w. According to Definition 2, this implies that K is not a kernel. Therefore, to guarantee that K is a kernel, w must be a pre-dominator of some u ∈ K , for all w ∈ L post -K . This implies that |K | = |L post -L D post |.

2

The next theorem shows that the set L pre -L D pre is also a minimum kernel.

Theorem 2 |L post -L D post | = |L pre -L D pre |.
The proof is done by showing that the proof of minimality of Theorem 1 can be carried out starting from L pre .

Computing Minimum Kernels

In this section, we present an linear-time algorithm for computing minimum kernels. The pseudo-code is shown in Figure 5. The procedure FINDLD is applied to the smaller of the sets L pre and L post .

FINDLD checks whether the leaves L pre of the tree T pre are dominated by some vertex of L pre in another tree, T post , or vice versa. In other words, FINDLD computes the set L D pre (L D post ).

2

As an example, let us compute a minimum kernel for the flowgraph in Figure 2. Its pre-and post-dominator trees are shown in Figures 3 and4. T pre has 7 leaves, L pre = {7, 8, 12, 14, 15, 16, 17}, and T post has 9 leaves, L post = {1, 3, 6, 7, 8, 11, 13, 14, 15}. So, we check which of the leaves of T pre dominates at least one other leaf of T pre in T post . Leaves L pre are marked as shaded circles in T post in Figure 4. We can see that, in T post , vertex [START_REF] Purdom | Immediate predominators in a directed graph[END_REF]

Decision Coverage Using Kernels

The kernel-based technique described above can be similarly applied to branch coverage by constructing pre-and post-dominator trees for the edges of the flowgraph instead of for its vertices. Figures 6 and7 show edge pre-and postdominator tree of the flowgraph in Figure 2.

Similarly to Definition 2, a kernel set for edges is defined as a subset of edges of the flowgraph which satisfies the property that any set of tests which executes all edges of the kernel executes all edges of the flowgraph. A 100% branch coverage can be achieved by constructing a set of tests for the kernel. Minimum kernels for Figures 6 and7 are: L pre -L D pre = {i, h, k, p, q,t, v, w, x, y} and L post -L D post = { f , g, k, n, p, q,t, w, x, y}.

Conclusion

In this paper we present a technique for structural testing based on kernel computation. A kernel has the property that any set of tests which executes all vertices (edges) of the kernel executes all vertices (edges) of the program's flowgraph. For large programs, the number of statements and branches to be covered by tests might be prohibitive. Kernels allow us to reduce the amount of test cases to be constructed while preserving a 100% coverage. We present a linear-time algorithm for computing kernels of a minimum size based on pre-and post-dominator relations of a flowgraph.

Future work includes investigating how properties of dominators can be further exploited. One possibility is to apply the presented algorithm to testing of finite state machines (FSMs). Similarly to program coverage, a state or a transition of the FSM is considered covered if it is visited during the execution of the input test sequence [START_REF] Tasiran | Coverage metrics for functional validation of hardware designs[END_REF]. Dominator relations can be used to identify kernels for FSM's states/transitions.

Figure 1 :

 1 Figure 1: Example C program.

Figure 2 :

 2 Figure 2: Flowgraph of the program in Figure 1.

Figure 5 :

 5 Figure 5: Pseudo-code of the algorithm for computing minimum kernels.

Theorem 3

 3 The algorithm KERNEL computes a minimum kernel of a flowgraph G = (V, E, entry, exit) in O(|V | + |E|) time. Proof: The correctness of the algorithm follows directly from Theorems 1 and 2. The complexity of the KERNEL is determined by the complexity of computing the T pre and T post trees. A dominator tree can be computed in O(|V | + |E|) time [20]. Thus, the overall complexity is O(|V | + |E|).

  dominates 12 and 14, and vertex 17 dominates all other leaves of L pre . Thus, L D pre = {16, 17}. The minimum kernel L pre -L D pre consist of five vertices: 7,8,12,14 and 15. For a comparison, let us compute the minimum kernel given by L post -L D post . The L post leaves are marked as shaded circles in T pre in Figure 3. We can see that, in T pre , vertex 6 dominates 7 and 8, vertex 3 dominates 6, 7 and 8, vertex 13 dominates 14, and vertex 1 dominates all other leaves of L post . Thus, L D post = {1, 3, 6, 13}. The minimum kernel L post -L D post consist of five vertices: 7,8,11,14 and 15. It is easy to see from the flowgraph why vertices 11 and 12 are interchangeable in two minimum kernels.

Figure 6 :Figure 7 :

 67 Figure 6: Edge pre-dominator tree of the flowgraph in Figure 2; shaded vertices are leaves of the tree in Figure 7.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgments

I am indebted to the anonymous reviewer who gave many valuable comments over the manuscript and suggested improvements in the proof of the Theorem 1.

This work was supported in part by the Research Grant 2002-4300 from the Swedish Research Council Vetenskpsrådet.


Srinivasan Murali
email: smurali@stanford.edu

Giovanni De Micheli

An Application-Specific Design Methodology for STbus Crossbar Generation

Keywords: Systems on Chips, Networks on Chips, crossbar, bus, application-specific, SystemC

As the communication requirements of current and future Multiprocessor Systems on Chips (MPSoCs) continue to increase, scalable communication architectures are needed to support the heavy communication demands of the system. This is reflected in the recent trend that many of the standard bus products such as STbus, have now introduced the capability of designing a crossbar with multiple buses operating in parallel. The crossbar configuration should be designed to closely match the application traffic characteristics and performance requirements. In this work we address this issue of application-specific design of optimal crossbar (using STbus crossbar architecture), satisfying the performance requirements of the application and optimal binding of cores onto the crossbar resources. We present a simulation based design approach that is based on analysis of actual traffic trace of the application, considering local variations in traffic rates, temporal overlap among traffic streams and criticality of traffic streams. Our methodology is applied to several MPSoC designs and the resulting crossbar platforms are validated for performance by cycle-accurate SystemC simulation of the designs. The experimental case studies show large reduction in packet latencies (up to 7×) and large crossbar component savings (up to 3.5×) compared to traditional design approaches.

Introduction

As the number of processor/memory cores and the number and size of applications run on Multiprocessor Systems on Chips (MPSoCs) increase, the communication between the cores will become a major bottleneck. Traditional communication architectures, such as single shared or bridged buses are inherently non-scalable and will not be able to support the heavy communication traffic [START_REF] Benini | Networks on Chips: A New SoC Paradigm[END_REF]. A communication-centric design approach, Networks on Chips (NoCs), has recently emerged as the design paradigm for designing a scalable communication infrastructure for MPSoCs [START_REF] Benini | Networks on Chips: A New SoC Paradigm[END_REF].

The need for scalable communication architectures is reflected in the recent trend that many of the standard bus products, such as the STbus R (from STMicroelectronics) have now introduced the capability of designing a crossbar with multiple buses operating in parallel, thus providing a low-latency and highbandwidth communication infrastructure. The communication architecture for the design should closely match the application traffic characteristics and performance requirements. As an example, let us consider a 21-core MPSoC running a set of matrix multiplication benchmarks (detailed explanation of the MPSoC and experimental set-up is presented in later sections). We consider three different communication architectures using STbus interconnection platform: a shared bus, a full crossbar and a partial crossbar. In Table 1, we present the average and maximum latency incurred by the packets, obtained from SystemC simulation of the design using these platforms and the size of the crossbars (in terms of number of components used) normalized with respect to the size of the shared bus. As seen from the table, as expected, both average and maximum packet latency is much higher for a single shared bus than the partial or full crossbars. However, it is interesting to note that an optimal partial crossbar gives almost the same performance as a full crossbar, even though it uses fewer resources than a full crossbar. A smaller crossbar configuration results in reduction in number of communication components used (such as buses, arbiters, adapters, etc), design area and design power.

In this research we target the design of the optimal STbus crossbar configuration for a given application, satisfying the performance characteristics of the application. The proposed design methodology is based on actual functional traffic analysis of the application, and the generated crossbar configuration is validated by cycle-accurate SystemC simulation of the application using that crossbar. Most previous works on bus generation and NoC topology generation (which are somewhat similar to crossbar generation) are either based on average communication traffic flow between the various cores or based on statistical traffic generating functions. While the former approaches fail to capture local variations in traffic patterns (as the average bandwidth of communication is a single metric that is calculated based on the entire simulation time), the latter approaches are only based on approximations to the functional traffic.

Our design methodology differs from the existing approaches in the fact that, it is based on the analysis of simulated traffic patterns in windows, considering local variations in the communication traffic and reducing the tem-poral overlap among traffic streams mapped onto the same resource. Moreover, our methodology is based on the actual traffic characteristics of the application obtained from SystemC simulations and the designed crossbar configuration is also validated by cycle-accurate simulations. Even though our design approach is fine-tuned for STbus crossbar architecture, it can be easily modified for other crossbar architectures as well. Several experimental case studies on MPSoC designs show large reduction in packet latencies (up to 7×) and large network component savings (up to 3.5×) compared to traditional design approaches.

Previous Work

A component-based design methodology for SoC design is presented in [START_REF] Cesario | Component-Based Design Approach for Multi-Core SoCs[END_REF]. The synthesis and instantiation of single bus and multiple bridged buses has been explored in many research works such as [START_REF] Yen | Communication synthesis for distributed embedded systems[END_REF], [START_REF] Daveau | Synthesis of system-level communication by an allocation based approach[END_REF], [START_REF] Gasteier | Bus-based communication synthesis on system level[END_REF], [START_REF] Ryu | Automated Bus Generation for Multiprocessor SoC Design[END_REF]. In [START_REF] Lahiri | Design Space Exploration for Optimizing On-Chip Communication Architectures[END_REF], the authors present an approach for mapping the system's communication requirements and optimizing the communication protocols for a given communication architecture template. In [START_REF] Lahiri | Design of High-Performance System-on-Chips using Communication Architecture Tuners[END_REF], the use of communication architecture tuners to adapt to runtime variability needs of a system is presented.

The need for scalable communication architectures and a communication centric design paradigm, Networks on Chips (NoCs), is presented in [START_REF] Benini | Networks on Chips: A New SoC Paradigm[END_REF]. A large body of research such as [START_REF] Guerrier | A generic architecture for on-chip packet switched interconnections[END_REF], [START_REF] Kumar | A network on chip architecture and design methodology[END_REF], [START_REF] Rijpkema | Trade-offs in the design of a router with both guaranteed and best-effort services for networks on chip[END_REF], [START_REF] Bertozzi | NoC Synthesis Flow for Customized Domain Specific Multiprocessor Systems-on-Chip[END_REF], focus on developing design tools and architectures for NoCs. A detailed survey of many of the NoC research works is presented in [START_REF] Jantsch | Networks on Chip[END_REF]. Mapping of communication requirements of a system onto a fixed set of NoC topologies is explored in [START_REF] Hu | Energy-Aware Mapping for Tile-based NOC Architectures Under Performance Constraints[END_REF], [START_REF] Hu | Exploiting the Routing Flexibility for Energy/Performance Aware Mapping of Regular NoC Architectures[END_REF], [START_REF] Murali | Bandwidth Constrained Mapping of Cores onto NoC Architectures[END_REF], [START_REF] Murali | SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs[END_REF].

In [START_REF] Pinto | Constraint-Driven Communication Synthesis[END_REF] design methodologies for application-specific bus design and in [START_REF] Pinto | Efficient Synthesis of Networks on Chip[END_REF], [START_REF] Murali | SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs[END_REF], for application-specific NoC topology design are presented. These works are based on average communication transferred between the various cores. In [START_REF] Ho | A Methodology for Designing Efficient On-Chip Interconnects on Well-Behaved Communication Patterns[END_REF], designing application-specific topologies based on actual simulation traces in presented. However, the methodology is based on eliminating contention and can lead to over-sizing of network components, as even a small amount of overlap between two traffic streams would result in the need for separate communication resources for them. In [START_REF] Bolotin | QNoC: QoS architecture and design process for Network on Chip[END_REF], the analysis is based on statistical traffic generators and not functional application traffic.

In this work, our design methodology is based on actual functional traffic of the application. We divide the entire simulation period into a number of fixed-sized windows. Within each window, we guarantee that the application communication requirements (such as the bandwidth requirements) are met. We minimize the overlap among traffic streams mapped onto the same resource, thereby reducing the latency for data transfer. We also consider the criticality and real-time requirements of streams and guarantee that the performance constraints (such as bandwidth and delay constraints) for these streams are met. Our methodology spans an entire design space spectrum with the analysis based on average communication traffic (as done in many previous works) and on peak bandwidth (as done in [START_REF] Ho | A Methodology for Designing Efficient On-Chip Interconnects on Well-Behaved Communication Patterns[END_REF]) being the two extreme design points. Thus our methodology also applies to cases where application traces are not available and only rough estimates of the traffic flows between the various cores is known. The design point in the spectrum is varied by controlling the window size used for the traffic analysis and design, which is explained further in Section 7.2.

Problem Definition and Analysis

Problem Definition

The STbus can be instantiated in three ways: as a shared bus, a partial crossbar or a full crossbar. The partial and full crossbars are actually composed of many buses to which the processor/memory cores are connected (refer Figure 1). Two separate STbus crossbars are instantiated for a design: one for the communication from initiators (masters) to targets (slaves) and the other for communication from targets to initiators. The initiator-target partial and full crossbars are shown in Figure 1. In this crossbar, all initiators are connected to all buses of the crossbar and one or more targets are connected onto every bus. There are additional interface components: arbiters and frequency/data width adapters (not shown in the figure for clarity) that facilitate the interconnection of heterogeneous processor and memory cores onto the bus. The target-initiator crossbar has a similar structure.

The type and size of crossbar needed for an application should closely match the traffic characteristics and performance requirements of the application. A full crossbar, although provides the best performance in terms of minimizing communication latency or maximizing communication throughput, results in a large increase in the number of network components used, design area and power. Note that the size of the two crossbars (the initiator-target and the target-initiator) can be different.

Application Traffic Analysis

In this subsection, we explore the traffic characteristics of applications and formulate the performance constraints to be satisfied by the crossbar designed for the system. As an example, we consider the 21-core matrix multiplication In this example, there are 9 ARM cores, their private memories, a shared memory for inter-processor communication, a semaphore memory for maintaining locks for shared memory accesses and an interrupt device. The ARM cores act as initiators and the memory cores act as targets. The ARM cores run a set of pipelined matrix multiplication benchmarks that involve accesses to their private memory and inter-processor communication through the shared memory. We performed a cycle-accurate simulation of the system with full STbus initiator-target and target-initiator crossbars. A small trace of the traffic to three of the targets is shown in Figure 2(b).

Even though the aggregate traffic (measured over the entire simulation period) to the three targets is lower than that can be supported by a single bus, using a single bus to connect all three targets will lead to high average and peak latency due to overlap in traffic patterns during some regions of the simulation. Another related point is that if overlap are not considered, connecting targets 1 and 2 on to the same bus is better than connecting targets 1 and 3 onto the same bus, as the former results in lower bandwidth needs. However, the latter solution will result in better performance (reduced latency) while still satisfying the bandwidth needs. Note that using peak bandwidth instead of the average bandwidth will solve this problem, but lead to an over-design of the crossbar (in terms of number of buses needed or their frequency of operation). The design methodology needs to consider overlap among the various traffic streams into account and should consider local variations in traffic rates. Moreover, the designed crossbar should be such that, while minimizing the average latency, should also minimize the maximum latency that any packet or traffic stream can incur. Also, some of the traffic streams can be more critical than the others and such real-time traffic streams need to be given guaranteed real-time performance.

Design Methodology

The design flow for the crossbar design is shown in Figure 3. The application is initially designed using full crossbar for initiator-target and target-initiator communication and a SystemC simulation of the design is carried out. For the simulations, we use the MPARM simulation environment [START_REF] Loghi | Analyzing On-Chip Communication in a MPSoC Environment[END_REF] that allows interconnection of ARM cores to several interconnection platforms (such as AMBA, STbus, ...) and to perform cycle accurate simulations for a variety of benchmark applications. We present here only the design of the initiator-target crossbar, as the target-initiator crossbar can be designed in a similar fashion.

To effectively capture local variations in traffic patterns and to perform overlap calculations, we define a windowbased traffic analysis. The entire simulation period is divided into a number of windows and the traffic characteristics to the various targets in each window are obtained. The traffic characteristics recorded include: the amount of data received by each target in every window, amount of pairwise overlap between the traffic streams to the targets in every window, the real-time requirements of traffic streams, etc. Without loss of generality, in the rest of the paper we assume that all the windows are of equal size, although the methodology also applies to windows with varying sizes. The size of the window is parameterizable and depends on the application characteristics and performance requirements. The effect of the window size on the quality of the solution is explored in Section 7.2.

After the data collection phase, a pre-processing phase is carried out in which the targets that have large overlap in any window and need to be put on different buses are identified. In this phase, the overlapping critical streams that need to be on separate buses are also identified. The maximum number of targets that can be connected to a single bus, to bound the maximum latency, is also identified in this phase.

In the next phase, the optimal crossbar configuration for the application, satisfying the performance constraints is obtained. To generate the optimal crossbar configuration, we use the traffic information collected in each window and check whether the bandwidth, overlap and criticality constraints are satisfied in each window.

In the final phase, the resulting crossbars are instantiated in the MPARM environment and SystemC simulations are carried out.

Problem Formulation

In this section we formulate the mathematical models of the crossbar design problem. 1 . The amount of data overlap (in number of cycles) between every pair of targets (t i , t j ) in each window m is represented by wo i,j,m .

The overlap between every pair of targets t i and t j , over the entire simulation period is obtained by summing the overlap between them in all the windows and represented by the entries of the overlap matrix OM :

om i,j = m wo i,j,m : ∀i, j (1)
In the pre-processing step of the design flow (refer Figure 3), those pair of targets that have overlap exceeding the threshold value (which is parameterizable) in any window are identified. By placing such targets onto separate buses, the maximum and average latency of data transmission can be reduced and in some cases can also speed up the process of finding the optimal crossbar configuration. The effect of this pre-processing step is explored in detail in Section 7.3. Also in this pre-processing step, the real-time traffic streams that overlap with each other in any window are identified. Such targets with overlapping real-time streams should not be placed on the same bus as real-time communication guarantee to the streams cannot be given in this case. We define the set of all targets that cannot be on the same bus by the conflict matrix:

c i,j = 1 , if t i & t j should be on different buses 0 , otherwise : ∀i, j (2)
We model the performance constraints that need to be satisfied by the crossbar configuration in each window as constraints of a Mixed Integer Linear Program (MILP).

Definition 3

The set X represents the set of binding variables x i,k , such that x i,k is one when target t i is connected to the bus b k and zero otherwise.

In the STbus crossbar, each target has to be connected to a single bus (while a single bus can connect multiple targets, as shown in Figure 1(a)). This is implemented by the following constraint:

k x i,k = 1 : ∀i (3)
In every window of the traffic analysis, the individual buses in the crossbar have to support the traffic through them in that window. By evaluating the bandwidth constraints over a smaller sample space of a window (which is typically few thousand cycles) instead of the entire simulation sample space (which can be millions of cycles) we are better able to track the local variations in the traffic characteristics. This window-based bandwidth constraint is represented by the equation:

i comm i,m × x i,k ≤ W S : ∀k, m (4)

Definition 4

The set SB represents the set of sharing variables sb i,j,k , such that sb i,j,k is one when targets t i and t j share the same bus b k and zero otherwise. The set S represents the set of sharing variables s i,j , such that s i,j is one when targets t i and t j share any of the buses of the crossbar and zero otherwise.

The sb i,j,k can be computed as a product of x i,k and x j,k . However, this results in non-linear (quadratic) equality constraints. To break the quadratic equalities into linear inequalities, we use the following set of equations:

sb i,j,k ∈ {0, 1} x i,k + x j,k -1 ≤ sb i,j,k 0.5 x i,k + 0.5 x j,k ≥ sb i,j,k : ∀i, j, k (5)
and the s i,k are computed using the equation:

s i,j = k sb i,j,k : ∀i, j (6)
The condition that certain targets are forbidden to be on the same bus, obtained from Equation 2, is represented by: c i,j × s i,j = 0 : ∀i, j

As the number of targets onto a single bus increases, even for traffic streams that don't have substantial overlap, the maximum latency that can be incurred by a packet/traffic stream can increase substantially. In the worst case, packets to all the targets onto a bus can arrive in the same cycle, which need to be serialized on the bus, thereby making the maximum latency incurred by packets to some of the targets higher. In order to reduce the maximum delay that can be incurred by any packet, we can restrict the maximum number of targets that can be connected to the same bus below a threshold (maxtb) that is parameterizable. This is represented by the following constraint:

i x i,k ≤ maxtb : ∀k (8)
The fact that all the integer variables introduced above take values of either 0 or 1 only, is represented by:

x i,k , s i,j , c i,j ∈ {0, 1} : ∀i, j, k

Crossbar Design Algorithm

The algorithm for the STbus crossbar design has two major steps: the first is to find the minimum crossbar configuration that satisfies the performance constraints (that were presented in the above section) and the second step is to find the optimal binding of the targets to the chosen crossbar configuration.

In order to find the best crossbar configuration, all possible configurations are tested in a binary search manner to find the minimum configuration that satisfies the performance constraints that were modeled as MILP constraints in the previous section.

The following MILP is tested for a feasible solution for each configuration until the best configuration is obtained: obj: Feasibility Analysis subject to Equations ( 3) to ( 9). [START_REF] Lahiri | Design of High-Performance System-on-Chips using Communication Architecture Tuners[END_REF] Note that the MILP has no objective function as the aim is to just test for feasibility.

Once the best crossbar configuration is obtained, in the next step, the optimal binding of the targets onto buses of the crossbar is obtained. A binding of targets to the buses that minimizes the amount of overlap of traffic on each bus will result in lower average and peak latency for data transfer. For this, the above MILP is solved with the objective of reducing the maximum overlap on each of the bus, and satisfying the performance constraints, as follows: min: maxov s.t.

i j om i,j × sb i,j,k ≤ maxov : ∀k and subject to Equations (3) to ( 9).

By splitting the problem into two MILPs, we speed up the execution time of the algorithm as solving MILP1 for feasibility check is usually faster than solving the MILP2 with objective function and additional constraints. The MILPs are solved using the CPLEX package [START_REF]ILOG CPLEX[END_REF]. The runtime of the algorithm for all our simulation studies was under few hours, when run on a 1GHz SUN machine. The runtime for the MILP is not that large as the largest possible STbus crossbar size (and maximum number of targets) is 32 and hence the number of integer variables is less than few thousand. flows (as done in previous approaches), by relaxing overlap constraints and using a single window for analysis. The SystemC simulation of the applications were carried out on the STbus platform using the designed crossbars. We briefly analyze here the quality of the crossbar design obtained for the matrix multiplication benchmark, Mat2 (refer Figure 2). In this benchmark, there are 9 initiators and 12 targets. Of the 12 targets, accesses to 3 of the targets (the shared memory, semaphore memory and interrupt device) is much lower than the accesses to private memories, as these are only used for inter-processor communication.

Experiments and Case Studies

There is substantial temporal overlap between the traffic flows from the various ARM cores to their private memories, as the ARM cores perform similar computations and thus access their memories at almost the same time. In order to satisfy the window bandwidth constraints, only few of them can share a single bus. Our methodology, when applied to this benchmark, results in the use of 3 buses for the initiator-target crossbar. Each of the bus has 3 private memories and one of the common memories connected to it. Moreover, the bindings are such that, the targets with highly overlapping streams are placed on different buses, an important design constraint explained in detail in Section 3.2. As a result, the designed crossbar has acceptable performance (in terms of average and maximum latency constraints) with 3.5× reduction in the number of buses used, when compared to a full crossbar. The average and maximum packet latencies for the applications obtained from the simulations, normalized with respect to the latencies incurred in a full crossbar system, are presented in Figures 4(a) and 4(b). As seen from the figure, the latencies incurred by crossbar designs based on average traffic flows are 4× to 7× higher than the crossbars designed using our scheme. Also, the latencies incurred in the designs generated by our scheme are within acceptable bounds from the minimum possible latencies (of a full crossbar). Moreover, depending on the design objective, crossbar size-performance trade-offs can be explored in our approach by tuning the analysis parameters (such as the window size, overlap threshold, etc.), as explained in the next subsections. In Table 2, we compare the number of buses used in the crossbar designed by our approach with that of full crossbar for the applications. We get large reduction (up to 3.5×) in the crossbar size by using our design approach.

Window Sizing

The size of the window used during the design process is an important parameter that determines the efficiency of the design methodology to capture the application performance parameters. A small window size results in much finer control of the application performance parameters and the resulting crossbars have lower latencies. However, a very small window size will lead to over-design of the network components. On the other hand, a large window size results in lesser control over the performance parameters of the application, but results in a more conservative design approach where higher packet latencies can be tolerated.

To illustrate these effects, we applied our design methodology with different window sizes for a synthetic benchmark with 20 cores. The typical burst sizes (we refer to a burst as a stream of packets generated by the same core) for the benchmark were around 1000 cycles. When the window size is much smaller than the burst size, the size of the crossbar generated is very close to that of a full crossbar (refer Figure 5(a)). When the window size is around few times that of the burst size (from 1-4 times), crossbar designed by our approach has much smaller size (typically around 25%) and acceptable latencies (around 1.5×) of that of a full crossbar. For aggressive designs, the window size can be set closer to the burst size and for conservative designs (where larger packet latencies can be tolerated), the window size can be set to few times the typical burst size. The acceptable window sizes for various burst sizes is presented in Figure 5(b). It can be seen from the plot that the window size varies almost linearly with the burst size, consolidating the above arguments.

Real-Time Streams & Effect of Binding

In each simulation window, the critical traffic streams that require real-time guarantees are recorded. During the pre-processing step of the design flow (refer Figure 3), the real-time traffic streams that overlap with each other in any window are identified. In order to provide real-time guarantees to such streams, in our methodology the cores with the overlapping critical streams are placed on separate buses of the crossbar. Experimental results on the benchmark applications show a very low packet latency (almost equal to the latency of perfect communication using a full crossbar) for such streams.

After finding the best crossbar configuration, we do an optimal binding of the cores onto the buses of the crossbar, minimizing the total overlap on each bus. By minimizing the overlap on each bus, the packet latencies reduce significantly. To illustrate this effect, we compare the crossbars designed using our approach with two binding schemes: random binding of cores onto the buses, satisfying the design constraints (Equations 3-9) and optimal binding that minimizes overlap on each bus, satisfying the design constraints. The average latency incurred by the random binding scheme for the benchmark applications was on an average 2.1× higher than that incurred by the optimal binding scheme.

Overlap Threshold Setting

By varying the three parameters: window size, overlap threshold and maximum number of targets (or initiators) on a bus, the crossbar can be designed such that the average and, more so, the maximum packet latencies incurred in the design are acceptable. The effect of the overlap threshold parameter on the size of the initiator-target crossbar generated for the synthetic benchmark is presented in Figure 6. The plots end at 50% overlap between targets because, if the pair-wise overlap between two targets exceeds 50% of the window size (in any of the windows), then the window bandwidth constraints cannot be satisfied. So, the maximum value of the overlap parameter can be set at 50% of the slot size. This will also speed-up the process of finding the best crossbar configuration, as such overlapping targets will be identified in the pre-processing phase (refer Figure 3) and will be forbidden to be on the same bus of the crossbar. From experiments, we found that for aggressive designs (where there are tight requirements on the maximum latencies) the threshold can be set to around 10% and for conservative designs, the threshold can be set to 30%-40% of the window size.

Conclusions and Future Work

To accommodate the growing communication demands of Multiprocessor Systems on Chips (MPSoCs), scalable communication architectures and related design methodologies are needed. In this work, we have presented a design methodology for designing the optimal crossbar configuration for an application and for binding the cores onto the crossbar resources. Our design approach is based on a simulation window-based analysis of the application traces, considering the local variations in traffic rates, temporal overlap among traffic patterns and criticality of traffic streams. The methodology has several parameters that can be tuned to explore the design space of the crossbar design and to match the application characteristics. The design methodology, though fine-tuned to STbus crossbar architecture, can be easily extended to other crossbar architectures as well. Several experimental studies show large reduction in latency and crossbar components usage, compared to traditional design approaches. In future, we plan to analyze the effect of using variable simulation window sizes for the design for guaranteeing Quality-of-Service (QoS) for applications.

  Figure 1. STbus crossbars

Figure 2 .

 2 Figure 2. Application Traffic Analysis

Figure 3 .

 3 Figure 3. Design Methodology application shown in Figure2(a). In this example, there are 9 ARM cores, their private memories, a shared memory for inter-processor communication, a semaphore memory for maintaining locks for shared memory accesses and an interrupt device. The ARM cores act as initiators and the memory cores act as targets. The ARM cores run a set of pipelined matrix multiplication benchmarks that involve accesses to their private memory and inter-processor communication through the shared memory. We performed a cycle-accurate simulation of the system with full STbus initiator-target and target-initiator crossbars. A small trace of the traffic to three of the targets is shown in Figure2(b).Even though the aggregate traffic (measured over the entire simulation period) to the three targets is lower than that can be supported by a single bus, using a single bus to connect all three targets will lead to high average and peak latency due to overlap in traffic patterns during some regions of the simulation. Another related point is that if overlap are not considered, connecting targets 1 and 2 on to the same bus is better than connecting targets 1 and 3 onto the same bus, as the former results in lower bandwidth needs. However, the latter solution will result in better performance (reduced latency) while still satisfying the bandwidth needs. Note that using peak bandwidth instead of the average bandwidth will solve this problem, but lead to an over-design of the crossbar (in terms of number of buses needed or their frequency of operation). The design methodology needs to consider overlap among the various traffic streams into account and should consider local variations in traffic rates. Moreover, the designed crossbar should be such that, while minimizing the average latency, should also minimize the maximum latency that any packet or traffic stream can incur. Also, some of the traffic streams can be more critical than the others and such real-time traffic streams need to be given guaranteed real-time performance.

Definition 1 Definition 2

 12 The set of all targets is represented by the set T . The set of all windows used for traffic analysis is represented by the set W , with the length of each window (in terms of number of cycles) represented by W S. The set of buses used in the crossbar is represented by the set B. The number of cycles that each target t i , ∀i ∈ 1 .. |T |, receives data in every window m, ∀m ∈ 1.. |W |, is represented by comm i,m

7. 1

 1 Application Benchmark AnalysisWe applied our design methodology for crossbar design of several MPSoCs: Matrix suite-1 (Mat1-25 cores), Matrix suite-2 (Mat2-21 cores), FFT suite (FFT-29 cores), Quick Sort suite (QSort-15 cores) and DES encryption system (DES-19 cores). For comparison purposes, we also designed crossbars based on average communication traffic

Figure 4 .

 4 Figure 4. Application relative latencies

Figure 6 .

 6 Figure 5. Effect of window size variations

Table 1 . Crossbar Performance and Cost

 1

	Type	Average	Maximum Size
		Lat (in cy) Lat (in cy) Ratio
	shared	35.1	51	1
	full	6	9	10.5
	partial	9.9	20	4

Table 2 . component savings

 2

	Appli	Full	Designed Ratio
	cation crossbar	crossbar
		bus count bus count
	Mat1	25	8	3.13
	Mat2	21	6	3.5
	FFT	29	15	1.93
	QSort	15	6	2.5
	DES	19	6	3.12

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

In the rest of this paper we follow the convention that variables i and j are defined for 1..|T |, variable k is defined for 1..|B| and m for 1..|W |.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgements

This research is supported by MARCO Gigascale Systems Research Center (GSRC) and the US National Science Foundation (under contract CCR-0305718).


D Maslov

C Young

D M Miller
email: mmiller@uvic.cagdueck@unb.ca

G W Dueck

Quantum Circuit Simplification Using Templates

Optimal synthesis of quantum circuits is intractable and heuristic methods must be employed. Templates are a general approach to reversible and quantum circuit simplification. In this paper, we consider the use of templates to simplify a quantum circuit initially found by other means. We present and analyze templates in the general case, and then provide particular details for circuits composed of NOT, CNOT and controlled-sqrt-of-NOT gates. We introduce templates for this set of gates and apply them to simplify both known quantum realizations of Toffoli gates and circuits found by earlier heuristic Fredkin and Toffoli gate synthesis algorithms. While the number of templates is quite small, the reduction in quantum cost is often significant.

Introduction

Research in quantum circuit synthesis is motivated by the growing interest in quantum computation [START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF] and advances in quantum circuit technology [START_REF]IBM's test-tube quantum computer makes history[END_REF][START_REF] Aaronson | Multilinear formulas and skepticism of quantum computing[END_REF]. Even for circuits with only a few variables, it is at present intractable to find an optimal circuit. Thus a number of heuristic synthesis methods have emerged. Application of these methods usually results in a non-optimal circuit specification, which can be later simplified using local optimization techniques.

Local optimization has only recently been considered as a possible tool for the simplification of quantum [START_REF] Lomont | Quantum circuit identities[END_REF][START_REF] Viamontes | Graph-based simulation of quantum computation in the state-vector and density-matrix representation[END_REF] and reversible circuits [START_REF] Iwama | Transformation rules for designing CNOT-based quantum circuits[END_REF]. While those works provide several rewriting rules, there is clearly a benefit to systemizing the approach through a method such as the templates discussed in this paper. A somewhat different approach for local optimization of reversible NOT-CNOT-Toffoli circuits was applied for the simplification of random reversible circuits in [START_REF] Shende | Scalable simplification of reversible logic circuits[END_REF]. That approach and our template method are very different in that they have different metrics for the circuit cost, use different types of gates, and are applied to different types of circuits. This makes it difficult to compare the methods. However, we believe that our method is more general and will be more scalable.

Templates have been considered for Toffoli [START_REF] Maslov | Simplification of Toffoli networks via templates[END_REF] and Toffoli-Fredkin [START_REF] Maslov | Fredkin/Toffoli templates for reversible logic synthesis[END_REF] reversible network simplification. In this paper, we revisit the definition of templates and show how they can be applied in the quantum case.

Background

We present a short review of the basic concepts of quantum computation necessary for this paper. For a more detailed introduction, please see [START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF].

The state of a single qubit is a linear combination α|0 + β|1 (also written as a vector (α, β)) in the basis {|0 , |1 }, where α and β are complex numbers called the amplitudes, and |α| 2 + |β| 2 = 1. Real numbers |α| 2 and |β| 2 represent the probabilities p and q of reading the 'pure' logic states |0 and |1 upon measurement. The state of a quantum system with n > 1 qubits is given by an element of the tensor product of the single state spaces and can be represented as a normalized vector of length 2 n , called the state vector. Quantum system evolution allows changes of the state vector through multiplication by the appropriate 2 n × 2 n unitary matrices.

The above models how a transformation can be performed, but does not indicate how to identify the unitary matrices that compose the transformation or how to implement them. Typically, certain primitive gates are used as elementary building blocks with an assumed unit cost [START_REF] Barenco | Elementary gates for quantum computation[END_REF][START_REF] Hung | Quantum logic synthesis by symbolic reachability analysis[END_REF][START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF]. Among these are:

• NOT (x → x) and CNOT ((x, y) → (x, x ⊕ y)) gates; • Hadamard gate defined by H = 1 √ 2 1 1
1 -1 ; • controlled-V gate that depending on the value on its control line changes the value on the target line using the transformation given by the matrix V = i+1 • controlled-V + that depending on the value of its control line changes the value on the target line using the transformation

V + = V -1 ; • rotation gates R(γ), γ ∈ [0, 2π].
The controlled V and V + gates can be seen to be controlled-sqrt-of-NOT gates since

V 2 = (V + ) 2 = 0 1 1 0
which is the transformation matrix for NOT. Note that once a gate is available, its inverse is also available with the same cost. This observation will be useful when considering the templates and their application to quantum circuit simplification.

The Toffoli gate [START_REF] Toffoli | Reversible computing[END_REF] and its generalization with more than two controls serve as a good basis for synthesis purposes as shown by several authors [START_REF] Jha | Reversible logic synthesis[END_REF][START_REF] Kerntopf | A new heuristic algorithm for reversible logic synthesis[END_REF][START_REF] Miller | A transformation based algorithm for reversible logic synthesis[END_REF]. The generalized Toffoli gate, which for simplicity we refer to simply as a Toffoli gate, is defined as follows: Definition 1. For the set of Boolean variables {x 1 , x 2 , ..., x n } the Toffoli gate has the form T OF (C; T ), where

C = {x i 1 , x i 2 , ..., x i k }, T = {x j } and C ∩ T = ∅. It maps each pattern (x + 1 , x + 2 , ..., x + n ) to (x + 1 , x + 2 , ..., x + j-1 , x + j ⊕ x + i 1 x + i 2 ...x + i k , x + j+1 , ..., x + n ).
C is called the control set and T is called the target.

Unfortunately, Toffoli gates are not simple transformations in quantum technology. Rather they require a number of quantum gates and Toffoli gates with a large number of controls can be quite costly [START_REF] Barenco | Elementary gates for quantum computation[END_REF][START_REF] Maslov | Improved quantum cost for n-bit Toffoli gates[END_REF]. In this paper, we apply templates to the best known quantum circuits implementing large Toffoli gates resulting in significant simplification. This is very useful since it allows simpler quantum realization of the circuits reported by authors who have used Toffoli gates with large control sets. Definition 2. An n-input, n-output Boolean function is reversible if it maps each of the 2 n input patterns to a unique output pattern.

Clearly, a reversible function f has an inverse (f -1 ). Each of the gates noted above implements a reversible function and thus there is a corresponding inverse gate. NOT, CNOT, and Toffoli gates are self-inverse. V and V + are the inverses of each other. The situation for rotation gates is more complex and is not considered here as we have not employed rotation gates in our work so far. Quantum circuits of necessity implement reversible functions.

We shall write G -1 to denote the gate implementing the inverse function of the function realized by gate G. In context, we will use G to mean a gate or the transformation matrix for that gate. The symbol ⊕ will be used in diagrams to denote a NOT gate.

Templates: definition

A Rewriting rule is a procedure that takes two equivalent (computing the same function) circuits and replaces one with the other. If the cost of the replacement circuit is less than the cost of the replaced circuit, this leads to a circuit cost reduction. Templates are a generalization of this idea.

Often, the cost of a circuit is defined simply as a, possibly weighted, gate count. We term this a linear cost metric. In the case of a non-linear cost metric (such as those used in [START_REF] Hung | Quantum logic synthesis by symbolic reachability analysis[END_REF][START_REF] Smolin | Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate[END_REF]), it is necessary to consider the cost of the entire circuit as the overall cost can be affected by a local optimization. An example of such a situation arises when considering Peres gates [START_REF] Peres | Reversible logic and quantum computers[END_REF] (defined by the transformation (a, b, c) → (a, b ⊕ a, c ⊕ ab)) which, when implemented by a quantum Toffoli gate T OF (a, b; c) followed by a CNOT gate T OF (a; b) would have a cost of 5 + 1 = 6, whereas a Peres gate can be directly constructed with 4 elementary quantum blocks.

We call a rewriting rule regular if the replacement circuit has smaller cost than the replaced circuit, otherwise we call it irregular. The idea of applying regular rewriting rules to simplify sub-circuits of a given circuit has two phases. First, find as many regular rewriting rules as possible, and second, apply them to reduce the cost of a given circuit. Direct application of such an approach to quantum circuit cost reduction can be found in [START_REF] Lomont | Quantum circuit identities[END_REF]. However, we see the following potential problems with that particular approach: • The number of regular rewriting rules is very large even for small parameters. For instance, in the case of the quantum gates listed above, the number of regular rewriting rules is infinite if no proper classification is presented and rotation gates with any parameter γ are allowed.

• Often, rewriting rules are redundant in the sense that a

G 1 G 2 G 3 → G 4 G 5 rewriting rule is a derivative of G 2 G 3 → G 5 rewriting rule if G 1 = G 4 .
• It often happens that interchanging the order of the gates, which sometimes is possible and itself does not change the cost of a circuit, may result in allowing a rewriting rule application that decreases the cost of the circuit.

We employ templates as a means to address the above problems while maintaining the advantages of rewriting rules. The following observations are beneficial to the understanding of templates:

Observation 1. For any circuit G 0 G 1 ... G m-1 realizing a reversible function f , circuit G -1 m-1 G -1 m-2 ... G -1 0 is a real- ization for f -1 . Observation 2. For any rewriting rule G 1 G 2 ... G k → G k+1 G k+2 ... G k+s its gates satisfy the following: G 1 G 2 ... G k G -1 k+s G -1 k+s-1 ... G -1 k+1 = I. Proof.
The following set of equalities constructed using the rule GG -1 = I for a single gate G proves the statement.

G 1 G 2 ... G k = G k+1 G k+2 ... G k+s G 1 G 2 ... G k G -1 k+s G -1 k+s-1 ... G -1 k+1 = G k+1 G k+2 ... G k+s G -1 k+s G -1 k+s-1 ... G -1 k+1 G 1 G 2 ... G k G -1 k+s G -1 k+s-1 ... G -1 k+1 = I. Observation 3. For an identity G 0 G 1 ... G m-1 and any parameter p, 0 ≤ p ≤ m -1, G 0 G 1 ...G p-1 → G -1 m-1 G -1 m-2 ... G -1
p is a rewriting rule. In the most trivial circuit cost metric, when the cost of every gate is assumed to be one (that is, the simple gate count is used), the rewriting rule is regular for parameters p in the range m 2 < p ≤ m -1. Proof. Proof of this statement follows from the previous one by renaming the subscripts and listing the equalities in the reverse order.

Observation 4. If G 0 G 1 ... G m-1 = I, then G 1 ... G m-1 G 0 = I.
Proof. The following proves the statement.

G 0 G 1 ... G m-1 = I G -1 0 G 0 G 1 ... G m-1 = G -1 0 I G 1 ... G m-1 = G -1 0 G 1 ... G m-1 G 0 = G -1 0 G 0 G 1 ... G m-1 G 0 = I. Definition 3.
A size m template is a sequence of m gates (a circuit) that realizes the identity function. Any template of size m must be independent of all templates of smaller or equal size, i.e. for a given template T of size m no application of any set of templates of smaller size can decrease the number of gates in T or make it equal to another template. The template G 0 G 1 ... G m-1 can be applied in two directions: Forward application is a rewriting rule of the form

G i G (i+1) mod m ... G (i+p-1) mod m → G -1 (i-1) mod m G -1 (i-2) mod m ... G -1 (i+p) mod m , where 0 ≤ i, p ≤ m -1.

Backward application is a rewriting rule of the form

G -1 i G -1 (i-1) mod m ... G -1 (i-k+1) mod m → G (i+1) mod m G (i+2) mod m ... G (i-k) mod m , where 0 ≤ i, p ≤ m -1.
Note, that template application requires the inverse be available for each gate type considered. Correctness of this definition follows from the four observations above.

A clear benefit of templates is the reduction of the number of rewriting rules and the consequent storage saving. In fact, one template occupies the same storage space as a single rewriting rule but is capable of storing up to 2m 2 nonredundant rewriting rules. Assuming the trivial circuit cost metric where each gate has a cost of one, the number of regular non-redundant rewriting rules can be as high as m 2 for odd m and m(m -1) for even m. For basic gate sets where the number of non-redundant rewriting rules is infinite or grows exponentially (for instance, using Toffoli gates with multiple controls results in an exponential growth of the number of rewriting rules), further compaction through classification is required. Depending on the form of the basic gates the classification approaches may vary [START_REF] Maslov | Fredkin/Toffoli templates for reversible logic synthesis[END_REF][START_REF] Maslov | Simplification of Toffoli networks via templates[END_REF].

The following Lemma is useful as it allows for a decrease in the number of gates that must be matched in order for a template to be applied as a regular rewriting rule.

Lemma 1. Assume a trivial cost metric where the cost of a circuit is calculated as a linear term with unit weights. Then, application of a template G 0 G 1 ... G m-1 for a parameter p = p 0 is equivalent to its application for parameter p = p 1 := m 2 +1 and p 0 -p 1 applications of an AA -1 template.

Proof. For simplicity, assume that the template G 0 G 1 ... G m-1 is applied forward for parameter i = 0, that is, starting with the gate G 0 . Then, for the parameter p = p 1 , the sequence of gates G 0 G 1 ... G p1-1 in the circuit to be simplified can be moved together and will be replaced with

G -1 m-1 G -1 m-2 ... G -1
p1 . For j = 0, 1, 2, ... and while p 0p 1j > 0 gate G p 1 +j can be moved to G -1 p 1 and the gate-inverse rule applies to delete them both. It can be easily seen that after p 0p 1 such applications of gate-inverse rules the circuit will take the form equivalent to the one achieved by application of G 0 G 1 ... G m-1 for parameter p = p 0 .

Templates: application

To identify templates, we first find all templates of the form ABAB. Such templates applied for parameter p = 2 result in construction of the rewriting rule AB → BA. That is, they define when the two gates can be moved past each other. We call such templates moving rules and apply them to move gates to form matches leading to reduction via other templates.

Second, we find all templates of the form AA -1 , which we call gate-inverse rules. This is straightforward as well, since every self-inverse gate A forms the template AA and every pair of gates A and B, where B = A -1 forms one template of the form AB.

Subsequent templates are found by identifying increasingly longer sequences of gates that realize the identity function and which can not be reduced by other templates.

As a general approach, we provide a complete classification of the templates of small size and then supplement those by a set of templates that appear to be useful when a specific synthesis procedure is applied. For example, if a synthesis procedure tends to use a specific type of subcircuit of cost µ which is neither optimal (assume an optimal cost of ν) nor can be simplified by a small size complete set of templates, a template with total cost µ + ν can be created using Observation 2 (followed by a generalization process when and if needed). In this paper, we do not construct any of these supplementary type templates, since we focus on using templates when any synthesis algorithm is used to find the initial circuit.

We now illustrate a set of quantum templates using NOT, CNOT and controlled-sqrt-of-NOT gates. We first describe the moving rule. Assuming gate A has control set C A (C A is an empty set in the case of an uncontrolled gate) and tar- 1, where V (or V + ) is substituted for all occurrences of V 0 and V + (or V ) is substituted for all occurrences of V 1 , i.e. the substitutions is consistent and distinct for V 0 and V 1 . The templates reported here were found by inspection. We are currently developing a program to find larger templates and to verify completeness. When applying templates, the smaller ones are tried first. This means that more general (smaller) rewriting rules are used first after which more specific rules are considered.

To illustrate how templates are applied, consider the example of a non-optimal quantum circuit for the 3-bit full adder with 10 gates which in a non-linear metric yields a final cost of 9 [START_REF] Hung | Quantum logic synthesis by symbolic reachability analysis[END_REF]. The original circuit presented in [START_REF] Hung | Quantum logic synthesis by symbolic reachability analysis[END_REF] does not appear to be correct since for the input pattern 0100 it gives 1111 as output instead of the expected 1011. The circuit shown in Figure 2A corrects this.

In the circuit in Figure 2A, gates 5 and 7 (counting from the left) can be moved together and form a gate-inverse pair. We move them together and delete them by applying the gate-inverse template. This results in the circuit in Figure 2B. Next, we notice that gates 4, 6 and 8 in this circuit can also be brought together (gates 4 and 8 should be moved towards gate 6). They match gates 5,1 and 2 in the rightmost upper template in Figure 1. Figure 2C shows the three gates brought together, and Figure 2D illustrates the resulting circuit after the template is applied.

The circuit that we found using templates simplification (Figure 2D) is the optimal (for a given input-to-output assignment) reported in [START_REF] Hung | Quantum logic synthesis by symbolic reachability analysis[END_REF]. It took our program 1.16 seconds (elapsed time) to simplify the circuit in Figure 2A into the circuit in Figure 2D. The time reported in [START_REF] Hung | Quantum logic synthesis by symbolic reachability analysis[END_REF] to synthesize such a circuit is 7 hours. This example clearly shows that templates are useful and effective.

A likely optimal quantum circuit for the 3-bit full adder can be constructed from the reversible implementation presented in [START_REF] Miller | A transformation based algorithm for reversible logic synthesis[END_REF] and shown in Figure 3A. We first substitute quantum circuits for the Peres gates (each of which is a Toffoli-CNOT pair) see Figure 3B, and then apply the templates. In this case, gates 4 and 6 can be moved together and match the gate-inverse template. So, they are both deleted leading to the circuit in Figure 3C.

¡ ¢ £ ¤ ¥ ¦ § ¦ © ¦ ¦ © ¦ © ¦ ¦ ¦ © ¦ © ¦ ¢ ¥ ¦ ¦ © ¦ © ¦ ¡ ¢ £ ¤ ¥ ! ¨¦ ¦ © ¦ © ¦ " ¢ ¥

Experimental results

Even though the set of gates NOT, CNOT, controlled-V and controlled-V + has been used by several authors [START_REF] Barenco | Elementary gates for quantum computation[END_REF][START_REF] Hung | Quantum logic synthesis by symbolic reachability analysis[END_REF][START_REF] Maslov | Improved quantum cost for n-bit Toffoli gates[END_REF][START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF] as elementary building blocks, there are not many quantum circuits reported. However, there are a number of reversible circuits [START_REF] Aaronson | Multilinear formulas and skepticism of quantum computing[END_REF][START_REF] Kerntopf | A new heuristic algorithm for reversible logic synthesis[END_REF][START_REF] Maslov | Reversible logic synthesis benchmarks page[END_REF][START_REF] Maslov | Fredkin/Toffoli templates for reversible logic synthesis[END_REF][START_REF] Miller | A transformation based algorithm for reversible logic synthesis[END_REF][START_REF] Mishchenko | Logic synthesis of reversible wave cascades[END_REF] using generalized Toffoli and Fredkin [START_REF] Fredkin | Conservative logic[END_REF] gates. Generalized Fredkin gates can be implemented as a circuit containing two CNOT gates and one generalized Toffoli gate [START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF]. The generalized Toffoli gate itself can be realized as a circuit with CNOT, controlled-V and controlled-V + gates [START_REF] Barenco | Elementary gates for quantum computation[END_REF][START_REF] Maslov | Improved quantum cost for n-bit Toffoli gates[END_REF]. Thus, any Fredkin-Toffoli reversible circuit can be transformed into a circuit using elementary quantum NOT, CNOT, controlled-V and controlled-V + gates.

To develop our general synthesis approach, we first consider quantum circuits for the generalized Toffoli gates and apply our templates to simplify them. Having done that, to simplify a given reversible circuit we: substitute Toffoli-CNOT equivalents for any Fredkin gates; substitute simplified quantum implementations for the Toffoli gates; and apply the templates to obtain a reduced quantum specification.

Table 1 summarizes the results of applying our templates to quantum Toffoli gate implementations [START_REF] Barenco | Elementary gates for quantum computation[END_REF][START_REF] Maslov | Improved quantum cost for n-bit Toffoli gates[END_REF] gate, the number of auxiliary lines associated with the particular implementation of this gate, and the gate count in the best reported quantum circuit with CNOT, controlled-V and controlled-V + gates. We show the gate counts for our optimized implementations and the percentage the size of the optimized circuit represents with respect to the size of the best previously reported realization.

The results in Table 1 show that the set of Toffoli gate size (m+1) realizations with implementation cost of 16m-32 and garbage lines (m -2) (for m > 3) are always simplified to size 12m -22 circuits. We conjecture this will always be the case.

We next consider the derivation of quantum circuits from Toffoli/Fredkin gate circuits. One of the main obstacles in such an approach is that given a Toffoli gate, there are multiple ways of substituting an equivalent quantum circuit. First, Toffoli gates are symmetric with regard to their control variables, while the corresponding quantum circuits are not. For m controls, this results in m! substitutions. In addition, the quantum realization of a Toffoli gate T OF (x 1 , x 2 , ..., x m ; x m+1 ) in an n-line circuit, uses k auxiliary lines (assuming m + k + 1 ≤ n). This gives (nm -1)-choose-k ways of assigning auxiliary lines for the quantum implementations to the remaining lines in the circuit. Also, since a Toffoli gate is self-inverse, but its quantum realizations are not symmetric circuits, the number of possible substitutions is doubled. Finally, each size (m + 1) Toffoli gate has two basic quantum realizations [START_REF] Barenco | Elementary gates for quantum computation[END_REF][START_REF] Maslov | Improved quantum cost for n-bit Toffoli gates[END_REF] one with only 1 garbage line and the other with (m -2) garbage lines. This very large search space requires a heuristic be used.

We first observe that quantum circuits for Toffoli gates of size (m + 1) that require (m -2) garbage lines are less costly and better structured. Thus, it is easier to come up with a good procedure for substituting these gates in the circuit to yield the most simplification. We use this implementation rather than using the implementation with just 1 garbage line which is more expensive. We further substitute the circuits for the Toffoli gates so that two neighboring Toffoli gates would share as many quantum gates as possible. Since this is not guaranteed to be the best way of replacing a Toffoli gate with a quantum circuit, we are now working on better ways of substituting the Toffoli gates as well as utilizing the quantum circuits for Toffoli gates which require only one auxiliary bit. Many reversible circuits have constant input values and garbage outputs. This typically results when a non-reversible function is mapped to a reversible one prior to synthesis as a reversible circuit. In these cases, we apply two additional procedures. First, we look at the beginning of the circuit for a gate whose control is an input constant. If such a gate can be moved to the beginning of the circuit one of two transformations applies. If the input constant controlling the gate is zero, the gate can be removed. If the input constant is one, the constant control of the gate can be deleted (assuming an uncontrolled gate has a lesser cost). The second procedure looks at the end of the circuit and for every gate with the target on a garbage output tries to move the gate to be the last gate affecting that output such that the output is not used after the gate is applied. Every such gate can be safely deleted from the circuit since we do not care about the resulting values on the garbage lines.

We took several circuits from [START_REF] Maslov | Reversible logic synthesis benchmarks page[END_REF] and compared their quantum realization costs before and after applying the above approach. Table 2 summaries the results. Different circuits for the same function are distinguished by the numbers that come after the # sign. Cost before and Garbage list the quantum gate count and number of garbage lines in the circuit to be simplified. It can be calculated that given a reversible circuit on n rails with Toffoli gates of maximal size M (M < n), the garbage overhead in our Toffoli gate substitution procedure is 2Mn -3 when this number is greater than zero and zero otherwise. Cost after shows the quantum gate count after reversible gates are substituted with their simplified quantum circuits and the resulting circuit is run through the template simplification process.

Finally we present a very good circuit for the 5-bit Grover oracle function 4mod5. It leaves the first four wires unchanged and inverts the last wire if, and only if, the first four wires represent an integer divisible by 5. We first found a Toffoli gate circuit using a synthesis method we are currently developing. We then applied the techniques described above. If we don't require that the first four lines pass the inputs unchanged, the circuit is as shown in Figure 4A the inputs are required to be passed through unchanged, the subcircuit in Figure 4B must be appended to the right of the circuit in Figure 4A.

Future work

There are several possibilities to improve our simplification approach. In addition to better substitution of quantum circuits for Toffoli gates and the search for new templates, we plan to adapt the templates tool for reversible circuits to minimize the quantum cost instead of the reversible gate count. This is expected to result in a better starting point for quantum cost reduction. We are also working on quantum gate level compaction, which should be possible to accomplish using the moving rule and its trivial extensions. Finally, we are interested in extending templates to other sets of quantum gates including rotation gates.

Conclusion

We have introduced templates for quantum circuit simplification. Templates can be developed for any type of quantum circuit, and can be applied for various cost metrics. We demonstrated the effectiveness of our approach using a variety of previously published circuits. In particular, we reduced the sizes of the best known Toffoli gate quantum realizations on average by 19.2% and the costs of a set of benchmark circuits on average by 30.2%.

Figure 1 .

 1 Figure 1. Quantum templates.

Figure 2 .Figure 3 .

 23 Figure 2. Simplification of a 10-gate quantum network for the 3-bit full adder.

Figure 4 .

 4 Figure 4. Circuit for the Grover oracle.

Table 1 . Toffoli gate simulations.

 1 . Columns Size, Garbage and Best reported show the size of the Toffoli

	Size Garbage	Best	Optimized	%
			reported implementation
	4	1	16	15	93.75%
	5	2	32	26	81.25%
	5	1	42	37	88.1%
	6	3	48	38	79.17%
	6	1	64	54	84.38%
	7	4	64	50	78.13%
	7	1	96	80	83.33%
	8	5	80	62	77.5%
	8	1	128	100	78.13%
	9	6	96	74	77.08%
	9	1	160	128	80%
	10	7	112	86	76.79%
	10	1	192	152	79.17%
	11	8	128	98	76.56%
	11	1	224	176	78.57%

Table 2 . Simplification of the benchmarks.

 2 . If

	Name	Garbage	Cost	Cost	%
			before after
	4mod5#1	4	24	15	62.5%
	4mod5#3	4	13	9	69.23%
	5mod5#1	8	184	128 69.57%
	5mod5#2	8	80	45	56.25%
	add3	2	12	6	50%
	mod1024adder	0	1975	1521 77.01%
	rd53#1	4	277	233 84.12%
	rd53#2	4	152	114	75%
	rd53#3	5	44	33	75%
	rd53#4	4	137	96	70.07%
	rd53#5	4	86	68	79.07%

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)