Raúl Blázquez

Fred Lee

David Wentzloff

Brian Ginsburg

Johnna Powell

Anantha Chandrakasan

Direct Conversion Pulsed UWB Transceiver Architecture

Ultra-wideband (UWB) communication is an emerging wireless technology that promises high data rates over short distances and precise locationing. The large available bandwidth and the constraint of a maximum power spectral density drives a unique set of system challenges. This paper addresses these challenges using two UWB transceivers and a discrete prototype platform.

System considerations

The use of ultra-wideband signals for communication purposes is approved by the FCC from 3.1 to 10.6 GHz with a maximum effective isotropic radiated power spectral density of -41.3 dBm/MHz. An effective high data rate transceiver in this band should provide robust communication under severe multipath conditions (rms delay spread of the channel on the order of 20 ns) and narrowband interferers. In addition, a fast signal acquisition algorithm must be implemented to reduce the duration of the preamble to a value comparable with current wireless systems (~20 µs).

The RF Front-end must meet the specifications on noise figure and linearity over a bandwidth larger than 500 MHz. The impulse responses of both the antenna and the RF front-end add to that of the channel. Since the receiver will only be able to deal with a maximum channel impulse response set by design, the RF front-end must be designed to meet this constraint.

The ADC requires sampling rates larger than 500 MSps. The specification of the data converter resolution determines not only its power dissipation but also that of the digital back end. A 1-bit analog-to-digital converter (ADC) in a noise limited regime, and a 4-bit ADC in a narrowband interferer regime are sufficient [START_REF] Blazquez | Digital architecture for an ultrawideband radio receiver[END_REF].

The back end requires parallelization to reduce the packet synchronization time and to process the large data rate provided by the ADC. The inter-symbol interference (ISI) due to multipath can be addressed with a Viterbi demodulator. The energy spread caused by the multipath can be compensated using a RAKE receiver. These elements require an estimation of the impulse response that may be obtained during the packet synchronization. The frequency of an interferer may also be estimated in the digital back end. The large complexity required in the synchronization and demodulation of the UWB signal results in more than half of the system power being dissipated in the digital back end and the ADC.

First generation transceiver

Fig. 1 shows a system-on-a-chip transceiver for baseband pulsed UWB signals [START_REF] Blazquez | A baseband processor for pulsed ultra-wideband signals[END_REF] that was implemented using a 0.18 µm CMOS technology at 1.8 V in a 4.3 mm × 2.9 mm die. A wireless link of 193 kbps was demonstrated with this transceiver. The RF front does not require a down converter. The analog-to-digital converter is a 4-way time-interleaved flash ADC that performs an initial 4-way parallelization of the signal. The timing synchronization is fully performed in the digital back end. Through further parallelization, packet synchronization is obtained in less than 70 µs.

Architecture of a 3.1-10.6 GHz transceiver

We are currently developing a second generation UWB system to operate in the 3.1-10.6 GHz band. The signal is comprised of a sequence of 500 MHz bandwidth pulses that are upconverted to one of 14 channels (subbands) in the 3.1-10.6 GHz band. The system is designed to transmit 100 Mbps. An electrically small planar antenna [START_REF] Powell | Differential and single ended elliptical antennas for 3.1-10.6 GHz ultra wideband communication[END_REF] of only 4.2 cm × 2.7 cm has been developed (Fig. 2). The block diagram of the receiver is shown in Fig. 3. The RF front end uses a direct conversion architecture. Both in-phase and quadrature channels are then digitized using two 5-bit successive approximation register ADCs that feed the digital back end.

In order to cope with the multipath, the channel impulse response is estimated with a precision of up to four bits during the packet preamble. This information is used in a RAKE receiver and in a Viterbi demodulator, both of them programmable. The digital back end detects the presence of an interferer and estimates its frequency that may be used in the front end notch filter. This receiver allows us to trade off power dissipation with signal processing complexity, quality of service and data rate, adapting to channel conditions.

A discrete prototype with the same specifications has been designed and implemented, allowing not only the testing of the different parts of the transceiver for specifications, but also a complete testing of the algorithms implemented in the digital back end under realistic conditions. This platform is also flexible enough to generate all kinds of signals within a bandwidth of 500 MHz, allowing the comparison between different modulation schemes. Fig. 4 shows an example of a modulated pulse used in this discrete prototype.

Conclusions

The key system challenges for UWB communication systems are outlined in this paper. The design trade-offs are illustrated using two different UWB transceivers and a discrete platform.

Figure 1 .

 1 Figure 1. Single chip UWB transceiver.

Figure 2 .

 2 Figure 2. Planar antenna for UWB.

Figure 3 .

 3 Figure 3. UWB system block diagram.

Figure

  Figure 4. 500 MHz pulse with carrier 5 GHz. 580 ps/div

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

Acknowledgements

This research is sponsored by Hewlett-Packard under the HP/MIT Alliance and the NSF under contract ANI-0335256.


I Papaefstathiou

T Orphanoudakis

G Kornaros
email: kornaros@ellemedia.com

C Kachris
email: kachris@ellemedia.com

I Mavroidis

A Nikologiannis

Queue Management in Network Processors

Keywords: Network processor, memory management, queue management 2 Related Work: Memory Management in Network Processors

One of the main bottlenecks when designing a network processing system is very often its memory subsystem. This is mainly due to the state-of-the-art network links operating at very high speeds and to the fact that in order to support advanced Quality of Service (QoS), a large number of independent queues is desirable. In this paper we analyze the performance bottlenecks of various data memory managers integrated in typical Network Processing Units (NPUs). We expose the performance limitations of software implementations utilizing the RISC processing cores typically found in most NPU architectures and we identify the requirements for hardware assisted memory management in order to achieve wire-speed operation at gigabit per second rates. Furthermore, we describe the architecture and performance of a hardware memory manager that fulfills those requirements. This memory manager, although it is implemented in a reconfigurable technology, it can provide up to 6.2Gbps of aggregate throughput, while handling 32K independent queues.

Introduction

