Christian Benkeser
email: benkeser@iis.ee.ethz.ch

Qiuting Huang
email: huang@iis.ee.ethz.ch

Design and Optimization of a Digital Baseband Receiver ASIC for GSM/EDGE

Keywords: Christian Benkeser, Qiuting Mobile communication, GSM, EDGE, baseband, pre-filter, Levinson, equalizer, DFSE, Viterbi decoder, low-power, ASIC, VLSI

Introduction

Cellular wireless communications has changed our lives in the past 20 years. Today, with 3.5 billion subscribers [START_REF]GSM Association, Market Data[END_REF] the far most important cellular communication system GSM is used by all sorts of people all around the world. Simple 2G data communication is possible with the standard extension GPRS, but good user experience during wireless web-browsing and other non-voice applications can only be achieved since 2.5G EDGE data-services have been introduced.

EDGE increases 2G peak data rates to 240 kbps, mainly due to a higher modulation order (8PSK) and stronger channel coding. The symbol rate of 270 kbps is identical with basic GSM, but 8PSK modulation improves the spectral efficiency, which comes at the cost of receiver complexity. Especially channel equalization and symbol demodulation is a challenging task in EDGE, and requires sophisticated low-complexity solutions to preserve the power-advantage and cost-advantage of 2G receivers. Although basic GSM can be implemented on advanced signal processors with tolerable power-levels today, EDGE requires efficient ASIC accelerators to reduce the power consumption to the required level in modern cellular phones.

In basic GSM with GMSK modulation typically the (optimum) Maximum-Likelihood Sequence-Estimator (MLSE) is used for channel equalization and demodulation. The complexity of an MLSE algorithm for 8PSK signals, however, would even exceed what can be implemented on ASICs. Therefore, in recent years a lot of work on channel equalization for EDGE has been performed. It has been shown that sub-optimum variants of the MLSE algorithm with acceptable computational complexity, like reduced-state sequence estimation [START_REF] Eyuboglu | Reduced-state sequence estimation with set partitioning and decision feedback[END_REF] or decision-feedback sequence estimation [START_REF] Duel-Hallen | Delayed decision-feedback sequence estimation[END_REF], are suitable for channel equalization of 8PSK modulated EDGE signals (e.g., [START_REF] Olivier | Efficient equalization and symbol detection for 8-PSK EDGE cellular system[END_REF][START_REF] Gerstacker | Equalization concepts for EDGE[END_REF]). Turbo equalization has also been discussed [START_REF] Szczecinski | Is turbo equalization useful in EDGE systems?[END_REF] and proposed as a solution for EDGE [START_REF] Laot | Low-complexity MMSE turbo equalization: a possible solution for EDGE[END_REF]. However, all these explorations are simulation-based system analyses where implementation aspects and crucial design metrics like power consumption are not considered. Further, a practical multi-mode solution supporting GMSK as well as 8PSK modulation has not been treated so far.

This work describes the design of a low-power and low-cost digital baseband receiver for GSM/GPRS/EDGE with focus on the most challenging block, the channel equalization. The entire receiver chain has been mapped to dedicated hardware in order to achieve best design metrics. Hardware realizations for key components of the receiver ASIC realization have been optimized to provide the flexibility required for the specified modulation types and coding schemes. Costly hardware resources are shared to keep the silicon area low, and algorithmic/architectural optimizations have been applied to achieve very low power consumption.

Outline

The paper is organized as follows. In Section 2 the GSM baseband transmitter and channel model are introduced. In Section 3 the high-level architecture of the receiver ASIC realized in this work is presented. Section 4 describes the implemented channel equalizer solution in detail. In Section 5 the implemented channel decoder solution is explained together with an analysis of the impact of hard-/soft-decision equalizer outputs on receiver implementation complexity. Measurement results and key figures of the receiver ASIC implementation are presented in Section 6. The paper is concluded in Section 7. encoder (rate 1/2 for GSM/GPRS or rate 1/3 for the coding schemes specified for EDGE). Then, selected bits are removed in the puncturing unit to adjust the code rate as required for the specific transmission mode. After that, the order of bits is scrambled in the block interleaver to distribute radio blocks of up to 1184 bits across 4 or 8 bursts3 . The resulting bits (information bits) are mapped in interleaved order on bursts with a length of 156.25 symbols (3 bits per symbol in 8PSK mode), which includes fixed tail bits for channel equalization, a fixed training sequence (TS) for channel estimation and a guard period 4 as shown in Fig. 2. Finally, in the symbol mapper and pulse shaping filter the bursts are GMSK or 8PSK modulated with a symbol period of T s = 3.69 µs as specified [START_REF]3rd Generation Partnership Project; Technical Specification Group GSM/EDGE Radio Access Network; Modulation[END_REF]. Typically the bursts are transmitted every 8 time slots as indicated in Fig. 2 according to the time division multiple access scheme defined for GSM, and the remaining 7 slots are reserved for other users. However, several slots can be reserved for data traffic of a single user in high-speed EDGE data transmission modes. The bursts are submitted through a multipath communication channel with additive white Gaussian noise (AWGN). The GSM test channel profiles [START_REF]Generation Partnership Project; Technical Specification Group GSM/EDGE Radio Access Network[END_REF] have a delay spread of up to 5 T s , causing considerable inter symbol interference (ISI). Even more ISI is introduced by the system itself, because the GSM channel bandwidth of 200 kHz is significantly lower than the symbol rate. Therefore, an overall communication channel with a delay spread of up to 8 T s has to be considered when removing ISI in the receiver with the channel equalizer.

System Overview

Digital Baseband Receiver

The complete receive chain shown in Fig. 1 has been implemented in our ASIC. As indicated in the corresponding simplified block-diagram (Fig. 3) two 2.5 kb RAMs allow the buffering of up to 2 GSM bursts, each comprising the in-phase and quadrature-phase component of 156 symbols. Each time a new GSM burst has been received the channel impulse response (CIR) is estimated with the training sequence by using the Least Squares technique [START_REF] Proakis | Digital Communications[END_REF]. The ISI of unknown data symbols adjacent to the training sequence causes estimation errors when considering all 26 symbols of TS. In our implementation only the central 16 symbols of TS are used to estimate the CIR. Since linear 8PSK modulation can be realized with simple FIR filtering in the transmitter, the CIR of the overall communication channel including the pulse shaping filter can be estimated at the receiver (cf., Fig. 1). In (non-linear) GMSK instead, the signal is modulated indirectly by filtering and accumulating the phase. Hence, the transmitter pulse shaping cannot simply be included in the estimated CIR. Channel equalization and demodulation are performed in our receiver implementation with the combination of a minimum-phase FIR pre-filter and a Decision-Feedback Sequence Estimator (DFSE) which are explained in detail in Section 4. The pre-filter coefficients computed with the estimated CIR are buffered to be used to filter the CIR and the stream of received samples. These are fed into the DFSE for channel equalization and demodulation.

High-speed EDGE transmission modes require continuous burst reception, because more than one burst can be allocated to a specific user in each time frame. Therefore, the demodulation of each burst has to be finished in one burst period of T b = 577 µs. When a radio block (4 or 8 bursts) has been demodulated, the de-interleaver can begin to reorder the bits. Both, burst and block de-interleaving are performed by generating the specific RAM addresses for writing to and reading from the de-interleaver memory. The de-puncturing unit introduces zeros (no a-priori information on the demodulated symbol) into the data stream to provide data blocks to the channel decoder with the correct code rate. A flexible Viterbi decoder for trellises with up to 64 states has been implemented to support 15 specified coding schemes. The channel decoder processes all branches in parallel to keep the receiver latency low.

A Combined Pre-filter and DFSE Solution

In an MLSE, as can be used for optimum equalization in GSM, all possible symbol combinations of length L that could have been transmitted are generated as reference symbol sequences. These sequences are modulated and convolved with the CIR to emulate the effect of ISI. The resulting reference signals are compared with the received samples to generate branch metrics which are a measure for the likelihood that the specific symbol sequence has been transmitted, given the received signal. The branch metrics are used by the Viterbi algorithm in a trellis diagram to find the most probable transmitted symbols. Contrary to implementations of Viterbi decoders, the branch metric generation is the most challenging part in an MLSE. The computational complexity can be characterized with the number of trellis branches B = M L to be processed, where M denotes the modulation order (alphabet size) with M = 1 for GMSK and M = 3 for 8PSK. The length of the reference symbol sequences L defines the maximum tap delay (delay spread) in the channel profile that is considered in the equalization. The storage requirements are defined by the number of states in each trellis stage according to S = M L-1 . When considering the impact of 7 previously transmitted symbols, i.e. L = 8, as required for GSM (cf., Section 2), the MLSE trellis is large in the GMSK case, and even beyond what can be realized with any hardware platform when processing 8PSK signals.

Contrary to the MLSE algorithm, in the DFSE not all possible symbol combinations of the reference sequence are used for the comparison with the received samples. Decisions of the Viterbi algorithm on previous symbols, so-called per-survivor estimates, are taken as fixed assumptions to reduce the number of branch metrics to be computed. Only the permutations of the first D symbols are considered as separate state transitions in the trellis, which reduces the number of branches to be processed to B = M D and the required number of trellis states to S = M D-1 . Therefore, the taps of the CIR which correspond to these first D symbols have greatest impact on the equalizer performance. In channels with strong delayed taps and comparably weak main taps, correct symbol demodulation can be difficult or even impossible for the DFSE algorithm. Therefore, minimum-phase pre-filtering is required to transform such channels into channels better suited for the DFSE. Such a pre-filter concentrates the energy of the channel taps in the front, in order to maximize the impact of the first D symbols during equalization, thus improving the DFSE performance (cf., Fig. 4). Simulations have shown that, depending on the channel profile, varying D from 2 to 4 brings a maximum performance gain of 1.6 dB in terms of SNR required to achieve an uncoded DFSE bit error-rate (BER) of 10 -3 with both GMSK and 8PSK modulated signals. The simulation results for the specified Hilly Terrain (HT) channel [START_REF]Generation Partnership Project; Technical Specification Group GSM/EDGE Radio Access Network[END_REF] profile for different DFSE configurations with pre-filtering are shown in Fig. 5. As can be seen increasing D from 2 to 4 improves the performance in this case by only 0.9 dB and 0.6 dB for GMSK and 8PSK modulated signals respectively. Almost optimum (MLSE) performance can be achieved with D = 4. Further increasing of D introduces additional complexity without a noticeable performance gain.

