Umit Y Ogras
email: uogras@ece.cmu.edu

Radu Marculescu
email: radum@ece.cmu.edu

Energy-and Performance-Driven NoC Communication Architecture Synthesis Using a Decomposition Approach *

In this paper, we present a methodology for customized communication architecture synthesis that matches the communication requirements of the target application. This is an important problem, particularly for network-based implementations of complex applications. Our approach is based on using frequently encountered generic communication primitives as an alphabet capable of characterizing any given communication pattern. The proposed algorithm searches through the entire design space for a solution that minimizes the system total energy consumption, while satisfying the other design constraints. Compared to the standard mesh architecture, the customized architecture generated by the newly proposed approach shows about 36% throughput increase and 51% reduction in the energy required to encrypt 128 bits of data with a standard encryption algorithm.

Introduction

The main bottleneck in designing today's Systems-on-Chip (SoCs) comes from global interconnects. Besides the increasing complexity due to the growing number of devices on the same chip, global interconnects continue to cause severe synchronization errors, unpredictable delays and high power consumption. As a result, it has been suggested to replace these custom wires with structured on-chip networks [START_REF] Dally | Route packets, not wires: On-chip interconnection networks[END_REF][START_REF] Hemani | Network on Chip: An Architecture for Billion Transistor Era[END_REF][START_REF] Guerrier | A Generic Architecture for On-Chip Packet Switched Interconnections[END_REF].

Typical SoCs that implement the Network-on-chip (NoC) approach consist of a number of heterogeneous devices such as CPU or DSP cores, embedded memory and application specific components, that communicate using packet switching. The design of NoCs trades-off several important architectural choices, such as topology and routing strategy selection, mapping the target application to the network nodes, etc. We can conceive these architectural choices as representing a 3-D design space. The first dimension of this space is the design of the communication infrastructure, e.g. the topology of the network and the width of the channel links; this is analogous to designing the roads in a big city. The next degree of freedom comes from the selection of communication paradigm which can be based on deterministic, adaptive or stochastic routing strategies. This second dimension is analogous to following the actual paths, while driving in a city traffic. The final dimension is application mapping to the network nodes, which consists of placing the message source/sink pairs to network nodes with the objective of satisfying some design constraints (e.g. energy, performance). Consequently, mapping has a big impact on the communication traffic pattern.

Communication infrastructure is the usual starting point in the design process of an NoC. Due to simplicity, a regular (i.e. grid-like) topology is usually chosen and then, the application mapping and routing strategy selection are carried out concurrently to optimize one or more design constraints, such as energy [START_REF] Hu | Exploiting the Routing Flexibility for Energy/ Performance Aware Mapping of Regular NoC Architectures[END_REF][START_REF] Kreutz | Communication Architectures for System-On-Chip[END_REF][START_REF] Murali | SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs[END_REF]. The selection of the interconnect topology has a dramatic impact on the overall performance, area, and power consumption. Hence, constraining the network architecture to consider only regular topologies, while exploring the remaining two dimensions of the design space, produces sub-optimal operating points. Furthermore, varying sizes and shapes of the cores and large deviations in the communication requirements cause waste of silicon area and over-designed networks or performance bottlenecks [START_REF] Murali | SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs[END_REF][START_REF] Jalabert | xpipesCompiler: A Tool for instantiating application specific Networks on Chip[END_REF]. Since exhaustive design space exploration is prohibitive, a new design methodology that considers all three design dimensions and copes with the inherent complexity is clearly needed.

To this end, we propose a methodology for communicationbased customized topology synthesis. While there exists many different communication patterns in a network, certain generic communication primitives, such as gossiping (all-to-all communication), broadcasting (one-to-all) and multicasting (oneto-many) are encountered most frequently [START_REF] Hedetniemi | A survey of gossiping and broadcasting in communication networks[END_REF][START_REF] Hromkovic | Dissemination Of Information In Interconnection Networks (Broadcasting & Gossiping)[END_REF]. Our approach is based on decomposing the communication requirements' of the target application as a combination of communication primitives. After the decomposition step, these basic communication primitives are replaced by their optimal implementations. Finally, the customized topology is obtained by gluing the optimal implementations together, while satisfying the imposed design constraints.

We illustrate our methodology using some random benchmarks with various characteristics and a real application, the Advanced Encryption Standard (AES). For comparison purposes, the AES algorithm is implemented using a customized architecture generated by the proposed algorithm and a standard mesh architecture. The direct comparison of these two designs using an FPGA prototype shows 36% throughput increase and 51% reduction in the energy required to encrypt 128-bit blocks of data in favor of the customized architecture.

The remaining part of the paper is organized as follows: Section 2 reviews related work. The methodology and the implementation of the decomposition algorithm are explained in sections 3 and 4, respectively. Practical considerations and the experimental results appear in Section 5. Finally, Section 6 concludes the paper by summarizing our main contributions.

Related Work

There has been recent research on finding efficient ways to design NoCs [START_REF] Dally | Route packets, not wires: On-chip interconnection networks[END_REF][START_REF] Hemani | Network on Chip: An Architecture for Billion Transistor Era[END_REF][START_REF] Guerrier | A Generic Architecture for On-Chip Packet Switched Interconnections[END_REF][START_REF] Hu | Exploiting the Routing Flexibility for Energy/ Performance Aware Mapping of Regular NoC Architectures[END_REF][START_REF] Kreutz | Communication Architectures for System-On-Chip[END_REF][START_REF] Murali | SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs[END_REF][START_REF] Jalabert | xpipesCompiler: A Tool for instantiating application specific Networks on Chip[END_REF][START_REF] Pinto | Efficient Synthesis of Networks On Chip[END_REF]. In [START_REF] Pinto | Efficient Synthesis of Networks On Chip[END_REF], the authors present a constraintdriven communication architecture synthesis approach based on point-to-point communication specifications. The resulting architecture consists of optimized channels that are obtained by merging or separating the original point-to-point links. Topology selection for application-specific NoCs is discussed in [START_REF] Murali | SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs[END_REF]. The authors present a tool that maps the target application to several well-known topologies under various routing scenarios. The resulting designs are evaluated in terms of power, performance and area, and the one giving the best results is selected. Similarly, in [START_REF] Kreutz | Communication Architectures for System-On-Chip[END_REF] the authors specify the application in a simulation environment and generate its dynamic communication graph using simulation traces. Then, the application is mapped to several communication architectures to find the best alternative. Finally, theoretical studies [START_REF] Kreutz | Communication Architectures for System-On-Chip[END_REF][START_REF] Murali | SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs[END_REF][START_REF] Jalabert | xpipesCompiler: A Tool for instantiating application specific Networks on Chip[END_REF][START_REF] Pinto | Efficient Synthesis of Networks On Chip[END_REF] report simulation results rather than real implementations, We propose a systematic design methodology for fully customized topology generation, and support our theoretical analysis with direct experiments on a real application.

Overview of the Proposed Methodology

Generally speaking, it is known how to synthesize the topologies on which the aforementioned communication problems (i.e. broadcasting, gossiping, etc.) can be solved in optimum time. There exists, however, little or no idea about the optimal topology needed for solving a general communication problem. This situation is similar to the logic synthesis problem: The input communication pattern is similar to the uncommitted logic function given to a logic synthesis tool, while the communication primitives appear as standard cells.

To synthesize a customized topology, we decompose the communication requirements of a given application into a set of generic communication primitives, such as gossiping and broadcasting, which may be stored in a communication library. Each primitive in the library has a representation graph as shown in Figure 1. This graph structure is the pattern that the decomposition algorithm searches for when processing the input application graph. For example, gossiping among 4 nodes implies that each node sends its information to all of the remaining nodes and, at the same time, learns the cumulative message of the network. This is represented by a graph where there is a directed edge from all nodes to all other nodes (see the first graph in Figure 1).

The graphs on which broadcasting (and similarly gossiping) can be completed in minimum time with minimum number of edges are called Minimum Broadcast Graphs (MBG) and Minimum Gossip Graphs (MGG), respectively. These optimal implementations provide the maximum degree of parallelism by enabling the highest number of concurrent communications at minimum cost, as shown in Figure 1 (Note that, in this figure, it is assumed that any processor can participate in at most one communication transaction at any given time instance). These optimal implementations, i.e. MBGs and MGGs, are added as implementations graphs to the library. For standard configurations, such graphs are readily available in the literature [START_REF] Hedetniemi | A survey of gossiping and broadcasting in communication networks[END_REF].