To meet the demand for higher performance, flexibility, and economy in emerging multi-service broadband networking systems, an alternative to Application Specific Integrated Systems (ASICs), which have been traditionally used to implement packet-processing functions in hardware, the so called Network Processors or Network Processing Units (NPUs), has emerged. NPUs can be broadly defined as System-on-Chip (SoC) architectures integrating multiple simple processing cores (so as to exploit parallelism and/or pipelining in order to increase the supported network throughput) and performing complex protocol processing at multi Gigabit per second rate. These processing cores are either Reduced Instruction Set Computing (RISC) CPUs, or dedicated hardware engines for specific complex packet processing functions that require wire-speed performance like classification, per-flow queuing, buffer and traffic management. Most modern networking technologies (like IP, ATM, MPLS etc.) share the notion of connections or flows (we adopt the term "flow" hereafter), that represent data transactions in specific time periods and between specific end-points in the network. Depending on the applications and algorithms used, the network processor typically has to manage thousands of flows, implemented as packet queues in the processor packet buffer [START_REF] Kumar | Beyond besteffort: Router architectures for the differentiated services of tomorrow's internet[END_REF]. Therefore, effective queue management is a key to high-performance network processing as well as to reduced development complexity. The focus of this paper is twofold: first we quantify the bottlenecks of employing packet queues in legacy general purpose processing units; then we briefly present an FPGA-based queue management system, which can scale efficiently and provide an efficient solution for demanding applications. We claim that this hardware module is a very useful component for every networking system that manipulates queues since: a) it supports a large number of simple request-acknowledge interfaces, b) it executes a large number of general instructions and c) it can handle either fixed size or variable length pieces of data. In particular, we believe that this system will be a valuable add-in, likewise a co-processor in a separate FPGA, for the commercial ASIC NPs that have no dedicated memory handling hardware. In order to accurately evaluate the effectiveness of the various software and hardware schemes, we first briefly describe, in Section 2, a number of existing NPU architectures focusing on their memory management optimizations and then we analyze the necessary external memory bandwidth needed for implementing a general queue management system in such an NPU. In particular, in section 3 we analyze the performance bottlenecks of a reference such system, examining the accesses to external memories in isolation, based on the memory access patterns of real-world network applications. In section 4 we present an analysis regarding the performance of a queue management implementation on a widely used Network Processor and in section 5 we proceed in a more detailed analysis expanding our results to a generic NPU prototype architecture. After summarizing our experiences from software-based implementations in section 5.4, in section 6, we present our FPGA-based queue management system. The conclusions of our paper are finally outlined in section 7.

packets to be stored in appropriate queue structures, either before or after processing, and then to be selectively transmitted. These queues of packets should not be, in the majority of cases, organized as simple FIFOs, but instead should provide the means to access certain parts of their structures (i.e. access packets which reside in a specific position in the queue e.g. head or tail of the queue etc.). In order to efficiently cope with these requirements several solutions, based on dedicated hardware modules, have been proposed. Initially those modules were targeting high-speed ATM networks, where, due to the fixed ATM cell size, very efficient queue management was possible ( [START_REF] Rexford | Scalable Architectures for Integrated Traffic Shaping and Link Scheduling in High-Speed ATM Switches[END_REF], [START_REF] Whelihan | Memory optimization in single chip network switch fabric[END_REF]), while later on they have been extended to the management of queues of variable-size packets [START_REF] Kornaros | A Fully-Programmable Memory Management System Supporting Queue Handling at Multi Gigabit rates[END_REF]. The basic advantage of these hardware implementations is, obviously, the high throughput they can achieve. On the other hand the functions they can provide (e.g. single vs. double linked lists, operations in the head/tail of the queue, copy operations etc.) need to be selected very carefully, when initially designing hardware module, in order for those systems to be efficient for the majority, at least, of the network applications. Several trade-offs between dedicated hardware modules and implementations in software, for ATM networks, have been exposed in [START_REF] Serpanos | Efficient Memory Management for High-Speed ATM Systems[END_REF]. In general, several commercial NPUs follow a hybrid approach for efficient memory management: they utilize specialized hardware units that implement certain memory access sub-operations, but they do not provide a complete queue management hardware implementation. The first generation of the Intel NPU family, the IXP1200 [START_REF] Lakshmanamurthy | Network Processor Performance Analysis Methodology[END_REF], provides an enhanced SDRAM control unit, which supports single byte, word, and long-word write capabilities using a read-modify-write technique and may reorder SDRAM accesses for best performance (the benefits of this feature will also be exposed in the following section). The SRAM Control Unit of the IXP1200 also includes an 8-entry Push/Pop register list for fast queue operations. Although these hardware enhancements improve the performance of typical queue management algorithms they cannot keep up with the requirements of high-speed networks. Therefore the next generation IXP-2400 provides high-performance queue management hardware that efficient supports the enqueue and dequeue operations [START_REF] Lakshmanamurthy | Network Processor Performance Analysis Methodology[END_REF]. Following the same approach the PowerNP NP4GS3 incorporates dedicated hardware acceleration for cell enqueue/dequeue operations in order to manage packet queues [START_REF] Allen | PowerNP network processor: hardware, SW and applications[END_REF]. Freescale's C-5 NPU also provided memory management acceleration hardware [START_REF] Corp | C-5 Network Processor Architecture Guide[END_REF], which is probably not adequate, though, to cope with demanding applications that require frequent access to packet queues. Therefore, the same company has also manufactured the Q-5 Traffic Management Coprocessor, which consists of dedicated hardware modules designed to support traffic management for up to 128K queues at a rate of 2,5 Gbps [START_REF] Inc | Q-5 Traffic Management Coprocessor Product Brief[END_REF].

External DRAM Memory Bottlenecks

