Anup Gangwar

M Balakrishnan

Preeti R Panda
email: panda@cse.iitd.ernet.in

Anshul Kumar
email: anshul@cse.iitd.ernet.in

R F R F Ld

/ St

Evaluation of Bus Based Interconnect Mechanisms in Clustered VLIW Architectures

With new sophisticated compiler technology, it is possible to schedule distant instructions efficiently. As a consequence, the amount of exploitable instruction level parallelism (ILP) in applications has gone up considerably. However, monolithic register file VLIW architectures present scalability problems due to a centralized register file which is far slower than the functional units (FU). Clustered VLIW architectures, with a subset of FUs connected to any RF are the solution to this scalability problem.

Recent studies with a wide variety of inter-cluster interconnection mechanisms have presented substantial gains in performance (number of cycles) over the most studied RFto-RF type interconnections. However, these studies have compared only one or two design points in the RF-to-RF interconnects design space. In this paper, we extend the previous reported work. We consider both multi-cycle and pipelined buses. To obtain realistic bus latencies, we synthesized the various architectures and found out post layout clock periods. The results demonstrate that while there is very little variation in interconnect area, all the bus based architectures are heavily performance constrained. Also, neither multi-cycle or pipelined buses nor increasing the number of buses itself is able to achieve performance comparable to point-to-point type interconnects. LD/ST ALU LD/ST ALU ALU ALU

Introduction

Media applications have large amount of instruction level parallelism (ILP) which justifies building very high issue-rate processors [START_REF] Fritts | Evaluation of static and dynamic scheduling for media processors[END_REF][START_REF] Stefanovic | Limits and graph structure of available instruction-level parallelism[END_REF][START_REF] Talla | Evaluating Signal Processing and Multimedia Applications on SIMD, VLIW and Superscalar Architectures[END_REF]. While, the exact amount of achievable ILP is still a point of debate, published work on future directions for architecture research points in the direction of very high issue-rate processors [START_REF] Fritts | Parallel Media Processors for the Billion-Transistor Era[END_REF][START_REF] Patt | One billion transistors one uniprocessor one chip[END_REF]. Whereas SuperScalar processors are more popular in the general application domain, VLIW processors have gained wide acceptance in the embedded systems domain e.g. TriMedia, TiC6x, Equator's MAP-CA and MAP-1000 [START_REF] Glaskowsky | MAP1000 unfolds at Equator[END_REF], HP-ST Microelectronic's Lx [START_REF] Faraboschi | Lx: A technology platform for customizable VLIW embedded processing[END_REF] etc.

VLIW architectures with a monolithic register file with all the FUs connected to it lead to an increase in the register file (RF) delay, power and area. The centralized RF thus * Currently with Calypto Design Systems (I) Pvt. Ltd., NOIDA, India becomes a bottleneck in performance on all these metrics [START_REF] Rixner | Register organization for media processing[END_REF]. The RF delay, power and area are more sensitive to the increase in number of ports rather than the RF size (number of registers) itself. Clustering the VLIW architecture into a number of small sets of FUs, wherein each such set has its own RF is a natural solution to such a scalability problem. However, the inter-cluster interconnect in such architectures plays a crucial role in processor performance [START_REF] Terechko | Inter-Cluster Communication Models for Clustered VLIW Processors[END_REF] and [START_REF] Gangwar | Impact of Inter-cluster Communication Mechanisms on ILP in Clustered VLIW Architectures[END_REF].

Till recently only one type of inter-cluster cluster interconnect, a simple bus connected to all the clusters, was used and researched in both industry and academia. However, two published results on evaluation of various intercluster interconnect mechanisms in clustered VLIW processors [START_REF] Terechko | Inter-Cluster Communication Models for Clustered VLIW Processors[END_REF] and [START_REF] Gangwar | Impact of Inter-cluster Communication Mechanisms on ILP in Clustered VLIW Architectures[END_REF] reported substantial performance gains in number of cycles when various other mechanisms are used. However, both these studies used few specific design points for evaluating bus based interconnects. In [START_REF] Terechko | Inter-Cluster Communication Models for Clustered VLIW Processors[END_REF], a single cycle transfer bus was connected to all the clusters and in [START_REF] Gangwar | Impact of Inter-cluster Communication Mechanisms on ILP in Clustered VLIW Architectures[END_REF] two single cycle transfer buses were connected to all.

In this paper we extend the previous reported work on performance of bus based inter-cluster interconnects in clustered VLIW processors. We start by showing that the clock-period is heavily constrained beyond two cluster architectures if single cycle transfer buses are used. Towards this end, we model the various clustered architectures in VHDL and perform synthesis, place and route using industry standard tools. We next use these results to arrive at realistic latencies for multi-cycle and pipelined buses such that the clock-period is not affected. Finally we carry out exhaustive performance evaluation of these bus-based architectures using the obtained latencies.

Inter-cluster Interconnect Architectures

Figure 1 shows the various interconnect architectures. Figures 1(a) and 1(b) show two alternatives for RF-to-RF architectures. In Figure 1(a) buses either run at processor frequencies, in which case the overall operation frequency of the processor comes down or they run at frequencies slower than the actual processor clock (multi-cycle). In Figure 1(b), buses are explicitly pipelined so that the processor operation frequency is not affected i.e. the inter-cluster interconnect path does not become the critical path. Figures 1(c), 1(d), 1(e), 1(f) and 1(g) show what have been termed as the direct communication architectures [START_REF] Gangwar | Impact of Inter-cluster Communication Mechanisms on ILP in Clustered VLIW Architectures[END_REF]. In these architectures, FUs from one cluster can directly communicate with the RF of another cluster.

Clock Period and Chip Interconnect Area for Clustered Architectures

To obtain realistic bus latencies and also to get a comprehensive performance estimate we evaluated the clockperiod obtained for various interconnect and cluster configurations. Towards this end we modeled the processors using parameterized VHDL. Our modeled processor has a standard load store architecture with RISC style instructions. The ALU components: adder, multiplier and divider are obtained using the Synopsys DesignWare libraries. This ensures that the critical path is not constrained due to inefficient implementation of these modules. The load/store unit follows standard Static RAM (SRAM) timing, such as that presented in [START_REF] Gaisler | LEON: A Sparc V8 Compliant Soft Uniprocessor Core[END_REF]. RF for any processor is custom designed [START_REF] Cruz | Multiple-banked register file architectures[END_REF][START_REF] Tseng | Banked multiported register files for high-frequency superscalar microprocessors[END_REF]. Since RFs cannot be synthesized efficiently by the common synthesizers, these are usually hand crafted. For lack of availability of such a handcrafted RF design, we included a dummy RF during synthesis. This RF doesn't contain the complicated muxing logic which a real RF has, however, it does ensure that proper port mappings are in place so that static timing analysis (STA) reports proper paths. The entire VHDL has been written at Register Transfer Level (RTL) to obtain most efficient implementation. Our parameterized VHDL model allows variation of: Interconnect architecture, Number of clusters, Register file size, Register file (and ALU) width, Data RAM size and Instruction RAM size. The flow used is industry standard Synopsys frontend (Design Compiler) and Cadence backend (SoC Encounter). We followed a hierarchical place and route approach in which clusters are first placed and routed and then processor floorplan is done. Pin positions on clusters are fixed manually to obtain good top-level floorplan.

We ran our experiments for two ASIC Technologies, UMC's 0.13µ six metal layer process and UMC's 0.18µ five metal layer process. The results are presented in Tables 1 and2. Table 1 shows variation of clock period for different interconnect mechanisms with an increase in the number of clusters. Table 2, shows variation of interconnect area as a percentage of the total chip area for different interconnect mechanisms with an increase in number of clusters. Abbreviation RF has been used in this table for single cycle transfer RF-to-RF architecture, WA for Write Across, RA for Read Across and WR for Write/Read Across. Results of both clock period and interconnect area are similar for 0.18µ technology and hence have not been shown.

Looking at these results, it is clear that point-to-point type interconnects scale very well with increase in number of clusters. In these cases the critical path is not through the inter-cluster interconnects. However, for RF-to-RF type interconnects beyond the two cluster configuration, the critical path does lie through inter-cluster communication bus and hence scalability is limited if the buses are run at processor frequency. We next use these clock-period numbers to arrive at realistic bus latencies for pipelined buses. These various bus configurations (pipelined and multi-cycle) are in turn used to perform an exhaustive design-space exploration. Figure 2 shows the overall design space exploration methodology. The Trimaran system is used to obtain an instruction trace of the whole application from which a DFG is extracted for each of the functions. Trimaran also performs a number of ILP enhancing transformation. The chain detection phase finds out long sequences of operations in the generated DFG. The clustering phase, which comes next, forms groups of chains iteratively, till the number of groups is reduced to the number of clusters in the architecture. The binding phase, binds these groups of chains to the clusters. We agree that ideal results are obtained, when all the problems i.e. operation to cluster and FU assignment, register allocation and scheduling are done simultaneously [START_REF] Kailas | CARS: A new code generation framework for clustered ILP processors[END_REF][START_REF] Ozer | Unified assign and schedule: A new approach to scheduling for clustered register file microarchitectures[END_REF]. However, this makes the problem intractable for large graphs. We thus divide the problem as follows: First operation to cluster binding is done and next operation to FU in a cluster binding is done. Since, during cluster-ing, the partial schedules are calculated (explained in detail later), the typical phase coupling problem [START_REF] Kailas | CARS: A new code generation framework for clustered ILP processors[END_REF][START_REF] Ozer | Unified assign and schedule: A new approach to scheduling for clustered register file microarchitectures[END_REF], is contained to a large extent, while still keeping the overall problem size manageable. Lastly, a scheduling phase schedules the operations into appropriate steps. More details on each of these phases is presented below.