After the decomposition step is completed, the communication primitives are replaced by their optimal implementations, and finally glued together to synthesize the customized architecture. As a result, the customized architecture naturally fits the communication requirements of the target applications.

Design of the Communication Library

The decomposition algorithm brakes down the input graph into a set of communication primitives stored in a library. Since the final decomposition and the run time of the algorithm itself depend on the primitives in the library, it is desirable to select the best set of graphs to be included in the library. While further research is needed in this area, we construct our current library using the minimum gossip and broadcast graphs that have efficient 2-D implementations and paths and loops of various sizes (Figure 1). This is due to several reasons: First, primitives consisting of a large number of edges will require more wiring resources which is limited by the metal layers allowed for global wires. Second, as the size of the primitives increases, it becomes less likely to detect these primitives in the input graph.

Energy Characterization of Implementation Graphs

We assume that, initially, each node in the implementation graph holds one bit of information, and stores the path(s) to send this bit to each of the remaining nodes. The energy con- sumed due to the transition of one bit of information from one network node to another node is defined as the bit energy (E bit ) [START_REF] Hu | Exploiting the Routing Flexibility for Energy/ Performance Aware Mapping of Regular NoC Architectures[END_REF] and it is given by where n hops is the number of hops, and E Sbit and E Lbit are the switch and link energy consumption, respectively. E S-bit values for different process technologies, voltage levels, operating frequencies are also stored in the library. Modelling E L-bit , on the other hand, requires more attention, since it depends on the link lengths which are not as easy to predict as for the regular grid structures. Hence, we assume that E L-bit per unit length is stored in the library and the E L-bit can be obtained from this data given the actual link length and also taking the repeaters into account. Finally, during the execution of the decomposition algorithm, the bit energy definition, the routing information and locations of the cores are used to determine the actual cost of a decomposition, as we describe in Section 4.2.

Graph Decomposition Algorithm

For simplicity, we assume that the target application is already mapped onto the processing cores and the communication volume between the cores is known. The application is specified by a graph , called Application Characterization Graph (ACG), where each vertex represents a core, and the directed edge e ij characterizes the data transfer from vertex i to vertex j. The communication volume and the required bandwidth from vertex i to vertex j are denoted by v(e ij ) and b(e ij ), respectively. Furthermore, we assume that an initial floorplanning step has been performed and optimized for chip area. Hence, the core coordinates are given as inputs to the algorithm.

Algorithm overview

We propose a depth-first search branch-and-bound algorithm to decompose an arbitrary input graph into a generic set of communication primitives. The algorithm first searches the input (application) graph for a subgraph that is isomorphic to one of the representation graphs in the library. After such a subgraph isomorphism (called a matching) is found, this subgraph is subtracted from the original graph. Subsequently, the same operation is recursively applied to the remaining graph until no matching can be found. For example, in the decomposition shown in Figure 2, the MGG-4 is first identified in the input graph and then subtracted from the input to obtain the remaining graph (see the left most branch in Figure 2). When it is no longer possible to find a subgraph isomorphism in the remaining graph, as is the case in this example, the algorithm stores the remaining graph, traces back to the previous level and continues with the next isomorphism from the library. In this example, a loop of size 4 is detected and the remaining graph looks like the middle branch in Figure 2. Since this graph does not have a subgraph isomorphic to any other graph in the library, the algorithm traces back again to the root of the tree. The final (right most) branch starts with a broadcast graph from one to three nodes. In this case, the remaining graph also has a subgraph isomorphic to one of the representation graphs in the library. Hence, the algorithm goes one level deeper and generates another possible decomposition.

In general, there will be more than one possible decompositions. For this reason, we associate a cost to each matching and, consequently, obtain a cost for each decomposition as explained in Section 4.3. For instance, in this simple example, the left most branch of cost 16 will be selected as the best decomposition of the initial graph.

Problem Formulation

We consider directed graphs, G(V,E), where V is the set of vertices and E is the set of edges. The algorithm uses graph addition, subtraction and subgraph isomorphism so, in the following, we provide some basic definitions. Given an input graph and a graph library L, the decomposition of G into L is specified by a subset of L, called The initial graph

E bit ij n hops E S-bit n hops 1 - + E L-bit = (1) G V E
G V G E G H V H E H A V E V V G V H = E E G E H = G V E S G V s E s R V R E R V R V = E R E E s - = V V G V E G E V e v i v j E = e f v i f v j E = e v i v j E = e f 1 -v i f 1 -v j E = f:V V G V E G E V S G L P 1 P 2 P n = M: V P V S P L C M :V V P R + G V E
D and the set of corresponding matchings. The input graph is given by where R(V R ,E R ) is a remainder graph which does not have a subgraph isomorphism with any communication primitives. The cost of the decomposition is given as For example, the cost of the leftmost decomposition, shown in Figure 2, is obtained by adding the costs for the matching M 1 and the remainder graph R as 16.

We denote the customized architecture obtained by connecting the implementation graphs of the communication primitives (Figure 1) in D, by and the mapping from the edges of the input graph to the edges in the implementation graphs by

, where is set of edges of ACG, and is set of edges of the implementation graph I. Let be the set of all possible decompositions. Problem Statement: Among all possible decompositions, find a decomposition , such that the total cost is minimized; that is, subject to the availability of wiring resources for the network links and the bandwidth requirements; that is, where . The former condition is checked by comparing the bisection bandwidth of the customized architecture with the maximum bisection bandwidth the particular technology provides for the network links. For example, for matching M 1 in Figure 2, edges e 13 and e 14 are both mapped to the edge in the implementation graph, since if vertex 1 needs to send a message to vertex 4, then it forwards the message to vertex 3 (the first graph in Figure 1). Hence, the bandwidth of should be larger than the sum of the bandwidth requirements of e 13 and e 14 . As a result, the left most branch in Figure 2 will be selected as the best solution provided that the constraints are satisfied.

Cost Assignment

Each path from the root to one of the leaves in the decomposition tree (see Figure 2) constitutes a natural decomposition of the input graph into the primitives. No matter which decomposition is chosen, the maximum number of hops between any two nodes (hence, the average hop number which directly impact the overall performance) in the customized architecture will be bounded by the largest diameter in the communication library. While each decomposition matches the communication requirements of the target application, quantifying the decompositions further is desirable both for selecting the best alternative and for reducing the search space by eliminating certain suboptimal branches. Since our goal is to select the architecture minimizing the total energy consumption, we select the energy consumption as the cost function.

The energy consumed due to the transportation of one bit of information from network node i to node j is given in Equation 1. Since the vertices of the ACG specify the communication volume between each pair of vertices, we can compute the total energy consumption of a matching M as where M imp is the set of edges in the implementation graph of the library component. Note that E bit is a function of the link length, l ij . Since we assume that the positions of the cores are determined by an initial floorplaning stage, the distances between all vertex pairs are known a priori. Hence, accurate E bit values can be imported from the library.

Details of the Decomposition Algorithm

The goal of the decomposition algorithm is to cover the input ACG with the set of library graphs resulting in the minimum total cost. We solve this minimization problem using a branch-and-bound algorithm as shown in Figure 3.

Initially, the cost of the covering is set to zero and the minimum cost achieved so far is set to infinity. The algorithm proceeds as explained in Section 4.2. The cost of each matching is computed using Equation 5, and when a complete decomposition is found (i.e. the algorithm reaches a leaf node), the cost of the decomposition is calculated with Equation 3. If this cost is smaller than the minimum cost obtained so far, the minimum cost is updated. In order to bound the search, we check the current cost of a decomposition and the minimum possible cost decomposing the remaining graph. If their sum is larger than the current minimum cost, the algorithm marks the cost of this branch as infinity and traces back to the previous level. Finally, the legal decomposition with minimum cost is selected as being the best decomposition.

G M i L i R V R E R + L i D = (2) C D C M i C R + L i D = ( 3
)
I V I E I f:E E I E e ij = E I e ij I = D C D min C D D , = (4)

The Routing Strategy

