The increasing prevalence and growing size of data in modern applications have led to high costs for computation in traditional processor-centric computing systems [1–20]. To mitigate these costs, the processing-in-memory (PIM) $[1,2,5,6$, 8,9,20-27] paradigm moves computation closer to where the data resides, reducing the need to move data between memory and the processor. Even though the concept of PIM was first proposed in the 1960s [24, 28], and various PIM architectures have been proposed since then [$10,17,18,20,29-65$], realworld PIM systems have only recently been manufactured [6670], among which the UPMEM PIM system [66, 67, 71] is the first PIM architecture to become commercially available. A general-purpose PIM system is often composed of regular DRAM (as its main memory) and specialized PIM DRAM DIMMs. A PIM module is a standard DDRx DIMM (module) with multiple PIM chips. Inside each PIM chip, there are multiple (e.g., 8) general-purpose in-order PIM cores, which have exclusive access to a DRAM bank and SRAM-based instruction/scratchpad memories.

High-Performance Computing (HPC) is shifting toward chiplet-based System-on-Chip (SoC) architectures, necessitating advanced simulation tools for design and optimization. In this work, we extend the gem5 simulator to support cachecoherent multi-chip systems by introducing a new chip-to-chip interconnect model within the Ruby framework. Our implementation is adaptable to various coherence protocols, such as Arm CHI. Calibrated with real hardware, our model is evaluated using PARSEC workloads, demonstrating its accuracy in simulating coherent chip-to-chip interactions and its effectiveness in capturing key performance metrics early in the design flow.

DRAM is a critical component of modern computing systems. Recent works propose numerous techniques (that we call DRAM techniques) to enhance DRAM-based computing systems’ throughput, reliability, and computing capabilities (e.g., in-DRAM bulk data copy). Evaluating the system-wide benefits of DRAM techniques is challenging as they often require modifications across multiple layers of the computing stack. Prior works propose FPGA-based platforms for rapid end-to-end evaluation of DRAM techniques on real DRAM chips. Unfortunately, existing platforms fall short in two major aspects: (1) they require deep expertise in hardware description languages, limiting accessibility; and (2) they are not designed to accurately model modern computing systems.We introduce EasyDRAM, an FPGA-based framework for rapid and accurate end-to-end evaluation of DRAM techniques on real DRAM chips. EasyDRAM overcomes the main drawbacks of prior FPGA-based platforms with two key ideas. First, EasyDRAM removes the need for hardware description language expertise by enabling developers to implement DRAM techniques using a high-level language (C++). At runtime, EasyDRAM executes the high-level software-defined memory system design in a programmable memory controller. Second, EasyDRAM tackles a fundamental challenge in accurately modeling modern systems: real processors typically operate at significantly higher clock frequencies than DRAM, a disparity that is difficult to replicate on FPGA platforms. EasyDRAM addresses this challenge by decoupling the processor–DRAM interface and advancing the system state using a novel technique we call time scaling, which faithfully captures the timing behavior of the modeled system.We validate EasyDRAM’s evaluation accuracy by comparing the memory latency profile of a real CPU-based system and its modeled implementation using EasyDRAM. We demonstrate the ease of use of EasyDRAM by evaluating two DRAM techniques end-to-end in a real FPGA-based system: (1) in-DRAM bulk data copy (i.e., RowClone) and (2) reduced-latency DRAM access that exploits the latency variation across DRAM cells. Implementing these two techniques requires no hardware modifications and only 325 lines of C++ code over EasyDRAM’s extensible code base. We compare our results to prior FPGA-based platforms. EasyDRAM yields more accurate results (e.g., by ≈20× for execution time) than the state-of-the-art related platform. We believe and hope that EasyDRAM will enable innovative ideas in memory system design to rapidly come to fruition. To aid future research, we open-source our EasyDRAM implementation at https://github.com/CMU-SAFARI/EasyDRAM.

International audience

International audience

GPUs are the prevailing solution to execute high-performance tasks (e.g., machine learning training). As the peak performance of modern GPUs increases with each generation, so does their thermal design power (TDP). Hence, identifying energy bottlenecks in the GPU architecture is crucial to designing more efficient architectures in the future. However, due to the complex proprietary nature of modern GPU architectures, providing a detailed breakdown of the GPU energy consumption is not trivial. The goal of this work is to estimate a lower bound for the energy consumed by data movement and storage in modern GPU architectures, leveraging internal power sensors. We establish a basic energy model for modern GPUs, focused on data movement to/from the hardware-managed caches and software-managed memories. We propose a methodology to calibrate the energy model using microbenchmarks, performance counters, and the internal power sensor. We experimentally calibrate the model on an A100 NVIDIA GPU. Then, we challenge the consistency of the results by cross-validating with modified microbenchmarks with additional instructions. Finally, we use the calibrated energy model to evaluate breakdowns for workloads of increasing complexity (e.g., a ResNet-50 training iteration with different software optimizations). Our results show that data movement dominates the dynamic energy consumption of the GPU (up to 84%), with DRAM accesses being the main contributor.

Training time has become a critical bottleneck due to the recent proliferation of large-parameter ML models. GPUs continue to be the prevailing architecture for training ML models. However, the complex execution flow of ML frameworks makes it difficult to understand GPU computing resource utilization. Our main goal is to provide a better understanding of how efficiently ML training workloads use the computing resources of modern GPUs. To this end, we first describe an ideal reference execution of a GPU-accelerated ML training loop and identify relevant metrics that can be measured using existing profiling tools. Second, we produce a coherent integration of the traces obtained from each profiling tool. Third, we leverage the metrics within our integrated trace to analyze the impact of different software optimizations (e.g., mixed-precision, various ML frameworks, and execution modes) on the throughput and the associated utilization at multiple levels of hardware abstraction (i.e., whole GPU, SM subpartitions, issue slots, and tensor cores). In our results on two modern GPUs, we present seven takeaways and show that although close to 100% utilization is generally achieved at the GPU level, average utilization of the issue slots and tensor cores always remains below 50% and 5.2%, respectively.

The computational workload involved in Convolutional Neural Networks (CNNs) is typically out of reach for low-power embedded devices. The scientific literature provides a large number of approximation techniques to address this problem. Among them, the Weight-Sharing (WS) technique gives promising results, but it requires carefully determining the shared values for each layer of a given CNN. As the number of possible solutions grows exponentially with the number of layers, the WS Design Space Exploration (DSE) time can easily explode for state-of-the-art CNNs. In this paper, we propose a new heuristic approach to drastically reduce the exploration time without sacrificing the quality of the output. The results carried out on recent CNNs (GoogleNet [1], ResNet50V2 [2], MobileNetV2 [3], InceptionV3 [4], and EfficientNet [5]), trained with the ImageNet [6] dataset, show over 5× memory compression at an acceptable accuracy loss (complying with the MLPerf [7] quality target) without any retraining step and in less than 10 hours. Our code is publicly available on GitHub [8].

Computer system simulators are major tools used by architecture researchers to develop and evaluate new ideas. Clearly, such evaluations are more conclusive when compared to commercial state-of-the-art architectures. However, the behavior of key components in existing processors is often not disclosed, complicating the construction of faithful reference models. The data prefetching engine is one of such obscured components that can have a significant impact on key metrics such as performance and energy.