Since a DRAM offers high throughput and very high capacity per unit cost, packet buffers are stored in external DRAMs in most of today's NPUs. Among DRAM technologies, we focus our analysis on DDR-SDRAM because it achieves very high performance while it is very cost-effective due to its widespread use. The DDR technology provides 12.8 Gbps of peak throughput when using a 64-bit data bus at 100 MHz with double clocking (i.e. 200 Mb/sec/pin). A DIMM module provides up to 2 GB of total capacity and it is organized into 4 or 8 banks in order to provide interleaving (i.e. to allow multiple parallel accesses). However, due to the bank-precharging period (i.e. when the bank is busy), successive accesses1 to the same bank may be performed every 160 ns. When a memory transaction tries to access a currently busy bank we say that a bank conflict has occurred. This conflict causes the new transaction to be delayed until the bank becomes available, thus reducing memory utilization. In addition, interleaved read and write accesses also reduce the mean memory utilization because they have different access delays 2 . By simulating a behavioral model of a DDR-SDRAM memory, we have estimated the impact of bank conflicts and read-write interleaving on memory utilization. Random bank access patterns were simulated as a realistic common case for typical network applications incorporating a large number of simultaneously active queues. The results of this simulation, for a range of banks, are presented in the two left columns of Table We considered aggregate accesses from 2 write and 2 read ports 3 . By serializing the accesses from the 4 ports in a round-robin manner we measured the throughput loss presented in Table 1. However, if the accesses of the 4 ports are scheduled in a more efficient way, we can achieve a lower throughput loss by reducing bank conflicts. The simplest approach is to effectively reorder the accesses of the 4 ports, in order to minimize bank conflicts. This can be performed by organizing pending accesses into 4 FIFOs (1 FIFO per port). In every access cycle the scheduler checks the pending accesses from the 4 ports for conflicts and selects an access that addresses a non-busy bank. The information for bank availability is achieved by keeping the memory access history (it remembers the last 3 accesses). In case that more than one accesses are eligible (i.e. belong to a non-busy bank), the scheduler selects one of the eligible accesses in a roundrobin order. In case that no pending access is eligible, the scheduler sends a no-operation to the memory, losing an access cycle. The results of this simple optimization are presented in Table 1. Assuming 8 banks per device, this very simple optimization scheme reduces the throughput loss by 50% in comparison with the not-optimized one.

4 Queue Management on the IXP1200

As it was described in Section 2, the most straightforward implementation of memory management in NPUs is based on software executed by one or more on-chip microprocessors. Apart from the memory bandwidth, which we examined in isolation in the previous section, a significant factor that affects the overall performance of a queue management implementation is the combination of the processing and data transfer latency (including the latency for the communication with the external memories and their controllers). Additionally, since dynamic memory management is usually based on the implementation of linked list structures, the respective pointer storage is almost always performed on SRAM memories; this is due to the fact that the pointer manipulation tasks need short accesses compared to the burst data accesses needed for buffering network packets.

The frequent pointer manipulation functions can also be the bottleneck of the queue management system depending on the application requirements and the hardware architecture. Therefore, the overall actual performance of a memory management scheme can only be accurately evaluated at the system level. We used Intel's IXP1200 as a typical NPU architecture and we provide indicative results regarding the maximum throughput that can be achieved when implementing queue management on this NPU. The IXP1200 consists of 6 simple RISC processing microengines [START_REF] Lakshmanamurthy | Network Processor Performance Analysis Methodology[END_REF] running at 200MHz. When porting the queue management software to those RISC-engines, special care should be given so as to take advantage of the local cache memory (called "Scratch memory") as much as possible. This is because any accesses to the external memories take a very large number of clock cycles. One can argue that using the multithreading capability of the IXP, someone can hide this memory latency. However, as it was demonstrated in [START_REF] Zhou | Queue Management for QoS Provision Build on Network Processor[END_REF], the overhead for the context switch, in the case of multithreading, exceeds the memory latency and thus this IXP feature cannot increase the performance of the memory management system, when external memories should be accessed.

Even by using a very small number of queues (i.e. less than 16), so as to be able to keep every piece of control information in the local cache and in the IXP's registers, we have measured that each microengine cannot service more than 1 Million Packets per Second (Mpps). Or, in other words, the whole of the IXP cannot process more than 6Mpps. Moreover, if 128 queues are needed, and thus some external memory accesses are necessary, each microengine can process at most 400Kpps. Finally, for 1K queues the peak bandwidth that can be serviced by all 6

IXP microengines is about 300Kpps, which agrees with the result in [START_REF] Spalink | Building a Robust Software-Based Router Using Network Processors[END_REF]. Since, in the worst case, the Ethernet packets are 64-byte long, we claim that the whole of the IXP cannot support more than 150Mbps of network bandwidth, even if only 1K queues are needed. We summarize the above throughput results in Table 2.

From the above it can easily be derived that this software approach, cannot cope with today's state-of-the-art network links, if the network application involves the handling of more than a hundred separate queues. In order to be able to experiment with different design alternatives and perform detailed measurements, we have implemented ourselves, a typical reference NPU. With the aid of a state-of-the-art FPGA that provides hard macros of very sophisticated embedded RISC cores, we have implemented the core design of an NPU. The architecture of the system, which was ported to a Xilinx Virtex-II Pro device [START_REF]Direct Memory Access and Scatter Gather Datasheet[END_REF], is depicted in Figure 1. As it is shown, the 64bit Processor local bus (PLB) is used as the system bus, at a clock frequency of 100MHz. The PowerPC 405 is used as the main processor. The OCM Controller is used to connect the PowerPC with the Specialized Instruction and Data Memory (16KBytes each). The size of the code used for memory management is small enough to fit in this small instruction memory. The packets are stored in an external DDR DRAM using a sophisticated DDR controller, while the queue information (mainly pointers) is stored in an external ZBT SRAM, using Xilinx's PLM External Memory Controller (EMC). In order to measure the performance of the system when real network traffic is applied to it, an Ethernet MAC port has been used. The MAC Core (provided by OpenCores) uses two WishBone(WB) Compatible ports. The first port is attached to the PLB Bus, through the PLB-to-WB Bridge, and is used for control. The second port is attached to a 4 Kbytes Dual Port internal Block RAM (DP-BRAM), and is used to store temporarily the in-coming and out-going Ethernet packets. With the aid of this on-chip DP-BRAM data transfers between the network interface and the queue manager (i.e. processor and buffer memory) can be achieved very efficiently.