While the designer has complete freedom to select any deadlock-free routing strategy, we generate a routing table as a by-product of the topology synthesis algorithm using the following observation. We know the optimal strategies that allow broadcasting (also gossiping) on MBGs (MGGs) [START_REF] Hedetniemi | A survey of gossiping and broadcasting in communication networks[END_REF][START_REF] Hromkovic | Dissemination Of Information In Interconnection Networks (Broadcasting & Gossiping)[END_REF]. The numbers on the implementation graphs, in Figure 1, show how gossiping can be completed in minimum number of rounds. For example, for MGG-4, the nodes (1,3) and (2,4) exchange their information during the first round. After that, during the second round, nodes (1,2) and [START_REF] Guerrier | A Generic Architecture for On-Chip Packet Switched Interconnections[END_REF][START_REF] Hu | Exploiting the Routing Flexibility for Energy/ Performance Aware Mapping of Regular NoC Architectures[END_REF] exchange the information they learned so far. Hence, after two rounds every node knows the initial information of all other nodes. Knowing this optimal schedule, we can generate a routing table such that each vertex knows precisely how to send a message to the vertices it is not directly connected to in the implementation graph. In this example, if vertex 1 needs to send a message to vertex 4, then it will forward its message to vertex 3 first, since there exists an optimal schedule which delivers the information to vertex 4 using this route.

Each node in the ACG holds a table containing the nodes to which it can send a packet. This table is updated during the decomposition process such that the nodes keep track to which neighbor they should forward a given packet. The cycles that can cause deadlock can be detected and avoided by the algorithm, while it is also possible to eliminate such cycles by introducing virtual channels.

Experimental Results

Experiments with Random Graphs

A set of benchmarks generated using TGFF [START_REF] Dick | TGFF: Task Graphs For Free[END_REF] and Pajek [14] are used to evaluate the run time of the algorithm and illustrate the decomposition approach.

The largest run time obtained for TGFF is 0.3 seconds corresponding to an automotive industry benchmark consisting of 18 nodes, as shown in Figure 4a. Figure 4b shows the average run time obtained using more than 60 larger graphs generated by Pajek. While the average run times are longer for this case, the algorithm can still decompose a graph with 40 nodes in less than 3 minutes.

The current version of the proposed approach is implemented in Matlab. The branch-and-bound algorithm calls a subgraph isomorphism function based on VF2 [START_REF]ARG Database CD[END_REF] written in C++. The run-time of the algorithm can be improved in a number of ways. While the VF2 isomorphism algorithm works simultaneously on two graphs, approaches that consider a collection of model graphs (like our library) and generate a decision tree for faster identification of subgraph isomorphisms have been developed [START_REF] Messmer | A Decision Tree Approach to Graph and Subgraph Isomorphism Detection[END_REF]. Furthermore, the requirement for perfect matching can be relaxed and the graphs that are sufficiently close to each other can be detected [START_REF] Foggia | A Performance Comparison of Five Algorithms for Graph Isomorphism[END_REF]. Finally, the run time can increase drastically, if the input graph does not have a subgraph isomorphic to the graphs in the library, because the algorithm tries all different permutations before quitting. Hence, the search for the isomorphism can be terminated after a time-out period rather than trying all permutations. Example: In order to illustrate the architecture synthesis process more clearly, we show one randomly generated ACG (using Pajek) and its customized implementation as in Figure 5. While the communication patterns in the input graph are not easily detectable by eye inspection, the algorithm decomposes it into the primitives in less than 0.1 seconds:

The output starts with the ID of the communication primitive in the library and its label. For example, in the sample output shown above, the first match is a gossip graph of size 4, whose ID in the library is 1. The following three matches are broadcast graphs from one node to three nodes and the final match is another broadcast graph from one node to 4 four nodes. In this particular example, there is no remaining graph after these matches are found. The algorithm also outputs the mapping from the graph in the library to the isomorphic subgraph. For example, the mapping in the first line shows that the vertex 1 of MGG4 is mapped to v1 in the input graph. Similarly, vertices 2,3 and 4 are mapped to v2, v5 and v6, respectively. If we investigate these vertices in the input graph (Figure 5a), we can indeed observe the gossip graph shown in Figure 1.

Distributed Implementation of AES

We distributed the AES operations to a network of 16 identical nodes each processing one byte of the input block and obtained the application characterization graph shown in Figure 6a. Then, we generated a customized communication This decomposition shows that the algorithm successfully captures the all-to-all communication patterns within the columns of ACG. The first line of the output shows that the vertices 1, 2, 3, 4 of the library graph is mapped to the vertices 1, 5, 9, 13 of the input graph, which is the first column. Similarly, the other columns are also mapped to a gossip graph of size 4. The output also shows that the second and fourth rows are mapped to loops of size 4. Finally, the remaining subgraph after these matches (the third row) cannot be matched to any graph in the library. Hence, it is reported as the remaining graph.

The resulting architecture (Fig. 6b) and the standard mesh architecture have prototyped using a Virtex 2 based development board equipped with a XC2V4000 device. Both designs utilize roughly 32% of the device resources.

Prototype Performance and Energy Comparison

The chip throughput and average latency experienced by the packets in the network are utilized to measure and contrast the performance of the proposed architecture and the standard mesh architecture. The throughput is expressed as where cycles/block is the time needed to encrypt one block (128 bits) of input data. For the mesh configuration, we measured directly on the prototype cycles/block which gives Mbps at a clock frequency of 100Mhz. On the other hand, for the customized topology, we measured cycles/blocks, resulting in a increased throughput of Mbps. Similarly, there is a 17% reduction in latency. The mesh network causes 11.5 cycle average latency, while for the customized architecture the average latency is only 9.6 cycles.

We also measured the power consumption of the two designs with the Xpower utility of Xilinx, after placement and routing, using the actual simulation traces. We measured 33% reduction in the average power consumption compared to a standard mesh architecture. The energy consumed per 128-bit input block is the product of the time it takes to encrypt the block and the average power consumption during this period, i.e., . As such, the mesh architecture requires 5.1 J, while the customized architecture requires only 2.5 J to encrypt one block; this results in roughly 51% energy savings.

The AES algorithm enables us to demonstrate our approach and develop NoC prototypes based on customized and standard mesh implementations. However, due to its modest processing and communication requirements, AES is far from demonstrating the benefits of a networked implementation.

Conclusion and Future Work

In this paper, we presented a methodology for customized communication architecture synthesis. The communication requirements of the algorithm are decomposed into a set of frequently encountered communication primitives using an efficient branch-and-bound algorithm. The algorithm searches efficiently the entire design space for the architecture that minimizes the total energy consumption of the system while satisfying the other design constraints. The effectiveness of our methodology is illustrated using the AES algorithm and some random graphs.

There are several future research directions. For instance, it is possible to relax the initial floorplan information and solve the optimization problem for the general case. Also the possibility of using adaptive or stochastic routing strategies should be investigated.

Figure 1 .

 1 Figure 1. Sample graphs in the library and their optimal implementations.