Design Space Exploration

DFG Generation: The DFG generation is carried out by matching source destination pair of register and memory usage. The machine model used for Trimaran is an extremely flexible one, with 256 GPR and 1024 Predicate registers. Trimaran also performs a number of ILP enhancing transformation, which in turn lead to an increase in the achievable ILP. Chain Detection: The second phase is the chains detection phase. In this phase long sequences of operations are found in this DFG. The idea is to bind these chains to one cluster (similar to the one discussed in [START_REF] Lapinskii | High quality operation binding for clustered VLIW datapaths[END_REF]. Singleton Merger: The chain detection phase returns a large number of chains. Including a significant number which have only one element (singleton). After observing the large number of singletons we specifically introduced a singleton merging phase. In this phase, the singletons which do not have any source or destination are distributed in n clusters number of chains (groups). The idea is that these would not constrain the scheduler in any way, as they donot have any source or destinations. Nodes, which have no destinations (sources) are merged with the shortest chain of their sources (destinations). Here the number of chains is reduced to the number of clus-ters, by grouping selected chains together. The idea here is to reduce the inter-cluster communication between various groups. However, the closeness between these groups is architecture dependent. This can be better understood by examining architectures shown in Figures 1(a) and 1(b). While in the former, data transfer from any cluster to any other cluster takes same number of cycles, in the latter this varies. This stage assumes that finally the communication would happen through the best possible inter-cluster interconnects. Thus, this schedule length effectively represents an upper bound on the actual schedule.

The loop (steps 3 to 15) reduces the number of chains to n clusters by pairwise merger of chains. The chains are examined pairwise for their affinity (step 4 to 11) and a lower triangular matrix C is formed. Here each element c i j gives the estimated schedule length due to merger of i and j (step 9). The C matrix is sorted according to multiple criteria (step 12). At each stage most beneficial n merge pairs are selected and merged (steps 13 to 14).

The schedule estimation algorithm, which has not been shown due to paucity of space works as follows: Each of the nodes in the particular merged group of chains is scheduled taking into account data dependency. For scheduling we assume that each operation takes one cycle. The basic scheduling algorithm is list scheduling with distance from sink as the heuristic. If at any stage a node has any outgoing edge, then the node connected to that particular edge is marked dirty. However, the schedule of this particular node and all its children is not updated till it is needed. If at a later stage any node has an incoming edge from this node or its children, then the schedule of the dirty node along with the schedule of all its connected nodes is updated. This leads to a significant saving in computation. Binding: The next step is to bind these groups of chains to clusters. Although the value of n clusters is quite small (not more than sixteen in our case), still the no. of possible bindings is quite large. This effectively rules out any exhaustive exploration of the design space. The following observation, established through experimentation, makes this stage extremely important: while a good result propagation algorithm can affect the schedule length by around a factor of two, a poor binding at times can lead to schedules which are more than three to four times larger than the optimal ones.

The binding heuristics are driven by the impact which communication latency of a particular node will have on final schedule. In effect we recognize that the data transfer edges from each of the merged group of chains to some other group are not equivalent. Some are more critical than the others in the sense that they would affect the schedule to a larger extent. The heuristics try to capture this, without explicit scheduling. We calculate the ASAP and ALAP schedules for each of the individual nodes. A first order estimate of this impact is given by the mobility of each individual node. Say, we have a communication edge from A i to A j , and ASAP and ALAP schedules for these nodes are a i , a j and l i , l j respectively. Then if (a jl i ) ≥ δ, where δ is the maximum communication distance between any two clusters, then this edge is not critical at all. As there is enough slack to absorb the effect of even the largest communication latency. On the other hand if, (l j = a i + 1) the node has zero mobility and is thus most critical. We calculate the weight of each communication edge as follows:

W i, j = max 0, δ - a j +l j 2 -a i +l i 2
While weighting measure is able to segregate non-critical edges from critical ones, it is not able to distinguish clearly between edges whose nodes have equal mobility. To take this second effect into consideration, we also pull in the distance from sink, or path length for each of the source nodes. This path length when multiplied with W i, j, gives us the final weight for each of the communication edges. Bind both nodes of this edge to closest clusters 5: end while 6: while (Not all clusters have been considered) do end if 13: end while Algorithm 2, shows the binding algorithm. The algorithm works on a weighted connectivity graph, which is generated as discussed above. The initial part of the algorithm (step 2 to 5) is basically a greedy one. While it seems to work well for architectures which communicate only in one direction, the algorithm fails to take advantages for architectures with bidirectional connectivity (buses). Partially motivated by this and partially by [START_REF] Lapinskii | High quality operation binding for clustered VLIW datapaths[END_REF], we thus bring in an additional iterative improvement phase, by performing a local search around this initial binding (step 6 to 13). Scheduling: The scheduling phase is architecture specific. We have separate schedulers for multi-cycle RF-to-RF type architectures and pipelined bus architectures. Although a few scheduling algorithms for clustered architectures have been reported in literature, they all are specifically meant for single cycle RF-to-RF type of architectures [START_REF] Desoli | Instruction Assignment for Clustered VLIW DSP Compilers: A New Approach[END_REF][START_REF] Lapinskii | High quality operation binding for clustered VLIW datapaths[END_REF][START_REF] Sanchez | Instruction scheduling for clustered VLIW architectures[END_REF]. Our scheduling algorithm again is a list scheduling algorithm with distance of the node from sink as the heuristic. What it additionally contains is steps to transfer data from one cluster to other. The result propagation algorithm, tries to move data to clusters using the bus paths by scheduling transfer operations.

Algorithm 2 Binding Algorithm

Experimental Results and Observations

We ran our experiments for a set of media applications. The main sources of benchmarks are MediaBench I [START_REF] Lee | Mediabench: A tool for evaluating and synthesizing multimedia and communicatons systems[END_REF], proposed MediaBench II [START_REF] Fritts | MediaBench II -Technology, Status, and Cooperation[END_REF] and DSP-Stone [START_REF] Zivojinovic | DSPStone -A DSP-oriented Benchmarking methodology[END_REF]. Results are shown in Figures 3, 4 and5. In Figure 3, results are grouped under numbers of the form (xB, yL). Here x denotes the number of buses and y denotes the bus latency. From the figure it is clear that performance comparable to point to point connected architectures is achieved by 8, 1, 16, 1 and 16, 2. configuration if the cycle time is not considered. However, such a solution is very expensive due to the extremely high number of buses required. Also, as shown in Section 3, global buses with a single cycle latency lead to a decrease in the overall clock period by up to a factor of five leading to a drastic decrease in overall performance (Figure 5. Another interesting feature is that the performance varies asymptotically with x/y i.e. the average data transferred per cycle. While running the buses at frequencies slower than the processor is one alternative, another one is to explicitly pipeline the buses taking clock-period into account. To simplify scheduling, we assume a homogeneous configuration of buses. Results for these configurations are shown in Fig- ure 4. Here results are again grouped under various numbers of the form (xB, yS, zL). Where, x denotes the number of buses, y, bus stride and z latency of each path between two consecutive appearance of registers in bus. Bus stride is the number of clusters skipped after which a pipeline register is introduced. Whereas for a stride of two, the inter-cluster interconnect does not appear in the critical path for a stride of four, it does. Therefore, for this stride we have shown results only for a latency of two. Another consideration is the divisibility of N clusters by y. As a consequence we have only been able to show results for four, eight and sixteen cluster configurations. From Figure 4 it is clear that the performance of pipelined buses is severely limited. To analyze this we need to consider the factors which limit performance of clustered architectures. These are required communication bandwidth and communication latency. Bus based architectures invariably suffer from increased latencies as compared to direct communication. This is due to the fact that an additional transfer (copy) instruction needs to be scheduled if data has to be moved between clusters. Whereas introducing registers in buses allows the simultaneous usage of various links in buses for local communication, this does come with a penalty of one additional cycle latency. Correlating with results of multi-cycle buses in Figure 3, it is evident that a large bandwidth is required for local transfers, however this is advantageous if the transfer does not incur any additional penalty. However, this is not the case with configurations which we have shown here as that is unrealistic (see Table 1).

(2B,1L) (2B,2L) (4B,1L) (4B,2L) (4B,4L) (8B,1L) (8B,2L) (8B,4L) (16B,1L) (16B,2L) (16B,4L)
Using the clock-period results it is possible to obtain a better picture of the final processor performance. Taking Write Across -1 architecture as the baseline case, we scale the reported ILPs using following formula: ILP e f f ective, x = ILP original, x * Clk Period WA. 1 Clk Period x . Here x is the architecture type under consideration, ILP original, x , is the original ILP reported in [START_REF] Gangwar | Impact of Inter-cluster Communication Mechanisms on ILP in Clustered VLIW Architectures[END_REF], Clk Period WA.1 is the clock-period of Write Across-1 type of architecture and Clk Period x is the clock period of architecture under consideration. considering only number of cycles. However, it needs to be noted that there is considerable variation in performance if applications are considered individually.

Conclusions and Future Work

In this paper we have presented an exhaustive evaluation of bus based inter-cluster interconnects in clustered VLIW processor. We have synthesized the processors with a variety of inter-clutter interconnects and obtained the achievable clock-period values. These values have in turn been used to arrive at realistic bus transfer latencies. The poor performance of such bus based interconnect in sharp contrast to the direct-communication type of interconnects speaks heavily against their usage. These results become all the more significant if one takes into view the fact that almost all the research architectures and quite a few of the commercial ones have based their work on these architectures. Our current work in progress focuses on high-level estimations for direct-communication type architectures to customize them on a per application (domain) basis.

2 Figure 1 .

 21 Figure 1. Some Inter-cluster Interconnect Architectures

  Figure 2. DSE Framework

1 : 6 :

 16 resources ⇐ All Clusters Res. per cluster 2: do pure vliw scheduling(graph, resources) 3: while (no o f chains(graph) > n clust) do 4: for (i = 1 to no o f chains(graph)) do 5: for ( j = 0 to i) do dup graph ⇐ graph dup(graph) 7: dup chains ⇐ graph dup(chains) 8: merge chains(dup graph, du chains, i, j) 9: c i, j ⇐ est sched(dup graph, dup chains) SORT (C); Sorting priority function: i) Increase in sched length ii) Larger communication edges, if sched length is same iii) Smaller chains, if sched length and communication edges are equal 13: n merge ⇐ MIN(0.1 * n chains , n chainsn clust ) 14: merge top n merge chains from A 15: end while The next phase is the clustering phase (Algorithm 1).