Num of

Configuration

The PowerPC has been configured to use the instruction and data cache, both in write back mode. The PowerPC and PLB Bus clock frequency has been set to 100MHz and the DDR controller is configured in burst mode. Finally, the code has been compiled using GCC optimization level 2 and then handcrafted. The frequency selection was dictated by the implementation timing requirements. A state of the art embedded RISC core though, (like the PowerPC core provided in the Xilinx Virtex II Pro family) can easily reach operation frequencies in the range 200-300 MHz (even in this reference FPGA device), so we also compare the performance in those projected range of frequencies. Note that the design of Figure 1 represents a typical organization of an NPU core design, where the PowerPC is used as a typical on-chip embedded processor; the PowerPC is may even be more powerful when compared to the typical such cores used in commercial NPs.

PPC

Queue structure

We implemented queues of packets as single-linked lists.

The incoming data items are partitioned into fixed size segments of 64 bytes each. Our implementation organizes the incoming packets into queues and handles and updates the data structures kept in the pointer memory. A free-list keeps the free parts of the memory, at any given time, and a queue-table contains the header of all the employed queues.

The Queue Manager supports mainly the following functions:

-Enqueue Segment -Dequeue Segment -Enqueue Free List -Dequeue Free List Each segment function is analyzed into separate segment and free list sub-operations. For example, the enqueue packet operation is analyzed into the following steps: First a new pointer is allocated from the free list, then this pointer is stored to the queue list and then the data are transferred to the memory.

Performance evaluation

Table 3 shows the number of cycles for the execution of each segment operation. For a 100Mbps network and a minimum packet length of 64 bytes the available time to serve this packet is 5.12 µsec. The majority of the cycles are spent waiting for the data from the memory and for the transactions over the PLB bus. Even if the processor operation frequency is set to 400MHz, the improvement in the overall performance would not be significant, since the maximum frequency of the PLB bus, in the state-of-the-art reconfigurable chip is 200MHz and in general it is hard to clock a bus, such as the PLB, at more than 200MHz even in an ASIC. As Table 3 demonstrates, half of the cycles are used to copy the data of the segment. A major improvement is to exploit the "line transactions" of the PLB. In this case, the PowerPC execute the line transactions over the bus using the data cache unit as a temporary buffer [START_REF][END_REF]. Using this configuration a segment can be retrieved from the BRAM and stored into the data cache in only 12 cycles (9 cycles for 9 double words and 3 cycle latency). Thus, the total number of cycles to copy a segment becomes:

Cycles

T C = (T R + T l ) + (T W + T l ) = 2*(9+3)=24 cycles
where T R denotes the number of cycles to read a segment from the on-chip buffer (Xilinx BRAM block), T W denotes the number of cycles to write a segment to the DDR DRAM and T l denotes the 3-cycles bus latency. Thus, the total number of cycles to enqueue and dequeue a packet becomes 128 and 118 respectively, which dictates that the 100MHz PowerPC would sustain up to about 200 Mbps throughput.

Another improvement would be to use a sophisticated DMA controller like the one in [START_REF] Meleis | Designing communication subsystems for high-speed networks[END_REF]. In this case, four 32bit registers (DMA control, source/destination address and length registers) have to be set before each transaction [START_REF]Direct Memory Access and Scatter Gather Datasheet[END_REF]. However, each single PLB write transaction needs 4 cycles, thus we need at least 16 cycles to initiate the DMA transfer and at least 34 cycles to copy the data from the BRAM to the DRAM or vice versa. Note that the total time per operation is approximately the same as before.

Hence, the overall throughput does not increase significantly, but in this configuration the processor has additional available processing power for other applications, due to the offloading of the data copying tasks to the DMA engine.

Impact on system level design

The results of the previous section provide some insight on the limitations of software-based queue management implementations. These results can be roughly summarized in the following "rule-of-thumb": the clock frequency of the system is proportional to the network bandwidth supported, since a system with a 100MHz microprocessor seems to be adequate to handle only a full duplex 100Mbps network link. Of course, the supported throughput can be increased by employing enhanced memory transfer techniques, more efficient buses etc. In any case, the performance limitations of the software approach, probably, make it unsuitable for Gigabit networks. The trade-off is throughput vs. programmability.

In case the NPU architecture targets a wide variety of applications with moderate throughput requirements (e.g. low-end wireline or wireless LANs, access or edge network equipment) and the application requirements may change over time, the inherent programmability of the embedded multiprocessor architectures offers an adequate solution. However, more demanding applications in terms of target link rates or amount of packet operations and queue manipulations may easily consume all the available processing resources even when advanced VLSI technologies are employed (in which case the final endsystem cost becomes an issue, since additional processing power will not come for free even when technology makes it feasible). Efficient application-specific hardware engines seem to be the only solution in this case.

An FPGA-based Memory Management System (MMS)

The hardware-oriented approach addresses the limitations identified in the previous sections. In order to achieve efficient memory management, in hardware, the incoming packets are partitioned into fixed size segments of 64 bytes each. The segmented packets are stored in the data memory, which is segment aligned. The MMS performs per flow queuing for up to 32 K flows; each packet is assigned to a certain flow. The MMS offers a set of operations on the segmented packet, for flexible queue management, such as: The MMS is a generic queue management block that can be easily incorporated in any networking embedded system that can handle queues.

Experimental results

