In this paper, an efficient computational scheme is proposed to calculate the symbol mean and variance from bit a priori information, when a so-called multilinear mapping is employed. The multilinear mapping is exploited to reduce the number of the terms needed for the calculation of the symbol mean and variance.

This paper presents a novel Reed-Solomon codes based transmission scheme called RS-SC-CP. While RS-SC-CP is essentially a Reed-Solomon (RS) coded single carrier with cyclic prefix (SC-CP) system, a filter bank representation of the RS code is used. This filter bank representation unveils a DFT synthesis bank, just as in a traditional Orthogonal Frequency Division Multiplexing (OFDM) system (allbeit in a finite field). Therefore, RS-SC-CP is topologically equivalent with OFDM. As such, the RS-SC-CP system inherits the advantages of an SC-CP system over a traditional OFDM system like a low Peak to Average Power Ratio (PAPR). But, more importantly, it allows us to use a novel equalization technique that resembles a traditional OFDM equalizer. The equalizer of an RS-SC-CP receiver is split into two stages: the first stage encompasses a partial equalization in the complex field, which ensures that the residual channel response has integer coefficients. It is calculated using a Minimum Mean Square Error (MMSE) criterion. The residual ISI is removed by a Galois field equalizer in the second stage, posterior to the RS decoding removing the noise. Finally, the performance of the RS-SC-CP system is further evaluated by simulations showing the performance gain of the RS-SC-CP system compared to a traditional coded OFDM or single carrier with cyclic prefix (SC-CP) scheme.

In this paper we present a macromodeling methodology to accurately reproduce the timing and the peak/average power behaviors of digital standard cells for a wide range of operating conditions determined by the load, the input transition time, and the supply variations. Our methodology significantly reduces the number of transient simulations for the cell characterization. The numerical results for the transient simulation of large digital systems indicate that we achieve a mean error of 10% for the power consumption and 4% for the propagation delay of the complete digital system while the mean error for the used gates in this system is 2.5% when compared to SPICE-based simulations.

This paper provides an extension of RS-OFDM for transmission over Rayleigh fading channels with additive white Gaussian noise (AWGN). RS-OFDM is a combination of Reed-Solomon (RS) codes and orthogonal frequency division multiplexing (OFDM), in which part of the RS code operates as an OFDM front-end. Apart from other advantages such as low peak to average power ratio (PAPR), this scheme benefits mainly from the fact that the overall code is an RS code, leading to optimal performance. This result was obtained previously under the constraint of impulse noise and a fixed integer valued channel. This paper shows that these constraints can be removed by splitting the equalization in two stages: the first stage encompasses a partial equalization in the complex field, which avoids noise amplification. This complex field equalizer also ensures that the residual channel response has integer coefficients. It is calculated using a minimum mean square error (MMSE) criterion. The residual ISI is removed by a Galois field equalizer in the second stage, posterior to the RS decoding removing the noise. Finally, the performance of the RS-OFDM system is further evaluated by simulations showing the performance gain of the RS-OFDM system compared to a traditional coded OFDM or single carrier with cyclic prefix (SC-CP) scheme.

In this paper, a joint solution to the design problem of a good error-correcting code for an OFDM scheme with a low peak to average power ratio (PAPR) in the case of impulse noise is presented. The PAPR problem is tackled by decomposing the circulant channel matrix into parallel channels by using DFT matrices in a Galois field of odd characteristic, rather than in a complex field. The modulo operation inherent to this field then limits the power of the modulated signal. More importantly, it is explained how this OFDM scheme can be seamlessly merged with a Reed-Solomon (RS) code, which due to its maximal Hamming distance is the preferred code for impulse noise cancellation. The overall scheme, referred to as RS-OFDM, shows an error correcting code that is matched to the OFDM-modulator. It is shown that the optimal Hamming distance of the RS code is preserved not only by the OFDM modulator, but also by the channel

In a synchronous clock distribution network with negligible skews, digital circuits switch simultaneously on the clock edge; therefore, they generate a lot of substrate noise due to the resulting sharp peaks on the supply current. A solution is to split a large design in different clock regions and introduce intentional clock skews between them, while taking the timing constraints into account. In this paper, the authors present a complete design flow to optimize the clock tree for less substrate-noise generation in large digital systems. It proposes a technique to assign combinatorial cells and flip-flops to the clock regions. It also takes into account the impact of unintentional clock skew such as jitter on the computed skews in order to assure a robust design. During the optimization, it uses compressed supply-current profiles to improve the CPU time. Experimental results show more than a factor-of-2 reduction in substrate-noise generation from large digital circuits of which the skews are optimized

Substrate noise generated by the switching digital circuits degrades the performance of analog circuits embedded on the same substrate. It is therefore important to know the amount of noise at a certain point on the substrate. Existing transistor-level simulation approaches based on a substrate model extracted from layout information are not feasible for digital circuits of practical size. This paper presents a complete high-level methodology, which simulates a large digital standard cell-based design using a network of substrate macromodels, with one macromodel for each standard cell. Such macromodels can be constructed for both EPI-type and bulk-type substrates. Comparison of our substrate waveform analysis (SWAN) to several measurements and to several full SPICE simulations indicates that the substrate noise is simulated with our methodology within 10%-20% error in the time domain and within 2 dB relative error at the major resonance in the frequency domain. However, it is several orders of magnitude faster in CPU time than a full SPICE simulation.

Transmit maximum-ratio combining (transmit MRC) is a popular antenna diversity technique that provides both spatial diversity and array gain in downlink multiple-input single-output (MISO) links. These gains, however, critically depend on the availability of the downlink channel state information (CSI). In time-division duplexing systems, channel reciprocity has been commonly put forth to justify the convenient use of the CSI already acquired from the uplink, in the calculation of the transmit-MRC weights. Recent work has questioned this practice, based on the non-reciprocity of multi-antenna RF transceivers, due to significant amplitude and phase mismatches across the antennas. Furthermore, expensive digital calibration solutions have been proposed to enforce the reciprocity of the multi-antenna RF transceivers. Both the impact of multi-antenna amplitude and phase mismatches and the performance of the proposed calibration approaches have only been assessed via simulations. In this contribution, we propose an alternative statistical analysis of the impact of these mismatches on transmit MRC. This analysis allows a faster and more reliable characterization as well as provides insight into the relative importance of these mismatches. Consequently, sufficient matching requirements can be extracted for the multi-antenna RF transceivers, for which simpler and cheaper calibration solutions can be devised.

The last decade shows a growing interest in soft decoding techniques, motivated by a soft decoding gain of roughly 2 dB. Most of the techniques are applied to concatenated codes, in particular to turbo codes. This is in strong contrast to many existing coding schemes where Reed-Solomon (RS) codes are common. Recently, we unveiled a filterbank structure behind the RS codes. Using this filterbank decomposition, a RS code is broken into many smaller subcodes that can consequently be used to build a soft-in soft-out (SISO) RS decoder. A limitation of this previous work is that it is only applicable to RS codes where the codeword and dataword length are not coprime. In this paper, this constraint is eliminated. A purely algebraic method is presented to construct a filterbank decomposition for any RS code, as long as a subfield exists in the Galois field in which the RS code operates. This method gives a lot of insight into the algebraic structure of RS codes and their corresponding filterbanks.

The last decade shows a growing interest in soft decoding techniques, motivated by a soft decoding gain of roughly 2dB. Most of the techniques are applied to concatenated codes, with turbo codes as the most famous example. This is in strong contrast with many existing coding schemes where Reed-Solomon (RS) codes are common. Recently, we unveiled an (FIR) filterbank structure behind the RS codes. Using this filterbank decomposition, a RS code is broken into many smaller subcodes that can consequently be used to build a SISO RS decoder. The aim of this paper is twofold: in the first part, an algebraic shortcut to construct the FIR filterbank is presented. This method gives a lot of insight into the algebraic structure of RS codes and their corresponding filterbanks. In the second part, motivated by the importance of systematic RS codes, a critically subsampled IIR filterbank structure implementing a systematic RS code is examined. The SISO RS decoder based on the IIR filterbank shows a lower computational complexity and better performance compared to the FIR counterpart.

Multirate systems and filterbanks are known to be powerful tools in image and audio applications. Recently, they are also recognised to play an important role in communication systems. This paper covers the use of filterbanks in a coding context. It is shown that their inherent periodically time varying character matches remarkably well with the cyclic properties of the family of Bose-Chaudhuri-Hochquenghem (BCH) codes. In this paper, the important subclass of Reed-Solomon (RS) codes is dealt with first. This section of the paper proves that an RS code can be implemented by a critically subsampled filterbank. The redundancy is added by the subbandfilters, which are shown to be variants of non-primitive BCH codes. The second part of the paper deals with BCH codes. In this part, a BCH code is decomposed as a sum of critically subsampled filterbanks. The critical subsampling is an important aspect in a number of applications. The use of these filterbanks in a CDMA system and in a soft-in soft-out (SISO) decoding context is briefly discussed

In the last decade, there has been a growing interest in soft decoding techniques. These techniques are used in the context of concatenated codes, with Turbo codes as the main example, but are almost never applied to existing classical codes. In this paper, the family of Reed-Solomon codes is considered and the complexity problem of Soft-In Soft-Out RS decoding is tackled by breaking RS codes into several smaller subcodes. The decomposition, presented here, is based on filterbanks with one subcode in each subband. The critical subsampling is then crucial if the filterbank is going to be used in a soft decoding setup. This paper focuses on the construction of such filterbanks, starting from non-critically subsampled filterbanks and evolving to a critically subsampled filterbank.

Cache misses form a major bottleneck for real-time multimedia applications due to the off-chip accesses to the main memory. This results in both a major access bandwidth overhead (and related power consumption) as well as performance penalties. We propose a new technique for organizing data in the main memory for data dominated multimedia applications so as to reduce the majority of the conflict cache misses. The focus of this paper is on the formal and heuristic algorithm we use to steer the data layout decisions and the experimental results obtained using a prototype tool. Experiments on real-life demonstrators illustrate that we are able to reduce up to 82 percent of the conflict misses for applications which are already aggressively transformed at source-level. At the same time, we also reduce the off-chip data accesses by up to 78 percent. In addition, we are able to reduce up to 20 percent more conflict misses compared to existing techniques.