Instead, the impact of the pre-filter can be dramatic. The uncoded BER of demodulated 8PSK signals, impaired by the HT channel are shown in Fig. 6. Different filter orders p for the pre-filter in front of a DFSE with D = 2 have been simulated. As can be seen, without pre-filtering the symbol sequence cannot be equalized with a DFSE properly. A pre-filter order p of only 16 causes the curves to saturate at a BER≥ 10 -3 , whereas the BER does not improve significantly with increasing the filter order beyond 32.

The most critical parts of our GSM/EDGE channel equalizer solution, i.e., the matrix inversion for the pre-filter coefficients computation and the DFSE realization, are described in detail in the following.

Pre-filter Implementation

A suitable pre-filter transforms the CIR to its minimum-phase equivalent, where the energy of the first filter taps is maximum compared to the impulse response of all other causal and stable filters with the same magnitude response [START_REF] Schmidt | Fractionally-spaced prefiltering for reduced state equalization[END_REF][START_REF] Smith | Introduction to Digital Filters: with Audio Applications[END_REF]. Such pre-filtering can be realized with a hardware-friendly FIR filter, however, the computation of the corresponding pre-filter coefficients is costly. Hence, a thorough complexity analysis of techniques for the generation of these filter coefficients is required.

In order to be able to make a fair comparison between algorithms, we have implemented the Linear Prediction (LP) method [START_REF] Gerstacker | On prefilter computation for reduced-state equalization[END_REF] and performed floatingpoint simulations for a filter order of p = 32 with our framework. Then, the MMSE-DFE [START_REF] Schmidt | Fractionally-spaced prefiltering for reduced state equalization[END_REF] and cepstrum method [START_REF] Oppenheim | Digital Signal Processing[END_REF] (recently proposed for GSM/EDGE in [START_REF] Detert | Prefiltered low complexity tree detection for frequency selective fading channels[END_REF]) have been implemented, and the parameters have been optimized, such that these algorithms provide the same BER performance at certain SNR points as the simulations with the LP method. It has been shown, that the cepstrum (MMSE-DFE) method requires p = 32 and p = 24 (p = 32 and p = 20) at SNR points corresponding to an uncoded BER of 1% and 0.1% respectively. In Fig. 7 the complexity of the different algorithms in terms of number of complex-valued multiplications and additions is compared 5 . The complexity has been evaluated at different BER operating points, because the MMSE-DFE method shows slightly better performance in low SNR regimes when compared to the LP and cepstrum approach. As can be seen, the computation of the prefilter coefficients via LP is significantly less complex than using MMSE-DFE or the cepstrum method.

Consequently, in our digital baseband receiver ASIC we have implemented a pre-filter with filter coefficients computation based on LP, which will be depicted shortly in the following (a detailed description can be found in [START_REF] Gerstacker | On prefilter computation for reduced-state equalization[END_REF]). We denote the discrete time received baseband signal as follows:

r[n] = L k=1 h[k] • s[n -k] + w[n] (1)
where h[n] denotes the complex baseband response of the overall channel with delay spread L (cf., Section 3), s[n] the GMSK or 8PSK modulated transmitted symbols, and w[n] complex additive white Gaussian noise (AWGN). H(z) denotes the transfer function that corresponds to the channel:

H(z) = L k=1 h[k] • z -k . (2)
Ideally, a discrete-time pre-filter A(z) transforms H(z) to its minimum-phase equivalent H min (z) according to

H min (z) = A(z) • H(z), (3)
with all-pass characteristic

|A(z)| = 1. (4)
Due to (4) the transfer function A(z) of the desired pre-filter can be written as a cascade of two filters according to

A(z) = H * (1/z * ) A M F • 1 H * min (1/z * ) A W F . (5)
A M F is a matched filter, matched to the channel h[n], where the filter coefficients are simply the complex-conjugated and time-reversed impulse response taps. Unfortunately, obtaining the filter coefficients of the whitening6 filter A W F (z) is a much more complex task that requires a costly matrix inversion.

Computation of filter coefficients with LP A linear predictor is based on the assumption that samples of a sequence can be (approximately) written as a linear combination of past samples. The linear prediction filter P (z) used to compute the filter coefficients of A W F (z) is defined as

ĥ[n] = p i=1 a i • h[n -i], (6)
with the linear predictor coefficients a i and the filter order p. The predictionerror can be computed according to

e[n] = h[n] -ĥ[n]. (7)
The filter coefficients are obtained by minimizing the mean-squared prediction error which leads to the normal equations or Yule-Walker equations [START_REF] Chu | Speech coding algorithms : foundation and evolution of standardized coders[END_REF][START_REF] Makhoul | Linear prediction: A tutorial review[END_REF]:

Φa a a = ϕ ϕ ϕ
Φ =      ϕ 0 ϕ -1 • • • ϕ -(p-1) ϕ 1 ϕ 0 • • • ϕ -(p-2) . . . . . . . . . ϕ p-1 ϕ p-2 • • • ϕ 0      (8)
with

ϕ ϕ ϕ = ϕ 1 ϕ 2 • • • ϕ p T
The coefficients ϕ k are given by the autocorrelation function (ACF) of h[n] according to

ϕ k = h[k] * h * [-k].
As can be seen in Fig. 8 the prediction-error filter F (z) that corresponds to the linear predictor P (z) is given by ĥ

[n] h[n] e[n]
Linear predictor Prediction-error filter

F (z) = 1 -P (z) p i = 1 P (z) = a i • z -i
Fig. 8. Block diagram of prediction-error filter used for the pre-filter coefficients computation in the LP approach.

F (z) = 1 -P (z) (9)
The generation of the A W F filter coefficients exploits the fact that such prediction-error filters are always minimum phase [START_REF] Chu | Speech coding algorithms : foundation and evolution of standardized coders[END_REF]. It has been shown in [START_REF] Gerstacker | On prefilter computation for reduced-state equalization[END_REF], that

A W F (z) = F * (1/z * ) (10)
is valid for an infinite filter order p → ∞ and that

A W F (z) ≈ F * (1/z * ) (11)
is a good approximation for high filter orders p.

Matrix Inversion

In a pre-filter implementation with LP the far most complex part is the inversion of the complex-valued p × p Toeplitz matrix (8) required to generate the prefilter coefficients. In our digital baseband receiver ASIC a pre-filter with order p = 32 has been implemented to guarantee high DFSE performance, even when the received signals have been impaired by channels with strong delayed taps.

The required inversion of a 32×32 matrix with an internal precision of 2×20 bits has been implemented in our design by excessively applying time-multiplexing and resource sharing to curtail silicon area. To this end, the recursive Levinson-Durbin (LD) algorithm shown in Alg. 1 is used. Its recursive nature is highly suitable for sequential implementations and the computational complexity is close to optimum matrix inversion algorithms for Toeplitz matrices [START_REF] Golub | Matrix computations[END_REF].

To improve the efficiency of an implementation of the LD recursion, the algorithm has been modified as follows:

-Initialization of the (real) scaling factor

E E = ϕ0 (12)
-Recursive generation of the (complex) coefficients ai by looping over

1 ≤ i ≤ p • Computation of the unscaled a a = - " ϕi + i-1 X j=i aj • ϕi-j # (13)
• Scaling with E to generate the new ai

ai = a E (14)
• Updating aj by looping over 1 ≤ j ≤ i -1

aj = aj + ai • a * i-j (15)
• Generation of the new scaling factor

E = (1 -|ai| 2 )E (16)
-The LP filter coefficients of P(z) are given by ai with 1 ≤ i ≤ p Alg. 1. LD recursion for complex coefficients.

-The initialization in equation ( 12) has been replaced with

E inv = 1 ϕ 0
-The scaling of a in equation ( 14) has been replaced with

a i = a • E inv
-The generation of the new scaling factor in equation ( 16) has been replaced with

E inv = E inv (1 -|a i | 2 )
Working with the inverse of the scaling factor E inv = 1 /E can be exploited to process the algorithm more efficiently in hardware (cf., the block diagram of the LD algorithm implementation in our receiver ASIC in Fig. 9): the division of the complex-valued a in ( 14) is replaced by a multiplication, and the multiplication in ( 16) is replaced with a real-valued division. Thus, one costly real-valued division is saved in each iteration of the LD recursion. Further, the division now has to be performed for the generation of the new (inverse) scaling factor, and therefore can be performed mostly in parallel to updating a j . It can be realized with a low-complexity sequential divider without stalling the LD recursion loop for many clock cycles. The sequential divider implementation in our design takes 9 clock cycles per division and requires only 1.7 k gate equivalents (kGE). It significantly reduces the logic depth of the costly divide operation such that timing closure of our receiver ASIC is not affected. In our design the matrix inversion of the complex-valued 32 × 32 matrix takes 2630 clock cycles.

f 1 2 f 2 2 f 1 3 f 2 3 g 3 g 2 compute a i compute a' RAM f 1 1 f 2 1 g 1 update a 1..i-1 RAM |x| 2 =x 2 re +x 2 im s 1 1 s 2 1 s 1 2 s 2 2 t 2 t 1 n d n d real DIV initial shared complex MULT g i f 2 1 f 2 2 f 2 3 autocorrelation of CIR 1 E generate 1 E 18b 2x20b 2x20b s 2 1 s 2 2 f 2 1 f 2 2 f 2 3
Costly hardware resources like multipliers, register arrays and RAMs, used in the LD recursion implementation, are also shared with other units of the prefilter block. As in the implementation of the LD recursion, the sequential data flow in the pre-filter coefficients computation allows time-multiplexing of costly hardware resources. Thus, the total pre-filter coefficients computation together with the actual FIR pre-filtering requires only 32 kGE and 2.5 kb memory. The total pre-filter coefficients computation takes less than 3000 clock cycles, and the FIR pre-filter of the received burst provides one filtered symbol per 16 clock cycles to the DFSE.

DFSE Design for GMSK and 8PSK

