Dieison Deprá
email: dadepra@inf.ufrgs.br

Sergio Bampi
email: bampi@inf.ufrgs.br

Techniques for Architecture Design for Binary Arithmetic Decoder Engines Based on Bitstream Flow Analysis

Keywords: Hardware Dedicated Architectures for Decoding H.264/AVC Video Standard, Arithmetic Entropy Coding, CABAC, CABAD

The design and implementation of a hardware accelerator dedicated to Binary Arithmetic Decoding Engine (BADE) is presented. This is the main module of the Context-Adaptive Binary Arithmetic Decoder (CABAD), as used in the H.264/AVC on-chip video decoders. We propose and implement a new approach for accelerating the decoding hardware of the significance map by providing the correct context for the regular hardware engine of the (CABAD). The design development was based on a large set of software experiments, which aimed at exploiting the characteristic behavior of the bitstream during decoding. The analysis gave new insights to propose a new hardware architecture to improve throughput of regular engines for significance map with low silicon area overhead. The proposed solution was described in VHDL and synthesized to standard cells in IBM 0.18 µm CMOS process. The results show that the developed architecture reaches 187 MHz with a non optimized physical synthesis.

Introduction

The growing importance of high definition digital videos, mainly for real-time application, is calling for higher video compression efficiency to save storage space and transmission bandwidth [START_REF] Wiegand | Overview of the H.264/AVC Video Coding Standard[END_REF]. The most advanced standard is the H.264/AVC, currently at the commercial state-of-the-art, defined by the ITUT/ISO/IEC [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. This standard defines a great set of tools, which act in different domains of image representation to get higher compression ratios, roughly doubling the ratio obtained, by the MPEG-2 compressors [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. The H.264/AVC introduces many innovations in the techniques used to explore the elimination of the redundancies found in digital video sequences.

The H.264/AVC standard specifies two alternative entropy methods: CAVLC (Context-Adaptive Variable Length Coding) and CABAC (Context-Adaptive Binary Arithmetic Coding) [START_REF] Wiegand | Overview of the H.264/AVC Video Coding Standard[END_REF]. Both are based on the fact that the digital video sequences present non-stationary but predictable statistical behavior [START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF]. Moreover, this statistical behavior is highly dependent on the type of content that is being processed and on the video capture technique [START_REF] Wiegand | Overview of the H.264/AVC Video Coding Standard[END_REF][START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. To address this issue, the H.264/AVC adopts an innovative approach that provides dynamic adaptive probabilities estimation, which is introduced in the CAVLC and CABAC [START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF] coding schemes.

The CABAC is the most important entropy encoding method defined by the H.264/AVC standard, allowing the H.264/AVC to reach 15% coding gain over CAVLC [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. However, to obtain these coding gains a significant computational complexity is added in the coding hardware. Moreover, the coding algorithm is essentially sequential, as each step iteration produces only one bit and the next step depends on the values produced in the previous iterations [START_REF] Wiegand | Overview of the H.264/AVC Video Coding Standard[END_REF]. The sequential nature of the CABAD leads to significant performance bottlenecks in the decoder. Many works found in the literature address these constraints trying to break data dependencies inherent to the nature of CABAC.

The goal of this work is to present a new hardware architecture to improve the throughput of the CABAD arithmetic engines. The architectural design aims to achieve a very efficient implementation, based on our experiments for a detailed bitstream flow analysis.

Next section presents an overview on context-adaptive binary arithmetic codec and the arithmetic engines are also detailed. Section 3 presents related works found in the literature. The bitstream flow analysis by simulation is discussed in Section 4. The architecture proposal is detailed in Section 5. The results of our architecture after synthesis are presented in Section 6. Section 7 the validation process applied in this case study are discussed. Finally, Section 8 addresses some conclusions and future work.

Context Adaptive Binary Arithmetic Codec Overview.

The context-adaptive binary arithmetic codec as defined by H.264/AVC standard is a framework for entropy encoding that transforms the value of a symbol in a word of code, with variable length near the theoretical limit of entropy [START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF]. It works with recursive interval divisions combined with context models that allow better coding efficiency [START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF]. Each subinterval represents a unique source symbol, and the size of the interval is proportional to that symbol probability of occurrence [START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF]. However, modeling occurrence probabilities of each symbol brings increasing computational complexity. One way to decrease this computational complexity is to use a binary alphabet [START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF].

The H.264/AVC standard, in its main and high profiles, supports the binary arithmetic coding/decoding, from the macroblock layer, to deal with information generated by the tools that act on the transform redundancies of the following kinds: spatial, temporal, and psycho-visual [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. In the entropy methods of H.264/AVC standard the information that is arriving at the inputs of the encoding process or at the outgoing outputs in the decoding process are named Syntax Elements (SE) [START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF]. The SE is composed by the following information: i) type, used for codec control to determine the encoding process to be used; ii) and the value to be encoded based on the control information provided [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF].

The decoding process is named CABAD and the encoding is referred to as CABAC. The encoding process receives at the input SEs with its type and value. Considering the SE type, a binarization method is applied to convert the SE value into a binary alphabet [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. Then, the context model selects the appropriate context and sends it to the stage of arithmetic coding, responsible for generating the output bitstream and updates the context models. In Fig. 1 the integrated encoding and decoding dataflow is presented. Both encoding and decoding processes are composed by three steps that can be organized into four modules, which are described in the following subsections. As shown in Fig. 1 both encoding and decoding processes are composed by four modules can be organized into three stages that are described below:

Binarization/Anti-Binarization: The binarization process consists of mapping SE values for a unique sequence of bits that represents the original value. This mapping is done to reduce the symbols in the encoding alphabet, thus simplifying the amount of elements to be modeled and minimizing the costs of the context modeling and facilitating the task of arithmetical coding. Each bit, generated through this process, is denoted as "bin" and the set of all "bins" (bits) is named "binstring". From a total of seven binarization methods, four are fundamental: unary; truncated unary; fixed length; and exponential Golomb [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF][START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF]. Probability modeling: A context is a probabilistic model that represents a statistical distribution of a particular symbol on the basis of the review of the symbols previously processed and the probability of occurrence of the current symbol. To adequately model all probabilities of occurrence of each symbol, CABAC defines 460 different contexts. Each bin of an SE can be associated with one or more contexts. During the encoding the probabilistic estimates must be kept updated to ensure the accuracy of the process. Each context model is composed by a pair of values, a 6-bit state value for the probability index (63 possible probability states), and a binary value for the most probable symbol "MPS". The state value is used as an index to the estimated probability value of the least probable symbol "LPS" [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF][START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF]. Binary Arithmetic Coder (BAC), or Decoder (BADE): It works based on the principle of recursive division of the interval of width R [START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF]. From the estimation of probability for LPS (pLPS) on a given range, two subintervals are obtained. The first is given by: rLPS = R * pLPS which is associated with LPS while the second (which is related to MPS) is given by: rMPS = R -rLPS. According to the encoded bin the rMPS or rLPS is chosen as new interval R. To simplify the computational complexity the value of R is quantized to 2 bits and the multiplication for rLPS values are pre-stored in a 64x4 fixed 2-D table indexed by the 6-bit state coming from context model and by the 2-bit quantized value of R. During binary arithmetic coding process two registers (range "R" and offset "O") are needed to keep the interval updates. The first one saves the current interval range while the second marks the lower bound within this interval (offset) [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF][START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF].

CABAD Algorithm Overview

The CABAD process involves a set of actions that occur below the slice layer. Fig. 2 shows the flow chart for these actions. For each new slice a new CABAD iteration happens. At the beginning of a slice a new context table is built from probability algorithm based on initial tables that depend on the slice type and of an index value (three possibilities) sent by the encoder. After that, CABAD initializes the variable CodlOffset getting the first nine bits reading from the encoded bitstream and the variable CodlRange si set to default value [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF].

The CABAD decoding of macroblock layer of SE values are performed until an "End One Slice" (EOS) SE type is found. The first step in the SE decoding is the decision of its type and, based on this information it chooses an anti-binarization method [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. After that, if the SE type is an EOS, then terminal decoding process is selected. Otherwise, for each bin of SE one of two other decoder processes, regular or bypass, must be chosen. For bins being decoded by regular process a context table address calculation must be done. The information retrieved from context table includes the MPS and its probability estimate index denoted by pState variable. The CABAD uses an offset fixed for each SE type combined with an increment defined by different possible forms, according to the SE type in conformance with [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF] to generate context table addresses. For some SEs, obtaining increment index involves referring to SE from the left, top and current macroblock and, for others, the bin index is used for this purpose.

For bins that use the regular decoding process the CABAD obtains new rLPS from a look-up in a fixed pre-stored table indexed by pState and then one of four possible values is selected by value of quantized CodlRange (CodlRange>>6) [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. Then, new value of CodlRange is calculated and the comparison between CodlRange and CodlOffset define if MPS or LPS happens. After that, the context table must be updated with new values for MPS and pState which are obtained from a fixed table with state transition with different values for MPS or LPS occurrence. Next, the CodlRange and CodlOffset registers are available for the normalization process. In this case one or more bits of bitstream can be consumed [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. Finally, one step of regular decoding process is finished; the contexts model and decoding environment register are updated. For other bins the bypass decoding process is applied. The bypass mode is simpler than the regular mode. Then, anti-binarization module is performed and the results of this operation determine if the binstring produced by the decoding environment matches with the method expected or not.

Related Work

Techniques to reduce the latency and data dependency of CABAD have been widely discussed in the literature and they follow five basic approaches: pipeline; contexts pre-fetching and cache; elimination of renormalization loop; parallel decoding engines; and memory organization. The pipeline strategy is used in [START_REF] Yang | A High Throughput VLSI Architecture Design for H.264 Context-Based Adaptive Binary Arithmetic Decoding With Look Ahead Parsing[END_REF] to increase the bins/cycle rate. An alternative to solve the latency of renormalization process is presented in [START_REF] Eeckhaut | Optimizing the critical loop in the H.264/AVC CABAC decoder[END_REF]. The speculative processing through the use of engines decoding parallel is explored first in [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF], then in [START_REF] Kim | High speed decoding of context-based adaptive binary arithmetic codes using most probable symbol prediction[END_REF] and [START_REF] Bingbo | A high-performance VLSI architecture for CABAC decoding in H.264/AVC[END_REF]. High efficiency in the decoding process using pre-fetching and cache contexts is discussed in [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] and [START_REF] Zhang | High-Performance CABAC Engine for H.264/AVC High Definition Real-Time Decoding[END_REF], respectively. Memory optimization and reorganization are addressed in [START_REF] Yang | A High Throughput VLSI Architecture Design for H.264 Context-Based Adaptive Binary Arithmetic Decoding With Look Ahead Parsing[END_REF].

The work of [START_REF] Bingbo | A high-performance VLSI architecture for CABAC decoding in H.264/AVC[END_REF] presents optimizations in the arithmetic engine through the parallel execution in speculative mode and the adoption of leading zero anticipation that allows counting of consecutives zeros in CodlRange. These two approaches bring reductions in the delay in the critical path.

The hardware architecture proposed in [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] is based on analysis of the relationship between bins count for each SE type and the occurrence of each SE type in one macroblock. The usage rate imposed by each SE in each of the three decoder engines is a relevant aspect that is used to optimize the overall decoding process.

An evaluation of the data dependencies in the regular mode of decoder arithmetic engine is presented in [START_REF] Kim | High speed decoding of context-based adaptive binary arithmetic codes using most probable symbol prediction[END_REF]. In this study, the frequency of changes to CodlRange and CodlOffset registers are considered for cases where renormalization process happens combined with the observation of MPS or LPS decision.

Considering the various architectures proposed by different authors for the CABAD, a static characteristics analysis of constraints for decoding bitstream process was considered and some experiments were conducted by software simulations to extract the dynamic behavior of the decoder flow. This analysis is addressed in Section 4.

Bitstream Flow Analysis for Decoder Process

All our analyses were based on results obtained from statistical data collected by software routines that we introduced into the decoder module of the reference software (JM), version 10.2 [START_REF] Suhring | H.264/AVC Reference Software[END_REF]. To reach more representative data set in our analysis we decided to work with four different digital video resolutions, in YUV video format 4:2:0, more often used in the reports found in the literature: QCIF, CIF, D1 and HD1080p. Moreover, we evaluated the impact of the quantization parameters on the bitstream behavior. For our statistics we selected all 18 QCIF, 17 CIF, 18 D1 video sequences available in [START_REF] Reisslein | YUV Video Sequences[END_REF], and also seven additional HD1080p video sequences. The last are designated as: rush-hour; riverbed; blue-sky; tractor; sunflower; station2; pedestrian area. In total, there were 60 digital video sequences in this analysis, each with 200 frames. Fig. 3 show one frame of the HD1080p video sequences used in this case study in additional to QCIF, CIF and D1 listed in Table 1. The encoding parameters employed for coding all sequences were: Profile IDC = 77, Level IDC = 40, SymbolMode = CABAC, GOP=IPBB and RDO=ON. Our experimental procedure was to perform, for all the video sequences, six different encoding processes, varying the parameters of quantization QPISlice and QPPSlice in pairs; namely the pairs were: 0:0, 6:0, 12:6, 18:12, 24:18, and 36:26, resulting in a total of 420 digital video sequences encoded. The decoding process was done for all encoded sequences using the JM v.10.2 decoder, to collect the statistics data and to obtain feedback for the validation process. The relations and statistical behavior were studied and synthesized, and they will be presented next.

One of the problems of CABAD is to determine the actual throughput needed for the decoding process to occur in real-time. This happens because the length of codeword generated by CABAD is variable and may change significantly between iterations, since the coding method is context types it can be difficult to determine the binstring length and the SE sequence, as they vary according to the slice type and the macroblock type. However, H.264/AVC standard in its level 4.0 defines the upper bit count at the input and output of the CABAD, before quantization, and the ratio between them varies between 1.3 and 2.1 times. Then, we can consider that, in the worst case, the architecture has to process at nearly 42Mbps, to reach throughput enough for real-time decoding at 30 frames per second in the 1080 x 1920 format (1080p).

The Binary Arithmetic Decoder Engines (BADE) are the CABAD kernels. They are responsible for regenerating the binstring since of the bitstream and internal variables. Each bin is produced by one of three BADE kinds. Considering that the decoding process is done bin by bin, it requires high performance because inside this module resides the CABAD critical path. The BADE basic Fig. 4.

Fig. 4. The three kinds of Binary Arithmetic Engines present into CABAC core, its organization and they connection with the internal registers

The H.264/AVC standard defines which type of BADE engine each SE Moreover, part of binstring of one SE another part can be produced by other BADE block and is used on most SEs. T part of motion vector differential (MVD) and transforms coefficient (COEF). Additionally, the signal bits of COEF have to be treated in the bypass engines. iterations, since the coding method is context-adaptive. Furthermore, for some types it can be difficult to determine the binstring length and the SE sequence, as they vary according to the slice type and the macroblock type. However, H.264/AVC standard in its level 4.0 defines the upper-limit bit/rate at 20Mbps. We analyzed the it count at the input and output of the CABAD, before quantization, and the ratio between them varies between 1.3 and 2.1 times. Then, we can consider that, in the worst case, the architecture has to process at nearly 42Mbps, to reach throughput time decoding at 30 frames per second in the 1080 x 1920 format

The Binary Arithmetic Decoder Engines (BADE) are the CABAD kernels. They are responsible for regenerating the binstring since of the bitstream and internal is produced by one of three BADE kinds. Considering that the decoding process is done bin by bin, it requires high performance because inside this module resides the CABAD critical path. The BADE basic organization is shown in The three kinds of Binary Arithmetic Engines present into CABAC core, its organization and they connection with the internal registers.

The H.264/AVC standard defines which type of BADE engine each SE Moreover, part of binstring of one SE type can be produced by one BADE type while another part can be produced by other one. The regular engine is the most complex is used on most SEs. The bypass engine is only used by the suffix part of motion vector differential (MVD) and transforms coefficient (COEF). Additionally, the signal bits of COEF have to be treated in the bypass engines.

adaptive. Furthermore, for some SE types it can be difficult to determine the binstring length and the SE sequence, as they vary according to the slice type and the macroblock type. However, H.264/AVC limit bit/rate at 20Mbps. We analyzed the it count at the input and output of the CABAD, before quantization, and the ratio between them varies between 1.3 and 2.1 times. Then, we can consider that, in the worst case, the architecture has to process at nearly 42Mbps, to reach throughput time decoding at 30 frames per second in the 1080 x 1920 format

The Binary Arithmetic Decoder Engines (BADE) are the CABAD kernels. They are responsible for regenerating the binstring since of the bitstream and internal is produced by one of three BADE kinds. Considering that the decoding process is done bin by bin, it requires high performance because inside this organization is shown in

The three kinds of Binary Arithmetic Engines present into CABAC core, its

The H.264/AVC standard defines which type of BADE engine each SE must use. type can be produced by one BADE type while he regular engine is the most complex he bypass engine is only used by the suffix part of motion vector differential (MVD) and transforms coefficient (COEF). Additionally, the signal bits of COEF have to be treated in the bypass engines. During software profiling, the BADE engine utilization by each SE type was observed to determine the better strategy for the dedicated architecture design.

By analyzing the bins count occurrence in the bitstream we observed that just four SE types (coded_block_flag, coeff_level, sig_coeff_flag and last_sig_flag) account for more than 93% of all bins, in average, for all types of macroblocks. Thus, a deeper analysis of the behavior of these SE types was performed to improve the gain in the BADE. In the first study we investigated the bins distribution for different SE types in each one macroblock types. In the Table 2 the results obtained are summarized. The results show that there are, on the average, seven significant coefficient flag (SE_SIG) and five least significant coefficient flag (SE_LAS) for each 4x4 residual blocks. The utilization of arithmetic engines shows that regular engines produce 80.8% of bins count while the bypass produced 19.2% of them. Another interesting fact is that many bins produced by regular and bypass is generated in a consecutive way, 84.92% and 29.35%, respectively. The occurrence of bins related to the SEs of the significance map (SE_SIG and SE_LAS) also deserve emphasis, since together they represent between 27% and 36% of all bins processed by the CABAD. Moreover, they have special interest for decoding engines since they usually occur in sequence, i.e. each SE_SIG is followed by a SE_LAS. However, this does not occur when the value of SE SE_SIG is zero, in this case the next SE decoded should be another SE SE_LAS. Fig. 5 illustrates the relationship between bins occurrence of the significance map for each of the resolutions discussed, highlighting the percentage difference occurrences between SE_SIG and SE_LAS.

Design Architecture

The proposed architecture development behavior of the bitstream for many coding scenarios and on few previous works found in the literature. The bitstream flow analyses have shown that for some specific situations using an approach with specialized process in the decoding process. As presented in section 2, 3 and 4, the exploration of the parallel speculative execution of BADE engines is a good alternative to reach greater throughput without excessive area increase.

Our design is based on the work presented in [START_REF] Depra | A novel hardware architecture design for binary arithmetic decoder engines based on bitstream flow analysis[END_REF] which applies multiple parallel engines for speculative execution. In this work we include few extensions mainly in the regular branch. The new arrangements in the regular engine interconnections aim at exploring characteristics behavior of the SE_SIG and for the SE_LAS kinds of the syntax element to reach high throughput in the significance map decoding.

From the work presented by Yu and He in [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] a significant part of the new proposed architecture for CABAD makes variable number of bins per cycle. Depending on each implementation, the context modeling can provide one or two context models for regular engines branch, thus varying the efficiency of the decoding. But, for spec not improve efficiency because according to the decision of the first regular engine the second bin for each one of these engines needs to use a different context.

The H.264/AVC standard defines that each 4x4 coefficient bl one significance map [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. This map set is composed by two types of SE (SE_SIG and SE_LAS) which should occur in a specific order. The significance map is generated according to the process order and the coefficients value. The process f of the significance map for a 4x4 coefficient Index line shows the index shows each one coefficients value for a 4x4 example block. The lines with and Flag LAST show the composition of the significance map for the 4x4 example block.

Bin occurrences for Significance Map SE in each resolution used.

Design Architecture

The proposed architecture development was based on observations made on the behavior of the bitstream for many coding scenarios and on few previous works found in the literature. The bitstream flow analyses have shown that for some specific situations using an approach with specialized processing can provide throughput gains in the decoding process. As presented in section 2, 3 and 4, the exploration of the parallel speculative execution of BADE engines is a good alternative to reach greater throughput without excessive area increase.

n is based on the work presented in [START_REF] Depra | A novel hardware architecture design for binary arithmetic decoder engines based on bitstream flow analysis[END_REF] which applies multiple parallel engines for speculative execution. In this work we include few extensions mainly in the regular branch. The new arrangements in the regular engine interconnections aim aracteristics behavior of the SE_SIG and for the SE_LAS kinds of the syntax element to reach high throughput in the significance map decoding.

From the work presented by Yu and He in [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] a significant part of the new proposed architecture for CABAD makes use of two regular engines for decoding a variable number of bins per cycle. Depending on each implementation, the context modeling can provide one or two context models for regular engines branch, thus varying the efficiency of the decoding. But, for special situations this approach may not improve efficiency because according to the decision of the first regular engine the second bin for each one of these engines needs to use a different context.

The H.264/AVC standard defines that each 4x4 coefficient block should refer to one significance map [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. This map set is composed by two types of SE (SE_SIG and SE_LAS) which should occur in a specific order. The significance map is generated according to the process order and the coefficients value. The process for generation of the significance map for a 4x4 coefficient block example is shown in Fig. 6 Index line shows the index or the values in zig-zag scan order while the Value line shows each one coefficients value for a 4x4 example block. The lines with and Flag LAST show the composition of the significance map for the 4x4 example was based on observations made on the behavior of the bitstream for many coding scenarios and on few previous works found in the literature. The bitstream flow analyses have shown that for some specific ing can provide throughput gains in the decoding process. As presented in section 2, 3 and 4, the exploration of the parallel speculative execution of BADE engines is a good alternative to reach greater n is based on the work presented in [START_REF] Depra | A novel hardware architecture design for binary arithmetic decoder engines based on bitstream flow analysis[END_REF] which applies multiple parallel engines for speculative execution. In this work we include few extensions mainly in the regular branch. The new arrangements in the regular engine interconnections aim aracteristics behavior of the SE_SIG and for the SE_LAS kinds of the From the work presented by Yu and He in [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] a significant part of the new use of two regular engines for decoding a variable number of bins per cycle. Depending on each implementation, the context modeling can provide one or two context models for regular engines branch, thus ial situations this approach may not improve efficiency because according to the decision of the first regular engine the second bin for each one of these engines needs to use a different context.

ock should refer to one significance map [START_REF]Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-TSG16/Q.6[END_REF]. This map set is composed by two types of SE (SE_SIG and SE_LAS) which should occur in a specific order. The significance map is generated or generation block example is shown in Fig. 6. The scan order while the Value line shows each one coefficients value for a 4x4 example block. The lines with Flag SIG and Flag LAST show the composition of the significance map for the 4x4 example Fig. 6. Significance Map generation for a 4x4 coefficients block.

As shown in Fig. 6 for each SE_SIG with value equal to one there is one SE_LAS, but when the SE_SIG is equal to zero then the SE_LAS element does not occur. Based on the results analysis, summarized in the Fig. 5, it is possible to identify that this mismatching between SE_SIG and SE_LAS pair happens, in average, for roughly 30% of the cases in the HD1080 video sequences that we tested. This fact opens the opportunity to explore decoding optimizations, specifically as to when one specialized process to supply the correct context for BADE can be used.

The proposed architecture employs multiple engines instances for the case of variable number of bins per cycle, and also adopts specialized mechanism for context selection. Our design basic structure is shown in Fig. 7. As Fig. 7 shows, the three kinds of engines present in CABAD are organized in one hierarchical arrangement, namely: one terminate engine, two regular engines and four bypass engines. The BADE block (in Fig. 7) receives three context pairs (STATE and MPS) and the bitstream buffer (BS). According to the SE kind, one of its engines is used. The Regular and Bypass engine instances are organized into two distinct branches. Inside the Regular branch two bins can be produced in one cycle while in the Bypass branch at most four bins can be produced in a single cycle. The Regular engine is more complex than the other engines, and contains the critical path of this module. We used optimizations to reduce the delay of this block.

Initially an operations reordering is made by the regular engine, as the approach presented in [START_REF] Kim | High speed decoding of context-based adaptive binary arithmetic codes using most probable symbol prediction[END_REF]. This results in two parallel paths inside the regular engine, one to treat the occurrence of the MPS and another for the LPS. Another important aspect is the access to static memories to retrieve information about the next state (access the MPS_TABLE, and the LPS_TABLE) and the rLPS estimate probabilities (RLPS_TABLE). These memories are addressed by pState, which is provided from the context model stored in the context memory. The fact that these memories are inside the regular engine affects the critical path. Furthermore, when we concatenate two regular engines, two accesses to these memories in the same cycle is required. To solve this problem we apply an approach similar to that adopted in [START_REF] Mei-Hua | Optimizing Design and FPGA Implementation for CABAC Decoder[END_REF], in which the memories are concatenated and combine the information about current, the next MPS states, the next LPS states and rLPS estimate probabilities. Thus, we can obtain all information needed to decode two bins that reference the same context with just one access to the static memory.

Finally, we applied the first one detect (FOD) strategy to solve the renormalization problem in an approach similar to [START_REF] Eeckhaut | Optimizing the critical loop in the H.264/AVC CABAC decoder[END_REF]. The special approach used to resolve the renormalization allows it to save between 2 to 8 cycles, because the loop is eliminated and the renormalization always happens in only one cycle. To reduce the FOD delay, the FOD is broken in two segments, one for the low interval part and another for the high interval part, as illustrated by Fig. 8. Then, adding just one multiplexer we can select the renormalization part between the low and high ranges. To finish, the Range first bit is used to choose between new and old register values for the renormalization process.

Fig. 8. Renormalization b

Considering that the regular engine is responsible for most of the bins produced by the CABAD, it seems a good alternative to increase the parallelism level in this engine, instantiating additional regular engines. Meanwhile, th the BADE critical path due to its long combinational logic depth (that includes adders, comparators, ROM and renormalization). Thus, it is not advantageous to use a larger number of regular engines concatenated because this would cau degradation for all other CABAD stages and the throughput may not be satisfactory. Moreover, our analysis has shown that the Regular engines are underutilized because the context modeling cannot be efficient for all situations, especially fo map decoding.

A new interconnection approach, namely of SP_SIGMAP, for regular engines was developed to improve throughput in the regular branch. The BADE block can receive three context pairs from context modeling. These context pairs can b significance map decoding to explore the characteristic behavior of these SEs. The first regular engine receives one context to decode one SE_SIG, while the second regular engine receives two contexts, being one to decode one SE_LAS and other to decode the next SE_SIG. If the first regular engine result was MPS then the second regular engine receives the second context else the third context will be delivered to the second regular engine. The interconnections for regular branch en in Fig. 9.

The next section analyzes the results obtained by our architectures when processing digital video test sequences, the same utilized in the simulation analysis discussed in section 4.

Renormalization block with FOD accelarates.

Considering that the regular engine is responsible for most of the bins produced by the CABAD, it seems a good alternative to increase the parallelism level in this engine, instantiating additional regular engines. Meanwhile, the regular engine is in the BADE critical path due to its long combinational logic depth (that includes adders, comparators, ROM and renormalization). Thus, it is not advantageous to use a larger number of regular engines concatenated because this would cause performance degradation for all other CABAD stages and the throughput may not be satisfactory. Moreover, our analysis has shown that the Regular engines are underutilized because the context modeling cannot be efficient for all situations, especially for significance A new interconnection approach, namely of SP_SIGMAP, for regular engines was developed to improve throughput in the regular branch. The BADE block can receive three context pairs from context modeling. These context pairs can be used in significance map decoding to explore the characteristic behavior of these SEs. The first regular engine receives one context to decode one SE_SIG, while the second regular engine receives two contexts, being one to decode one SE_LAS and other to decode the next SE_SIG. If the first regular engine result was MPS then the second regular engine receives the second context else the third context will be delivered to the second regular engine. The interconnections for regular branch engines are shown

The next section analyzes the results obtained by our architectures when processing digital video test sequences, the same utilized in the simulation analysis Considering that the regular engine is responsible for most of the bins produced by the CABAD, it seems a good alternative to increase the parallelism level in this e regular engine is in the BADE critical path due to its long combinational logic depth (that includes adders, comparators, ROM and renormalization). Thus, it is not advantageous to use a se performance degradation for all other CABAD stages and the throughput may not be satisfactory. Moreover, our analysis has shown that the Regular engines are underutilized because r significance A new interconnection approach, namely of SP_SIGMAP, for regular engines was developed to improve throughput in the regular branch. The BADE block can receive e used in significance map decoding to explore the characteristic behavior of these SEs. The first regular engine receives one context to decode one SE_SIG, while the second regular engine receives two contexts, being one to decode one SE_LAS and other to decode the next SE_SIG. If the first regular engine result was MPS then the second regular engine receives the second context else the third context will be delivered to gines are shown

The next section analyzes the results obtained by our architectures when processing digital video test sequences, the same utilized in the simulation analysis Fig. 9. Regular engines interconections inside the Regular Branch.

Experimental Results

The developed architectures were described in VHDL and synthesized to 0.18 um CMOS standard cells based on the IBM cell library using the Cadence RTL compiler. The Modelsim tool, version 6.01a, was used during the simulation and architectural validation process. The architecture development presents a new arrangement for binary arithmetic decoders of CABAD that is able to generate up to 4 bins per cycle, in the best case. The utilization of four decoding bypass engines inside the BADE increases the hardware resources required, while providing more efficiency compared to the BADE architecture with just two decoder bypass engines. Table 3 shows the hardware synthesis results for the architecture proposed. It compares the solutions with two and four decoder bypass engines in the architecture and our design. The results in Table 3 indicate that the increase in the hardware costs is around 2.4% for our design and the maximum frequency decreases 1.7%, both when compared to the design proposed in [START_REF] Depra | A novel hardware architecture design for binary arithmetic decoder engines based on bitstream flow analysis[END_REF]. A large number of test-benches were developed and run to evaluate the performance o from the reference software during the decoding process of the 440 digital video sequences listed in Section 4. For these video test main approaches adopted can improve the throughput works presented in [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] and [START_REF] Depra | A novel hardware architecture design for binary arithmetic decoder engines based on bitstream flow analysis[END_REF]. So, the potential gain for the four Bypass engines (4 BYPASS) and for the specialized context selection for significance map in regular engines (SP SIGMAP) were analyzed for each different resoluti sequences tested. The results of th Fig. 10. Performance analysis to four classic resolutions.

The data presented in Fig.

the throughput from 4.97% for HD1080 up to 8.75% for QCIF video sequence resolutions. Furthermore, the 4 BYPASS approach offers additional gain from 3.99% up to 4.68% for HD1080 and QCIF, respectively. The pro approaches, and when compared to [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] which does not use neither of these techniques, it reaches 8.96% to 13.43% throughput gains. When compared to [START_REF] Depra | A novel hardware architecture design for binary arithmetic decoder engines based on bitstream flow analysis[END_REF] the proposed design shows the throughput gains indicated

The strategy to evaluate the performance of our hardware was also employed to validate our design: in these simulations we compared the outputs generated by our architecture to the results generated by the JM10.2 decoding module [START_REF] Suhring | H.264/AVC Reference Software[END_REF]. To this e we introduced extra code (routines) in this software to save the inputs and the outputs of the BADE engines for later comparison with the hardware simulations. This strategy was used for extensive architecture validation.

Validation Process

In the development cycle of integrated of the design time. This information indicates the challenge of this process. The approach used in this work to minimize this time was to make a hierarchical and incremental validation. In this approach, several validation steps were made to the complexity and the abstraction level of the developed blocks. developed and run to evaluate the performance of our architecture with data extracted from the reference software during the decoding process of the 440 digital video sequences listed in Section 4. For these video test-benches we observed that the two main approaches adopted can improve the throughput when compared to previous works presented in [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] and [START_REF] Depra | A novel hardware architecture design for binary arithmetic decoder engines based on bitstream flow analysis[END_REF]. So, the potential gain for the four Bypass engines (4 BYPASS) and for the specialized context selection for significance map in regular engines (SP SIGMAP) were analyzed for each different resolution of the video sequences tested. The results of these analyses are shown in Fig. 10.

Performance analysis to four classic resolutions.

The data presented in Fig. 10 shows that the SP SIGMAP approach can improve the throughput from 4.97% for HD1080 up to 8.75% for QCIF video sequence resolutions. Furthermore, the 4 BYPASS approach offers additional gain from 3.99% up to 4.68% for HD1080 and QCIF, respectively. The proposed design adopts both approaches, and when compared to [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] which does not use neither of these techniques, it reaches 8.96% to 13.43% throughput gains. When compared to [START_REF] Depra | A novel hardware architecture design for binary arithmetic decoder engines based on bitstream flow analysis[END_REF] the proposed design shows the throughput gains indicated in the SP SIGMAP line of Fig. 10 The strategy to evaluate the performance of our hardware was also employed to in these simulations we compared the outputs generated by our architecture to the results generated by the JM10.2 decoding module [START_REF] Suhring | H.264/AVC Reference Software[END_REF]. To this e we introduced extra code (routines) in this software to save the inputs and the outputs of the BADE engines for later comparison with the hardware simulations. This strategy was used for extensive architecture validation.

Validation Process

lopment cycle of integrated circuits, the validation process can reach 70% of the design time. This information indicates the challenge of this process. The approach used in this work to minimize this time was to make a hierarchical and tion. In this approach, several validation steps were made to the complexity and the abstraction level of the developed blocks. f our architecture with data extracted from the reference software during the decoding process of the 440 digital video benches we observed that the two when compared to previous works presented in [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] and [START_REF] Depra | A novel hardware architecture design for binary arithmetic decoder engines based on bitstream flow analysis[END_REF]. So, the potential gain for the four Bypass engines (4 BYPASS) and for the specialized context selection for significance map in regular on of the video shows that the SP SIGMAP approach can improve the throughput from 4.97% for HD1080 up to 8.75% for QCIF video sequence resolutions. Furthermore, the 4 BYPASS approach offers additional gain from 3.99% posed design adopts both approaches, and when compared to [START_REF] Yu | A High Performance CABAC Decoding Architecture[END_REF] which does not use neither of these techniques, it reaches 8.96% to 13.43% throughput gains. When compared to [START_REF] Depra | A novel hardware architecture design for binary arithmetic decoder engines based on bitstream flow analysis[END_REF] the proposed of Fig. 10. The strategy to evaluate the performance of our hardware was also employed to in these simulations we compared the outputs generated by our architecture to the results generated by the JM10.2 decoding module [START_REF] Suhring | H.264/AVC Reference Software[END_REF]. To this end, we introduced extra code (routines) in this software to save the inputs and the outputs of the BADE engines for later comparison with the hardware simulations. This circuits, the validation process can reach 70% of the design time. This information indicates the challenge of this process. The approach used in this work to minimize this time was to make a hierarchical and tion. In this approach, several validation steps were made according

In the first step, the blocks of lower abstraction level were validated as standalone block. This was accomplished by generating the intermediate data from the specifications given in the H.264/AVC standard. These stimuli were used in each of the blocks and the verification was done by comparing the waveforms in the simulator to the functional definition of that block.

In the second step, the blocks were grouped according to their function and the validation was done for the entire group. In this step a software implementation of the norm was used to produce the input stimuli and the expected output. The software model used to generate the stimuli and the expected results was based on the reference software of the H.264/AVC (Surking, 2009). Modifications were done in this software to get the right data for the hardware validation. Fig. 11 illustrates the data extraction process for validation. The data extraction process for the production of input stimuli and the results for comparison were done using the same standard video sequences of the section 4. Actually these stimuli were produced at the same time the data for static and dynamic analysis were produced. This approach allowed us to significantly reduce the time spent, once we had to process all the video sequences only once. It also made the data used for analysis and validation consistent with each other.

The second step followed the flow showed in Fig. 12. Inside a test-bench file, the input stimuli were injected into the validating block (Design Under Test -DUT). The outputs of the DUT were stored for later comparison to the expected outputs.

Conclusions and Future Work

This work presented a novel dedicated hardware architecture for the BADE of the CABAD block that supports the decoding of up to four bins per cycle. The architectural decisions were supported by a detailed analysis of the bitstream flow generated by a software video decoder. The results show that, with a hardware cost increase of just 2.4%, we obtain 5% efficiency gain in the utilization rate of the BADE module. The analysis of the bitstream flow shows that it is possible to explore the dynamic behavior of CABAD algorithms to develop novel hardware solutions.

The next step in this development will be to integrate this BADE module inside the CABAD top-level hardware architecture and to evaluate performance and throughput of the entire H.264/AVC decoding hardware with the same digital video sequence inputs. Given that in our simulation experiments we used a limited length for the search area for the motion vector calculations, one needs to analyze the behavior of the bitstream flow when the search area for motion estimation is increased.

Fig. 1 .

 1 Fig. 1. CABAC and CABAD dataflow diagram with the three stages and four modules that compose the encoder and decoder.

Fig. 2 .

 2 Fig. 2. CABAD algorithm flow diagram shows the action sequence released by CABAC Decoder to process each one SE inside of the slice layer.

Fig. 3 .

 3 Fig. 3. Samples of HD1080 video sequence, that named: rush-hour; riverbed; blue-sky; tractor; sunflower; station2; pedestrian area, respectively.

Fig. 5 .

 5 Fig. 5. Bin occurrences for Significance Map SE in each resolution used.

Fig. 7 .

 7 Fig. 7. BADE core with arrangement.

Fig. 11 .

 11 Fig. 11. Data extraction process for functional validation of the individual blocks and the complete architecture.

Fig. 12 .

 12 Fig.12. Processo de extração de dados para a validação funcional dos blocos individuais e da arquitetura completa.

Table 1 .

 1 All video sequence used in this case study.

		Video Sequences
	QCIF	CIF	D1	HD1080
	(176×144)	(352×288)	(720×480)	(1920×1080)
	Akiyo	Bridge-close	Abstract	Bluesky
	Bridge-close	Bridge-far	Artant	Pedestrian
	Bridge-far	Bus	Chips	Riverbed
	Carphone	Coastguard	Concert	Rush-hour
	Claire	Container	F1	Station2
	Coastguard	Flower	Football	Sunflower
	Container	Foreman	Ice	Tractor
	Foreman	Hall	Leaves
	Grand-mother	High Way	Letters
	Hall	Mobile	Mobile
	Highway	Mother-daughter	Parkrun
	Miss-america	News	Rafting
	Mobile	Paris	Rugby
	Mother-daughter	Silent	Seawall
	News	Stefan	Suzie
	Salesman	Tempete	Tempete
	Silent	Waterfall	Toweres
	Suzie		Waterfall

Table 2 .

 2 Distribution of bins by different SE types for each macroblock type.

		Information	Code Block Flag (%)	Sig & Last Flags (%)	Coefficient Levels (%)	Other SEs (%)
		Total occurs	2.32	60.38	34.30	3.00
	I MB	Bins generated Regular Process	0.67 0.86	17.62 22.31	80.00 74.68	2.31 2.15
		Bypass Process	0	0	100	0
		Total occurs	2.51	58.50	37.07	1.92
	P MB	Bins generated Regular Process	1.47 1.76	34.21 40.95	62.05 54.90	2.27 2.39
		Bypass Process	0	0	98.33	1.67
		Total occurs	2.61	57.58	38.56	1.25
	B MB	Bins generated Regular Process	1.80 2.17	39.75 47.98	46.29 37.46	12.16 12.39
		Bypass Process	0	0	98.97	1.03
		Total occurs	2.55	58.07	37.65	1.73
	Average	Bins generated Regular Process	1.54 1.86	35.14 42.41	61.10 53.30	2.22 2.43
		Bypass Process	0	0	98.78	1.22

Table 3 .

 3 Distribution of bins by different SE types for each macroblock type.

			Architectures for multi bin BADE engines
	Information	[6] 1	[12]	Proposal Our	Differences (percent)
	Gates	3671	3928	4022	94 (+2.4%)
	Max. Frequency	191.86	190.25	187	-3,25 (-1.7%)
	Max. Bins/Cycle	3(2R1B)	4(4B)	4(4B)	0
			1 Our implementation of the author´s proposal.

Acknowledgment

The authors gratefully acknowledge the Brazilian R&D agencies, CNPq and CAPES, for financial support.


Sergio Bampi
email: bampi@inf.ufrgs.br

Ricardo Reis
email: reis@inf.ufrgs.br

Challenges and Emerging Technologies for System Integration Beyond the End of the Roadmap of Nano-CMOS

Keywords: Nanoelectronics, Beyond CMOs, Roadmap, CMOS

By 2020 it is very likely that nano-CMOS will reach the end of the scaling roadmap. Such end will not mean the demise of silicon technology at all. While there are uncertainties as to what will be the show-stoppers, there is a large number of transitional and compatible to CMOS technologies that will be more important than just 2-D scaling. This paper discusses possible limitations bringing the end of scaling and also proposes a likely scenario for hardware technology evolution and related challenges for integrating systems in the next 20 years. The scenario beyond the end of the roadmap is drawn, in which key technologies will be developed to be compatible with nano-scaled CMOS in silicon, and not to replace it entirely. Transitional technologies will rather coexist and be built upon a basic CMOS-like technology platform of silicon-oninsulator. Radically new devices at the 1-10 nm scale will most likely be built on a silicon substrate with the same technical requirements (such as cleanness, lithographic resolution, long-range ordering, etc) of near end-of-roadmap CMOS industry. The end of scaling will not necessarily lead to the onset of a post-silicon era. Advanced materials research has not pointed so far to a nonsilicon scenario well beyond 2020. The computing systems challenges will be dealt with new forms of integration, hierarchically ordered from the micronlevel, to sub-micron level (500nm to 100nm) non-digital, down to nano-scaled transistors on silicon further down to 10 nm. In this hierarchy, at the bottom, it is highly possible that disruptive molecular-level devices (self-assembled in the scale of 2 to 10 nanometers) will eventually be production-worthy for 100 Giga-to Tera-scale devices integration. Structures like graphene-based carbon tubes or planes are the most viable candidates for molecular devices. In this presentation the computer-systems relevant issues of systems power dissipation, noise, hardware design complexity, and resilience to systems failures in the presence of device variances and faults, are addressed as the challenging computing research topics that will guide future research in computing architectures at the tera-scale integration beyond 2020.

Introduction

CMOS (complementary metal-oxide-semiconductor) circuits on silicon substrates of various types (bulk, silicon-on-insulator SOI, strained silicon with silicon-germanium alloys, etc) have been the dominant devices on which ICT (digital information and communication technologies) hardware and software have been developed for about 30 years. The integrated circuit and discrete silicon devices industries are even older, namely 50 years old in 2009 since Jack Kilby´s patent in 1959 [START_REF] Kilby | US Patent[END_REF]. Reliable estimation is that the worldwide semiconductor industry reached US$261.9 billion revenue in 2008 [4], a 4.4 % decline from 2007, due to the 2008-2009 economic downturn worldwide. In 2007 the revenue in this industry topped at US$273 billion per year, a dollar-mark that is forecasted to be surpassed only in 2011, after the economic recovery expected in 2010. Electronics manufacturing worldwide produces an output of roughly US$1.6 Trillion per year, and it has grown about 3 percentage points over the average growth of the rest of the world-manufacturing sector, consistently in the period 1996-2008. IT services enabled by equipment produced by this industry will continue to grow at even higher rates, powered by software as-services and by the increasingly pervasive communication services that will grow above the average world GDP growth rate for the next decades.

IT and wireless communications devices are forecasted to move into most objects the humans relate to. Chips with simple processors and communicators will be embedded into buildings and most life-related engines, as ubiquitous as paints or information ducts. The everdecreasing cost of chips in this micro-and nano-worlds provides the efficiency gains that will make this IT explosion viable. The integration paradigm in semiconductor circuits -reliable and low-cost due to mass-production -will ultimately make it viable to connect 10 11 to 10 12 objects simultaneously to the internet, roughly hundreds of IP-powered systems or nodes per individual, in average.

The grand challenges in computer science will be shaped by this tera-scale number of complex embedded hardware, autonomous systems and communicating devices, all interacting much like generalpurpose computers do today over the Internet protocols. What will be the key enablers to this internet-of-things? In our view, towards 2030 the main-stay of the electronics integration technology will continue to be nano-scaled CMOS devices manufactured on silicon wafers. To which disruptive, yet-in-research devices will be added, to be made compatible with silicon ultra-clean in-fab processing. For instance, solid-stage storage devices with 5-10 nm-sized devices for each 1-bit of RAM, integrated in the range of 256 Gbits/chip is within reach of massproduction in the next 10 years. Still manufactured in CMOS. Also other types of sensors, which will be compatible with -if not on the same -silicon substrate as the dense CMOS devices, will bring the "sensing-and-computing" hardware integration into a great variety of products and applications. With great benefits resulting thereof for health-care, cheap communications, and intelligent machines. These will sense tens of environmental variables, do analog and digital processing in CMOS, and then act more and more autonomously.

Mature electronic packaging technologies at the 10-100 micron scale will continue to evolve to provide increasing hardware power efficiency. The 3-D integration will make new systems into compact volumes -with silicon dies in them, interconnected by fine wires (10 µm to 40 µm wide). While this is an evolutionary scenario drawn in this paper, its enormous technical and scientific impacts in terms of building ever-more complex systems have to be modeled, designed and fabricated as computer systems in the giga-scale era. Most importantly, because such systems are of heterogeneous nature, in which sensing physical events is as important as communicating information over RF devices; all with many digital processors and dedicated software embedded at their core. Moreover, one can assert that the impact on Computer Science brought by disruptive device technologies, even at the molecular level, is most often a change of focus at the system to model, instead of the introduction of a radically new scientific methodology in Computer Science. Hence, Computer Systems research will continue to thrive on this method: system modeling, verify/refine the computing model, actual design, and finally, realize and fabricate those complex systems. Designing them today is an extremely complex task, in which hardware integration capabilities in silicon already surpass the capacity to design complex systems-on-chip timely. Impacts on the ICT (information and telecommunication technologies) due to this heterogeneous integration will be enormous. The companies that may lead the pack in modeling, specification, designing and also manufacturing of those nano-circuits are poised to rip the most economic benefits in the world ICT market. Clever and IP-powered electronic devices will also unveil new large IT applications and markets This paper is organized as follows: in section 2 we address the ITC grand challenges and the ITRS roadmap for the world electronics industry. Section 3 briefly addresses roadblocks to continuing downscaling (size reduction) of circuits on planar structures and the emerging alternatives for silicon. Section 4 presents the systems-onchips challenges, which are more relevant to overcome when dealing with computer systems design. In Section 5 the impacts for the future of the hardware industry will be addressed, while section 6 concludes this paper.

Related Work

The advances in ICT technologies present grand challenges for advanced research in computing systems [START_REF]Grand Challenges in Computer Science Research in Brazil 2006-2016[END_REF]. The most likely scenario in the global nano-electronics industry hints for transitional and nonreplacing integrated technologies to be introduced with silicon devices -far from full replacement of the latter. For reasons that are dealt with in sections 3 and 4 of this paper, it is very likely that a transition to nonsilicon IC technologies will not take place in the next 20 years.

The most comprehensive industry expert's panel publishes the ITRS (International Technology Roadmap for Semiconductors) roadmap [START_REF]The International Technology Roadmap for Semiconductors -2009[END_REF]. The roadblocks to future progression in terms of integration into a silicon surface are well mapped, and several problems with yet unknown technical solutions are pointed out and updated yearly in that roadmap. The significance of those roadblocks is by no means saying that silicon will be replaced as the implementation technology -instead it is pointing to likely events that could be "showstoppers" for more integration onto silicon. Once overcoming them, the industry envisions the goal of fabricating flash memories with densities up to 256 to 512 Gbits/chip by 2021, compared to 16G -32G bits/chip today. The industry forecasts these densities using nano-CMOS, still on silicon chips. Table 1 shows the predictions by experts of the ITRS panel up to the year 2024, for several circuit-meaningful dimensions in CMOS technologies: half-pitch in flash memories uncontacted polycides (polysilicon with silicides on top), photoresist printed gate length, and physical gate lengths in state-of-the art microprocessor in mass production (MPUs, in Table 1). The technology roadblocks that exist for the continuing scaling down to 7 to 8 nm technology by 2024, with physical gate lengths of such quantumconfined electron wavelength, are too many to discuss in short. Compared to 23nm of nano-CMOS 32nm technologies currently (2010) in production in selected state-of-the-art nano-electronics production facilities, areal densities can be improved by a factor of about10-15 times. Producing such physical channel lengths of the order of the silicon wavelength will mean effectively quantum devices, where energy bands will considerable differ from the bulk semiconductor. The minimum physical length evolution in the past and future is shown in Figure 2, in a log y-scale, to show the enormous scaling achieved in microelectronics since 1970. This dimension downscaling alone does not provide the full picture. A factor of 4 to 5 in the transistor length reduction, from today to 2020, can lead to a 10-15X (maximum 20X)

integration gain, at best, if measured in logic gates per square millimeter of silicon area, considering the logic part of a system-onchip design. The point is that logic gates are very different than digital cells for storing bits. For this reason, we foresee a large divergence in the semiconductor industry paths for two kinds of products: a) memory chips, b) processing (analog or digital) chips, named MPU/ASIC in Table 1. For both types, the 3-D integration will provide another leap in terms of systems integration. With gains on the order of 10X -100X in integration density, at a lower cost than planar-only downscaling and integration. The ITRS industry panel assesses continuously the emerging devices, which are candidates to replace silicon. Figure 1 from ITRS conceptually separates the emerging devices in terms of the state variables used to enable in the physical world the digital state abstraction (charge, as in CMOS devices, phase state of a molecule or atom, and spin or magnetic number state of a given electron level or molecule, respectively). The devices in the red polygon (resonant tunneling device -RTD, single-electron SET switch) are nonconventional devices also fabricated on silicon planar technology. Currently the carbon nanostructures (single plane, carbon nano-tubes -CNTs, multi-walled tubes, etc) are the most likely candidates for the non-silicon transistor. These devices are being pursued at the research laboratories precisely because they can be manufactured by keeping compatibility with conventional planar CMOS silicon fabrication. Low dimensionality structures (2-D monoatomic layers) require an extremely clean surface on which to be built, like those of silicon wafers today. In fact, 2-D mono-layers of atoms on semiconductors were demonstrated in labs since the late 1970s. The aforementioned compatibility is the main reason as to why CNTs are considered the alternative transistor, replacing nanowires of silicon -or most likely sharing the silicon wafer surface with silicon nanowires over insulators. The alternatives in spintronics or molecular devices will not be described here, even though they deserve careful discussion as revolutionary alternative candidates in the future technology roadmaps. These emerging devices are being pursued in pre-competitive research phase exactly because they do not rule out the compatibility with current silicon technologies. These alternatives are in the infancy of materials and devices research, well behind the systems integration capability of current nano-CMOS technologies.

3

The "More Moore" Brick-Walls

The technical and physical roadblocks that are forecast for silicon technology evolution down the integration path have different natures and assumptions. The limits or "brick-walls" imposed to silicon scaling that are of a physical nature are shown in Figure 2. The oxide thicknesses in MOSFET transistors today have reached 1 (one) nanometer to 1.5 nm, which is the lower limit for direct metal-to-semiconductor electron tunneling through the insulator. This limit cannot be surpassed, and the solution was to replace silicon-dioxide by another insulator with a higher dielectric constant. This material solution is already in production at leading fabrication of 45nm nano-CMOS today. Device structures at 10nm sizes have quantum-mechanical behavior since the conduction band electron wave-length for a thermal-voltage average energy is typically around 10nm. This limit will be attained by the physical gate lengths (Lg) of production transistors in the year 2020, as predicted by ITRS in Table 1.

In Figure 2 any dimension below 0.3 nm is certainly hypothetical, since this is just the separation between individual nuclei of the atoms in the silicon solid, which is a physical scale at which the electron orbital's are probabilistically distributed as quantum particles binding the atoms. This limit is marked in Figure 2, and it is clearly physically unattainable in the gate oxide thickness. Instead, higher-K dielectrics will be used to surmount this barrier. Those are limits to the evolution of current CMOS silicon chips, which combined to the economics of this industry will eventually call for a " show-stopper" in terms of CMOS down-scaling in the Lg (physical gate length) curve in Figure 2.

The first ITRS roadmaps (ITRS, 2007) were introduced to predict the evolution of the CMOS technology in the time period marked in Figure 2 by the top arrow. Some industry experts forecast that at 16nm CMOS node (for which 7 to 9 nm Lg will be the physical transistor length, the same magnitude of the in-band electron wavelength in Fig. 2), the circuits will be at the limit of its technical and economical viability, at least for processors. And this could occur before 2020. Memory devices could experience even further downscaling, hence an increasing divergence between memory and processor CMOS technologies is forecasted by the authors. It is important that the challenges for CMOS downscaling be understood as a combination of factors of the natures above-mentioned: i) economical ii) technical, iii) electrical, and iv) physical or materials. While those roadblocks combined may hinder the mainstream use of 16nm CMOS in 2020, they will not drive silicon technology out of the mainstay, or make current silicon technologies less viable. The "more-Moore" brick-walls will not be dealt with in detail here, since they are most out of the scope of architectural challenges. The relevant point is that no other economically and technically viable integration technology other than CMOS is within sight. The economic gains of the hardware systems integration will be moved into the "more than Moore" devices, which are addressed in the next section.

SIZE (F m), Voltage (Volts) vs. Year

At ITRS roadmap introduction (extrapolated)

4

Grand Challenges for Systems-On-Chips Integration

The most important computing devices in the future will be at the leafend of the Web, as always-on, ambient-aware micro-devices. For their impact to be far-reaching, they will have to be compact, resilient to failures and attacks, communicating through RF. They are ubiquitous, in most senses of their operation. This will be the economic driver to sustain the growing of the computing infrastructure into most objects.

The main challenges for the design of this new hardware are listed below, according to the characteristics of the hardware architectures that will need considerable research and breakthroughs.

Heterogeneous Hardware Integration

Silicon integration technology will not reach the end of affordable fabrication on planar structures on-wafer in the foreseeable future.

Going below 10nm CMOS in all film levels is still uncertain for technical reasons aforementioned. The new trend of 3-D, multi-stack, multi-die integration will be an enabling technology that will push the integration level not only a factor of 100 over conventional planar silicon: it will allow heterogeneous integration of systems-in-package that will contain: transducers to electro-optical devices, sensors, actuators, besides the usual processor and memory subsystems. The socalled more-than-Moore path to integration will provide more complex and new functions of high value for the IT devices. The 3-level stack of mass-produced digital cameras is today just an example of a system technology that has just begun. By 2020 3-D integration will make viable powerful massively parallel computers on few cubic centimeters, with 1K to 10K CPUs, for which the power efficiency and dissipation is the single most important design constraint.

An important impact on computing and communication will happen with the opto-electronics integration. Currently the transducers like lasers and photodetectors for serial optical communication links are done in III-V (like InP, InGaAsP) compound semiconductors. This is a niche market that may merge into 3-D packages with silicon substrates. Recent developments on photonic devices with nano-structured silicon show promising perspectives for optic emitters on silicon -an important breakthrough. This will provide more integration, not an optical computer, since these new devices are well suited for serial communication links, not information processing. The photoelectronics systems in the future could move onto silicon substrates, narrowing the market for III-V semiconductor devices like LEDs and discrete semiconductor lasers.

Nano-power Computing for Autonomic Systems

The research on autonomic systems will strive on a technology that has yet to be discovered: computing systems that can reliably compute in bursts, at very low MIPS rates, and still be able to communicate to the next hierarchy at the network, using average nano-watts over long periods of time (years) and few micro-watts over short communication times. Heterogeneous integration will be key again to provide intelligent energy scavenging from the environment for such devices. This is a well-known research field in CS, which still requires breakthrough-engineering solutions at the circuit level.

Design and Architectural Complexity

The sequential computing paradigm and the ever-increasing complexity of systems-on-chip are considerable challenges to be overcome at the system design tools. Massively parallel systems are viable to integrate for general computing onto single chips. The applications and the parallel programming models are key to demonstrate an efficient use of such parallelism. The restrictions are well known since the mid-80s research on parallel -and room-scaled systems: While few parts could be computing, other parts sit idle wasting power. For this reason, the software stack necessary to exploit effectively the massively parallel systems also needs challenging innovation.

The application-specific complex systems can decompose the applications and map it beforehand to specific silicon cores. Some could be programmable cores, some certainly dedicated cores. These systems are, for instance, multiprocessors SoCs that are specifically designed for certain applications. This is viable for network processing, media processors (audio & video streams), and pattern matching processing. General computing is a different challenge though. Designing in parallel and making effective usage of hundreds of processors simultaneously is a methodology yet to be dealt with effectively in the computer science research community.

Simple IP objects -sense-compute-communicate

The future Net or Internet will have 10 11 to 10 12 objects interconnected -from PDAs to vehicles to mundane appliances. Communication hardware has to be cheap (integrated in silicon, with processors and memory), hence mass-produced. And this ubiquitous computing era will be enabled in silicon chips -not in molecular level devices, for certain. Molecular devices will find applications in dense memories at Tera-scale bits/cm 2 , but for radiation fields for communication over 1m to 100m the technology requires tens of FW or even mW power, and this RF systems requires much larger silicon area than Mbits of storage.

The first appliances to reach 100% connectivity are the communication and entertainment gadgets (like phones, audio and video systems) that empower individuals to communicate.

The market driver for electronics now and into decades ahead will be at the leaf-cells of this net-of-things, in local wireless personal networks (PANs). And these PANs will have simple objects that have to do simple tasks to empower the Net to a ubiquitous phase: to sense, to compute efficiently and to communicate with a small bandwidth to the next IP hop. Most connected objects will have one IP address, but locally will interoperate with multiple sensors and computing deviceswhich are to be cheap and simple to design. For those, the conventional nano-scale CMOS, at the current level of 65nm or below is more than sufficient. In fact the 45nm CMOS technology available today is too expensive for most system needs in ubiquitous communication. Energy transducing at FW level requires area, not area reduction. Smaller, in this case, does not mean better. With sensors integration on-chip this is often the case also. High performance analog sub-systems, with large signal-to-noise ratio, also do not scale in total silicon area as they are designed in more advanced CMOS.

Electronic Design Automation Tools

The quality of the SoCs design is directly dependent of the quality of the EDA (Electronic Design Automation) tools available. So, the challenge is to find out algorithms that can emulate the skills and strategies of experienced designers and cope with the restriction and features of new fabrication technologies. The variability of recent and future technologies demands new design tools sets, tuned to new design methodologies, which could provide reliable SoCs even using nonreliable components. Also to minimize power and delay there is a strong request to reduce at most the amount of transistors used to implement a function [START_REF] Reis | Design Automation of Transistor Networks, a New Challenge[END_REF]. The reduction of the needed number of transistors to implement a function helps to reduce area, and doing this the average length of interconnections will also be reduced, and consequently the delay will also be reduced. But maybe the main advantage on reducing the number of transistors is the reduction on the static power consumption due to the leakage current [START_REF] Reis | Design Automation of Transistor Networks, a New Challenge[END_REF]. The traditional standard cell approach is far away from an optimal physical design approach, as the number of available cells in a traditional cell library has no more than 150 different logic functions. If we put a limit of 4 stacked transistors in a CMOs circuit the number of possible logic functions goes to 3503 [START_REF] Detjens | Technology Mapping in MIS[END_REF], several times more than the number of functions available in a traditional cell library. So, it is needed a tool that would be able to generate any kind of transistor network, even with different number of P and N transistors. ASTRAN [START_REF] Ziesemer | Transistor Level Automatic Layout Generator for non-Complementary CMOS Cells[END_REF] is a tool that can do it.

Also, in a cell library we find normally 3 different sizing for each cell.

When doing the cell generation on the fly we can do any sizing we want. So, a cell is automatically customized to the location of the circuit where it will be inserted. The Physical Design at a Network of Transistors Level depends on the construction of an all-new physical design approach.

Another challenge is the search for efficient EDA tools to cope with the design of 3D chips.

Impacts on The Global Hardware Industry

The ICT hardware is produced in complex industries for the global IT market. The electronics industry is globally a 1.6 Trillion US dollars industry, in which the key in its supply chain are the semiconductor chip industry and the software industry. The semiconductor industry accounted for around US$ 273 Billion revenues in the 2007 calendar year.

The integrated circuits (ICs) are high tech intermediate industrial goods, essential for all electronics. The system drivers for the IC industry can be separated in the following categories: a) portable/consumer devices; b) networking and communication; c) medical electronics; d) office and departmental computing devices; e) automotive, and f) defense electronics. The ICT hardware is the most important driver for the semiconductor industry. The new market drivers for ICT are the devices for the ubiquitous, ambient-aware, permanently-on computing devices. Mostly of light computing load, but extreme mobility and energy autonomy. The intelligent objects of the future InterNet will require cheap, and yet powerful and communicating devices. These everlasting requirements mean that silicon circuits on planar wafers will not become economically unviable in the foreseeable future. Quite the contrary, the semiconductor industry will be a key enabler of the next generation computing -and in all spectrum of computing power. Uninformed is the confusion to be made with the trend to draw and fabricate nano-wires onto silicon substrates -the silicon manufacturing for CMOS transistors below 10nm is technically feasible, although such manufacturing is currently ruled out as being too costly. And not viable with photolithography tools that today use deep UV (ultraviolet) 193 nm light sources to fabricate 50nm device structures. Hence, the experts in technology presently assert that it may not be viable to assemble 10 Billion dollars fabrication lines for very high volume of silicon, but they do not contradict the fact that 45 nm to 180 nm CMOS nano-devices are economically the viable integration choice, now and into future generations. In this reasoning, the CMOS silicon technologies and their derivatives will be mainstream for an industry that reached 270 billion dollar yearly, and it is bound to increase.