In a synchronous clock-distribution network, digital circuits switch simultaneously on the clock edge; therefore, they generate ground bounce due to sharp peaks of the supply current. We demonstrate an effective combination of two methodologies for ground-bounce reduction based on shaping the supply current: 1) introducing intentional skews to the synchronous clock network and 2) frequency modulation of the system clock. The former technique reduces the time-domain peaks as well as the spectral power of the supply current by spreading the simultaneous switching activities. The latter technique reduces the power contained in the clock harmonics by spreading this power into the side lobes formed around the clock harmonics without any change in the spectral power of the supply current. We also describe an analytical framework to analyze the impact of cycle-to-cycle variations of the supply current on the ground-bounce voltage. Simulation results for a 40K-gates circuit in a 0.18-/spl mu/m 1.8-V CMOS process on a bulk-type substrate show around 26 dB reduction in the spectral peaks of the ground-bounce spectrum at the circuit resonance and factors of 3.04/spl times/ and 2.64/spl times/ reduction in the peak-to-peak and RMS values, respectively, of the ground bounce in the time domain when these two techniques are combined. These two techniques are believed to be good candidates for the development of digital low-noise designs in CMOS technologies.

Nowadays, a lot of effort is spent on developing inexpensive orthogonal frequency-division multiplexing (OFDM) receivers. Especially, zero intermediate frequency (zero-IF) receivers are very appealing, because they avoid costly IF filters. However, zero-IF front-ends also introduce significant additional front-end distortion, such as IQ imbalance. Moreover, zero-IF does not solve the phase noise problem. Unfortunately, OFDM is very sensitive to the receiver nonidealities IQ imbalance and phase noise. Therefore, we developed a new estimation/compensation scheme to jointly combat the IQ imbalance and phase noise at baseband. In this letter, we describe the algorithms and present the performance results. Our compensation scheme eliminates the IQ imbalance based on one OFDM symbol and performs well in the presence of phase noise. The compensation scheme has a fast convergence and a small residual degradation: even for large IQ imbalance, the overall system performance for an OFDM-wireless local area network (WLAN) case study is within 0.6 dB of the optimal case. As such, our approach greatly relaxes the mismatch specifications and thus enables low-cost zero-IF receivers.

Substrate noise is a major obstacle for mixed-signal integration. In this paper we propose a fast and accurate high-level methodology to simulate substrate noise generated by large digital circuits. The methodology can handle any substrate type, e.g. bulk-type or EPI-type, and takes into account the effects of interconnect and supply. For each standard cell a substrate macromodel is used in order to efficiently simulate the total system, which consists of a network of such macromodels. For a 40K gates telecom circuit fabricated in a 0.18 mm CMOS process, measurements indicate that substrate noise is simulated by using our methodology within 20% error but several orders of magnitude faster in CPU time than a full SPICE simulation..

A long, long time ago, in a laboratory far, far away, EDA researchers and developers used paper tape instead of Linux, rubylith instead of GDS II, yellow wires instead of ten levels of metal. Sitting around a potbellied stove, in their rocking chairs, practitioners of that era (and this) will offer insight into why some great ideas were immediately put into practice while others stayed on the drawing board or in the ivory tower. They will share remembrances of things past, of simpler days when foundries made steel, when options meant CMOS or bipolar, when real parts were measured instead of benchmarks touted. Their stories of what it was like, what has changed, and whether the "good old days" were then or now will be followed by questions and, possibly, answers.

The digital switching noise that propagates through the chip substrate to the analogue circuitry on the same chip is a major limitation for mixed-signal SoC integration. In synchronous digital systems, digital circuits switch simultaneously on the clock edge, hereby generating a large ground bounce. In order to reduce the spectral peaks in the ground bounce spectrum, we combine the two techniques: (1) phase modulation of the clock; and (2) introducing intended clock skews to spread the switching activities. Experimental results show around 16 dB reductions in the spectral peaks of the noise spectrum when these two techniques are combined. These two techniques are believed to be good candidates for the development of methodologies for digital low-noise design techniques in future CMOS technologies.

We aim to bridge the gap between classical coding theory and soft decoding. Reed-Solomon (RS) codes are chosen as an example, and a few standard possibilities for a soft RS decoder are explored. Soon, it is noticed that the resulting (standard) algorithms are too complex and/or not very performant. However, by employing a special critically sampled filter bank representation for the RS codes, an algorithm is developed that shows a good tradeoff between computational complexity and soft decoding performance. Furthermore, it is demonstrated that this algorithm shows remarkable similarities with turbo codes, thereby preserving the perfectness of the original RS code.

In this paper, we compare high-performance OFDM and single-carrier with frequency-domain equalization (SC-FD) schemes using multiple-antennas and decision-feedback equalization (DFE), while also accounting for the power amplifier efficiency. To make a realistic comparison, we also consider most important digital imperfections such as channel and noise estimation, transmit and receive filtering, clipping and quantization as well as link layer impact. Our analysis shows that for frequency-selective channels, the relative performance impact of the power amplifier is negligible compared to the frequency diversity impact. The higher frequency diversity exploitation of SC-FD allows it to transmit more efficiently than OFDM in most cases. Therefore, SC-FD is a suitable candidate for broadband wireless communication, especially for battery-powered up-link transmission.

The joint linear precoder and decoder minimum mean squared error (MMSE) design represents a low complexity yet powerful solution for spatial multiplexing MIMO systems. Its performance, however, critically depends on the availability of timely channel state information (CSI) at both transmitter and receiver. In practice, the latter assumption can be severely challenged, due to channel time variations that lead to outdated CSI at the transmitter. State-of-the-art designs mistakenly use the outdated CSI to design the linear precoder and rely on the receiver to reduce the induced degradation. In this paper, we propose a robust Bayesian joint linear precoder and decoder solution that takes into account the uncertainty of the true channel, given the outdated CSI at the transmitter. We finally assess the robustness of our design to channel time variations through Monte-Carlo analysis of the system's MMSE and average bit-error rate (BER) performance.

The last decade has shown a growing interest in soft decoding techniques. These techniques are almost never applied to existing nearly perfect codes, but instead other families of concatenated codes arise with Turbo codes as the main example. The problem is that for the application of soft decoding, the perfect codes need to be broken into several smaller component codes. In this paper, the family of Reed-Solomon codes is considered, and, using filterbanks, they are broken into several component codes (one in each subband). This paper focuses on the construction of such filterbanks, and gradually evolves towards a critically subsampled filterbank. The critical subsampling is crucial if the filterbank is going to be used in a soft decoding setup.

OFDM is a popular modulation scheme for broadband wireless communication. It elegantly handles multipath and has low complexity. Recently, single-carrier with frequency-domain processing (SC-FD) is gaining attention as a possible competitor for OFDM. It is based on the same principles and, therefore, it has similar multipath handling capabilities and low complexity. Moreover, SC-FD promises several other attractive advantages, such as power amplifier efficiency and inherent frequency diversity exploitation. Current performance comparisons do not consider these effects combined. We make the comparison in a realistic scenario considering both the power amplifier efficiency and frequency diversity. Our results show that, in a multipath environment, SC-FD can outperform OFDM by 4 dB, largely due to the better frequency diversity exploitation. Therefore, SC-FD is a good alternative to OFDM for battery-powered terminals, and is therefore especially suited for uplink communication.

Zero-IF transceivers are gaining interest because of their potential to enable low-cost OFDM terminals. However, the zero-IF architecture introduces IQ imbalance which may have a huge impact on the performance. Rather than increasing component cost to decrease the IQ imbalance, an alternative is to tolerate the IQ imbalance and compensate it digitally. Current solutions require extra analog hardware at the transmitter. We analyze transmit IQ imbalance estimation and propose a low-cost, highly effective estimation scheme, which is fully digital and located at the receiver. Performance analysis shows that this scheme can provide up to 4 dB gain while meeting the IEEE 802.11a constellation accuracy specification and more if larger IQ imbalance is present in the transmitter. It therefore enables the design of low-cost, low-complexity OFDM modems.

To approach the potential MIMO capacity while optimizing the system bit-error rate (BER) performance, the joint transmits and receive minimum mean squared error (MMSE) design has been proposed. It is the optimal linear scheme for spatial multiplexing MIMO systems, assuming a fixed number of spatial streams p as well as a fixed modulation and coding across these spatial streams. However, state-of-the-art designs arbitrarily choose and fix the value of the number of spatial streams p, which may lead to an inefficient power allocation strategy and a poor BER performance. We have previously proposed to relax the constraint of fixed number of streams p and to optimize this value under the constraints of fixed average total transmit power and fixed spectral efficiency, what we referred to as spatial-mode selection. Our previous selection criterion was the minimization of the system sum MMSE. In the present contribution, we introduce a new and better spatial-mode selection criterion that targets the minimization of the system BER. We also provide a detailed performance analysis, over flat-fading channels, that confirms that our proposed spatial-mode selection significantly outperforms the state-of-the-art joint Tx/Rx MMSE design both for uncoded and coded systems, thanks to its better exploitation of the MIMO spatial diversity and more efficient power allocation.

