Franco Fummi
email: franco.fummi@univr.it

Mirko Loghi
email: loghi@sci.univr.it

Stefano Martini
email: martini@sci.univr.it

Marco Monguzzi
email: monguzzi@sitek.it

Giovanni Perbellini
email: perbellini@sci.univr.it

Massimo Poncino
email: massimo.poncino@polito.it

Virtual Hardware Prototyping through Timed Hardware-Software Co-simulation

Designers of factory automation applications increasingly demand for tools for rapid prototyping of hardware extensions to existing systems and verification of resulting behaviors through hardware and software co-simulation. This work presents a framework for the timing-accurate cosimulation of HDL models and their verification against hardware and software running on an actual embedded device of which only a minimal knowledge of the current design is required. Experiments on real-life applications show that early architectural and design decisions can be taken by measuring the expected performance on the models realized using the proposed framework.

Introduction

Co-simulation allows functional and/or timed verification of mixed hardware-software systems. When a complete hardware (HDL) model of the system is available, a wide range of techniques and tools support designers in prototyping additional hardware and software to extend the system itself. In many situations, however, particularly whenever systems are already on the market, designers may face requests for extending systems that grew over time as merging of different parts, some written with different modeling languages and some others drawn as schematics; This complicates the process of correctly reverse-engineering the project, or requiring different tool versions setup (some of which not more supported anymore, in some cases). Furthermore, designers may not have access to some parts of the project because of intellectual property issues. In this work, we propose a methodology for (i) extending an hardware system that requires minimal knowledge of the current design and (ii) allows an effective timing-accurate simulation of the new project. Time-to-market may particularly benefit from this approach to rapid prototyping, by increasing the chance of success in a project where new hardware has to extend actual systems. Furthermore, by supporting timing-accurate co-simulation, the framework fulfills the severe timing requirements in verifying software and hardware mixes for industrial control applications.

The proposed methodology explicitly targets the interaction of a microprocessor-based board, which hosts an operating systems and executes the software portion of the design, and a hardware simulator, which models the device under design. In that respect, it sensibly differs from other previous approaches, since the co-simulation must deal with issues other than just the (timing-accurate) interaction between two applications (the SW and HW simulators), like the OS support for co-simulation, as well as the remote interface between the board and the HW simulator. The proposed co-simulation framework has been successfully applied to the Ultimodule SCM2x0 platform for factory automation [1], a RISC system based on an user configurable FPGA system on chip (SOC) and hosting a RTOS [START_REF]RedHat eCos[END_REF] to allow real time operations, that delivers optimized, industry-ready solutions. The framework provides designers with a low cost development tool to rapid prototyping model of new hardware, either to be driven from the SCM2x0 or extending the module itself, thus actively interacting with final customers during the requirements collection and shortening the process of new projects implementation. The paper is organized as follows. Section 2 review existing work on timed co-simulation; Section 3 describes the main features of the proposed co-simulation framework, whose technical issues are discussed in Sections 4 and 5. Finally, Section 6 reports some experimental results, and Section 7 is devoted to concluding remarks.

Previous Work

The literature on HW/SW co-simulation is quite vast, and covers many different involved aspects. Historically, HW/SW co-simulation has been mostly focused on functional simulation, in which timing information, when available, is obtained from a static timing analysis of the various components. Simulation performance was the strongest limitation to the development of effective timing accurate co-simulation strategies. This is particularly true for heterogeneous approaches, where a significant overhead is imposed by the effort of keeping the synchronization between the two (the software and the hardware one) simulation engines ( [START_REF] Ghosh | A Hardware-Software Co-Simulator for Embedded System Design and Debugging[END_REF][START_REF] Liem | System-on-Chip Co-Simulation and Compilation[END_REF][START_REF] Valderrama | Automatic VHDL-C Interface Generation for Distributed Co-Simulation: Application to Large Design Examples[END_REF][START_REF] Coste | Multilanguage Design of Heterogeneous Systems[END_REF]). Although homogeneous environments (in which a single simulation engine is used) may make this task more manageable, homogeneity is usually achieved by abstracting away the distinction between hardware and software, making the very notion of time quite imprecise ( [START_REF] Buck | Ptolemy: A Framework for Simulating and Prototyping Heterogeneous Systems[END_REF][START_REF] Balarin | Hardware-Software Co-Design of Embedded Systems: The Polis Approach[END_REF]). Only recently, some approaches have addressed this performance bottleneck by explicitly targeting the timing accuracy of co-simulation. One class of approaches borrows ideas from the theory of distributed synchronization, using the similarity between timed co-simulation and distributed event-driven simulation algorithms. [START_REF] Yoo | Optimistic Timed HW-SW Cosimulation[END_REF][START_REF] Sung | Optimized Timed Hardware Software Cosimulation Without Roll-Back[END_REF][START_REF] Kim | Virtual Synchronization for Fast Distributed Cosimulation of Dataflow Task Graphs[END_REF][START_REF] Yi | Virtual Synchronization Technique with OS Modeling for Fast and Time-Accurate Cosimulation[END_REF]. All these approaches follow an asynchronous paradigm, in which each simulator manages its local time, and the local times evolve at different speeds. They differ, however, in how the overhead required by synchronization is managed; the solutions consider either the use of rollback of the simulation (when one simulator receives a past event from the other simulator - [START_REF] Yoo | Optimistic Timed HW-SW Cosimulation[END_REF]), or a proper alignment between the local clocks and global clock, when rollback is not possible, allowing synchronization to occur only when events are exchanged ( [START_REF] Sung | Optimized Timed Hardware Software Cosimulation Without Roll-Back[END_REF][START_REF] Kim | Virtual Synchronization for Fast Distributed Cosimulation of Dataflow Task Graphs[END_REF][START_REF] Yi | Virtual Synchronization Technique with OS Modeling for Fast and Time-Accurate Cosimulation[END_REF]). Another class of solutions is based on the construction of a timing model for software, obtained by attaching timing annotations to the ISS (for instance, an execution time in cycles for each executed instruction). Timing synchronization between software and hardware is then achieved using the accumulated delays for the software, and the cycle information provided by a HDL simulator for the hardware [START_REF] Yoo | Fast Timed Cosimulation of HW/SW Implementation of Embedded Multiprocessor SoC Communication[END_REF][START_REF] Bacivarov | Timed HW-SW Cosimulation Using Native Execution of OS and Applications SW[END_REF]. All the above approaches provide a reasonably effective solution to the timed co-simulation problem. However, they are explicitly targeted for the interaction of two (or more) co-simulation engines, and are not thus suitable for our virtual prototyping context, which requires the timing-accurate interfacing of a simulator for hardware and a software program running on an actual board, possibly hosting a RTOS. In other terms, we need synchronization between actual (i.e., not simulated) time (on the board side where SW is executed) and simulated time (on the host computer side where an HW model is simulated). This requirement rules out many of the possibilities previously reviewed; options such as simulation rollback or the use of instruction-based timing models, for instance, are either infeasible or inadequate. In fact, the real-time execution of the software on the board is based on the synchronization given by the hardware timer which monotonically increases its value. Moreover, the board may include some hardware devices which synchronizes their work by exploiting the timer value, thus rollback cannot be implemented, since it would require the rollback of the behavior of such real hardware components. The proposed co-simulation methodology solves this problem by defining the concept of virtual tick.

Co-Simulation Methodology

The objective of this work is the timed HW/SW cosimulation of a system in which a portion of the hardware is described in some HDL and the software is running on a microprocessor-based board. Figure 1 shows the specific instance of the system considered in this work. The board includes a CPU, memory, and various hardware devices; some devices are conventionally implemented in hardware (ASICs), while some others by means of reconfigurable hardware (a FPGA hosted on the board). The CPU runs application software that accesses hardware functionalities by using device drivers provided by a RTOS. A hardware timer produces the signal that increments the clock counter used by SW and HW functions to synchronize their execution, thus allowing real-time behavior. Virtual HW prototyping is implemented by executing the hardware model on a host computer by means of simulation of a given HDL model. We selected SystemC as HDL, since it allows to model a hardware behavior at different abstraction levels. Moreover, a synthesis flow easily transforms HW models into HW devices. Two are distinguishing features of the proposed cosimulation methodology:

1. Communication between HW (the SystemC simulator) and the SW (the board) is realized by means of a driverbased scheme. More specifically, the SW accesses to the HW device under design trough a device driver used to send and receive data to/from the SystemC model, viewed as any other device. Such scheme implies that communication between HW and SW occurs through the interrupt mechanism. However, due to the "remote" nature of the virtual HW device, the interaction between the board and the hardware simulator on the host PC is implemented by means of the network communication APIs of the OS. Similarly to previous schemes ( [START_REF] Benini | SystemC Co-simulation and Emulation of Multi-Processor SoC Designs[END_REF][START_REF] Fummi | Native ISS-SystemC Integration for the Co-Simulation of Multi-Processor SoC[END_REF]) the proposed methodology uses the remote IPC to implement the interaction between SW and HW models; however, the use of a real board and the requirement of timed HW-SW co-simulation completely differentiates the methodology proposed in this work. In particular, our scheme can be viewed as a variant of the solution originally proposed in [START_REF] Fummi | Native ISS-SystemC Integration for the Co-Simulation of Multi-Processor SoC[END_REF]; the details will be described in Section 5. Moreover, with respect to the paper [START_REF] Formaggio | A Timing-Accurate HW/SW Co-Simulation of an ISS with SystemC[END_REF] the proposed framework estabilishes a complete timed co-simulation between the HW model and all the SW running on the board, while [START_REF] Formaggio | A Timing-Accurate HW/SW Co-Simulation of an ISS with SystemC[END_REF] allows to synchronize the HW model with the application SW thread only. Performance estimation of the proposed methodology are thus more accurate.