On the systems design area, the impact of complex systems integration in silicon has already established a global economic paradigm for systems development: the design teams in the nano-electronics industry are increasingly global, and they require a tight integration of software embedding techniques and hardware design. The latter enabling the former. The main impacts for the industry in the future are: a) Managing complex systems design of ever increasing complexity hardware in global, multi-national engineering teams of software and hardware developers. The industry goal is to manage the high Non-Recurring Engineering (NRE) expenses, as well as to develop products that reach high volume scale quickly. General computing/communication devices are by definition high volume in the global markets. Embedded software is essential to enable services and other country-specific features, while the chip devices will have to truly global enabler.

b) The arrangement of 16nm-22nm CMOS factories around intercompany alliances for manufacturing. The complexity and challenges of CMOS manufacturing are to be overcome only to the extent that the integration benefits override the competition and can financially offset the large investments for CMOS wafer fabs. Such alliances are growing since the inception of Sematech in the 1980´s, an organization that brings together development teams from tens of different leading semiconductor companies to develop the key technologies for the future of semiconductor manufacturing. c) Design methodologies will have to incorporate "more-than-Moore" heterogeneous device design. Integrating optics, sensors, actuator, and the like will require more complex and diverse EDA tools, dealing with other domains, not just digital systems design. d) Design methodologies to cope with the request of strong reduction on power consumption. The cost of transistor is being reduced more and more, but the cost of energy to work a transistor is more and more expensive, as well the mechanisms to do power dissipation.