Machine Learning (ML) frameworks are tools that facilitate the development and deployment of ML models. These tools are major catalysts of the recent explosion in ML models and hardware accelerators thanks to their high programming abstraction. However, such an abstraction also obfuscates the run-time execution of the model and complicates the understanding and identification of performance bottlenecks. In this paper, we demystify how a modern ML framework manages code execution from a high-level programming language. We focus our work on the TensorFlow eager execution, which remains obscure to many users despite being the simplest mode of execution in TensorFlow. We describe in detail the process followed by the runtime to run code on a CPU-GPU tandem. We propose new metrics to analyze the framework's runtime performance overhead. We use our metrics to conduct in-depth analysis of the inference process of two Convolutional Neural Networks (CNNs) (LeNet-5 and ResNet-50) and a transformer (BERT) for different batch sizes. Our results show that GPU kernels execution need to be long enough to exploit thread parallelism, and effectively hide the runtime overhead of the ML framework.

Hybrid storage systems (HSS) use multiple different storage devices to provide high and scalable storage capacity at high performance. Data placement across different devices is critical to maximize the benefits of such a hybrid system. Recent research proposes various techniques that aim to accurately identify performance-critical data to place it in a "best-fit" storage device. Unfortunately, most of these techniques are rigid, which (1) limits their adaptivity to perform well for a wide range of workloads and storage device configurations, and (2) makes it difficult for designers to extend these techniques to different storage system configurations (e.g., with a different number or different types of storage devices) than the configuration they are designed for. Our goal is to design a new data placement technique for hybrid storage systems that overcomes these issues and provides: (1) adaptivity, by continuously learning from and adapting to the workload and the storage device characteristics, and (2) easy extensibility to a wide range of workloads and HSS configurations.

Bulk bitwise operations, i. e., bitwise operations on large bit vectors, are prevalent in a wide range of important application domains, including databases, graph processing, genome analysis, cryptography, and hyper-dimensional computing. In conventional systems, the performance and energy efficiency of bulk bitwise operations are bottlenecked by data movement between the compute units (e.g., CPUs and GPUs) and the memory hierarchy. In-flash processing (i. e., processing data inside NAND flash chips) has a high potential to accelerate bulk bitwise operations by fundamentally reducing data movement through the entire memory hierarchy, especially when the processed data does not fit into main memory. We identify two key limitations of the state-of-the-art in-flash processing technique for bulk bitwise operations; (i) it falls short of maximally exploiting the bit-level parallelism of bulk bitwise operations that could be enabled by leveraging the unique cell-array architecture and operating principles of NAND flash memory; (ii) it is unreliable because it is not designed to take into account the highly error-prone nature of NAND flash memory. We propose Flash-Cosmos (Flash C omputation with-O ne-S hot M ulti-O perand S ensing), a new in-flash processing technique that significantly increases the performance and energy efficiency of bulk bitwise operations while providing high reliability. Flash-Cosmos introduces two key mechanisms that can be easily supported in modern NAND flash chips: (i) M ulti-W ordline S ensing (MWS), which enables bulk bitwise operations on a large number of operands (tens of operands) with a single sensing operation, and (ii) E nhanced S LC-mode P rogramming (ESP), which enables reliable computation inside NAND flash memory. We demonstrate the feasibility of performing bulk bitwise operations with high reliability in Flash-Cosmos by testing 160 real 3D NAND flash chips. Our evaluation shows that Flash-Cosmos improves average performance and energy efficiency by $3.5 \times /32 \times$ and $3.3 \times /95 \times$, respectively, over the state-of-the-art in-flash/outside-storage processing techniques across three real-world applications.

Long-latency load requests continue to limit the performance of modern high-performance processors. To increase the latency tolerance of a processor, architects have primarily relied on two key techniques: sophisticated data prefetchers and large on-chip caches. In this work, we show that: (1) even a sophisticated state-of-the-art prefetcher can only predict half of the off-chip load requests on average across a wide range of workloads, and (2) due to the increasing size and complexity of on-chip caches, a large fraction of the latency of an off-chip load request is spent accessing the on-chip cache hierarchy to solely determine that it needs to go off-chip. The goal of this work is to accelerate off-chip load requests by removing the on-chip cache access latency from their critical path. To this end, we propose a new technique called Hermes, whose key idea is to: (1) accurately predict which load requests might go off-chip, and (2) speculatively fetch the data required by the predicted off-chip loads directly from the main memory, while also concurrently accessing the cache hierarchy for such loads. To enable Hermes, we develop a new lightweight, perceptron-based off-chip load prediction technique that learns to identify off-chip load requests using multiple program features (e.g., sequence of program counters, byte offset of a load request). For every load request generated by the processor, the predictor observes a set of program features to predict whether or not the load would go off-chip. If the load is predicted to go off-chip, Hermes issues a speculative load request directly to the main memory controller once the load’s physical address is generated. If the prediction is correct, the load eventually misses the cache hierarchy and waits for the ongoing speculative load request to finish, and thus Hermes completely hides the on-chip cache hierarchy access latency from the critical path of the correctly-predicted off-chip load. Our extensive evaluation using a wide range of workloads shows that Hermes provides consistent performance improvement on top of a state-of-the-art baseline system across a wide range of configurations with varying core count, main memory bandwidth, high-performance data prefetchers, and on-chip cache hierarchy access latencies, while incurring only modest storage overhead. The source code of Hermes is freely available at: https://github.com/CMU-SAFARI/Hermes.

Microcontroller units (MCUs) are often used in Internet of Things nodes that operate intermittently. Such nodes alternate active and inactive phases under strict energy constraints. Typically, the memory system has a significant impact on overall MCU energy consumption. Memory accesses and memory leakage power often dominate the consumption of active and inactive phases, respectively. Emerging Non-Volatile Memory (NVM) technologies have recently enabled the design of non-volatile MCUs that can significantly reduce energy consumption during inactive phases. However, replacing all memories with emerging NVMs is not necessarily the best solution, as it often results in dynamic power overhead during active phases. Instead, a hybrid memory architecture that combines volatile and non-volatile technologies is a promising alternative. However, designing hybrid memory MCUs is challenging because the technology that best fits a data segment depends on its access pattern during execution (e.g., program memory experiences mostly reads while the stack alternates reads and writes). For a given intermittent application, our goal is to find the best memory architecture based on a data mapping that takes advantage of the different properties of the available memory technologies. To this end, we present MemCork, a tool for hybrid memory architecture exploration in intermittent computing devices. Based on an instrumented execution on a technology-agnostic FPGA prototype, our tool exhaustively explores the possible data mapping and memory architecture combinations to find the most energy-efficient solution. We evaluate MemCork on two representative intermittent applications and find a customised memory architecture and data mapping that reduces energy consumption by up to 23% compared to a fully NVM solution.