Figure 2 .

 2 Figure 2. The illustration of the algorithm.

  input graph; currentCost = 0; minCost = inf; Best Decomposition = NetDecomp(I, minCost, currentcost); NetDecomp(I, minCost, currentcost) { For all Graphs in the Library G: if (a subgraph, S, in I is isomorphic to G) { RemainingGraph = I -S; currentCost = currentCost + cost of G; if (currentCost + minimum remaining cost < minCost) ndChild = NetDecomp(I, minCost, currentcost); else childCost = inf; nodeCost = cost of G + min(childCost); Check Constraints and Update minCost; } ndCost = Cost of the Remaining Graph; // None of the graphs in the library match to the input.

Figure 3 .

 3 Figure 3. The pseudo-code of the graph decomposition algorithm.

Figure 4 .Figure 5 .

 45 Figure 4. Run time of the algorithm for random graphs generated by TGFF (a) and Pajek (b)

Figure 6 .

 6 Figure 6. The ACG and customized network architecture. (a) (b)

  The communication library, , is the set of representation graphs of the communication primitives. A subgraph isomorphism from the input graph to one of the graphs in the library is called a matching and shown as .

	Definition 1 Given two graphs	and	,
	their sum is		such that	and
		.
	Definition 2 Given a graph	and one of its subgraphs
	, their difference is called the remaining graph,
	, such that	and
	Definition 3 A bijective function f:	is a graph iso-
	morphism from	to	if:
	1. For any edge		, there exists an edge
		.
	2. For any edge		, there exists an edge
			.
	An injective function	is a subgraph isomorphism
	from	to	if there exists a subgraph
				Finally,	a	cost,

such that f is a graph isomorphism from G to S. Definition 4 , is assigned to each matching, as explained in Section 4.3.

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

*This research is supported in part by CyLab ARO under grant no. 9097 and by MARCO/DARPA Gigascale Systems Silicon Center under grant no. 2003-DT-660.


Benoît Miramond
email: miramond@lami.univ-evry.fr

Jean-Marc Delosme
email: delosme@lami.univ-evry.fr

Lami

Design space exploration for dynamically reconfigurable architectures

By incorporating reconfigurable hardware in embedded system architectures it has become easier to satisfy the performance constraints of demanding applications while lowering system cost. In order to evaluate the performance of a candidate architecture, the nodes (tasks) of the data flow graphs that describe an application must be assigned to the computing resources of the architecture: programmable processors and reconfigurable FPGAs, whose run-time reconfiguration capabilities must be exploited. In this paper we present a novel design exploration tool-based on a local search algorithm with global convergence properties-which simultaneously explores choices for computing resources, assignments of nodes to these resources, task schedules on the programmable processors and context definitions for the reconfigurable circuits. The tool finds a solution that minimizes system cost while meeting the performance constraints; more precisely it lets the designer select the quality of the optimization (hence its computing time) and finds accordingly a solution with close-to-minimal cost.

Introduction

Because of the quickly rising design cost of embedded systems and the difficulty to fulfill tighter and tighter time-to-market objectives, reuse between system generations must be intensified and systems must become increasingly flexible. Thus upcoming systems should exhibit heightened degrees of flexibility [START_REF] Haubelt | System design for flexibility[END_REF]. When performance constraints are stringent, programmable logic is of particular interest since it offers an alternative to standard application specific ICs of equivalent efficiency while being suited to more contexts. Dynamically reconfigurable logic circuits (DRLCs), such as the Virtex family of products from Xilinx, when combined in a SoC with IP cores such as an ARM9x processor [START_REF]Altera. Excalibur architecture, www.altera.com[END_REF] or an AVR-type micro-controller [START_REF] Atmel | AT94K architecture[END_REF], provide solutions that are both flexible and efficient. For reconfigurable systems, rapid system prototyping amounts essentially to programming a heterogeneous system consisting of processor(s) and dynamically reconfigurable logic. In comparison with a custom SoC, a reconfigurable SoC may be more expensive but permit a shorter time-to-market and hence potentially more units to be sold. To perform periodic computations in a system with a DRLC, the specification of the application must be partitioned into run-time contexts. In order to meet the performance constraints in a multiprocessor system, both a schedule of the tasks assigned to the processors and a schedule of the run-time contexts must be determined. Fast development of embedded applications on reconfigurable architectures thus requires system level tools that exploit to the full the dynamic reconfiguration capabilities of the system resources and takes proper account of the reconfiguration times of the DRLCs. This paper presents a technique for automatically mapping an application described by a precedence graph onto a heterogeneous architecture with at least one programmable processor and at least one reconfigurable circuit (RC). Section 2 summarizes the state of the art. The scheduling and partitioning problem is formulated in section 3, where the models of architecture and application are given. Our partitioning algorithm and its application to reconfigurable architectures are detailed in section 4. Experimental results are given in section 5, followed by our conclusions.

Related Work

To ensure that the performance constraints will be met in an embedded system with DRLCs, the computations within the application must be statically partitioned into those to be executed on the DRLCs and those to be executed on the processors (HW/SW spatial partitioning), the hardware tasks must be partitioned into run-time hardware contexts (temporal partitioning), and the software tasks, the run-time hardware contexts and the communications must be scheduled (static software scheduling). Therefore, finding a solution in order to run an application on a given reconfigurable architecture amounts to determining a solution to each one of the following three-coupled-subproblems: HW/SW spa-tial partitioning, SW scheduling, temporal partitioning. Since we are interested in finding the solution with minimum cost that satisfies the performance constraints, we have developed a local search method-an adaptive version of simulated annealing-that explores the space of the solutions to these three subproblems and converges to a solution close to the global optimum. Partitioning and scheduling techniques targeting reconfigurable architectures have been recently presented, often with differing objectives. Rakhmatov et al. [START_REF] Rakhmatov | Hardware-software bipartitioning for dynamically reconfigurable systems[END_REF] start from a control flow formulation of the application and present a solution of the spatial partitioning problem based on a maximum flow formulation. Kaul et al. [START_REF] Kaul | An automated temporal partitioning and loop fission approach for FPGA based reconfigurable synthesis of DSP applications[END_REF] introduce an ILP-based method of resolution of the temporal partitioning problem. Maestre et al. have proposed in [START_REF] Maestre | Kernel scheduling in reconfigurable computing[END_REF] a search technique for the order of execution of the contexts of a DRLC. The algorithm is greedy and finds a temporal partitioning and a scheduling of the contexts for a partially reconfigurable circuit. In contrast with the above three papers, Chatha et al. deal in [START_REF] Chatha | Hardware-software codesign for dynamically reconfigurable architectures[END_REF] with the hardware/software partitioning problem. They propose a partitioning method by migrating tasks between hardware and software and then applying a modified list scheduling algorithm. This approach accounts for all of the characteristics of the problem but considers neither the possibility of a partial reconfiguration of the FPGA nor the overlap of processor computation (software tasks) and hardware reconfiguration. Studies such as the one of Noguera et al. [START_REF] Noguera | HW/SW codesign techniques for dynamically reconfigurable architectures[END_REF] consider the partitioning and the dynamic scheduling on an architecture comprising a CPU and an RC connected via a bus. The RC is composed of an array of programmable logic blocks on which the tasks waiting to be executed are dynamically assigned. Concretely, these studies do not take into account task performance estimates nor total system execution time during the partitioning step, and then determine a dynamic scheduling that decides at run time the order of execution of the ready tasks. Consequently the tasks with the highest computational complexity are assigned to hardware with no regard to the global effect on the system. The complexity is thus relegated to the dynamic scheduler (a centralized control scheme requiring dedicated hardware), and the exploration of the space of solutions of the three coupled subproblems described earlier is not performed. Finally, Ben Chehida and Auguin present in [START_REF] Chehida | HW/SW partitioning approach for reconfigurable system design[END_REF] an approach dealing with all three sub-problems. Spatial partitioning is explored with a genetic algorithm. For each such solution, temporal partitioning is effected by means of a clustering technique and is followed by global scheduling. The two algorithms employed after spatial partitioning are deterministic and generate a single temporal partitioning and a single schedule for each spatial partitioning solution. Our contribution, discussed in the next section, is to con-currently explore all three sub-problems and hence examine different solutions for a spatial partitioning of the tasks between hardware and software.

Problem formulation

We present in this section our formulation of the problem of mapping an application on a reconfigurable architecture following our partitioning methodology. First we present the model used to represent the application, then the type of architecture targeted and, finally, the definition of a problem solution in terms of the three subproblems, HW/SW spatial partitioning, temporal partitioning and HW/SW static scheduling.

Application model

The application is described by a precedence graph (hence acyclic) G =< V, E >. The graph nodes v i ∈ V correspond to coarse grains. Each node is characterized by an index i ∈ [1, N], where N = |V |, a functionality F (v i ) (FFT, DCT, FIR filter, etc.), the number C(v i ) of combinational logic blocks (CLBs) for the hardware implementation, and an estimate of the execution time on the processor, t sw i , and on the RC, t hw i . An edge e ij , between nodes v i and v j , is characterized by the amount of data transferred, q ij , and by a transfer time dependent on the communication link, t ij . An example of representation of an application is given in Fig. 1(a).

Reconfigurable architecture

Our method is not restricted to a particular target architecture since it can explore the types and numbers of programmable and dedicated computing resources in the system in order to minimize the global system cost while satisfying performance constraints [START_REF] Miramond | Optimization method for hw/sw partitioning of systems described with multiple models of computation[END_REF]. However, as far as this article is concerned, we restrict the application of our method to a generic architecture composed of a programmable processor and a dynamically reconfigurable unit, as expounded in [START_REF] Chehida | HW/SW partitioning approach for reconfigurable system design[END_REF]. Thus, the criterion to be optimized becomes here the execution time. The proposed approach applies to a partially reconfigurable architecture insofar as the FPGA reconfiguration time depends on the number of CLBs needed to perform the desired computations. If an RC does not permit multi-context execution, i.e. initiation of several contexts in parallel, reconfiguration cannot be overlapped with computations on the FPGA. An objective is to decompose the computations effected on the RC into different contexts, and determine their sequential execution order. Moreover, each context can carry out one or more computational tasks, according to the numbers of CLBs required for the tasks. Finally, processor and RC communicate via a shared memory connected to each one by a bus [START_REF] Chehida | HW/SW partitioning approach for reconfigurable system design[END_REF]. The transfer time t ij of data between a task v i executed on the processor and a task v j executed on the circuit is estimated in terms of the size q ij of the data and the bus transfer rate D. Performance estimates are made at compile-time, in particular communication latencies are statically evaluated as ordered transactions.

Formulation

The problem to be solved is to find a spatio-temporal mapping of an application, described by a task graph, onto the architecture described in section 3.2. We do this by exploring the space of feasible solutions, where a solution is defined by

• an assignment of the tasks on the processor (software) and the reconfigurable circuit (hardware), • an assignment of the hardware tasks to time segments (logical contexts to be executed), • an execution schedule for the software tasks and the hardware contexts, and • an ordering of the transactions on the shared communication medium, i.e. a total order imposed on the transactions consistent with the task execution ordering. Our method conforms to an object-oriented paradigm; the object concept is exploited at every level to achieve a high degree of flexibility and facilitate tool evolution. Class Processing Element belongs to the Resource class of the system, which is abstract and polymorphic. When several tasks are assigned to the same resource, their execution order on that resource depends on the resource type (processor, ASIC, reconfigurable IC). Indeed, at the (coarse) granularity level considered here, software task execution is sequential-the processor exhibiting actual parallelism only at a finer level. At the other extreme, the computations for several tasks could be performed with maximal parallelism on an ASIC dedicated to these computations. A dynamically reconfigurable circuit provides an intermediate solution since it can execute contexts both sequentially and concurrently; this corresponds to implementing a partial order for task execution. Therefore, a solution consists of

• a total order on the system processor,

• a globally total, locally partial (GTLP) order on the DRLC (see Fig. 1(b)) , and, • if there were an ASIC in the system, a partial order on that circuit. To define a total order for a processor-type resource, sequentialization edges (hence with zero computation-time) that enforce that order are inserted between the tasks assigned to the resource. The order is imposed by the search algorithm at each iteration, see section 4. The set of sequentialization edges for the processor-assigned tasks is denoted by E sw . To impose the order A → C → B on the processor in Fig. 1 Globally Total • the reconfiguration time per CLB, t R ,

¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ £ £ £ £ £ £ £ £ £ £ £ £ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ § § § § § § § § § § § § § § § § § § § § § § § § § § § § § § §
• the total number of CLBs in the circuit N CLB .

Considering a context as a resource in itself, an object of Context type is a Resource that contains in addition :

• the list I of initial nodes of the context, whose immediate predecessors are all outside the context; • the list T of terminal nodes of the context, whose immediate successors are all outside the context; • the number of CLBs used in the context.

The weight of a context sequentialization edge e ∈ E hw is therefore equal to t e = t R ×n CLB , where n CLB is the number of CLBs used by the context of the edge's head.

Design-space exploration

Using the characterization of solutions of section 3, we describe in this section the exploration of the space of solutions. This exploration starts from a random initial solution and then uses a version of the local search method based on the simulated annealing meta-heuristics to reach a solution close to the global minimum of the cost function. This method being iterative, it can be interrupted by the user at any time and will then return the current solution. The transition from one solution to the next is the result of the selection and application of the so-called "moves".

Local search algorithm

To perform a search that reaches a solution at most a few percent away from the global optimum, we have pursued the work carried out by Lam, who presented in [START_REF] Lam | An efficient simulated annealing schedule[END_REF] both an adaptive cooling schedule and a scheme for move selection that speed up significantly the convergence of simulated annealing. Adaptive SA employs a cooling schedule whose general form is independent of the optimization problem at hand. The problem's cost function is viewed as the energy of a dynamical system whose states are the problem's solutions. The schedule is obtained by maximizing the rate at which the temperature can be decreased subject to the constraint that the system be maintained in quasi-equilibrium. The adaptive nature of the schedule comes from the fact that it is expressed in terms of statistical quantities (mean, variance, correlation) of the system's cost function. Move generation affects the correlation between consecutive cost values and the adaptive schedule specifies how to control move generation to maximize cooling speed while satisfying the quasi-equilibrium condition. This version of simulated annealing has been used in VLSI circuit place and route tools [START_REF] Swartz | Automatic layout of analog and digital mixed macro/standard cell integrated circuits[END_REF]. We have recently improved on the estimation procedure and refined the move selection process [START_REF] Miramond | Optimization method for hw/sw partitioning of systems described with multiple models of computation[END_REF]. These modifications have been validated on several types of problems, including graph partitioning and continuous function minimization.

Move definition

For our problem, a move consists in moving a node from one resource to another. Each move is defined by randomly selecting both the task v s to move (source object) and a destination task v d (destination object). A simple rule consists in randomly selecting an integer between 0 and N , the number of nodes in the graph, to determine the index of v s and an integer between 0 and N , to determine the index of v d , and effect accordingly one of four types of moves : • (m 3 ) If 0 is selected for the source and if there is a task that is alone on one resource, then that resource is removed from the system and the task is assigned to the same resource as the destination task. • (m 4 ) If 0 is selected for the destination, there is no destination node. This is interpreted as a request for resource creation (processor, ASIC, DRLC) with assignment of the source task to that resource. Moves m 1 and m 2 allow the simultaneous exploration of spatial partitioning (m 2 ), temporal partitioning and context sequential ordering (m 2 with R(v s ) and R(v d ) of context type), and the sequential ordering of software tasks (m 1 ). Moves m 3 and m 4 would allow the exploration of the system architecture if it were not fixed a priori; however, in this paper, the architecture comprises one processor and one DRLC, hence the probability of generating a 0 is set to 0.

• (m 1 ) If R(v s ) = R(v d )

Move realization

Once a move has been selected, a search graph G = < V, E ∪ E sp ∪ E sr > is deduced from the task graph by adding, temporarily, sequentialization edges. These edges are added, according to its type, by the resource on which the task is to be executed (see section 3.3). Consider the move corresponding to v s = G and v d = J, which concerns the DRLC. In a context-type resource, only a partial order is imposed, and here v s only has to precede H. The search graph G is updated by calling the method for updating the source resource, R(v s ).schedule(v s , v d ), and the method for updating the destination resource, R(v d ).schedule(v s , v d ). Here, in the source resource (context R(v s )), the temporary (dashed) edges (GF ) and (GH) are deleted and the edge (DF ) is created while, in the destination resource (context R(v d )), no modification is needed since G goes from terminal node of the current context to initial node of the following context. In the destination resource, another context will be spawned if

n CLB (R(v d )) + C(v s ) > N CLB .
A move will not be performed if a cycle appears when the search graph is updated (detectable in O(1) operations on the associated transitive closure matrix).

Solution evaluation

After each move, the performance of the new solution is evaluated by determining the longest path in the modified search graph (Fig. 1(c)). Exploiting the property that simulated annealing is a local search method, the longest path may in some cases be obtained incrementally by means of a Woodbury-type update formula [START_REF] Carré | Graphs and Networks[END_REF].

Experimental results

In order to assess the effectiveness of our method, we have applied it to the motion detection application described in [START_REF] Chehida | HW/SW partitioning approach for reconfigurable system design[END_REF]. The application performs object labeling with a realtime constraint of 40 ms per image. Since a software implementation on an ARM922 processor leads to an execution time of 76.4 ms, some portions of the application must be hardware-accelerated to meet the time constraint [START_REF] Chehida | HW/SW partitioning approach for reconfigurable system design[END_REF]. The target architecture consists of an ARM922 processor and a reconfigurable FPGA of the Xilinx Virtex-E family. The reconfiguration time per CLB is t R = 22.5 µs. The performance estimates for the tasks of the application on this architecture were obtained in the EPICURE project [START_REF] Auguin | Partitioning and codesign tools & methodology for reconfigurable computing: the EPICURE philosophy[END_REF]; several estimates are provided for each task on the FPGA, thus allowing exploration of the trade-off between number of CLBs and execution time. For each function (node) in the application, multiple implementations have been effectively synthetized. The node implementations considered form a set of dominant solutions in the area-time domain, each being characterized by the associated number of CLBs and the corresponding execution time. During exploration, SA chooses for each node implemented in hardware one of its implementations (5 or 6 synthesized solutions per function). Our method explores solutions characterized by a spatial partitioning, a temporal partitioning and a sequential ordering of the FPGA contexts. Results from a typical example of exploration of the solution space are presented in Fig. 2. The FPGA size is 2000 CLBs for this run. Both the execution time in ms and the number of FPGA contexts allocated at each iteration are plotted; the number of contexts ranges from 1 to 8 for the example. The initial solution is generated with a random hardware/software partition. A random number of tasks are moved, one by one, to the reconfigurable circuit. A new context is created when the capacity of the last context is exceeded. In the example of Fig. 2, only 9 (among 28) tasks are assigned to hardware; they require 995 CLBs, hence only one context. The execution time of this initial solution (67.9 ms) exceeds the 40 ms constraint; this poor performance is due to the excessive communication times resulting from the random nature of the initial partition. To illustrate the optimization method, the first 1200 iterations are performed at infinite temperature and the solution space is then broadly explored-the execution time ranging from 35 ms to 70 ms and the number of contexts from 1 to 8-while the average performance shows no improvement, as expected. When the method is activated and adaptive cooling starts, the execution time falls quickly below the 40 ms constraint. Between iterations 1500 and 3000 the number of contexts grows, as the relatively fine level of improvement of the partition of the tasks between contexts is then reached and explored. The final, frozen, configuration, has an execution time of 18.1 ms, well below the constraint, and uses 3 contexts. The example shows that the performance constraint can be satisfied with an FPGA device of size 2000 CLBs. We examine next the impact of the device size (number of CLBs) on the performance that can be achieved. As a byproduct of this study we determine the size of the smallest device for which the 40 ms constraint is attained. Fig. 3 presents the results of our experiments using simulated annealing for FPGA sizes ranging from 100 to 10000 CLBs. Each value is an average of the results obtained for 100 runs. For each of the device sizes considered, the average values of the execution time, the reconfiguration time and the number of contexts are shown. As the size increases, the execution time drops quickly once the number of CLBs is large enough for a context to hold more than one task to be executed, since parallelism is then provided within the hardware. A minimum execution time is reached for about 800 CLBs and, as size increases further, execution time grows slowly and reaches a plateau around 5000 CLBs. Indeed, from this size up, all the hardware tasks can be executed in a single context. For such large devices, the optimisation method starts from random solutions with one context and an execution time exceeding 75 ms to finally reach solutions with a single context as well but whose execution time is more than halved. For small devices, holding from 400 to 1500 CLBs, the small context size leads to solutions with a large number of contexts (up to 10), number which drops steadily as size increases. Because of the compensation between number and size of contexts, total reconfiguration time remains roughly constant. Our best solutions improve on those obtained in [START_REF] Chehida | HW/SW partitioning approach for reconfigurable system design[END_REF], whose execution time is 28 ms. Moreover a run of our method takes less than 10 seconds, to be compared to the 4 minutes of the genetic algorithm used in [START_REF] Chehida | HW/SW partitioning approach for reconfigurable system design[END_REF]. In that paper, the population size is 300, hence even if it was reduced to 100, the method would still be an order of magnitude slower than ours.

Although the example seems simple, the solution space is big. If the graph were a chain (hence with a total order), then, for 28 nodes, 2 changes of context would give 378 combinations and 6 changes 376,740 combinations. However there are many total orders possible for the actual 28node example. Accounting just for the first 20 nodes, which form, in this case, a 7-node chain followed by a 7-node chain in parallel with a 6-node chain, there are 1716 total orders. In fact the 6-node chain is followed by a 2-node chain in parallel with one node (3 orders) followed by 5 nodes, hence the 28 nodes form a 7-node chain followed by a 7-node chain in parallel with one of 3 14-node chains.

Thus there are 3 21 7 total orders for the example, i.e.

348,840 orders, therefore for 2 changes of context there are 131,861,520 combinations and for, say, 4 changes of context there are 7,142,499,000 combinations. This is assuming that all the processing is performed on the RC; there are many more combinations when the fact that some nodes may be executed in software is taken into account.

Conclusions

This paper develops an application, to reconfigurable architectures, of a general method of hardware/software partitioning optimization [START_REF] Miramond | Optimization method for hw/sw partitioning of systems described with multiple models of computation[END_REF]. We have been able to quickly specialize our tool to this class of architectures, thus demonstrating the ease of incorporation of models of target architectures. This flexibility has been made possible by the object modeling effort on our application and architecture models, and by our work on acceleration of the simulated annealing Compared to other optimization methods, this approach does not require either tuning, as one can find in tabu search (tabu list sizes) or genetic algorithms (population size, reproduction rate...), or problem specific adaptation effort (chromosome encoding). With our method, adaptation to new models of computation and target arhitectures only requires the definition of simple simulated annealing moves. This study confirms that our method is not only flexible but also efficient since the execution times for the motion detection application improve on those available on the same benchmark. We are currently working on developing simulated annealing moves for systems described by multiple models of computation, including SDF and CFSM.

  (b), the edge (C, B) is added. Sequentialization Total Order Locally Partial Order

Figure 1 .

 1 Figure 1. (a) Task graph example, (b) a spatiotemporal partitioning, and (c) its schedule.

  and the resource R is a processor, the move is a modification of the (total) execution order on the resource coherent with the precedence relationships imposed by the task graph. For instance, if v s = B and v d = A in Fig. 1(b) , the total order is modified from A, C, B to B, A, C. If R is an ASIC or an RC context no move is performed. • (m 2 ) If R(v s ) = R(v d ), the move consists in switching the assignment of the source task to the same re-source as the destination task. For instance, recalling that the contexts of a DRLC are considered as resources, if v s = C and v d = D in Fig. 1(b), the task C will be executed on the DRLC and, moreover, in execution context 1.

Figure 2 .

 2 Figure 2. Evolution of execution time and number of contexts in a typical run.

Figure 3 .

 3 Figure 3. Execution time, reconfiguration times, and number of contexts vs. FPGA size.

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)