7 : 8 : 11 :

 7811 prev sched len ⇐ sched len(graph) Swap binding for two adjacent clusters 9: sched len ⇐ schedule graph(graph) 10: if (prev sched len < sched len) then Swap back bindings for these clusters 12:

Figure 3 .

 3 Figure 3. Average Variation in Performance for Multicycle Configurations

Figure 4 .

 4 Figure 4. Average Variation in Performance for Pipelined Bus Configurations

Figure 5 Figure 5 .

 55 Figure 5. Effective Variation in Performance for UMC 0.13µ ASIC Technology and Multi-cycle Configurations

Table 1 .

 1 Clock Period (ns) for UMC 0.13µ ASIC Tech.

	N Clust	WA.1	RA.1	WA.2	RA.2	WR.2	RF
	2	0.851	0.859	1.036	0.894	0.891	1.152
	4	0.883	0.944	1.030	1.001	0.956	1.987
	6	0.929	0.977	1.104	1.015	1.051	2.760
	8	1.005	1.065	1.077	1.108	1.112	3.891
	10	1.026	1.064	1.126	1.091	0.995	5.110
	N Clust	WA.1	RA.1	WA.2	RA.2	WR.2	RF
	2	39.45	39.34	39.42	39.16	39.33	43.43
	4	36.71	36.65	36.63	36.53	36.65	36.67
	6	35.69	35.66	35.73	35.61	35.55	35.71
	8	34.90	34.62	35.02	34.82	34.84	34.98
	10	34.89	34.84	34.95	34.73	34.81	34.89

Table 2 . Interconnect Area (as % of Chip Area) for UMC

 2

0.13µ ASIC Tech.

1 :

 1 connect graph ⇐ gen connect graph(graph, chains) 2: while (Not all nodes in connect graph are bound) do

	3:	source node ⇐ f ind highest wt edg(connect graph)

4:

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

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


C Nácul
email: nacul@ics.uci.edu

Tony Givargis
email: givargis@ics.uci.edu

Lightweight Multitasking Support for Embedded Systems using the Phantom Serializing Compiler

Embedded software continues to play an ever increasing role in the design of complex embedded applications. In part, the elevated level of abstraction provided by a high-level programming paradigm immensely facilitates a short design cycle, fewer errors, portability, and reuse. Serializing compilers have been proposed as an alternative to traditional OS techniques, enabling a designer to develop multitasking applications without the need of OS support. In this work, we outline the inner workings of the Phantom serializing compiler and analyze the quality of the generated code with respect to memory and processing overheads. Our results show that such serializing compilers are extremely efficient, making them ideal to be used in design of highly parallel applications (e.g., multimedia, graphics, and signal processing applications).

INTRODUCTION

The functional complexity of embedded software continues to rise due to a number of factors such as sophisticated user interfaces, seamless operation across multiple communication protocols, need for security, and so on. Consequently, the development of embedded software poses a major design challenge. At the same time, the elevated level of abstraction provided by a high-level programming paradigm immensely facilitates a short design cycle, fewer errors, portability, and IP reuse. In particular, the concurrent programming paradigm is an ideal model of computation for design of embedded systems, which often encompass inherent concurrency.

Furthermore, embedded systems often have stringent performance requirements and, consequently, require a carefully selected and performance tuned embedded processor to meet specified design constraints. In recent years, a plethora of highly customized embedded processors have become available. As an example, Tensilica [11] provides a large family of highly customized applicationspecific embedded processors.

Such embedded processors ship with cross-compilers and the associated tool chain for application development. However, to support a multitasking application development environment, there is a need for an operating system (OS) layer that can support task creation, task synchronization, and task communication.

Such OS support is seldom available for each and every variant of the base embedded processor. In part, this is due to the lack of system memory and/or sufficient processor performance to afford the high performance penalty of having a full-fledged OS (e.g., in the case of micro-controllers such as the Microchip PIC [7] and the Philips 8051 [9]). Additionally, manually porting and verifying an OS to every embedded processor available is a high-cost job, in terms of time and money.

To fill the gap in realizing a multitasking application targeted at a particular embedded processor, researchers have proposed Phantom [START_REF] Nacul | Code Partitioning for Synthesis of Embedded Applications with Phantom[END_REF]. Phantom provides a fully automated source-to-source translator, taking a multitasking C program extended with POSIX as input and generating an equivalent, embedded processor independent, single-threaded ANSI C program, to be compiled using the embedded processor-specific tool chain. The output of Phantom is a highly tuned, correct (i.e., by construction) ANSI C program that embodies the application-specific embedded scheduler and dynamic multitasking infrastructure along with the user code.

In this work, we outline the inner workings of the Phantom serializing compiler. Specifically, we provide details on the architecture of Phantom generated code, such as memory layout, code organization, and the scheduler. Moreover, we analyze the quality of the Phantom generated code with respect to memory and processing overheads. Through our experiments, we show that such serializing compilers are extremely efficient, making them ideal to be used in design of highly parallel applications (e.g., multimedia, graphics, and signal processing applications).

Phantom is a new approach in addressing the challenge of multitasking support for embedded applications. We are unaware of any related work that use a similar compiler-based technique as that used in Phantom. However, we can identify three different approaches that address some of the design challenges solved with Phantom, namely a Virtual Machine (VM) based technique, template-based OS generation techniques, and static scheduling techniques. In the VM approach, portability is achieved, but with the overhead imposed by the VM layer. Moreover, the VM has to be ported to each new platform. To improve on these, solutions like JITs [START_REF] Aycock | A Brief History of Just-In-Time[END_REF] and customized VMs for embedded platforms [START_REF] Verdiere | Speedup Prediction for Selective Compilation of Embedded Java Programs[END_REF] have been proposed. In the template based OS generation, a custom OS is generated from a generic library of templates [START_REF] Gauthier | Automatic Generation and Targeting of Application-Specific Operating Systems and Embedded Systems Software[END_REF][5] [START_REF] Vercauteren | A Strategy for Real-Time Kernel Support in Application-Specific HW/SW Embedded Architectures[END_REF]. However, no single generic OS template can be used in the variety of embedded processors available. Finally, the static scheduling techniques [START_REF] Cortadella | Task Generation and Compile-Time Scheduling for Mixed Data-Control Embedded Software[END_REF][3] [START_REF] Lin | Efficient Compilation of Process-Based Concurrent Programs without Run-Time Scheduling[END_REF] solve the static, a priori known, tasks class of problems, without addressing the dynamic multitasking issues.

The remainder of this work is organized as follows. In Section 2, we briefly describe Phantom, the source to source translator. In section 3, we discuss the architecture of the code generated by Phantom. In Section 4, we describe our experiments and give insight into the performance of code generated with Phantom. Finally, in Section 5, we state our conclusions. which is a subset of the standard POSIX interface [START_REF]POSIX Open Group[END_REF]. These primitives provide functions for task creation and management (e.g., task create, task join, etc.) as well as a set of synchronization variables (e.g., mutex t, sema t, etc.). Output of Phantom is a singlethreaded strict ANSI C program Poutput that is equivalent in functionality to Pinput. More specifically, Poutput does not require any OS support and can be compiled by any ANSI C compiler into a self sufficient binary for a target embedded processor.

THE PHANTOM APPROACH

Introduction

Figure 1 is the block diagram of Phantom. The multitasking C application is compiled with a generic front-end compiler to obtain the basic block (BB) control flow graph (CFG) representation. This intermediate BB representation is annotated, identifying Phantom primitives. The resulting structure is used by a partitioning module to generate non-preemptive blocks of code, which are called atomic execution blocks (AEBs), to be executed by the scheduler. Every task in the original code is partitioned into many AEBs, generating an AEB Graph. Then, a live variable analysis is performed on the AEB graphs and the result is fed back to the partitioning module to refine the partitions until acceptable preemption, timing, and latency are achieved. The resulting AEB graphs are then passed to the code generator to output the corresponding ANSI C code for each AEB node. In addition, the embedded scheduler, along with other C data structures and synchronization APIs are included from the Phantom system support library, resulting in the final ANSI C single-threaded code.

In the current version, Phantom is able to handle soft, firm, and event-driven real-time applications. All the modules pictured in Figure 1 are implemented and can be used in the automatic code generation process. Next, we briefly present the major components of Phantom. For a more complete description of these components, including discussions about code partitioning, please refer to [START_REF] Nacul | Code Partitioning for Synthesis of Embedded Applications with Phantom[END_REF].