Computer system simulators are major tools used by architecture researchers. Two key elements play a role in the credibility of simulator results: (1) the simulator's accuracy, and (2) the quality of the baseline architecture. Some simulators, such as gem5, already provide highly accurate parameterized models. However, finding the right values for all these parameters to faithfully model a real architecture is still a problem. In this paper, we calibrate the memory hierarchy of an in-order core gem5 simulation to accurately model a real mobile Arm SoC. We execute small programs, which we design to stress specific parts of the memory system, to deduce key parameter values for the model. We compare the execution of SPEC CPU2006 benchmarks on the real hardware with the gem5 simulation. Our results show that our calibration reduces the average and worst-case IPC error by 36 % and 50%, respectively, when compared with a gem5 simulation configured with the default parameters.

The design and implementation of Convolutional Neural Networks (CNNs) for deep learning (DL) is currently receiving a lot of attention from both industrials and academics. However, the computational workload involved with CNNs is often out of reach for low power embedded devices and is still very costly when running on datacenters. By relaxing the need for fully precise operations, approximate computing substantially improves performance and energy efficiency. Deep learning is very relevant in this context, since playing with the accuracy to reach adequate computations will significantly enhance performance, while keeping quality of results in a user-constrained range. AdequateDL is a project aiming to explore how approximations can improve performance and energy efficiency of hardware accelerators in DL applications. This paper presents the main concepts and techniques related to approximation of CNNs and preliminary results obtained in the AdequateDL framework.

Transient attacks manipulate speculative execution to alter the control flow path in an application program and modify microarchitectural state. These state changes are not captured by the existing Instruction Set Architectures (ISAs). In this paper, we propose a novel OS-level detection-based mitigation mechanism, called Transit-Guard, that uses machine learning and real-time behavioral data of concurrent processes to detect and subsequently mitigate these attacks at run-time.

Modern computer memories have shown to have reliability issues. The main memory is the target of a security threat called Rowhammer, which causes bit flips in adjacent victim cells of aggressor rows. Numerous countermeasures have been proposed, some of the most efficient ones relying on memory controller modifications, which make them non-integrable in existing systems. These solutions have to be effective against attacks on current and future architectures and technology nodes. In order to prove the efficiency of such mitigation techniques, we have to use simulation platforms. Unfortunately, existing architecture simulators do not provide any implementation of unintended memory modifications like bit-flips. Integrating memory corruption into architecture simulators would allow the construction of attacks and mitigations for current and future computers, using feedback from the simulator. In this paper, we propose an implementation of the Rowhammer effect in the gem5 architecture simulator, demonstrate its capabilities and state its limitations.

Recent advances in machine learning have made it possible to consider the implementation of smart applications in constrained systems at the edge of the network. These memory and Central Processing Unit (CPU) intensive applications may require specific exploration methodologies to design efficient node computing devices. To better guide and validate these explorations, we need to perform energy and performance evaluations of the system. Software-based evaluation tools are application-oriented and do not consider real-time and hardware constraints. Alternatively, hardware prototyping allows an accurate and real-time evaluation but offers limited flexibility and does not allow agile design exploration of the microcontroller unit (MCU). In this work, we propose a Field Programmable Gate Arrays (FPGA) based edge computing node emulation platform. Our solution combines the flexibility and the real-time capability of programmable logic with hardware prototype evaluation. We present an open-source microcontroller architecture for design exploration which integrates an activity monitor to collect traces at run-time. These activity traces are then used to profile the energy consumption of different components in the edge computing node. Importantly, our FPGA is connected to real sensors and communication modules to enable interactions with the environment during the node evaluation and exploration.

Deep neural networks demonstrate impressive levels of performance, particularly in computer vision and speech recognition. However, the computational workload and associated storage inhibit their potential in resource-limited embedded systems. The approximate computing paradigm has been widely explored in the literature. It improves performance and energy-efficiency by relaxing the need for fully accurate operations. There are a large number of implementation options with very different approximation strategies (such as pruning, quantization, low-rank factorization, knowledge distillation, etc.). To the best of our knowledge, no automated approach exists to explore, select and generate the best approximate versions of a given convolutional neural network (CNN) according to the design objectives. The goal of this work in progress is to demonstrate that the design space exploration phase can enable significant network compression without noticeable accuracy loss. We demonstrate this via an example based on weight sharing and show that our method can obtain a 4x compression rate in an int-16 version of LeNet-5 (5-layer 1,720-kbit CNNs) without re-training and without any accuracy loss.

The following topics are dealt with: embedded systems; logic design; CMOS integrated circuits; neural nets; integrated circuit design; field programmable gate arrays; low-power electronics; formal verification; multiprocessing systems; Internet of Things.

Current main memory organizations in embedded and mobile application systems are DRAM dominated. The ever-increasing gap between today's processor and memory speeds makes the DRAM subsystem design a major aspect of computer system design. However, the limitations to DRAM scaling and other challenges like refresh provide undesired trade-offs between performance, energy and area to be made by architecture designers. Several emerging NVM options are being explored to at least partly remedy this but today it is very hard to assess the viability of these proposals because the simulations are not fully based on realistic assumptions on the NVM memory technologies and on the system architecture level. In this paper, we propose to use realistic, calibrated STT-MRAM models and a well calibrated cross-layer simulation and exploration framework, named SEAT, to better consider technologies aspects and architecture constraints. We will focus on general purpose/mobile SoC multi-core architectures. We will highlight results for a number of relevant benchmarks, representatives of numerous applications based on actual system architecture. The most energy efficient STT-MRAM based main memory proposal provides an average energy consumption reduction of 27% at the cost of 2x the area and the least energy efficient STT-MRAM based main memory proposal provides an average energy consumption reduction of 8% at the around the same area or lesser when compared to DRAM.

In theory, tools like VTR---a retargetable toolchain mapping circuits onto easily-described hypothetical FPGA architectures---could play a key role in the development of wildly innovative FPGA architectures. In practice, however, the experiments that one can conduct with these tools are severely limited by the ability of FPGA architects to produce reliable delay and area models---these depend on transistor-level design techniques which require a different set of skills. In this paper, we introduce a novel approach, which we call Fpresso, to model the delay and area of a wide range of largely different FPGA architectures quickly and with reasonable accuracy. We take inspiration from the way a standard-cell flow performs large scale transistor-size optimization and apply the same concepts to FPGAs, only at a coarser granularity. Skilled users prepare for \fpresso locally optimized libraries of basic components with a variety of driving strengths. Then, ordinary users specify arbitrary FPGA architectures as interconnects of basic components. This is globally optimized within minutes through an ordinary logic synthesis tool which chooses the most fitting version of each cell and adds buffers wherever appropriate. The resulting delay and area characteristics can be automatically used for VTR. Our results show that \fpresso provides models that are on average within some 10-20\% of those by a state-of-the-art FPGA optimization tool and is orders of magnitude faster. Although the modelling error may appear relatively high,we show that it seldom results in misranking a set of architectures, thus indicating a reasonable modeling faithfulness.

Computing on field-programmable gate arrays (FPGAs) has been receiving continued interest as it provides high performance at relatively low power budgets, while avoiding the high non-recurring engineering (NRE) costs associated with ASIC designs. However, FPGA development is typically performed using register transfer level (RTL) languages which make the design process protracted and error-prone when compared to software design flows. To ease these problems, high-level synthesis (HLS) tools have been introduced which abstract away the RTL architecture description from the designer. In this work we explore the design space of a nonbinary GF (q) low-density parity-check (LDPC) decoder using Vivado HLS and compare it with state-of-the-art RTL designs.