Extensive experiments of the MMS were performed, in the framework described in the last section, and by using micro-code specifically developed for the embedded CPUs of the reference hardware platform. Table 4 shows the measured latency of the segment commands. The actual data accesses at the Data Memory can be done, almost, in parallel with the pointer handling. In particular, a data access can start right after the first pointer memory access of each command has been completed. This is achieved because the pointer memory accesses, of each command, have been scheduled in such as way that the first one provides the corresponding Data memory address. The MMS latency has been measured for a system that has a conservative clock of 125 MHz (according to the synthesis and placement and routing tools, the MMS can work at more than 200MHz in a 0.18µm CMOS technology). Table 5 shows the MMS average latency for different loads. The total latency of a command consists of three parts: the FIFO delay, the execution latency and the data latency. MMS keeps incoming commands in FIFOs (one per port) so as to smooth the bursts of commands that may arrive simultaneously at this module. The latency that a command suffers, until it reaches the head of the FIFO, is the FIFO latency. As soon as a command reaches the head of the FIFO it starts its execution by accessing the pointer memory. The latency introduced from this point until the execution is completed is the execution latency. This latency defines the time interval between two successive commands; in other words it states the MMS processing rate. Finally, the delay required to read or write a data segment along including the possible DRAM bank conflict delay is called the data latency. Since the MMS accesses the pointer memory in parallel with the DRAM, the execution accounts only for 10.5 cycles of overhead delay.

Simple Commands

The MMS can handle one operation per 84 ns or 12 Mops/sec operating at 125MHz. In other words, and since each operation is executed on 64-byte segments, the overall bandwidth the MMS supports is 6.145Gbps.

Conclusions

It is widely supported that one of the most challenging tasks in network processing is the memory/queue handling. In this paper, we have first analyzed the memory access characteristics and the processing requirements of some common queue manipulation functions. Our performance evaluation of queue management implementations, both on the commercial IXP1200 NPU, as well as on our reference prototype architecture, exposes the significant processing resources required when general-purpose RISC engines are used to implement queue manipulation functions. Those results show that even with state-of-the-art VLSI technology and processor frequencies in the order of several hundreds MHz, a single processor can only achieve a throughput in the order of hundreds of Mbps (and for a moderate number of queues). Hence, we claim that, in order to support the multi Gigabit per second rates of today's networks we need specialized hardware modules.

In this paper we also briefly presented such a hardware module, which supports up to 6.2Gbps of network bandwidth when implemented on an FPGA. Since the hardware cost of the device is limited, we claim that such a hardware subsystem significantly increases the overall network processing performance at an acceptable cost.

Figure 1 :

 1 Figure 1: NPU core architecture set-up on the Xilinx Virtex-II Pro FPGA platform

Figure 2 :

 2 Figure 2: MMS Architecture

Table 1 :

 1 1.

		No Optimization	Optimization
		Throughput Loss	Throughput Loss
	banks	Bank	Bank conflicts +	Bank	Bank conflicts +
		conflicts	write-read	conflicts	write-read
			interleaving		interleaving
	1	0.750	0.75	0.750	0.750
	4	0.522	0.5	0.260	0.331
	8	0.384	0.39	0.046	0.199
	12	0.305	0.347	0.012	0.159
	16	0.253	0.317	0.003	0.139

DDR-DRAM throughput loss using 1 to 16 banks

  46 for the first segment of the packet, 68 for the rest

	Function
		Enqueue	Dequeue
	Dequeue Free List	34	42
	Enqueue Segment	46/68 *	52
	Copy a segment	136	136
	Total	216/238	230

*

Table 3 :

 3 Cycles per packet operationLet assume that the PowerPC's clock frequency is set to 100 MHz, then the available time for processing a single packet is 512 clock cycles for a half-duplex network, or 256 cycles for a full duplex network. This means that for the queue management only, all the available processing capacity of the PowerPC core has to be used so as to support a full duplex 100Mbps line. In other words, the PowerPC cannot afford to further manipulate the packet, thus another processor must be used for further processing.

Table 4 :

 4 Latency of the MMS commands

Overall Load FIFO delay Execution delay Data delay Total delay per command (Gbps) clock cycles

	6.14	68	10.5	31.3	109.8
	4.8	57	10.5	30.8	98.3
	4	20	10.5	30	60.5
	3.2	20	10.5	29.1	59.6
	1.6	20	10.5	28	58.5

Table 5 :

 5 MMS Delays

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

A new read/write access to 64-byte data blocks can be inserted to DDR-DRAM every 4-clock-cycles (access cycle = 40 ns).

Write access delay = 40 ns, Read access delay = 60 ns. When write accesses occur after read accesses, the write access must be delayed 1 access cycle.

A write and a read port from/to the network, a write and a read port from/to an internal processing unit. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Acknowledgments

This work was performed in the framework of the WEBSoC project, which is partially funded by the Greek Secretariat of Research & Technology.


Andreas Raabe
email: raabe@cs.uni-bonn.de

Blazej Bartyzel
email: bartyzel@cs.uni-bonn.de

Joachim K Anlauf
email: anlauf@cs.uni-bonn.de

Gabriel Zachmann

Hardware Accelerated Collision Detection -An Architecture and Simulation Results

We present a hardware architecture for a single-chip acceleration of an efficient hierarchical collision detection algorithm as well as simulation results for collision queries using this architecture. The architecture consists of two main stages, one for traversing simultaneously a hierarchy of discretely oriented polytopes, and one for intersecting triangles. Within each stage, the architecture is deeply pipelined and parallelized. For the first stage, we compare and evaluate different traversal schemes for bounding volume hierarchies.

A simulation in VHDL shows that a hardware implementation can offer a speed-up over a software implementation by orders of magnitude. Thus, real-time collision detection of complex objects at rates required by force-feedback and physically-based simulations can be achieved.

Introduction

Collision detection is a fundamental task in areas like animation systems, virtual reality, games, physically-based simulation, automatic path finding, virtual assembly simulation, and medical training and planning systems.

In many of these systems, collision avoidance is the ultimate goal. Most approaches today are reactive, i.e., they first place objects at a new trial position, then they check for collisions, and then compute new forces or positions, based on physical laws, so as to remove any collisions.

This approach poses very high demands on collision detection, because it must perform many collision checks per simulation cycle. A particularly demanding application is force-feedback, where updates of about 1000Hz must be done in order to achieve stable force computations. Since collision detection is such a fundamental task, it is highly desirable to have hardware acceleration available just like 3D graphics accelerators. Using specialized hardware, the system's CPU can be freed from computing collisions.