d) The integration technologies of importance are both on-chip planar tooling, as well as multi-chip 3-D stacking with through-silicon vias. This system-in-package trend is to use silicon thinned-wafers with chips on top, similar to what a PC board does with copper. Hence, silicon will be replacing board layers, instead of being replaced by emerging devices.

e) The trend towards miniaturized components on a packaged 3-D system, of about 1 to 5 cm3, will be the mainstream in the 2020´s, or even earlier. This is a transitional technology that will not drive silicon out of the computing -it will instead thrive on it. f) 3-D integration is a key technology that will further even more the divergence between manufacturing technologies for memory on-{bampi,reis}@inf.ufrgs.br silicon, and manufacturing technologies for processors, sensors, actuators and RF front-end circuits.

Conclusions

This paper discussed the challenges for ICT hardware integration technologies. In our scenario we dismiss the "beyond silicon" jargon commonly used as a synonym for silicon technology full replacement.

Future disrupting technologies will have to find compatibility with computing-on-silicon, 3-D stacking of dies or otherwise they will be ruled out as unviable by the leading hardware manufacturers.

Transitional technologies are likely to emerge, in which at the nanoscale semiconductor materials other than silicon (Si) will be used. Si substrate will still hold submicron-scale devices. This is a reality today, with germanium 2-D ultra-thin layers (sub-10-nm thicknesses) as part of 20nm CMOS transistors. Future transitional technologies will include carbon on different forms and shapes (tubes or planes called graphenes), and even light-emitting devices with nano-particles. All being held by a silicon matrix. Transitional technologies will enable new systems integration on silicon, even electro-optics integration.