Timing synchronization is realized using the notion of

virtual tick. The latter term identifies the fact that the co-simulation is driven by the SystemC simulated time (a virtual time), rather than the real time of the timer on the board. This implies thus that (i) SystemC becomes the master of the co-simulation, and (ii) the real-time behavior of the HW/SW components of the board will actually depend on the SystemC virtual clock rather than the actual clock counter that is updated by the RTOS timer interrupt routine. In other terms, in hardware terms, it is the (SystemC) device that determines the advance of time.

Given the different natures of the two times, the continuous-time evolution of the timer (on the board) becomes a discrete-time evolution based on the simulated time.

Timing Synchronization Protocol

The previous section has described the main features of the proposed timed co-simulation methodology. In this section, we concentrate on the timing issues of the co-simulation, and in particular on how to synchronize the hardware timer with the simulated time of the SystemC kernel.

Enforcing Timing Synchronization

The hardware timer hosted on the board generates periodic pulses (HW ticks); software operations on the board are synchronized with respect to a SW tick, which is derived by interrupting the system after a specified amount of HW ticks. When the interrupt occurs, a timer interrupt service routine is invoked, which increments the SW tick counter and takes care of the alarms, and eventually calls the scheduler to provide it with the time-slice use for scheduling decisions.

The key point of our approach is that timing-accurate cosimulation is realized by altering the way the SW tick is updated; rather than modifying it any time the HW timer generates an interrupt, the changes are driven by the Sys-temC clock. The idea, summarized in Figure 2, is that the SystemC simulator sends, in correspondence of each SystemC clock cycle, a "message" to the board to force the update of the SW tick. The message actually appears to the board as a regular device-driven interrupt request. When the message has been sent, the SystemC simulator must wait for a response message before starting the next simulation cycle. In order to implement this idea, however, it is essential to observe that the interval between two HW ticks (1 ms in the Figure 2) can be shorter than the time required to send a message (via socket) from the host running the SystemC simulator to the board. Therefore, after one SW tick, the board must spend some time (denoted with idle time in the following) for waiting the arrival of the message from the SystemC simulator. During this idle time, the board must put all system and user threads into a sleep step, but those that are necessary to keep the socket connection between the Board and SystemC active.

Reducing IPC Overhead

In the previous description, the SW tick is incremented for each increment of the SystemC clock. This scheme is clearly highly inefficient, because it requires an excessive amount of synchronization. To reduce the communication overhead, we limit the number of required synchronization points. This can be achieved by having SystemC to send the synchronization message only after n clock cycles. This implies that the board (actually, the OS), upon arrival of this "multiple-tick" message, must run for n SW ticks. We call synchronization time (T sync ), the interval (measured in SystemC clock cycles) between two synchronization events which are sent from SystemC to the board. This is obviously possible only if there no exchange of data between the board and the SystemC simulator occurs during normal execution.

Implementation Details

The implementation of the proposed methodology requires three main tasks. First, the definition of the communication interface; second, the modification of the OS running on the board, in order to support the board, and, third, the modification of SystemC simulation kernel, in order to setup the proper synchronization commands. In such a way the synchronization (but also the exchange of data) between the two components is properly managed. This section details the three above issues.

Implementing the Communication

The generic architecture of the proposed methodology shown in Figure 1 shows a generic socket-based connection between the two actors involved in the communication. The latter is specifically implemented through three TCP/IP ports: A (DATA PORT), used to exchange data, An interrupt port (INT PORT), which carries the signal interrupt, and a clock port (CLOCK PORT), which takes care of the exchange of the timing information that keep the two systems synchronized. Whenever a synchronization event goes from the SystemC kernel to the board, the OS running on the board advances the application for T sync cycles. At the same time the Sys-temC kernel advances its simulation for T sync cycles and then it waits an answer from the board. Therefore, when a time packet is exchanged between the two actors, they are fully synchronized and they can further proceed. Also, whenever an interrupt is sent from the SystemC environment, the OS reads and writes on the DATA PORT to exchange data with the simulated hardware.

SystemC Kernel Modifications

The synchronization between the board and SystemC is realized by modifying the SystemC kernel in such a way that it can establish and control the communication. The required modifications to the SystemC kernel essentially consist of:

• The addition of two new types of ports (driver in and driver out), that are devoted exclusively to the communication between a SystemC module and the OS running on the board. These classes are derived from the sc in and sc out SystemC classes, respectively. • The addition of the special process driver process. Similarly to a sc method, a driver process will be triggered when a new data is present on a driver in port to which the process is sensitive.

• The modification of the event scheduling algorithm, in order to handle the presence of special ports and processes. • The adding of an additional module to the design, triggered by the positive edge of the clock, which sends and receives the synchronization packets from the board. The core of a standard SystemC simulation engine is enclosed in a function called simulate. Such a function is invoked when the simulation starts, and it runs the simulation loop, calling the proper routines to collect, handle and dispatch events. In the modified version of the SystemC kernel, we replaced that function with another one, called driver simulate. This new function opens the communication channels, opening the TCP/IP DATA PORT and INT PORT ports. Then it iterates on a modified simulation loop, which performs the following actions:

• Check for the presence of data on DATA PORT. If there is one, the datum is read and the required actions are performed. These actions are:

-Reading from the SystemC port; -Sending data to the board; in case of a read, and:

-Reading further data from the channel.

-Writing the SystemC ports.

-Advancing the driver process; in case of a write.

• A standard simulation cycle is accomplished. As in the conventional SystemC simulation step, events are handled and generated. New events are scheduled and dispatched. • The interrupt signal is checked. If it is active, a packet is sent to the board via the INT PORT, so the board will react by sending a request packet on the data channel.

OS Modifications

There are two main modifications required by the OS. The first one is concerned with the communication between the board and the hardware. Since the simulated hardware is modeled as an external device, this amounts to write a new device driver to the OS. The driver is initialized at system boot, and it passively listens to the interrupt signal. As for any other physical device, activation of the interrupt signal notifies that the simulated device has some data to exchange, so the driver routines are in charge to read data from the DATA PORT. Whenever data are read, they are transferred and elaborated by the proper function. Then, if needed, the results are sent back to the device, writing on the DATA PORT.

The second main modification is concerned with the enforcement of the timing synchronization. To keep the software running on the board temporally aligned with the hardware simulated in the SystemC framework, the execution of the application must be driven by the same clock of the Sys-temC simulation.

The idea is to freeze the board until a SystemC clock pulse is received, then allow the execution for T sync cycles and then block the board again. Since a timing packet from the SystemC side has to be received on a TCP/IP port, however, such approach is not viable. In order to receive and manage the clock pulse, in fact, the board cannot be completely idle, and some tasks on the board must be kept running.

Rather than completely stopping the entire board, however, we can identify what are the set of OS threads that are in charge to control the communication and that must thus keep always active. We called such threads communication threads. Once the latter have been identified, we split the behavior of the OS in two major states: normal and idle. In the normal state the OS acts in a conventional way, scheduling user and system threads according to their priorities. In the idle state, conversely, only a limited number of tasks are allowed to run: the communication threads, the idle thread, the channel thread and the systemc thread (Figure 3). The idle thread is a thread provided by almost all OSs, whose only purpose is to waste CPU cycles when no elaboration has to be performed. The channel thread is a thread that is spawned when the device driver is initialized, and listens on the INT PORT, through which it performs the communication.

¡ £ ¤ ¦ ¦ © ¤ ! " # $ & ' ¡ " $ # ! " # $ & ' ¡ ) & 1 $ ! " # $ & £ " $ 1 ! " # $ & 5 ' $ # ! " # $ & ' 6 7 9 A B C E G H P 7 Q H Q R S ¡ £ ¤ ¦ ¦ © ¤ ! " # $ & ' ¡ " $ # ! " # $ & ' ¡ ) & 1 $ ! " # $ & £ " $ 1 ! " # $ & 5 ' $ # ! " # $ & ' 6 7 9 A V W P R 7 Q H Q R S Y `a b c d `e d d f d g `e d d f d g ¡ h ' $ ¦ £ ! " # $ & ¡ h ' $ ¦ £ ! " # $ &
The channel thread cannot be halted when the OS is in the idle state, otherwise some events can be lost. Clearly, only the data exchange is performed by this thread, while the data management is left to other threads that run only when the OS is in the running state. Last, the systemc thread is the special thread that we add to the OS for synchronization purposes. It is in charge of listening to the CLOCK PORT for an incoming clock pulse from the SystemC side; when such an event occurs, it reacts accordingly.

The typical sequence of operations of the OS works as follows. The normal state should last for a time at least equal to T synch cycles. The timer interrupt, which is invoked on regular intervals, is used to handle the switch from the normal to the idle state. When it is time for such a state switch, the following steps are performed:

• A flag is set.
• The need for a re-scheduling of the tasks is signaled to the scheduler; • The scheduler saves the context (in particular, the value of the timeslice) of the thread currently in execution; • The scheduler activates one of the threads allowed in idle state. • The current time of the board is sent back to SystemC, to signal that the OS is frozen. The idle state continues until a packet is received on the CLOCK PORT from the SystemC side. Upon occurrence of this event:

• The above mentioned flag is cleared; • The scheduler is invoked;