In this paper we present a new efficient architecture for hierarchical collision detection of two rigid objects using high-end ASIC technology.

We also present simulation results concerning its speed and size, which show that an implementation in dedicated hardware can speed up applications by at least an order of magnitude.

Related Work

Considerable work has been done on hierarchical collision detection in software [START_REF] Eckstein | Dynamic collision detection in virtual reality applications[END_REF][START_REF] Gottschalk | OBB-Tree: A hierarchical structure for rapid interference detection[END_REF][START_REF] Hubbard | Collision detection for interactive graphics applications[END_REF][START_REF] Van Den Bergen | Collision Detection in Interactive 3D Computer Animation[END_REF][START_REF] Zachmann | Rapid collision detection by dynamically aligned DOP-trees[END_REF]. Some of the bounding volumes (BVs) utilized are spheres, axis-aligned bounding boxes (AABB), oriented bounding boxes (OBB), and discretely oriented polytopes (DOP).

The first publications of work on dedicated hardware for collision detection was presented in [START_REF] Zachmann | An architecture for hierarchical collision detection[END_REF][START_REF] Zachmann | High-performance collision detection hardware[END_REF]. They focused on a space-efficient implementation of the algorithms, while we aim at maximum performance in this paper. In addition, they presented only a functional simulation, while we present a full VHDL implementation.

All other hardware-related research so far has tried to utilize existing graphics accelerator boards (GPU) [START_REF] Baciu | RECODE: an imagebased collision detection algorithm[END_REF][START_REF] Govindaraju | CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware[END_REF][START_REF] Gress | Object-space interference detection on programmable graphics hardware[END_REF][START_REF] Knott | CInDeR: Collision and interference detection in real-time using graphics hardware[END_REF][START_REF] Myszkowski | Fast collision detection between complex solids using rasterizing graphics hardware[END_REF]. While earlier approaches, such as [START_REF] Myszkowski | Fast collision detection between complex solids using rasterizing graphics hardware[END_REF], can basically handle only convex objects, later algorithms, such as [START_REF] Baciu | RECODE: an imagebased collision detection algorithm[END_REF][START_REF] Knott | CInDeR: Collision and interference detection in real-time using graphics hardware[END_REF], have extended these to more general cases such as unions of convex objects or closed objects. The general class of "polygon soups" can be handled by [START_REF] Govindaraju | CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware[END_REF], but they use a hybrid approach where the graphics hardware only identified potentially colliding sets.

All of the approaches using graphics hardware have the disadvantage that they either compete with the rendering process for the same hardware resource, or an additional graphics board must be spent for collision detection. The former slows down the overall frame rate considerably, while the latter would be a tremendous waste, since most of the resources of the hardware would not be utilized at all. Furthermore, most of these approaches work in image space, which reduces precision significantly.

The Algorithm

Hierarchical Collision Detection and Bounding Volumes

In this paper we concentrate on hierarchical collision detection. This avoids checking every triangle of an object A for collision with all triangles of object B by hierarchically grouping triangles (or other graphical primi- tives). This yields a so-called bounding volume hierarchy (BVH), where each leave corresponds to one triangle and inner nodes correspond to groups of triangles. In order to achieve a feasible hardware design, we use a binary tree here, but n-ary trees could be considered as well. Each node of the tree stores a bounding volume (BV) that encloses all triangles in its group. Note that only leaves explicitely store any triangles.

Q Q D (Q) Q D (D (Q)) O d' i d i
In this work, we use k-DOPs as BVs because they were proven to yield very fast collision queries by extensive benchmarking in software [START_REF] Zachmann | Rapid collision detection by dynamically aligned DOP-trees[END_REF], and are likely to perform well in hardware.

If two objects are checked for intersection, both hierarchies are traversed starting at both roots. If their BVs intersect, then the next level of BVs is checked. Since two objects will usually intersect only locally in a very small number of primitives, this yields a significant speed-up in the average case. In practical cases, the complexity is in O(log n) (n = number of primitives) because only a small diagonal "slice" of constant width down the BVH needs to be visited.

k-DOPs

As motivated above, we use k-DOPs as BVs. A k-DOP consists of k distances d j along pairwise linearly independent vectors B j . Each of these vectors forms the normal of a halfspace. These vectors are chosen such that they form k/2 pairs, each of which defines a so-called slab [START_REF] Zachmann | Rapid collision detection by dynamically aligned DOP-trees[END_REF]. The intersection of these slabs forms the BV:

D = \ j=1,...,k H j , H j : B j x -d j ≤ 0 (1)
The orientation matrix B is fixed and equal for all objects. This yields a very space-efficient description for every k-DOP: only the k numbers d j need to be stored. To avoid rounding errors we use single-precision floating-point numbers. Assume O and Q to be two objects. Let D Q (Q) denote the minimum DOP which bounds Q with respect to the ori-

entation matrix B in Q's own reference frame F(Q). Since calculating D O (Q) is prohibitively expensive, we calculate D O (D Q (Q)), which is the minimum DOP in F(O) bound- ing D Q (Q).
Naturally, this incurs a loss of the BVs tightness to the underlying geometric structure.

Assume M to be the rotation and o the translation which transforms F(Q) into F(O). Then, we need to find distances

d i which bound M • D Q (Q) + o minimally.
Applying M and o to (1) yields

h j : b j x -d j + b j o ≤ 0, where b j = B j M -1 (2) Assume D O (D Q (Q)) is the intersection of H i : B i x -d i ≤ 0, i = 1,...,k (3)
Then, each d i corresponds to exactly one vertex of D Q (Q) and therefore to three d j (see Fig. 1). These correspondences are the same for all nodes in an object's DOP hierarchy. So they can be determined at startup. Let j l , 0 ≤ l ≤ 2, be the indices corresponding to