HLS tools have been introduced with the promise of easening and shortening the design cycle of tedious and error-prone RTL-based development of hardware accelerators. However, they do so either by concealing meaningful hardware decisions which model the computing architecture-such as OpenCL compilers-or by abstracting them away into a high-level programming language-usually C-based. In this paper, we show that although Vivado HLS is sufficiently mature to generate a functionally correct FPGA accelerator from a naive description, reaching an accelerator which optimizes the FPGA resource utilization in a way that conveys maximum performance is a process for a hardware architect mindset. We use a highly demanding application, that requires real-time operation, and develop a non-binary LDPC decoder on a state-of-the-art Virtex 7 FPGA, using the Vivado HLS framework. Despite using the same programming syntax as a C-language software compiler, the underlying programming model is not the same, thus, the optimizations required in code refactoring are distinct. Moreover, directive-based optimizations that tweak the synthesized C description hardware must be used in order to attain efficient architectures. These processes are documented in this paper, to guide the reader on how an HLS-based accelerator can be designed, which in our case can come close to the performance achieved with dedicated hand-made RTL descriptions.

Field Programmable Gate Arrays (FPGAs) can be customized into application-specific architectures to achieve high performance and energy-efficiency. Unfortunately, they are yet to gain significant adoption by application developers due to their low-level programming model. Moreover, to obtain good performance in an FPGA design, one often needs to correctly parallelize computation and balance the computational throughput with the available data access bandwidth. To address the programming model problem, recent efforts have focused on composing applications out of parallel computational patterns, such as map, reduce, zipWith and foreach, and leveraging the properties of these patterns to generate highly parallel hardware modules capable of high performance. In this work, we focus on the problem of further improving the performance and show that we can utilize the knowledge of how data is consumed and produced by these computational patterns in conjunction with the information of the system architecture to automatically parallelize computations across multiple hardware modules. To achieve this, we automatically infer synchronization needs arising due to parallelization and generate a complete system that can obtain high performance for a given application. We evaluate our approach using seven applications from different domains and show that our automatically generated designs achieve performance improvements ranging from 1.8 to 9.4 times.

In the last decade, progress in logic synthesis has brought about new advantageous circuit representations. These representations, such as And-Inverter Graphs in the ubiquitous open-source synthesizer ABC, have inspired new designs of Field Programmable Gate Arrays (FPGAs), which, instead of using Look-Up Tables (LUTs), mimic the topology of the circuit representation in the basic logic cells. More recent examples are Majority-Inverter Graphs, another uniform representation which has triggered considerable interest in synthesis and which naturally suggests new logic cells. Yet, in this paper we observe how naïvely adapting technology mapping solutions for classic LUT-based FPGAs to these new architectures incurs severe shortcomings. The key issue is that LUTs are inherently input-constrained (the logic function they implement is irrelevant) and have generally a single output; on the other hand, logic cells made of uniform networks of some fundamental logic function (e.g., And-Invert) are constrained in terms of logic depth and multiple outputs are an integral feature. We introduce novel and effective solutions to address these differences; the result is a highly versatile mapper—thus enabling further research in these new architectures—with a significantly better performance than what is described in literature for one such architecture. Specifically, when we compare with the state of the art on one sample architecture, we obtain a significant decrease in area (on average 18% over several benchmarks) while also improving slightly the critical path (a reduction of 3%).

Carry chains facilitate the implementation of adders and improve the performance of arithmetic circuits in FPGAs. The last version of the commonly used open-source Verilog-to-Routing (VTR) CAD flow now enables modelling carry chains in FPGA architectures. However, one of the shortcomings of the existing flow lies in its inability to identify arithmetic operations when described as gate-level circuits. Moreover, the VTR flow squanders most of the LUTs preceding the chain logic. This paper focuses on these two problems and proposes preprocessing the circuit before technology mapping to allow for a more efficient use of carry chains. The first proposed method maps logic on the carry chains for circuits expressed using a gate-level description. On average, it identifies about 30% more meaningful full adders than the existing tool flow operating on the RTL descriptions. Area is thus improved by up to 15% with an average of 6% for almost no delay penalty. Secondly, we increase the use of the LUTs preceding the chain logic by a factor 2 on average. This reduces delay (up to 9%) and area (up to 2%), compared to the existing VTR flow. The new approach is independent of the specific carry-chain architecture and can be generically adapted to any FPGA with built-in hardened adders.

We introduce a compiler that automatically inserts software countermeasures to protect cryptographic algorithms against power-based side-channel attacks. The compiler first estimates which instruction instances leak the most information through side-channels. This information is obtained either by dynamic analysis, evaluating an information theoretic metric over the power traces acquired during the execution of the input program, or by static analysis. As information leakage implies a loss of security, the compiler then identifies (groups of) instruction instances to protect with a software countermeasure such as random precharging or Boolean masking. As software protection incurs significant overhead in terms of cryptosystem runtime and memory usage, the compiler protects the minimum number of instruction instances to achieve a desired level of security. The compiler is evaluated on two block ciphers, AES and Clefia; our experiments demonstrate that the compiler can automatically identify and protect the most important instruction instances. To date, these software countermeasures have been inserted manually by security experts, who are not necessarily the main cryptosystem developers. Our compiler offers significant productivity gains for cryptosystem developers who wish to protect their implementations from side-channel attacks.

Hybrid flash storages combine a small Single-Level Cell (SLC) partition with a large Multilevel Cell (MLC) partition. Compared to MLC-only solutions, the SLC partition exploits fast and short local write updates, while the MLC part brings large capacity. On the whole, hybrid storage achieves a tangible performance improvement for a moderate extra cost. Yet, device lifetime is an important aspect often overlooked: in a hybrid system, a large ratio of writes may be directed to the small SLC partition, thus generating a local stress that could exhaust the SLC lifetime significantly sooner than the MLC partition's. To address this issue, we propose Libra , which builds on flash storage made solely of MLC flash and uses the memory devices in SLC mode when appropriate; that is, we exploit the fact that writing a single bit per cell in an MLC provides characteristics close to those of an ordinary SLC. In our scheme, the cell bit-density of a block can be decided dynamically by the flash controller, and the physical location of the SLC partition can now be moved around the whole device, balancing wear across it. This article provides a thorough analysis and characterization of the SLC mode for MLCs and gives evidence that the inherent flexibility provided by Libra simplifies considerably the stress balance on the device. Overall, our technique improves lifetime by up to one order of magnitude at no cost when compared to any hybrid storage that relies on a static SLC-MLC partitioning.