To support processing both GMSK and 8PSK modulated signals with little overhead, our implementation of the DFSE algorithm always operates on the same number of trellis states. In GMSK mode 8 states allow D = 4 symbols to be considered in building the trellis, such that near MLSE performance can be achieved. In 8PSK mode with D = 2 the high-order pre-filter allows for good performance without having to introduce additional trellis states as previously shown. The binary alphabet in GMSK requires only 2 branches per trellis state to be processed, whereas 8PSK has 8 branches in the trellis going to each trellis state, which leads to a 4x higher computational complexity. The symbols of the training sequence do not have to be demodulated since they are known at the receiver 7 . Therefore, computations can be saved by simply skipping the received symbols that correspond to the training sequence. Our DFSE implementation builds two separate sub-trellises per burst: one trellis for the first 58 information symbols, using TB1 and the first symbols of TS as tail bits, and one trellis for the second 58 information symbols, using the last symbols of TS and TB2 as tail bits (cf., Fig. 2). Consequently, tail bits for both sub-trellises are known in the DFSE, which enables reliable demodulation of the information symbols with 20% less symbols to be processed. Fig. 10 shows the block-diagram of the implemented DFSE algorithm. To enable the equalization of all specified channel profiles, channel taps with a maximum delay of L = 8 symbol periods are considered in our DFSE implementation (cf., Section 2). Therefore, the reference symbol sequences have a length of 8 symbols, and the (pre-filtered) CIR fed into the DFSE block consists of 8 symbol-spaced taps.

To modulate the symbols each reference sequence (one for each trellis branch) is fed into a look-up table (LUT) to generate the corresponding constellation points. In GMSK mode all 2 L = 256 possible constellation points which arise from ISI due to the pulse shaping filter have to be stored. In 8PSK mode, where the estimated CIR also comprises transmitter pulse shaping, only 2 × 8 different constellation points have to be stored 8 . With a precision of 6 bit and 8 bit for the GMSK and 8PSK constellation points respectively, the LUT can be reduced to only 0.8 kb by exploiting symmetries.

The vector product of the modulated reference symbol sequence with the pre-filtered CIR, both complex-valued and with a length of 8, is by far the most computation-intensive part in a DFSE implementation: 8 multiplications and 7 additions are required for each trellis branch, leading to high implementation complexity. To keep the silicon area low we have time-multiplexed the vector product implementation for 4 symbols with 4 channel taps, thus spending 2 clock cycles for the generation of each reference signal.

In GMSK mode, after the convolution with the channel a phase rotation of π /2 introduced in the transmitter modulator [START_REF]3rd Generation Partnership Project; Technical Specification Group GSM/EDGE Radio Access Network; Modulation[END_REF] is compensated for 9 . Finally, the trellis branch metrics typically are computed by building the Euclidean ( 2 -) distance

d 2 = (x I -y I ) 2 + (x Q -y Q ) 2 (17)
7 In our prototype ASIC implementation the training sequence code (TSC) #1 has been used. The specifications allow the base station to choose among 8 different TSCs with similar autocorrelation properties. 8 16 instead of 8 constellation points have to be considered, because a phase rotation of 3π /8 between subsequent transmitted symbols is specified [START_REF]3rd Generation Partnership Project; Technical Specification Group GSM/EDGE Radio Access Network; Modulation[END_REF]. 9 The sign of the GMSK phase rotation depends on the symbol to be transmitted.

However, it can be shown that due to differential encoding on the transmitter side, the received symbols can be de-rotated for the comparison in the Viterbi equalizer without having to consider previous symbols.

between the reference signal and the received sample. To avoid costly square operations in this time critical path in our implementation we generate the 1distance

d 1 = |x I -y I | + |x Q -y Q | (18)
as an approximation. In terms of SNR the performance degradation with this sub-optimal solution is less than 0.5 dB in GMSK and within 1 dB in 8PSK mode [START_REF] Benkeser | Power Efficiency and the Mapping of Communication Algorithms into VLSI[END_REF].

Each branch metric is added to the state metric of the state from which the specific branch is originating. The smallest metric incident on each state is selected and stored in the state metric memory, which is double-buffered with 2 RAMs to avoid that the old state metrics are overwritten. The decision on the winner branch is stored in the winner path and the estimates RAMs (cf., Fig. 10). To avoid access problems two estimates RAM instantiations are required for the storage of the last 8 -D per-survivor estimates for each of the 8 trellis states. The winner path RAM stores all decisions in the trellis to find the most likely symbol sequence during final back-tracing.

The total DFSE implementation requires only 18 kGE and less than 2 kb memory. The demodulation of one GMSK burst takes 6228 clock cycles, and processing an 8PSK modulated burst requires 17360 cycles. When taking into account the time required to generate the pre-filter coefficients plus 128 cycles for the channel estimation, burst-wise operation of the fastest EDGE transmission modes is possible with a system clock frequency of only 40 MHz.

Complexity of Combined Pre-filter and DFSE

The pre-filter block is almost twice as complex in terms of silicon area as the DFSE, and occupies one third of the logic cells of the total digital receiver. As previously shown, proper pre-filtering is essential to achieve high DFSE performance, especially when reducing the number of trellis states with D < 4. Although, the significant complexity of the pre-filter block gives rise to the question, if a pre-filter with a lower order and a DFSE with more trellis states would achieve a similar performance at a reduced total equalizer implementation complexity.

Lowering the filter order p reduces the filter's ability to compute the optimum minimum-phase equivalent of the CIR. The lower the filter order the more energy will be (in average) in the delayed taps of the filtered CIR. Further, the allpass characteristic of the pre-filter (cf., equation 4) deteriorates for small p. Such sub-optimum pre-filtering causes higher error rates after DFSE equalization and demodulation as shown in Fig. 6. Increasing the number of trellis states processed in the DFSE can (partially) compensate for this performance loss. But increasing the number of channel taps considered in building the trellis for example from D = 2 to D = 3 increases the number of branches to be processed by a factor of 8 in 8PSK modulation. Hence, the processing delay would increase by more than 120 k cycles with our architecture. On the other hand, with the highly sequential and resource-saving architecture of the proposed low-complexity pre-filter implementation, going down from a pre-filter order of 32 to for example 10 16 would save less than 2 k cycles. Furthermore, the silicon area of the pre-filter cannot be reduced significantly when lowering the filter order, because hardware resources have already been extensively re-used in the proposed architecture. Concluding, the implementation of a pre-filter with a high filter order pays off because it allows for excellent BER performance at a significantly reduced implementation complexity of the DFSE equalizer.

Hard-Decision Receiver Back-End Realization

The TDMA-based architecture of GSM/EDGE foresees burst-wise processing in the receiver: to save power only the signal streams on time slots with data dedicated for the specific user are equalized and demodulated. However, after the de-mapping of the bursts, de-interleaving, de-puncturing and channel decoding is required on a radio block basis, because block-interleaving is performed over 4 or 8 bursts in the transmitter signal processing chain (cf., Section 2).

In GSM/GPRS radio blocks of up to 456 bits contain one radio link control (RLC) block of information bits and in specific transmission modes (CS2-4) a short sequence called uplink state flag (USF) 11 . The coding scheme used for the information bits can be determined on the receiver side by checking the demodulated stealing flag bits on either side of the training sequence (cf., Fig. 2). In EDGE the radio blocks comprise the USF sequence, one or two (separately encoded) RLC blocks of information bits, and an RLC/MAC header part. To ensure strong header protection the header is encoded, interleaved and punctured independently from the information bits [START_REF] Seurre | EDGE for Mobile Internet[END_REF]. In EDGE the stealing flags indicate the coding used for the header, and the header itself provides control information, e.g. the modulation and coding scheme (MCS1-9) used for the coding of the information bits and an RLC block identifier. This block identifier is used by the incremental redundancy (IR) management on higher layers to determine if the received RLC blocks are a re-transmission of previously transmitted RLC blocks which have not been correctly decoded. IR uses different puncturing schemes for the re-transmission of RLC blocks, such that they can be combined with the previously received and stored blocks to increase the chance of correct decoding.

In the following de-mapping, block de-interleaving, de-puncturing and channel decoding as implemented in our receiver ASIC are described, highlighting the enormous complexity reduction that can be achieved by generating harddecisions (instead of soft-decisions) in the DFSE equalizer implementation.

De-mapping, de-interleaving and de-puncturing

The implemented DFSE equalizer demodulates the received data stream and generates hard-decisions for each transmitted information symbol. Due to the nature of the Viterbi algorithm [START_REF] Viterbi | Error bounds for convolutional codes and an asymptotically optimum decoding algorithm[END_REF] the DFSE provides the demodulated symbols d k with k = 0..115 for each sub-trellis corresponding to 58 information symbols i in inverse order, more specifically

d k = i sub1 58 , i sub1 57 , .., i sub1 1 , i sub2 58 , i sub2 57 , .., i sub2 1 . (19)
The symbols are de-mapped to actual bits and written into the de-interleaver memory. Burst de-interleaving is a simple task and can be performed by applying the specific memory write addresses. When a radio block of 4 or 8 bursts has been buffered in the de-interleaver memory block de-interleaving can begin.

The rules for the generation of the interleaved bit order (as defined for block interleaving on the transmitter side) seem to be complex and not suitable for an integration in hardware. Modulo and integer divisions are used in the specifications to compute the interleaved addresses, e.g., for MCS-9 the standard specifies the interleaving according to

Π(k) = 306(k mod 4)+3 44k mod 102+ k 4 mod 2 + k+2- k 408 mod 3 (20)
with k = 0..1223, such that each encoded bit of a radio block that was not punctured is interleaved to the address Π(k). Obtaining the de-interleaved address Π -1 (k) for a specific bit position k is even more complex and difficult to realize. However, when generating the interleaved addresses in ascending order, i.e., k = 0, 1, 2, .., complex modulo and division operations can be replaced by simple add-compare-select stages and counters (an example for such a simplified implementation is illustrated in Fig. 11 for a modulo and for a divide operation of ( 20)). Therefore, the de-interleaving can be performed most efficiently by applying the interleaved positions (generated in ascending order) as read addresses to the de-interleaver memory and writing the corresponding data items to the channel decoder input memory in natural order. With de-/puncturing the situation is similar: generating the bit positions which have to be punctured can be implemented efficiently with counters, whereas the inverse operation of determining if a specific address has been punctured is a complex task.

