No description available.

Pipelined circuits operate as an assembly line that starts processing new instructions while older ones continue execution. Control properties specify the correct behaviour of the pipeline with respect to how it handles the concurrency between instructions. Control properties stand out as one of the most challenging aspects of pipelined circuit verification. Their verification depends on the datapath and memories, which in practice account for the largest part of the state space of the circuit. To alleviate the state explosion problem, abstraction of memories and datapath becomes mandatory. This thesis provides a methodology for an efficient abstraction of the datapath under all possible control-visible behaviours. For verification of control properties, the abstracted datapath is then substituted in place of the original one and the control circuitry is left unchanged. With respect to control properties, the abstraction is shown conservative by both language containment and simulation. For verification of control properties, the pipeline datapath is represented by a network of registers, unrestricted combinational datapath blocks and muxes. The values flowing through the datapath are called parcels. The control is the state machine that steers the parcels through the network. As parcels travel through the pipeline, they undergo transformations through the datapath blocks. The control- visible results of these transformations fan-out into control variables which in turn influence the next stage the parcels are transferred to by the control. The semantics of the datapath is formalized as a labelled transition system called a parcel automaton. Parcel automata capture the set of all control visible paths through the pipeline and are derived without the need of reachability analysis of the original pipeline. Datapath abstraction is defined using familiar concepts such as language containment or simulation. We have proved results that show that datapath abstraction leads to pipeline abstraction. Our approach has been incorporated into a practical algorithm that yields directly the abstract parcel automaton, bypassing the construction of the concrete parcel automaton. The algorithm uses a SAT solver to generate incrementally all possible control visible behaviours of the pipeline datapath. Our largest case study is a 32-bit two-wide superscalar OpenRISC microprocessor written in VHDL, where it reduced the size of the implementation from 35k gates to 2k gates in less than 10 minutes while using less than 52MB of memory.

In this dissertation, the design and analysis of several fast arithmetic components are presented. Our contributions focus on the fast CORDIC rotation architectures and multipliers. In the CORDIC design, we proposed a fast rotation architecture that can reduce by half the average number of rotations. Furthermore, a new parallel CORDIC rotation algorithm and architecture (called para-CORDIC) is proposed that leads to smaller area and delay compared with the conventional CORDIC algorithm and previous works. In the design of the multiplier generator, a delay-efficient algorithm is used to perform the partial products summation and the final addition during the synthesis of fast parallel multipliers based on standard cell library or other full-custom circuit components. In the field of fixed-width multiplier designs, a lower-error fixed-width carry-free multiplier with low-cost compensation circuits is proposed that has smaller absolute average errors and variances compared with pervious methods.

During the last forty years, advancements have pushed state-of-the-art placers to impressive performance placing modern multimillion gate designs in under an hour. Wide industry adoption of the analytical framework indicates the quality of these approaches. However, modern designs present significant challenges to address the multi objective requirements for multi GHz designs. As devices continue to scale, wires become more resistive and power constraints significantly dampen performance gains, continued improvement in placement quality is necessary. Additionally, placement has become more challenging with the integration of multi-objective constraints such as routability, timing and reliability. These constraints intensify the challenge of producing quality placement solutions and must be handled carefully. Exasperating the issue, shrinking schedules and budgets are requiring increased automation by blurring the boundary between manual and automated placement. An example of this new hybrid design style is the integration of structured placement constraints within traditional ASIC style circuit structures. Structure aware placement is a significant challenge to modern high performance physical design flows. The goal of this dissertation is to develop enhancements to state-of-the-art placement flows overcoming inadequacies for structured circuits. A key observation is that specific structures exist where modern analytical placement frameworks significantly underperform. Accurately measuring suboptimality of a particular placement solution however is very challenging. As such, this work begins by designing a series of structured placement benchmarks. Generating placement for the benchmarks manually offers the opportunity to accurately quantify placer performance. Then, the latest generation of academic placers is compared to evaluate how the placers performed for these design styles. Results of this work lead to discoveries in three key aspects of modern physical design flows. Datapath placement is the first aspect to be examined. This work narrows the focus to specifically target datapath style circuits that contain high fanout nets. As the datapath benchmarks showed, these high fanout nets misdirect analytical placement flows. To effectively handle these circuit styles, this work proposes a new unified placement flow that simultaneously places random-logic and datapath cells. The flow is built on top of a leading academic force-directed placer and significantly improves the quality of datapath placement while leveraging the speed and flexibility of existing algorithms. Effectively placing these circuits is not enough because in modern high performance designs, datapath circuits are often embedded within a larger ASIC style circuit and thus are unknown. As such, the next aspect of structured placement applies novel data learning techniques to train, predict, and evaluate potential structured circuits. Extracted circuits are mapped to groups that are aligned and simultaneously placed with random logic. The third aspect that can be enhanced with improved structured placement impacts local clock tree synthesis. Performance and power requirements for multi-GHz microprocessors necessitate the use of a grid-based clock network methodology, wherein a global clock grid is overlaid on the entire die area followed by local buffered clock trees. This clock mesh methodology is driven by three key reasons: First, full trees do not offer enough performance for modern microprocessors. Second, clock trees offer significant power savings over full clock meshes. Third, local clock trees reduce the local clock wiring demands compared to full meshes at lower level metal layers. To meet these demands, a shift in latch placement methodology is proposed by using structured placement templates. Placement configurations are identified a priori with significantly lower capacitance and the solutions are developed into placement templates. Results through careful experimentation demonstrate the effectiveness of these approaches and the impact potential for modern high-speed designs. / text