Zero-IF receivers are gaining interest because they enable low-cost WLAN OFDM terminals. However, zero-IF receivers introduce IQ imbalance which may have a huge impact on performance. Rather than increasing component cost to decrease the IQ imbalance, an alternative is to tolerate the IQ imbalance and compensate it digitally. Current solutions converge too slowly for bursty WLAN communication. Moreover, the tremendous impact of a frequency offset on the IQ estimation/compensation problem is not considered. We analyze joint IQ-CFO estimation/compensation and propose a low-cost, highly effective compensation scheme. For large IQ imbalance (/spl epsi/=10%, /spl Delta//spl phi/=10/spl deg/) and large frequency offset, our solution results in an average remaining degradation below 0.5 dB compared to the reference case without IQ imbalance or frequency offset. It therefore enables the design of low-cost, low-complexity WLAN OFDM receivers.

The combination of space-time block coding (STBC) and direct-sequence code-division multiple access (DS-CDMA) has the potential to increase the performance of multiple users in a cellular network. However, if not carefully designed, the resulting transmission scheme suffers from increased multiuser interference (MUI), which dramatically deteriorates the performance. To tackle this MUI problem in the downlink, we combine two specific DS-CDMA and STBC techniques, namely single-carrier block transmission (SCBT) DS-CDMA and time-reversal STBC. The resulting transmission scheme allows for deterministic maximum-likelihood (ML) user separation through low-complexity code-matched filtering, as well as deterministic ML transmit stream separation through linear processing. Moreover, it can achieve maximum diversity gains of N/sub T/N/sub R/(L+1) for every user in the system, irrespective of the system load, where N/sub T/ is the number of transmit antennas, N/sub R/ the number of receive antennas, and L the order of the underlying multipath channels. In addition, it turns out that a low-complexity linear receiver based on frequency-domain equalization comes close to extracting the full diversity in reduced, as well as full load settings. In this perspective, we also develop two (recursive) least squares methods for direct equalizer design. Simulation results demonstrate the outstanding performance of the proposed transceiver compared to competing alternatives.

Microelectromechanical systems (MEMS) components are gradually finding their way in communication applications. To fully understand their behavior in electrical circuits, an interpretable model is required that, in addition, can be simulated efficiently. This paper presents a model for a MEMS variable capacitor (varicap), that can be evaluated much more efficiently and equally accurate during circuit simulation than the differential equations that are normally used to describe this component. The model, based on Volterra series, describes the frequency dependence (e.g., the mechanical resonance) in combination with the nonlinear behavior of the MEMS varicap. The model is simple enough such that it can be interpreted by designers who want to use the MEMS varicap in RF communication circuits.

In the design of embedded systems, a processor architecture is a tradeoff between energy consumption, area, speed, design time, and flexibility to cope with future design changes. New versions in a product generation may require small design changes in any part of the design. We propose a novel processor architecture concept, which provides the flexibility needed in practice at a reduced power and performance cost compared to a fully programmable processor. The crucial element is a novel protocol combining an efficient, customized component with a flexible processor into a hybrid architecture.

The two major obstacles toward high-capacity indoor wireless networks are distortion due to the indoor channel and the limited bandwidth which necessitates a high spectral efficiency. A combined orthogonal frequency division multiplexing (OFDM)/spatial division multiple access (SDMA) approach can efficiently tackle both obstacles and paves the way for cheap, high-capacity wireless indoor networks. The channel distortion due to multipath propagation is efficiently mitigated with OFDM while the bandwidth efficiency can be increased with the use of SDMA. However, to keep the cost of an indoor wireless network comparable to its wired counterpart's cost, low-complexity SDMA processors with good performance are of special interest. In this paper, we propose a new multiuser SDMA detector which is designed for constant modulus signals. This constrained least squares (CLS) receiver, which deterministically exploits the constant modulus nature of the subcarrier modulation to achieve better separation, is compared in terms of performance and complexity with the zero forcing (ZF) and the minimum mean square error (MMSE) receiver. Additionally, since the CLS detector relies on reliable channel knowledge at the receiver, we propose a strategy for estimating the multiple input multiple output (MIMO) channels. Simulations for a Hiperlan II-based case-study show that the CLS detector significantly outperforms the ZF detector and comes close to the performance of the MMSE detector for QPSK. For higher order M-PSK, the CLS detector outperforms the MMSF detector. Furthermore, the estimation complexity for the CLS detector is substantially lower than that for the MMSE detector which additionally requires estimation of the noise power.

In a synchronous clock distribution network with zero latencies, digital circuits switch simultaneously on the clock edge, therefore they generate substrate noise due to the sharp peaks on the supply current. We present a novel methodology optimizing the clock tree for less substrate generation by using statistical single cycle supply current profiles computed for every clock region taking the timing constraints into account. Our methodology is novel as it uses an error-driven compressed data set during the optimization over a number of clock regions specified for a significant reduction in substrate noise. It also produces a quality analysis of the computed latencies as a function of the clock skew. The experimental results show >x2 reduction of substrate noise generation from the circuits having four clock regions of which the latencies are optimized.

Summary form only given, as follows. While process technologists are obsessed to follow Moore's curve down to nanoscale dimensions, design technologists are confronted with gigascale complexity. On the other hand, post-PC and post dotcom products require zero cost, zero energy yet software programmable novel system architectures to be sold in huge volumes and to be designed in exponentially decreasing time. How do we cope with these novel silicon architectures? What challenges in research does this create? How to create the necessary tools and skills and how to organize research and education in a world driven by shareholders value? Can you spare half an hour to reflect on these challenges to the design community?

Coarse-grained reconfigurable architectures have become increasingly important in recent years. Automatic design or compiling tools are essential to their success. In this paper, we present a retargetable compiler for a family of coarse-grained reconfigurable architectures. Several key issues are addressed. Program analysis and transformation prepare dataflow for scheduling. Architecture abstraction generates an internal graph representation from a concrete architecture description. A modulo scheduling algorithm is key to exploit parallelism and achieve high performance. The experimental results show up to 28.7 instructions per cycle (IPC) over tested kernels.

The two major obstacles toward high-capacity indoor wireless networks are distortion due to the indoor channel and the limited availability of bandwidth which necessitates a high spectral efficiency. A combined orthogonal-frequency division multiplexing/spatial-diversity multiple access (OFDM/SDMA) approach can effectively tackle both obstacles. The channel distortion due to multipath propagation is easily mitigated with OFDM while the bandwidth efficiency can be increased with the use of SDMA. In order to keep the network's cost acceptable, simplified SDMA processors are preferred over the exponentially complex optimal maximum-likelihood processors. However, these simplified processors perform significantly worse than the optimal ones in terms of average bit error rate (BER). In this paper, we show that by adapting the constellation sizes applied on the individual subcarriers to the channel conditions, the performance of OFDM/SDMA processors can be significantly enhanced. In the uplink, we derive simple closed-form equations for the optimal constellation sizes for both a simple linear minimum mean-square error (MMSE) detector and for a nonlinear MMSE decision feedback equalizer (DFE) detector. Furthermore, for each detector, we introduce a simplified loading algorithm which lowers the computational and signaling complexity substantially at a small performance penalty. In the downlink, we study the dual precoders of the uplink detectors, respectively, the linear MMSE precoder and the nonlinear Tomlinson-Harashima (TH) MMSE-based precoder. For both precoders, we derive expressions for the optimal and the simplified constellation sizes. Additionally, we show that in time-division duplexing systems, the constellation distribution of a set of dual detectors/precoders is identical for up- and downlink, which effectively halves the computational complexity of adaptive loading. In the fully loaded uplink, the proposed adaptive loading algorithm results in a gain of 9 dB for a BER=10/sup -3/ for the linear MMSE detector and a gain of 4.5 dB for the nonlinear MMSE-DFE detector. In the fully loaded downlink, a gain of 6.3 dB is achieved for the MMSE precoder and 5.5 dB for the TH-MMSE precoder.

We present a new exploration and optimization method at the system level to select customized implementations for dynamic data sets, as encountered in telecom network, database, and multimedia applications. Our method fits in the context of embedded system synthesis for such applications, and enables to further raise the abstraction level of the initial specification, where dynamic data sets can be specified without low-level details. Our method is suited for hardware and software implementations. In this paper, it mainly aims at minimizing the average memory power, although it can also be driven by other cost functions such as memory size and performance. Compared with existing methods, for large dynamic data sets, it can save up to 90% of the average memory power, while still saving up to 80% of the average memory size.

A systematic methodology for the reduction of the power consumption and the execution time in realizations of multimedia applications on programmable processors is proposed. The methodology is mainly based on the application of data transfer and storage optimizing code transformations to a high-level description of the target algorithm. Application of the code transformations according to the proposed order moves the main part of the memory accesses from the large background memories (lying possibly off-chip) to smaller ones (on-chip) or even to foreground storage. Data cache performance is improved as well. In this way the power consumption in the data memory hierarchy of the target processor and in the related interconnect, which forms a significant part of the total power budget of the system, is significantly reduced. Execution time and the power consumption due to instruction storage and transfers are reduced as well after the application of the proposed methodology. Experimental results from real-life applications prove the effectiveness of the proposed methodology.

A virtual interface between Java and FPGA for networked reconfiguration is presented. Through the Java/FPGA interface, Java applications can exploit hardware accelerators with FPGAs for both functional flexibility and performance acceleration. At the same time, the interface is platform independent. It enables the networked application developers to design their applications with only one interface in mind when considering the interfacing issues. The virtual interface is part of our work to build a platform-independent deployment framework for the networked services. In the framework, both the software and hardware components of services can be platform independently described and deployed.

Substrate noise generated by large digital circuits degrades the performance of analog circuits sharing the same substrate. Existing approaches usually extract the model of the substrate from the layout information and then simulate the extracted transistor-level netlist with this substrate model using a transistor-level simulator. For large digital circuits, the substrate simulation is however not feasible with a transistor-level simulator. In our previous work, it has been demonstrated that efficient and accurate simulation of substrate noise generation at gate-level is feasible. In this paper several important extensions to our previous work are introduced: modeling of I/O cells, modeling of input transition time and load dependency and the extraction methodology of an equivalent substrate model within multiple supply domains. Experimental results show an improved accuracy (6.3% error on RMS substrate voltage with respect to a full SPICE level simulation) with these extensions, while maintaining a large speedup with respect to SPICE simulations.

Cache misses form a major bottleneck for real-time multimedia applications due to the off-chip accesses to the main memory. This results in both a major access bandwidth overhead (and related power consumption) as well as performance penalties. In this paper, we propose a new technique for organizing data in the main memory for data dominated multimedia applications so as to reduce majority of the conflict cache misses. The focus of this paper is on the formal and heuristic algorithms we use to steer the data layout decisions and the experimental results obtained using a prototype tool. Experiments on real-life demonstrators illustrate that we are able to reduce up to 82% of the conflict misses for applications that are already aggressively transformed at the source-level. At the same time, we also reduce the off-chip data accesses by up to 78% and combined with address optimizations we are able to reduce the execution time. Thus our approach is complimentary to the more conventional way of reducing misses by reorganizing the execution order.

This paper summarizes a new methodology for the design of concurrent dynamic real-time embedded systems. An embedded system can be specified at a grey-box abstraction level in a combined MTG-CDFG model. The authors believe that task concurrency management can be implemented in four major steps. Firstly, the grey box model is built, including the necessary concurrency extraction. Then transformations are applied on the specified MTG-CDFG to increase the opportunities for concurrency exploration and cost minimization. Then static scheduling will be applied on the design time analyzable parts of the grey-box model, including processor assignment in the multiple processor context. Finally, a dynamic scheduler will schedule the dynamic and coarse-grain constructs at run time on the given platform while making trade-offs based on Pareto curves.

Article Share on Solving large scale assignment problems in high-level synthesis by approximative quadratic programming Authors: Florin Balasa University of Illinois at Chicago, Dept. EECS, Chicago, IL University of Illinois at Chicago, Dept. EECS, Chicago, ILView Profile , Werner Geurts Target Compiler Technologies, Leuven, B-3001, Belgium Target Compiler Technologies, Leuven, B-3001, BelgiumView Profile , Francky Catthoor Interuniv. Microelectronics Center, Katholieke Universiteit Leuven Interuniv. Microelectronics Center, Katholieke Universiteit LeuvenView Profile , Hugo De Man Interuniv. Microelectronics Center, Katholieke Universiteit Leuven Interuniv. Microelectronics Center, Katholieke Universiteit LeuvenView Profile Authors Info & Claims GLSVLSI '01: Proceedings of the 11th Great Lakes symposium on VLSIMarch 2001 Pages 19–24https://doi.org/10.1145/368122.368149Online:01 March 2001Publication History 1citation163DownloadsMetricsTotal Citations1Total Downloads163Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In the forward link of WCDMA systems, the multipath propagation channel destroys the orthogonality of the spreading codes and therefore causes multi-user interference (MUI). We propose new training-based and semi-blind space-time chip equalizer receivers for the forward link of WCDMA systems with a continuous code-multiplexed pilot. Both least-squares (LS) algorithms for block processing and recursive least-squares (RLS) algorithms for adaptive processing are derived. The proposed receivers can track fast fading multipath channels and outperform the RAKE receiver with perfect channel knowledge.

Future broadband satellite systems, supporting user terminal mobility, will employ regenerative LEO satellites with multiple spot-beams per satellite. MC-CDMA is a promising multiple-access technique for these systems, because it exploits the advantages of both OFDM and CDMA. However, the detector design for the reverse link, taking into account both intra- and inter-beam interference, is still an open area of research. In this paper, we propose a new MC-CDMA multiuser detector, that can deal with both intra- and inter-beam interference in frequency-selective fading channels. The ideal detector consists of an initial linear MMSE stage and possibly multiple nonlinear pcPIC-MMSE stages, that act on a per-carrier basis. Furthermore, to take care of its initialisation, we devised a training-based fully adaptive detector, that does not require any a priori information and achieves the same steady-state performance as the ideal detector. The MMSE/pcPIC-MMSE detector outperforms a classical MMSE detector by 4 dB for a BER of 10/sup -2/, while still maintaining linear complexity in the number of users.

In the forward link of WCDMA systems, multipath propagation destroys the orthogonality of the user signals and causes multi-user interference (MUI). Channel equalization can restore the orthogonality and suppress the MUI. However, adaptive implementations of the chip equalizer receiver that can track time-varying multipath channels are hard to realize in practice. In this paper, we propose new training-based and semi-blind space-time chip equalizer receivers for the forward link of WCDMA systems employing long spreading codes and a time-multiplexed pilot. The proposed receivers exploit the presence of user specific pilot symbols in the so-called dedicated physical control channel (DPCCH) of the Universal Terrestrial Radio Access (UTRA). Whereas the DPCCH-trained receiver only assumes knowledge of the desired user's pilot symbols and code sequence in a training-based cost function, the enhanced DPCCH-trained receiver assumes knowledge of each active user's pilot symbols and code sequence in a semi-blind cost function. For both receivers, we derive a least squares algorithm for block processing and a recursive least squares algorithm for adaptive processing. Both receivers can track time-varying multipath channels and outperform the conventional RAKE receiver with perfect channel knowledge. The enhanced DPCCH-trained chip equalizer receiver outperforms the regular DPCCH-trained chip equalizer receiver and comes close to the performance of the ideal fully-trained chip equalizer receiver.

We show a new approach for globally applied automatic loop transformations, to optimize data transfer and storage in embedded multi-media applications.The approach makes use of an extended polytope model, in which loop nests are modeled by polytopes, and all polytopes are considered at the same time to perform global loop transformations.Transformations are done in two separate steps: rst all polytopes are placed in a common iteration space, and afterwards an ordering (for single-processor target architectures) or a space-time mapping (for parallel target architectures) is de ned in that common space.The methodology is illustrated on a simple example, and preliminary results for some representative applications are given.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific

In this paper we propose a system-level design environment, aimed at System-on-Chip (SOC) designs, including real-time embedded software. While many SOC modeling languages originate from hardware description languages, and thus tend to describe statical architectures, we observe that embedded software makes SOC designs essentially dynamic, and so a SOC modeling environment must include dynamic behavior. Such behavior is analogous to the services an Operating System offers in the software world, hence the term System-on-Chip Operating System (SoCOS).

In embedded data-dominated applications a global system-level data transfer and storage exploration phase is crucial in obtaining an efficient solution. We have developed a novel formalism to describe reusable blocks such that the essential part of the design exploration freedom is retained. This formalism is the basis for a system-level reuse methodology which allows to reuse large parts of the design as structural VHDL and describes the costly data access related constructs at higher levels in the code hierarchy. Compared to a reuse approach based on fixed blocks, considerable power and area savings can be obtained as demonstrated on real-life video and modem applications.

Two major technical challenges in the design of future broadband wireless networks are the impairments of the propagation channel and the need for spectral efficiency. We previously proposed a combined OFDM/SDMA approach that mitigates the channel impairments by orthogonal frequency division multiplexing (OFDM) with cyclic prefix insertion and that achieves a high spectral efficiency by space division multiple access (SDMA). However, because of the multicarrier modulation, this approach requires high-backoff power amplifiers in the analog frontend. We present a SC-FD-SDMA basestation, which avoids these expensive amplifiers by using constant-envelope single-carrier (SC) modulation and still features the advantages of frequency-domain (FD) multipath mitigation and SDMA. We pay special attention to the initialization of such basestation and its fixed point requirements, since they are critical aspects of any realistic implementation. A case-study shows how SC-FD-SDMA enables a 100 Mbps wireless LAN with a bandwidth efficiency of 8 bps/Hz and an uncoded BER of 10/sup -3/ at 13.5 dB.

No abstract available.

The execution of multimedia applications on a microprocessor greatly benefits from hardware acceleration, both in terms of speed and energy consumption. While the basic functionality implemented in these accelerators remains constant over different product versions, small changes are still often required. With the proposed architecture and protocol, the accelerator hardware has the performance and cost benefits of a hardwired solution, while featuring all the flexibility needed in practice. From a user point of view, the entire application is still programmable.

Two major technical challenges in the design of future broadband wireless networks are the impairments of the propagation channel and the need for spectral efficiency. To mitigate the channel impairments, orthogonal frequency division multiplexing (OFDM) can be used, which transforms a frequency-selective channel in a set of frequency-flat channels. On the other hand, to achieve higher spectral efficiency, space division multiple access (SDMA) can be used, which reuses bandwidth by multiplexing signals based on their spatial signature. In this paper, we present a combined OFDM/SDMA approach that couples the capabilities of the two techniques to tackle both challenges at once. We propose four algorithms, ranging from a low-complexity linear minimum mean squared error (MMSE) solution to the optimal maximum likelihood (ML) detector. By applying per-carrier successive interference cancellation (pcSIC), initially proposed for DS-CDMA, and introducing selective state insertion (SI), we achieve a good tradeoff between performance and complexity. A case study demonstrates that, compared to the MMSE approach, our pcSIC-SI-OFDM/SDMA algorithm obtains a performance gain of 10 dB for a BER of 10/sup -3/, while it is only three times more complex. On the other hand, it is two orders of magnitude less complex than the ML approach, for a performance penalty of only 2 dB.

In embedded data-dominated applications, a global system-level data transfer and storage exploration phase is crucial in obtaining a cost- and performance-efficient solution. We have developed a novel formalism to describe reusable blocks such that the essential part of the design exploration freedom is retained. This formalism is the basis for a system-level reuse methodology which allows reusing large parts of the design as heavily optimized structural VHDL or assembly code and describes the costly data access-related constructs at higher levels in the code hierarchy. Compared to a reuse approach based on fixed blocks, considerable power and area savings can be obtained, as demonstrated on real-life video and modem applications.

Although a single-chip solution seems to be ultimate goal for the design of wireless transceivers, there are many reasons to believe that this approach is not feasible for high performance applications. Especially the RF front-ends of these transceivers require components that are difficult to combine into one single chip. As an alternative we propose a single-package solution that contains different components that are interconnected with a multi-chip module (MCM) interconnect technology. By implementing passive front-end components directly into this interconnect technology, instead of using external commercial components, a cost-effective realization of the front-end can be obtained with a higher performance or a lower power consumption.

A methodology for power efficient partitioning of real-time datadominated system specifications is presented. The proposed methodology aims at reducing the memory requirements in realizations of such applications by applying extensive code transformations in the initial system specification before partitioning over processors. This reorganization basically aligns the data production and consumption between the different procedures of the initial specification thus reducing the memory size requirements (and the resulting power) of the system's realizations especially those in the interfaces between different processors. The main novel contribution is that performance issues are explicitly taken into account during power oriented system-level transformations. The proposed methodology can be applied both in a parallel (programmable) processor context and also in heterogeneous hardware-software architectures.

Deep-submicron technology combined with the tremendous growth of global networking leads to SoC and requires a rethinking of communication architectures and disciplinary design methodologies. This creates the need for SoC engineers to be able to bridge the gap between system level concepts and their implementation in heterogeneous silicon architectures. The concept of a design center is introduced where academic staff and students team-up around visionary information technology design projects. Building actual software-hardware prototype demonstrators is undertaken as a means to create new methodologies that give rise to new CAE tools, libraries, teaching material and training courses available over the network. A design center is the ideal environment for educating the SoC engineer. In such schools emphasis is on broad education in the basics of computing, communications and components. Design practice (including non-technical skills) are learned by team-based integrated projects in product design.

Data transfers and storage are crucial cost factors in multimedia systems. Systematic methodologies are needed to obtain dramatic reductions in terms of power, area and cycle count. Upcoming multimedia processing applications will require high memory bandwidth. In this paper, we estimate that a software reference implementation of an MPEG-4 video encoder typically requires five Gtransfers/s to main memory for a simple profile level L2. This shows a clear need for optimization and the use of intermediate memory stages. By applying our ACROPOLIS methodology, developed mainly to relieve this data access bottleneck, we have arrived at an implementation which needs a factor 65 less background accesses. In addition, we also show that we can heavily improve on the memory transfers, without sacrificing speed (even gaining about 10% on cache misses and cycles for a DEC Alpha), by aggressive source code transformations.

Application studies in the areas of image- and video-processing indicate that between 50%-80% of the power cost in these systems is due to data storage and transfers. This is especially true for multiprocessor realizations because conventional parallelization methods ignore the power cost and focus only on performance. However, the power consumption also heavily depends on the way a system is parallelized. To reduce this dominant cost, we propose to address the system-level storage organization for the multidimensional signals as a first step in mapping these applications, before the parallelization or partitioning decisions (in particular, before the hardware/software (HW/SW) partitioning, which is traditionally done too early in the design trajectory). Our methodology is illustrated on a parallel quadtree-structured difference pulse-code modulation video codec.

A folded very large scale integration (VLSI) architecture is presented for the implementation of the two-dimensional discrete wavelet transform, without constraints on the choice of the wavelet-filter bank. The proposed architecture is dedicated to flexible block-oriented image processing, such as adaptive vector quantization used in wavelet image coding. We show that reading the image along a two-dimensional (2-D) pseudo-fractal scan creates a very modular and regular data flow and, therefore, considerably reduces the folding complexity and memory requirements for VLSI implementation. This leads to significant area savings for on-chip storage (up to a factor of two) and reduces the power consumption. Furthermore, data scheduling and memory management remain very simple. The end result is an efficient VLSI implementation with a reduced area cost compared to the conventional approaches, reading the input data line by line.

In this paper, we present the problem of storage bandwidth optimization (SBO) in VLSI system realizations. Our goal is to minimize the required memory bandwidth within the given cycle budget by adding ordering constraints to the flow graph. This allows the subsequent memory allocation and assignment tasks to come up with a cheaper memory architecture with less memories and memory ports. The importance and the effect of SBO is shown on realistic examples both in the video and asynchronous transfer-mode (ATM) domains. We show that it is important to take into account which data is being accessed in parallel, instead of only considering the number of simultaneous memory accesses. Our problem formulation leads to the optimization of a conflict (hyper) graph. For the target domain of ATM, only flat graphs without loops have to be treated. For this subproblem, a prototype tool has been implemented to demonstrate the feasibility of automating this important system design step.

Matisse is a design flow intended for developing embedded systems characterize dby tight inter action b etwe encontrol and data-flow behavior, intensive data storage and tr ansfer, dynamic creation of data, and stringent real-time requirements. Matisse bridges the gap from a system specification, using a cocurr ent obje ct-oriented language, to an optimize d embedded single-chip HW/SW implementation. Matisse supp orts stepwise system-level exploration and refinement, memory architecture exploration, and gradualincorporation of timing constr aints b efore going to tr aditional tools for HW synthesis, SW compilation, and HW/SW interprocessor communication synthesis. Application of Matisse on telecom protocol processing systems shows significant improvements in area usage and power c onsumption.

In this p ap er we pr esent our novelpower exploration methodolo gy for applic ations with dynamic data types. Our methodolo gy is crucial to obtain effe ctive solutions in an emb edded (HW or SW) processor context. The c ontributionsare twofold. First we define the complete search sp ace for Virtual Memory Management (VMM) mechanisms in a structured way with orthogonal de cision tr eesSe condly we present our systematic methodolo gy for explor ation of the maximal power that takes into account characteristics of the application to he avily prune the search space guiding the choies of a VMM mechanism. Finally we demonstrate for two industrial examples that power can vary consider ably dep ending on the VMM chosen. Moreover these exp eriments show the effe ctiveness of our exploration methodolo gy.

A program transformation strategy is presented that is able to reduce the buffer size and power consumption for a relatively large class of (pseudo)regular data-dominated signal processing algorithms. Our methodology is targeted toward an implementation on programmable processors, but most of the principles remain valid for a custom processor implementation. As power and area cost are crucial in the context of embedded multimedia applications, this strategy can be very valuable. The feasibility of our approach is demonstrated on a representative high-speed video processing algorithm for which we obtain a substantial reduction of the area and power consumption compared to the classical approaches.

Data-transfer intensive applications typically contain heavily accessed memories involving considerable arithmetic for the computation and the selection of the different memory access pointers. This data processing, namely addressing, becomes dominant in the overall arithmetic cost and it has to be executed under very tight timing constraints. Different high-level optimizing alternatives suitable for addressing are explored in our Adopt methodology and prototype tool environment to reduce the addressing overhead. They include address expression splitting/clustering, induction variable analysis, target architecture selection, and global-scope algebraic optimization. In addition, some steps aiming to reduce at the system level the time-multiplexed address unit cost, are also incorporated for area and power efficiency. The techniques are demonstrated on test-vehicles representative of real-life applications, shelving important savings on the overall arithmetic cost.

Efficient use of an optimized custom memory hierarchy to exploit temporal locality in the data accesses can have a very large impact on the power consumption in data dominated applications. In the past, experiments have demonstrated that this task is crucial in a complete low-power memory management methodology. But effective formalized techniques to deal with this specific task have not been addressed yet. In this paper, the surprisingly large design freedom available for the basic problem is explored in-depth and the outline of a systematic solution methodology is proposed. The efficiency of the methodology is illustrated on a real-life motion estimation application. The results obtained for this application show power reductions of about 85% for the memory subsystem compared to the case without a custom memory hierarchy. These large gains justify that data reuse and memory hierarchy decisions should be taken early in the design flow.

In this paper we present the second stage of a two-phase strategy for reducing the required background memory sizes for a large class of data-intensive multimedia applications. This strategy is particularly useful in an embedded application context, where memory size and the corresponding power consumption are the main cost factors together with data transfers. Our strategy optimizes the storage order of arrays in memory by trying to improve the reuse of memory locations, as well for elements of the same array as for elements of different arrays. Although size reduction is the main objective, an added benefit is a reduced power consumption due to the decreased capacitive load of the memories. The memory size reduction task is part of an overall memory size and power reduction methodology called ATOMIUM in which other tasks can increase its effectiveness (e.g. loop, transformations), but it can also be used on a stand-alone base. The effectiveness of our approach is demonstrated by experimental results for some real-life multimedia applications, for which a considerable memory size reduction was obtained.

Exploitation of deep-submicron technology will dependcritically on the availability of global system engineers ableto bridge the gap between software-centric system thinkingand hardware-software implementation of it in novel siliconarchitectures. This requires a rethinking of presentengineering schools which are not well equipped to tackleglobal system engineering aspects. The concept of designinstitute is introduced where, based on visionary systemdesign demonstrators, new methodologies, tools, librariesand courses are created and distributed over the globalnetwork. Design institutes provide a learning school fornew design paradigms and form the ideal environment forthe education of global system designers.

We describe a system design methodology well-suited for telecom network applications. This methodology is being developed into a compiler called Matisse. The entry point for this methodology is a system specification model that is first compiled into an abstract machine. The abstract machine is implementation-independent, which permits the exploration of different embedded hardware/software realizations. The proposed methodology and tools bridge the gap between system specification and synthesis tools commercially available. This yields several advantages over the design methodology currently used in industry.

Article Formalized methodology for data reuse exploration in hierarchical memory mappings Share on Authors: J. Ph. Diguet IMEC, Kapeldreef 75, B-3001 Leuven, Belgium IMEC, Kapeldreef 75, B-3001 Leuven, BelgiumView Profile , S. Wuytack IMEC, Kapeldreef 75, B-3001 Leuven, Belgium IMEC, Kapeldreef 75, B-3001 Leuven, BelgiumView Profile , F. Catthoor IMEC, Kapeldreef 75, B-3001 Leuven, Belgium IMEC, Kapeldreef 75, B-3001 Leuven, BelgiumView Profile , H. De Man IMEC, Kapeldreef 75, B-3001 Leuven, Belgium IMEC, Kapeldreef 75, B-3001 Leuven, BelgiumView Profile Authors Info & Claims ISLPED '97: Proceedings of the 1997 international symposium on Low power electronics and designAugust 1997 Pages 30–35https://doi.org/10.1145/263272.263278Online:01 August 1997Publication History 46citation185DownloadsMetricsTotal Citations46Total Downloads185Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We reflect on the nature of digital telecommunication systems. We argue that these systems require, by nature, a heterogeneous specification and an implementation with heterogeneous architectural styles. CoWare is a hardware/software co-design environment based on a data model that allows to specify, simulate, and synthesize heterogeneous hardware/software architectures from a heterogeneous specification. CoWare is based on the principle of encapsulation of existing hardware and software compilers and special attention is paid to the interactive synthesis of hardware/software and hardware/hardware interfaces. The principles of CoWare are illustrated by the design process of a spread-spectrum receiver for a pager system.

Image and video processing applications involve large multidimensional signals which have to be stored in memory modules. In application-specific architectures for real-time multidimensional signal processing, a significant cost in terms of chip area and power consumption is due to these background memory units. The multidimensional signals are usually modeled in behavioral descriptions with array variables. In the algorithmic specifications of our target applications, many of the array references cover large amounts of scalars. Therefore, the efficient handling of array references in the specifications for image and video processing is crucial for obtaining low cost memory allocation solutions. This paper addresses a central problem which arises when handling the array variables in behavioral specifications: the computation of the number of scalars covered by an array reference. This problem is closely related to the computation of dependences in data-flow analysis. The novel algorithms proposed in this paper are embedded in the ATOMIUM environment-a memory management system for multidimensional signal processing.

To construct complete systems on silicon, application specific DSP accelerators are needed to speed up the execution of high throughput DSP algorithms. In this paper, a methodology is presented to synthesize high throughput DSP functions into accelerator processors containing a datapath of highly pipelined, bit-parallel hardware units. Emphasis is put on the definition of a controller architecture that allows efficient run-time schedules of these DSP algorithms on such highly pipelined data paths. The methodology is illustrated by means of an image encoding filter bank.

Deep sub-micron processing technologies have enabled the implementation of new application-specificembeddedarchitecturesthat integrate multiple software programmable processors (e.g. DSPs, microcontrollers) and dedicated hardware components together onto a single cost-efficient IC. These application-specific architectures are emerging as a key design solution to today's microelectronics design problems, which are being driven by emerging applications in the areas of wireless communication, broadband networking, and multimedia computing. However, the constructionof these customized heterogeneous multiprocessor architectures, while ensuring that the hardware and software parts communicate correctly, is a tremendously difficult and highly error proned task with little or no tool support. In this paper, we present a solution to this embedded architecture cosynthesis problem based on an orchestrated combination of architectural strategies, parameterized libraries, and software tool support....

Heterogeneous embedded multiprocessor architectures are becoming more prominent as a key design solution to today's microelectronics design problems.These application-specific architectures integrate multiple software programmable processors and dedicated hardwarecomponents together on to a single cost-efficient IC.In contrast to general-purpose computer systems, embedded systems are designed and optimized to provide specific functionality, using possibly a combination of different classes of processors (e.g.DSPs, microcontrollers) from different vendors.While these customized heterogeneous multiprocessor architectures offer designers new possibilities to tradeoff programmability, processing performance, power dissipation, and design turnaround time, there is currently a lack of tools to support the programming of these architectures.In this paper, we consider the problem of providing real-time kernel support for managing the concurrent software tasks that are distributed over a set of processorsin an application-specific multiprocessorarchitecture.This is complementary to current research activities that aim to provide efficient retargetable code generation [8,11,10] for a broad range of embedded processors.

In this paper we present our power exploration methodology for data dominated video applications. This formalized methodology is based on the observation that for this type of application the power consumption is dominated by the memory architecture. Hence, the first exploration stage should be to come up with an optimized memory organisation. Other important observations are that the power consumption of the address generators is of the same magnitude as that of the data-paths and that the address generators are better optimized using specialized techniques.

In this paper, we present a novel approach to model the search space for the custom implementation of set data types, a data type that is commonly found in important application domains such as network component realizations and database applications. The main objective is to arrive at power efficient realizations of these data types in custom data structures, but the model can also be used with nonpower cost functions. Based on the model, we propose an efficient optimization method for finding the implementation with minimum power consumption without performing an exhaustive scan of the search space. The range of power costs for different solutions can easily span four orders of magnitude, so a near optimal solution is crucial. This paper also strongly contributes to our overall goal of a higher level of specification and shorter design cycles for table-based memory organizations for applications where these data types are frequently used. The proposed model and methodology are suited for both hardware and software realizations.

Different options for gradually building up DSP expertise are discussed. First the importance of DSP design education in universities and polytechnic schools is explained. Thereafter the paper focuses on the role that an independent research institute can play in the education towards industry in DSP design. It is shown how DSP system design and implementation expertise is intensified by following different steps in the learning process. This is demonstrated by means of several experiments that have taken place in the scope of the "DSP Valley" initiative and the "Large Installations Plan" of the "Human Capital and Mobility" Programme, which is a programme set up by the European Community.

In this paper, several DSP system design principles are presented which are valid for a large class of memory-intensive algorithms. Our main focus lies on the optimization of the memory and I/O, since these are dominant cost factors in the domain of video and imaging applications. This has resulted in several formalizable mapping principles, which allow to prevent the memory from becoming a bottleneck. First, it as shown that for this class of applications, compile-time data caching decisions not only have a large effect on the performance, but also can have an even larger effect on the overall system cost and power consumption. This is illustrated by means of experiments in which the whole range of no cache up to large cache sizes is scanned. Next, it is shown that when enforcing constant I/O rates to reduce buffer sizes, the area gain may be far more important than the small performance decrease associated with it. A technique to achieve this in an efficient way is proposed. The main test-vehicle which is used throughout the paper to demonstrate our approach is the class of motion estimation type algorithms.

In this paper, a novel technique for the synthesis of complex multifunctional units is presented. Given a set of functions, the goal is to minimize the area cost of a unit that can execute these functions. A set of primitive functional units is allocated and shared between operations which belong to different functions. In the presented approach, a bipartite matching-based technique is extended with a quadratic cost function which allows for a much more accurate modeling of interconnect cost compared to previous approaches. In the optimization process, functional unit type selection, instance allocation, and instance assignment are performed simultaneously. As an extension of the technique, a set of constraints which exclude solutions with false combinatorial cycles are also presented. The technique finds its main applicability in the synthesis of custom accelerator data paths in high throughput signal processing applications, as required in video, image processing, front end speech processing, and user-end telecom. In addition, it can be applied in the synthesis of the data path of domain-specific instruction set processors. Experiments show that highly optimized results can be obtained within acceptable CPU times.>

Memory cost is responsible for a large amount of the chip and/or board area of customized video and image processing system realizations. In this paper, we present a novel technique-founded on data-flow analysis which allows one to address the problem of background memory size evaluation for a given nonprocedural algorithm specification, operating on multidimensional signals with affine indexes. Most of the target applications are characterized by a huge number of signals, so a new polyhedral data-flow model operating on groups of scalar signals is proposed. These groups are obtained by a novel analytical partitioning technique, allowing to select a desired granularity, depending on the application complexity. The method incorporates a way to tradeoff memory size with computational and controller complexity.>

Many real-time signal processing applications are dominated by iterative loop constructs which exhibit a large amount of parallelism. In general, a realisation matched to the required rate of these applications exploits only a relatively small part of the parallelism available in the algorithm. This paper addresses the important problem of selecting the appropriate algorithmic-level decisions, in particular loop manipulations and the like, to arrive at an area-optimized specification for use in register-transfer level synthesis tools. One of the crucial cost factors in this optimisation is memory storage related. An effective model and methodology are proposed to derive an optimized architecture with fully matched throughput, while avoiding a full traversal of the large search space. The effectiveness of our approach is substantiated with several realistic test cases.>

This paper addresses the problem of deriving optimised array architectures for real-time multi-dimensional signal processing systems, as occurring in image, speech and video applications. The starting point is a set of Weak Single Assignment Codes. For this abstract specification, we solve the difficult task of finding a globally optimised architecture with matched throughput while avoiding an explosion of the search space. The cost function not only includes the data-path area but incorporates also the crucial foreground and background memory storage. The effectiveness of our solution has been substantiated with realistic test cases.>

An important practical approach to automatic verification of finite state concurrent systems is temporal logic model checking.However, a major barrier towards wider application of such methods is the state explosion problem that often occurs during the composition of complex communicating systems.In addition to being large, many systems have very deep state spaces as well.In this paper, we propose an abstraction method based on time abstraction which can significantly reduce both the size as well as the depth of the state space that must be explored during model checking.It is especially suited for applications involving systems that are loosely coupled in the sense that communication activity is relatively sparse, such as applications involving DSPs, which have large intervals of autonomous processing, with communication activity in between.All properties expressible with the temporal logic CTL or CTL -X are strongly preserved under the proposed abstraction.In particular, we give a method that can replace a chain of states by a single state with a time label.The abstracted model is represented by means of a timed label transition system model.We give a composition algorithm for composing the individually time abstracted models to form a global model that can be converted back to a conventional, but potentially much reduced,state space suitable for model checking.Furthermore, a similar approach can be followed in dealing with wait states in which a system is idling while waiting for an escape signal.For many cases, our approach is successful in alleviating the state explosion problem that often arises in composition of communicating systems.

Functional verification of large digital synchronous circuits with respect to complex arithmetic and decision making algorithms is becoming more and more important. Indeed, today, system complexities are still growing, while time-to-marked is still decreasing. First-time-right circuits can be obtained by adequate checking tools for timing, electrical and behavioural verification. The paper presents new results for automatic functional verification, based on the SFG-tracing methodology, applied on applications for medium and high throughput DSP, such as audio, video and image processing. The verification is formal, complete, efficient and independent. It checks functional correctness across synthesis tasks such as allocation, scheduling, clustering, specific datapaths and controller generation, redundancy removal, buffering, pipelining, retiming, etc.>

In this paper, novel and optimized test strategies are presented for the generation of a set of predetermined test vectors on chip to be used as part of a BIST strategy for complex programmable data paths. Starting from a set of faults and a corresponding set of test vectors that cover these faults, the corresponding self-test hardware is determined automatically. For this purpose, a cellular automaton has been made. The CAD tool CAST accomplishes the synthesis of the cellular automaton and the self-test control logic, and evaluates the solution obtained. Dedicated test strategies for 1-pattern tests on the one hand and 1- and 2-pattern tests on the other hand have been developed. These new optimized strategies guarantee a BIST implementation with 100% stuck-at and stuck-open/close fault coverage for all detectable faults. They have been applied to data paths as used in an industrial-size speech processing vocoder design, developed with the silicon compiler CATHEDRAL-II.>

Memory cost is typically responsible for up to 80% of the chip and/or board area of most video and image processing system realizations. We present a novel technique - founded on data-flow analysis - which allows us to address the problem of background memory size evolution for a given nonprocedural algorithm specification. Usually, the number of signal instances is huge, so a new data-flow model grouping scalar signals in so-called basic sets is proposed. The method also incorporates a way to trade-off memory size with computational and controller complexity.

In this paper, a novel technique for the synthesis of complex multi-functional units is presented. Given a set of functions or instructions, the goal is to minimize the area cost of a unit that can execute these functions. A common set of primitive functional units is allocated and shared between operations which belong to different functions. In the present approach, a bipartite matching based technique is extended with a quadratic cost function which allows for a much more accurate modeling of interconnect cost compared to previous approaches. In the optimization process, functional unit type selection, instance allocation and instance assignment are performed simultaneously. As an extension of the technique, a set of constraints which exclude solutions with false combinatorial cycles are also presented. Experiments show that highly optimized results can be obtained with acceptable CPU times.

A method is presented for minimal sizing and verification of communication buffers in an environment of communicating concurrent processes. Methods described in the literature based on lifetime analysis techniques are mainly suited for sizing buffers in a network of processes with non-conditional interactions. We consider a more general problem where the execution of each process inherently depends on complex interactions with other processes as well as its internal conditional behavior and propose the use of implicit state enumeration techniques to solve buffer sizing and verification for this case. A model of the network of processes and buffers is introduced that is transformed into a network of finite state machines by modeling communicating buffers as counters. The transformed network forms a finite state space model on which implicit state space exploration algorithms are applied. The model allows us to handle the buffer sizing and verification problems with processes that operate on different, but related clocks. To reduce the complexity of the state space, abstraction techniques can be used to produce simplified versions of finite state machines that hide away unnecessarily detailed information. The feasibility of the proposed approach is demonstrated by a practical example.

Most research in logic synthesis has mainly focussed on area and delay optimizations. In this paper, we focus on the problem of mapping a technology independent circuit to a library of gates such that power is minimized while satisfying some user-specific timing constraints. Such timing constraints can often be rather stringent. We present a new technology mapping algorithm based on extending the dynamic programming paradigm for low-power under timing constraints. The effectiveness of this algorithm is based on two key observations: first, the switching activities of different nodes in a network can vary significantly; and second, the power contribution from a node is directly proportional to its switching activity. Therefore, it is possible to significantly optimize for low power by minimizing the fanout load of "high" switching nodes whenever possible, and trying to compensate instead for delay at the fanout of "lower" switching nodes. In addition to extending dynamic programming for low power under timing constraints, we have also developed optimization techniques that can be used to optimize further for low power and delay. We present experimental results on a large set of standard benchmarks to demonstrate that substantial optimization is possible.>

This paper presents a partial scan methodology suited for (pipelined) data paths described at the register-transfer level. The method is based on feedback elimination by making existing registers scanable or by adding extra transparent scan registers. An optimal set (in terms of area cost) of scan registers is selected using an exact branch and bound algorithm. Our symbolic test pattern generation technique can very effectively deal with the delay in the remaining sequential circuit parts. Furthermore, the symbolic test method makes various scan schemes possible which ensures a correct application and evaluation of the test vectors. They are discussed and compared in terms of their hardware requirements, test application times and test accuracy.>

Multidimensional (M-D) signal processing is a key component of most real-time signal and data processing VLSI systems in industry. Handling the M-D nature of data in an efficient way is crucial to arrive at acceptable system implementations. This aspect of design has often been ignored up to now in high-level synthesis. In this paper, a polyhedral based model is presented for the linear, piecewise linear and data dependent signal indexing as occurring in practical M-D signal processing applications. The model features a mathematical description of dependencies between individual operations and signal instances of M-D signals for all algorithms that contain signal indexing specified by a mixture of indexing by iterators and M-D signals embedded in the data flow. The exact modeling of M-D signal indexing is especially essential for deriving alternative control flow structures for a given data flow specification. Exploration of various control flow structures allows one to arrive at an efficient large-scale memory organization during high level synthesis of architectures, both in terms of storage locations and access order.>

A novel solution for the efficiency problems encountered in static timing verification is presented. The LSP algorithm is submitted to a critical analysis. A new hierarchy based approach is presented and its advantages and limitations are highlighted. Finally, some results on real life circuits are presented.>

Real-time DSP applications require a bit-true synthesis system to generate correct and efficient ASICs. This requires concise simulation and synthesis models, which are presented in this paper and exemplified for a non-restoring division operation. Such models are used in the synthesis library of bit-true Cathedral-II compiler, by which industrial size applications have been synthesised.>

A constraint satisfaction framework is proposed that can guarantee necessary and sufficient conditions for a state graph assignment to result in a transformed state graph that is race-free. Performing transformations at the state graph level has the advantage that the requirements imposed on the initial signal transition graph (STG) are very weak. Unlike previous methods, the initial STG need not be a live, safe, free choice net. The only requirement is that the corresponding initial state graph should be finite and connected, and have a consistent state assignment. Hence, a very broad range of STGs can be synthesized. The transformation achievable using the proposed framework correspond to very complex transformations on STGs. Even transformations that convert a free choice net into a correct non-free choice net, and a 1-safe net into a correct 2-safe net are feasible. Addition of transitions that do not follow the Petri net firing rule is also possible.>

A just-in-time (JIT) scheduling approach that incorporates register optimizations during scheduling is introduced. The technique is implemented in a hierarchical list scheduler, SMART, that is part of the Cathedral silicon compiler. Due to its computational complexity it can schedule hierarchical graphs containing a thousand or more operations. Experiments on relevant industrial examples show a gain in registers of more than 25% due to the proposed register optimization.>

In this paper, optimized test methodologies will be presented for the generation of a set of predetermined test vectors on chip to be used as part of a BIST strategy for complex programmable data paths. For this purpose, use has been made of a cellular automaton. CAST-2 accomplishes the synthesis of the cellular automaton and the self-test control logic, and evaluates the obtained cellular-automata based solution. Dedicated test strategies for one-pattern tests on the one hand and one- and two-pattern tests on the other hand have been developed. These optimized techniques guarantee a BET implementation with 100 % stuck-at and stuck-open/close fault coverage for all detectable faults. The method has been applied to the data paths of an industrial-size speech processing application, developed with the silicon compiler CATHEDRAL-11. The total data path self-test overhead in terms of area is economically acceptable in practice.

At the highest abstraction level, the specification of a data path consists of a number of interconnected abstract building blocks and a constraint on the minimal clock frequency. An algorithm which optimally selects hardware blocks for implementing these abstract building blocks is presented. A technique for hierarchical redistribution and insertion of pipeline registers is also presented. Finally, the two optimization tasks are combined. This combination makes the area tradeoff between the cost of additional speedup circuitry and pipeline registers possible. The techniques are based on accurate hierarchical timing models for the hardware blocks. The automation relieves the designer of the numerous, time-consuming critical path verifications and area evaluations that are required to explore the large design space. The implementation of the algorithms has resulted in a CAD tool called HANDEL, embedded in the data-path compiler CHOPIN.>

The proposed synthesis method starts from a graph-theoretic specification called a signal transition graph (STG). A method for transforming a given STG into an STG that satisfies the original timing behavior and that in addition obeys the unique state coding requirement is given. It is shown that in general, many valid solutions to this problem are possible. Therefore, an attempt is made to find a transformed STG that can be realized in a circuit with optimized speed and area.>

There are already good systematic design methodologies for the design of regular architectures starting from some algorithm description of an application. However, since the solution space of these methods can be quite large, heuristics must be built in the CAD tool that supports these design methodologies. The authors present the manual design of a motion estimation application using a systematic design methodology. The heuristics used to obtain an efficient design are indicated clearly. These heuristics consider efficient I/O, small intermediate memory structures and high average load of the PEs. The heuristic rules are incorporated in the Cathedral-IV CAD tools for the design of regular architectures.>

The goal of this paper is to extend the synthesis of real

An efficient ASIC architecture for the sequential stack decoding (SSD) algorithm used for channel coding is presented. It is different from the maximal likelihood (ML) Viterbi decoder (VD), mainly in the search for the correct memory path. Due to the dedicated memory organization, the storage space and required hardware can be reduced while the decoding efficiency remains almost the same. The proposed architecture results from step by step design of the I/O interface, high-level memory management, dedicated data paths, and controller. The ordering of these steps is important in optimizing the final solution. In addition, the construction of this hardware organization can be made by using the available hardware building blocks.>

A preprocessing technique for scheduling of large hierarchical and conditional DSP (digital signal processing) applications on a multiregister file architecture is described. Its goals are the optimization of the register cost and the reduction of the time complexity of complex techniques. These are both achieved by reducing the operation mobility through hierarchical clustering. The metric used in the clustering process is a multidimensional distance vector, based on a hierarchical and multidimensional extension of the min-flow algorithm. Network models are presented to take loop hierarchy and conditions into account. By scheduling the clusters separately, a large scheduling problem is divided into several smaller scheduling problems, which makes complex, optimal scheduling techniques feasible again for the scheduling of large graphs.>

The authors demonstrate that, next to allocation and scheduling of data path operations, efficient storage schemes and memory access are crucial in DSP (digital signal processor) ASIC (application-specific integrated circuit) design. For complex, medium throughput DSP applications, the authors have identified a strategy and important optimization tasks for compiling multidimensional data structures into distributed dual-port register files and single-port SRAM (static random-access memories). These techniques have been implemented in the Cathedral-II silicon compiler. The applicability of the proposed strategy has been demonstrated during the design of an 800 bit/s vocoder. Window computation reduced 23833 entries of 56 arrays to 932 locations.>

The SFG-tracing methodology addresses the automatic verification of digital synchronous circuit implementations as specified at the algorithmic level as signal- (SFG) or data flow graphs. The SFG-tracing methodology is a multi-level design verification paradigm that aims at bridging the gap between higher level specifications down to lower level implementations up to the transistor switch level. The concepts of the SFG-tracing methodology are illustrated by the automatic verification of a transistor level implementation of a small chip generated from its high level specification by the Cathedral-II silicon compiler. This application, although simple, includes a datapath, register files, a multi-branch micro coded controller, and additional circuitry as necessary for design for testability measures. This application illustrates the SFG-tracing verification methodology as applied to one member of a partitioned SFG behavioral specification. Experimental results on more complex, completely verified designs of 32000 transistors demonstrate the feasibility of the approach.>

Taking into account RC effects in VLSI simulation and verification systems, without seriously degrading their efficiency, requires preliminary data reduction. A tool, DARSI (data reduction system for interconnects), that can handle both polysilicon and diffusion resistive effects is presented. It contains the reduction scheme described by S.-L. Su et al. (Proc. IEEE Conf. Computer-Aided Design, p.270-3, 1986), a novel line-based reduction method, a novel loop reduction scheme, and a technique for identifying important diffusion resistors. The number of parasitic elements is considerably reduced, while guaranteeing delay errors to be less than a few percent. DARSI is implemented in a general-purpose rule-based verification environment for VLSI and has a nearly linear complexity. Application to several practical designs is also discussed.>

The optimal architectural design of the processing elements (PEs) for an application specific regular array (RA) is nontrivial if the application has a complex operation set. The authors present an approach that extends the conventional, linear time-space transformation for such cases. In application-specific-integrated-circuit (ASIC) architectures, one has the freedom to fine-tune all aspects of the architecture to optimize the throughput. Therefore, the PEs can be designed to match the throughput and to optimize the area-cost of an RA architecture. The method presented allows a free design of the PEs with internal pipelining of the data paths, hardware sharing of operators among operations, multicycle operators, and interleaving of the execution of different index points. Compared to methods that allow only parts of these experiments, the local area-time tradeoffs are now explicitly incorporated in the global space-time assignment problem.>

A system is presented which automatically generates layout of bit-sliced data paths in high performance DSP circuits. The system consists of a linear placement tool, a track assignment tool and detailed layout tools. In this paper we will present algorithms for linear placement of modules and routing track assignment across the modules. By taking advantage of the inherent structure of the circuits an A* based linear placement algorithm has produced better results compared to a simulated annealing based approach.

The Silage language is presented, together with a number of extensions to the original design which result in a powerful specification language and design environment for complex digital signal processing (DSP) systems. Aspects of Silage discussed include the applicative language, timing information and time-domain operations, data typing, and functional language, pragmatic directives, and loops and conditionals.>

Synthesis support for the design of asynchronous circuits is crucial. The synthesis method proposed starts from a graph-theoretic specification called a signal transition graph (STG). This work deals with the theoretical foundations of a method to transform a given STG into an STG that satisfies the original timing behavior and that in addition obeys the unique state coding requirement. It is shown that in general, many valid solutions to this problem are possible. The authors find a transformed STG that can be realized in a circuit with optimized speed and area.>

Pipelining and hardware selection are important optimization tasks in the design of high-performance data paths. At the highest abstraction level, the specification of a data path consists of a number of interconnected abstract building blocks and a constraint on the minimal required clock frequency. An algorithm which optimally selects hardware blocks from a library for implementing these abstract building blocks is presented, and a technique for hierarchical redistribution and insertion of pipeline registers is described. Finally, both optimization tasks are combined. This combination makes the area tradeoff between additional speed-up circuitry and pipeline registers possible.>

Novel rules to derive the signal flow in a VLSI-design are presented. This method is based on design-style independent logical principles, which makes it suitable for circuits that have not been checked on their electrical correctness. The use of two global principles has an important influence for more complicated designs, but also results in an efficiency penalty which may be kept reasonable by introducing graph reduction rules and heuristics. The different steps in the tagging process are explained and illustrated with examples. The dataflow rules are integrated in the overall DIALOG system to perform electrical verification, and they offer an invaluable help to break up the verification problem in subproblems and to cope with feedback in designs, by introducing the concept of intended unilateral blocks.>

A novel method for the generation of a set of predetermined test vectors on chip to be used as part of a BIST (built-in self-test) strategy for a class of data paths is presented. Given a set of faults and a corresponding set of test vectors which cover these faults, the corresponding self-test hardware will be generated automatically. For this purpose, use has been made of a cellular automaton which can be toggled between two rules. The CAD (computer-aided-design) program CAST accomplishes the synthesis of the cellular automaton, and the method has been applied to a data path used in the Cathedral-II/second silicon compilation environment. This technique makes it possible to obtain a BIST implementation with 100% stuck-at and stuck-open/close fault coverage for all detectable faults at the cost of an area overhead which is larger than that of conventional LFSR-(linear-feedback-shift-register) based methods but which is still acceptable.>

A typical digital image communication system based on a number of ASIC architectural designs is currently under development. After partitioning the complete system into several stages, each selected algorithm can be implemented on a single ASIC based on an efficient architectural style. The required throughput for high-performance data compression and channel coding has been obtained due to the optimization of the critical path in the architectural design. Input/output (I/O) operations, which create the bottleneck for many image-processing algorithms, are handled by a dedicated I/O interface unit. Construction of each dedicated data path in the architecture is based on a limited parameterizable functional building block (FBB) library. The dedicated data paths have been constructed by partitioning the initial signal flow graph (SFG) into compatible graphs and by matching the graphs in each partition onto a collection of time-multiplexed FBBs. Hierarchically partitioned controllers were used to meet the high-throughput requirements. The ASIC architectures proposed are oriented to broadband integrated services digital networks (B-ISDN) as well as high-performance digital image compression systems.>

The state of the art of compiling digital signal processing (DSP) algorithms into silicon is discussed. It is indicated how digital signal processing differs from numerical data processing, including the consequences for the synthesis tools. On the basis of a broad range of DSP applications, four classes of architectures are then distinguished to serve as templates for four different synthesis systems. Although each of these four silicon compilers is tuned to a specific class of applications in order to generate area-efficient chips, they all accept as input the same behavioral DSP specification. The four selected architectural styles are best characterized by hard-wired bit-serial data-paths, microcoded multiprocessors, cooperating bit-parallel data-paths, and regular arrays. The characteristics of the first three architectures are treated in more detail in a discussion of three different Cathedral synthesis environments for their respective design. A fourth Cathedral environment, aiming at the synthesis of regular arrays, is still in an early stage of development and is not discussed. The claims for the compilers are substantiated by typical designs.>

A new approach to the false path problem in timing verifiers is presented. This approach is based on the modeling of both the logic and timing behavior of a circuit. Using the logic propagation conditions associated with each delay, efficient algorithms have been developed to find statically sensitizable paths. These algorithms simultaneously perform a longest path search and a partial verification of the sensitization of the paths. The resulting paths undergo a final and complete sensitization. The algorithms find the longest statically sensitizable path, whose length is a lower bound to the critical path length, and its associated sensitizing input vector. The algorithms can be easily modified to provide an ordered list of all the statically sensitizable paths above a given threshold. An initial analysis of the circuit by the PERT algorithm guides the critical path search and allows pruning of subgraphs that cannot lead to the solution. Results show that these techniques succeed in curbing the combinatorial explosion associated with the longest statically sensitizable path search.>

A computer program for microcode compilation for custom digital signal processors is presented. This tool is part of the CATHEDRAL II silicon compiler. The following optimization problems are highlighted: scheduling, hardware assignment, and loop folding. Efficient techniques to solve these problems are developed. This allows for the automatic synthesis of processor architectures which simultaneously exploit pipelining and parallelism. A demonstrator design is presented.>

Several novel methods for the electrical-level simulation of digital VLSI MOS circuits on a shared-memory multiprocessor system are presented. A novel parallel algorithm, the overlapped phases algorithm, for the efficient simulation of circuits containing feedback loops, is presented. The algorithm is based on data flow scheduling and local relaxation of the feedback loops. A novel method for the partitioning of largepass transistor networks is discussed. The method is based on the signal flow direction in the elements. This partitioning allows an efficient simulation of these large networks on a multiprocessor system. Parallel element evaluation and the time segment pipelining method, two methods to increase the performance of the parallel circuit simulator, are explained. Simulation tests with actual circuits show a substantial acceleration for the new methods.>

This paper discusses the kernel implementation issues of a new and more formal approach to electrical verification. Rule based analysis of the transistor network is applied to derive the signal flow direction and to identify control and state nodes. Symbolic analysis of Boolean expressions, capturing all aspects of switch level networks, allows to take into account the logical structure of the network and its environment during verification and guarantees more relevant error reports. The application of the proposed strategy on real life examples, demonstrates its usefulness and allows for a realistic evaluation of the tool.

In this paper, we discuss a control-flow transformation called loop folding, during the scheduling of register-transfer code for DSP-systems. Loop folding is functionally equivalent to data-path pipelining. An iterative loop-folding procedure, implemented in the CATHEDRAL II compiler, is presented. This technique may significantly improve the utilization of parallel hardware, available in a data path.

This paper presents several new methods for the efficient parallel simulation of VLSI circuits that contain feedback loops or “difficult” parts such as arrays, registers and pass-transistor networks. A new parallel algorithm has been developed for the efficient simulation of circuits containing feedback loops. It is based on dataflow scheduling and local relaxation of the loops. For the simulation of large pass-transistor networks a partitioning method is used that is based on signal flow in the elements. Parallel element evaluation and time-segment pipelining are included to increase the performance of the parallel circuit simulator. Simulation tests with actual circuits show a substantial acceleration for the new methods.

This paper describes a new method for solving the false path problem in static timing analysis of acyclic, combinational circuits. The conditions under which a path is false are accurately defined. The fact that these conditions explicitly take into account the dynamic behaviour of the circuit, constitutes the main contribution of the paper. An algorithm for computing the longest dynamically sensitizable paths in an acyclic, combinational circuit is presented.

This paper presents a new approach to module generation. It is based on the observation that a function, realized by a module instance (e.g. a 16-bit multiplier) when restricted to a sub-function, can be realized by a reduction of the instance to a sub-instance (e.g. a 8-bit multiplier). This reduction is performed automatically by REDUSA. It offers important advantages in both the construction and verification aspects of module generators.

A novel methodology is proposed for the data-path definition and assignment for high-throughput front-end audio, image, and video applications. The technique is based on the concept of the identification of application-specific units that can solve the computational bottlenecks of an algorithm in an efficient way. An algorithm for the automatic assignment of operations on these specific units is presented. A test vehicle taken from the video field demonstrates the proposed method.>

A description is given of efficient techniques for checking tautology of a Boolean expression, i.e. whether two Boolean expressions are equivalent, taking into account 'don't care' behavior if necessary. If two Boolean expressions appear to be not equivalent, a test case is generated. The tautology checker has been developed to perform functional and logical verification of combinational modules and is integrated in an environment for formal electrical verification. Its efficiency is based on a delicate and optimized interaction between a carefully chosen set of Boolean rewriting rules and a number of heuristics. A number of test cases show its performance as compared to existing tautology checkers. Figures on industrial PLAs are included.>

This paper presents a new approach to module generation. It is based on the observation that a function, realized by a module instance (e.g. a 16-bit multiplier) when restricted to a sub-function, can be realized by a reduction of the instance to a sub-instance (e.g. a 8-bit multiplier). This reduction is performed automatically by REDUSA. It offers important advantages in both the construction and verification aspects of module generators.

It is considered that the integration of high-speed consumer digital signal processing (DSP) application requires an efficient IC architecture which is fully adapted to the application at hand. On the other hand, the design time can be reduced substantially by maintaining only a very small cell-library and by applying powerful CAD tools. From the experience collected with a large number of realistic and practical case studies, a selection has been made of promising, efficient architectural strategies that satisfy these constraints. Guidelines for the architectural design process are proposed that depend on the required throughput and the structure of the algorithm and corresponding signal flow-graph.>

The Segmented Waveform Relaxation Method (SWRM) is a new and efficient waveform relaxation method for circuit-level simulation of large-scale digital MOS networks. SWRM is original in two aspects. 1) Dynamic feedback loop cutting and waveform event driven scheduling result in a varying simulation order of the subcircuits and, for digital synchronous circuits, lead to logically correct and accurate ground waveforms in one waveform iteration where the only approximation is due to Miller feedback over MOS capacitances (timing error being usually <5 percent). 2) Dynamic decomposition of large subcircuits at MOS transistors which are temporarily in a nonconducting state. SWRM has been implemented in the program SWAN and tested on large industrial circuits (up to 4000 transistors) with speed gains of 10 /spl gt/ 100 over SPICE2G6. A mixed-mode switch electrical implementation of SWRM together with novel acceleration methods on parallel computers will be described together with test results on real-life circuits.