In this paper the authors proposed that: i) nano-scaled CMOS on silicon will remain the basic technology well into the 2020s, and will still be the key for electronics systems innovation; ii) non-silicon technologies that are compatible with the silicon substrate and can co-exist in the silicon fabrication line will be the winner technologies for the next massive hardware platform of commercial significance for general computing: heterogeneous system-in-package, with the most valuable general computing and memory still relying on silicon chips with complex 3-D integration between dies; iii) the CMOS technology evolution will diverge into two CMOS tiers: one technology for very dense memories, tera-scale bits on-the-same-chip, for main memory, and the other CMOS tier for multi-processors and x-level caches on a single chip. This latter CMOS tier will be used for programmable logic devices, which will continue to play a key role in computing systems design well into the future.

The architectures with over 1K or 10K processors per 3-D package (less than 1 to 3 cm3) will be the main high-end computing engines for servers in the 2020s. The issues that are relevant to the industry are:

how to move forward in heterogeneous integration to create value and commercial opportunities in computer systems design; and how to create value and new technology jobs by fabricating the devices that embed ICT intelligence and bring to fruition the capacity to envision future ICT products. Not the least, industry has to produce them on the scale that the economics of this industry dictates, as envisioning is easy, making them is very challenging. In the 2020s and beyond, ICT will still be relying on silicon technology.