The ePUMA architecture is a novel master-multi-SIMD DSP platform aimed at low-power computing, like for embedded or hand-held devices for example. It is both a configurable and scalable platform, designed for multimedia and communications. Numbers with both integer and fractional parts are often used in computers because many important algorithms make use of them, like signal and image processing for example. A good way of representing these types of numbers is with a floating-point representation. The ePUMA platform currently supports a fixed-point representation, so the goal of this thesis will be to implement twelve basic floating-point arithmetic operations and two conversion operations onto an already existing datapath, conforming as much as possible to the IEEE 754-2008 standard for floating-point representation. The implementation should be done at a low hardware and power consumption cost. The target frequency will be 500MHz. The implementation will be compared with dedicated DesignWare components and the implementation will also be compared with floating-point done in software in ePUMA. This thesis presents a solution that on average increases the VPE datapath hardware cost by 15% and the power consumption increases by 15% on average. Highest clock frequency with the solution is 473MHz. The target clock frequency of 500MHz is thus not achieved but considering the lack of register retiming in the synthesis step, 500MHz can most likely be reached with this design.

Pipelined circuits operate as an assembly line that starts processing new instructions while older ones continue execution. Control properties specify the correct behaviour of the pipeline with respect to how it handles the concurrency between instructions. Control properties stand out as one of the most challenging aspects of pipelined circuit verification. Their verification depends on the datapath and memories, which in practice account for the largest part of the state space of the circuit. To alleviate the state explosion problem, abstraction of memories and datapath becomes mandatory. This thesis provides a methodology for an efficient abstraction of the datapath under all possible control-visible behaviours. For verification of control properties, the abstracted datapath is then substituted in place of the original one and the control circuitry is left unchanged. With respect to control properties, the abstraction is shown conservative by both language containment and simulation. For verification of control properties, the pipeline datapath is represented by a network of registers, unrestricted combinational datapath blocks and muxes. The values flowing through the datapath are called parcels. The control is the state machine that steers the parcels through the network. As parcels travel through the pipeline, they undergo transformations through the datapath blocks. The control- visible results of these transformations fan-out into control variables which in turn influence the next stage the parcels are transferred to by the control. The semantics of the datapath is formalized as a labelled transition system called a parcel automaton. Parcel automata capture the set of all control visible paths through the pipeline and are derived without the need of reachability analysis of the original pipeline. Datapath abstraction is defined using familiar concepts such as language containment or simulation. We have proved results that show that datapath abstraction leads to pipeline abstraction. Our approach has been incorporated into a practical algorithm that yields directly the abstract parcel automaton, bypassing the construction of the concrete parcel automaton. The algorithm uses a SAT solver to generate incrementally all possible control visible behaviours of the pipeline datapath. Our largest case study is a 32-bit two-wide superscalar OpenRISC microprocessor written in VHDL, where it reduced the size of the implementation from 35k gates to 2k gates in less than 10 minutes while using less than 52MB of memory.