In order to minimize implementation complexity in our ASIC design, we apply the write addresses to the decoder input memory in natural (ascending) order and perform the de-puncturing and de-interleaving in a combined step:

-Initialization of the de-interleaver counter to q = 0.

-For all k = 0, 1, 2, .. in ascending order check if the kth bit has been punctured in the transmitter.

• If 'yes', write a zero (no a-priori information available for channel decoding) to the kth position of the channel decoder input memory. • If 'no', generate Π(q) to read the corresponding data item from the deinterleaver memory: write +1 for a stored logic '0' and -1 for a stored logic '1' to the kth position of the decoder memory, and increment the de-interleaver counter q by one.

It may seem a waste of hardware resources that memory space is provided for the zeros corresponding to the punctured bits. The de-puncturing could also be performed when reading the bits from the channel decoder input memory into the channel decoder. However, the memory space for the punctured bits is required because the received radio block could be a re-transmission initiated by the IR management. In this case, the received information and the information of the previously received and stored blocks has to be combined and written into the channel decoder input memory to be used by the channel decoder. Therefore, the capacity of the channel decoder input memory is defined by the maximum (encoded) RLC block size before puncturing.

Flexible Hard-Decision Viterbi Decoder

Channel coding for the different transmission modes in GSM, GPRS and EDGE is all based on convolutional encoding. However, the coding schemes differ in code rate r, constraint length c, decoder block size B, and trellis termination with tail bits [START_REF]3rd Generation Partnership Project; Technical Specification Group GSM/EDGE Radio Access Network; Channel Coding[END_REF]:

-The convolutional code for basic GSM and GPRS transmission modes has a code rate of r = 1/2 and a constraint length of c = 5. Block sizes vary from less than 100 up to 338. -The RLC blocks in the EDGE modes are encoded with a r = 1/3 convolutional code with c = 7. Block sizes vary from less than 200 up to 612.

-To reduce the coding overhead in the relatively short header sequences of the EDGE modes, the headers are encoded with tail-biting codes [START_REF] Ma | On tail biting convolutional codes[END_REF][START_REF] Biglieri | Coding for wireless channels[END_REF]. Here, no tail bits indicating the initial and final state of the convolutional encoder are transmitted. Instead, only the fact that the initial and final state of the tail-biting convolutional encoder are identical can be used by the decoder to find the most probable sequence.

In order to maximize the utilization of hardware resources, a single flexible Viterbi decoder solution is favorable over separate channel decoder implementations for the different requirements. Such a flexible Viterbi decoder has to support up to 64 trellis-states (c = 7) by taking into consideration up to 3 encoded input data items to compute the branch metrics (r = 1/3). Further, standard trellis-termination has to be supported as well as uninitialized trellis processing for the tail-biting codes. Finally, the channel decoder input memory has to be capable of storing up to 3 • 612 = 1836 data items.

We have implemented a fully-parallel 64-state sliding-window Viterbi decoder which supports the trellis structures required for GSM/GPRS and for EDGE. The data blocks are processed in windows of W=32 with an acquisition length of A=32 to reduce the memory requirements of the decoder (more details on Viterbi decoder design can be found, e.g., in [START_REF] Truong | A VLSI design for a trace-back Viterbi decoder[END_REF]). In transmission modes that use convolutional codes with c < 7 only the required hardware resources are activated in order to save power. Although all trellis states that correspond to a bit to be decoded are processed in parallel, the complexity of the Viterbi decoder is comparably small. Since hard-decisions are demodulated in our receiver ASIC, the channel decoder inputs can be represented with only 2 bits which keeps the numeric range of the state metrics small 12 . The branch metric computation can be realized very efficiently when taking into consideration that the 2 bit inputs i ∈ {-1, 0, 1} the (ideal) encoder output corresponding to the trellis state e ∈ {-1, 1} the resulting difference is |i -e| ∈ {0, 1, 2}.

As can be seen in the block diagram of our Viterbi decoder implementation in Fig. 12, calculating the distance between decoder inputs and state-specific encoder outputs can be realized with only two logic gates. Depending on the code rate r, two or three units to compute the distance are enabled in each of the 128 branch metric computation units (BMUs) for the generation of the branch metrics b. The complexity of the state metric recursions can be kept low as well because the metric increase in each trellis stage is limited to

∆m max = c max • max |i -e| = 6. (21)
Therefore, in our implementation with W=32 the state metrics m can be realized with only 8 bit without the need for normalization circuits. The initialization of the state metrics m 0 is configurable in our implementation to allow for path memory Convolutional encoder polynome look-up table uninitialized decoder runs in order to find the most probable start-and end-state of the trellis in tail-biting mode. Then, these are used in a second decoder run to decode the (header) bit sequence (details on decoding tail-biting codes can be found, e.g., in [START_REF] Cox | An efficient adaptive circular Viterbi algorithm for decoding generalized tailbiting convolutional codes[END_REF][START_REF] Anderson | An optimal circular Viterbi decoder for the bounded distance criterion[END_REF]).

The trace-back provides the decoded bits in windows of W=32 according to the decisions stored in the path memory in inverse order, such that an output buffer for 32 bits is necessary to bring them into natural order. Our channel decoder implementation requires about 150 cycles to decode the header and 4000 cycles to decode the two RLC blocks in the fastest EDGE transmission mode MCS-9. With a target clock frequency of 40 MHz the decoder latency translates to only about 100 µs, which allows to compensate for potential delays between header and data block decoding 13 .

Discussion: Hard-Decision vs. Soft-Decision Receiver Back-End

When designing a wireless receiver many decisions have to be taken where performance trades against complexity and cost. Often a specific performance goal (e.g., BER under specific conditions) can be met with different combinations of devices, algorithms and architectures. E.g., choosing a radio-frequency IC with a comparably high noise-figure could be (at least partially) compensated for in the digital baseband receiver by implementing the best-performing channel equalizer and decoder algorithms. To find the optimum implementation for a given application under specific constraints it is crucial to know the performance as well as the complexity increase of the different design options.

Using demodulated soft-decision values can improve the BER after channel decoding by 2-3 dB in terms of SNR (e.g., [START_REF] Clark | Error-correction coding for digital communications[END_REF]). However, the generation of softdecision outputs with a Viterbi equalizer is complex and significantly increases the required memory capacity. For each incoming branch to each trellis state the corresponding sum of the branch and state metric has to be stored. Hence, assuming an 8-state DFSE with a 58-stage trellis using 12 bit state metrics and 8 incoming branches (8PSK) to each trellis state (as implemented in our ASIC, cf., Section 4.3) the soft-output DFSE would require an additional 44.5 kb of memory capacity. To generate reliable soft-decisions several paths have to be traced back for each trellis stage [START_REF] Hagenauer | A Viterbi algorithm with soft-decision outputs and its applications[END_REF] which is difficult to realize in hardware and which significantly increases the required number of memory accesses during back-tracing, leading to higher power consumption.

Storing soft-decisions instead of hard-decisions in the de-interleaver and channel decoder input memory requires a higher storage capacity, and processing soft-inputs in the Viterbi decoder increases the complexity of the BMU and state metric recursion units.

The implemented digital baseband receiver ASIC with hard-decision DFSE outputs contains RAMs to store 20 kb. With typical soft-decisions of 5 bit instead, 76 kb memory would be required which translates to an increase of the core size by a factor of more than 2, and to a chip where more than 2/3 of the silicon area are occupied only by memory.

Even more dramatic are the savings achieved by using hard-decision equalizer outputs when thinking of the memory required for the storage of previously received and not correctly decoded radio blocks for IR. According to the specifications, a multi-slot class 12 user equipment 14 has to store up to 24 radio blocks 13 The header information has to be extracted and processed first (typically by higher layers) to obtain the coding scheme, puncturing pattern and RLC block identifier. When a re-transmission has occurred the previously received data block will be restored from an IR memory to combine it with the received data block in the channel decoder input memory. 14 Such a MS is capable of receiving on 4 time slots per frame. with the modulation and coding scheme MCS-9, which translates to about 150 kb using 5 bit soft-values. With hard-decisions only the puncturing pattern and the actual bits have to be stored, which saves as much as 120 kb memory.

Implementation Results

Functional tests and power measurements of fabricated chips (see Fig. 14) have been performed on a digital tester. The fixed-point simulation model of the implemented design has been verified and used to generate the block errorrates (BLERs) of the receiver as shown in Fig. 13 for the various modulation and coding schemes (MCS) of EDGE with the specified Hilly Terrain (HT) test channel with a vehicle speed of 100 km/h. It should be noted that the standard requires MCS1-6 to achieve a BLER of 10 % and MCS7 to achieve a BLER of 30 % at a certain receive power level. For MCS8-9 there are no specifications for these propagation conditions. Assuming the noise-figure of a state-of-the-art RF transceiver IC 15 these BLERs can be achieved at the specified power levels. Other key characteristics are summarized in Table 1. The ASIC occupies 1.0 mm 2 in 0.

Conclusion

EDGE enables 2G data services all over the world with data rates suitable for many cellular applications. The introduction of 8PSK modulation improves the bandwidth utilization, but significantly increases equalizer complexity. Latest 65 nm signal processors provide the computational power required to perform the digital baseband signal processing for EDGE. However, power and silicon area of such implementations exceed what is desirable for a low-power, low-cost 2.5G solution required in modern cellular phones.

In this work a combined architecture for GSM/GPRS/EDGE has been presented. We have shown how the digital baseband can be mapped efficiently to dedicated hardware by using suitable algorithms and architectures to share hardware resources with little overhead. A certain amount of flexibility can support the specified transmission modes with different modulation and coding schemes. Our approach to reduce complexity in the most crucial block, the channel equalizer, is to maximize the effort in the pre-processing FIR filtering, in order to be able to reduce DFSE complexity. Using hard-decisions at the equalizer output is the key to curtail memory requirements in the back-end of a digital baseband receiver for EDGE. With 1.0 mm 2 and only 1.3 mW average power consumption our ASIC implementation shows that cost-effective multi-mode digital baseband receiver accelerators for GSM/EDGE can be realized at ultra low-power.