The design cycle for complex special-purpose computing systems is extremely costly and time-consuming. It involves a multiparametric design space exploration for optimization, followed by design verification. Designers of special purpose VLSI implementations often need to explore parameters, such as optimal bitwidth and data representation, through time-consuming Monte Carlo simulations. A prominent example of this simulation-based exploration process is the design of decoders for error correcting systems, such as the Low-Density Parity-Check (LDPC) codes adopted by modern communication standards, which involves thousands of Monte Carlo runs for each design point. Currently, high-performance computing offers a wide set of acceleration options that range from multicore CPUs to Graphics Processing Units (GPUs) and Field Programmable Gate Arrays (FPGAs). The exploitation of diverse target architectures is typically associated with developing multiple code versions, often using distinct programming paradigms. In this context, we evaluate the concept of retargeting a single OpenCL program to multiple platforms, thereby significantly reducing design time. A single OpenCL-based parallel kernel is used without modifications or code tuning on multicore CPUs, GPUs, and FPGAs. We use SOpenCL (Silicon to OpenCL), a tool that automatically converts OpenCL kernels to RTL in order to introduce FPGAs as a potential platform to efficiently execute simulations coded in OpenCL. We use LDPC decoding simulations as a case study. Experimental results were obtained by testing a variety of regular and irregular LDPC codes that range from short/medium (e.g., 8,000 bit) to long length (e.g., 64,800 bit) DVB-S2 codes. We observe that, depending on the design parameters to be simulated, on the dimension and phase of the design, the GPU or FPGA may suit different purposes more conveniently, thus providing different acceleration factors over conventional multicore CPUs.

Despite the progress of higher-level languages and tools, Register Transfer Level (RTL) is still by far the dominant input format for high performance digital designs. Experienced designers can directly express their microarchitectural intuitions in RTL. Yet, RTL is terribly verbose, burdened with trivial details, and thus error prone. In this paper, we augment a modern RTL language (Chisel) with new semantic elements to express an imprecise specification: a sketch. We show how, in combination with a naïve, unoptimized, but functionally correct reference, a designer can utilize the language and supporting infrastructure to focus on the key design intuition and omit some of the necessary details. The resulting design is exactly or almost exactly as good as the one the designer could have achieved by spending the time to manually complete the sketch. We show that, even limiting ourselves to combinational circuits, realistic instances of meaningful design problems are solved quickly, saving considerable design and debugging effort.

Worst-case design is one of the keys to practical engineering: create solutions that can withstand the most adverse possible conditions. Yet, the ever-growing need for higher energy efficiency suggest a grim outlook for worst-case design in the future. In this paper, we propose opportunistic runtime approximations to enable a continuous adaptation of the processing precision (operator type and bitwidth) to the actual execution context without modifying the algorithm functionality. We show that by relaxing the processing precision whenever possible, a VLSI implementation of an advanced wireless receiver algorithm based on opportunistic run-time approximations can save about 40% of the energy consumed by an optimized static implementation. These energy savings are achieved at the expense of a slight increase in overall chip area.

And-Invert Cones (AICs) have been suggested as an alternative to the ubiquitous Look-Up Tables (LUTs) used in commercial FPGAs. The original article suggesting the new architecture made some untested assumptions on the circuitry needed to implement AIC architectures and did not develop completely the toolset necessary to assess comprehensively the idea. In this paper, we pick up the architecture that some of us proposed in the original AIC paper and try to implement it as thoroughly as we can afford. We build all components for the logic cluster at transistor level in a 40~nm technology as well as a LUT-based architecture inspired by Altera's Stratix~IV. We first determine that the characteristics of our LUT-based architecture are reasonably similar to those of the commercial counterpart. Then, we compare the AIC architecture to the baseline on a number of benchmarks, and we find a few difficulties that had been overlooked before. We thus explore other design possibilities around the original design point and show their detailed impact. Finally, we discuss how the very structure of current logic clusters seems not perfectly appropriate for getting the best out of AICs and conclude that, even though they are not confirmed as an immediate blessing today, AICs still offer rich research opportunities.

Field Programmable Gate Arrays (FPGAs) are very versatile devices, but their complicated programming model has stymied their widespread usage. While modern High-Level Synthesis (HLS) tools provide better programming models, the interface they offer is still too low-level. In order to produce good quality hardware designs with these tools, the users are forced to manually perform optimizations that demand detailed knowledge of both the application and the implementation platform. Additionally, many HLS tools only generate isolated hardware modules that the user still needs to integrate into a system design before generating the FPGA bitstream. These problems make HLS tools difficult to use for application developers who have little hardware design knowledge. To address these problems, we propose an automated methodology to generate FPGA bitstreams from high-level programs written in Domain-Specific Languages (DSLs). We leverage the domain-knowledge conveyed by the DSL and its domain-specific semantics to extract application parallelism, perform optimizations and also identify a suitable system-architecture for the implementation, thereby, relieving the user from most of the hardware-level details. We demonstrate the high productivity and high design quality this approach offers by automatically generating hardware systems from applications written in OptiML, a machine-learning DSL. To evaluate our methodology, we use four OptiML applications and show that we can easily generate different solutions which achieve different trade-offs between performance and area. More importantly, the results reveal that our generated hardware achieves much better performance compared to the one obtained from using the HLS tool without platform-specific optimizations.

Craig interpolation is a known method for expressing a target function f as a function of a given set of base functions G. The resulting interpolant represents the dependency function h, such that f = h(G). Generally, the set G contains enough base functions to enable the existence of multiple dependency functions whose quality mainly depends on which base functions were selected for reconstruction. The interpolation is not an optimisation problem and thus, often, it selects some random base functions and, particularly, omits others potentially required for an optimal implementation of the target function. Mainly, it is impossible to impose that the interpolant uses a specific base function. In this paper, we propose a method that forces a specific base function gias a primary input of a dependency function. Such a dependency function is built as a Shannon expansion of two constrained Craig interpolants for the assignments of the primary inputs for which gievaluates to 0 and 1, respectively. We also introduce a method that iteratively imposes a predefined set of base functions. In each iteration, we generate a new dependency function for use as the target function of the next iteration in order to force the use of a base function. We show that, unlike the standard Craig interpolation method, our carving method succeeds to impose the desired base functions with very high probability. It recomposes single-output logic circuits as their delay- or area-optimised implementations regardless of the input implementation. The proposed methods can be efficiently employed for rewriting circuits in some synthesis-based algorithms.

This paper introduces a generic and automated methodology to protect hardware designs from side-channel attacks in a manner that is fully compatible with commercial standard cell design flows. The paper describes a tool that artificially adds jitter to the clocks of the sequential elements of a cryptographic unit, which increases the non-determinism of signal timing, thereby making the physical device more difficult to attack. Timing constraints are then specified to commercial EDA tools, which restore the circuit functionality and efficiency while preserving the introduced randomness. The protection scheme is applied to an AES-128 hardware implementation that is synthesized using both ASIC and FPGA design flows.

On a Multi-Level Cell (MLC) flash memory, a flash block that is becoming unreliable to store multiple bits per cell can be “revived” by storing only a single bit per cell. While the revived-block capacity is halved, its lifetime is significantly extended without jeopardizing the stored data. We present Phoenix, a technique that benefits from this feature to extend a device lifetime, and we evaluate its potential through detailed trace simulation on realistic benchmarks. Phoenix shows systematic lifetime extensions ranging from 3% up to 17%, without extra memory requirements or performance loss.

Fixed-point format is essential to most efficient Digital Signal Processing (DSP) implementations. The conversion of an algorithm specification to fixed-point precision targets the minimization of the implementation cost while guaranteeing a minimal processing accuracy. However, measuring such processing accuracy can be extremely time consuming and lead to long design cycles. In this paper, we study reference approaches to measure fixed-point errors of Linear Time-Invariant (LTI) systems without feedback. Unsurprisingly, we find the existing analytical approach significantly faster than a straightforward simulation-based estimation. However, we also show that such analytical approach can incur high estimation errors for some particular bitwidth configurations. Accordingly, we propose a new hybrid approach, which is able to reduce by up to 4 times the error of the analytical estimation, while still being more than 10 times faster than the simulation-based estimation.

