In this thesis a number of energy saving methods for a multiplier on algorithmic level are investigated. For the investigation a multiplier is constructed in VHDL, after which the circuit's performance is investigated. A number of techniques for reduced power consumption are introduced in the circuit and are then evaluated. The conclusions are that all investigated methods, pipelining, interleaving and voltage scaling, should be maximally made use of in order to minimize the power consumption. / I detta arbete undersöks ettantal energibesparande metoder för en multiplikator på algoritmnivå. För undersökningen konstrueras en multiplikator i VHDL, varefter kretsens prestanda undersöks. Ett antal tekniker för minskad effektförbrukning införs i kretsen och utvärderas därefter. Slutsatsen är att samtliga undersökta metoder, pipelining, interleaving och spänningsskalning, bör utnyttjas maximalt för att minimera effektförbrukningen.

This work is focused on the CORDIC algorithm for wireless LAN. The primary task is to create a VHDL description for CORDIC vector rotation algorithm. The basic research has been carried out in MATLAB. The VHDL implementation of the CORDIC algorithm is based on the results obtained from the MATLAB simulation. Mentor Graphics FPGA Advantage© for Xilinx 4010XL FPGA has been used for the hardware implementation.

The purpose of this thesis is to explore the formal verification technique of completion functions and equivalence checking by verifying two pipelined cryptographic circuits, KASUMI and WG ciphers. Most of current methods of communications either involve a personal computer or a mobile phone. To ensure that the information is exchanged in a secure manner, encryption circuits are used to transform the information into an unintelligible form. To be highly secure, this type of circuits is generally designed such that it is hard to analyze. Due to this fact, it becomes hard to locate a design error in the verification of cryptographic circuits. Therefore, cryptographic circuits pose significant challenges in the area of formal verification. Formal verification use mathematics to formulate correctness criteria of designs, to develop mathematical models of designs, and to verify designs against their correctness criteria. The results of this work can extend the existing collection of verification methods as well as benefiting the area of cryptography. In this thesis, we implemented the KASUMI cipher in VHDL, and we applied the optimization technique of pipelining to create three additional implementations of KASUMI. We verified the three pipelined implementations of KASUMI with completion functions and equivalence checking. During the verification of KASUMI, we developed a methodology to handle the completion functions efficiently based on VHDL generic parameters. We implemented the WG cipher in VHDL, and we applied the optimization techniques of pipelining and hardware re-use to create an optimized implementation of WG. We verified the optimized implementation of WG with completion functions and equivalence checking. During the verification of WG, we developed the methodology of ``skipping" that can decrease the number of verification obligations required to verify the correctness of a circuit. During the verification of WG, we developed a way of applying the completion functions approach such that it can deal with a circuit that has been optimized with hardware re-use.

New low power solutions for Very Large Scale Integration (VLSI) are proposed. Especially, we focus on leakage power reduction. Although neglected at 0.18u technology and above, leakage power is nearly equal to dynamic power consumption in nanoscale technology, e.g., 0.07u. We present a novel circuit structure, we call it sleepy stack, which is a combination of two well-known low-leakage techniques: the forced stack and sleep transistor techniques. Unlike the forced stack technique, the sleepy stack technique can utilize high-Vth transistors without incurring a large delay increase. Also, unlike the sleep transistor technique, the sleepy stack technique can retain exact logic state while achieving similar leakage power savings. In short, our sleepy stack structure achieves ultra-low leakage power consumption while retaining logic state. We apply the sleepy stack technique to both generic logic circuits as well as SRAM. At 0.07u technology, the sleepy stack logic circuits achieves up to 200X leakage reduction compared the forced stack technique with small (under 7%) delay variations and 51~118% area overheads. The sleepy stack SRAM cell with 1.5xVth achieves 5X leakage reduction with 32% delay increase or 2.49X leakage reduction without delay increase compared to the high-Vth SRAM cell. As such, the sleepy stack technique can be applicable to a design that requires ultra-low leakage power with quick response time while paying area and delay cost. We also propose a new low power architectural technique named Low-Power Pipelined Cache (LPPC). Although a conventional pipelined cache is mainly used to reduce cache access time, we lower supply voltage of cache using LPPC to save dynamic power. We achieve 20.43% processor dynamic energy savings with 4.14% execution cycle increase using 2-stage low-Vdd LPPC. Furthermore, we apply LPPC to the sleepy stack SRAM. The sleepy stack pipelined SRAM achieves 17X leakage power reduction while increasing execution time by 4% on average. Although this combined technique increases active power consumption by 33%, this technique is well suited for the system that spends most of its time in sleep mode.