Fig. 1 Fig. 1 .

 11 Fig.1shows the GSM/EDGE baseband transceiver system model used in this work. On the transmitter side the input data is first encoded with a convolutional

Fig. 2 .

 2 Fig. 2. Time division multiple access and the normal burst in GSM.

Fig. 4 .

 4 Fig. 4. The concept of pre-filtering required for the DFSE.

Fig. 5 .

 5 Fig. 5. Uncoded BER of GMSK and 8PSK modulated signals after pre-filtering with pre-filter order p = 32 and D = {2, 3, 4}. The specified Hilly Terrain (HT) channel profile (no vehicle speed) has been used for the simulations.

Fig. 6 .

 6 Fig. 6. Uncoded BER of 8PSK modulated signals after pre-filtering and channel equalization with DFSE (D = 2) with variable pre-filter order p. The specified Hilly Terrain (HT) channel profile (no vehicle speed) has been used for the simulations.

Fig. 7 .

 7 Fig. 7. Complexity comparison of different algorithms for channel shortening prefilters.

  with the filter coefficients vector a a a = a 1 a 2 • • • a p T and the Toeplitz matrix

Fig. 9 .

 9 Fig. 9. Block diagram of the LD recursion implementation.

Fig. 10 .

 10 Fig. 10. Block diagram of the DFSE implementation.

Fig. 11 .

 11 Fig. 11. Simplified implementation of integer division (a) and modulo operation (b) as required for interleaving.

Fig. 12 .

 12 Fig. 12. Block diagram of the flexible 64-state parallel Viterbi decoder implemented in our design.

Fig. 13 .

 13 Fig. 13. Receiver block error-rates in various modulation and coding schemes (MCS) of EDGE for the specified Hilly Terrain (HT) test channel with a vehicle speed of 100 km/h.

P r e -f i l t e r c o e f f s c o mp u t a t i o n & p r e -f i l t e r i nCh a n n e l d e c o d e r i n p u t me mo r yFig. 14 .

 14 Fig. 14. EDGE receiver ASIC micrograph with highlighted units.

Table 1 .

 1 IRIS305 from ACP AG, a single-chip RF transceiver supporting both TD-SCDMA/HSPA (3G) and GSM/GPRS/EDGE (2.5G) standards. Key characteristics of the receiver ASIC implementation.

	Technology	0.13 µm CMOS
	Supply Voltage VDD	1.2 V-0.6 V
	Core Size	1.0 mm 2
	Gate Count	97 kGE
	Total Memory	20.3 kb
	Max. System Clock Frequency	172 MHz
	Leakage current @ VDD=1.2 V (0.6 V) 0.49 mA (0.15 mA)
	Average power measured during continuous burst
	reception @ target frequency f=40 MHz, VDD=1.2 V (0.6 V)
	GSM CS1 (GMSK)	2.4 mW (0.6 mW)
	EDGE MCS9 (8PSK)	5.2 mW (1.3 mW)

15 E.g.,

Depending on the specific modulation and coding scheme the bits can be interleaved over

or 8 bursts[START_REF]3rd Generation Partnership Project; Technical Specification Group GSM/EDGE Radio Access Network; Channel Coding[END_REF].[START_REF] Olivier | Efficient equalization and symbol detection for 8-PSK EDGE cellular system[END_REF] The guard period of 8.25 symbols ensures that subsequent bursts do not interfere with each other due to inter-symbol interference.

Real-valued multiplications/additions have been counted as 0.25/0.5 complex-valued operations here.

Details on the noise-whitening characteristic of this filter can be found in[START_REF] Chu | Speech coding algorithms : foundation and evolution of standardized coders[END_REF].

Simulations have shown that the performance degradation due to reducing the filter order from 32 to 16 cannot even be compensated for completely by increasing D to 4.

The USF indicates to the user equipment (UE) in which time slot a radio block can be transmitted in the case that two UEs share the same physical channel.

Hard-decisions in the original sense require only 1 bit. Another bit has to be spent to be able to represent the zero (no a-priori information) for the punctured bits.

Acknowledgments

The authors would like to thank Andreas Burg, Andreas Bubenhofer, Johannes Widmer, Stefan Zwicky, Harald Kröll, and Christoph Roth for their support. This project was funded by CTI (No. 11370.1), Switzerland in collaboration with Advanced Circuit Pursuit AG.


Tsung-Yi Ho

Sheng-Hung Liu

Fast Legalization for Standard Cell Placement with Simultaneous Wirelength and Displacement Minimization

Keywords: Displacement, Legalization, Placement, Wirelength

Legalization is one of the most critical steps in modern placement designs. Since several objectives like wirelength, routability, or temperature are already optimized in global placement stage, the objective of legalization is not only to align the cells overlap-free to the rows, but also to preserve the solution of global placement, i.e., the displacement of cells needs to be minimized. However, minimizing displacement only is not enough for current timing-driven SoC designs. Blind displacement minimization may increase the half-perimeter wirelength (HPWL) of nets significantly that degrades the chip performance. In this paper, we propose a fast legalization algorithm for standard cell placement with simultaneous wirelength and displacement minimization. The main contributions of our work are: (1) a fast row selection technique by using k-medoid clustering approach; (2) an exact linear wirelength model to minimize both wirelength and total displacement; (3) a constant time approach to determine the median in trial placement stage. Compared with the state-of-the-art legalization algorithms, experimental results show that our legalizer acquires much better achievement in terms of HPWL, total and maximum displacements, and running time on legalized NTUplace3 global placement results on both ISPD 2005 and 2006 placement contest benchmarks.

Introduction

The conventional standard cell placement includes three stages: global placement, legalization, and detailed placement. Typically, global placement generates an initial placement with minimum total half-perimeter wirelength (HPWL) and tries to optimize some objectives such as routability, timing, temperature, and etc. This results in few cell overlap and the cells are not aligned to the rows. There has been several researches in the area of global placement in the past few years [START_REF] Brenner | Faster and better global placement by a new transportation algorithm[END_REF][START_REF] Chen | NTUplace3: A high-quality mixed-size analytical placer considering preplaced blocks and density constraints[END_REF][START_REF] Chan | mPL6: Enhanced multilevel mixed-size placement[END_REF][START_REF] Kahng | Implementation and extensibility of an analytic placer[END_REF][START_REF] Roy | Capo: Robust and scalable open-source min-cut floorplacer[END_REF][START_REF] Spindler | Fast and robust quadratic placement based on an accurate linear net model[END_REF]. After global placement stage, legalization targets [START_REF] Agnihorti | Fractional cut: Improved recursive bisection placement[END_REF] to remove overlaps between cell instances, [START_REF] Brenner | Legalizing a placement with minimum total movement[END_REF] to put all instances on the rows in the core area, and (3) to minimize the displacements of instances between the initial placement and the legalized one. That is, legalization tries to make the placement legal and to preserve the result from the global placement stage. After legalization, detailed placement is used to improve the solution quality of the legal placement. Legalization with only displacement minimization may significantly induce the solutions with more HPWL than global placement stage. For example, if cell a is to be legalized in Figure 1 (a), blind legalization with only displacement minimization may increase the HPWL as shown in Figure 1 (b). However, by taking HPWL into consideration, we can legalize cell a with both displacement and HPWL minimization.

Previous Work

Existing legalization techniques include network flow [START_REF] Brenner | Legalizing a placement with minimum total movement[END_REF][START_REF] Doll | Iterative placement improvement by network flow methods[END_REF], ripple cell movement [START_REF] Hur | Mongrel: Hybrid techniques for standard cell placement[END_REF], dynamic programming [START_REF] Agnihorti | Fractional cut: Improved recursive bisection placement[END_REF], simulated annealing [START_REF] Sarrafzadeh | NRG: Global and detailed placement[END_REF], single row optimization [START_REF] Kahng | On legalization of rowbased placements[END_REF], diffusion-based method [START_REF] Ren | Diffusionbased placement migration[END_REF], computational geometry [START_REF] Luo | Computational geometry based placement migration[END_REF], packing [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF], and quadratic programming [START_REF] Spindler | Fast and robust quadratic placement based on an accurate linear net model[END_REF]. Domino [START_REF] Doll | Iterative placement improvement by network flow methods[END_REF] partitions cells in subcells (all having the same height and width) and rows in places, and assigns them by using a min-cost-max-flow approach. Similar to Domino, [START_REF] Brenner | Legalizing a placement with minimum total movement[END_REF] assigns sets of modules to row regions. Mongrel [START_REF] Hur | Mongrel: Hybrid techniques for standard cell placement[END_REF] uses a greedy heuristic to move cells from overflowed bins to under capacity bins in a ripple fashion based on total wirelength gain. Fractional Cut [START_REF] Agnihorti | Fractional cut: Improved recursive bisection placement[END_REF] assigned cells to rows by dynamic programming and the cells of each row are packed from left to right. Sarrafzadeh [START_REF] Sarrafzadeh | NRG: Global and detailed placement[END_REF] uses simulated annealing for legalization. The authors of [START_REF] Kahng | On legalization of rowbased placements[END_REF] assigned cells to the rows by cell juggling and the cells of each row are placed by finding a shortest path in a graph. Diffusion-based placement migration is presented in [START_REF] Ren | Diffusionbased placement migration[END_REF] to remove cell overlap incrementally. In [START_REF] Luo | Computational geometry based placement migration[END_REF], cells are spread and aligned to rows by computational geometry techniques. Sarrafzadeh [START_REF] Sarrafzadeh | NRG: Global and detailed placement[END_REF] uses a cell shifting technique to reduce the maximum bin density. HPWL-driven legalizers only target on HPWL minimization within a row by dynamic programming approach [START_REF] Kahng | Optimization of Linear Placements for Wirelength Minimization with Free Sites[END_REF][START_REF] Kahng | On legalization of rowbased placements[END_REF].

