Energy-Efficient Implementation of Communication Algorithms Through Complexity Reduction

Abstract

Energy-efficient implementations are essential for the future and modern society, especially in digital signal processing (DSP) and communication systems, where the rapid growth of devices, such as those battery-driven internet of things (IoT) sensors, necessitates low-complexity and low-power solutions. This thesis concentrates on two areas: constant multiplication and active user detection in wire-less networks.

Constant multiplication can be implemented using a shift-and-add (SHA) network. Typically, the number of adders/subtracters is minimized, but the number of cascaded adders/subtracters (depth) also impacts the power consumption. The two classes of algorithms used to solve the problem are adder graph algorithms or sub-expression sharing algorithms. Adder graph algorithms typically yield better results for a single or a low number of inputs, since they do not depend on the representation of the numbers involved. However, they can lead to very high run times and worse results when the number of inputs is high. At the same time, it is known that it is possible to transpose the problem. For example, a sum of products (many inputs) can be transposed to a single input with multiple coefficients, meaning that it is possible to transpose the problem to the more advantageous form, solve it and then transpose the solution back. However, there has been no systematic algorithm available to obtain the transposed result that takes depth into account. In this thesis, a systematic algorithm that obtains the minimum depth of the transposed SHA network subject to the input is introduced.

The practical application of the constant multiplication problem is demonstrated through the implementation of a reconfigurable lowpass equalizer, widely used in communication systems and DSP. Various formulations of the constant multiplication problem, combined with pipelining, are explored to identify the most efficient implementation in a 28 nm FD-SOI standard cell, significantly reducing power consumption and highlighting the real-world impact of our research.

The second research focuses on the challenge of detecting active users in massive machine-type communication (mMTC) scenarios involving large numbers of devices. The problem is addressed using a pilot-hopping sequence method and is formulated as a non-negative least-squares (NNLS) problem. This work implements two NNLS algorithms, fast projected gradient (Fast) and multiplicative updates (Mult), to solve the active user detection problem. These implementations are implemented in a 28 nm FD-SOI process and are optimized for energy efficiency, chip area, and detection speed. The results demonstrate the ability to perform over a million detections per second with significantly lower energy consumption compared to existing methods. However, the implementations lack reconfigurability, and it can be argued whether the high detection rates are relevant for current practical applications.

To enhance practicality and reconfigurability, the Fast algorithm is implemented using a reconfigurable time-multiplexed architecture, reducing resources by reusing them within one iteration. This architecture employs a novel user re-ordering method to enable parallel memory access and continuous operation for successive iterations, thereby increasing the execution speed. The architecture is implemented on numerous FPGA families, demonstrating resource efficiency and reconfigurability by storing the pilot-hopping sequences in memory, while obtaining a more practically usable detection rate of about one to a few thousand detections per second depending on the FPGA family.

Alternate abstract:

Energieffektiva implementationer är avgörande för framtiden och det moderna samhället, särskilt inom digital signalbehandling (DSP) och kommunikationssystem, där den snabba tillväxten av enheter, såsom de inom Internet of Things (IoT), kräver lösningar med låg komplexitet och låg effektförbrukning. Denna avhandling fokuserar på två områden: konstantmultiplikation och detektering av aktiva användare i trådlösa nätverk.

Konstantmultiplikation kan implementeras med ett shift-and-add (SHA) nätverk. Vanligtvis så minimeras antalet adderare/subtraherare, men antalet kaskadkopplade adderare/subtraherare (djupet) påverkar också effektförbrukningen. De två klasserna av algoritmer för att lösa konstaktmultiplikation baseras på adderargrafer eller gemensamma deluttryck. Addergrafer är oftast bättre vid en eller få ingångar, eftersom de inte beror på vilken representation som talen uttrycks med. För många ingångar så kan beräkningstiden öka väldigt snabbt samt att resultaten ofta är sämre eftersom sökrymden ökar fort. Samtidigt så är det välkänt att det får att transponera problemet. Till exempel så kan en summa produkter (många ingångar) transponeras till en ingång som multipliceras med många olika konstanter. Detta leder till att det är möjligt att transponera problemet till den mest fördelaktiga formen, lösa det och sedan transponera lösningen. Det har tidigare inte funnits någon systematisk algoritm för att transponera ett nätverk som tar hänsyn till djupet, men i denna avhandling så presenteras en som garanterar minimalt djup givet en viss adderargraf som argument.

Den praktiska tillämpningen av konstantmultiplikation demonstreras genom implementering av en konfigurerbar lågpassutjämnare, som är allmänt använd i DSP- och kommunikationssystem. Olika formuleringar av konstantmultiplikationsproblemet, kombinerat med pipelining, utforskas för att identifiera den mest effektiva implementationen i en 28 nm FD-SOI-standardcell, vilket avsevärt minskar strömförbrukningen och visar den verkliga påverkan av vår forskning.

Den andra forskningen fokuserar på utmaningen att detektera aktiva användare i massive machinetype communication (mMTC) med ett stort antal enheter. Problemet hanteras med hjälp av en pilothoppingssekvensmetod och formuleras som ett problem med non-negative least-squares (NNLS). Detta arbete implementerar två NNLS-algoritmer, fast projected gradient (Fast) och multiplikativa uppdateringar (Mult), för att lösa problemet med detektering av aktiva användare. Dessa implementationer implementerade i en 28 nm FD-SOI-process och är optimerade för energieffektivitet, chiparea och detekteringshastighet. Resultaten visar att mer än en miljon detektioner per sekund kan utföras med betydligt lägre energiförbrukning än befintliga metoder, till stor del för att en iteration beräknas helt parallelt. Dock saknas möjlighet att ändra användarsekvenser och det kan diskuteras om den höga detektionstakten är praktiskt användbar.

För att öka praktiskheten implementeras Fast-algoritmen med en konfigurerbar tidsmultiplexad arkitektur, vilken sparar resurser genom att återanvända dem i en iteration. Denna arkitektur använder en ny metod att ordna om användarna för att möjliggöra parallell minnesåtkomst och kontinuerliga beräkning-ar för efterföljande iterationer, vilket ökar exekveringshastigheten. Arkitekturen implementeras på olika FPGA-familjer och visar resurseffektivitet och konfigurerbarhet genom att pilothoppningssekvenserna sparas i minne, samtidigt som en mer praktiskt användbar detektionshastighet från ungefär ett tusen till några tusen detektioner per sekund beroende på FPGA-familj.