Scheduling and Synchronization

We define the basic unit of execution, scheduled by the scheduler, an atomic execution block (AEB). An AEB is a block of code that is executed in its entirety prior to scheduling the next AEB. A task Ti is partitioned into an AEB graph whose nodes are AEBs and edges represent control flow. Consider the example shown in Figure 2, implementing a game between two tasks that are picking up random numbers, and the corresponding CFG of function game of the example, pictured in Figure 3. Figure 3(a) shows the output of the compiler front-end that is fed to the partitioning module, annotated with the Phantom primitives. The partitioner adds two control basic blocks, setup and cleanup, as shown in Figure 3 We note that an AEB node may be composed of one or more basic blocks. The termination of an AEB region transfers the control back to the scheduler. The scheduler, then, has a chance to activate the next AEB, from either the same task or from another task that is ready to run. A detailed description of the code layout and the scheduler implementation is in Section 3.

It may happen that a function f in the original input code is phantomized (i.e., partitioned) into more than one AEB, each one of them being implemented as a separate region of code. In that case, there is a need for a mechanism to save the variables that are live on transition from one AEB to the other, so that the transfer of one AEB to another is transparent to the task. Also, every task must maintain its own copy of local variables during the execution of f as part of its context. Phantom solves this issue by storing the values of local variables of f in a structure inside the task context, emulating the concept of a function frame. The frame of a phantomized function f is created in the fsetup block, and cleaned up in the last AEB of f . These operations are included by the partitioner for every function that needs to be phantomized. They are represented by the dark nodes in Figure 3(b).

During runtime, there is a need to maintain, among others, a reference to the next AEB node that is to be executed some time in the future, called next aeb, in the context information for each task that has been created. When a task is created, the context is allocated, the next aeb field is initialized to the entry AEB of the task, and the task context is pushed onto the queue of existing tasks to be processed by the embedded scheduler.

The embedded scheduler is responsible for selecting and executing the next task, by activating the corresponding AEB of the task to be executed. The next aeb reference of a task Ti is used to resume the execution of Ti by jumping to the region of code corresponding to the next AEB of Ti. At termination, every AEB updates the next aeb of the currently running task to refer to the successor AEB according to the tasks's AEB Graph.

The scheduling algorithm in Phantom is a priority based scheme, as defined by POSIX. The way priorities are assigned to tasks, as they are created, can enforce alternate scheduling schemes, such as round-robin, in the case of all tasks having equal priority, or earliest deadline first (EDF), in the case of tasks having priority equal to the inverse of their deadline. Additionally, priorities can also be changed at run-time, so that scheduling algorithms based on dynamic priorities can be implemented.

Phantom implements the basic semaphore (sema t in POSIX) synchronization primitive, upon which any other synchronization construct can be built. To implement semaphores, there is a need to add to a task Ti's context an additional field called status. Status is one of blocked or runnable and is set appropriately when a task is blocked waiting on a semaphore.

A semaphore operation, as well as a task creation and joining, is what is called a synchronization point. Synchronization points are identified by a gray node in Figure 3. At every synchronization point a modification in the state of at least one task in the system might happen. Either the current task is blocked, if a semaphore is not available, or a higher priority task is released on a semaphore signal, for example. Therefore, a function is always phantomized when synchronization points are encountered, and a call to a synchronization function is always the last statement in its AEB. At this point, the scheduler must regain control and remove the current task from execution in case it became blocked or is preempted by a higher priority task.

Partitioning

The partitioning of the code into AEBs is key to implementing multitasking at a high abstraction level. Recall that boundaries of AEB represent the points where tasks might be preempted or resumed for execution. Some partitions are unavoidable and must be performed for correctness, specifically, when a task invokes a synchronization operation, or when a task creates another task.

However, partitioning beyond what is needed for correctness impacts timing. In general, partitioning will determine the granularity level of the scheduling (i.e., the time quantum), as well as the task latency. A complete discussion on partitioning, with a deeper analysis of different partitioning schemes and algorithms for exploring different code partitions, is described in a separate work [START_REF] Nacul | Code Partitioning for Synthesis of Embedded Applications with Phantom[END_REF].

Experiments with Phantom

The Phantom approach has been successfully applied to a number of applications developed for testing the translation flow [START_REF] Nacul | Code Partitioning for Synthesis of Embedded Applications with Phantom[END_REF]. In [START_REF] Nacul | Code Partitioning for Synthesis of Embedded Applications with Phantom[END_REF]. In general, multitasking applications synthesized with Phantom show a much improved performance (i.e., low operating overhead). The reason is two fold. First, the generated application encompass a highly tuned multitasking framework that meets the application-specific needs. Second, the multitasking infrastructure itself is very compact and efficient, resulting in a much lighter overhead for context switching, task creation, and synchronization.

With regard to different partitioning schemes, it was shown that there is a clear correlation between partition and performance metrics, like latency and multitasking overhead [START_REF] Nacul | Code Partitioning for Synthesis of Embedded Applications with Phantom[END_REF]. Different code partitioning can reduce application latency by as much as two orders of magnitude, at the expense of an increase of the multitasking overhead by a factor of 120 [START_REF] Nacul | Code Partitioning for Synthesis of Embedded Applications with Phantom[END_REF]. The effect of partitioning is highly dependent on the application structure itself.

GENERATED CODE ARCHITECTURE

Code Layout

The code layout of the input program Pinput, once processed by a C pre-processor, is conceptually organized in two sections, as shown in Figure 4. The first section contains all global declarations and variables, while the second section contains a set of functions. One of these functions is the main function, i.e., the entry point of the application. The Phantom output program Poutput is organized in five sections, as shown in Figure 4. The first sec-tion contains global declarations and variables. The second section contains a set of functions that are not phantomized. The third section contains a set of functions, each corresponding to one phantomized function of Pinput. The fourth section contains a single function, called scheduler, which contains the code for all the phantomized functions, as well as the scheduling algorithm. Finally, the fifth section contains the main function of Poutput.

All the functions of Pinput are analyzed and classified in two groups: the phantomized and non-phantomized functions. A function is phantomized if (i) it is the entry point of a task, (ii) contains a synchronization primitive(s), or (iii) calls a phantomized function. Note that, since main is the entry point of the first task that is created by default, it is automatically phantomized.

The second section of Poutput contains all non phantomized routines, copied over from Pinput. The third section contains the setup functions, each corresponding to a phantomized function of Pinput. A setup function is responsible for allocating the frame structure of each phantomized function. The frame and task context memory layout is described in a later subsection.

The next section of Poutput contains the phantomized functions, along with the scheduler. All of these (i.e., the phantomized functions and scheduler) are embodied into a single C function of Poutput, namely scheduler. Recall that a phantomized function is partitioned into a set of AEBs, aeb0, aeb1, . . . , aebn. An AEB aebi is in turn composed of one or more basic blocks Bi,enter, Bi,2, Bi,3, . . . , Bi,exit. By definition, execution of AEB aebi starts at the entry basic block of Bi,enter and ends at the exit basic block Bi,exit. The exit basic block Bi,exit of AEB aebi transfers control to a special basic block sched that serves as the entry point of the scheduling algorithm. The scheduler function contains all these basic blocks, starting with basic block sched, in low-level C, using C labels to denote basic block boundaries and C goto statements as a branching mechanism. The scheduling algorithm is described in a later subsection.

Finally, the fifth section of Poutput, contains an implementation of the main function, which creates a single task, corresponding to the main entry point of Pinput, and calls the scheduler function to invoke the scheduling algorithm.

Memory Layout

Each time a task is created, memory is allocated to store its context. At any given time, a special global variable, named current, is made to point to the context of the running task by the scheduler. Moreover, a queue of running tasks, named tasks, is maintained, according to the priorities of each task, by the scheduler, as described in the following subsection. The context of a task is further defined in Figure 5. The stack is managed by the setup and the cleanup AEBs of phantomized functions. Specifically, when a function g of the current task calls a phantomized function f , the setup function fsetup is invoked. Then, fsetup pushes f 's frame onto the stack of the current task, copies f 's arguments to the frame, saves the return AEB of the calling function g, and makes the current task's next AEB point to the entry AEB of f . The structure of the setup function is shown in Figure 7. Conversely, when a called function f complete its execution, the cleanup AEB aebexit of f performs the following. First, it restore the current task's next AEB to point to the next AEB of the calling function g, which was stored in the frame of f by the f 's setup function. Then, it pops the frame of the current task's stack, as shown in Figure 8.

struct

Scheduler

The scheduler's code is included in the same C function containing the phantomized functions, called scheduler. The scheduling algorithm makes use of a priority queue that stores all the runnable tasks. The priority queue guarantees that the highest priority task is always the first task in the queue. In case of a priority tie among two or more tasks, the scheduler implements a round-robin scheme among them, so that all equal-priority tasks fairly share the processor. When a task is selected by the scheduler for execution, the global current pointer is updated accordingly.

Each AEB returns the execution to the scheduler upon termination. This is accomplished through a jump to the first basic block of the scheduler. Once the scheduler determines the next task Ti to be executed, it uses Ti's next aeb reference to transfer control back to the next AEB. The transfer of control from the scheduler to the next AEB of the running task is implemented using a switch statement containing goto's to all AEB's of the application. When the AEB completes execution, control is returned to the scheduler, which then pushes the current task's context back to the queue of runnable tasks if the task is not blocked or terminated. An overview of the scheduler is depicted in Figure 9. An optimization in the scheduling algorithm allows a task to execute more than one AEB each time it is selected from the priority queue. We call this a short context switch. With the short context switch, it is possible to save the overhead of pushing/popping a new task from the priority queue with a bypass. A full context switch is executed every so often, alternating short and full context switches with a pre-determined ratio. A full context switch ensures a fair sharing of the processor among equal-priority tasks.

