No description available.

No description available.

Abstract Multiple-input multiple-output (MIMO) techniques have been adopted since the third generation (3G) wireless communication standard to increase the spectral efficiency, data rate and reliability. The blessings of MIMO technologies for the baseband transceiver comes with the price of added complexity. Therefore, research on VLSI architectures for MIMO signal processing has generated a lot of interest over the past two decades. The advent of massive MIMO as a key technology for the fifth generation (5G) era also increased the interest in VLSI architectures related to MIMO communication research. In this thesis, we explored different VLSI architectures for MIMO detection and precoding algorithms. The detection and precoding are the most complex parts of a MIMO baseband transceiver. We focused on algorithm and architecture optimization and presented several VLSI architectures for MIMO detection and precoding. The thesis proposed an application specific instruction-set processor (ASIP) for a multimode small-scale MIMO detector. In a single design the detector supports minimum mean-square error (MMSE), selective spanning with fast enumeration (SSFE) and list sphere detection (LSD). In addition, a multiprocessor architecture is proposed in this thesis for a lattice reduction (LR) algorithm. A modified Lenstra-Lenstra-Lovasz (LLL) algorithm is proposed for LR to reduce the complexity of the original LLL algorithm. We also propose a massive MIMO detection algorithm based on alternating direction method of multipliers (ADMM). The algorithm is referred to as ADMM based infinity norm (ADMIN) constrained equalization. The ADMIN detection algorithm is implemented as an application-specific integrated circuit (ASIC) and for field programmable gate array (FPGA). A multimode precoder ASIP is also proposed in this thesis. In a single design, the ASIP supports norm-based scheduling, QR-decomposition, MMSE precoding and dirty paper coding (DPC) based precoding. / Tiivistelmä Moni-tulo moni-lähtö (MIMO) -tekniikoita on sopeutettu kolmannen sukupolven (3G) langattomasta viestintästandardista alkaen spektritehokkuuden, tiedonsiirtonopeuden ja luotettavuuden parantamiseksi. MIMO-teknologioilla on useita hyviä puolia suhteessa peruskaistan vastaanottimeen, mutta samalla monimutkaisuus on lisääntynyt. VLSI-arkkitehtuurien tutkimus MIMO-signaalinkäsittelyssä on sen vuoksi herättänyt paljon kiinnostusta viimeisen kahden vuosikymmenen aikana. Myös MIMO:n saavuttama asema viidennen sukupolven (5G) viestintästandardin pääteknologiana on lisännyt kiinnostusta VLSI-arkkitehtuureihin MIMO-viestinnän tutkimuksessa. Tässä tutkielmassa on tutkittu erilaisia VLSI-arkkitehtuureja MIMO-signaalien tunnistus- ja esikoodausalgoritmeissa. Signaalien tunnistus ja esikoodaus ovat peruskaistaa käyttävän MIMO-vastaanottimen monimutkaisimmat osa-alueet. Tutkielmassa on keskitytty algoritmien ja arkkitehtuurien optimointiin ja esitetty useita VLSI-arkkitehtuureja MIMO-signaalien tunnistusta ja esikoodausta varten. Tutkielmassa on ehdotettu sovelluskohtaisen prosessorin (Application Specific Instruction-set Processor eli ASIP) käyttä pienen mittakaavan monimuotodetektorissa. Detektorin rakenne tukee samanaikaisesti keskineliöpoikkeaman minimointia (MMSE), SSFE (Selective Spanning with Fast Enumeration) -algoritmia ja LSD (List Sphere Detection) -algoritmia. Lisäksi tässä tutkielmassa ehdotetaan monisuoritinarkkitehtuuria hilan redusointialgoritmille (Lattice Reduction eli LR). LR-algoritmia varten ehdotetaan muokattua Lenstra-Lenstra-Lovasz (LLL) -algoritmia vähentämään alkuperäisen LLL-algoritmin monimutkaisuutta. Lisäksi MIMO-signaalien tunnistusalgoritmin perustaksi ehdotetaan vuorottelevaa kertoimien suuntaustapaa Alternating Direction Method of Multipliers eli ADMM). ADMM-perustaisesta taajuusvasteen rajoitetusta ääretön-normi-korjauksesta (infinity norm constrained equalization) käytetään nimitystä ADMIN-algoritmi. ADMIN-tunnistusalgoritmi toteutetaan sovelluskohtaisena integroituna piirinä (Application-Specific Integrated Circuit eli ASIC) ohjelmoitavaa porttimatriisia (Field Programmable Gate Array eli FPGA) varten. Lisäksi ehdotetaan ASIP-monimuotoesikooderin käyttöä. ASIP-esikooderin rakenne tukee normiperustaista aikataulutusta, QR-hajotelmaa, MMSE-esikoodausta ja likaisen paperin koodaukseen (Dirty Paper Coding eli DPC) perustuvaa esikoodausta.