Luciano Lavagno
email: lavagno@polito.itwatanabe@cadence.com

Claudio Passerone

Vishal Shah

Yosinori Watanabe

A Time slice based scheduler model for System Level Design

 as our codesign environment.

Introduction

One of the main objectives of an effective hw/sw design flow is to provide the system designer with the ability to model a system at varying levels of abstraction, and with tools and techniques to analyze and verify his models. Integrated simulation of hardware and software components is an important step of a codesign flow as it allows a designer to explore the design space and evaluate the performance of an algorithm on a particular hw/sw partition choice. Changing from one partitioning decision and algorithm implementation to another is less time consuming if the models are still abstract and less detailed, which is usually the case early on in the design stages. Hence codesign tools from companies such as Mentor Graphics, Cadence, Synopsys and CoWare, and from university groups such as Roses, Metropolis, and others, support hw/sw cosimulations at various levels of abstraction.

Raising the abstraction level makes both design activities, such as creating and changing components of a design, and verification activities, such as simulation and formal verification, much faster. It is generally considered the only means to cope with the increased number of gates that Moore's law offers to designers whose number and whose productivity in terms of "design objects per day" are almost constant over time. Debugging and optimization become much easier when the number of objects is reduced, as long as "referential transparency" is preserved, meaning that design decisions have an obvious and controllable impact on the quality of the final results. Higher abstraction levels also increase the modularity of design, by reducing the number of implementation details, and thus further increase productivity by means of re-use. Designers can focus on functionality and constraints, rather than on implementation details.