Despite their many advantages, FPGAs are still inefficient. This inefficiency is mainly due to programmable routing networks; however, FPGA logic blocks also have their share of contribution. From the performance perspective, fewer hops in the routing network translates to a shorter critical path; and that requires large logic blocks capable of covering big portions of circuits. Recent work has shown that And-Inverter Cones (AICs) can considerably reduce the number of logic block levels compared to Look-Up Tables (LUTs). The best performance is achieved when both AICs and LUTs are used, but the AIC implementation requires radical changes in the FPGAs architecture. In this paper, we use AICs as shadow logic for LUTs in LUT-clusters, which requires minimal architectural changes while exploiting the benefits of both AICs and LUTs. The basic idea is to reuse the input crossbar of LUT-clusters for the shadow AICs while combining both LUTs and AICs in the same cluster. We also propose changes in the AIC architecture to enhance mapping on AICs. Our experimental results indicate that the new cluster architecture can reduce the average circuit delay by 12% with respect to standard FPGA clusters. However, this performance gain comes at a price of 43% area overhead in terms of number of logic clusters. Our results show that for a modest 6% increase in area, FPGA manufacturers can move towards next-generation FPGA logic elements. This transition would provide faster design options without major architectural changes.

Despite their many advantages, FPGAs still come with significant overheads in area, delay, and power consumption due to an extreme programmability in both the routing and logic. From the performance perspective, large logic blocks, capable of covering big portions of circuits, lead to fewer hops in the routing network, and thus, to a shorter critical path. Recent work has shown that And-Inverter Cones (AICs) can considerably reduce the number of logic block levels compared to Look-Up Tables (LUTs), in a radically altered FPGAs architecture. In this paper, we use AICs as shadow logic for LUTs, which incurs minimal architectural changes with respect to current FPGAs, while exploiting the benefits of both AICs and LUTs. We also propose changes in the AIC architecture, for a more compact technology mapping. The new architecture reduces the average circuit delay by up to 35% with respect to standard FPGAs at the expense of a 3x increase in the number of the logic clusters. Other benchmarks show more moderate area overheads, e.g., 16% delay improvement for 20% area overhead.

Tools to design hardware at a high level of abstraction promise software-like productivity for hardware designs. Among them, tools like Spiral, HDL Coder, Optimus and MMAlpha target specific application domains and produce highly efficient implementations from high-level input specifications in a Domain Specific Language (DSL). But, developing similar domain-specific High-Level Synthesis (HLS) tools need enormous effort, which might offset their many advantages. In this paper, we propose a novel, cost-effective approach to develop domain-specific HLS tools. We develop the HLS tool by embedding its input DSL in Scala and using Lightweight Modular Staging (LMS), a compiler framework written in Scala, to perform optimizations at different abstraction levels. For example, to optimize computation on matrices, some optimizations are more effective when the program is represented at the level of matrices while others are better applied at the level of individual matrix elements. To illustrate the proposed approach, we create an HLS flow to automatically generate efficient hardware implementations of matrix expressions described in our own high-level specification language. Although a simple example, it shows how easy it is to reuse modules across different HLS flows and to integrate our flow with existing tools like LegUp, a C-to-RTL compiler, and FloPoCo, an arithmetic core generator. The results reveal that our approach can simultaneously achieve high productivity and design quality with a very reasonable tool development effort.

Historically, hardware acceleration technologies have either been application-specific, therefore lacking in flexibility, or fully programmable, thereby suffering from notable inefficiencies on an application-by-application basis. To address the growing need for domain-specific acceleration technologies, this paper describes a design methodology (i) to automatically generate a domain-specific coarse-grained array from a set of representative applications and (ii) to introduce limited forms of architectural generality to increase the likelihood that additional applications can be successfully mapped onto it. In particular, coarse-grained arrays generated using our approach are intended to be integrated into customizable processors that use application-specific instruction set extensions to accelerate performance and reduce energy; rather than implementing these extensions using application-specific integrated circuit (ASIC) logic, which lacks flexibility, they can be synthesized onto our reconfigurable array instead, allowing the processor to be used for a variety of applications in related domains. Results show that our array is around 2× slower and 15× larger than an ultimately efficient ASIC implementation, and thus far more efficient than fieldprogrammable gate arrays (FPGAs), which are known to be 3-4× slower and 20-40× larger. Additionally, we estimate that our array is usually around 2× larger and 2× slower than an accelerator synthesized using traditional datapath merging, which has, if any, very limited flexibility beyond the design set of DFGs.

Hybrid flash architectures combine static partitions in Single Level Cell (SLC) mode with partitions in Multi Level Cell (MLC) mode. Compared to MLC-only solutions, the former exploits fast and short random writes while the latter brings large capacity. On the whole, one achieves an overall tangible performance improvement for a moderate extra cost. Yet, device lifetime is an important aspect often overlooked. In this paper, we show how a dynamic SLC-MLC scheme provides significant lifetime improvement (up to 10 times) at no cost compared to any classic static SLC-MLC partitioning based on any state of the art Flash Translation Layer policy.

Hardware specialization is often the key to efficiency for programmable embedded systems, but comes at the expense of flexibility. This paper combines flexibility and efficiency in the design and synthesis of domain-specific datapaths. We merge all individual paths from the Data Flow Graphs (DFGs) of the target applications, leading to a minimal set of required resources; this set is organized into a column of physical operators and cloned, thus generating a domain-specific rectangular lattice. A bus-based FPGA-style interconnection network is then generated and dimensioned to meet the needs of the applications. Our results demonstrate that the lattice has good flexibility: DFGs that were not used as part of the datapath creation phase can be mapped onto it with high probability. Compared to an ASIC design of a single DFG, the speed of our domain-specific coarse-grained reconfigurable datapath is degraded by a factor up to 2×, compared to 3-4× for an FPGA; similarly, our lattice is up to 10× larger than an ASIC, compared to 20-40× for an FPGA. We estimate that our array is up to 6× larger than an ASIC accelerator, which is synthesized using datapath merging and has limited or null generality.

Hardware designers and engineers typically need to explore a multi-parametric design space in order to find the best configuration for their designs using simulations that can take weeks to months to complete. For example, designers of special purpose chips need to explore parameters such as the optimal bit width and data representation. This is the case for the development of complex algorithms such as Low-Density Parity-Check (LDPC) decoders used in modern communication systems. Currently, high-performance computing offers a wide set of acceleration options, that range from multicore CPUs to graphics processing units (GPUs) and FPGAs. Depending on the simulation requirements, the ideal architecture to use can vary. In this paper we propose a new design flow based on Open CL, a unified multiplatform programming model, which accelerates LDPC decoding simulations, thereby significantly reducing architectural exploration and design time. Open CL-based parallel kernels are used without modifications or code tuning on multicore CPUs, GPUs and FPGAs. We use SOpen CL (Silicon to Open CL), a tool that automatically converts Open CL kernels to RTL for mapping the simulations into FPGAs. To the best of our knowledge, this is the first time that a single, unmodified Open CL code is used to target those three different platforms. We show that, depending on the design parameters to be explored in the simulation, on the dimension and phase of the design, the GPU or the FPGA may suit different purposes more conveniently, providing different acceleration factors. For example, although simulations can typically execute more than 3× faster on FPGAs than on GPUs, the overhead of circuit synthesis often outweighs the benefits of FPGA-accelerated execution.