Tanto nos circuitos integrados para processamento de sinais digitais quanto em microprocessadores, a parte operativa é o núcleo onde a computação dos dados é realizada. A geração deste bloco costuma ser crítica para o desempenho global dos dispositivos. Ferramentas específicas para a geração de parte operativa costumam tirar proveito da regularidade estrutural do circuito para produzir leiautes mais densos e com melhor desempenho. Este trabalho apresenta um novo fluxo de projeto para geração de parte operativa onde foi desenvolvido um gerador automático de leiaute de células CMOS com suporte à lógica não-complementar e um compilador de parte operativa. O uso destas duas ferramentas permite a rápida prototipação de uma biblioteca inteira de células lógicas otimizadas, para atender diferentes requisitos de desempenho, que em seguida são utilizadas para montagem de cada um dos blocos funcionais da parte operativa pelo compilador. Comparações feitas com a ferramenta de síntese de células lógicas mostraram que a metodologia desenvolvida é capaz de produzir resultados similares em área e tempo de geração que métodos exatos e ainda possui a vantagem de suportar o uso de múltiplas métricas de qualidade durante o posicionamento dos transistores. As células geradas automaticamente apresentaram acréscimo de área médio de apenas 14% quando comparado às standard-cells e com resultado de atraso e consumo de potência muito próximos ou melhores. Circuitos de parte operativa foram gerados automaticamente pelo compilador e apresentaram na média, menor área, consumo de potência e atraso que circuitos gerados com um fluxo de síntese automático para standard-cells. / Datapath is the core where all the computations are performed in circuits for digital signal processing and also in microprocessors. The performance of the whole system is frequently determined by the implementation of the datapath. Tools dedicated for synthesis of this unit are called datapath compilers and use to take advantage on the structural regularity of the circuit to produce dense layouts and with good performance. This work presents a new flow for datapath generation. An automatic cell synthesis tool with support to non-complementary logic is used in conjunction with a datapath compiler to achieve timing optimization and technology independence. The cell library produced as result of the synthesis process is used by the compiler to place the cells and generate each one of the datapath operators. Comparisons with other cell sythesis tools shown that our approach was able to produce results comparable in area and generation time. Automatically generated cells were compared to standard-cell layouts and presented an average area overhead of just 14% while our circuits presented better or very close delay and power consumption. The datapaths produced by the compiler were compared to a traditional standard-cell based synthesis design flow and presented smaller area, delay and power consumption in average than this approach.

Tanto nos circuitos integrados para processamento de sinais digitais quanto em microprocessadores, a parte operativa é o núcleo onde a computação dos dados é realizada. A geração deste bloco costuma ser crítica para o desempenho global dos dispositivos. Ferramentas específicas para a geração de parte operativa costumam tirar proveito da regularidade estrutural do circuito para produzir leiautes mais densos e com melhor desempenho. Este trabalho apresenta um novo fluxo de projeto para geração de parte operativa onde foi desenvolvido um gerador automático de leiaute de células CMOS com suporte à lógica não-complementar e um compilador de parte operativa. O uso destas duas ferramentas permite a rápida prototipação de uma biblioteca inteira de células lógicas otimizadas, para atender diferentes requisitos de desempenho, que em seguida são utilizadas para montagem de cada um dos blocos funcionais da parte operativa pelo compilador. Comparações feitas com a ferramenta de síntese de células lógicas mostraram que a metodologia desenvolvida é capaz de produzir resultados similares em área e tempo de geração que métodos exatos e ainda possui a vantagem de suportar o uso de múltiplas métricas de qualidade durante o posicionamento dos transistores. As células geradas automaticamente apresentaram acréscimo de área médio de apenas 14% quando comparado às standard-cells e com resultado de atraso e consumo de potência muito próximos ou melhores. Circuitos de parte operativa foram gerados automaticamente pelo compilador e apresentaram na média, menor área, consumo de potência e atraso que circuitos gerados com um fluxo de síntese automático para standard-cells. / Datapath is the core where all the computations are performed in circuits for digital signal processing and also in microprocessors. The performance of the whole system is frequently determined by the implementation of the datapath. Tools dedicated for synthesis of this unit are called datapath compilers and use to take advantage on the structural regularity of the circuit to produce dense layouts and with good performance. This work presents a new flow for datapath generation. An automatic cell synthesis tool with support to non-complementary logic is used in conjunction with a datapath compiler to achieve timing optimization and technology independence. The cell library produced as result of the synthesis process is used by the compiler to place the cells and generate each one of the datapath operators. Comparisons with other cell sythesis tools shown that our approach was able to produce results comparable in area and generation time. Automatically generated cells were compared to standard-cell layouts and presented an average area overhead of just 14% while our circuits presented better or very close delay and power consumption. The datapaths produced by the compiler were compared to a traditional standard-cell based synthesis design flow and presented smaller area, delay and power consumption in average than this approach.