• The scheduler resumes the thread that was suspended and restores its context (in particular, the value of its timeslice). Figure 4 summarizes the events that cause the OS to switch between the two states.

Experimental Analysis

The co-simulation methodology presented in this paper has been used to verify the design of a small 4-port router described in SystemC, an extension of the Multicast Helix Packet Switch example distributed with SystemC 2.0.1. This router receives data packets on its input ports and forwards them to the proper output port according to a routing table embedded into the router. Whenever a new packet arrives on one of the input ports, it is stored into an internal buffer. If the buffer is full, the packet is dropped. Each packet is then read from the buffer by the main process of the router, and checked for errors by a checksum algorithm. If the checksum is correct the destination address stored in the packet is used to find the right output port using the routing table; otherwise the packet is dropped. The packets consist of the following fields:

• Source address: the address of the producer.

• Destination address: the address of the consumer to which the packet must be sent; • Packet identifier: an integer value used for debugging purposes only; • Data field.

• Checksum: a 16 bit field used for error detection. The overall HW/SW configuration of the following entities:

• SystemC model of the router;

• SystemC model of the packet generator (producer), which is attached to an input port of the router, and generates packets with a random destination address.

• SystemC model of the packet destination (consumer),

which is attached to an output port of the router, and analyzes the integrity of the received packet. • C application computing the checksum, executing on a SCM220 Ultimodule TM board running the eCos operating system. In order to enable the proposed methodology, we have created a special device driver for the router and embedded it into eCos; the C source code calls the appropriate driver interface functions to communicate with the SystemC module. In addition, the modifications described in Section 5 have been added to eCos.

Co-Simulation Overhead

The first experiment is concerned with the evaluation of the overhead of synchronization. Figure 5 reports the overall time (in seconds) as a function of the number of exchanged packets N , for different values of T synch .

¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ £ £ £ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ § ¨ § © § § ¨ § § § § ¨ § © § § ¨ § § § § ¨ § © § § ¨ § ! " # # # $ # # # & # # # " # # # # ' ( 0 1 2 3 5
.

Figure 5. Co-Simulation Overhead.

The increase in the slope of the curves for decreasing values of T synch in the plot shows that the overhead increases as the synchronization become tighter. The increase is due to (i) the increased cost of communication, and (ii) the overhead in the OS, which spends more time in switching between the running and the idle state.

The plot also shows an interesting feature of the proposed co-simulation scheme, namely, the fact that simulation time increases linearly with N , whatever the value of T sync . This implies that the overhead is approximately constant, and does not depend on the number of exchanged packets. For instance, simulating the transmission of N = 100 packet takes 241 seconds for T sync = 1000 and 32 seconds for T sync = 10000, corresponding to a ratio of 241/32 ≈ 8, which also for any other value of N . Figure 6 quantifies the overhead more precisely, by showing its direct dependency on T synch ; values are now expressed as the ratio between the actual simulation time (for a given T synch ) and the time spent by a simulation without synchronization (corresponding to T synch → ∞), assumed to be equal to 1.

The plots confirms the results of Figure 6, but emphasizes the fact that overhead decreases quite rapidly for larger values of T synch (notice the log-scale on the Y-axis). For instance, imposing synchronization at each simulation cycle yields a simulation time which 1000x the time required for an untimed simulation; this overhead decreases to 100x if we synchronize once every 360 cycles.

The plot also shows that changing the amount of work done (N = 100 and N = 1000 exchanged packets) does not significantly change the rate at which the overhead decreases.

Co-Simulation Accuracy

The seconds experiment aims at assessing the simulation accuracy as a function of T sync . The accuracy is expressed in terms of the percentage of packets that can be handled by the system. This number is 100% when the systems are very tightly coupled (a synchronization event for each simulated cycle), and it expected to progressively decrease as the synchronization becomes more loosely coupled. The plots of Figure 7 confirm this expected behavior. Notice however . Figure 6. Co-Simulation Overhead vs. Tsync that the 100% percentage of forwarded packets is maintained up to a value of T sync around 5000, allowing thus a significant reduction of the simulation overhead. The similarity of the two curves for N = 100 and N = 1000 shows that there is only a marginal degradation of the accuracy when increasing the number of packets sent. The small difference is due to the fact that dropped packets tend to increase when there is more work to be done. One final remarks is related to the choice of T synch . In many cases, the value of T synch is precisely defined by the timing constraints imposed by the device to be designed, and there is thus little margin to change it. There may be however situations in which T synch is allowed to vary over a given range of values. In these cases, the plots of Figure 6 and Figure 7 can be used together to define with an optimal value of T synch . In fact, because of the opposite dependencies of the overhead and of the accuracy on T synch , there is a value of T synch which maximizes the product (accuracy x overhead). If the optimal value falls in the allowed range, the designer may then use it as the synchronization interval for the co-simulation.

¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ £ £ £ £ £ £ £ £ £ £ £ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¦ ¦ § ¦ § § ¦ § § § ¦ § § § § ¦ § § ¦ § ¦ ¦ § ¦ § " ¦ § # ¦ § & ¦ § ' ¦ § ( ) 0 1 2 3
A A A A A A A A A A A A A B B B B B B B B B B B B B C C C C C C C C C C C C C D D D D D D D D D D D D D E E E E E E E E E E F F G G G G G G G G G G G G G H I H Q S H I H Q T H I H Q V H I H Q W H I H Q X H H I H Q X S H I H Q X I Y

Conclusions

We have proposed a new HW/SW co-simulation methodology which is suitable for virtual prototyping of new hardware devices to be added to an existing processor-based system. Two are the main features of the proposed scheme. First, the time-accurate nature of the co-simulation, which allows to debug the device under design with the precision of the target hardware simulator. Second, thanks to the features of OS running on the board, the co-simulation even allows to meet real-time constraints, provided that these are relative to the same timing reference used by the board. The proposed framework has been successfully applied to a Ultimodule SCM2x0 board to design a device implementing the function of a packet router, and to carry out a design exploration before implementing the device onto the board.

Figure 1 .

 1 Figure 1. Co-Simulation Methodology.

Figure 2 .

 2 Figure 2. Co-Simulation timing view.

Figure 3 .

 3 Figure 3. OS Normal and Idle States.

Figure 4 .

 4 Figure 4. Switching from Normal to Idle and Viceversa.

Figure 7 .

 7 Figure 7. Simulation Accuracy vs. Tsync.

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)


Ozcan Ozturk
email: ozturk@cse.psu.edu

Mahmut Kandemir
email: kandemir@cse.psu.edu

Nonuniform Banking for Reducing Memory Energy Consumption *

Main memories can consume a large percentage of overall energy in many data-intensive embedded applications. The past research proposed and evaluated memory banking as a possible approach for reducing memory energy consumption. One of the common characteristics/assumptions made by most of the past work on banking is that all the banks are of the same size. While this makes the formulation of the problem easy, it also restricts the potential solution space. Motivated by this observation, this paper investigates the possibility of employing nonuniform bank sizes for reducing memory energy consumption. Specifically, it proposes an integer linear programming (ILP) based approach that returns the optimal nonuniform bank sizes and accompanying data-to-bank mapping. It also studies how data migration can further improve over nonuniform banking. We implemented our approach using an ILP tool and made extensive experiments. The results show that the proposed strategy brings important energy benefits over the uniform banking scheme, and data migration across banks tends to increase these savings.

Introduction

Behavior of many data intensive embedded systems is dictated by their data access pattern, making memory system performance critical. In fact, the past research [START_REF] Catthoor | Custom Memory Management Methodology[END_REF][START_REF] Farkas | Quantifying the energy consumption of a pocket computer and a Java virtual machine[END_REF] showed that a significant portion of overall execution energy (excluding input/output units) is spent in memory system. While circuit level techniques targeting energy efficiency are extremely important, high level approaches [START_REF] Cao | Data memory design considering effective bitwidth for low-energy embedded systems[END_REF][START_REF] Sudarsanam | Simultaneous Reference Allocation in Code Generation for Dual Data Memory Bank ASIPs[END_REF][START_REF] Saghir | Exploiting dual data-memory banks in digital signal processors[END_REF][START_REF] Panda | Memory Bank Customization and Assignment in Behavioral Synthesis[END_REF] at the architectural and software levels can also play a major role in shaping the overall memory energy behavior and optimizing it.

Recently, banking has been used as a popular method for reducing memory energy consumption. In banking, memory space is divided into multiple banks, each of which can be controlled independently of the others. Experiments per-formed by several research groups [START_REF] Delaluz | DRAM energy management using software and hardware directed power mode control[END_REF][START_REF] Lebeck | Power aware page allocation[END_REF][START_REF] Delaluz | Improving Off-Chip Memory Energy Behavior in a Multi-processor, Multi-bank Environment[END_REF][START_REF] Farrahi | Memory Segmentation to Exploit Sleep Mode Operation[END_REF] reported significant reductions in memory energy due to banking. This is mainly because each read/write access in a banked memory architecture experiences a smaller capacitance, as compared to a monolithic unbanked memory system. Another advantage of the banked architecture (especially in the context of DRAMs) is low-power operating modes that can be used to place a bank into the low-power mode if it is not being actively used. Several efforts were already made to determine when and how the banks should be powered down, and also which low-power mode to employ when more than one mode are available. Broadly speaking, these methods are either hardware [START_REF] Delaluz | DRAM energy management using software and hardware directed power mode control[END_REF] or software [START_REF] Lebeck | Power aware page allocation[END_REF][START_REF] Delaluz | Improving Off-Chip Memory Energy Behavior in a Multi-processor, Multi-bank Environment[END_REF] oriented.