Tetris is a fast greedy heuristic which is widely used in industry [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF]. Tetris sorts the cells first, and legalizes one cell at a time then. The legalization of one cell is done by moving the cell over the rows, and within a row by moving the cell over free sites. This movement is done until the best free site is found. Once a cell has been legalized, it will not be moved anymore. This results in a high total cell displacement during legalization. Recently, Spindler et al. present a similar approach, called Abacus [START_REF] Spindler | Abacus: Fast legalization of standard cell circuits with minimal movement[END_REF], that it places a cell from row to row until the location with the smallest displacement is found. However, as a cell is placed into a row, the legalized cells in that row are re-placed by dynamic programming technique to minimize the total displacement. Both Tetris and Abacus scan rows with minimum cost vertically. Tetris scans all rows (see Figure 2 (a)). Abacus sorts the rows by the y-position. A lower bound of the cost is computed by assuming cells are only moved vertically. Abacus moves the cell to the best row first, and then tries to move the cell to the rows with the lower bound not exceeding the minimal cost of an already found legal position (see Figure 2 (b)). In this paper, our legalizer constructs the binary index tree for the rows via clustering techniques. By traversing the binary index tree, our legalizer only scans some candidate rows then the running time is significantly reduced (see Figure 2 (c)).

Our Contribution

The main contributions of our work are: (1) a fast row selection technique by using k-medoid clustering approach; (2) an exact linear wirelength model to minimize both total displacement and HPWL; (3) a constant time approach to determine the median in trial placement stage. The remainder of this paper is organized as follows. Section 2 details our algorithm. Section 3 shows the experimental results. Finally, concluding remarks are given in Section 4.

Algorithm

Figure 3 shows the overview of our legalization algorithm. First, a binary index tree for rows is constructed for fast row scanning (line 1). After that, cells are sorted according to the sum of their x-position and the half of their width (line 2). Then, cells are legalized one by one according to the sorting order (line 3-8). "DFS" (line 5) adopt depth-first search manner to search the best row for each cell; i.e., the cost (the sum of HPWL and displacement of the cell) of the row is minimum by using the binary index tree for row scanning (line 1). Then the cell is inserted to the best row for HPWL and displacement minimization (line 6).

Obstacle

Binary Index Tree

Fast row scanning can be achieved by searching a binary index tree constructed by top-down row clustering technique. In this paper, we adopt k-medoid [START_REF] Lucasius | On k-medoid clustering of large data sets with the aid of a genetic algorithm: background, feasibility and comparison[END_REF] clustering algorithm as the main method for clustering rows. Typically, k-medoid algorithm clusters items by using their similarity. To cluster rows, we define the similarity between rows as the distance between each row. If the distance between each row is far, the similarity is small, and vice versa. Initially, all rows are in a cluster, called root cluster. cluster is less than 3. Finally, we construct a binary index tree for row clusters.

The relation between rows and binary index tree is shown in Figure 4.

Row Scanning

Before placing cells into the rows, legalizers perform row scanning then do trial placement for cells. Different from previous legalizers that scan all rows, our legalizer can find the best row efficiently by searching on the binary index tree. As mentioned earlier, the nodes in the binary index tree represent row clusters. The edge cost in the binary index tree is the distance from a cell to the row cluster. To compute the distance from a cell to the row cluster, we need to compute the distance between rows first. D min (row i , row j ) and D max (row i , row j ) are two kinds of the distance from row i to row j . We adopt D min (row i , row j ) as the distance for clustering rows by using k-medoid algorithm and D max (row i , row j ) as the distance used for computing the edge cost of the binary index tree. If row i overlaps row j horizontally, D min (row i , row j ) is the vertical distance from row i to row j (see Figure 5 (a)). If row i does not overlap row j horizontally, D min (row i , row j ) is the sum of vertical and horizontal distance from row i to row j (see Figure 5 (b)). D max (row i , row j ) is the sum of the vertical distance and maximum horizontal distance from the left of row i to the left (see Figure 5 (c)) of row j or from the right of row i to the right of row j (see Figure 5 (d)). Moreover, the computation of distance from cells to row clusters is the same with distance between rows.

D min (row i , row j )

i j i j (a) (b) i i D max (row i , row j ) j j (c) (d) Row ( ) ( )
Vertical Distance Horizontal Distance After the distance between rows is computed, we defined radius of a row cluster is the farthest distance between its central row to other rows. According to triangle inequality, the distance from a cell to the row cluster, i.e. D min (cell, row cluster), can be derived as shown in Figure 6.

A depth-first search (DFS) approach is used for finding the best row. Algorithm 2 describes the function DFS. DFS starts from root cluster. The cell is always moved into the nearer cluster for trial placement first (line 5-18). The cell is not moved to cluster if D min (cell, row cluster) is larger than the current best displacement. The cost of the row is the sum of both HPWL and displacement of the cell after the cell is moved to the row (line 21). After DFS, the best row can be found quickly, then cells will be inserted into it. For simultaneous wirelength and displacement minimization, the cost of row for placing a cell depends on the displacement and the HPWL of it. Since a cell may be connected by multiple nets, the cost by simply adding the displacement and the HPWL of a cell may not be precise. Furthermore, we not only target to minimize total displacement but also to minimize maximum displacement, we consider both factors by a combined cost function. The cost function is defined as follows:

Cost(i) = HP W L + N i (α • (DP S ) + β • (DP P )) (1)
where N i represents the number of the net belongs to cell i. DP S is the cell displacement between original position and legalized position. DP P is the total increased displacement caused by inserting one cell into row. α, β are userspecified parameters. An example of cost computation is shown in Figure 8.

Obstacle-Aware Cell Ordering

Modern chip designs often consist of many preplaced blocks, such as analog blocks, memory blocks, and/or I/O buffers, which are fixed in the chip and cannot overlap with other blocks. These preplaced blocks, i.e., obstacles, impose more constraints on the legalization problem. A legalization algorithm without considering obstacles may significantly induce increasing cell displacement or inferior solutions. Different from all previous works that insert cell according to its x-position in the global placement, we insert cell according to its central position (i.e., x-position of cells + cell width/2). As illustrated in Figure 9, an obstacle lies in the middle of the row shred the row into two subrows. If cells are inserted by x-position, the larger cell 1 will be inserted first but cause larger displacement for cell 2 and 3 since they are inserted to another subrow that across the obstacle (See Figure 9 (a)). It is not worth because only cell 1 is inserted into the left subrow with smaller displacement and cell 2 and 3 are squeezed to right subrows with larger displacement. If cells are inserted by their central position, most of the smaller cells that are capable of being inserted to fragmentary subrows can reduce the total displacement significantly (See Figure 9 (b)). Moreover, it is capable of handling the relative order problem.

Cell Insertion

Most of previous works use simple quadratic wirelength model to measure cell displacement. The drawback lies in the preciseness since the square of larger cell displacement will have dramatically difference. Different from Abacus that uses quadratic model, we adopt an exact linear wirelength model for measuring cell displacement. Cells of one row are abutting in the legal placement and form a cluster. Assume the row has c clusters and cluster c has n cells which are sorted by their global x-position + width/2. To minimize the cell displacement, the objective function is defined as follows:

min n i=1 |x c i -x c i | (2)
where x c i and x c i are initial and legalized position of cluster c. The constraint (2) assures that there is no overlap between the cells and is defined as follows:

x c i -x c i-1 ≥ w c i-1 i = 2, ..., n (3)
where w c i is cell width. However, solving linear programs with "≥" constraints is time consuming in general. If the same solution of the linear program is found by "=" constraints, then the linear program is solved quite fast by solving one linear equation. The situation that "=" constraints are sufficient is given if all cells of one row are abutting in the legal placement and form a cluster. There, two cells are "abutting" if there is no free space between them in the legal placement. With only "=" constraints, (2) is transformed to:

x c i = x c 1 + i-1 k=1 w c k i = 2, ..., n (4)
By (3), we can transform (1) into (4) such that the optimal value only depends on variable x c 1 .

min n i=1 |x c 1 -[x c i - i-1 k=1 w c k ] d c i | (5)
where d c i is the candidate position of cluster c for cell i and all d c i form a set D c . The optimal x c 1 can be derived by finding the median m of all d c i .

Find Median

As shown in Figure 10, a row has several clusters. The positions of these clusters are determined by X c . If the clusters are overlapped, they will be merged and form a new cluster.

The intuitive method for finding the median is to sort n elements in D c while the time complexity of sorting for trial placement and insertion are both O(nlogn). An efficient method for finding the median is to apply the deterministic partitioning algorithm from quicksort while the time complexity for trial placement and insertion are both O(n). In this paper, we adopt red-black trees for finding the median while the time complexity for trial placement and insertion are both O(logn). Moreover, red-black trees can be used to record already sorted D c since D c will not be changed after cells are placed. Thus, we can derive the set of X c as follows:

X c = {x c (i)} i = 2, ..., n (6)
where x c (i) corresponds to the already sorted elements in D c . Since cells are not really placed on rows in trial placement stage, unnecessary movement of cells can be pruned in this stage. By exploring all possible movements of clusters, we found only the rightmost cluster (i.e., cluster c ) will move to the left and others will stay still. By this observation, we have 3 lemmas for our trial placement stage. By these 3 lemmas, the time complexity of our trial placement is only O(1) since we only need to compare 3 possible positions then we can find the best position for all clusters. The comparison of time complexity in listed in Table 1.

Lemma 1 If the number of the cells in cluster c is even, the cell i is placed to the right of cluster c and the position of cluster c will not be changed.

Proof: Let c is the number of clusters in a row. N c is the number of the cells in cluster c . W c is the width of cluster c . The candidate position for cell i is x i which is the difference of W c and the original x position of cell i. If cell i and cluster c overlap horizontally, x i is less than the original x position of cluster c .

As shown in Figure 11, assume N c is an even number. The original x position of cluster c is the median of X c (i.e., Nc 2 ). Therefore, there are Nc 2 -1 elements that are smaller than the original x position of cluster c , and Nc 2 elements that are larger than the original x position of cluster c . After cell i and cluster c are merged, x i is added into X c . Since x i is smaller than the x position of cluster c, the number of X c which smaller than the original x position of cluster c is Nc 2 . Therefore, the median of X c does not changed. The new x position of cluster c is the original x position of cluster c .

Lemma 2 If the number of the cells in cluster c is odd, the cell i is placed to the right of cluster c and the position of cluster c will shift to the left.