In order to implement the short context switch, we add a counter to the scheduling algorithm, used to keep track of the number of consecutive short context switches performed. The counter is initialized to a value representing the ratio between short and full context switches. The value of the counter defines a time quantum, i.e., a number of consecutives AEBs of the same task to be executed before a full context switch. The counter is decremented at every short context switch, and a full context switch is executed once the counter reaches zero and expires. Obviously, a full context switch can happen before the counter expires, in the case that a task is blocked or terminates. Alternatively, a timer can be used in place of a counter, yielding a real time-sharing of the processor in the round-robin approach. Figure 10 shows the optimized scheduler algorithm, incorporating the short context switch optimization.

In Phantom, for efficiency reasons, a limited priority queue is implemented. A limited priority queue is one that allows a finite, and a priori known, number of priority levels (e.g., 32). However, this does not pose any limitations, since the number of priority levels, required by the application, can be provided to the Phantom serializing compiler. The implementation of the priority queue is as follows. A separate array-based queue is allocated for each priority level, which are accessed by the scheduler in order of highest to lowest priority. Manipulation of the array-based queues at each priority level is very efficient, and takes constant time. At any given point, a reference is maintained to the highest non-empty priority queue. Given this, the overall access to the queue of runnable tasks by the scheduler requires constant running time, regardless of the number of runnable tasks.

EXPERIMENTAL RESULTS

A set of synthetic benchmarks was implemented to evaluate the overhead imposed by the Phantom multitasking infrastructure. Various parameters of Phantom were evaluated, like context switching overhead, task creation cost, task joining cost, and mutex synchronization cost.

Cost was measured as the average number of instructions executed on the host processor for performing a particular operation (e.g., task creation, task joining, etc.) We compiled and executed the applications on a UltraSPARC-IIe workstation, 500 Mhz, with 256Mb of RAM running Solaris operating system. We used cputrack tool to obtain number of instructions and CPU cycles executed by a target program. (cputrack uses hardware counters to track CPU usage). All benchmarks were compiled with GCC v3.3. The time cost of each metric was calculated from the average CPI (cycles per instruction) of each benchmark, associated with the processor cycle time.

For each benchmark, designed to measure a particular metric, we first obtained a baseline execution count. The baseline execution count accounted for all the computation code less the Phantom generated multitasking infrastructure. Then, the multitasking infrastructure was enabled and instruction counts were re-evaluated. The difference between the baseline and the version with the multitasking infrastructure gave us a measure of the performance of Phantom for that metric. All experiments in this phase were performed using at most one task active and a single priority level. On average, Phantom multitasking infrastructure overhead is small, and has an impact of less than 1% in the execution time of the synthetic benchmarks. Our results are summarized in Table 1.

Next, we evaluated the impact of multiple task and multiple priorities in task context switch. In these experiments, we used a mixed scheduler, with a 10:1 ratio between short and full context switch. Figure 11 shows the results. Here, the horizontal axis of the plot depicts the number of runnable tasks in the system (i.e., one of 2, 10, 20, 50, 100, 500, and 1000 tasks). The vertical axis of the plot depicts the average number of instructions for performing a context switch.

We note from Figure 11 that the overhead of context switch is small, fairly constant, and independent of the number of runnable tasks in the system. A similar result was obtained for task creation overhead. Contrary to intuition, there is initially a slight decrease in the context switch time when the number of tasks increase. With a small number of tasks, there are more reorganizations in the priority queue, since every context switch can possibly insert a task with a different priority in the queue. As the number of tasks increase, reorderings are less constant, since a task with the same priority is likely to be in the queue already. Therefore, context switch is slightly faster. Nevertheless, the impact of Phantom in the execution time of the benchmarks is typically less than 1%, for the applications tested. A similar trend is observed with respect to the number of priorities, i.e., increasing the number of priorities does not have a significant impact on context switch time. As before, there is a slight difference in context switch time when few tasks are present. In this case, the priority queue has to be reorganized more often, increasing the context switch by a small margin. The efficiency of the Phantom generated code makes it practical for designing multimedia, digital signal processing, or other highly parallel applications, using the concurrent programming model.

CONCLUSIONS

In this work, we have outlined the code architecture and memory layout of Phantom serializing compiler. A serializing compiler is a source-to-source translator that takes a POSIX compliant multitasking C program as input and generates an equivalent, embedded processor independent, single-threaded ANSI C program, to be compiled using the embedded processor-specific tool chain. Serializing compilers have been proposed as an alternative solution, enabling a designer to develop multitasking applications without the need of OS support. We have also analyzed the quality of the generated code with respect to memory and processing overheads. Our results show that such serializing compilers are extremely efficient, making them ideal to be used in design of highly parallel applications (e.g., multimedia, graphics, and DSP applications).

Our future direction of research is to incorporate real-time scheduling into the Phantom serializing compiler. Specifically, we plan to allow deadline driven task scheduling using dynamic priorities. In addition, we would like to investigate power management strategies (e.g, voltage scaling, power modes, memory management, etc.) to be automatically generated by the Phantom serializing compiler.

Figure 1 :

 1 Figure 1: Phantom Compiler Architecture

Figure 2 Figure 3 :

 23 Figure 2: Code Example

Figure 3 (

 3 c) shows the AEB graph of function game as being composed of AEBs aeb 0, aeb 1, aeb 2, aeb 3, aeb 4 and aeb 5.

Figure 4 :

 4 Figure 4: Code Layout of Input and Output Programs

Figure 5 :

 5 Figure 5: The Task Context Data Structure Most of the fields of this structure were discussed earlier. Here, we focus on the stack field of a context. The purpose of the stack is to store the task-local data of each phantomized function. Moreover, the choice of a stack is to allow for recursion and nested function calls. The collection of all this data for a phantomized

Figure 6 :

 6 Figure 6: The Frame Data Structure

Figure 7 :

 7 Figure 7: Code Structure of Setup Functions

Figure 8 :

 8 Figure 8: Code Structure of Cleanup AEB

Figure 9 :

 9 Figure 9: Code Structure of Scheduling Function

Figure 10 :

 10 Figure 10: Code Structure of Optimized Scheduling Function

Figure 11 :

 11 Figure 11: Phantom Context Switch Cost in Instructions with Multiple Threads and Multiple Priorities

  (b), and subsequently divides the function code into a number of AEBs,

	typedef struct {	int main(int argc, char **argv) {
	int id;	pthread_t t1, t2;
	pthread_mutex_t *lock;	int r;
	pthread_mutex_t *unlock;	struct game_t g1, g2;
	}game_t;	pthread_mutex_t m1, m2;
	int winner;
	void *game(void *arg) { /* THREAD */	pthread_mutex_init(&m1, NULL);
	game_t g = (game_t *)arg;	pthread_mutex_lock(&m1);
	int num;	pthread_mutex_init(&m2, NULL);
		pthread_mutex_lock(&m2);
	while(1) {	g1.id = 1;
	pthread_mutex_lock(g->lock);	g2.id = 2;
	if(winner) {	g1.lock = g2.unlock = &m1;
	pthread_mutex_unlock(g->unlock);	g2.lock = g1.unlock = &m2;
	return NULL;	winner = 0;
	}	pthread_create(&t1, NULL, game, &g1);
	else {	pthread_create(&t2, NULL, game, &g2);
	num = rand();	pthread_mutex_unlock(&m1);
	if(num == g->id)	pthread_join(t1, NULL);
	winner = g->id;	pthread_join(t2, NULL);
	pthread_mutex_unlock(g->unlock);
	}	printf("Winner is %d\n", winner);
	}
	}	}

Table 1 :

 1 Phantom Multitasking Performance Results

						No optimization (-O0)	With optimization (-O2)
				Metric		Instructions Time (µs) Instructions Time (µs)
				full context switch	427	1.81	206	0.47
				short context switch	82	0.35	37	0.08
				mixed context switch (10:1)	124	0.52	58	0.13
				task creation		1113	4.74	833	1.90
				task join		506	2.15	227	0.52
				mutex lock		68	0.29	40	0.09
				Average Context Switch Overhead
		160
	Context Switch overhead (Instructions)	60 80 100 120 140
		40	1	10	100	1000
				Number of Tasks
			1 Priority -O0 2 Priorities -O0 4 Priorities -O0	8 Priorities -O0 1 Priority -O2 2 Priorities -O2	4 Priorities -O2 8 Priorities -O2

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

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

Acknowledgment

This work was supported by the National Science Foundation award number CCR-0205712 and by CAPES Foundation, Brazil, award number 1054/01-5.


Domenico Barretta

William Fornaciari

Mariagiovanna Sami

Multithreaded Extension to Multicluster VLIW Processors for Embedded Applications

Instruction Level Parallelism (ILP) extraction for multicluster VLIW processors is a very hard task. In this paper, we propose a retargetable architecture that can exploit ILP and thread level parallelism jointly, thus allowing an easier parallelism extraction and improving the performance with respect to traditional multicluster VLIW processors.

Introduction

In current Very long Instruction Word (VLIW) architectures, exploiting high amounts of latent Instruction Level Parallelism (ILP) may be a very difficult task [START_REF] Faraboschi | Instruction scheduling for instruction level parallel processors[END_REF], because the degree of ILP is mainly limited by the number of functional units that can work simultaneously when they are connected to a single register file.