In this paper we focus on a design approach based on the separation of concerns [START_REF] Balarin | Hardware-Software Co-Design of Embedded Systems -The Polis Approach[END_REF][START_REF] Balarin | Modeling and designing heterogenous systems[END_REF], in which high-level functional models are annotated, by hand or automatically, with the results of mapping decision to a variety of architectural components, such as processors, buses, memories, standard cells, IP blocks, FPGAs, and so on. Annotating performance directly at the algorithmic level makes design space exploration much faster, even though often such high-level time and power estimates are only approximate. This can however help identify algorithmic and communication blocks which are bottlenecks in a given mapping choice, and hence drive the designer to better solutions.

The goal of the paper is to show that one need not annotate performance information at a very fine-grained level (e.g. for software, instruction level or below), but only coarser-grained information is really needed to make choices with a good level of fidelity. We do so by using as an example the Metropolis modeling and simulation environment [START_REF] Balarin | Modeling and designing heterogenous systems[END_REF], and by focusing on the representation of the functionality and performance of a set of software tasks mapped to a processor under control of a time-sliced real-time executive. While the results are specific to this application, the techniques and the conclusions that we can draw from this exercise are much broader, and can be extended to other types of software execution environments and hardware architectures.

Related Work

To cope up with the pressures of time-to-market and design complexity of hw/sw systems, several attempts have been made to raise the level of modeling abstraction [START_REF] Balarin | Metropolis: An integrated environment for electronic system design[END_REF][START_REF] Gajski | SpecC: specification language and methodology[END_REF][START_REF] Buck | Ptolemy: a framework for simulating and prototyping heterogeneous systems[END_REF]. However, a design with abstract models introduces several limitations on the accuracy of performance estimates. Scheduling policies tend to have a significant effect on the performance of a system and hence, capturing scheduler overheads in system level design is important.