d i . Then,   b j 0 b j 1 b j 2   x -   d j 0 d j 1 d j 2   +   b j 0 b j 1 b j 2   o = 0 (4) b i x -d i = 0 (5)
Equating ( 4) and ( 5) yields

d i = C i j 1 d j 1 +C i j 2 d j 2 +C i j 3 d j 3 + c i ( 6
)
where C and c are chosen to be

C i j := B i b j 0 b j 1 b j 2 -1
and

c i := b i o.
Both are the same for all nodes in an object's DOP hierarchy; thus, they can be calculated at startup.

Checking D O (D Q (Q)) and D O (O)
for intersection amounts to projecting them on the k axes given by B. They overlap if and only if there is no axis on which they are non-intersecting. Since there are always two antiparallel axes, we need to take that into account (see Fig. 2).

If e denotes the k-vector describing D O (O), then this test can be expressed as

overlap ⇔ ∃i ∈ [1, k 2 ] : e i+ k 2 > -d i ∨ d i+ k 2 > -e i (7)

Triangle Intersection

Once the BVH traversal reaches two leaves, we need to test the enclosed triangles for intersection. Here, we utilize the same algorithm that was already proposed in [START_REF] Zachmann | An architecture for hierarchical collision detection[END_REF]. It transforms both triangles so that one of them becomes the "unit" triangle. That way, the checks to be performed on the other triangle become very simple and standardized.

For sake of reference, we just give one of the criteria for a non-intersection of one edge:

a < 0 ∨ b < 0 ∨ a + b > r z ( 8
)
where

a = P x Q z -Q x P z b = P y Q z -Q y P z (9)
with PQ being an edge of the triangle, and r = Q -P. The other criterion is very similar.

The Architecture

To achieve maximum possible speed we assume to be using high-end hardware components: our target ASIC technology is a NEC UX5 CB-130 in 0.095µm-coppertechnology. With a maximum of 61 gates in a row it can establish up to 800 MHz clockrate, which is our target frequency for the simulations (Sect. 5). Furthermore, we assume DDR2 memory modules.

As BVs we chose to use 24-DOPs because extensive software benchmarking has shown 24 axes to be a good compromise of tightness and effort.

Design of the DOP Intersection Test

Our DOP intersection test is the combination of criterion ( 7) with [START_REF] Hubbard | Collision detection for interactive graphics applications[END_REF], which amounts to the function [START_REF] Zachmann | Rapid collision detection by dynamically aligned DOP-trees[END_REF] This can be implemented as the following three-staged macro-pipeline, which we call DOPTRF unit (because it computes basically one row of the DOP transformation, i.e., Equation 6, plus part of the test, i.e., Equation 7): The macro-pipeline stages were refined furthermore resulting in a pipeline of 15 stages and therefore an initialization delay of 15 clock cycles.

d i = d k C i0 + d m C i1 + d n C i2 + c i + e i+ k 2
We use 24 DOPTRF units in parallel, and their results are NOR-reduced to check the criterion. To fill the pipeline we use a 756-bit wide bus from the DDR2-RAM. A hypermultiplexer (D KLMSEL) routes the correct inputs of the DOP to the DOPTRF units, which will then be transformed into the reference frame of the other DOP (see Fig. 3). A D CNTR unit controls which DOP pair will be processed next (see Section 4.3).

Design of the Triangle Intersection Test

Using homogeneous coordinates, the affine transformations needed for the triangle intersection test (see Section 3.3) can be represented as 3 × 4 matrices.

The T CHECK unit that performs the intersection test gets as input one triangle V i A = [x i y i z i 1] , 1 ≤ i ≤ 2, the precomputed matrix M B := [m i j ], and M AB := b i j that transforms O's reference frame into Q's.

Calculating V i A = M B × M AB ×V i
A is done in the first two of 5 macro pipeline stages. These will be detailed in the following.

b i j = {[(b i1 m 1 j ) + (b i2 m 2 j )] + (b i3 m 3 j )} (11) b i4 = {[(b i1 m 14 ) + (b i2 m 24 )] + [(b i3 m 34 ) + (b i4 )]} (12) i, j = 1,...,3
The forth row of the resulting matrix is always [001]. These substages are further divided into microstages to gain maximum clock frequency. With this refinement, the first macro stage consumes 36 multiplication and 24 addition floating point units and takes 15 clock cycles delay to produce the first result.

nd macro stage: Calculating

V i A = M b × V i
A works very similarly. The resulting substages are:

V i = {[(b i1 V i x ) + (b i2 V i y )] + [(b i3 V i z ) + (b i4 )]} (13)
Dividing this into microstages yields 27 multiplications, 27 additions, and another 15 clock cycles delay.

3 rd macro stage: Before checking the edges of T A for intersection with the unit triangle, we need to calculate a and b according to Eq. 9 for all three edges. Therefore, we need to calculate P x Q z , Q x P z , P y Q z , and Q y P z first. Additionally, we calculate r z . This takes 12 multiplications, 3 additions, and 8 clock cycles. Calculating a and b from these terms takes another 6 additions and 4 clock cycles.

4 th macro stage: For all three edges we now need to calculate a + br z . After division into microstages this consumes 6 additions and 8 cycles. Overall pipeline: Putting all stages together, we get a pipeline with 52 clock cycles delay.

To fill the pipeline with data we need to buffer the triangle addresses, look them up in the DDR2 RAM which contains vertex data and the transformation matrices, and divide the data into two sets (because all edges of T A have to be checked against T B and vice versa). The whole TRI UNIT is presented in Fig. 4.

Control

When the two object hierarchies are traversed symmetrically, each intersecting DOP pair results in 4 child pairs to be checked for intersection. However, other ways of traversing both BVHs can be more efficient. So far, we have compared those two possibilities that allow a small control unit and reduce the number of necessary memory accesses and transformations.

Traversing two BV hierarchies simultaneously and symmetrically basically amounts to traversing a 4-ary tree of BV pairs.

Let us denote the BVs in one tree by A, B, C, etc., and the BVs in the other tree by 1, 2, 3, etc.