Tanto nos circuitos integrados para processamento de sinais digitais quanto em microprocessadores, a parte operativa é o núcleo onde a computação dos dados é realizada. A geração deste bloco costuma ser crítica para o desempenho global dos dispositivos. Ferramentas específicas para a geração de parte operativa costumam tirar proveito da regularidade estrutural do circuito para produzir leiautes mais densos e com melhor desempenho. Este trabalho apresenta um novo fluxo de projeto para geração de parte operativa onde foi desenvolvido um gerador automático de leiaute de células CMOS com suporte à lógica não-complementar e um compilador de parte operativa. O uso destas duas ferramentas permite a rápida prototipação de uma biblioteca inteira de células lógicas otimizadas, para atender diferentes requisitos de desempenho, que em seguida são utilizadas para montagem de cada um dos blocos funcionais da parte operativa pelo compilador. Comparações feitas com a ferramenta de síntese de células lógicas mostraram que a metodologia desenvolvida é capaz de produzir resultados similares em área e tempo de geração que métodos exatos e ainda possui a vantagem de suportar o uso de múltiplas métricas de qualidade durante o posicionamento dos transistores. As células geradas automaticamente apresentaram acréscimo de área médio de apenas 14% quando comparado às standard-cells e com resultado de atraso e consumo de potência muito próximos ou melhores. Circuitos de parte operativa foram gerados automaticamente pelo compilador e apresentaram na média, menor área, consumo de potência e atraso que circuitos gerados com um fluxo de síntese automático para standard-cells. / Datapath is the core where all the computations are performed in circuits for digital signal processing and also in microprocessors. The performance of the whole system is frequently determined by the implementation of the datapath. Tools dedicated for synthesis of this unit are called datapath compilers and use to take advantage on the structural regularity of the circuit to produce dense layouts and with good performance. This work presents a new flow for datapath generation. An automatic cell synthesis tool with support to non-complementary logic is used in conjunction with a datapath compiler to achieve timing optimization and technology independence. The cell library produced as result of the synthesis process is used by the compiler to place the cells and generate each one of the datapath operators. Comparisons with other cell sythesis tools shown that our approach was able to produce results comparable in area and generation time. Automatically generated cells were compared to standard-cell layouts and presented an average area overhead of just 14% while our circuits presented better or very close delay and power consumption. The datapaths produced by the compiler were compared to a traditional standard-cell based synthesis design flow and presented smaller area, delay and power consumption in average than this approach.

Software defined radios have the potential of changing the fundamental usage model of wireless communications devices, but the capabilities of these transceivers are often limited by the speed of the underlying processors and FPGAs. This thesis presents the digital design for an impulse-based ultra wideband communication system capable of supporting raw data rates of up to 100 MB/s. The transceiver is being developed using software/reconfigurable radio concepts and will be implemented using commercially available off-the-shelf components. The receiver uses eight 1 GHz ADCs to perform time interleaved sampling at an aggregate rate of 8 Gsamples/s. The high sampling rates present extraordinary demands on the down-conversion resources. Samples are captured by the high-speed ADC and processed using a Xilinx Virtex-II Pro (XC2VP70) FPGA. The testbed has two components: a non real-time part for data capture and signal acquisition, and a real-time part for data demodulation and signal processing. The overall objective is to demonstrate a testbed that will allow researchers to evaluate different UWB modulation, multiple access, and coding schemes. As proof-of-concept, a scaled down prototype receiver which utilized 2 ADCs and a Xilinx Virtex-II Pro (XC2VP30) FPGA was fabricated and tested. / Master of Science