In the past, there have been several efforts expended in the direction of modeling schedulers, preemptive and otherwise, for coarse grain models of software tasks [START_REF] Balarin | Hardware-Software Co-Design of Embedded Systems -The Polis Approach[END_REF][START_REF] Yi | Fast and Time-Accurate Cosimulation with OS Scheduler Modeling[END_REF][START_REF] Cockx | Efficient modeling of preemption in a virtual prototype[END_REF][START_REF] Gerstlauer | RTOS modeling for system level design[END_REF]. The scheduler model we present, is closest to [START_REF] Gerstlauer | RTOS modeling for system level design[END_REF] and it can be seen as an optimization to it for the case of modeling time-slice based scheduling policies. While the authors of [START_REF] Gerstlauer | RTOS modeling for system level design[END_REF] describe the scheduler model, they do not detail the approach to be used for time-slice based scheduling and dynamic scheduling in general.

Polis [START_REF] Balarin | Hardware-Software Co-Design of Embedded Systems -The Polis Approach[END_REF] represents each component of a design using a finite state machine based representation. It can then synthesize an RTOS that schedules the models of software tasks on the hardware model. While it can generate time-slice based schedulers, it does not provide the designer any control over modifying the behavior of a particular scheduler, and hence the designer cannot exploit the efficiency that is on offer by models of software that can be less than time-slice accurate. A similar approach is adopted in [START_REF] Cockx | Efficient modeling of preemption in a virtual prototype[END_REF]. Yi et.al. [START_REF] Yi | Fast and Time-Accurate Cosimulation with OS Scheduler Modeling[END_REF] annotate a software model with a preemptive scheduler overhead by running the software tasks on an instruction set simulator. While this increases accuracy and is helpful towards the final stages of the design, it is of no help when a designer only needs a rough estimate on his software models also capturing the scheduler overhead.

The basic advantage that our model aims to capture is to exploit the level of abstraction, both of hardware and software models, available in System Level Design frameworks and use it to improve simulation efficiency. We used Metropolis because it gave us an explicit control over how a scheduler is modeled and how it interfaces with the hardware and software components modeled at varying levels of abstraction.

The Metropolis Framework

Metropolis [START_REF] Balarin | Metropolis: An integrated environment for electronic system design[END_REF] is a system-level design infrastructure based on a model with precise semantics that is general enough to support existing computation models and accommodate new ones. It can represent all the key ingredients in the design flows: function, architecture, mapping, refinement, abstraction and platforms. To allow better reuse of models, the focus is on separation of independent aspects, such as:

• Computation and communication.

• Functionality and architecture.

• Behavior and performance.

The system to be developed is hierarchically decomposed into several objects, with two distinct networks at the top level. The scheduled network, which contains all blocks related to function, architecture and mapping, and the scheduling network, which is used to drive the execution of the scheduled network and assign cost and performance using special objects called quantity managers.

Function is defined by a network of concurrent processes that communicate through communication media (similar to SystemC and SpecC channels). Processes and media are both described using a sequential language called metamodel, which is similar to Java TM , but has been extended to support modular specifications using ports and interfaces. The behavior of the network is a sequence of event vectors, where each event in a vector represents the execution of a computation or communication step (e.g. an assignment, or reading a shared memory location, or writing a FIFO queue) by a particular process.

The architecture provides computation and communication services to the function. It is a network of processes and media as well, and services are specified using the same metamodel used in the function side. Services are decomposed into a sequence of events, and each event can be annotated with a value representing its cost and performance, in terms of a number of physical and abstract quantities.

Mapping is used to associate functions to services provided by the architecture. It is achieved by synchronizing events occurring within function processes with events occurring in the architecture. The annotations defined for the architectural events are thus inherited by those in the function side, allowing to determine the costs and performance of the entire system.

Performance annotation and the modeling of scheduling policies is done using the abstraction of quantity managers. Figure 1 shows a high level anatomy of a quantity manager. Its input can be seen as a set of annotation requests from the software tasks, queued in using the request(...) method, and its output can be seen as either a single result or a sequence, indicating the execution order of the tasks, constructed by the resolve(...) method.

Simulation of a hw/sw design is divided into two phases, the request phase and the resolve phase. In the request phase, the software tasks (as well as the hardware-mapped processes, which are however outside the scope of this paper) instantiated in the scheduled network execute their behavioral description till they reach a point where a request for performance annotation is made. At this point they will generate an event and queue in their annotation request to the quantity managers which control the physical quantity that the tasks want to be annotated with. After all the tasks have made such requests, the second phase, the resolve phase starts. In this phase a quantity manager will have a set of annotation requests from the tasks. Based on its policies, the quantity manager will annotate the selected requests and notify the owner tasks. The request phase now starts again. The notified tasks will further execute their behavioral descriptions till they reach the next annotation point. This alternation between the request and resolve phase is comparable to the two-stage simulation cycle semantics of VHDL simulators.

Figure 2 shows a design that contains more than one quantity managers. It models a shared bus architecture. As seen in this case, one quantity manager might need to know the decision of other quantity managers before it can finalize on its own decision. In our example, as the bus is shared between Cpu1 and Cpu2, before a CpuQM schedules a task it has to know whether it has the bus ownership. In such cases, the resolve phase might have to be run iteratively for an implicit communication between the quantity managers. In the interest of a modular, loosely coupled design specification, the modeling semantics of quantity managers do not allow them to communicate with each other explicitly. An iterative execution of the resolution phase allows all the quantity managers to reach a mutually agreeable decision. For instance, when Task A and Task C request cpu functionality which also needs bus access, in the first execution of the resolution phase each quantity manager, in our case the bus-time quantity manager and the two cpu-time quantity managers, determine their decision. In the next execution of the resolution phase each cpu-time quantity manager can check if the decision of the bus-time quantity manager conflicts with their own decision. If it does, the cpu-time quantity manager can be modeled to do a rollback or make a different choice and the resolution phase can be run again.

The main reason for using Metropolis as our design framework was the ease and flexibility it gives in design space exploration and rapid systems prototyping, and its modeling abstractions being based on formal execution semantics, all key requirements for Embedded Systems de-

The Scheduler Model

Our approach to model schedulers is based on the principle of exploiting the availability of abstract hardware and software models in system level design frameworks. It aims to increase the simulation efficiency by reducing the amount synchronization required between a scheduled network and a scheduling network. It should be noted that, though we discuss our modeling technique in regard to Metropolis framework, it is general enough to be applied to any simulation environment that is based on two phase execution semantics between functionality and scheduling. To generalize, a scheduled network can be seen just as a group of components capturing functionality in the system and the scheduling network can be seen as a group of components capturing the scheduling aspects of the system. Ptolemy [START_REF] Buck | Ptolemy: a framework for simulating and prototyping heterogeneous systems[END_REF], is one such environment with analogous modeling and execution semantics in terms of actors and directors.

In the following we will assume that the performance of application software tasks is modeled at the level of basic blocks. Several methods have been proposed to estimate the CPU cycles required for an instruction [START_REF] Malik | Static timing analysis of embedded software[END_REF][START_REF] Suzuki | Efficient software performance estimation methods for hardware/software codesign[END_REF][START_REF] Zivojnovic | Compiled hw/sw co-simulation[END_REF]. Using these methods, a designer can construct a model for software, in which the cycle count of all the instructions in a basic block is aggregated, and a single request for the time annotation of this aggregated amount of cpu cycles is made to the quantity manager. It should be noted that the aggregated cycle count for a basic block is not yet annotated with the overhead caused by scheduling effects, it is the quantity manager model that does this annotation.

In this research we focused on modeling a time-slice based task scheduler, improving simulation efficiency when the annotation granularity of the processes to be executed is coarser than the time-slice, as can happen in the case where the designer wants to annotate software performance at the basic-block level. The model is applicable to different kind of shared resources, such as buses and memories with burstmode and DMA access, but in the following we will concentrate, without loss of generality, only on CPUs.

Our goal is to avoid starting a new resolution phase each time a time-slice elapses, otherwise we would lose possible gains in simulation performance that can be achieved by using coarser annotations at the process level. When the annotation granularity is fine, e.g. at the instruction level, our technique, while still applicable, does not provide significant advantages, since the performance bottleneck is created by the high-detailed models.

Algorithm 1 details the resolution mechanism that we implemented in a Metropolis quantity manager. At the start of each resolve phase all quantity managers instantiated in the scheduling network will have a set of requests. These requests are from the software tasks that wish to use the resource controlled by a quantity manager. Based on the scheduling policy modeled, the quantity manager will decide which task should be allowed to use the resource. Step 1 of the algorithm selects the request R from the input set X, containing the task requests.