A Dual-Eulerian graph is a plane multigraph G that contains an edge list which is simultaneously an Euler tour in G and an Euler tour in the dual of G. Dual-Eulerian tours play an important role in optimizing CMOS layouts of Boolean functions. When circuits are represented by undirected multigraphs the layout area of the circuit can be optimized through finding the minimum number of disjoint dual trails that cover the graph. This paper presents an implementation of a polynomial time algorithm for determining whether or not a plane multigraph is Dual-Eulerian and for finding the Dual-Eulerian trail if it exists.

As VLSI technology scales to 65nm and below, traditional communication between design and manufacturing becomes more and more inadequate. Gone are the days when designers simply pass the design GDSII file to the foundry and expect very good man¬ufacturing and parametric yield. This is largely due to the enormous challenges in the manufacturing stage as the feature size continues to shrink. Thus, the idea of DFM (Design for Manufacturing) is getting very popular. Even though there is no universally accepted definition of DFM, in my opinion, one of the major parts of DFM is to bring manufacturing information into the design stage in a way that is understood by designers. Consequently, designers can act on the information to improve both manufacturing and parametric yield. In this dissertation, I will present several attempts to reduce the gap between design and manufacturing communities: Alt-PSM aware standard cell designs, printability improve¬ment for detailed routing and the ASIC design flow with litho aware static timing analysis. Experiment results show that we can greatly improve the manufacturability of the designs and we can reduce design pessimism significantly for easier design closure.

The main objective of this thesis is to develop a new design paradigm that combines microarchitecture design and circuit design with physical design for deep submicron technology. For deep submicron technology, wire delay will be the bottleneck for high performance microarchitecture design. Given the location information, inter-module latency can be calculated and hence, performance of the system can be estimated. In this thesis, we present a novel microarchitectural floorplanning that can help computer architects tackle the wire delay problem early in the microarchitecture design stage. We show that by employing microarchitectural floorplanning up to 40\% performance gain can be achieved. We also extend the framework to include three dimensional integrated circuit (3D-IC). 3D-IC is a new integration technique that is also introduced to address the wire delay issue in deep submicron technology. By combining microarchitectural floorplanning with 3D-IC, we show that wire delay impact can be reduced substantially. We also show that not only the module location, but also the module size can impact the performance. Adaptive search engine is introduced to identify the right module size. Using our adaptive search engine, we show that the system can identify good module sizes that help improve the performance with a shorter run-time than the limited runtime brute force search. Our microarchitecture-aware physical planning assumes that the target clock period can be achieved by inserting more flip-flops into the system. Inserting flip-flops along the wires can make the system meet the timing constraints without violating correctness of the circuit on that path because the function of the wire is to transfer signal from one location to another. However, inserting the flip-flop along the paths that consist of gates cannot guarantee the correctness of that path. A circuit optimization technique that allows flip-flop insertion along circuit path is called retiming. In this dissertation, We show that retiming can be used to achieve target clock period in microprocessor design. With the same target clock period, power reduction technique can be combined with retiming to help reduce the power consumption. We show that up to 34% power reduction can be achieved without timing violation. Furthermore, to tackle the problem of process variation in deep submicron, we also propose a modified retiming that can tolerate errors from statistical timing computation. We show that our statistical retiming algorithm provides close results to Monte-Carlo simulation results.