One of the common characteristics/assumptions of these prior banking related studies is that most of them assume all the banks are of the same size, i.e., they are uniform. While this makes the formulation of the problem easy, it also prevents some further opportunities by restricting the data mapping unnecessarily. In particular, in embedded systems that execute a single application, one can come up with a customized banking strategy where the banks can be of different sizes. Such a banking is referred to as nonuniform banking in this paper. The first contribution of this paper is to present an ILP (integer linear programming) based approach that decides the best (nonuniform) bank architecture and accompanying data mapping for a given array based embedded application. We show through experiments that working with customized nonuniform memory banks brings significant energy savings over an alternate strategy that works with uniform bank sizes (which is also formulated using ILP).

While our empirical evaluation of the nonuniform banking shows promising results, one can achieve further energy savings by not fixing the location of each data (i.e., its bank) for the entire execution, that is, by migrating data across the banks during the course of program execution. The second contribution of this paper is an ILP formulation of the data migration problem in the nonuniform bank architecture. Our experimental results with data migration show that it brings additional energy savings over nonuniform banking.

This paper is organized as follows. Section 2 gives a brief overview of banked memory architecture and explains our

Architecture and Access Pattern Extraction

Our architectural model is based on a multi-bank memory system, which is similar to RDRAM [11]. In this model, each memory bank can be in one of four operating modes: active, standby, nap or power-down. These memory banks can be placed into low-power modes independently. Memory access requests (read/write) are serviced only if the corresponding bank is active, that is, the bank is not in one of the low-power operating modes (standby, nap, powerdown).

Each low-power mode has different energy consumption (per cycle) and resynchronization cost, since low-power operating modes are typically implemented by disabling certain parts of the DRAM chip. Bringing a low-powered memory bank back to the active mode causes a resynchronization cost (wake-up penalty), which makes a tradeoff analysis between performance and energy inevitable. Energy consumption (per cycle) and resynchronization costs for typical, RDRAM-like low-power operating modes are given in Table 1. As can be seen from this table, when choosing a low-power mode for an idle bank, a tradeoff analysis between energy savings (by using a more aggressive mode) and performance penalty (caused by this aggressive mode due to increase in cycles) has to be performed. If the bank in question is predicted to be idle for sufficiently long time, a more power saving operating mode should be selected. This follows from the fact that frequent transitions between low-power and active modes may result in non-tolerable performance penalties. Hence, a suitable lowpower operating mode should be selected based on bank inter-access time (the time between successive accesses to the same memory bank).

Embedded programs constructed using loop nests (with compile time known bounds) and array accesses (with affine subscript expressions) are the main focus in this paper. Such codes frequently occur in embedded image/video processing domain [START_REF] Catthoor | Custom Memory Management Methodology[END_REF]. An optimizing compiler can analyze these loop-intensive applications with regular data access patterns. Since frequent transitions between low-power modes and active mode can be very costly, one early design decision that we made is to perform these mode transitions at well-defined program points. In our implementation, these transition points, which delimit the boundaries of execution phases, are expressed in terms of loop iterations. In this paper, we adopted the concept of a step to define these transition points. Although, in theory, we have the flexibility to assign any number of iterations between two transition points, these points should be selected carefully. That is, in moving from one point to another during execution, the data access pattern should exhibit a significant change. To make these steps explicit we need to modify the input code as explained below.

An example loop nest that accesses an array X through two references with affine subscript expressions X[i+2,j-1] and X[i,j] is shown in Figure 1. The unit of data that is being stored in banks (and also the unit of data migration across banks when migration is used) is a data block (data tile). Figure 2 shows a two-dimensional array that is logically divided into data blocks. All the data blocks have the same size except possibly at the boundaries of the array. The blocked (tiled) version of the original loop nest is given on the right hand side of the Figure 1. In this code, loops i and j iterate over the data blocks, and are referred to as the block (inter-tile) iterators. Also, ii and jj are called intra-tile iterators, and iterate over the elements of a given data block. A main factor which effects the data access pattern is the data block size. In our experiments, we manually selected the suitable data blocks and their sizes. An optimizing compiler can be used in the future to automate the data access pattern extraction.

ILP Formulation

ILP provides a set of techniques that solve those optimization problems in which both the objective function and constraints are linear functions and the solution variables are restricted to be integers. The 0-1 ILP (also known as ZILP) is an ILP problem in which each (solution) variable is restricted to be either 0 or 1 [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF]. It is used in this paper for determining the optimal bank sizes, data to bank mapping, and data migration pattern. Table 2 gives the constant terms used in our ILP formulation. Bank energies given in this table (i.e., AE, IE, IE S , IE N and IE P ) are shown as energy consumption per step.

for i=1, N1, 1 for j=1, N2, 1 ...X[i+2,j-1]... ...X[i,j]... =⇒ for i =1, N1, T1 for j =1, N2, T2 for ii=i , min(N1,i +T1-1), 1 for jj=j , min(N2,j +T2-1), 1 ...X[ii+2,jj-1]... ...X[ii,jj]...
Our presentation is in two parts. In the first part, we are partitioning the given memory space into nonuniform banks in the most energy efficient way, and determine optimal location (banks) for each data block. The second part incorporates data migration into the nonuniform bank strategy. In both cases, data-to-bank mapping is optimized.

Memory Partitioning and Data Assignment

Our objective is to partition the available memory into nonuniform (sized) banks to minimize the overall energy consumption. We determine the number of banks and their sizes based on the data access pattern and the total memory size (to be partitioned) using 0-1 variables. For each possible bank size, we define 0-1 variables. By using these 0-1 variables, we determine the partitions (banks) and their contents. Although, we restrict the possible sizes to be powers of two to simplify the problem, it can be extended to cover all possible sizes. This way we keep the problem size smaller (less variables and constraints) and by doing so, we reduce the ILP solution time. If, for example, the memory size in question is 4k (assuming that k is a power of two) and the minimum bank size possible is k, then we will have 0-1 variables for one 4k-bank, two 2k-bank and 4 1k-bank. If two of the four 1k-bank variables and one 2k-bank variable are returned as 1 from the ILP solver, then we conclude that the application in question will spend the minimum energy when the memory space is partitioned into three banks of sizes k, k and 2k. Our formulation also gives the optimum mapping of the data blocks to these banks.

In our implementation, we identify memory banks with a pair of attributes (l, n): l is used for its size (in terms of data blocks it can hold), and n is used for distinguishing a bank from the other banks that have the same size. For example, with a memory of size 8k, there can be two banks with a size of 4k, where k is the minimum bank size possible. These two banks can be expressed using the pairs (4k, 1) and (4k, 2).

Assuming that N denotes the maximum number of banks possible if each bank holds only one data block (which occurs when the minimum possible bank size is used), S the number of steps, M the number of data blocks, we can use 0-1 variables to specify potential location (L) of each data block. Specifically,

• L m,l,n : indicates whether data block m is residing in bank (l, n).

There are possibly N l banks of size l ( N l at most if all of the banks are of size l). We use a variable for each one of these bank candidates. If this 0-1 variable is 1 then we conclude that the corresponding bank actually exists. We specify whether bank (l, n) actually exists (returned by our ILP formulation) by using E l,n .

• E l,n : indicates whether data bank (l, n) exists.

In our ILP formulation, we use variable A to identify if the bank is currently active.

• A l,n,s : indicates whether bank (l, n) is active at step s due to a read/write operation on it.

Although it is better to have a bank in low-power operating mode from the energy perspective, depending on the data access pattern, it might be better not to go to a lowpower operating mode for performance reasons. As a result, frequent switchings between low-power modes and active mode in short intervals should be avoided. Our next set of 0-1 variables are used to capture the switchings between the active and low-power modes for a given bank. If a bank is activated from a low-power mode, the following variable is set to 1:

• X l,n,s : indicates whether bank (l, n) is activated at step s.

On the other hand, if a bank is switched to a low-power mode, Y l,n,s will be set to 1. In other words,

• Y l,n,s : indicates whether bank (l, n) goes to the lowpower mode at step s.

After having defined our 0-1 integer variables, we can now discuss our ILP formulations. The following constraints are needed to capture the values of X l,n,s and Y l,n,s . A bank (l, n) is activated at step s, if it is not active at step (s -1) and is active at step s:

X l,n,s ≥ A l,n,s -A l,n,s-1 , ∀l, n, s. (1)
A bank (l, n) goes to a low-power mode at step s if it is active at step (s -1) but it is not active at step s:

Y l,n,s ≥ A l,n,s-1 -A l,n,s , ∀l, n, s. (2)
In our experiments, we assume that bank sizes are restricted to be powers of two. For example, if the memory in question can hold at most 8 data blocks then this memory can be partitioned into memory banks such that each bank can hold 1,2,4 or 8 data blocks. Since available memory space is partitioned among banks, the total size of the banks (determined by the ILP solver) should be equal to the available memory space:

log 2 N i=0 N 2 i j=1 E 2 i ,j × 2 i = N. (3)
A data block can be residing in a bank only if the bank in question exists:

E l,n ≥ L m,l,n , ∀m, l, n. (4)
Since a data block can be residing only in a single bank at any given time, it must satisfy the following constraint:

log 2 N i=0 N 2 i j=1 L m,2 i ,j = 1, ∀m. (5)
The limited bank capacity forms the basis for the next constraint that needs to be satisfied. Assuming that the size of a block is size block , the following expression can be written for each possible bank size l:

size block × M i=1 L i,l,n ≤ l, ∀l, n. (6)
A bank is currently active (at step s) if one of its data blocks is accessed:

A l,n,s ≥ R m,s × L m,l,n , ∀m, l, n, s. (7)
R m,s indicates whether block m is accessed at step s. Its value is extracted from the data access pattern.

Having specified the necessary constraints in our ILP formulation, we next give our objective function. In our execution model, there are four components of the total memory energy consumption:

• active: the energy consumed when a bank is read/written.

• low-power: the energy consumed when a bank is in the low-power mode.

• activation: the energy consumed to activate a bank from the low-power mode.

• deactivation: the energy consumed to switch a bank to the low-power mode.

Based on these, we can express memory energy consumption (B) as follows:

B = log 2 N i=0 N 2 i j=1 S k=1 (A i,j,k × AE + (1 -A i,j,k ) × IE +X i,j,k × RE + Y i,j,k × DE) × σ i . ( 8
)
In this formulation, AE, IE, RE and DE correspond to active energy, low-power energy, activation energy, and deactivation energy, respectively. Note that, σ is used to capture the energy consumption behavior of the banks with different sizes. For example, if the size of the bank is doubled the energy spent would be σ times of the original energy consumption. Based on this formulation, our 0-1 ILP problem can be defined as one of "minimizing B under constraints (1) through [START_REF] Delaluz | DRAM energy management using software and hardware directed power mode control[END_REF]."

Data Migration

Further energy improvements can be achieved by migrating data blocks among banks during the course of execution. In particular, in some cases, instead of activating/deactivating a bank, it might be more beneficial to transfer the data block to an already active bank. To incorporate data migration into our ILP formulation, several modifications to the original problem have to be made.

Since the location of a data block is no longer restricted to be the same throughout the execution of the program (due to migration), we have to include the step parameter, s, in the location variable, L. For this purpose, L m,l,n is replaced with L m,l,n,s to indicate whether block m is residing in bank (l, n) at step s.

Equations ( 4),( 5) and ( 6) should also be written for every step to capture bank existence constraint, data block location constraint (a data block can be in a single bank at any time) and bank size constraint. Equation [START_REF] Delaluz | DRAM energy management using software and hardware directed power mode control[END_REF], on the other hand, does not require any change except for the variable renaming, since it is already expressed for every step s.

Migration behavior of data blocks needs to be captured as well. We use Z m,s to serve for this purpose. A data block m migrates (at step s) if its current location (bank) is different from its previous location (i.e., the one in the previous step):

Z m,s ≥ L m,l,n,s -L m,l,n,s-1 , ∀m, l, n, s. (9)
Although data migration can reduce the energy consumption (as it can empty banks which can be placed into the low-power mode), it also brings additional energy consumption due to migrating data blocks. This overhead has to be included in the ILP formulation:

T = M i=1 S j=1 (Z i,j × M E). (10)
Then, our new 0-1 ILP problem can be defined as "minimizing B+T under constraints (1) through ( 7) and ( 9)."

Experimental Evaluation

Setup

We performed several experiments with five arrayintensive benchmarks to test the effectiveness of our ILP-based approach. Table 3 lists the benchmark codes used in this study and their important characteristics (taken from the Spec and Perfect Club benchmark suites). The second column gives the total size of the data processed by each benchmark, and the third column shows the data block size used. The last column gives the number of arrays for each benchmark. The default simulation parameters used in our experiments are given in Table 4. Note that, the energy values given in Table 4 are normalized to power-down energy. The low-power energy values given in this table reflect the actual energy consumption values from Table 1. For example, the ratio between the power-down bank energy and the active bank energy is 1:714, which corresponds to 0.005 nJ / 3.570 nJ. During activation (from a low-power mode to the active mode) and deactivation (from the active mode to a low-power mode), 3 4 of the active mode energy is assumed to be spent.

We performed experiments with three different execution models for each benchmark code in our experimental suite:

• Uniform Banking: This in a sense is the conventional memory space management strategy which has a fixed bank size and that does not use any data migration. Data blocks are placed into uniform memory banks and they do not move during the course of execution. Even though banks are uniform, we still implement this scheme using ILP to obtain the optimum data-to-bank mapping and minimum energy under this banking. The only difference from our initial ILP formulation is in selecting the bank sizes and the number of banks. Specifically, the bank sizes and the number of banks are given as constants to the ILP tool. In this case, Equation (3) and Equation (4) become unnecessary, and the start and end values of index variables i and j in Equation ( 5) and Equation ( 8) need to be changed such that they include only the specified bank size and the given number of banks. • Nonuniform Banking: This is the integer linear programming based strategy discussed in this paper wherein banks with different sizes are employed. The data blocks frequently accessed together can be placed in a larger bank, whereas a single data block (without any access pattern relationship with other data blocks) can be placed in a smaller sized bank to optimize the energy consumption in active banks and during bank activations/deactivations.

Benchmark

• Migration: This is an extension to the previous strategy (see Section 3.2) where data migration is employed to decrease the energy consumption further. An accessed data block is migrated to an active bank if doing so is profitable from the energy consumption point of view. The rationale behind this scheme is to transfer the data block being accessed to one of the active memory banks, thereby cutting the number of active memory banks as much as possible.

Results

Table 5 gives the results based on power-down operating mode (i.e., when, as a low-power mode, we use only the power-down mode). Note that, all the values are relative to the ratios given in Table 4. Energy improvement brought by the Nonuniform Banking version over the Uniform Banking version for different bank sizes are given in columns two through five. Bank sizes are given as ratios to a data block size as given in Table 4. For example, in the third column (titled '2'), we compare our approach with the Uniform Banking strategy with banks that have fixed sizes of 2k (assuming that a data block size is k). In our approach, a total of 8k memory is partitioned nonuniformly. However, in uniform banking scheme, memory is composed of four different banks where all of the banks are of size 2k. The sixth column gives the average improvement brought by our approach over the uniform banking scheme. We see that the overall average reduction in energy consumption is 10.4%, showing the benefits of nonuniform banking. ILP solution times for our approach range from 163 sec (btrix) to 64 min (bmcm). As it was stated earlier, we used also ILP to obtain the results for the Uniform Banking approach in order to make a fair comparison against our approach. Performance results are given in Figure 3. These values are given as improvements brought by the Nonuniform Banking approach over the Uniform Banking scheme with different bank sizes. Negative values indicate that there is a performance overhead if our approach is used. The average performance im- provement values are -5%, 14%, 7%, 13% and -4% for adi, apsi, bmcm, btrix and wss, respectively. One can observe from this figure that the maximum overhead brought by our approach is 22% for wss with a bank of size 8. On the other hand, maximum improvement brought by our approach is 28% for btrix with a bank of size 1. In general, the larger the bank size, the better the performance is. This follows from the fact that the number of banks to activate (if the corresponding bank is in a low-power operating mode) decreases if a larger bank size is preferred. Figure 4 shows the reduction in energy consumption for btrix benchmark when only Nonuniform Banking is used, when Uniform Banking is used with data migration, and when Nonuniform Banking is used along with data migration. Each bar represents percentage reduction in energy over the Uniform Banking scheme without data migration. We see that Nonuniform Banking reduces energy by 15% and data migration (on a uniform bank) reduces by 20% when used separately. If these two approaches are combined to form the Nonuniform Banking scheme with data migration strategy, then the energy reduction reaches 38% on average.

Conclusion

Memory system can be a major energy consumer in embedded systems. Therefore, recent years have witnessed several studies that target at reducing memory energy consumption. Banking is such a scheme and has received a lot of attention recently from both hardware and software communities. One of the common characteristics/assumptions made by most of the past work on banking is that all the banks are of the same size. While this makes the formulation of the problem easy, it also restricts the potential solution space. This paper investigates the possibility of employing nonuniform bank sizes for reducing memory energy consumption. We show through experiments that working with customized nonuniform memory banks brings important savings over the uniform banking strategy. The second contribution of this paper is a formulation of the data migration problem. Our experiments with data migration show that it brings additional energy savings over nonuniform banking.

Figure 1 .

 1 Figure 1. An example loop nest written in a pseudo high-level language (left) and its blocked (tiled) version (right). Each data block (tile) is of size T 1 × T 2 array elements, and the transformed loop nest is structured based on this tile size.

Figure 2 .

 2 Figure 2. Dividing a two-dimensional array into data blocks (tiles).

Figure 3 .

 3 Figure 3. Percentage improvements in performance brought by the Nonuniform Banking approach over the Uniform Banking approach.

Figure 4 .

 4 Figure 4. Percentage reductions in energy brought by different schemes.

Table 1 . Energy consumptions (per cycle) and resynchronization costs for our operat- ing modes.

 1

	Operating	Energy	Resynchronization
	Mode	Consumption (nJ)	Cost (cycles)
	Active	3.570	0
	Standby	0.830	2
	Nap	0.320	30
	Power-down	0.005	9000
	data access pattern extraction strategy. Section 3 describes
	our ILP variables, constraints, and overall problem formu-
	lation. Section 4 introduces the experimental platform, and
	presents the results. Section 5 concludes with a summary of
	the paper.

Table 2 . The constant terms used in our ILP formulation. These are either architecture specific or program specific.

 2

Table 3 . The benchmark codes used in this study.

 3

	Parameter	Value
	Number of Banks	4
	Data Block Size : Memory Bank Capacity	1:1,1:2,1:4,1:8
	σ	1.3
	Bank Energy (Power-down)	1
	Bank Energy (Nap)	64
	Bank Energy (Standby)	166
	Bank Energy (Active)	714
	Bank Activation Energy	535.5
	Bank Deactivation Energy	535.5
	Data Migration Energy	142.8