Figure 1 .

 1 Figure 1. Conceptual hierarchy of alternative computing devices (ITRS, 2007)

Figure 2 ,

 2 Figure 2, Evolution of CMOS technology: the minimum supply voltage, oxide thickness and junction depth. Comparison to basic physical limits -electron wavelength in conductionband and distance between silicon atoms [5].

Table 1 Evolution

 1

		of CMOS Scaling [ITRS, 2009]
	Year of Fabrication	2009 2012 2015 2018 2021 2024
	Uncontacted poli-Si ½ pitch	38	25	18	12.6	8.9	6.3
	[nm]
	MPU/ASIC Metal_1 ½ pith	54	32	21	15	10.6	7.5
	[nm]
	MPU Printed Gate Length	47	31	22	15.7	11.1	7.9
	[nm]
	MPU Physical Gate length	29	22	17	12.8	9.7	7.4
	[nm]
	Bits/chip DRAM production	2G	4G	8G	16G	32G	64G
	[Gb]
	Bits/chip FLASH production	22G	32G	64G	256G 512G 2048G
	[Gb] 2 bits/cell

{bampi,reis}@inf.ufrgs.br

Acknowledgements

The authors acknowledge the support of CNPq and FINEP for their research in micro-and nano-electronics, as well as the PGMICRO and PPGC graduate students and faculty members at UFRGS Federal University. This work is being supported by CNPq through the Millennium Institute NAMITEC (Network of Excellence Centers) and by the current National Institute (INCT) on Nano-electronics, which has more than 15 Universities working in challenging aspects of micro and nano-circuits integration in Brazil.