Multicluster VLIW architectures tackle this problem by introducing more than one register file and clustering the functional units based on the register files they are connected to. This approach allows higher ILP levels than the base VLIW architectures. However, since each functional unit can access just its own register file, communication may have a significant negative impact on the overall performance when data are moved from a register file to another.

Furthermore, with few exceptions, complex applications do not exhibit a constantly predominant type of parallelism through the set of procedures of which they are composed and massive ILP can be found only in some segments of the application, leading to low usage of VLIW CPU resource. This fact limits the efficiency of highly parallel architectures when executing such an application and is the reason for the interest in flexible architectures that can exploit different types of parallelism in order to increase the overall performance. Some examples of this trend are constituted by [1,[START_REF] Espasa | Simultaneous multithreaded vector architecture: Merging ILP and DLP for high performance[END_REF][START_REF] Molina | Trace level speculative multithreaded architecture[END_REF][START_REF] Tsai | The superthreaded processor architecture[END_REF]. All the cited examples are based on superscalar architectures.

Other architectures that exploit both ILP and thread level parallelism are dynamically scheduled architectures. In our case we must confront with the problem of introducing thread level parallelism in a "pure" VLIW processor, that is therefore totally static.

The proposed architecture

The goal of our work is introducing thread level parallelism in a multicluster VLIW processor by allowing each cluster to execute a different thread. Since this approach is very scalable, we will consider for simplicity a processor that is composed of two clusters.

The main idea is to design a processor that can switch at run time between two different computation models. In ILP mode all clusters execute one single thread using long instructions (bundles) composed of up to 2M possible operations (where M is the issue width). In MT mode each cluster executes a different thread using bundles composed of up to M operations.

Instruction issue unit (IIU) and instruction cache are strictly correlated, therefore they must be designed jointly so that both ILP and MT fetch behaviors may be implemented.

Consider a single-ported, n-way set associative (where n is the number of clusters) multibank instruction cache composed by 2M banks. In ILP mode we can fetch 2M operations from the only program counter in use. In MT mode, at each cycle we fetch 2M instructions -starting from the address pointed by the program counter of a thread -and store the instructions in a buffer. At the following cycle, we fetch from the other program counter. This solution allows the issue, at each cycle, of M instructions per thread, while reading from the cache 2M consecutive instructions, as described in Fig. 1. The control signal named T S (Thread Selection) is applied either to select the program counter to access the instruction cache or to enable the input for the correct instruction buffer. The addressing logic between the instruction buffer and the instruction issue unit is used to select the correct M operations in the buffer to be issued.

In the original architecture we have just one branch unit that computes the program counter. Since the proposed architecture may execute instructions from more than

Figure 1. The proposed instruction issue mechanism

one control flow, we need a branch unit for each program counter we introduce. We need therefore a branch unit per cluster. This allows a simple way for each cluster to update its program counter based on the subroutine in execution.

In ILP mode, the buffers are bypassed, and the T S control signal is forced to always be zero, so that the program counter from cluster 0 is always sent to the instruction cache.

Other parts of the architecture have to be replicated, such as memory protection units, control registers, and so on. Furthermore, memory protection units must be modified to tackle the problem of possible concurrent memory operations accessing the same address.

Decision about which parts of the code should be run in ILP mode and which parts should be run in MT mode must be taken by the programmer. Source code is by default compiled for ILP mode and the programmer must explicitly call a function to create threads to be run in MT mode. The call is very similar to the traditional "create thread" call, with the exception that one thread per cluster must be created. The compiler automatically inserts mode switch instructions and schedules the code for the correct execution mode.

Experimental results

In order to evaluate the performance improvements that can be obtained by our method, we have done several experiments by using as driving application an industrial benchmark hereinafter called jpeg2ppm. Two application kernels were also used: Aes encryption/decryption and Matrix Product.

Comparisons are provided with a reference multicluster VLIW architecture named ST200 [START_REF] Faraboschi | ST200: A VLIW architecture for media-oriented applications[END_REF]. The simulator for the proposed architecture was developed by modifying a cycle accurate Instruction Set Simulator (ISS), jointly developed by STMicroelectronics and Università di Genova [START_REF] Barbieri | A VLIW architecture simulator innovative approach for HW-SW co-design[END_REF] for micro architecture modeling of media processors and embedded systems. The performance obtained on a two clustered modified architecture was compared with the perfor-mance of a two clustered ST200 that exploits only ILP. The percentage improvement in Table 1

Concluding remarks

In this paper, we proposed a multicluster VLIW architecture that can switch at run-time between two different computation modes, ILP and MT, in order to better exploit the types of parallelism present in each part of an application.

A very important consideration is scalability: ILP exposure does not increase dramatically when the number of clusters of a VLIW processor grows beyond two. The performance of the proposed architecture on MT portions of code is, instead, expected to scale well with the number of clusters.

Table 1 . Performance Comparison

 1 is computed as Max IPC indicates the theoretical parallelism extracted by the compiler, whereas actual parallelism indicates the average number of instructions executed in a clock cycle, including stall cycles.

	CyclesN ew-CyclesOld CyclesOld	• 100. Aes Jpeg2ppm	Matrix
	RISC ops	1.24%	2.04%	8.73%
	Active cycles	-45.72%	-19.16%	-49.24%
	Inactive cycles	-13.99%	-2.19%	-39.46%
	Total cycles	-33.74%	-11.88%	-46.87%
	Max IPC	86.51%	26.21% 114.27%
	Actual IPC	52.77%	15.79% 104.63%

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


Bharat Sukhwani

Uday Padmanabhan

Janet M Wang

Nano-Sim: A Step Wise Equivalent Conductance based Statistical Simulator for Nanotechnology Circuit Design

New nanotechnology based devices are replacing CMOS devices to overcome CMOS technology's scaling limitations. However, many such devices exhibit nonmonotonic I-V characteristics and uncertain properties which lead to the negative differential resistance (NDR) problem and the chaotic performance. This paper proposes a new circuit simulation approach that can effectively simulate nanotechnology devices with uncertain input sources and negative differential resistance (NDR) problem. The experimental results show a 20-30 times speedup comparing with existing simulators.

Introduction

Due to the increasing circuit complexities and scaling limits of the CMOS devices, new devices, such as resonant tunneling diodes (RTD), resonant tunneling transistors (RTT) and carbon nanotubes (CNT), are being investigated to replace the traditional CMOS devices. Different from the existing CMOS devices, the new devices exhibit nonmonotonic I-V characteristics which consist of multiple peaks and valleys. In additional, the new devices may also demonstrate strong sensitiveness towards uncertain environmental changes. The non-monotonic I-V characteristics and the response to uncertain changes are the two main issues in the circuit modeling and simulation for the nanotechnologies.

The traditional deterministic circuit simulators, such as SPICE, estimate the nonlinear device performance by the differential conductance technique together with Newton-Raphson (NR) iterations. When used to simulate the nonmonotonic I-V characteristics, differential conductance technique introduces negative differential resistance (NDR) problem which either causes oscillations of Newton-Raphson iterations or results in false convergence during transient simulation. When applied to analyzing systems with uncertain sources, especially time variant uncertain sources, SPICE-like deterministic simulators require several hundreds to over thousands of Monte Carlo simulations at each time point. The high computational complexity at each time step makes the traditional circuit simulators unable to analyze practical circuits.

Recent research work attempts to modify the Newton-Raphson method to force it to converge to meaningful solutions. For example, Bhattacharya and Mazumder [START_REF] Bhattacharya | Augmentation of SPICE for Simulation of Circuits Containing Resonant Tunneling Diodes[END_REF] proposed current stepping and time-step auto reduction schemes to modify the SPICE simulators. Le et al. in [START_REF] Le | Circuit Simulation of Nanotechnology Devices with Non-monotonic I-V Characteristics[END_REF] proposed a piece-wise linear approach to replace Newton-Raphson iterations. The paper approximated the nonlinear nanodevice by piece-wise linear conductance. By applying an adaptive time step control mechanism together with the current stepping approach, the method generates accurate results within reasonable run time.

This paper presents two new approaches for nanocircuit modeling and analysis. The first approach models the nanodevice as step-wise equivalent conductance (SWEC) to avoid non-linear devices related Newton-Raphson iterations. In cases of non-monotonic I-V characteristics, the new approach always models the devices as positive conductance. Thus, the SWEC technique completely prevents the occurrence of the NDR problem. The second approach predicts the nanocircuit performance with uncertain inputs by a new stochastic integration technique called Euler-Maruyama method (EM). Equivalent to Euler integration approaches in the deterministic differential equations, the EM method numerically integrates the stochastic differential equations in the time domain to approximate the solutions at each time step.

The rest of this paper adheres to the following format. Section 2 summarizes the anticipated characteristics of the nanoelectronic devices and the existing techniques for the simulation of nanocircuits. Section 3 discusses the features and methodology of SWEC and its application to the resonant tunneling diodes. Section 4 explains the EM based performance prediction. Section 5 presents the results and Section 6 concludes this paper.

Background

Anticipated characteristics

Strong quantum effects in nanotransistors and nanowires manifest themselves in a level of "potentialities" and a level of "actualizations". "Potentialities" point to a probabilistic approach to the modeling of nanodevices and nanowires. "Actualizations" demand an accurate estimation approach to capture the discrete nature of the devices and wires. The proposed two approaches in this paper target both "potentialities" and "actualizations".

Actualizations.

In most RTT based nanotransistors, for example, the different discrete energy levels of each material within the transistor terminals act as barriers to current flow. Current flows only when a modulated voltage aligns these energy levels. Electrons may then resonate, "tunnel" across the base, and thus provide current flow from the emitter to the collector. The resulting I-V characteristics exhibits multiple peaks with a staircase contour that leads to the negative differential resistance problems. Figure 1(a) shows the collector current versus the collectoremitter voltage for the RTT. A similar curve applies to nanowires. Figure 1(b) illustrates the I-V characteristics of an individual carbon nanotube (CNT). The staircase characteristics of the conductance signal confirms that the carbon nanotubes behave as quantum wires. 2.1.2 Potentialities. Nanocircuits are sensitive to the environmental changes and have been widely accepted as best candidates for future biomedical sensors. However, the highly sensitive property also leads to uncertain performance. One way to predict the performance is to model the nanocircuit as a system with random inputs.

Conventional circuit simulation tools, such as SPICE, can only handle circuits with deterministic inputs. The current paper is the first one which discusses the possible extension of Euler integration method to Euler-Maruyama integration method.

In the next two sections, we demonstrate the SWEC application in the RTD-based circuit and the EM approach to analyze circuit with random inputs.

Step Wise Equivalent Conductance Model

NDR problem in Existing Simulators

SPICE-like simulators use Newton-Raphson method to solve nonlinear circuit equations. One important assumption made during these iterations is that the initial guess is close enough to the correct solution of the equation. When the initial guess is far from the correct solution, successive iterations produce oscillatory results even if the circuit is not oscillatory. Figure 2 shows the dependence of the convergence of Newton-Raphson method on the initial guess. Starting with initial guess x0 leads to oscillations between points x1 and x2 whereas having x0' as the initial guess makes the simulation converge [START_REF] Mohan | Device and Circuit Simulation of Quantum Electronic Devices[END_REF].

During transient analysis, SPICE uses the solution at one time point as the initial guess for the next iteration. This strategy works when the applied voltage change is very small. However, if the previous simulation point had a much different applied voltage than the current point, this could also lead to convergence problems. In order to avoid such problems, SPICE employs techniques such as source stepping and device limiting. But, as pointed out by [8], none of these techniques are helpful while simulating circuits having non-monotonic I-V characteristics.

Step Wise Equivalent Conductance Model

Due to the quantum effect, nanotechnology devices exhibit the staircase I-V characteristics shown in Figure 1 (a) and (b). The Step Wise Equivalent Conductance technique approximates the non-linear characteristics of a nanodevice with a stepwise constant conductance that captures the staircase characteristics accurately. It is a noniterative method and involves computation of the equivalent conductance at each time step. The technique exploits the fact that within a reasonably small time step, every nonlinear circuit behaves linearly [START_REF] Shen | SWEC: A StepWise Equivalent Conductance Timing Simulator for VLSI Circuits[END_REF]. It replaces a nonlinear circuit by a linear circuit composed of time-varying conductors. For the integration of the time-varying circuit within one time step, an effective constant conductance is determined for each time-varying conductor. The implicit integration of the equivalent linear time-varying circuit does not require solution of any non-linear equation. The method is consistent, absolutely stable and convergent.

The idea of Step-Wise Equivalent Conductance can be best explained by the nodal equation of a circuit

) ( ) ( ) ( ) ( t bu t V C t V t G
s G is the conductance matrix and is the capacitance matrix. At every time point, the value of devices' equivalent conductance is evaluated and the matrix is updated. It is important to note that the estimation of the equivalent conductance of the device at every time point is very prone to error and the accuracy of the approach depends on how the time step is chosen. Too large a time step might lead to the failure of implicit integration methods to capture the response of the circuit, while too small a time step hampers the speed of the simulator. To achieve a good tradeoff between the accuracy and speed, we need to adaptively control the time step according to the situation at every time point. The adaptive time step control scheme is explained in detail in the Section 3.4.

C G (1)

For example, the I-V characteristics of a MOS transistor are described as:

2 ) ( 2 DS DS th GS D V V V V L kW I th GS DS V V V if 2 2 th GS V V L kW th GS DS V V V (2) if
where is the transconductance parameter, W is the effective channel width, and k L is the effective channel length of the transistor. The MOS transistor's equivalent conductance is the ratio of and , evaluated at that time [3].

))