Table 4 . The default simulation parameters.

 4

Table 5 . Percentage reductions in energy brought by Nonuniform Banking approach over the Uniform Banking approach with varying (fixed) bank sizes.

 5

		nonuniform migration nonuniform+migration
	Percentage Reduction in Energy	0% 5% 10% 15% 20% 25% 30% 35% 40%
		1	2	4	8

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

* This work is supported in part by NSF Career Award #0093082


Vinil Varghese

Tom Chen

Peter M Young

Systematic Analysis of Active Clock Deskewing Systems Using Control Theory

A formal methodology for the analysis of a closed loop clock distribution and active deskewing network is proposed. In this paper an active clock distribution and deskewing network is modeled as a closed loop feedback system using state space equations. State space analysis allows systematic analysis of any clock distribution and deskewing systems to determine various conditions under which a system can over-compensate and become potentially unstable. Such an analysis can be very useful to designers as they will be able to determine analytically as to how the clock deskewing system behaves. By using the proposed approach, repeated simulations can be greatly limited and maybe entirely avoided. We applied the proposed method to an experimental clock deskewing system to illustrate the effectiveness of the proposed approach. The proposed approach can be further extended to determine performance of such systems under different configurations.

I. INTRODUCTION

The current level of integration has made clock distribution an increasingly difficult task. The increase in process and environment variations due to aggressive scaling and integration has continued to contribute to increase in clock skew. One effective method of dealing with increasing clock skew in the design process is the adoption of on-chip active skewing system [START_REF] Rusu | Clock Generation and Distribution for the first IA-64 Microprocessor[END_REF].

The existing clock deskewing approaches can be broadly categorized into two different types of designs, namely, open loop and closed loop designs. The open loop design methods for clock distribution are based on implementing geometrically and electrically matched clock distribution structures to minimize skew on the chip. The most commonly used method for distributing clock signals in chips is to insert buffers either at the clock source and/or along a clock path, forming a clock tree structure. This clock source is frequently described as the root of the tree. A mesh version of the clock tree structure is also used in which shunt paths further down the clock distribution network are placed to minimize the interconnect resistance within the clock tree. This mesh structure effectively places the branch resistances in parallel, minimizing the clock skew [START_REF] Friedman | Clock Distribution Networks in Synchronous Digital Integrated Circuits[END_REF], [START_REF] Wagner | Clock system design[END_REF], [START_REF] Friedman | Clock dsitribution design in VLSI circuits-An overview[END_REF]. Another approach for distributing clock signals utilizes a hierarchy of planar symmetric H-tree or X-tree structures [START_REF] Friedman | Clock Distribution Networks in Synchronous Digital Integrated Circuits[END_REF], [START_REF] Weste | Principles of CMOS VLSI Design : A System Perspective[END_REF], [START_REF] Wagner | Clock system design[END_REF], [START_REF] Friedman | Clock dsitribution design in VLSI circuits-An overview[END_REF]. These methods will no longer be able to achieve the skew requirements in the future due to the complexity of the designs and increased process variations. Several attempts have been made to utilize localized clock skew to improve synchronous performance by providing more time for the critical worst case data paths. However, in order for these methods to be effective, the accurate value of clock skews need to be known during the design. This is difficult to achieve [START_REF] Friedman | Clock Distribution Networks in Synchronous Digital Integrated Circuits[END_REF], [START_REF] Friedman | Clock dsitribution design in VLSI circuits-An overview[END_REF], [START_REF] Cirit | Clock skew elimination in CMOS VLSI[END_REF], [START_REF] Sutoh | A clock distribution technique with an automatic skew compensation circuit[END_REF]. In order to compensate for skew in real time a closed loop clock distribution system known as the active deskewing system, has been proposed by [START_REF] Chen | Internal technical report[END_REF], [START_REF] Rusu | Clock Generation and Distribution for the first IA-64 Microprocessor[END_REF], [START_REF] Rusu | Clock Generation and Distribution for the first IA-64 Microprocessor[END_REF], [START_REF] Geannopoulos | An adaptive digital deskewing circuit for clock distribution networks[END_REF], [START_REF] Aguiar | Highly efficient multi-point clock distribution networks[END_REF], [START_REF] Singer | The first IA-64 microprocessor: A design for highly parallel execution[END_REF]. Such a system exhibits disturbance rejection and is robust to modeling errors.

For a closed loop feedback system approach employed in an active deskewing scheme, stability is an important criterion. The existing analysis methods for the closed loop deskewing systems are based on repeated brute force simulations. This type of method is very time consuming and does not give a definitive result by which one can say assertively that the system designed is stable or not. Since active deskewing systems employ closed loop techniques, it can be modeled as a closed loop control system using state space equations. This paper describes an analytical approach using the state space equations in control theory. The proposed approach can be used to analyze the stability a given clock deskewing system using the existing control system theories. We will illustrate how the state space equations, both in linear and non-linear models, can be formulated and how some of the existing control system theories can be applied to optimize performance and to determine the stability of a given active deskewing system.

II. DESCRIPTION OF CLOCK DESKEWING SYSTEM

In the active clock deskewing system, the entire chip is divided into many clock zones. Figure 1 shows a schematic of a 28-zone clock deskewing system. Clocks in each zone are derived from a clock buffer assigned to that zone. Each of the zones have a certain communication pattern among themselves to ensure that the skew across the chip is within a given specification. The clock buffers in a each zone communicate with each other through a hierarchical ring structure as shown in Figure 1. Each clock buffer adjusts its output based on the phase difference in the arrival time of the clock between it and its neighbors. When skew at a certain spot of the chip is increased, the clock buffers within this region will be automatically adjusted to minimize the skew within this region. This will in turn cause increase in region-to-region skew. Thus, in each of the regions, the skew will be automatically adjusted. Hence a wave of adjustment is carried out throughout the chip until the skew is within the required specification. The logical implementation of the deskew stations is shown in Figure 2. [START_REF] Vinil | Stability analysis of active clock deskewing systems using a control theoretical approach[END_REF] describes this logical implementation in detail. A slightly complex example of the implementation of such a scheme is shown in Figure 3. The 27-zone system is more complex compared to the 28-zone system due to the higher level of hierarchy, which makes it more difficult to analyze in terms of performance. The active clock deskewing scheme is a non-linear discrete timeinvariant MIMO control system. It can be initially modeled as a linear system in order to understand the dynamics of the system better. We will present the linear system representation first, followed by a more accurate representation using non-linear state space equations. The approximation used in the linear system involved using linear gain values in the system matrix, rather than using non-linear elements that saturate the adjustments in the outputs.

The linear model for the active clock deskewing scheme can also be used to analyze stability for optimization of the acquisition time. The acquisition time for the system is defined as the number of clock cycles the system takes to deskew on the occurrence of noise to the system in the form of jitter. The two different linear models, namely, the un-optimized linear model and the optimized linear model, are discussed in the following subsections.

A. Un-optimized Linear Model

Let T arr k be a vector of the arrival times of the clock in all the clock zones at clock cycle k; let T nom be the nominal clock period from the PLL; and let U 1 be a matrix describing the connections among clock zones along with the gains that are associated with each connection. The state space equation for updating (adjusting) clock period at clock cycle k + 1 is:

T arr k+1 = T nom + T arr k + U 1 • T arr k (1)
The values of gains in the matrix U 1 is chosen such that the following equation is satisfied:

| eig(1 + U 1) |< 1 (2)
If the absolute value of the eigen values of (1 + U 1) is less than one, it implies that the system is stable. Equation ( 1) can be better explained using a simple case of a clock distribution network employing the proposed deskewing scheme.

Consider an active clock deskewing scheme as shown in Figure 4. This network has 4 clock zones. Assume the arrival times of all the zones except zone 2 to be zero. The zones compare their current and past arrival times of the clock signal with their neighbors. A jitter of 20 ps is introduced to zone 2. The matrix T arr k can be written as:

T arr k =             0 0 20 0 0 0 0 0            
Let the nominal arrival time of the system be 350 ps, hence the vector Tnom is:

Tnom =             350 350 350 350 350 350 350 350            
The matrix U 1 can be written as:

U 1 =            -k1 -k1 0 0 k1 k1 0 0 1 -1 0 0 0 0 0 0 k2 k2 -2 * k2 -2 * k2 0 0 k2 k2 0 0 1 -1 0 0 0 0 0 0 k1 k1 -k1 -k1 0 0 0 0 0 0 1 -1 0 0 0 0 k1 k1 0 0 -k1 -k1 0 0 0 0 0 0 1 -1           
Using the stability criterion mentioned in Equation ( 2), the values of k1 and k2 were found to be 0.06 and 0.07 respectively. The matrix U 1 for this example is:

U 1 =            -0.06 -0.06 0 0 0.06 0.06 0 0 1 -1 0 0 0 0 0 0 0.07 0.07 -0.14 -0.14 0 0 0.07 0.07 0 0 1 -1 0 0 0 0 0 0 0 .06 0.06 -0.06 -0.06 0 0 0 0 0 0 1 -1 0 0 0 0 0 .06 0.06 0 0 -0.06 -0.06 0 0 0 0 0 0 1 -1           
The Table I shows the skew between the clock arrival times of all the four zones. As can be seen from Table I, absolute value of the maximum skew at the first clock cycle was 20 ps and at the end of the eighth clock cycle it reduced to 3.2 ps.

B. Optimized Linear Model