Using a FIFO for determining the next DOP pair to be tested for intersection results in a plain breadth-first search on the collision tree. The processed DOP-sequence is

A1 -B2 B3 C2 C3 -D4 D5 E4 E5 -D6 D7 E6 E7 -F4 F5 G4 G5 -F6 F7 G6 G7
This can easily be optimized so that between testing two nodes of the same depth only one DOP needs to be fetched from memory. The resulting sequence is A1 -B2 B3 C3 C2 -D4 D5 E5 E4 -E6 E7 D7 D6 -F6 F7 G7 G6 -G4 G5 F5 F4 Using a LIFO the sequence depends on the length of the pipeline. If we assume the pipeline to be of length one (for simplicity of presentation) we receive a plain depth first search. A1 -B2 -D4 D5 E5 E4 -B3 -E6 E7 D7 D6 -C2 -G4 G5 F5 F4 -C3 -F6 F7 G7 G6

If we push and pop nodes pairwise, we can easily reduce the number of necessary memory accesses as we did before.

Note that our DOP transformation pipeline has 15 stages. Thus, the traversal is not plain depth-first in the strictest sense. Instead, it proceeds along several paths in a depthfirst manner.

Simulation Results

For benchmarking our architecture we used three different objects each of which in several polygon complexities (see Fig. 5). For each of them, two copies are placed at different distances from each other and with different rotations. For each constellation, the collision detection query time is determined. Comparing the performance of LIFO and FIFO control, we see that finding all intersecting primitives takes equally long (see Fig. 6a).

Since using a LIFO corresponds to depth-first search on the collision tree, finding the first collision is usually much faster than using a FIFO. Our simulation results verify this (see Fig. 6b).

Another disadvantage of using a breadth-first search is the size needed for the memory structure. In the worst case, when all nodes need to be checked for intersection we must store them all in the FIFO before any leaves are checked and the queue size reduces.

With a strict depth-first traversal, the LIFO would need to be only as large as the depth of the BVH. However, as explained in Section 4.3, our traversal is not strictly depthfirst. Fortunately, memory usage of the LIFO in our design seems to behave just as well (see Fig. 7).

Fig. 8 shows that our collision detection architecture, when implemented on a NEC CMOS ASIC (CB-130 UX5, 800 MHz), is up to 1000 times faster than the software implementation in determining all intersecting triangles of two objects. The software times were obtained on a 1GHz Pentium 3.

As mentioned above, a recent trend in computer graphics is to implement computationally intensive algorithms on the GPU. However, according to [START_REF] Gress | Object-space interference detection on programmable graphics hardware[END_REF] it seems that an implementation on the GPU cannot gain a significant speed-up over a pure CPU-based implementation. This is probably because the GPU is a streaming architecture.

Conclusion and Future Work

In this paper, we have presented, to our knowledge, the first simulation in VHDL of a hardware architecture for collision detection. We showed that hardware acceleration can be an effective way to speed up hierarchical collision detection. Using several pipelining and parallelization techniques, we achieved a speed-up of factor 1000 in VHDL simulations compared to a software implementation.

We also showed that, for simultaneous traversal of BVHs, a LIFO-controlled pipeline is far more space efficient than a FIFO-controlled one, without loss of processing speed.

Since the present paper is one of the first to look at hardware acceleration of collision detection, we believe there are many avenues for further research.

An important concern is the reduction of the bandwidth in order to make the bus from chip to memory smaller. Currently, we are investigating discretization and compression of the BVs. Furthermore, we will evaluate different kinds of primitives and BVs.

Another important issue is collision detection of deformable objects. It remains an open problem exactly which algorithms and data structures are best suited for hardware implementation.

Since we use a pipelined dataflow architecture, advanced pipelining techniques like speculative execution could be applied to reduce the number of pipeline stalls.

Figure 1 .

 1 Figure 1. Our DOP overlap test gains its speed by transforming DOP Q into O's reference frame F(O). The tightness loss is shown in dark grey. Obviously, each d is determined by exactly three original d's.

Figure 2 .

 2 Figure 2. Two objects overlap, iff their projections intersect on every axis. Each object O has its own reference frame (RF) F(O) that describes its rotation R O and translation T O with respect to world coordinates. When an object moves, only R O and T O have to be updated. So checking two DOPs for intersection requires transformation of one of them into the RF of the other.Assume O and Q to be two objects. Let D Q (Q) denote the minimum DOP which bounds Q with respect to the orientation matrix B in Q's own reference frameF(Q). Since calculating D O (Q) is prohibitively expensive, we calculate D O (D Q (Q)), which is the minimum DOP in F(O) bounding D Q (Q).Naturally, this incurs a loss of the BVs tightness to the underlying geometric structure.Assume M to be the rotation and o the translation which transforms F(Q) into F(O). Then, we need to find distancesd i which bound M • D Q (Q) + o minimally.Applying M and o to (1) yields

Figure 3 .

 3 Figure 3. Architecture for DOP intersection testing.

Figure 4 .

 4 Figure 4. Architecture for Triangle Intersection 1 st macro stage: The calculation of M b = b i j = M B ×M AB is split into three substages (marked with different brackets):

Figure 5 .

 5 Figure 5. For benchmarking and testing, a number of different test objects with several polygon complexities were used. 5 th macro stage: Here, we check the signs of a, b, and a + br z for all edges. This needs one clock cycle.

Figure 6 .

 6 Figure 6. Top: Comparing LIFO and FIFO controlled intersection testing shows that finding all intersecting primitives takes equally long. Bottom: Our comparison shows that LIFO control is far superior to FIFO control when finding the first intersecting primitive.

Figure 7 .

 7 Figure 7. Although our hardware architecture implements a traversal scheme (LIFO') that is not quite a LIFO, it uses still only very few memory, compared to a FIFO.

Figure 8 .

 8 Figure 8. Comparison of software with hardware implementation at various distances and polygon complexities. Our collision detection architecture is up to 1000 times faster in determining all intersecting triangles of two objects than the software implementation running on a 1GHz Pentium 3.

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)