This thesis presents a low-power LDPC decoder design based on speculative scheduling of energy necessary to decode dynamically varying data frame in both block-fading channels and general AWGN channels. A model of a memory-efficient low-power high-throughput multi-rate array LDPC decoder as well as its FPGA implementa- tion results is first presented. Then, I propose a decoding scheme that provides the feature of constant-time decoding and thus facilitates real-time applications where guaranteed data rate is required. It pre-analyzes each received data frame to estimate the maximum number of necessary iterations for frame convergence. The results are then used to dynamically adjust decoder frequency and switch between multiple-voltage levels; thereby energy use is minimized. This is in contrast to the conventional fixed-iteration decoding schemes that operate at a fixed voltage level regardless of the quality of data received. Analysis shows that the proposed decoding scheme is widely applicable for both two-phase message-passing (TPMP) decoding algorithm and turbo decoding message passing (TDMP) decoding algorithm in block fading channels, and it is independent of the specific LDPC decoder architecture. A decoder architecture utilizing our recently published multi-rate decoding architecture for general AWGN channels is also presented. The result of this thesis is a decoder design scheme that provides a judicious trade-off between power consumption and coding gain.

Moore’s Law has driven a continuous demand for decreasing feature sizes used in Very Large Scale Integrated (VLSI) technology which has outpaced the solutions offered by lithography hardware. Currently, a light wavelength of 193nm is being used to print sub-65nm features. This introduces process variations which cause mismatches between desired and actual wafer feature sizes. However, the layout which affects the printability of a circuit can be modified in a manner which can make it more lithography-friendly. In this work, we intend to implement these modifications as a series of perturbations on the initial layout generated by the CAD tool for the circuit. To implement these changes we first calculate the feature variations offline on the boundaries of all possible standard cell pairs used in the circuit layout and record them in a Look-Up Table (LUT). After the CAD tool generates the initial placement of the circuit, we use the LUT to estimate the variations on the boundaries of all the standard cells. Depending on the features which may have the highest feature variations we assign a cost to the layout and our aim is now to reduce the cost of the layout after implementing perturbations which could be a simple cell flip or swap with a neighboring cell. The algorithm used to generate a circuit placement with a low cost is Simulated Annealing which allows a high probability for a solution with a higher cost to be selected during the initial iterations and as time goes on it tends closer to the greedy algorithm. The idea here is to avoid a locally optimum solution. It is also essential to minimize the impact of the iterations performed on the initial solution in terms of wirelength, vias and routing congestion. We validate our procedure on ISCAS85 benchmark circuits by simulating dose and defocus variations using the Mentor tool Calibre LFD. We obtain a reduction of greater 20% in the number of instances with the highest cell boundary feature variations. The wirelength and the number of vias showed an increase of roughly 2.2-8.8% and 1.2- 7.8% respectively for different circuits. The routing congestion by and large remains unaffected.

As VLSI technology scales to 65nm and below, traditional communication between design and manufacturing becomes more and more inadequate. Gone are the days when designers simply pass the design GDSII file to the foundry and expect very good man¬ufacturing and parametric yield. This is largely due to the enormous challenges in the manufacturing stage as the feature size continues to shrink. Thus, the idea of DFM (Design for Manufacturing) is getting very popular. Even though there is no universally accepted definition of DFM, in my opinion, one of the major parts of DFM is to bring manufacturing information into the design stage in a way that is understood by designers. Consequently, designers can act on the information to improve both manufacturing and parametric yield. In this dissertation, I will present several attempts to reduce the gap between design and manufacturing communities: Alt-PSM aware standard cell designs, printability improve¬ment for detailed routing and the ASIC design flow with litho aware static timing analysis. Experiment results show that we can greatly improve the manufacturability of the designs and we can reduce design pessimism significantly for easier design closure.

In this dissertation, we propose area-efficient Advanced Encryption Standard (AES) processor designs by applying four new common-subexpression-elimination (CSE) algorithms to the sub-functions that realize the various transformations in AES encryption and decryption. The first category of sub-functions is derived by combining adjacent transformations in each AES round into a new transformation. The other category of sub-functions is from the integrated transformations in the AES encryption and decryption process with shared common operations. Then the proposed bit-level CSE algorithm reduces further the area cost of realizing the sub-functions by extracting the common factors in the bit-level expressions of these sub-functions. The separate area-reduction effects of combinations, integrations and CSE optimization mentioned above are analyzed in order to examine the efficiency of each technique. Cell-based implementation results show that the area reduction rates of the AES processors with our proposed CSE methods achieve significant area improvement compared with Synopsys optimization results.