In closed loop active clock deskewing systems, the acquisition time is a very important factor. The un-optimized clock deskewing scheme can be modified to improve the acquisition time. This was achieved by modeling the entire system as a discrete linear quadratic regulator (DLQR) [START_REF] Kailath | Linear Systems[END_REF]. The basic state space equation remains the same as that for the un-optimized systems (Equation ( 1)), with the only difference being that the matrix U 1 gets modified. The state space equation for the optimized deskewing system is:

T arr k+1 = T nom + T arr k + U 2 • T arr k (3)
By modeling the linear system as a linear quadratic regulator, the output can be kept small using as little as input as possible. This allows a trade-off to be made between the input effort and the regulation of the output and can be formulated as a least squares problem. The optimization is done using Riccati recursions performed by DLQR. The matrix U 2 was generated using DLQR which generates a discrete linear quadratic regulator. All the inputs to the system except the Matrix U 1 remain the same. The matrix U 1 is replaced by the matrix U 2. The matrix U 2 for the example in Figure 4 is:

U 2 =            -0.

C. Non-Linear Model

The non-linear model of active deskewing systems takes into account some practical issues of noise and implementation. When correcting the clock arrival time for a given zone based on skew, the amount of correction is often discrete due to quantized increments and decrements of delay. To account for quantized adjustments, we define step as the minimum amount of delay by which the variable delay buffer (VDB) increases or decreases the arrival time of the clock at each clock zone. In addition, adjustments to the clock arrival time of a clock zone should be made based on "real" skew between clock zones, rather than false skew caused by potential jitter. Therefore, adjustments to the clock arrival time of a clock zone will be made if there are consecutive skew comparison results of the same direction between two clock zones. To simplify the discussion without losing generality, we assume that the window for preventing clock jitter is 3 clock cycles. That is: a clock zone in the deskewing system needs to wait for consistent "increase" or "decrease" requests from its neighbors in 3 consecutive clock cycles before it will adjust its own clock output. The corrections to a clock zone can be written as:

∆T r1 = f (mod(clk cycle, n) • step • f ( 1 3 (sign[U • T arr1 k ] +sign[U • T arr2 k ] + sign[U • T arr3 k ])) (4)
where T arr1 k is the current state vector containing the arrival time of the clock in each zone of the deskewing system at the k th instant. T arr2 k is the state vector containing the arrival time of the clock in each zone of the distribution at the (k -1) th instant. T arr3 k is the state vector containing the arrival time of the clock in each zone of the distribution at the (k -2) th instant. These past values of arrival times are used so as to make a correction only if the same type of correction (either positive or negative) was requested in the previous two consecutive clock cycles as well. For example, consider the case when the previous two comparisons of clock arrival times for any zone required the zone to speed up the clock arrival time for that zone. If the current comparison also requires the clock arrival time to speed up, only then will the clock arrival time for that zone be sped up. The function f in Equation ( 4) is a threshold function and can be defined as:

f (x) = 1, x ≥ 1 = 0, -1 > x < 1 = -1, x ≤ -1 (5)
The term f

( 1 3 (sign[U • T arr1 k ] + sign[U • T arr2 k ] + sign[U • T arr3 k ]))
checks if the values of the past two comparisons were the same as the result of the current comparison. It outputs a 1 or a -1 depending on whether three consecutive comparisons required the delay to be increased or decreased by a step size, and 0 otherwise.

The function, mod(clk cycle, n), in Equation ( 4) allows the adjustments to the clock arrival time of clock zones n-1 clock cycles out of every n clock cycles. The one remaining clock cycle in every n clock cycles are used for the global clock arrival time adjustment to accommodate the centering of arrival time. This may be desirable to ensure that there is no systematic drift of clock arrival time at the global level. Such a scheme can be modeled as: 6) describes a mechanism that speeds up or slows down the clock in each zone once in every n clock cycles by five times the nominal step size where period • k represents the nominal clock arrival time at time k.

∆T r2 = 5•step•[1-f (mod(clk cycle, n))]•f (period•k-T arr1 k ) (6) Equation (
The nonlinear model to describe the active deskewing system can be formulated as:

T arr1 k+1 = T arr1 k + ∆T r 1 + ∆T r 2 (7)

IV. STABILITY ANALYSIS USING CONTROL THEORY

The stability analysis for the linear models can be simply performed by observing the absolute value of the eigen values of the system matrix as shown in Equation ( 2).

Analytically proving stability of a nonlinear time-invariant system is very difficult in general. However, if the nonlinearity of the system fits into a certain set of special cases, a variety of methods can be used for stability analysis [START_REF] Balas | µ-analysis and synthesis[END_REF], [START_REF] Desoer | Feedback System: Input-Output Properties[END_REF], [START_REF] Safonov | Stability margins of diagonally perturbed multivariable feedback systems[END_REF]. One of the unifying methods for nonlinear control system stability analysis is integral quadratic constraints (IPC) [START_REF] Goh | Robust analysis, sectors, and quadratic functionals[END_REF], [START_REF] Jonsson | Unifying format for multiplier optimization[END_REF], [START_REF] Rantzer | System analysis via integra quadratic constraints[END_REF], [START_REF] Megretski | A guide to IQCβ: Software for robustness Analysis[END_REF], [START_REF] Kretchmar | Robust reinforcement learning control with static and dynamic stability[END_REF]. In the IQC framework, the nonlinear functions can be bounded using sector-bounded limiting nonlinearity. In other words, the nonlinear functions in a system are replaced by linear functions that are upper bound of the nonlinear functions. We then prove whether the control system with the linear upper-bound functions is stable under any circumstances. Stability analysis for linear systems is well established and understood. If the sector-bound linear system is proven to be stable, the nonlinear system must also be stable. However, if the sector-bound linear system can not be proven to be stable, the stability of the nonlinear system is unknown.

In the system model in Equation [START_REF] Sutoh | A clock distribution technique with an automatic skew compensation circuit[END_REF], the nonlinear functions mod, sign, and the threshold function f are bounded using linear functions. One of the sector blocks (sector-bound linear functions) used in the IQC analysis toolbox [START_REF] Megretski | A guide to IQCβ: Software for robustness Analysis[END_REF] is shown in Figure 5. For example, the sec(x) x Fig. 5. Sector block in IQC toolbox nonlinear element f in Equation ( 7) can be approximated using a modified sector block:

1 2 + 1 2 • sec (8)
This modified sector block is shown in Figure 6. The function f

1/2 + 1/2*sec(x)
x Fig. 6. Modified sector function can be approximated using the modified sector block as shown in Figure 7. The nonlinear element f (mod(clk cycle, 10)) can be

f 1 (x) x 1 1 -1 -1
Fig. 7. Approximation of element f using the modified sector block approximated using the modified sector in Equation ( 8) as shown in Figure 8. Approximation of [1f (mod(clk cycle, 10))] is shown in Figure 9. Using these modified sector blocks, the entire nonlinear system model can be built in SIMULINK using the IQC toolbox. Equation 9 describes the nonlinear model after replacing the nonlinear elements in Equation [START_REF] Sutoh | A clock distribution technique with an automatic skew compensation circuit[END_REF] with sector blocks from the IQC toolbox.

T arr1 k+1 = T nom + T arr1 k + ( 1 2 + 1 2 • sec) • step • ( 1 2 + 1 2 • sec) •(U • T arr1 k ) + ( 1 2 + 1 2 • sec) • (U • T arr2 k ) +( 1 2 + 1 2 • sec) • (U • T arr3 k ))) +5 • step • 1 2 + 1 2 • sec • 1 2 + ( 1 2 • sec) -states1 k ) (9)
To help illustrate the modeling of the proposed non-linear deskewing system, Figure 10 shows the various blocks present in the IQC toolbox that were used to build the simulink model of the nonlinear system. The SIMULINK block diagram of the 27-zone nonlinear active deskewing system for analysis of stability using IQC toolbox is shown in Figure 11.

V. EXPERIMENTAL RESULTS

simulations for the linear and non-linear models were performed and all simulations were performed for a duration of 300 clock cycles. External noise in the form of clock jitter was introduced to all test systems at clock cycles 10, 60, 110, 160, 210, and 260. Figures 12 and13 show the skew of each of the zones in the 28-zone system for linear and non-linear models, respectively. The results show that both the linear and the non-linear systems deskew the external clock 9) where the nonlinear elements were replaced using the sector blocks. The delay blocks were created using state space models since the IQC toolbox does not contain discrete delay elements in the iqc lib SIMULINK library. The performance block was used to analyze the stability of this nonlinear system. The performance block is required to be used by the iqc gui command in order to determine if the system is stable or not. The iqc gui command when used to determine stability of systems, returns an output value of iqc gain if the system is stable else it does not return any value for iqc gain.

Step size for the deskewing system was set to 0.5 ps.

It is possible that the entire deskewing system becomes unstable. This happens when the clock zones keep over-compensating for the skew. Stability is guaranteed only for a certain range of step size by which the adjustment to the arrival time of the clocks are adjusted. The range for values of step in Equation ( 9) depends on the topology of clock distribution network. It also depends on how often the adjustments need to be done on the clock arrival times. For the 4-zone system shown in Figure 4, the value of step for which the system became unstable was found to be 9 ps. The simulation results for the 4-zone system using the nonlinear model in Equation ( 9) is shown in Figure 16. As seen in the results, the skew of each zone in the systems keeps increasing since the system overcompensated for the skew, thus making the system unstable. This result is also confirmed by using IQC stability analysis.