Our quantity manager model, instead of choosing a single software task as its scheduling decision, will choose a sequence of tasks. This sequence corresponds to the alternation of execution slices of the various tasks mapped to the shared resource and it is this sequence that captures the timesliced execution of the tasks. The sequence stops, and the resolve() method terminates, when the last slice selected completely fulfills the request of a task. This task is signaled to proceed, while the other tasks in the sequence stay suspended since they need more slices to finish.

Step 2 models this. It first checks whether the resource amount requested by the selected software task exceeds the time slice defined for the resource. If it does then the request is updated to reflect that the task was alloted resource amount = time slice, and is put back in the request set X. It then records the selected task in a sequence Y and the control goes back to step 1. When a task is selected whose requested resource amount <= time slice, the task is recorded in the sequence Y and control is transferred to Step 3, which exits with Y as its scheduling decision.

If t 1 , t 2 ,..., t n denote n software tasks respectively, and the value of Y is t 1 , t 2 , t 1 , t 2 , t 1 then the scheduling decision can be seen as, t 1 got the entire amount of resource it had requested for and that it can proceed, while t 2 got resource amounting to two time slices and is waiting to get more resource. In reaching this scheduling decision, t 1 and t 2 were each preempted twice. The value of Y represents the execution order of tasks. In this case the order of preemption of tasks is t 1 , t 2 , t 1 , t 2 .

Example

Consider the hw/sw model of Figure 3. Here 3 tasks A, B and C request cpu cycles. Suppose A requests 10 cycles, B 20 and C 30 cycles and the time-slice for using the cpu Algorithm 1: Select resource owners Input: Set X of requests from software tasks Output: Sequence Y representing the execution order of software tasks 1. R = remove(X, selection policy)

where selection policy = FCFS, priority based, etc. 2. if requested amount(R) > time slice requested amount(R) = requested amount(R) -time slice insert(X, R) insert(Y, task owner(R)) go to 1 else insert(Y, task owner(R)) go to 3 3. return Y is defined as 10 cycles. Figure 4(a) shows the state of request queue of cpu time quantity manager after the execution of phase 1 . The number next to each task name indicates the number of cycles the task is waiting to be allocated. In this case, our model of preemptive scheduler, based

¡ ¡ ¡ ¡ ¢ ¢ £ ¤ ¤ ¥ Task A Task B Task C ¦ ¦ § ¨© © © ©
CPU CpuQM req [START_REF] Suzuki | Efficient software performance estimation methods for hardware/software codesign[END_REF] req(20) req(30)

Figure 3. Shared Cpu

on FCFS selection policy, will allocate first 10 and the next 10 cycles to C and B respectively, and then put them back in the queue since their entire quantity request has not been filled. Figure 4(b-d) show the state of the queue at the end of each time slice. At the end of 3 time slices the scheduler has with it at least one request, that of task A whose entire request for quantity has been satisfied. The cpu quantity manager will remove the request of task A from the queue and transfer the execution control to it. Figure 4(d) shows the status of the queue after this scheduling decision.

It should be noted here that in theory, control should have transferred to tasks C and B at the end of 10 and 20 cpu cycles respectively, but the coarseness of the annotation requested by the designer did not make this a requirement. If the designer wants control to be transferred to the software task at the expiry of each time slice, his annotation requests should be always smaller than the time slice defined for the resource. This allows him to introduce more details in his

Limitations

This approach to modeling time-slice based scheduling, while reducing the number of calls to the scheduling network, introduces some limitations. The foremost limitation that we can see is that we cannot directly extend this approach to handle preemptions caused by unpredictable events, like when the occurrences of non periodic interrupts are to be modeled. This is because, to exploit the technique, the quantity manager should be able to make assumptions on when to assign resources that are requested. This is clearly impossible when the instant in which the event occurs is not known in advance. The solution, that was first discussed in [START_REF] Balarin | Hardware-Software Co-Design of Embedded Systems -The Polis Approach[END_REF], is to modify the Quantity Manager for the CPU so that it does not allow any requests to be made to the Global Time Manager (another quantity manager in Metropolis) until it is known that global time has reached that point, and hence no preemption can occur for the executing task any longer. In case the task gets preempted before, such pending requests are postponed in time, by the amount corresponding to the duration of the preempting task (and possibly of other tasks preempting it). Also in a system modeling multiple schedulers as in Figure 2, where there exists dependencies between scheduling decisions of each scheduler, in order to reach a global stable state of the system at the end of each time-slice, a scheduler might need to know the decision of scheduler lower in the hierarchy before it can finalize its own decision. While this increases the accuracy, it does introduce significant amounts of overhead as we show in the experimental results. For the example in Figure 2, a CPU scheduler before deciding on a result sequence will need to know the scheduling decision of the bus scheduler at the end of each time slice. This is because each run of the resolve() method of the time-slice scheduler outputs a sequence of task executions, rather than a single task as its result. Therefore to achieve results accurate at time-slice level the resolution of bus requests from the very same tasks should follow an equivalent execution order for the two schedulers to be consistent.

In case the synchronization between schedulers cannot be achieved, either because the models do not support it, or because it may imply reduced simulation performance, the events scheduled in the architecture might be in conflict between each other. For instance, the trace of the simulation might show a bus access from a process that has made a request for CPU cycles while it is not actually running on the CPU, because the current slice is assigned to another process. If one is just interested in aspects not involving the perfect synchronization of the events, such as the total bus load or its switching activity, then the model may still valid and the results that are obtained are often correct, albeit approximate. For a more refined simulation at a lower level of abstraction, on the other hand, the models should allow the information sharing between schedulers, or the time-slice scheduler should limit the sequences always to a single slice. Figure 5 shows an example of what happens when two schedulers are synchronized, and when they are not. It shows a Gantt chart of three processes, that have requested a certain amount of CPU cycles, shown in parenthesis. The arrows in the chart represent bus accesses. In both cases, three runs of the resolve() method of the time-slice scheduler are shown. In Figure 5-(a), the bus and the CPU scheduler are synchronized; thus all bus accesses happen when the corresponding process is actually running on the processor. On the other hand, in Figure 5-(b), the two schedulers are not synchronized. Without any other information, the bus scheduler will schedule accesses to the bus at its own convenience (typically earlier than the previous case), so the result is inconsistent. However, the number of bus accesses is the same in both cases. This model trades off these limitations with the efficiency it can achieve at the simulation level, without compromising on the accuracy of the functional behavior.

Experimental Results

In this section we compare the results obtained by two time-slice accurate scheduler models, S1 which optimizes the simulation performance, using the technique presented in Section 4, and model S2, that is based on a naive approach of invoking the scheduler at the end of each time-slice.

The system we model and simulate has 4 software tasks. Each of them models a behavior shown in Figure 6. It reads a 1000 data words from memory, does some computation on it and then writes back a 1000 words to memory. On the architecture side, we have a cpu model that has performance estimates for load and store instructions. Our RTOS model only contains the scheduler. To simulate this hardware software combination, we map the read and the write instructions of the software tasks to the load and store instructions of the cpu.

In order to illustrate the generality of our approach, we also model the same system specification in SpecC environment, where we model the 4 software tasks, the Cpu and the Scheduler as a network of behaviors communicating by exchanging events.

As Table 1 shows, in the Metropolis framework, the scheduler model S1 outperformed model S2 by reducing the simulation time by upto 23%, and in the SpecC framework by 27%. The difference in the performance numbers on the two environments can be attributed to different modeling mechanisms and code generation backends. We achieve performance improvements in simulation time by decreasing the number of scheduler invocations. The results are reported on the particular hardware/software combination we modeled. Depending on the coarseness or the fineness of the models the results may vary and one can achieve more or less improvements.

Conclusion

System Level Design facilitates modeling at high-level of abstraction as well as mixing highly detailed and low detailed models. There is a lot of opportunity to exploit the presence of abstract models in order to improve the performance of design tools. This paper presented an approach to model time-slice based schedulers in such environments exploiting this advantage. Our future work aims to address the limitations of this technique.

Figure 1 .

 1 Figure 1. Quantity Manager Anatomy

Figure 2 .

 2 Figure 2. Shared Bus Architecture

Figure 4 .

 4 Figure 4. CpuQM Request Queue state

Figure 5 .

 5 Figure 5. CPU and bus scheduler (a) synchronized, (b) not synchronized

Figure 6 .

 6 Figure 6. Process and Cpu Model

Table 1 .

 1

	Design Environment % reduction in simulation time
	Metropolis	23
	SpecC	27

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)