Functional verification is a critical problem facing the semiconductor industry: hardware designs are extremely complex and highly optimized, and even a single bug in deployed systems can cost more than $10 billion. We focus on the verification of pipelining, a key optimization that appears extensively in hardware systems such as microprocessors, multicore systems, and cache coherence protocols. Existing techniques for verifying pipelined machines either consume excessive amounts of time, effort, and resources, or are not applicable at the bit-level, the level of abstraction at which commercial systems are designed and functionally verified. We present a highly automated, efficient, compositional, and scalable refinement-based approach for the verification of bit-level pipelined machines. Our contributions include: (1) A complete compositional reasoning framework based on refinement. Our notion of refinement guarantees that pipelined machines satisfy the same safety and liveness properties as their instruction set architectures. In addition, our compositional framework can be used to decompose correctness proofs into smaller, more manageable pieces, leading to drastic reductions in verification times and a high-degree of scalability. (2) The development of ACL2-SMT, a verification system that integrates the popular ACL2 theorem prover (winner of the 2005 ACM Software System Award) with decision procedures. ACL2-SMT allows us to seamlessly take advantage of the two main approaches to hardware verification: theorem proving and decision procedures. (3) A proof methodology based on our compositional reasoning framework and ACL2-SMT that allows us to reduce the bit-level verification problem to a sequence of highly automated proof steps. (4) A collection of general-purpose refinement maps, functions that relate pipelined machine states to instruction set architecture states. These refinement maps provide more flexibility and lead to increased verification efficiency. The effectiveness of our approach is demonstrated by verifying various pipelined machine models, including a bit-level, Intel XScale inspired processor that implements 593 instructions and includes features such as branch prediction, precise exceptions, and predicated instruction execution.

<p>In this thesis a number of energy saving methods for a multiplier on algorithmic level are investigated. For the investigation a multiplier is constructed in VHDL, after which the circuit's performance is investigated. A number of techniques for reduced power consumption are introduced in the circuit and are then evaluated. The conclusions are that all investigated methods, pipelining, interleaving and voltage scaling, should be maximally made use of in order to minimize the power consumption.</p> / <p>I detta arbete undersöks ettantal energibesparande metoder för en multiplikator på algoritmnivå. För undersökningen konstrueras en multiplikator i VHDL, varefter kretsens prestanda undersöks. Ett antal tekniker för minskad effektförbrukning införs i kretsen och utvärderas därefter. Slutsatsen är att samtliga undersökta metoder, pipelining, interleaving och spänningsskalning, bör utnyttjas maximalt för att minimera effektförbrukningen. </p>

This thesis demonstrate how pipelining in a RISC processor is achieved by implementing a subset of MIPS R2000 instructions on FPGA. Pipelining, which is one of the primary concepts to speed up a microprocessor is emphasized throughout this thesis. Pipelining is fundamentally invisible for high level programming language user and this work reveals the internals of microprocessor pipelining and the potential problems encountered while implementing pipelining. The comparative and quantitative flow of this thesis allows to understand why pipelining is preferred instead of other possible implementation schemes. The methodology for programmable logic development and the capabilities of programmable logic devices are also given as background information. This thesis can be the starting point and reference for programmers who are willing to get familiar with microprocessors and pipelining.

Este trabalho apresenta um novo modelo de busca especulativa de múltiplos fluxos de instruções em arquiteturas superescalares. A avaliação de desempenho de uma arquitetura superescalar com esta característica é também apresentada como forma de validar o modelo proposto e comparar seu desempenho frente a uma arquitetura superescalar real. O modelo em questão pretende eliminar a latência de busca de instruções introduzida pela ocorrência de comandos de desvio em pipelines superescalares. O desempenho de uma arquitetura superescalar dotada de escalonamento dinâmico de instruções, previsão de desvios e execução especulatva é bastante inferior ao desempenho máximo teórico esperado. Como demonstrado em outros trabalhos, isto ocorre devido às constantes quebras de fluxo, derivadas de instruções de desvio, e do conseqüente esvaziamento da fila de instruções. O emprego desta técnica permite encadear instruções pertencentes a diferentes fluxos lógicos, logo após a identificação de uma instrução de desvio, disponibilizando um maior número de instruções ao mecanismo de escalonamento dinâmico e diminuindo o número de ciclos com despacho nulo devido as quebras de fluxo. Algumas considerações sobre a implementação do modelo descrito são apresentadas ao final do trabalho assim como sugestões para trabalhos futuros. / This work presents a new model to fetch instructions along multiple streams in superscalar pipelines. Also, the performance evaluation of a superscalar architecture including this feature is presented in order to validate the model and to compare its performance with a real superscalar architecture. The proposed technique intents to eliminate the instruction fetch latency introduced by branch instructions in superscalar pipelines. The performance delivered by a superscalar architecture which incorporate dynamic instruction scheduling, branch prediction and speculative execution is not the expected one which should be at least proportional to the number of functional units. Related works have shown that constant stream breaks caused by disruptions in the sequential flow of control reduce the amount of instructions into the instruction queue. This technique allows instruction fetch through different logic streams, as soon as the branch instruction has been detected during the fetch. The scheduler needs a large instruction window to be able to schedule efficiently consequently the instructions window should hold as many instructions as possible to allow an efficient schedule. The improvement realized by the proposed scheme is to increase the size of the instruction window by putting there more instructions avoiding interruptions on the event of branch occurrence. Some considerations about the implementation of this model are presented at final as well as suggestions to future works.