Proof: As shown in Figure 12, assume N c is a odd number and the original x position of cluster c is the median of X c (i.e., Nc+1 2 ). Therefore, the number of X c which smaller than the original x position of cluster c is Nc+1 2 -1. The number of X c which larger than the original x position of cluster c is Nc+1 2 -1. After cell i and cluster c are merged, x i is added into X c . Since x i is smaller than the original x position of cluster c , the number of X c which smaller than the original x position of cluster c is Nc+1 2 . Therefore, the median of X c will be changed. The new x position of cluster c is Nc+1 2 of new X c instead of the original x position of cluster c . In other words, new x position of cluster c is the maximum one between ( Nc+1 2 -1) of original X c and x i ). By Lemma 2, cluster c may overlap with cluster c-1 when cluster c shifts to the left. In this situation, cluster c-1 and cluster c are merged and then form a new and bigger cluster c-1 and the number of the clusters of the row becomes c -1. Under this circumstance, we further observe that although cluster c shifts to the left, the positions of other c -1 clusters will not be influenced by cluster c . The details are described in Lemma 3.

Lemma 3 cluster c has no influence on other n -1 clusters.

Proof: As shown in Figure 13, X c is the difference between X c and W c-1 . If a new cell added to the row, it will cause cluster c overlapped with cluster c-1 , then cluster c-1 and cluster c will be merged together. After cluster c-1 and cluster c are merged, the position of the new cluster c-1 is found by the median of new X c-1 (i.e., original X c-1 merged with X c ). The median of original X c (i.e., X c (N c /2 + 1)) is larger than the median of X c-1 (i.e., X c-1 ((N c-1 + 1)/2)), because cluster c-1 and original cluster c are not overlapped. Once a new cell added to the row, it will cause cluster c overlaps cluster c-1 , the median of new X c (i.e., X c (N c /2)) will be smaller than the median of X c-1 (i.e., X c-1 ((N c-1 + 1)/2)). Therefore, after cluster c-1 and cluster c are merged, the median of new X c-1 is unchanged (i.e., X c-1 (N c-1 + 1)/2). It means that the x position of new cluster c-1 is unchanged, and the position of cell is the sum of (X c-1 (N c-1 + 1)/2), W c-1 , and L c .

In trial place step, the position of the cell on the row can be calculated by finding the maximum of the following three numbers: x', the sum of the Nc+1 2 -1)

of X c and W c , and the sum of the x position of cluster c-1 (i.e., (X c-1 ((N c-1 + 1)/2))), W c-1 , and L c .

Experimental Results

We have implemented our legalizer in the C++ language on a 2-GHz 64-bit Linux machine with 16GB memory. For fair comparison, we evaluate NTUplace3 [START_REF] Chen | NTUplace3: A high-quality mixed-size analytical placer considering preplaced blocks and density constraints[END_REF], Tetris [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF], Abacus [START_REF] Spindler | Abacus: Fast legalization of standard cell circuits with minimal movement[END_REF], and Kahng [START_REF] Kahng | Optimization of Linear Placements for Wirelength Minimization with Free Sites[END_REF] on the same platform. Furthermore, to verify the efficiency and effectiveness of our legalizer, we perform experiments on two benchmark suites, such as ISPD 2005 and 2006 placement contest benchmarks [22]. The global placement results are obtained from NTUplace3 [START_REF] Chen | NTUplace3: A high-quality mixed-size analytical placer considering preplaced blocks and density constraints[END_REF]. Extensive experiments demonstrate that in terms of HPWL, total and maximum displacements, and running time, we acquire much better achievement than all the state-of-the-art algorithms such as Tetris [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF], Abacus [START_REF] Spindler | Abacus: Fast legalization of standard cell circuits with minimal movement[END_REF], and Kahng [START_REF] Kahng | Optimization of Linear Placements for Wirelength Minimization with Free Sites[END_REF] in any aspect.

Benchmarks

The cell numbers of the ISPD 2005 benchmarks range from 210K to 2169K, the fixed macro numbers range from 543 to 23084, and the row numbers range from 890 to 2694. The cell numbers of the ISPD 2006 benchmarks range from 330K to 2507K, the fixed macro numbers range from 337 to 26582, and the row numbers range from 930 to 4182. The benchmark information is listed in Table 2.

HPWL

In the first experiment, we evaluate the HPWL of our legalizer on the both benchmarks. On legalized NTUplace3 [START_REF] Chen | NTUplace3: A high-quality mixed-size analytical placer considering preplaced blocks and density constraints[END_REF] global placements on ISPD 2005 placement contest benchmarks, the HPWL is 1.92X, 1.19X and 1.92X of our legalizer compared to Tetris [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF], Abacus [START_REF] Spindler | Abacus: Fast legalization of standard cell circuits with minimal movement[END_REF], and Kahng [START_REF] Kahng | Optimization of Linear Placements for Wirelength Minimization with Free Sites[END_REF], respectively. It should be noted that Kahng [START_REF] Kahng | Optimization of Linear Placements for Wirelength Minimization with Free Sites[END_REF] only focusing on HPWL minimization. Moreover, we also compare the HPWL after our legalizer with the original HPWL of NTUplace3 global placement results [START_REF] Chen | NTUplace3: A high-quality mixed-size analytical placer considering preplaced blocks and density constraints[END_REF], we can further reduce HPWL by 18%. The details of HPWL experiments on ISPD 2005 benchmarks are listed in Table 3. On legalized NTUplace3 [START_REF] Chen | NTUplace3: A high-quality mixed-size analytical placer considering preplaced blocks and density constraints[END_REF] global placements on ISPD 2006 placement contest benchmarks, the HPWL is 1.44X, 1.25X and 1.43X of our legalizer compared to Tetris [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF], Abacus [START_REF] Spindler | Abacus: Fast legalization of standard cell circuits with minimal movement[END_REF], and Kahng [START_REF] Kahng | Optimization of Linear Placements for Wirelength Minimization with Free Sites[END_REF], respectively. Compare the HPWL after our legalizer with the original HPWL of NTUplace3 global placement results [START_REF] Chen | NTUplace3: A high-quality mixed-size analytical placer considering preplaced blocks and density constraints[END_REF], we can further reduce HPWL by 19%. The details of HPWL experiments on ISPD 2006 benchmarks are listed in Table 4.

Displacement

In the second experiment, we report the total and maximum displacement on both ISPD benchmarks. On legalized NTUplace3 global placements on ISPD 2005 placement contest benchmarks, the total displacement is 25.76X, 1.09X, and 27.16X, the maximum displacement is 1.88X, 1.04X, and 2.40X of our legalizer compared to Tetris [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF], Abacus [START_REF] Spindler | Abacus: Fast legalization of standard cell circuits with minimal movement[END_REF], and Kahng [START_REF] Kahng | Optimization of Linear Placements for Wirelength Minimization with Free Sites[END_REF], respectively. The details of displacement experiments on ISPD 2005 benchmarks are listed in Table 5.

On legalized NTUplace3 global placements on ISPD 2006 placement contest benchmarks, the total displacement is 5.27X, 1.15X, and 5.43X, the maximum displacement is 1.51X, 1.35X, and 1.51X of our legalizer compared to Tetris [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF], Abacus [START_REF] Spindler | Abacus: Fast legalization of standard cell circuits with minimal movement[END_REF], and Kahng [START_REF] Kahng | Optimization of Linear Placements for Wirelength Minimization with Free Sites[END_REF], respectively. The details of displacement experiments on ISPD 2006 benchmarks are listed in Table 6. It should be noted that Abacus [START_REF] Spindler | Abacus: Fast legalization of standard cell circuits with minimal movement[END_REF] achieved the best published results in displacement but our legalizer still get better results due to the exact linear wirelength model.

Running time

In the third experiment, we evaluate the running time on both ISPD benchmarks. On legalized NTUplace3 global placements on ISPD 2005 placement contest benchmarks, the running time is 5.79X, 36.18X, and 5.94X of our legalizer compared to Tetris [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF], Abacus [START_REF] Spindler | Abacus: Fast legalization of standard cell circuits with minimal movement[END_REF], and Kahng [START_REF] Kahng | Optimization of Linear Placements for Wirelength Minimization with Free Sites[END_REF], respectively. The details of running time experiments on ISPD 2005 benchmarks are listed in Table 7.

On legalized NTUplace3 global placements on ISPD 2006 placement contest benchmarks, the running time is 6.28X, 26.15X, and 6.49X of our legalizer compared to Tetris [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF], Abacus [START_REF] Spindler | Abacus: Fast legalization of standard cell circuits with minimal movement[END_REF], and Kahng [START_REF] Kahng | Optimization of Linear Placements for Wirelength Minimization with Free Sites[END_REF], respectively. The details of running time experiments on ISPD 2006 benchmarks are listed in Table 8. It should be noted that Tetris [START_REF] Hill | Method and system for high speed detailed placement of cells within integrated circuit designs[END_REF] achieved the fastest published results but our legalizer still get better results due to the row indexing and fast trial placement techniques.

Figure 14 (a) shows the global placement result of "adaptec1" obtained from NTUplace3. To further reveal the difference of Tetris, Abacus, Kahng, and ours, we plot the movement pictures during legalization in Figure 14 (b),(c),(d), and (e).

Conclusions

In this paper, we proposed a fast legalization algorithm with simultaneous displacement and HPWL minimization. The main contributions of our work are: (1) a fast row selection technique by using k-medoid clustering approach; (2) an exact linear wirelength model to minimize both wirelength and total displacement; (3) a constant time approach to determine the median in trial placement stage. Compared with the state-of-the-art algorithms, experimental results have shown that our legalizer obtains very high-quality results on legalized NTUplace3 global placements on both ISPD 2005