( ( t G DS I DS V 2 ) ( ) ( DS th GS V V V L kW t G th GS DS V V V DS th GS V V V L kW 2 2 th GS DS V V V
If the gate voltage is less than , the drain current is zero and hence the equivalent conductance is also zero. The transient analysis evaluates the equivalent conductance of every device at each time point using equation [START_REF] Shen | An Accurate and Efficient Delay Model for CMOS Gates in Switch-Level Timing Analysis[END_REF]. The equivalent conductance remains unchanged until the next point in time, giving rise to a stepwise signal in the time domain.

) ( GS V th V D I ) (t G
Because of the possible non-monotone behavior of the device characteristics, both SPICE (based on first order derivative of device I-V characteristics) and ACES (based on a piece wise linear approximation of the device) experience the negative differential resistance problems. SWEC, on the other hand, produces a positive equivalent conductance even for a non-monotone signal. Figure 3 (a To summarize, the SWEC approach only calculates the positive and constant equivalent conductance at each point in time. Therefore it avoids both computationally expensive solution of non-linear equations and the NDR problem.

Application of SWEC to RTDs

D V n C e e A V J kT q V n C B kT q V n C B 1 1 / ) ( / ) ( 1 tan 2 1 1 ln ) ( 1 1 ) 1 ( ) ( / 2 2 kT qV n e H V J ) ( ) ( ) ( 2 1 V J V J V J
where A , ,C , , B D H , and are device parameters which define the I-V characteristics of a particular RTD. The I-V characteristics of an RTD are shown in Figure 4. It can be divided into three regions, a first positive differential resistance region (PDR1), a negative differential resistance region (NDR) followed by a second positive differential resistance region (PDR2).

1 n 2 n if if (3)
Based on 1 st order Taylor expansion, Equation ( 5) approximates the value of the equivalent conductance of the non-linear circuit elements at the next time point: [START_REF] Schulman | Physics based RTD Current-Voltage Equations[END_REF] where is the value of the time step at and

) ( 2 ) ( ) 1 ( n G h n G n G eq n eq eq
n h n ) (n G eq
is the time derivative of the equivalent conductance evaluated at . The values of and for an RTD can be evaluated using equation ( 6) and ( 7) respectively.

n ) (n G eq ) (n G eq V V J V J G eq ) ( ) ( 2 1 V e H D V n C A kT qV n ) 1 ( tan 2 . 1 1 ln / 1 1 2 where kT q V n C B e ) ( 1 and kT q V n C B e ) ( 1 . ( 6
)
The expression for the equivalent conductance of an RTD (equation ( 6)) contains the voltage across the RTD as the only time varying quantity. Hence, the time derivative of the equivalent conductance of an RTD can be written as

/ 2 2 1 2 1 1 1 1 _ ) 1 ( tan 2 . 1 1 ln . 1 1 1 ln . 1 tan 2 . 1 1 1 2 2 V e H D V n C A e kT qHn V V n C D Dn A V D V n C kT qA n V dV dG kT qV n kT qV n RTD eq (8) 1 1 ) ( ) ( n n RTD n RTD h t V t V dt dV ( 9
)
Figure 5 shows the differential conductance result for an RTD from [START_REF] Bhattacharya | Augmentation of SPICE for Simulation of Circuits Containing Resonant Tunneling Diodes[END_REF] and stepwise equivalent conductance result from our approach. The differential conductance approach generates negative values of the conductance as the device enters the resistance decreasing region (RDR), whereas the stepwise equivalent conductance approach always generates positive values of the conductance.

(4)

Adaptive control of Time Steps

Selection of step size is one of the critical steps of circuit simulation. SWEC employs adaptive control of time step according to the situation at each time point [START_REF] Shen | SWEC: A StepWise Equivalent Conductance Timing Simulator for VLSI Circuits[END_REF]. For a given percent error, we try to maximize the size of the time step so as to speed up the simulations. The percentage local error, , at the output at time is given as

1 n t ) , ( ) , ( 1 1 n n o o n n o t t V V t t V n where
is the actual change in output voltage and is the estimated change by using the equivalent conductance model [START_REF] Shen | SWEC: A StepWise Equivalent Conductance Timing Simulator for VLSI Circuits[END_REF]. For a given value of ) , (

1 n n o t t V n o V
, the constraint on the time step can be calculated.

Figure 6 shows an inverter and its RC equivalent circuit assuming the PMOS to be off.

is the equivalent conductance of the NMOS. It can be shown that the % local error [START_REF] Shen | SWEC: A StepWise Equivalent Conductance Timing Simulator for VLSI Circuits[END_REF] will be less than

eq G _ if 0 3 i V h , 0 G C h L where dt dV dt t dV GS in ) (
Experimental results indicate that a good accuracy is achieved if these constraints are satisfied for all the devices in the circuit [4].

Figure 6 -Inverter and its RC equivalent circuit

Thus the time step constraints can be calculated for each transistor and the minimum of those can be used as the next time step, i.e.

j i V V t G C MIN h n t i i t GS n jk k j n , , ) ( 2 ,
) ( * i is the index of the transistors which are on and is the index of the nodes.

is the grounded capacitor at node .

is the sum of all the conductance connected to node at time [START_REF] Shen | SWEC: A StepWise Equivalent Conductance Timing Simulator for VLSI Circuits[END_REF].

j j C j k n jk t G ) ( j n t

Transient Simulation with Random Inputs

Circuit response with random noise is an active research topic in the analog circuit design area. Because of the uncertain behavior of nanodevices, a few recent papers [START_REF] Ferzli | Statistical estimation of leakageinduced power grid voltage drop considering within-die process variations[END_REF] [12] also discussed the power grid analysis with random current draws from nanodevices. In both research topics, the stochastic differential equation (SDE) model plays an important role in finding the expected value of the circuit response or performance.

However, as pointed out by some recent publications [START_REF] Lin | Apache's New Power Analysis Trend[END_REF], the expected value of the performance can only provide an average performance, while the transient value is also important to most applications. For example, in the power grid analysis case, even though the average voltage drop is zero, if the transient voltage drop at a certain time point exceeds certain constraints, the whole design is still going to fail. Likewise, the transient response of nanocircuit offers real time performance estimation and catches the possible signal integrity problems in the circuits. [START_REF] Quarles | Analysis of performance and convergence issues for circuit simulation[END_REF] Existing simulators only analyze circuits with deterministic inputs, the current paper is the first one discussing the transient simulation technique for nanocircuit with uncertain inputs.

Model the Input as Wiener Process

The state equation for a nanocircuit can be written as

) ( ) ( t Bu dt dx C x t G dt t Bu C xdt t G C dx ) ( ) ( 1 1 or ( 13
) with 0 ) 0 ( x x
as the initial value. Here is the response of the circuit, G and C are the parasitic matrices. Since G is time variant, Equation ( 13) also includes cases with the nonlinear nanodevices. Assume represents the random time domain input. Because of its high randomness, is generally modeled as white noise. Let x where denotes a normally distributed random variable with zero mean and unit variance; 3) For

) (t u ) (t u dt t u t dW ) ( ) ( .
) 1 , 0 ( N T v u t s 0 the increments ) ( ) ( s W t W and ) ( ) ( u W v W are independent.
For computational purposes it is useful to consider discretized cases where is specified at discrete values. We thus set for some positive integer and let denote with .

) (t W t N T dt / N j W ) ( j t W jdt t j (12)

The Euler-Maruyama Method

The Stochastic Differential Equation in Equation ( 13) can be written in integral form as

) ( ) ( ) ( ) ( 0 0 1 1 0 s BdW C ds t X t G C X t X t t ( 14
)
The solution is a random variable for each t. The second integral on the right-hand side of ( 14) is to be taken as the Ito integral. The Ito integral defines the stochastic integration operation. The stochastic integration can not be understood as a deterministic ordinary integral [START_REF] Higham | An Algorithmic Introduction to Numerical Simulation of Stochastic Differential Equations[END_REF] By analogy with the above two ways, the stochastic integral can be estimated as in Equation ( 15) or (16):

T t dW t h 0 ) ( ) ( )) ( ) ( )( ( 1 0 1 j N j j j t W t W t h )) ( ) ( )( 2 ( 1 0 1 1 j N j j j j t W t W t t h
Equation ( 15) and ( 16) give markedly different answers. Even with , the mismatch of the two equations does not go away. This emphasizes the significant difference between deterministic and stochastic integration: that is, we have to be precise about the way the sum is formed. Though the expected value of the results from Equation ( 15) and ( 16) are the same, for the purpose of transient performance prediction, each equation leads to different prediction mechanism [START_REF] Evans | An Introduction To Stochastic Differential Equations[END_REF]. In the current paper, we use Equation ( 15) for stochastic integration. Equation ( 15) is also referred as Ito integral.

t

Euler-Maruyama defines a numerical method for solving Equation ( 13) with Ito integral. The solution as the random variable arises when we take the zero stepsize limit in the numerical method. It is usual to rewrite [START_REF] Evans | An Introduction To Stochastic Differential Equations[END_REF] in differential equation form as

) (t X ) ( ) ( ) ( 1 1 t BdW C dt t G C t dX
with and . To apply a numerical method to (17) over [0, T], we first discretize the interval. Let t = T/L for some positive integer L, and j = j t. Our numerical approximation to X( j) will be denoted Xj . The Euler-Maruyama (EM) method takes the form 0

) 0 ( X X T t 0 )) ( ) ( ( ) ( 1 1 1 1 1 j j j j j t W t W B C t t G C X X
where . To understand where Equation (18) comes from, notice from the integral form Equation ( 15) that

L j , , 2 , 1 ) ( ) ( ) ( ) ( 1 1 1 1 1 s BdW C ds s G C t X t X tj tj tj tj j j
Each of the three terms on the right-hand side of Equation ( 18) approximates the corresponding term on the right-hand side of Equation (19). We also note that in the deterministic case ( and constant), Equation (19) reduces to Euler's method. Following the Black-Scholes approach [START_REF] Higham | An Algorithmic Introduction to Numerical Simulation of Stochastic Differential Equations[END_REF] [14], we can predict the peak performance within certain time window. A close analogy to this problem is the stock price prediction.

Transient Analysis:

We simulated an FET-RTD inverter circuit using the stepwise equivalent conductance technique. The input voltage switches between 0 and 5V. As can be seen from Figure 8(c), SPICE3 fails to converge to the correct solution [START_REF] Le | Circuit Simulation of Nanotechnology Devices with Non-monotonic I-V Characteristics[END_REF]. SWEC generates more accurate response without needing to solve set of non linear equations, thus yielding better results at less computational expense. Figure 9(a) shows the circuit of an RTD-D flip-flop. Refer [START_REF] Mazumder | Digital Circuit Applications of Resonant Tunneling Devices[END_REF] for details on the working of the circuit. The circuit was simulated with the clock waveform as shown in Figure 9(b). The data applied and the output obtained is as shown in Figure 9(c). The input waveform switches at t = 300ns and the output waveform switches at the rising edge of clock at t = 350ns. This shows that we could capture the right behavior of the circuit using our stepwise equivalent conductance technique.

Performance Prediction:

Figure 10 demonstrates the results from both true solution and EM integration method. The circuit is a time-variant nanoscale transistor with some parasitic RCs. From 0-1ns, we observe a possible performance peak about 0.6 V.

Conclusions

This paper proposes a new stepwise conductance based statistical simulator. It not only prevents the NDR problems, but also predicts the performance within certain time windows. The proposed simulator has over 20-30 times speedup over the SPICE-like simulator.

Figure 1 -

 1 Figure 1 -I-V curves for (a) RTT (b) CNT [9]

Figure 2 -

 2 Figure 2 -Dependence of NR method on initial guess [8]

  ) and (b) compare the equivalent conductance definition for piecewise linear (PWL) and stepwise approximations.

Figure 3 -

 3 Figure 3 -Equivalent conductance as per (a) piecewise linear model, and (b) step wise

Figure 4 -

 4 Figure 4 -RTD I-V Characteristics

Figure 5 -

 5 Figure 5 -RTD conductance as function of applied bias

Figure 7 (

 7 Figure7(a) shows the I-V characteristics of the RTD as captured by our approach. The circuit consisted of a series combination of a resistor and an RTD across a voltage source (a voltage divider circuit). The figure also shows the I-V characteristics as captured by our implementation of the Modified Limiting Algorithm (MLA) presented by Bhattacharya and Mazumder[START_REF] Bhattacharya | Augmentation of SPICE for Simulation of Circuits Containing Resonant Tunneling Diodes[END_REF]. As we can see, our approach is able to capture the negative resistance region of the I-V curve very closely and accurately. Similar curve for a nanowire is shown in Figure7(b). A range of voltages were applied to the series combination of a nanowire and a resistor and the nanowire current-voltage obtained using SWEC was plotted. This figure conforms well to the I-V characteristics of a carbon nanotube, indicating that SWEC is able to simulate the circuits involving nanowires.

Figure 7 -

 7 Figure 7 -I-V characteristics using SWEC (a) RTD (b) Nanowire

  Figure 8(a) shows the circuit and the output obtained at the junction of two RTDs is shown in Figure 8(b). The values of model parameters used for this simulation are as follows: A = 1e-4; B = 2; C = 1.5; D = 0.3; n1 = 0.35; n2 = 0.0172; H = 1.43e-8. Shown also are the responses obtained by other circuit simulators.

Figure 8 -

 8 Figure 8 -(a) FET-RTD Inverter, Output generated by (b) SWEC, (c) SPICE3, (d) ACESn [2]

Figure 9 -

 9 Figure 9 -(a) RTD-D Flip Flop, (b) Clock Signal, (c) Input and output waveforms

  is called Wiener process or Brownian motion.

	(11)
	W	(t	)
		A standard Wiener process over	, 0 [ T	]	is a random
	variable that depends continuously on	t	, 0 [ T	]	and satisfies
	three conditions: 1)	W	(	) 0	0	(with probability 1); 2) For
	0			s	t		T	, the random variable given by the increment
	W	(	t	)		W	(	s	)	is normally distributed with mean zero and
	variance	t		s	, i.e.		W	( t	)	W	(	s	)	t	s	N	(	) 1 , 0

  [START_REF] Evans | An Introduction To Stochastic Differential Equations[END_REF].

	T
		h	t (	)	dt	integration converge to the same solution in the
	0
	deterministic cases:
	N j	1 0	h	(	t	j	)(	t	j	1	t	j	)	j N	0 1	h	(	t	j	2 t	j	1	)(	t	j	1	t	j	)
																														X	(t	)
																														For	example,	the	following	two	ways	of

Table I -Comparison of DC simulations performance

 I

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)