In general, it is relatively easier for Monte Carlo simulations to detect an unstable system. However, it is not possible for Monte Carlo simulations to prove a system in stable. The confidence grows with increasing amount of simulations. The proposed approach using control theory can prove a system is stable a much less amount of effort.

Simulations for stability analysis for the nonlinear systems were performed using the IQC-toolbox for Matlab. The CPU time for stability analysis for the 28-zone and 27-zone systems were 350 and 276 minutes, respectively, running on a 1.9GHz Pentium4 processor with 512MB of memory.

VI. CONCLUSIONS

With increasing clock frequencies and higher constraints on clock skew due to increased process and temperature variations, active clock deskewing schemes can be effectively used to reduce clock skew. Current methods for stability analysis of such closed loop active deskewing systems use brute force approaches and involve simulating the systems for very long periods of time with varying set of input conditions and without a definite answer as to whether the system is stable or not. This paper presents a systematic approach to analyze the stability of closed loop active deskewing systems using a control system theory approach. Linear models allow faster evaluation of systems, and more importantly, allow experiments on trading off system complexity and acquisition time using DLQR. The non-linear models allow more realistic modeling of the actual systems. However, the computational complexity for stability analysis using IQC increases significantly. Experimental 28-zone and 27-zone active deskewing systems were modeled as a closed loop feedback system both in linear and non-linear approach and analyzed with existing control theory analysis tools to determine its performance and stability. The stability of the systems was demonstrated using

Fig. 1 .

 1 Fig. 1. Block diagram of 28 zone clock distribution network

Fig. 2 .Fig. 3 .

 23 Fig. 2. Logical implementation of a deskew station

Fig. 4 .

 4 Fig. 4. A simple active deskewing network with 4 clock zones

Fig. 8 .

 8 Fig. 8. Approximation of element f (mod(clk cycle, 10)) using the modified sector block

Fig. 9 .

 9 Fig. 9. Approximation of element [1f (mod(clk c ycle, 10))] using the modified sector block

Fig. 10 .

 10 Fig. 10. Blocks used in IQC toolbox

Fig. 11 .

 11 Fig. 11. Block Diagram of the Nonlinear Model using IQC toolbox

Fig. 12 .Fig. 13 .

 1213 Fig. 12. Clock skew of each zone for the linear un-optimized 28-zone clock distribution system.

Fig. 14 .Fig. 15 .

 1415 Fig. 14.Clock skew of each zone in an un-optimized 27-zone clock distribution system.

Fig. 16 .

 16 Fig.[START_REF] Desoer | Feedback System: Input-Output Properties[END_REF]. Clock skew for each zone in an unstable 4-zone system

DLL Control System VDB Zone Clock Grid Feedback Clock Zone Clock Clock signals from neighboring zones 2 2 Shift Register

  TableIIbelow shows the skew between the clock arrival times of all the four zones. It is clear that the acquisition time of the optimized linear model is shorter than that of un-optimized linear model.

	76	0	0.2 4	0	0 .2 4	0	0 .24	0	
	0 0.24 0 0.2 4 0 0.2 4	-0.76 0 0 .24 0 0 .24 0	0 -0.76 0 0 .24 0 0 .2 4	0.24 0 -0.76 0 0.24 0	0 0.2 4 0 -0.76 0 0 .24	0.24 0 0.24 0 -0.76 0	0 0 .24 0 0.24 0 -0.76	0.24 0 0.24 0 0.24 0	         
	0	0 .24	0	0.24	0	0.24	0	-0.76

TABLE II SKEW

 II OF THE CLOCK ZONES FOR 8 CLOCK CYCLES CALCULATED FROM

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


Sankalp S Kallakuri

Alex Doboli
email: adoboli@ece.sunysb.edu

Eugene A Feinberg
email: eugene.feinberg@stonybrook.edu

Buffer Insertion for Bridges and Optimal Buffer Sizing for Communication Sub-System of Systems-on-Chip

We have presented an optimal buffer sizing and buffer insertion methodology which uses stochastic models of the architecture and Continuous Time Markov Decision Processes CTMDPs. Such a methodology is useful in managing the scarce buffer resources available on chip as compared to network based data communication which can have large buffer space. The modeling of this problem in terms of a CT-MDP framework lead to a nonlinear formulation due to usage of bridges in the bus architecture. We present a methodology to split the problem into several smaller though linear systems and we then solve these subsystems.

Introduction

We have applied CTMDP (Continuous Time Markov Decision Processes) to optimise the buffer space used in SoC architectures. This involves using continuous time queueing models for the architectures. The use of such continuous time stochastic models is necessary due to the continuous time nature of tasks when they are executed on the IP cores and the shift from RTL level design to system level design. A finite amount of buffer space has to be distributed among a set of processors talking to a bus and the continuous time modeling allows incorporating how long certain amounts of buffer space have to be allotted as well as how much of the space should be allotted to processor. The division of the finite buffer space by certain stochastic policies generated through the CTMDP based solutions [START_REF] Feinberg | Optimal control of average reward constrained continuous time finite markov decision processes[END_REF] could lead to an optimal division of the buffer resources. We found this optimal distribution of buffer space different from simple division of the space depending on traffic ratios.

While attempting to solve the buffer sizing problem we encountered a problem when there were bridges between buses. A typical example of such an architecture has been shown in Figure 1 where buses b,f and g talk to each other apart from processors. The architectures in which two buses are connected by a bridge which is a typical example in the AMBA and CoreConnect systems. For such a scenario with bridges the model developed for CTMDPs was nonlinear and the system of quadratic equations were not solvable for a test example shown in Figure 1. We solved this problem by splitting the system to smaller subsystems and solving linear equations obtained from CTMDP based methods for the subsystems.

CTMDPs and continuous time modeling have been used in work done by Pedram et al. and Marculescu et al. in the generation of power management policies. We have attempted to use similar stochastic modeling for optimal buffer sizing as well as distribution of finite buffer space.

Buffer Insertion with Split Subsystems

In Figure 1 the architecture has buses that are connected only to processors like bus a, as well as buses b,f and g which are connected to other buses too. Thus communication between processors 2,3 and 5 will involve insertion of buffers and will require the controller to take into account traffic from all three processors while making arbitration decisions for any of these three buses. One of the problems with designing such an arbiter is that it would require equations which would be quadratic in nature due to the interaction between two buses. Each bus by itself has been modeled by a linear set of equations. In case the buses talk to each other through bridges the equality constraints and the cost function have quadratic terms. The number of quadratic terms depend on how many points in the bus topology are there in which buses are connected to each other and an equation may have more than one quadratic term. An attempt was made to solve the nonlinear equations by using the nonlinear solver from Matlab ver. 6.1. but we were not able to get solutions for them.

The solution we propose for this problem is to split the bus architecture into a set of linear systems which are sep- In order to find the optima for the entire system all the equations shall be solved in one go and not sequentially for each subsystem. In Figure 2 for subsystem 1 initially the buses b,f and g were communicating but after the split bus b becomes a shared resource between buffer b1, buffer b2, and processors 2 and 3 isolating it from buses f and g thus enabling us to write a set of linear equations for it. After solving the CTMDP for this system of equations and translating the state action pair probabilities into buffer space requirements by using the Kswitching policy [START_REF] Feinberg | Optimal control of average reward constrained continuous time finite markov decision processes[END_REF] for a certain processor bus pair, the system is resimulated with the new buffer lengths and the losses are compared.

Experiments

The experiments used a network processor as a test architecture for the buffer insertion and buffer space distribution. In Figure 3 we have plotted the loss rates at the processors before and after the buffer sizing as the first and second bars of Figure 3. We found that though the loss rates decrease drastically for some processors for example processor 16 in Figure 3 they increase slightly for some processors for example processor 1. The third bar in Figure 3 are the loss rates for a timeout based policy, in which the processors request is not served if the data in the buffer times out i.e. reaches a threshold time. The threshold time chosen was the average time spent by a request in a buffer. We repeated these experiments for 10 iterations and found that though the loss may increase for some processors the overall loss of the system decreases by about 20% as compared to the constant buffer sizing policy and 50% for the timeout policy. We feel the difference before and after resizing could be improved with better profiling and weighing of the loss In Table 1 we present the variation in the loss rates before and after sizing the buffers. We have presented the results only for a few processors which show significant variation but a similar trend was observed for the rest of the processors. We observed that some processors loss rates may increase when the buffer space is very limited as in the 160 units case and the redistribution doesn't provide much improvement as discussed in the previous paragraph. We increased the total buffer space from 160 to 320 and 640. The loss rates after resizing decreased with the increase in buffer space and fell to zero for the total buffer space of 640 units.

Conclusion

We have presented a methodology to judge the amount of buffer space required and in what points in the architecture it would be required by using stochastic models of the architecture. The use of CTMDP based methods gives us the optimal redistribution of the finite amount of buffer space so that loss is minimised, as seen in the experiments. The use of buffers for bridges can lead to efficient communication between two buses and buses can talk through them with reduced or no loss to other buses used by a different set of processors.

Figure 2 .

 2 Figure 1. Sample Architecture buffers

Loss rates before and after sizing

	300
	250
	LOSS
	200
	150
	100
	50
	0	0	2	4	6	8	10	12	14	16	18
				PROCESSORS
	Figure 3. PROCESSOR	Buf 160		Buf 320	Buf 640
				pre post pre post pre post
		1		70	83		41	40	48	0
		4		80	100		78	55	74	0
		15		107	90		99	12	88	0
		16		96	82		84	0	93	0

Table 1 . Loss under varying total buffer size at

 1 processors i.e. allowing some losses to be more important than the others.

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