Este trabalho apresenta um novo modelo de busca especulativa de múltiplos fluxos de instruções em arquiteturas superescalares. A avaliação de desempenho de uma arquitetura superescalar com esta característica é também apresentada como forma de validar o modelo proposto e comparar seu desempenho frente a uma arquitetura superescalar real. O modelo em questão pretende eliminar a latência de busca de instruções introduzida pela ocorrência de comandos de desvio em pipelines superescalares. O desempenho de uma arquitetura superescalar dotada de escalonamento dinâmico de instruções, previsão de desvios e execução especulatva é bastante inferior ao desempenho máximo teórico esperado. Como demonstrado em outros trabalhos, isto ocorre devido às constantes quebras de fluxo, derivadas de instruções de desvio, e do conseqüente esvaziamento da fila de instruções. O emprego desta técnica permite encadear instruções pertencentes a diferentes fluxos lógicos, logo após a identificação de uma instrução de desvio, disponibilizando um maior número de instruções ao mecanismo de escalonamento dinâmico e diminuindo o número de ciclos com despacho nulo devido as quebras de fluxo. Algumas considerações sobre a implementação do modelo descrito são apresentadas ao final do trabalho assim como sugestões para trabalhos futuros. / This work presents a new model to fetch instructions along multiple streams in superscalar pipelines. Also, the performance evaluation of a superscalar architecture including this feature is presented in order to validate the model and to compare its performance with a real superscalar architecture. The proposed technique intents to eliminate the instruction fetch latency introduced by branch instructions in superscalar pipelines. The performance delivered by a superscalar architecture which incorporate dynamic instruction scheduling, branch prediction and speculative execution is not the expected one which should be at least proportional to the number of functional units. Related works have shown that constant stream breaks caused by disruptions in the sequential flow of control reduce the amount of instructions into the instruction queue. This technique allows instruction fetch through different logic streams, as soon as the branch instruction has been detected during the fetch. The scheduler needs a large instruction window to be able to schedule efficiently consequently the instructions window should hold as many instructions as possible to allow an efficient schedule. The improvement realized by the proposed scheme is to increase the size of the instruction window by putting there more instructions avoiding interruptions on the event of branch occurrence. Some considerations about the implementation of this model are presented at final as well as suggestions to future works.

Este trabalho apresenta um novo modelo de busca especulativa de múltiplos fluxos de instruções em arquiteturas superescalares. A avaliação de desempenho de uma arquitetura superescalar com esta característica é também apresentada como forma de validar o modelo proposto e comparar seu desempenho frente a uma arquitetura superescalar real. O modelo em questão pretende eliminar a latência de busca de instruções introduzida pela ocorrência de comandos de desvio em pipelines superescalares. O desempenho de uma arquitetura superescalar dotada de escalonamento dinâmico de instruções, previsão de desvios e execução especulatva é bastante inferior ao desempenho máximo teórico esperado. Como demonstrado em outros trabalhos, isto ocorre devido às constantes quebras de fluxo, derivadas de instruções de desvio, e do conseqüente esvaziamento da fila de instruções. O emprego desta técnica permite encadear instruções pertencentes a diferentes fluxos lógicos, logo após a identificação de uma instrução de desvio, disponibilizando um maior número de instruções ao mecanismo de escalonamento dinâmico e diminuindo o número de ciclos com despacho nulo devido as quebras de fluxo. Algumas considerações sobre a implementação do modelo descrito são apresentadas ao final do trabalho assim como sugestões para trabalhos futuros. / This work presents a new model to fetch instructions along multiple streams in superscalar pipelines. Also, the performance evaluation of a superscalar architecture including this feature is presented in order to validate the model and to compare its performance with a real superscalar architecture. The proposed technique intents to eliminate the instruction fetch latency introduced by branch instructions in superscalar pipelines. The performance delivered by a superscalar architecture which incorporate dynamic instruction scheduling, branch prediction and speculative execution is not the expected one which should be at least proportional to the number of functional units. Related works have shown that constant stream breaks caused by disruptions in the sequential flow of control reduce the amount of instructions into the instruction queue. This technique allows instruction fetch through different logic streams, as soon as the branch instruction has been detected during the fetch. The scheduler needs a large instruction window to be able to schedule efficiently consequently the instructions window should hold as many instructions as possible to allow an efficient schedule. The improvement realized by the proposed scheme is to increase the size of the instruction window by putting there more instructions avoiding interruptions on the event of branch occurrence. Some considerations about the implementation of this model are presented at final as well as suggestions to future works.