An environment for the generation of modules is described. It includes tools for interactive design of parameterised procedures describing the structure as well as the topology. For the layout symbolic cells are used which are automatically fitted together as defined by the topology.

This paper presents the design of a parameterisable multiplication-accumulation unit for integrated digital signal processing devices. It is especially suited for macrocell based customised signal processors as proposed by [1]. The complete architecture including the data-path and associated control are described. Estimates of the chip area and speed are presented based on a 3 µm CMOS cell library. The essential advantage of the proposed design is that the time taken for ann-bit byn-bit multiplication of two signals is(n/4)+1processor cycles where each cycle only requires the shifted values of two numbers to be added to a third number using a carry-save and a carry-propagate adder. Compared to conventional shifter-adder based multiplication units this leads to an improvement in the throughput by approximately a factor 4 with one-third the area of a fully hardwired array multiplier for a 16×16 bit multiplication.

CAD tools to support a top-down custom design methodology for integrated digital filters are presented. The methodology is based on a tool-box concept, which makes use of specialised analysis, synthesis and optimization programs at each design level: the network, the architecture and the circuit layout. In this paper, CAD tools for filter synthesis, network optimization and architecture optimization are developed. These tools complement design aids for architecture synthesis, and automatic layout generation (silicon compilers) to create a complete design environment. By combining both synthesis as well as optimization aids at each design level, it is possible to achieve complete automation while retaining efficient use of silicon area, speed and power consumption. Application of these tools to the custom integration of wave digital filters with bit-serial architectures is demonstrated.