X' c :{ x' c (1) , x' c (2), x' c (3), …, x' c (N c /2), x' c (N c /2+1), …, x' c (N c -2), x' c (N c -1), x' c (N c ) } N c / 2 N c / 2 ∵ x' c (N c /2) <x c-1 ((N c-1 +1)/2)< x' c (N c /2+1) c ( c / ) c 1 (( c 1 )/ ) c ( c / ) ∴ X c-1 merge X' c :{:{ … , x c-1 ((N c-1 +1)/2), … } (N c-1 -1 +N c )/ 2 (N c-1 -1 +N c )/ 2 ∴ x c-1 ((N c-1 +1)/2
) is also the median

Fig. 1 .

 1 Fig. 1. (a) Original placement before legalizing cell a. (b) Placement with larger HPWL after legalizing cell a. (c) Placement with smaller HPWL after legalizing cell a.

Fig. 2 .

 2 Fig. 2. (a) Tetris scans all rows. (b) Abacus scans the rows by y-position. (c) Our legalizer only scans the rows when they are necessary.

Fig. 4 .

 4 Fig. 4. Top-down clustering constructs a binary index tree for rows.

Fig. 5 .

 5 Fig. 5. (a) Dmin(rowi, rowj) with horizontal overlaps. (b) Dmin(rowi, rowj) without horizontal overlaps. (c) Dmax(rowi, rowj) with horizontal overlaps. (d) Dmax(rowi, rowj) without horizontal overlaps.

Fig. 6 .

 6 Fig.6. Illustration of the minimum distance computation between a cell and a row cluster.

Fig. 7 .

 7 Fig. 7. The algorithm of function DFS.

Fig. 8 .

 8 Fig. 8. Illustration of the cost(i) to find the best row.

Fig. 9 .

 9 Fig. 9. Ordering for obstacle-aware cell insertion.

Fig. 10 .

 10 Fig. 10. Illustration of cluster merging.

N c is aN c / 2 N c / 2 N c / 2 N c / 2 Fig. 11 . 2 Fig. 12 . 1 X

 2222112121 Fig. 11. Nc is an even number.

Fig. 13 .

 13 Fig. 13. Merge process of clusterc-1.

Fig. 14 .

 14 Fig. 14. (a) Global placement result of adaptec1. (b) Cell movement during Tetris [7]. (c) Cell movement during Abacus [19]. (d) Cell movement during Kahng [9]. (e) Ours.

  and 2006 placement contest benchmarks. if row best is null or displacement best > D R then

	16	DFS(cell, row_cluster.RightChild);
	17	end
	18	end
	19	end
	20 else
	21	foreach row in row_cluster do
	22	displacement candidate = TrialPlace(row, cell);
	23	if displacement candidate < displacement best then
	24	displacement best = displacement candidate ;
	25	end
	26	end
	27 end

Table 1 :

 1 Time complexity for trial placement and cell insertion

		Trial Trial	Insert Insert
	Sorting algorithm O(nlogn) O(nlogn)
	SELECT algorithm	O(n)	O(n)
	Red-Black tree Red Black tree	O(logn) O(logn) O(logn) O(logn)
	Ours	O(1)	O(logn)

Table 2 :

 2 Statistics of two benchmark suites of the ISPD placement contest

		ISPD 2005 Benchmarks			ISPD 2006 Benchmarks
	N Name	# C ll # Cells	# Fi d M # Fixed Macros	# R # Rows	N Name	# C ll # Cells	# Fi d M # Fixed Macros	# R # Rows
	adaptec1	210904	543	890	adaptec5	843128	646	1944
	adaptec2	254457	566	1170	newblue1	330073	337	930
	adaptec3	450927	723	1944	newblue2	441516	1277	1925
	d t 4 adaptec4	494716 494716	1329 1329	1944 1944	bl 4 newblue4	646139 646139	3422 3422	1524 1524
	bigblue1	277604	560	890	newblue5	1233058	4881	2130
	bigblue2	534782	23084	1566	newblue6	1255039	6889	2316
	bigblue3	1093034	1293	2316	newblue7	2507954	26582	3258
	bigblue4 bigblue4	2169183 2169183	8170 8170	2694 2694

Table 3 :

 3 Wirelength comparison between NTUplace3, Tetris, Abacus, Kahng, and ours on ISPD 2005 benchmarks

	ISPD 2005 Benchmarks NTUplace3 [5]	Tetris [7]	Abacus [19]	Kahng [9]	Ours
	Name	HPWL	HPWL	HPWL	HPWL	HPWL
	adaptec1	9.56E+07	1.20E+08	9.50E+07	1.19E+08	8.00E+07
	adaptec2 adaptec2	9 98E+07 9.98E+07	1 39E+08 1.39E+08	1 01E+08 1.01E+08	1 39E+08 1.39E+08	8 80E+07 8.80E+07
	adaptec3	2.43E+08	2.61E+08	2.40E+08	2.61E+08	2.00E+08
	adaptec4	2.14E+08	2.53E+08	2.09E+08	2.52E+08	1.80E+08
	bigblue1	1.10E+08	5.00E+08	1.10E+08	4.98E+08	9.40E+07
	bigblue2 bigblue2	1 65E+08 1.65E+08	1 79E+08 1.79E+08	1 64E+08 1.64E+08	1 78E+08 1.78E+08	1 30E+08 1.30E+08
	bigblue3	4.15E+08	5.86E+08	4.67E+08	5.85E+08	3.60E+08
	bigblue4	8.97E+08	1.04E+09	9.09E+08	1.03E+09	7.60E+08
	AVG.	1.18	1.92	1.19	1.92	1

Table 4 :

 4 Wirelength comparison between NTUplace3, Tetris, Abacus, Kahng, and ours on ISPD 2006 benchmarks

	ISPD 2006 Benchmarks NTUplace3 [5]	Tetris [7]	Abacus [19]	Kahng [9]	Ours
	Name	HPWL	HPWL	HPWL	HPWL	HPWL
	adaptec5	4.01E+08	4.95E+08	4.07E+08	4.94E+08	3.14E+08
	newblue1	6.42E+07	1.03E+08	6.40E+07	1.03E+08	5.74E+07
	newblue2	2.16E+08	2.46E+08	2.20E+08	2.45E+08	2.02E+08
	newblue4	2.89E+08	3.20E+08	2.84E+08	3.19E+08	2.32E+08
	newblue5	5.06E+08	5.34E+08	5.01E+08	5.32E+08	4.23E+08
	newblue6	5.09E+08	6.15E+08	6.18E+08	6.15E+08	4.25E+08
	newblue7	1.13E+09	1.30E+09	1.25E+09	1.30E+09	9.24E+08
	AVG.	1.19	1.44	1.25	1.43	1

Table 5 :

 5 Displacement comparison between NTUplace3, Tetris, Abacus, Kahng, and ours on ISPD 2005 benchmarks

	ISPD 2005 Benchmarks	Tetris [7]	Abacus [19]	Kahng [9]	Ours
	Name	TOTAL	MAX	TOTAL	MAX	TOTAL	MAX	TOTAL	MAX
	adaptec1	7.91E+07	2490	5.89E+06	1247	8.10E+07	2490	6.00E+06	1211
	adaptec2 adaptec2	1 31E+08 1.31E+08	3432 3432	1 90E+07 1.90E+07	3485 3485	1 32E+08 1.32E+08	3432 3432	1 90E+07 1.90E+07	3239 3239
	adaptec3	1.22E+08	4581	5.11E+07	5419	1.23E+08	4577	4.80E+07	5733
	adaptec4	1.56E+08	2197	2.74E+07	1702	1.58E+08	3161	2.60E+07	1736
	bigblue1	7.38E+08	9319	4.63E+06	1304	7.90E+08	9319	4.80E+06	1342
	bigblue2 bigblue2	6 25E+07 6.25E+07	1143 1143	1 31E+07 1.31E+07	871 871	6 77E+07 6.77E+07	3757 3757	9 20E+06 9.20E+06	718 718
	bigblue3	8.01E+08	5886	4.20E+08	6729	8.02E+08	5886	3.50E+08	6756
	bigblue4	8.21E+08	2115	6.56E+07	5701	8.36E+08	2115	6.00E+07	5203
	AVG.	25.76	1.88	1.09	1.04	27.16	2.40	1	1

Table 6 :

 6 Displacement comparison between NTUplace3, Tetris, Abacus, Kahng, and ours on ISPD 2006 benchmarks

	ISPD 2006 Benchmarks	Tetris [7]	Abacus [19]	Kahng [9]	Ours
	Name	TOTAL	MAX	TOTAL	MAX	TOTAL	MAX	TOTAL	MAX
	adaptec5	4.65E+08	5117	9.12E+07	3617	4.68E+08	5117	8.79E+07	4920
	newblue1	1.44E+08	3639	1.37E+07	2990	1.45E+08	3639	1.31E+07	1459
	newblue2	2.17E+08	6162	1.05E+08	4535	2.18E+08	6162	7.37E+07	2131
	newblue4	2.17E+08	2214	4.24E+07	2808	2.30E+08	2214	4.16E+07	2327
	newblue5	1.55E+08	4030	3.52E+07	1527	1.61E+08	4030	3.31E+07	1777
	newblue6	8.97E+08	2609	2.68E+08	7485	9.07E+08	2609	2.23E+08	7514
	newblue7	1.22E+09	4248	3.99E+08	10527	1.34E+09	4248	3.20E+08	7246
	AVG.	5.27	1.51	1.15	1.35	5.43	1.51	1.00	1.00

Table 7 :

 7 Runtime comparison between NTUplace3, Tetris, Abacus, Kahng, and ours on ISPD 2005 benchmarks

	ISPD 2005 Benchmarks	Tetris [7]	Abacus [19]	Kahng [9]	Ours
	Name	TIME (s)	TIME (s)	TIME (s)	TIME (s)
	adaptec1	32	101	34	16
	adaptec2 adaptec2	44 44	321 321	47 47	11 11
	adaptec3	163	647	169	24
	adaptec4	213	682	218	47
	bigblue1	38	110	40	18
	bigblue2 bigblue2	360 360	601 601	365 365	72 72
	bigblue3	1453	15033	1465	82
	bigblue4	1272	4456	1304	304
	AVG.	5.79	36.18	5.94	1

Table 8 :

 8 Runtime comparison between NTUplace3, Tetris, Abacus, Kahng, and ours on ISPD 2006 benchmarks

	ISPD 2006 Benchmarks	Tetris [7]	Abacus [19]	Kahng [9]	Ours
	Name	TIME (s)	TIME (s)	TIME (s)	TIME (s)
	adaptec5	304	2225	312	51
	newblue1	32	123	35	24
	newblue2	389	1032	395	53
	newblue4	274	1327	281	49
	newblue5	598	1869	612	116
	newblue6	839	4917	854	188
	newblue7	5163	16844	5245	365
	AVG.	6.28	26.15	6.40	1