Look-Up Tables (LUTs) are universally used in FPGAs as the elementary logic blocks. They can implement any logic function and thus covering a circuit is a relatively straightforward problem. Naturally, flexibility comes at a price, and increasing the number of LUT inputs to cover larger parts of a circuit has an exponential cost in the LUT complexity. Hence, rarely LUTs with more than 4-6 inputs have been used. In this paper we argue that other elementary logic blocks can provide a better compromise between hardware complexity, flexibility, delay, and input and output counts. Inspired by recent trends in synthesis and verification, we explore blocks based on And-Inverter Graphs (AIGs): they have a complexity which is only linear in the number of inputs, they sport the potential for multiple independent outputs, and the delay is only logarithmic in the number of inputs. Of course, these new blocks are extremely less flexible than LUTs; yet, we show (i) that effective mapping algorithms exist, (ii) that, due to their simplicity, poor utilization is less of an issue than with LUTs, and (iii) that a few LUTs can still be used in extreme unfortunate cases. We show first results indicating that this new logic block combined to some LUTs in hybrid FPGAs can reduce delay up to 22-32% and area by some 16% on average. Yet, we explored only a few design points and we think that these results could still be improved by a more systematic exploration.

Advanced handheld applications are demanding for implementations of higher energy efficiency and higher performance. In typical implementations, the finite precision information is only known after fixed-point refinement, once the data-flow has been frozen. Instead, in this paper we suggest the propagation of finite precision information to drive data-flow transformations in order to achieve a higher mapping efficiency. Then, provided a flexible architecture with low run-time switching overhead, the data-flow under execution can opportunistically be tuned to provide the instantaneous computational accuracy required by the application. Thereby, the average number of operations and the precision of those is minimized. This principle is demonstrated with the implementation of the 128-point FFT present in a WLAN receiver. Compared to a conventional implementation, a reduction of 49% to 65% of the number of cycles can be achieved depending on conditions external to the receiver.

Fixed-point refinement of signal processing systems is an essential step performed before implementation of any signal processing system. Existing analytical techniques to evaluate performance of fixed-point systems are not applicable to the errors due to quantization in the presence of un-smooth operators. Thus, it is inevitable to use simulation to evaluate performance of fixed-point systems in the presence un-smooth operators. This paper proposes a hybrid technique which can be used in place of pure simulation to accelerate the performance evaluation. The principle idea in the proposed hybrid approach is to selectively simulate parts of the system only when un-smooth errors occur but use analytical results otherwise. The acceleration thus obtained reduces the performance evaluation time which can be used to explore a wider word-length design space or speedup the optimization process. This method has been tried on a complex MIMO sphere decoding algorithm and the results obtained show several orders of magnitude improvement in terms of evaluation time.

Emerging SDR baseband platforms are usually based on multiple DLP+ILP processors with massive parallelism. Although these platforms would theoretically enable advanced SDR signal processing, existing work implemented basic systems and simple algorithms. Importantly, MIMO is not fully supported in most implementations. Implemented MIMO but with a simple linear detector. Our work explores the feasibility for SDR implementations of soft-output ML MIMO detectors, which brings 6-12 dB SNR gains when compared to popular linear detectors. Although soft-output ML MIMO detectors are considered to be challenging even for ASICs, we combine architecture-friendly algorithms, application specific instructions, code transformations and ILP/DLP explorations to make SDR implementations feasible. In our work, a 2times4 ADRES based ASIP with 16-way SIMD can deliver 193 Mbps for 2times2 64 QAM, and 368 Mbps for 2times2 16 QAM transmissions. To the best of our knowledge, this is the first work exploring SDR based soft-output ML MIMO detectors.

Complex signal processing algorithms are often specified in floating point precision. Thus, a type conversion is needed when the targeted platform requires fixed-point precision. In this work we proposed a new method to evaluate the final impact of finite precision processing in wireless applications. The latter combines analytical analysis with simulations. This extends previous work including the effect of the decision-making errors resulting from quantization. Thereby efficient dimensioning of the minimum bit-widths that satisfy a given accuracy constraint can be deployed. The method is validated with two representative case studies, namely an OFDM inner receiver and a Near-ML MIMO (Multiple Inputs, Multiple Outputs) detector.

Wireless communication standards are continuously evolving and getting more diverse.This requires a wide variety of baseband implementations within a short time-to-market. Besides, deep sub-micron technology significantly increases the design complexity and associated cost. These yield a growing need for reconfigurable/programmable baseband solutions. Implementing the whole base band functionality on programmable architectures, as foreseen in the tier-2 SDR, will become a must. However, the energy efficiency of SDR baseband platforms is unavoidably worse than the ASIC counterparts. This brings a challenging gap to bridge, which is even broadening further in emerging high rate standards. With a holistic view, we advocate a system level algorithmic approach to bridge this gap. Specifically, we propose to leverage the advantages (programmability) of SDR platforms to compensate for its disadvantages (energy efficiency). Highly flexible baseband algorithms are designed to exploit the abundant dynamics in the environment and the user requirements.In this way, the baseband can utilize the dynamics and substantially reduce the average energy consumption. In this paper, we present a design methodology and principles, illustrated with 3 representative case studies in HSDPA, WiMAX, and 3GPP LTE.

Nowadays, mobile devices are integrating an increasing variety of wireless communication standards, and each standard demands a multitude of modes. This tremendous diversity, combined with the increasing development-cost of deep-submicron silicon, desires highly flexible baseband implementations. The tier-2 SDR (Software Defined Radio) paradigm, where the entire baseband runs on programmable architectures, is very attractive to obtain the desired flexibility. Parallel ISP (Instruction Set Processor) based SDR baseband platforms have attracted extensive interest in recent years. However, such implementations typically come with a much lower energy-efficiency than traditional implementations as ASICs (Application Specific Integrated Circuits). This energy efficiency gap remains to be bridged in order to make SDR more pervasive. Importantly, the gap is becoming even more and more challenging in emerging high rate communication standards, such as 3GPP LTE, Mobile WiMAX and 802.11n. This situation demands disruptive innovations.

The software-defined radio (SDR) concept aims to enabling cost-effective multi-mode baseband solutions for wireless terminals. However, the growing complexity of new communication standards applying, e.g., multi-antenna transmission techniques, together with the reduced energy budget, is challenging SDR architectures. Coarse-grained array (CGA) processors are strong candidates to undertake both high performance and low power. The design of a candidate hybrid CGA-SEVID processor for an SDR baseband platform is presented. The processor, designed in TSMC 90 G process according to a dual-VT standard-cells flow, achieves a clock frequency of 400 MHz in worst case conditions and consumes maximally 310 mW active and 25 mW leakage power (typical conditions) when delivering up to 25,6 GOPS (16-bit). The mapping of a 20 MHz 2times2 MIMO-OFDM transmit and receive baseband functionality is detailed as an application case study, achieving 100 Mbps+ throughput with an average consumption of 220 mW.