An expert system (DIALOG) is described to check correctness of logic levels and timing composition rules in n- or CMOS VLSI logic. Knowledge is described in an engineer oriented language (LEXTOC) allowing for unification (cfr PROLOG), object creation, property assignment, association of relations, rule formulation, logic or arithmetic evaluation as well as conversational constructs. The system is illustrated by checking racefree dynamic CMOS design composition rules. Up to 250 transistors can be handled in the LISP interpretative way on the VAX 11/780. An efficient automatic translation of LEXTOC into Pascal shows the feasibility for batch oriented debugging of up to 50,000 transistors in a workstation environment, while keeping knowledge programming efficiency of LEXTOC.

An interactive CAD methodology is presented for designing digital filters with optimised discrete coefficients. The objective is to minimise the cost of integrationC(\undertilde{a})subject to the constraint that the desired specifications on the complex frequency transfer functionH(w,\undertilde{a})are satisfied. The vector a represents the fixed coefficients in the filter network. For VLSI DSP architectures, where multiplication is implemented using software controlled or hardwired shift-and-add operations,C(\undertilde{a})is defined as the total number of non-zero bits in the discrete representation of\undertilde{a}. An accurate multiparameter analysis technique, based on the bilinear property ofH(w,\undertilde{a}), is exploited to develop numerically reliable and computationally efficient tools for function evaluation and feasible region determination. These are built into a CAD framework together with tools for computingC(\undertilde{a})and predicting the location of the minima ofC(\undertilde{a})Extremely fast optimisation strategies using this framework are demonstrated, for different filter topologies with up to 10 coefficients.

In this paper a new algorithm for switch level simulation is presented. The algorithm is compatible with classical time wheel mechanisms for logic simulation and therefore allows for assignable delay modeling also at the switch level. The key to this algorithm is a local relaxation method which takes care of localized bilateral effects. The algorithm is shown to be 0(n) and proven to converge to a unique solution.