ML and near-ML MIMO detectors have attracted a lot of interest in recent years. However, almost all the reported implementations are delivered in ASICs or FPGAs. Our contribution is optimizing the near-ML MIMO detector for parallel programmable architectures, such as those with ILP and DLP features. In the proposed SSFE (selective spanning with fast enumeration), architecture-friendliness is explicitly introduced from the very beginning of the design flow. Importantly, high level algorithmic transformations make the dataflow pattern and structure fit architecture-characteristics very well. We enable abundant vector-parallelism with highly regular and deterministic dataflow in the SSFE; memory rearrangements, shuffling and non-predictable dynamism are all elaborately excluded. Hence, the SSFE can be easily parallelized and efficiently mapped onto ILP and DLP architectures. Furthermore, to fine-tune the SSFE on parallel architectures, extensive pre-compiler transformations are applied with the help of the application-level information. These optimize not only computation-operations but also address-generations and memory-accesses. Experiments show that the SSFE brings very efficient resource-utilizations on real-life VLIW architectures. Specifically, with the SSFE the percentage of NOPs instructions on VLIW is below 1%, even better than that achieved by the software-pipelined FFT. To the best of our knowledge, this is the first reported work about comprehensive optimizations of near-ML MIMO detectors for parallel programmable architectures.

The PFFT (Partial FFT) is an extended FFT where only part of input or output bins are used. By pruning the useless dataflow, the PFFT can potentially achieve a significant speedup in many important applications. Although theoretical aspects of the PFFT have been thoroughly studied in past three decades, efficient implementations were rarely reported. The most important obstacle is the highly irregular dataflow and the associated control flow. In addition, a size-N PFFT has 2Ndataflow possibilities, so that delivering both flexibility and efficiency in the same implementation is very challenging. This paper presents a generic scheme to map the highly irregular dataflow of arbitrary PFFT onto ILP architectures with highly efficient SWP (Software-Pipelining). Constraints and opportunities of algorithms and architecture are carefully analyzed and exploited. We introduce a multi-phase partitioning, bringing heterogeneous control structures and heterogeneous software pipelining schemes to minimize control overheads and to maximize the efficiency of SWP. The proposal has been tested with 10 representative benchmarks extracted from baseband applications. In experiments cycle-counts, instructions, NOPs, LID/LIP access/miss/hit are thoroughly analyzed. Comparing to full FFTs with efficient SWP, our work reduces 20.5% - 87.5% cycle-counts, 11.2% - 86.5% instructions, 16.1% - 79.4% LID cache accesses and 19.5% - 87.1% LIP cache accesses. To the best of our knowledge, this is the first reported work about the generic software-pipelined PFFT on ILP architectures.

User demand, standards and products for digital nomadic communications are evolving quickly. The combination of this changing environment together with the need for short time-to-market pushes for more flexible implementations. Software Defined Radios (SDR) have been introduced as the ultimate way to achieve such flexibility. The reduced energy budget required by battery-powered solutions makes the typical worst-case static dimensioning unaffordable under highly dynamic operating conditions. Instead, more energy-scalable algorithms and implementations are entailed to provide flexibility while maintaining the required energy efficiency. Particularly, energy-scalable implementations can exploit data format properties to offer different tradeoffs between accuracy and energy. In this paper, such a technique is developed and applied to the SDR implementation of a 2 antennas 200 Mbps+ OFDM (Orthogonal Frequency-Division Multiplexing) inner modem receiver on a C-programmable CGA (Coarse Grain Array) processor with extensive SIMD (Single Instruction Multiple Data) support. By defining separate implementations for different combinations of modulation scheme and coding rate, up to 3-fold gains can be achieved in the average energy consumption.

In this paper, we will present a near-ML (maximum likelihood) MIMO (multiple input multiple output) detector explicitly optimized for parallel programmable baseband architectures, such as DSPs (digital signal processors) with VLIW (very long instruction word), SIMD (single instruction multiple data) or vector processing features. First, we propose the SSFE (selective spanning with fast enumeration) algorithm as an architecture friendly near-ML MIMO detector. The SSFE has a distributed and greedy algorithmic structure that brings a completely deterministic and regular dataflow. This enables efficient parallelization on programmable architectures. More importantly, in order to exploit the abundant flexibility enabled by programmable architectures, we propose an efficient online algorithm to adaptively adjust the search range of the SSFE according to the numerical properties of MIMO channel matrixes. Such adaptiveness brings significant throughput improvements at negligible performance degradations. Specifically, on VLIW DSP TI TMS320C6416, such a dynamic adaptation brings 2.62 times to 28.6 times improvements (comparing to the static SSFE) for 1/2 turbo-coded 4 times 4 64 QAM transmissions over 3GPP suburban macro channels, delivering 80 - 103 Mbps average throughput.

The diversity and evolution of wireless communication standards are fast-pacing. This requires a wide-variety of baseband implementations within short time-to-market. Besides, always deeper submicron technology significantly increase design cost. This yields an increasing need for using reconfigurable or programmable solutions for an always larger part of wireless modems. Mapping the whole baseband functionality on a programmable architecture, as foreseen in tier-2 SDR, will become a must in future implementation. In handhelds where the multi-mode trend adds extra needs for programmability, the energy efficiency of SDR baseband is however a major concern. New processor architectures with major improvements on energy efficiency (GOPS/mW) are emerging but are still not sufficient to catch the continuously increasing complexity of wireless physical layers within the shrinking energy budget. To enable SDR in size, weight and power constrained devices, innovation is also needed at the software side. Specifically, a thorough architecture-aware algorithm implementation methodology is needed for the baseband signal processing functions, which account for most of the SDR computational complexity. We present the premise of such a methodology and illustrate its effectiveness on the design of key kernels from present and future wireless baseband systems.

ML and near-ML MIMO detectors have attracted a lot of interest in recent years. However, almost all of the reported implementations are delivered in ASIC or FPGA. Our contribution is to co-optimize the near-ML MIMO detector algorithm and implementation for parallel programmable base-band architectures, such as DSPs with VLIW, SIMD or vector processing features. Although for hardware the architecture can be tuned to fit algorithms, for programmable platforms the algorithm must be elaborately designed to fit the given architecture, so that efficient resource-utilizations can be achieved. By thoroughly analyzing and exploiting the interaction between algorithms and architectures, we propose the SSFE (selective spanning with fast enumeration) as an architecture-friendly near-ML MIMO detector. The SSFE has a distributed and greedy algorithmic structure that brings a completely deterministic and regular dataflow. The SSFE has been evaluated for coded OFDM transmissions over 802.11n channels and 3GPP channels. Under the same performance constraints, the complexity of the SSFE is significantly lower than the K-Best, the most popular detector implemented in hardware. More importantly, SSFE can be easily parallelized and efficiently mapped on programmable baseband architectures. With TI TMS320C6416, the SSFE delivers 37.4 - 125.3 Mbps throughput for 4x4 64 QAM transmissions. To the best of our knowledge, this is the first reported near-ML MIMO detector explicitly designed for parallel programmable architectures and demonstrated on a real-life platform.