Senior Hideo Ohno

Senior Member IEEE Mark D Stiles

Bernard Dieny

Spintronics

I. Introduction

This special issue covers recent developments in spintronics, where the spin degree of freedom of electrons is used to expand the capabilities of electronic devices. The articles that follow cover the progress over the last ten years. This progress has led to technologies ranging from some that are already commercially important, through promising ones currently in development, to very speculative possibilities. The most commercially important class of devices consists of magnetic sensors, which play an important role in a wide variety of applications, a particularly prominent example of which is magnetic recording. Non-volatile memories, in particular magnetic random access memories (MRAM) based on magnetic tunnel junctions, are commercial products and may develop into additional high impact applications either as stand-alone memories to replace other random access memories or embedded in CMOS logic. A number of technologies have appealing capabilities that may improve sensors and magnetic memories or develop into other devices. These technologies include three-terminal devices based on different aspects of spin transfer torques, spin-torque nano-oscillators, devices controlled by electric-fields rather than currents, and devices based on magnetic skyrmions. Even further in the future are spintronics based applications in energy harvesting, bio-inspired computing, and quantum technologies.

Spintronics utilizes the spin degree of freedom of electrons. The concept of using the spin-degree of freedom to control electrical current dates back to 1960s in an early study carried out in Leo Esaki's group at IBM showing that an antiferromagnetic barrier of EuSe sandwiched between metal electrodes exhibits a large magnetoresistance [START_REF] Esaki | Magnetointernal field emission in junctions of magnetic insulators[END_REF]. Subsequent advances of semiconductor thin film deposition techniques such as molecular beam epitaxy led to the development of semiconductor quantum structures, which prompted studies of magnetic multilayers [START_REF] Shinjo | Preparation and characterization of Fe/Mg superlattice films[END_REF]. Subsequent studies of magnetic multilayers resulted in the discovery of giant magnetoresistance (GMR) in 1988 [3]. This effect was used to make magnetic sensors, which boosted the areal density of hard disk drives and led to the 2007 Nobel Prize in Physics awarded to Albert Fert and Peter Grünberg [3].

The first Special Issue on Spintronics of the Proceedings of the IEEE was published in 2003 and covered developments prior to that year [START_REF]Special issue on spintronics[END_REF]. Since then rapid progress has continued to enhance both the role and the potential of spintronics. Applications now range from nano-scale spintronics sensors that further enhance the areal density of hard disk drives, through magnetic random access memories that are seriously being considered to replace static and dynamic random access memory (SRAM and DRAM), to devices utilizing spin current and the resulting torque to make oscillators and to transmit information without current. The spin-degree of freedom is also being used to convert heat to energy through the spin Seebeck effect, to manipulate quantum states in solids for information processing and communication, and to realize biologically inspired computing. These new developments in information storage, computing, communication, energy harvesting and highly sensitive sensors have prompted this special issue on Spintronics.

II. Overview of the Special Issue

This issue contains twelve papers and covers the fields that have made remarkable progresses since the 2003 issue was published. When reading this special issue, it is useful to consider how well the field was able to envision the future in that earlier issue. In 2003, the field was in the middle of rapid development in the science of semiconductorbased spintronics with great optimism about potential for applications. The earlier special issue devoted several articles to that topic. While the scientific progress continued, the promise of applications has not yet been realized, although semiconductorspintronic-based quantum computing is still being actively pursued. At the time, there was steady progress in metal-based spintronics and even then several applications, including sensors and magnetic random access memories, were in development. This development continues to this day and is represented by several articles in the present collection. The metrology and physics at low temperatures covered in the previous issue continue to be of great importance for further advancing the field, but the emphasis of the field and the present special issue has shifted more to the applied aspects of spintronics.

The first paper by Eric Fullerton and Jeff Childress describes modern digital data storage, particularly hard disk drives and the role played by two breeds of spintronics sensors that replaced conventional sensors utilizing anistotropic magnetoresistance (AMR); the first was based on GMR and the second on tunnel magnetoresistance (TMR). TMR is also currently being used as a building block of magnetoresistive random access memory covered by a subsequent paper in this issue. Spintronic sensors are part of the technology development that enabled the increase of storage density by several orders of magnitude reaching 10 TB per unit, laying the foundation of today's information age in the form of data centers installed by the cloud computing industry.

The second paper authored by Dmytro Apalkov, Bernard Dieny and Jon Slaughter deals with magnetoresistive random access memory (MRAM) and particularly spin-transfertorque MRAM, a nonvolatile memory with very high endurance and scalability. The current STT-MRAM technology uses an array of magnetic tunnel junctions (MTJs) with perpendicular easy-axis of magnetization. These MTJs utilize interface perpendicular anisotropy at the CoFeB-MgO interface, along with the large TMR of the system, for reading the state of magnetization. Spin-transfer-torque exerted by spin-polarized current is used to change the magnetization direction offering an efficient way of rewriting the memory. The CoFeB-MgO perpendicular-easy-axis MTJs present a high tunnel magnetoresistance ratio, high thermal stability, low-switching current, and high tolerance to annealing, all of which are critical for nonvolatile working memory applications of energy critical missions, such as in controllers for internet-of-things (IoT) applications, where reduction of standby power is of the highest priority. Thermally assisted MRAM is another MRAM technology in which the write step is assisted by the Joule heat produced by a pulse of current flowing through the magnetic tunnel junctions. The article also presents the technology's possible impacts on applications such as sensor networks/big data, smart phones, and high end computing.

The third paper by Seo-Won Lee and Kyung-Jin Lee describes emerging three-terminal spintronic memory devices. Three-terminal devices have an advantage over the standard two-terminal MTJs used in memory applications like MRAM in that separating the read and write functions potentially overcomes (1) the correlations between read, write, and breakdown voltages, (2) the correlation between the switching current and retention times, and (3) the rapid increase of critical switching currents for current pulses shorter than 10 ns. The article describes two writing schemes: one is based on spin currents generated by an electrical current running through a heavy metal adjacent to the free layer of the interface; this spin current then exerts a torque, called the spin-orbit torque, on the magnetization. In this scheme, the write current does not pass through the magnetic tunnel junction, separating the write and read functions. The other scheme uses current induced domain wall motion to move a domain wall in the free layer of the MTJ from one side of the fixed layer to the other. In this scheme, the current passes through the free layer, but not the tunnel barrier, again separating the read and write functions. On the other hand, three-terminal devices have a significant disadvantage compared to their twoterminal counterparts in that the area required for installing three-terminal devices is twice as large as for the corresponding two-terminal devices. The increase in area makes threeterminal devices unfavorable for high density applications. For applications in which the density is not the top priority, the separation of the read and write current paths in threeterminal MRAM devices is very attractive for high speed and reliable operation.

The fourth paper by Takahiro Hanyu et al. discusses how spintronic-based nonvolatile memories can be used in conjunction with complimentary-metal-oxide-semiconductor (CMOS)-based logic applications. Making embedded working memory nonvolatile is a crucial first step toward standby-power-free logic circuits that are much needed for internet-of-things applications. Conventional two-terminal MTJs have a characteristic of requiring high current densities for switching times below 10 ns. This requirement can be masked by smart circuit design involving the separation of the CMOS and MTJ write processes, resulting in fast and nonvolatile memory operation with reduced power consumption. This approach combined with a nonvolatile flip-flop provides the basis for the design and demonstration of a spintronics-based microprocessor unit where fine grained power gating is used to reduce the power consumption. Another application of embedded MRAM devices is an architecture called logic-in-memory where memories are embedded on the logic CMOS plane. This type of architecture, proposed in 1969 [START_REF] William | Cellular logic-in-memory arrays[END_REF], minimizes the interconnection delay between memory and logic because of the much reduced physical length between the two. However, the overhead of having memory and logic in close proximity has been prohibitively high until now. MRAM-based logicin-memory reduces this overhead allowing the design and demonstration of power efficient field programmable gate arrays (FPGA), ternary content addressable memory (TCAM) as well as other variants. These circuits have the advantage of both the minimized interconnection delay and the non-volatility of the memory.

The fifth article by Swaroop Ghosh deals with security issues in spintronic devices. These devices have shown great promise for logic and memory applications due to their energyefficiency, very high write endurance and non-volatility. Besides, these systems gather a number of entropy sources which can be advantageously used for hardware security. In particular, the spatial and temporal randomness in the magnetic system associated with complex micromagnetic configurations, non-linearity of magnetization dynamics, cell to cell process variations or thermally induced fluctuations of magnetization can be employed to realize novel hardware security primitives such as physical unclonable functions, encryption engines, and true random number generators. Due to their relative simplicity of integration, the spintronic circuits can complement the existing CMOS based security and trust infrastructures. However, spintronics circuits have also their specific vulnerabilities. New forms of attacks could be launched using low cost noninvasive techniques such as temperature rise or large magnetic field exposure with the intention to corrupt the data. Data privacy associated with the non-volatility of the spintronics elements is also an addressed issue. Security vulnerabilities, security and privacy attack models and possible countermeasures to enable safe computing environment using spintronics are thoroughly addressed and discussed in this review article.

The sixth article by Paulo P. Freitas et al. describes spintronic sensors starting from their fundamental physical principles: anisotropic magnetoresistance, giant magnetoresistance, and tunneling magnetoresistance. It then discusses typical device geometries, such planar-Hall structures and spin valves, sensitivities, intrinsic noise mechanisms, biasing and interconnection schemes. These magnetoresistive integrated thin film devices can be fabricated with high yields, in 200 mm diameter wafers, to detect fields ranging from a few tens of millitesla down to tens of picotesla, therefore spanning 8 to 9 orders of magnitude in field range. They are large bandwidth devices that can operate from DC to the gigahertz range, with an adjustable impedance (from 1Ω to 100 kΩ) and a magnetic sensitivity range (from 0.1 mT to 100 mT ) that can be matched to specific application requirements. These devices can be used with a variety of systems including integration with CMOS and incorporation on flexible substrates. Magnetic flux guides provide field gain to access the picotesla range for frequencies below 100 Hz. The spatial resolution scales with the sensor dimensions (down to tens of nanometers), for applications requiring a small footprint, good field sensitivity and good spatial resolution. In addition to the hard disk market (read heads are covered in the first article in this series), the range of applications spans from industrial applications to biosensor and biomedical applications. The paper describes sensor layout and full system integration including signal conditioning electronics (discrete or ASIC) for some of these applications.

The seventh article by Tingsu Chen et al. deals with spin torque nano-oscillators (STNOs) and spin Hall effect nano-oscillators (SHNOs) are two members of an emerging class of miniaturized and ultra-broadband microwave signal generators. Both types of devices are based on magnetic resonances in single or coupled magnetic thin films where spin transfer torque, either from a spin-polarized current, (STNOs), or a pure spin current, (SHNOs), is used to both excite the resonances and subsequently tune them. These devices are autooscillators and so do not require any active feedback circuitry with positive gain for their operation. The auto-oscillatory state has strong non-linearity causing phase-amplitude coupling, which governs a wide range of properties, including frequency tunability, phase noise, modulation, injection locking, and mutual synchronization. STNOs and SHNOs can in principal operate at any frequency supported by a magnetic mode, resulting in a potential frequency range of over six orders of magnitude, from below 100 MHz for magnetic vortex gyration modes to beyond 1 THz for exchange dominated modes. Since STNOs and SHNOs can also act as tunable detectors over this frequency range, there is significant potential for novel devices and applications. The primary hurdles to be overcome before such applications can become reality are the low output power and the large phase noise. Intense research is directed to achieve increasingly high output powers, primarily through the use of magnetic tunnel junctions, and higher coherence, through the mutual synchronization of either individual oscillators, or concurrent modes in the same oscillator.

The eighth article, by Ken-ichi Uchida et al. discusses one of the more recent developments in spintronics, spin caloritronics, and how it might be used to develop more efficient thermoelectrics. Much of the focus of research in spin caloritronics has been the longitudinal spin Seebeck effect, which refers to spin-current generation by temperature gradients across junctions between metallic layers and magnetic layers. The generated spin current in the metallic layer gets converted into a charge current by the inverse spin Hall effect, making a two-step conversion process from a thermal gradient perpendicular to the interface into a charge current in the plane of the interface. This process can be used for thermoelectric conversion. Device structures using the spin Seebeck effect differ significantly from those using conventional Seebeck effects due to the orthogonality of the thermal gradient and resulting charge current, giving different strategies for applications of the two effects. This paper reviews the physics background, typical experiments, mechanisms that determine the efficiency, and prospects for applications of spin Seebeck effects.

The ninth article, by Kang Wang et al. deals with electric-field control of the spin-orbit interaction. Electric-field control of the carrier concentration in diluted magnetic semiconductors, as in ordinary semiconductor field-effect transistors, leads to manipulation of magnetization through properties like the transition temperature and anisotropy. This control of magnetic properties through electric fields rather than currents suggests paths toward low energy magnetization reversal, which is needed for low-power electronics and spintronics. One specific way to accomplish this low energy switching is through electric-field control of spin-orbit interactions that lead to modification of the magnetic anisotropy. By applying a voltage to a device it is possible to change the anisotropy such that the magnetization rotates into a new direction. While such demonstrations of switching alone are not sufficient to make a viable device, voltagecontrolled reversal is a promising pathway towards low-energy nonvolatile memory devices. The article finally discusses new materials such as antiferromagnets and topological insulators for spintronics and their electric-field tunable properties.

The tenth article, by F. Joseph Heremans et al. goes over progress made in quantum technologies based on the quantum nature of spins in deep level defects found in diamond (nitrogen-vacancy center) and in silicon carbide (divacancy). The quantum nature of these spins manifests itself even at room temperature and can be used as extremely sensitive nanoscale temperature, magnetic-field and electric-field sensors. The authors then discuss the development of quantum networks and quantum transducers that lead to quantum technology, by fully utilizing microwave, photonic, electrical and mechanical control of these spins.

The eleventh article by Julie Grollier et al. discusses approaches to bio-inspired computing based on spintronic devices. The hope for bio-inspired computing is that it enables low power, high performance computing and the expectation is that spintronic devices could play an important role in this development. The article describes some of the features of bio-inspired computing and some of the properties of magnetic tunnel junctions that may be useful in implementing some of these features. Low power, high performance bio-inspired hardware relies on ultra-high density networks built out of complex processing units interlinked by tunable connections. The article describes several ways in which spin torque driven magnetic tunnel junctions, with their multiple, tunable functionalities and CMOS compatibility are very well adapted for this purpose.

A number of groups have recently proposed a variety of bio-inspired architectures including one or several types of spin torque nanodevices. This article discusses the different bio-inspired concepts that can be implemented in spintronics (spiking neural networks, associative memories and so on) and their application scope. It describes how they could be mapped in hardware by hybridizing spintronics on CMOS, and reviews the recent advances in this direction.

The last article, by Wang Kang et al., discusses the device prospects of one of the most recent topics to generate substantial excitement in spintronics -skyrmions. The concept of skyrmions derives from high energy physics. In magnetic systems, they are magnetic textures that can be viewed as topological objects. There are indications that they have properties that might make them useful objects in which to store and manipulate information. Many of the ideas are similar to ideas that were developed decades ago for bubble memory or, more recently, racetrack memory. There are several possible advantages for skyrmion devices as compared to other related devices. They are potentially higher density and lower energy, although the arguments for these remain to be experimentally verified. The authors describe ideas that have been developed for creating, transporting, and manipulating skyrmions. They then describe how the concepts can be combined to make logic devices.

III. The future of spintronics

How will these articles be viewed in another thirteen years? Will the role of spintronics in technology increase or decrease? We are optimistic that it will continue to having increasing impact but the future is uncertain. The importance of magnetic sensors is likely to remain important while the importance of the magnetic sensor in hard disk drives appears to depend on the economics of mass storage in the cloud. MRAM appears likely to play an increasing role both as standalone memory and embedded in CMOS. The degree of adoption still depends on a few technical and many economic considerations. In the past few months, we however witness an acceleration of announces and demonstrations related to STT-MRAM produced by major microelectronics companies which seem to indicate that large volume production of STT-MRAM is getting quite close. If the adoption of this technology by microelectronics industry becomes a reality, the whole field will be strongly boosted. Spintronics can play in the future a very important role in areas such as Internet of Things, ultralow-power electronics, high performance computing (HPC). Besides, in thirteen years, we are likely to see a much greater role played by alternative forms of computing. The role that spintronics plays in those technologies is likely to be strongly influenced by the success of MRAM. If MRAM is successful, we will have developed the ability to manufacture it making it easier to import into other technologies. Several of the articles in this special issues address recent technical developments that have significant virtues for applications. It is likely that some will play a role in technology thirteen years from now but many will not. Research on many of these ideas will continue and will spawn related areas. Material research is key along this road. Innovative materials allowing efficient charge to spin and spin to charge current conversion, or good control of magnetic properties by voltage, or efficient injection/manipulation/detection of spins in semiconductors can play major roles. Along this idea, the use of oxide materials in spintronic devices can become quite important. Oxides share crystallinity with semiconductors in distinction to metallic magnetic devices.

Will the greater control that comes with crystallinity give advantages to oxides in future devices? These are some of the many topics that are likely to be addressed in the next thirteen years.


Advancements in spintronics

Applications now include nanoscale Spintronics sensors that further enhance the areal density of hard disk drives, through MRAMs that are seriously being considered to replace embedded flash, static random access memories (SRAM) and at a later stage dynamic random access memories (DRAM).

By Hideo Ohno, Mark Stiles, and Bernard Dieny, IEEE

Spintronics is the concept of using the spin degree of freedom to control electrical current to expand the capabilities of electronic devices. Over the last 10 years' considerable progress has been made. This progress has led to technologies ranging from some that are already commercially valuable, through promising ones currently in development, to very speculative possibilities.

Today, the most commercially important class of devices consists of magnetic sensors, which play a major role in a wide variety of applications, a particularly prominent example of which is magnetic recording. Nonvolatile memories called magnetic random access memories (MRAMs) based on magnetic tunnel junctions (MTJs), are commercial products and may develop into additional high impact applications either as standalone memories to replace other random access memories or embedded in complementary metal-oxide-semiconductor (CMOS) logic. Some technologies have appealing capabilities that may improve sensors and magnetic memories or develop into other devices. These technologies include three-terminal devices based on different aspects of spin-transfer torques, spin-torque nano-oscillators, devices controlled by electric fields rather than currents, and devices based on magnetic skyrmions. Even further in the future are Spintronics-based applications in energy harvesting, bioinspired computing, and quantum technologies.

But before we get into detail about where Spintronics is today, we need to cover the history of Spintronics.

The history of spintronics

Spintronics dates to the 1960s and was discovered by a group at IBM headed by Leo Esaki, a Japanese physicist who would later go on to win a share of the Nobel Prize I 1973 for discovering the phenomenon of electronic tunneling. Esaki and his team conducted a study which showed an antiferromagnetic barrier of EuSe sandwiched between metal electrodes exhibits a large magnetoresistance.

Subsequent advances of semiconductor thin film deposition techniques such as molecular beam epitaxy led to the development of semiconductor quantum structures, which prompted studies of magnetic multilayers. Ensuing studies of magnetic multilayers resulted in the discovery of giant magne-toresistance (GMR) in 1988. This effect was used to make magnetic sensors, which boosted the areal density of information stored on hard disk drives and led to the 2007 Nobel Prize in Physics awarded to Albert Fert and Peter Grunberg.

Since then rapid progress has continued to enhance both the role and the potential of Spintronics. So, let's take a look at where we are now.

Where we are now

Applications now include nanoscale Spintronics sensors that further enhance the areal density of hard disk drives, through MRAMs that are seriously being considered to replace embedded flash, static random access memories (SRAM) and at a later stage dynamic random access memories (DRAM). Applica-tions also include devices that utilize spin current and the resulting torque to make oscillators and to transmit information without current. Now let's look at those applications and more in-depth.

Modern Hard Disk Drives: Two breeds of Spintronics sensors have replaced traditional anisotropic magnetoresistance (AMR) sensors. Those sensors include giant magnetoresistance (GMR) sensors (used in hard disk drives between 1998 and 2004) and tunnel magnetoresistance (TMR) sensors (used since 2004).

Those sensors are part of the technology development that enabled the increase of storage density of hard disk drives by several orders of magnitude, laying the foundation of today's information age in the form of data centers installed by the cloud computing industry.

Magnetoresistive Random Access Memory (MRAM):

MRAM and particularly spin-transfertorque MRAM (STT-MRAM) is a nonvolatile memory with very high endurance and scalability. The current STT-MRAM technology uses an array of MTJs with an easy axis of magnetization oriented out of the plane of the layers. These MTJs utilize interface perpendicular anisotropy at the CoFeB-MgO interface, along with the large TMR of the system, for reading the state of magnetization. The spin-transfer torque exerted by a spin polarized current is used to change the magneti-zation direction, offering an efficient way of rewriting the memory. FIGURE 1show the main families of MRAM that have evolved since 1995.

Three Terminal Magnetic Memory Devices:

Recent physics developments raise the prospect of three-terminal spintronic memory devices. These devices have an advantage over the standard two-terminal devices used in memory applications such as MRAM in that separating the read and write functions poten-tially overcomes several future roadblocks in the devel-opment of MRAM. There are two writing schemes: one is based on spin currents generated by an electrical current running through a heavy metal adjacent to the free layer of the MTJ. The current causes a spin current both in the bulk of the heavy metal and at the interface; this spin current then exerts a torque, called the spin-orbit torque, on the magnetization. In this scheme, the write current does not pass through the MTJ, separating the write and read functions. The other scheme uses current-induced domain wall motion to move a domain wall in the free layer of the MTJ from one side of the fixed layer to the other. In this scheme, the current passes through the free layer, but not the tunnel barrier, again separating the read and write functions.

Standby-Power-Free Integrated Circuits Using MTJ-Based VLSI Computing: Spintronic-based nonvolatile embedded working memory used in conjunction with CMOS-based logic applications is a crucial first step toward standby-power-free logic circuits that are much needed for Internet of Things (IoT) applications. MRAM based logic-in-memory reduces the overhead of having memory and logic apart and gives both minimized interconnection delay and nonvolatility.

Security: These devices have shown great promise for logic and memory applications due to their energy efficiency, very high write endurance, and nonvolatility. Besides, these systems gather many entropy sources which can be advantageously used for hardware security. The spatial and temporal randomness in the magnetic system associated with complex micromagnetic configurations, the nonlinearity of magnetization dynamics, cell-to-cell process variations, or thermally induced fluctuations of magnetization can be employed to realize novel hardware security primitives such as physical unclonable functions, encryption engines, and true random number generators.

Spin-Torque and Spin-Hall Nano-Oscillators: Spin-torque nano-oscillators (STNO) and spin-Hall effect nano-oscillators (SHNO) are in a class of miniaturized and ultra-broadband microwave signal generators that are based on magnetic resonances in single or coupled magnetic thin films. These oscil-lators are based on magnetic resonances in single or combined magnetic thin films where magnetic torques are used to both excite the resonances and subsequently tune them. The torques can be either spin-transfer torques due to spin-polarized currents (STNOs) or spin Hall torques due to pure spin currents (SHNOs). These devices are auto-oscillators and so do not require any active feedback circuitry with a positive gain for their operation. The autooscillatory state is strongly nonlinear, causing phase-amplitude coupling, which governs a wide range of properties, including frequency tunability, modulation, injection locking, mutual synchronization, but also causes significant phase noise. STNOs and SHNOs can, in principle, operate at any frequency supported by a magnetic mode, resulting in a potential frequency range of over six orders of magnitude, from below 100 MHz for magnetic vortex gyration modes to beyond 1 THz for exchange dominated modes. Since STNOs and SHNOs can also act as tunable detectors over this frequency range, there is significant potential for novel devices and applications.

Beyond the applications listed, the spin degree of freedom is also being used to convert heat to energy through the spin Seebeck effect, to manipulate quantum states in solids for information processing and communication, and to realize biologically inspired computing. These may lead to new develop-ments in information storage, computing, communication, energy harvesting, and highly sensitive sensors. Let's take a look at these new developments.

Thermoelectric Generation Based on Spin Seebeck Effects:

The study of combined heat and spin flow, called spin caloritronics, may be used to develop more efficient thermoelectric conversion. Much of the focus of research in spin caloritronics has been the longitudinal spin Seebeck effect, which refers to spin-current generation by temperature gradients across junctions between metallic layers and magnetic layers. The generated spin current in the metallic layer gets converted into a charge current by the inverse spin Hall effect, making a twostep conversion process from a thermal gradient perpen-dicular to the interface into a charge current in the plane of the interface. This process can be used for thermoelectric conversion. Device structures using the spin Seebeck effect differ significantly from those using conventional Seebeck effects due to the orthog-onality of the thermal gradient and resulting charge current, giving different strategies for applications of the two effects.

Electric-Field Control of Spin-Orbit Interaction for Low-Power Spintronics: Control of magnetic properties through electric fields rather than currents raises the possibility of low energy magnetization reversal, which is needed for low-power electronics and Spintronics. One specific way to accomplish this low energy switching is through electric-field control of electronic states leading to modification of the magnetic anisotropy. By applying a voltage to a device, it is possible to change the anisotropy such that the magnetization rotates into a new direction. While such demonstrations of switching alone are not sufficient to make a viable device, voltage controlled reversal is a promising pathway toward low-energy nonvolatile memory devices.

Control of Spin Defects in Wide-Bandgap Semiconductors for Quantum Technologies:

The spins in deep level defects found in diamond (nitrogen-vacancy center) and in silicon carbide (divacancy) have a quantum nature that manifests itself even at room temperature. These can be used as extremely sensitive nanoscale temperature, magnetic-field, and electric-field sensors. In the future, microwave, photonic, electrical, and mechanical control of these spins may lead to quantum networks and quantum transducers.

Spintronic Nanodevices for Bioinspired Computing: Bioinspired computing devices promises low-power, high-performance computing but will likely depend on devices beyond CMOS. Lowpower, high performance bioinspired hardware relies on ultrahigh-density networks built out of complex processing units interlinked by tunable connections (synapses). There are several ways in which spin-torque-driven MTJs, with their multiple, tunable functionalities and CMOS compatibility, are very well adapted for this purpose. Some groups have recently proposed a variety of bioin-spired architectures that include one or several types of spin-torque nanodevices.

Skyrmion-Electronics: An Overview and Outlook:

The concept of skyrmions derives from high energy physics. In magnetic systems, skyrmions are magnetic textures that can be viewed as topological objects. Theory suggests that they have properties that might make them useful objects in which to store and manip-ulate information. Many of the ideas are similar to ideas that were developed decades ago for bubble memory or, more recently, racetrack memory. There are several possible advantages for skyrmion devices as compared to other related devices. They are potentially higher density and lower energy, although the arguments for these remain to be experimentally verified.

So, what does the future of spintronics have in store?

The future Spintronics will continue to have increasing impact, but the future is somewhat uncertain. The importance of magnetic sensors is likely to remain important while the importance of the magnetic sensors in hard disk drives appears to depend on the economics of mass storage in the cloud.

MRAM seems likely to play an increasing role both as standalone memory and embedded in CMOS. The degree of adoption still depends on a few technical and many economic considerations. The acceleration, over the past few months, of announcements and demonstrations related to STT-MRAM produced by major microelectronics companies, seems to indicate that large volume production of STT-MRAM is getting quite close. If the adoption of this technology by microelectronics industry becomes a reality, the whole field will be strongly boosted.

In the future, Spintronics can play a critical role in areas such as IoT, ultralow-power electronics, high-performance computing (HPC). Besides, in the next 10 to 15 years, we are likely to see a much greater role played by alternative forms of computing. The role that Spintronics plays in those technologies is likely to be strongly influenced by the success of MRAM. If MRAM is successful, we will have developed the ability to manufacture it making it easier to import into other technologies. Some of the recent technical developments that have significant virtues for applications will likely play a role in technology 10 to 15 years from now but many will not. Research on many of these ideas will continue and will spawn related areas. Material research is key along this road.

Innovative materials allowing efficient charge to spin and spin to charge current conversion, or good control of magnetic properties by voltage, or efficient injection/manipulation/detection of spins in semicon-ductors can play major roles. Along with this idea, the use of oxide materials in spintronic devices can become quite important. Oxides share crystal-linity with semiconductors in distinction to metallic magnetic devices. Will the greater control that comes with crystallinity give advantages to oxides in future devices? These are some of the many topics that are likely to be addressed in the coming years.


Clément Dorffer

Cédric Herzet

Angélique Drémeau

REGION-BASED RELAXATIONS TO ACCELERATE GREEDY APPROACHES

Keywords: Sparse approximation, atom selection, low-complexity methods

We propose a low-computational strategy for the efficient implementation of the "atom selection step" in sparse representation algorithms. The proposed procedure is based on simple tests enabling to identify subsets of atoms which cannot be selected. Our procedure applies on both discrete or continuous dictionaries. Experiments performed on the standard "Gaussian deconvolution" problem show the computational gain induced by the proposed approach.

PROBLEM STATEMENT

We consider the problem of sparsely approximating a signal vector y ∈ H in some dictionary A, where H is a Hilbert space with inner product •, • and induced norm • . In the last decades, many works have addressed this problem in a "discrete" setting, where the dictionary A contains a finite number of elements. In the recent years, several contributions have focused on the more involved problem of sparse representations in a "continuous" dictionary [START_REF] De | Exact reconstruction using Beurling minimal extrapolation[END_REF][START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF][START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF][START_REF] Denoyelle | Support Recovery for Sparse Super-Resolution of Positive Measures[END_REF][START_REF] Tang | Compressed sensing off the grid[END_REF][START_REF] Bredies | Inverse problems in spaces of measures[END_REF][START_REF] Rao | Forwardbackward greedy algorithms for atomic norm regularization[END_REF][START_REF] Boyd | The alternating descent conditional gradient method for sparse inverse problems[END_REF][START_REF] Semper | Grid-free direction-of-arrival estimation with compressed sensing and arbitrary antenna arrays[END_REF]. In this setup, the dictionary A is typically defined as

A = {a(θ) : θ ∈ Θ} (1)
where a : Θ → H is some continuous function and Θ is some compact subset of R d . Sparse representations in continuous dictionaries may seem intractable from both a theoretical and practical point of view since A contains an infinite uncountable number of elements. Nevertheless, recent theoretical works showed that, under some mild conditions, sparse linear combinations of elements of A may be recovered as the solution of convex optimization problems over the space of Radon measures [START_REF] De | Exact reconstruction using Beurling minimal extrapolation[END_REF][START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF][START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF][START_REF] Denoyelle | Support Recovery for Sparse Super-Resolution of Positive Measures[END_REF]. From a practical point of view, several contributions have also proposed methodologies to access to the solution of these convex optimization problems, see [START_REF] Tang | Compressed sensing off the grid[END_REF][START_REF] Bredies | Inverse problems in spaces of measures[END_REF][START_REF] Rao | Forwardbackward greedy algorithms for atomic norm regularization[END_REF][START_REF] Boyd | The alternating descent conditional gradient method for sparse inverse problems[END_REF][START_REF] Semper | Grid-free direction-of-arrival estimation with compressed sensing and arbitrary antenna arrays[END_REF].

In this paper, we assume H is defined over the real field R and the elements of the sparse representation to be positive. 1We focus on the efficient implementation of a particular step of the procedures (see e.g., [START_REF] Bredies | Inverse problems in spaces of measures[END_REF][START_REF] Rao | Forwardbackward greedy algorithms for atomic norm regularization[END_REF][START_REF] Boyd | The alternating descent conditional gradient method for sparse inverse problems[END_REF]) based on the "Frank-Wolfe" (FW) algorithm [START_REF] Frank | An algorithm for quadratic programming[END_REF], namely the so-called "atom selection" step:

Find

a max ∈ arg max a∈A a, r , (2)
where r ∈ H is some "iteration-dependent" element. 2 We note that ( 2) is also central to the implementation of many standard greedy procedures, e.g., MP [START_REF] Mallat | Matching pursuits with timefrequency dictionaries[END_REF] or OMP [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF].

Although greedy and FW-based procedures are commonly assumed to be low-complexity methodologies in the sparse-representation literature, we see from (2) that identifying a max nevertheless requires to sweep over all the elements of A. If the dictionary contains a huge number of elements (and in particular if A is continuous), finding the true maximizer can thus lead to an overwhelming complexity. Quite surprisingly, little attention has been brought to the practical implementation of (2) in the current literature. Most of the contributions simply suppose that "an efficient scheme to evaluate (2) exists". A noticeable exception is [START_REF] Karin C Knudson | Inferring sparse representations of continuous signals with continuous orthogonal matching pursuit[END_REF], where the authors propose to approximate the solution of (2) as the output of a low-dimensional interpolation scheme.

In this paper, we propose an efficient methodology to perform (2) with a prescribed accuracy. Our procedure is inspired from our work [START_REF] Herzet | Gather and Conquer: Region-based Strategies to Accelerate Safe Screening Tests[END_REF]: it consists in performing simple tests allowing to identify groups of atoms not attaining the maximum value of (2). Although motivated in the context of continuous dictionaries, our methodology applies to both the continuous and discrete settings. It may provide important computational gain as soon as the number of atoms in A is large. Moreover, in the context of continuous dictionaries, and considering "inexact" versions of the FW algorithm (see [START_REF] Jaggi | Revisiting frank-wolfe: Projection-free sparse convex optimization[END_REF]), the proposed framework can also be exploited to derive upper bounds on the maximum value of (2) that can, in turn, be used to check the "δ-accuracy" of the selected atoms.

THE PROPOSED STRATEGY

Hereafter, we first expose our atom rejection strategy in Section 2.1. Then, in Section 2.2, we propose a strategy to ensure that the selected atom achieves the maximum of (2) with a prescribed accuracy.

Atom rejection procedure

Our proposed selection strategy is based on the following observations. If S is a (closed) subset of A, then max a∈S a, r ≤ max a∈A a, r .

Hence, letting τ max a∈S a, r , we have ∀a ∈ A:

a, r < τ ⇒ a / ∈ arg max ã∈A ã, r . (3)
In other words, if a ∈ A is an atom which satisfies the inequality in the left-hand side of (3), then this atom is surely not the one to be selected by [START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF]. Elaborating on this observation, we further have:

max a∈R a, r < τ ⇒ ∀a ∈ A ∩ R : a / ∈ arg max ã∈A ã, r , (4)
where R is some arbitrary subset of H. In the sequel we will refer to R as "region". The operational meaning of ( 4) is as follows: if the inequality in the left-hand side is satisfied, one is ensured that no atom in A ∩ R will attain the maximum of a, r . The entire set A ∩ R can thus be ignored, enabling us to reduce the number of candidate atoms to be tested in the selection [START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF]. Test (4) constitutes the basis of our complexity reduction method, described in Algorithm 1. Our goal is to identify subsets of the dictionary, say A not , that do not contain a max . This goal is achieved by applying the discriminative test (4) on a set of regions {R l } L l=1 . Once a set A not has been identified, we are left with the simpler problem Find a max ∈ arg max a∈A\Anot a, r .

(

The computation savings induced by ( 5) stands in the reduction of the number of atoms to be tested to find a max . In the discrete setting, the computational reduction is a direct function of the cardinality of A and A\A not . In the continuous setting, both A and A\A not usually contain an infinite number of atoms. Nevertheless the search of a max over the reduced domain A\A not may be much faster than over the entire space A.

The choice of the regions {R l } L l=1 is a degree of freedom of the procedure, different choices leading to different performance. The complexity associated to the evaluation of the left-hand side of ( 4) is a direct function of the geometry of R. The following result, proved in our companion paper [START_REF] Herzet | Gather and Conquer: Region-based Strategies to Accelerate Safe Screening Tests[END_REF]Theorem 1], shows that for "dome" and "sphere" regions, test (4) can be carried out at the cost of one inner product in H:

Algorithm 1 Efficient atom selection strategy

Inputs: residual r, subset of atoms S, set of regions {R l } L l=1 Init: :

A not = ∅ Evaluate τ = max a∈S a, r for all 1 ≤ l ≤ L do if max a∈R l a, r < τ then A not = A not ∪ (A ∩ R l ) end if end for Find a max ∈ arg max a∈A\Anot a, r Theorem 1. Let B t, {a : a -t ≤ } (sphere), D t, {a : a, t ≥ , a = 1} (dome). If R = B t, , then max a∈R a, r < τ if and only if t, r < τ -r . Moreover, if R = D t, , then max a∈R a, r < τ if and only if t, r < τ, > t, r τ + t 2 -t, r 2 t 2 -τ 2 t 2 .
B t, and D t, define a sphere and a dome in H. Other geometries are possible, leading to different results. The analysis of different geometries of regions will be investigated in our future work.

Guarantees of δ-optimality

Although problem (5) may be structurally easier than its standard counterpart (2), finding an exact maximizer of a, r may still be complicated (in particular in the continuous setting). Hopefully, "inexact" versions of the FW algorithm exist [START_REF] Jaggi | Revisiting frank-wolfe: Projection-free sparse convex optimization[END_REF]: in these variants, the atom selected at each iteration, say a δ max , must verify

δ ≥ max a∈A a, r -a δ max , r (6)
where δ is some prescribed accuracy level.

In practice, (6) may seem difficult to check since evaluating the right-hand side of this expression entails knowing max a∈A a, r . Nevertheless, if one can identify some upper bound on max a∈A a, r , say β, a sufficient condition for [START_REF] Bredies | Inverse problems in spaces of measures[END_REF] to hold simply writes

δ ≥ β -a δ max , r . (7)
Algorithm 2 Region-based upper bound estimation Inputs: residual r, atom subset A\A not Build: a set of (dome or sphere) regions {R l } L l=1 , such that

A\A not ⊆ ∪ L l=1 R l (12)
for all 1 ≤ l ≤ L do Compute β l = max a∈R l a, r using ( 9) or [START_REF] Frank | An algorithm for quadratic programming[END_REF]. end for Set the upper bound: β = max 1≤l≤L β l . Check the relaxed condition [START_REF] Rao | Forwardbackward greedy algorithms for atomic norm regularization[END_REF].

In the sequel, we leverage [START_REF] Rao | Forwardbackward greedy algorithms for atomic norm regularization[END_REF] to derive accuracy guarantees on our atom selection method. More specifically, we emphasize that the "region-based" framework considered in this paper is prone to deriving simple upper bounds on max a∈A a, r .

We first note that max a∈A a, r = max a∈A\Anot a, r , so we can concentrate on the evaluation of an upper bound over A\A not . Next, if one can identify a set of (closed and bounded) regions {R l } L l=1 (possibly different from those considered in Section 2.1) such that A\A not ⊆ ∪ L l=1 R l , we have that

max a∈A\Anot a, r ≤ max 1≤l≤L max a∈R l a, r . (8)
Finally, max a∈R l a, r has a simple analytical expression for some particular geometries of R l :

Theorem 2. ∀r ∈ H we have max a∈Bt, a, r = t, r + r ,

max a∈Dt, a, r = r if ≤ t,r r f ( ) otherwise , (9)
where

f ( ) t, r + 1 -2 r 2 -t, r 2 . (11)
A proof of this result can be found in our companion paper [START_REF] Herzet | Gather and Conquer: Region-based Strategies to Accelerate Safe Screening Tests[END_REF]Theorem 2]. We see that by combining Theorem 2 with (8), we obtain an easy computable upper bound on max a∈A\Anot a, r . The δ-accuracy of some candidate atom a δ max can then be verified via [START_REF] Rao | Forwardbackward greedy algorithms for atomic norm regularization[END_REF]. The proposed strategy is summarized in Algorithm 2.

EXPERIMENTS

In this section, we illustrate the performance achieved by the proposed methodologies in the case of a Gaussian deconvolution problem. In this setup, the "atom" function defining the dictionary in ( 1) writes (up to some normalization factor) as where σ 2 = 0.01 and ∆ = 0.02 are some parameters. In Fig. 1, we first assess the performance of the atomrejection procedure introduced in Section 2.1 (see Algorithm 1) on random realizations of r. In order to evaluate the computational gain induced by the proposed methodology, we consider a discrete setting where A contains a finite number of atoms. In particular, we set

a : Θ → R m θ → exp -(i∆-θ) 2 2σ 2 1≤i≤m (13)
Θ = θ min + j 2048 θ range : j = 1 . . . 2048
where θ min = 0 and θ range = 2. The figure of merit represented in Fig. 1 then writes

computational gain = 1 - L + card{A\A not } card{A} . (14)
The numerator (resp. denominator) of the ratio in ( 14) represents the total number of inner products needed to identify a max with Algorithm 1 (resp. a brute-force approach). The "computational gain" thus represents the proportion of inner products which can be saved by using the proposed methodology (as compared to a brute-force approach). We consider both the cases where the regions {R l } L l=1 are defined as either spheres B t, or domes D t, (see Theorem 1). The centers of the regions correspond to a regular subsampling of the dictionary A. The radius of the spheres are set to = 0.3 and the radius of the domes to = 0.9550. These radii have been chosen so that sphere and dome regions cover exactly the same subset of atoms of the dictionary. The vector r is built as a Gaussian random linear combination of 5 atoms of A. The results are averaged over 50 realizations of r.

We see in Fig. 1 that the computational gain induced by our method raises up to 0.8 for both sphere and dome regions when L = 128. In other words, the proposed methodology allows for the savings of 80% of the inner products needed by a brute-force evaluation of (2). The gain is usually slightly larger for dome regions (blue) than for sphere regions (red). This is due to the fact that dome regions preserve the unit norm of the atoms and thus allow for a finer "covering" of the dictionary. In our second experiment, we assess the overall computational savings allowed by our atom-rejection procedure when used in the selection step (2) of a FW algorithm [START_REF] Frank | An algorithm for quadratic programming[END_REF]. More specifically, we address the resolution of a LASSO problem with de Gaussian dictionary defined in [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF]. The observation vector used as input of the LASSO problem, say y, is built as the Gaussian random linear combination of 5 atoms of the dictionary. The epigraph formulation of the LASSO problem, as suggested in [START_REF] Denoyelle | Theoretical and Numerical Analysis of Super-Resolution Without Grid[END_REF]Chapter 4], is considered and standard FW algorithm is applied. 3 The optimization procedure is stopped when a primal-dual gap of 10 -2 is attained. The complexity of the FW algorithm (with and without the proposed atom-rejection procedure) is measured by the number of multiplications 4 needed to complete the optimization process. The obtained results are illustrated in Fig. 2 as a function of the number of regions L used in the atom-rejection procedure. We see that for L varying between 2 5 and 2 8 , the proposed methodology allows for significant complexity savings. Fig. 3 offers a different perspective on this result: it represents the percentage of multiplications saved by using the proposed methodology. We see that, for values of L ranging between 2 5 and 2 8 , savings of roughly 60% can be achieved.

In our last experiment, we assess the quality of the δ- 3 The penalization parameter "λ" used in the LASSO problem is set to λ = 0.5 max θ∈Θ | a(θ), y |. 4 Multiplications dominate the complexity of floating-point operations.

where β is the bound defined in Algorithm 2. We consider the following simulation setup. The vector r is built as the Gaussian random linear combination of 5 atoms of A. The results are averaged over 50 realizations of r. We suppose that the atoms in A\A not correspond to parameters in the interval I θmax = [θ max -ρ, θ max +ρ], where θ max is the parameter associated to a max (that is a max = a(θ max )). Two different values of ρ are considered in Fig. 4. The centers of the regions used in Algorithm 2 correspond to a regular subsampling of I θmax . The radius of all the regions is the same and is chosen ∀L so that A\A not ⊆ ∪ L l=1 R l , that is the set of regions {R l } L l=1 covers the residual dictionary. We see in Fig. 4 that, quite logically, the tightness of the proposed bound improves with the number of regions and the decrease of ρ. We also note that the dome regions lead again to superior performance than sphere regions.

CONCLUSIONS

In this paper, we propose an atom-rejection procedure that allows to reduce the computation complexity of the atomselection step inherent to greedy algorithms. Our approach relies on the partition of the atoms into regions having suitable geometries. We show that the maximization of linear functionals over these regions has simple analytical solutions which can, in turn, be exploited to reduce the cost of greedy procedures. Our experiments, carried out in the context of the standard Gaussian deconvolution problem, show that large computational gains can be achieved when dealing with large dictionaries.

Fig. 1 .

 1 Fig. 1. Computational gain achieved by the atom rejection method described in Algorithm 1 as a function of the number L of regions for random realizations of r.

Fig. 2 .

 2 Fig. 2. Total number of multiplications carried out during the FW algorithm as a function of the number L of regions.

Fig. 3 .

 3 Fig.3. Percentage of saved multiplications to complete the optimization process by using the proposed atom-rejection procedure.

5 Fig. 4 .

 54 Fig. 4. Tightness of the upper bounds defined in Theorem 2.

This can be done without loss of generality as the standard problem can be exposed as a particular case of the positive one.

We note that if A is a "continuous" dictionary, the continuity of a : Θ → H and the compactness of Θ ensures the existence of a maximizer by virtue of the Weierstrass theorem, see e.g.,[START_REF] Bertsekas | Nonlinear Programming[END_REF] Proposition A.8].

ACKNOWLEDGMENTS

The authors thank the DGA/MRIS, the ONR (N62909-17-1-2007) and the ANR (ANR-15-CE23-0021) for their financial support.


Frédéric Champagnat

Cédric Herzet

ATOM SELECTION IN CONTINUOUS DICTIONARIES: RECONCILING POLAR AND SVD APPROXIMATIONS

Keywords: Sparse representation, Continuous dictionary, BLASSO, SVD

This paper deals with efficient atom selection procedure in a continuous dictionary, as required for instance in a Frank-Wolfe approach within a BLASSO problem for the onedimensional deconvolution problem. We show that efficient maximization of a correlation between any given vector and an atom sweeping a continuous dictionary can be performed through a particular piece-wise linear approximation of dictionaries: the polar approximation. We finally identify the polar approximation as being optimal in a mean square error sense for dictionaries with raised-cosine Toeplitz kernels.

PROBLEM STATEMENT

Sparse representations in redundant dictionaries is a problem of great interest which has attracted the attention of many researchers during the last decades. Recently, this paradigm has been reformulated in a "continuous" setup, where the representation dictionary contains an infinite uncountable number of elements. In this context, the collection of atoms forming the dictionary A typically takes the form:

A = {a(θ) : θ ∈ Θ} (1)
where a : Θ → H is some continuous bounded function, Θ an interval of R d and H some Hilbert space (with inner product •, • and induced norm • ).

In the last years, several theoretical works showed that sparse linear combinations of continuous atoms (say y = K i=1 α i a(θ i ) with α i ∈ R and θ i ∈ Θ) can be recovered under mild conditions as the solution a convex optimization problem over the space of Radon measure: 1 min µ∈M(Θ)

1 2 y -Aµ 2 + λ µ TV (2)
where M(Θ) is the space of Radon measures over Θ, A : M(Θ) → H is a "dictionary-dependent" bounded linear operator and µ TV is the so-called "Total Variation" norm, see e.g., [START_REF] De | Exact reconstruction using Beurling minimal extrapolation[END_REF][START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF][START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF][START_REF] Denoyelle | Support Recovery for Sparse Super-Resolution of Positive Measures[END_REF]. Problem ( 2) is commonly referred to as "BLASSO" and can be seen as the continuous counterpart of the well-known LASSO problem [START_REF] Foucart | A mathematical introduction to compressive sensing[END_REF]. Despite these nice theoretical results, finding the solution of BLASSO turns out to be a challenging issue since it entails the resolution of an optimization problem over the infinitedimensional set of Radon measures M(Θ). Hence, several works recently addressed the problem of designing tractable algorithms solving [START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF], see [START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF][START_REF] Ekanadham | Recovery of sparse translation-invariant signals with continuous basis pursuit[END_REF][START_REF] Bredies | Inverse problems in spaces of measures[END_REF][START_REF] Knudson | Inferring sparse representations of continuous signals with continuous orthogonal matching pursuit[END_REF][START_REF] Rao | Forward-backward greedy algorithms for atomic norm regularization[END_REF][START_REF] Boyd | The alternating descent conditional gradient method for sparse inverse problems[END_REF][START_REF] Catala | A lowrank approach to off-the-grid sparse deconvolution[END_REF]. This article is part of this trend. We propose an efficient procedure to solve BLASSO for "one-dimensional (1D) deconvolution" problems (d = 1). Our procedure is based on a fast (approximated) implementation of the well-known Frank-Wolfe (FW) algorithm [START_REF] Frank | An algorithm for quadratic programming[END_REF].

PRACTICAL IMPLEMENTATIONS OF BLASSO

We first review some algorithmic solutions proposed in the literature to address the BLASSO problem [START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF]. We leverage these considerations to build a new fast solving methodology for BLASSO in the next section.

FW-based Implementations

Among the different works addressing the resolution of (2), quite a fair number of them were based on variations of the well-known FW iterative algorithm, see [START_REF] Bredies | Inverse problems in spaces of measures[END_REF][START_REF] Rao | Forward-backward greedy algorithms for atomic norm regularization[END_REF][START_REF] Boyd | The alternating descent conditional gradient method for sparse inverse problems[END_REF]. A common feature of all these procedures stands in the following "atom selection" step:2

a max ∈ arg max a∈A a, r , (3)
where r ∈ H is some iteration-dependent vector. From a practical point of view, FW-based procedures thus trade the infinite-dimensional search over the space of Radon measure against the maximization of some linear function over the dictionary A.

Although most contributions of the literature assume that "some efficient scheme to find a max exists", the search over the entire dictionary (3) may reveal to be a tedious operation since A is commonly a highly non-convex set. In this paper, we propose a solution to this issue in the case of 1D-deconvolution problems. Our approach is based on some finite-dimensional approximations of the dictionary.

Dictionary approximations

A practical way of avoiding the infinite-dimensional nature of problem (2) consists in approaching A by a set of finitedimensional approximations.

This strategy can be formalized as follows. Let Θ = ∪ L =1 Θ be a partition of the parameter space. Using definition (1), A can then be expressed as A = ∪ L =1 A where A = {a(θ) : θ ∈ Θ }. For some proper choice of Θ , all the atoms in A may be "close" to some low-dimensional subspace of H. In such a case, A can be accurately approximated as3

 = K k=1 c k v k : c ∈ C (4)
for some v k ∈ H and C ⊆ R K . An approximation of the overall dictionary A can then be simply written as

 = ∪ L =1  . (5)
We note that ( 4) is tantamount to approximating the atoms of A in some linear K-dimensional subspace of H. In the sequel, we will thus refer to (4)- [START_REF] Foucart | A mathematical introduction to compressive sensing[END_REF] as "piece-wise linear approximation of A".

From a computational point of view, working with piecewise linear approximations may be far more efficient than exploiting the true dictionary. This idea has thus been used in several contributions, where different choices for {v} K =1 and C were suggested. We describe hereafter the "polar" and "SVD" approximations proposed in [START_REF] Ekanadham | Recovery of sparse translation-invariant signals with continuous basis pursuit[END_REF][START_REF] Knudson | Inferring sparse representations of continuous signals with continuous orthogonal matching pursuit[END_REF].

Assume Θ is an interval of R and {Θ } L =1 some subintervals of Θ, say Θ = θ -∆ 2 , θ + ∆ 2 where { θ } L =1 are points on a regular grid and ∆ is the space between two grid points. The "polar" decomposition presented in [START_REF] Ekanadham | Recovery of sparse translation-invariant signals with continuous basis pursuit[END_REF] considers the case where K = 3 and define C as

C = (1, cos(ωτ ), sin(ωτ )) : τ ∈ - ∆ 2 , ∆ 2 (6)
for some ω ∈ R. The vectors {v k } 3 k=1 are chosen so that

a( θ ) ∈ Â and a( θ ± ∆ 2 ) ∈ Â. (7)
This choice entails in particular that perfect atom interpolation is achieved on the grid

{ θ } L =1 ∪ { θ ± ∆/2} L =1 .
The "SVD" approximation presented in [START_REF] Knudson | Inferring sparse representations of continuous signals with continuous orthogonal matching pursuit[END_REF] computes {v k } K k=1 according to a different criterion. More specifically, the authors suggest to select {v k } K k=1 to minimize the "mean square approximation error (MSAE)" between the atoms in A and their projections onto V = span({v} K =1 ) (see Section 3 for more details).

We note that the authors deviate nevertheless from the goal of achieving the minimum MSAE by constraining the coefficients c k to belong to some pre-specified intervals of values. We elaborate on this topic in the next section. In particular, we emphasize that quasi-optimal MSAE can be achieved in some situations, by imposing polar constraints (6) on the coefficients c k 's.

EFFICIENT FW-IMPLEMENTATION WITH QUASI • -OPTIMAL APPROXIMATION

Dictionary approximations have been used to devise different "low-complexity" continuous sparse representation procedures in the literature. In [START_REF] Ekanadham | Recovery of sparse translation-invariant signals with continuous basis pursuit[END_REF], the authors used approximate dictionaries to build a discrete surrogate of the BLASSO problem. In [START_REF] Knudson | Inferring sparse representations of continuous signals with continuous orthogonal matching pursuit[END_REF], a modified version of orthogonal matching pursuit [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF] was proposed.

In this paper, we show that fast (approximate) FW-based implementation of BLASSO can be devised by using approximated dictionaries. Our contribution is twofold. We first show that any piece-wise linear approximation enforcing polar constraints (6) allows for an efficient implementation of the atom selection step [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF]. Second, we emphasize that, in some particular cases, the • -optimal approximation of Âk in the "SVD" subspace proposed in [START_REF] Knudson | Inferring sparse representations of continuous signals with continuous orthogonal matching pursuit[END_REF] admits a polar decomposition. Overall, combining these two ingredients, we propose a fast approximate implementation of FW for BLASSO.

Atom selection with polar decomposition

We focus on the atom selection step (3) when A is approached by some piece-wise linear approximation (4)-( 5). We consider the case where K = 3 and assume that polar constraints [START_REF] Ekanadham | Recovery of sparse translation-invariant signals with continuous basis pursuit[END_REF] are imposed on the coefficients c k . We make no assumptions on the choice of the vectors {v k } 3 k=1 . Using the partition of the approximate dictionary (5), we first have that

max a∈ Â a, r = max max a∈ Â a, r . (8)
Moreover, if the subdictionary  takes the form (4) and C is defined as in [START_REF] Ekanadham | Recovery of sparse translation-invariant signals with continuous basis pursuit[END_REF], the inner maximization in the right-hand side of (8) can equivalently be rewritten as

max τ ∈[-∆ 2 , ∆ 2 ] v 1 , r + cos(ωτ ) v 2 , r + sin(ωτ ) v 3 , r . (9)
Now, (9) has a closed form expression, as shown by the following lemma:

Lemma 1. Let f (τ ) = a cos(ωτ ) + b sin(ωτ ) with 0 < ω ≤ 2π. Then, max τ ∈[-1 2 , 1 2 ] f (τ ) = √ a 2 + b 2 if ρ > η a η + |b| 1 -η2 otherwise where ρ = a √
a 2 +b 2 and η = cos(ω/2). Moreover, the unique minimizer of the problem writes

arg max τ ∈[-1 2 , 1 2 ] f (τ ) = ω -1 arcos(ρ) sign (b) if ρ > η 1 2 sign (b) otherwise
Proof: Using symmetry of the optimization domain and sin(ωτ ) = -sin(-ωτ ), the problem can be rewritten as

max η≤η≤1 a η + |b| 1 -η 2 (10)
by setting η = cos(ωτ ). The final results are direct consequences of [14, Lemma 2].

Lemma 1 thus provides an efficient procedure to solve (8) when  takes the form (4) and C is defined as in [START_REF] Ekanadham | Recovery of sparse translation-invariant signals with continuous basis pursuit[END_REF]. We show hereafter that such approximation spaces appear as quasi-optimal in a MSAE sense for translation invariant dictionaries.

• -optimal approximation

Since (4) enforces  to belong to some K-dimensional subspace of H (namely V = span({v } K k=1 )), we can raise the following questions: i) Given a K-dimensional subspace V and some atom a ∈ A , what is the "best" approximation of a in V ?

ii) How to choose some "good" K-dimensional approximation subspace for all the atoms in A ?

The answers to these questions have been known in the literature for decades. The best approximation of a in V with respect to the distance induced by • is given by the so-called "orthogonal projector":

P V (a) arg min ã∈V a -ã . (11)
P V (a) always exists and is unique since

V is K-dimensional.
As for the second question, a common criterion to select a "good" approximation subspace is the minimization of the "average projection error", that is

V K opt = arg min V :dim(V )=K Θ a(θ) -P V (a(θ)) 2 dθ. (12)
It can be seen [START_REF] Schmidt | Zur theorie der linearen und nichtlinearen integralgleichungen. iii. teil[END_REF], that the solution of this problem only depends on the kernel function specifying the inner product between two atoms of A :

κ(θ, θ ) a(θ), a(θ ) . ( 13
)
More specifically, the following result shows that an orthogonal basis of V K opt can be found as the solution of an eigenvalue problem:

Theorem 1 (Spectral decomposition [START_REF] Schmidt | Zur theorie der linearen und nichtlinearen integralgleichungen. iii. teil[END_REF]). Let

R : L 2 (Θ ) → L 2 (Θ ) u(θ) → Θ κ(θ, θ )u(θ )dθ , ( 14
)
where L 2 (Θ ) is the set of square-integrable functions on Θ . Let σ 2 k K k=1 be the K largest eigenvalues of R and {u k } K k=1

the associated orthonormal eigenfunctions. Then,

v k Θ a(θ)u k (θ)dθ, k = 1 . . . K (15)
is an orthogonal basis of V K opt . Moreover, we have ∀θ ∈ Θ :

P V K opt (a(θ)) = K k=1 σ k u k (θ)v k . ( 16
)

Raised-cosine kernels

In [START_REF] Knudson | Inferring sparse representations of continuous signals with continuous orthogonal matching pursuit[END_REF], the authors suggested to choose the "SVD" approximation vectors {v k } 3 k=1 as in [START_REF] Schmidt | Zur theorie der linearen und nichtlinearen integralgleichungen. iii. teil[END_REF]. Their dictionary approximation does however not attain the • -optimal error because the decomposition coefficients of each atom a(θ) (in the definition of C) is not constrained to be equal to c k = σ 2 k u k (θ), as in ( 16). This choice is probably due to the fact that u k (θ) is typically a complicated function of θ.

In this section we emphasize that the decomposition coefficients of a(θ) (in some particular basis of V 3 opt ) may nevertheless have a desirable form in some cases. Our starting point is the following observation: for many standard 1Ddeconvolution problems, kernel κ(θ, θ ) can be accurately approximated as

κ(θ, θ ) = a + b cos(ω(θ -θ )), (17)
for some a ∈ R, b ∈ R and ω ∈ R + . Indeed, for 1D-deconvolution problems the dictionary is translation invariant, so κ is a Toeplitz kernel: we have κ(θ, θ ) = κ(θ -θ ) where κ is the autocorrelation of any atom. For standard atoms, κ has a smooth symmetric bell shape, and can be accurately approximated by a raised-cosine, see Table 1.

The next theorem shows that any dictionary A whose kernel satisfies (17), admits a "polar" decomposition for the projection operator onto V 3 opt :

Lemma 2. Assume the kernel function κ(θ, θ ) associated to A verifies (17). Then, there exists {v i ∈ H} 3 i=1 such that

P V 3 opt (a(θ)) = v 1 + cos(ωθ)v 2 + sin(ωθ)v 3 . (18)
Proof : Using (16), it is sufficient to show that the first three eigenfunctions of R (defined in ( 14)) can be written as linear combinations of cos(ωθ), sin(ωθ) and the constant function over Θ , say 1 Θ (θ). Now, using a simple trigonometric identity, we obtain κ(θ, θ ) = a + b cos(ωθ) cos(ωθ ) + b sin(ωθ) sin(ωθ ), and therefore span(R) = span(1 Θ (θ), cos(ωθ), sin(ωθ)). Finally, since the first three eigenfunctions of R must belong to span(R), we obtain the result.

Eigenvalues and eigenfunctions of κ(θ, θ ) can be derived in closed form, but, for the sake of conciseness, we restrict ourselves to the result stated in Lemma 2. We note however that the vectors {v k } 3 k=1 can be readily evaluated from the knowledge of a, b and ω.

We conclude this section by identifying a basis {v k } 3 k=1 such that the piece-wise linear approximation (4) obeys

 = P V 3 opt (a(θ)) : θ ∈ Θ ( 19
)
when C is defined as in [START_REF] Ekanadham | Recovery of sparse translation-invariant signals with continuous basis pursuit[END_REF]. This result is a direct consequence of Lemma 2, it is stated in the following Theorem 2.

Theorem 2. Let Θ = θ -∆ 2 , θ + ∆ 2 .
Assume the kernel function κ(θ, θ ) associated to A verifies (17) and let {v i ∈ H} 3 i=1 be the vectors defined in Lemma 2. If

v 1 = v 1 v 2 = cos(ω θ )v 2 + sin(ω θ )v 3 v 3 = cos(ω θ )v 3 -sin(ω θ )v 2 (20)
then approximation (4) with C defined as in (6) obeys (19).

The combination of Lemma 1 + Theorem 2 leads to a fast implementation of atom selection step (3) with (quasi) •optimal piece-wise linear dictionary approximation.

NUMERICAL EXPERIMENTS

We explore hereafter the generality and accuracy of the (quasi) • -optimal approximation in the case of translation invariant dictionaries. We have already noticed that in such case κ is a Toeplitz kernel defined by autocorrelation κ of any atom. For sufficiently smooth atoms (see below the discussion on the Laplacian atom), κ has a smooth symmetric bell shape near zero. A raised-cosine approximation of such a bell shaped function is built by matching κ at points {0, ∆/2, ∆}, and closed form expressions can be derived for a, b and ω in terms of κ(0), κ(∆/2) and κ(∆).

The accuracy of such an approximation is measured in Table 1 using a P SN R metric: where M SE is the mean squared error between κ and its raised-cosine approximation. For the Gaussian atom, the approximation is already excellent at σ = 1. For the Laplacian atom, a raised-cosine approximation for κ is also available, although it has a derivative singularity at zero. The approximation of the Laplacian is less accurate than that of the Gaussian, but is already very good for σ = 2.

P SN R = 10 log 10 ( κ(0) -κ(∆)) 2 M SE , σ 1
Therefore, for large enough σ, or, equivalently, small enough ∆, (17) holds for Gaussian and Laplacian atoms. In such context, one may consider dictionary approximations (4) with v k defined by (20) and C defined as in [START_REF] Ekanadham | Recovery of sparse translation-invariant signals with continuous basis pursuit[END_REF].

We next assess the ability of such approximations to achieve accurate atom selection. We study the basic problem of estimating the true location θ of the atom as follows

Table 2 shows that the approximation recovers the true location of the atom with very good accuracy (less than 0.004 the width of the approximation cell), improving with increasing smoothness of the atom.

CONCLUSION

This paper deals with efficient atom selection procedure in a translation invariant continuous dictionary, as required in a Frank-Wolfe approach within a BLASSO problem for 1Ddeconvolution. The main results are Lemma 1 and Theorem 2 whose combination leads to a fast implementation of atom selection step (3) with (quasi) • -optimal piece-wise linear dictionary approximation. Such approximations are shown to be accurate for typical Gaussian and Laplacian atoms, even if the latter has a singularity at zero on its derivative.

θ = arg max θ∈Θ v 1

 1 + cos(ωθ)v 2 + sin(ωθ)v 3 , a θ , (21) where {v i ∈ H} 3 i=1 fulfills the assumptions of Theorem 2. We use Lemma 1 to compute θ, then define bias = max θ ∈Θ | θ(θ ) -θ |.

Table 1 .

 1 P SN R of the approximation of κ on [-1, 1] by a raised-cosine, for Gaussian and Laplacian atoms. P SN R is computed w.r.t σ, the standard deviation of the atom.

				2	3	4	5
		P SN R gauss		30 71 96 113 127
		P SN R laplace 0.5 23 37 47	54
	σ	0.5	1	1.5		2	2.5
	bias 3.3e-3 2.6e-4 6e-5 2.3e-5 1.1e-5

Table 2 .

 2 Maximal bias for estimation of θ on [-1/2, 1/2] (∆ = 1) using (21), for Gaussian atoms. Bias is computed w.r.t σ, the standard deviation of the atom.

With a slight abuse of notation, we use the notation "a" to denote both an element of A and the continuous bounded function a : Θ → H.

The vectors v k typically differ for each subdictionary  . Nevertheless, we drop this dependence in our notations to keep our exposition as simple as possible.


P Hussein

Coussy

Senior member IEEE C Chavet

F Lozachmeur

T Barguil

A S Hussein

Senior member P Coussy

SOLVING MEMORY ACCESS CONFLICTS IN LTE-4G STANDARD

Keywords: Hardware design, memory access conflicts, LTE standard, Error Correction Codes, Rate Matching

HAL is

INTRODUCTION

The works of Shannon [START_REF] Shannon | A mathematical theory of communication[END_REF] have demonstrated it is possible to send digital data through noisy channel with high reliability. The idea roughly consist to first encode a digital message with an Error Correction Code (ECC) at transmitter side, and then to decode it at receiver side in order to retrieve the original message (cf. Figure 1). Several ECC have been introduced since so far to sustain this concept. In order to achieve high throughput requirements ECC decoders are based on parallel architectures. In such parallel architectures, several Processing Elements PEs are concurrently used to decode the received information [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF]. In this context, several memory banks RAMs are connected with these PEs through a dedicated interconnection network. This network transfers data between PEs and RAMs according to predefined access orders, i.e. the interleaving rules. Designing efficient parallel hardware architecture i.e. with no memory access conflicts is a very complex and time consuming task (e.g. several man/months in 3GPP-LTE for an expert). A lot of work has been done to explore solutions to avoid interleaving conflicts in ECC architectures ( [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] to [START_REF] Giulietti | Parallel turbo coding interleavers: avoiding collisions in accesses to storage elements[END_REF]). This paper however focuses on LTE-4G standard [START_REF]LTE, Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access; Multiplexing and Channel Coding (Release 8)[END_REF] which relies on QPP algorithm that has been designed to avoid such problems [START_REF] Wong | Reconfigurable Turbo Decoder With Parallel Architecture for 3GPP LTE System[END_REF]. Unfortunately, conflicting issues still appear when inverse Rate Matching (RM) module and ECC decoder are connected (see Figure 1). Indeed, on the one hand the goal of RM is to match the number of bits of packets sent through the channel, to the number of bits that can be transmitted for a given allocation (required throughput, QoS…). On the other hand, the encoder maps X message digits into C code-word digits (with C > X) providing the code rate r=X/C which defines the redundancy introduced by ECC. Unfortunately, the sequence of code-words generated by the inverse rate matching does not match with the order expected by the ECC decoder [START_REF] Wong | Reconfigurable Turbo Decoder With Parallel Architecture for 3GPP LTE System[END_REF]. This paper is organized as follows. Section 2 describes how LTE-4G RM builds packets for channel transmission and why memory access conflicts appear in parallel LTE decoder. Section 3 proposes a deeper analysis of memory access conflicts between inverse RM module and ECC decoder. Section 4 describes a dedicated memory mapping approach and presents results which show that any conflicts for any block sizes and any parallelism degrees in the context of LTE-4G are removed.

LTE-4G OVERVIEW

Building payload for channel transmission

To transmit a code at an arbitrary rate (depending on available physical resources) a Rate Matching is performed after the turbo encoding (WCDMA [START_REF]LTE, Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access; Multiplexing and Channel Coding (Release 8)[END_REF], which performs a 1/3 rate encoding). For every single input bit, 3 output bits are given: the first bit is the original input bit (called systematic bit) ; the remaining two bits are the interleaved versions of the input bit (referred as parity 1 and parity 2 bits, Figure 2). These three streams of systematic, P1 and P2 are then provided as inputs to the rate matching module. Transmission RM algorithm punctures the bits of a mother code-word produced by the encoder. First, from the incoming message bits D = {d0, d1,…,dM-1}, with M<6145, the turbo-encoder generates three encoded sequences dk (i) , i=0,1,2 which are referred as Systematic, Parity 1 and Parity 2 respectively (Figure 2). If M is not a regular payload size defined in [START_REF]LTE, Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access; Multiplexing and Channel Coding (Release 8)[END_REF], filler bits are added in order to reach the next upper regular one. For example, if M = 84, 4 filler bits are added in order to reach the nearest bigger payload size K7 = 88. It should be noticed that a filler bit is a <NULL> value and that the generated Parity 2 sequence is not affected by filler bits. The turbo-encoder also computes 4 tail bits added in each generated code-word as RSC. At this step, the number of encoded message bits D is D=88+4=92.

Then each sequence is considered as a matrix of 32 columns ܥ( ௦௨ ் =32). The bits sent to the sub-block interleavers are denoted as ݀ () , ݀ ଵ () , ݀ ଶ () ,… ݀ ିଵ () , where D is the number of bits. The output sequences of bits of the sub-block interleavers are derived as follows:

1-Let ܥ ௦௨ ் = 32 be the number of columns of the matrix. The columns of the matrix are numbered 0,1…

ܥ ௦௨ ் -1.

2-Determine the number of rows ܴ ௦௨

் of the matrix by finding minimum integer such that:

ܦ ≤ ܴ ௦௨ ் × 32
However, if the resulting matrices are not entirely filled, dummy bits (i.e. <NULL> values) are padded at the beginning of the matrices. Now the matrices are ready to perform intercolumn permutation, as described in [START_REF]LTE, Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access; Multiplexing and Channel Coding (Release 8)[END_REF], and the resulting interleaved sequences (i.e., ݒ () , ݒ (ଵ) , ݒ (ଶ) ) are provided to the bit collection step and next interlaced in a circular buffer. Finally, the payload sequence of encoded bits ݁ for transmission is generated as defined in the standard:

1-E bits are extracted from the circular buffer starting from an offset k0 and all dummy and filler bits are discarded. 2-If the algorithm reaches the end of the circular buffer, then it moves to its first element. In the LTE-4G standard, four redundancy versions (rv, a.k.a. code rate) are defined: they respectively start to read data at the top of the columns 2, 26, 41 or 53 (resp. rv0, rv1, rv2, rv3). In our pedagogical example with E=88 and rv0, the generated sequence of output bits transferred over the channel, is presented in Figure 3.

Channel de-interleaving and resulting memory conflicts

From the receiver point of view (cf. Figure 4), the input order corresponds to the output sequence ݁ described in the previous section. Each input is one LLR (Log-Likelihood Ratio) and is quantized on qw bits. The channel de-interleaver module performs different functions on the incoming quantized bit-LLR: The first step consists in retrieving turbo-encoded bit sequence and provide it to the parallel turbo decoder (CTC decoding). The turbo decoder receives a vector of K payload bits and produces 3ki + 12 coded bits, including filler bits and dummy bits where ki is one of the 188 block sizes defined in the standard (see [START_REF]LTE, Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access; Multiplexing and Channel Coding (Release 8)[END_REF]), ranging from 40 to 6144 payload bits. The constant value 12 refers to termination/tail bits added in the code-word as Recursive Systematic Code (RSC, [START_REF] Berrou | Near Shannon limit error-correcting coding and decoding: Turbo-codes[END_REF]). In the next subsections, the way packets are built at the transmitter side is not formally detailed. Rather, a pedagogical example, built with respect to the standard process from [START_REF]LTE, Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access; Multiplexing and Channel Coding (Release 8)[END_REF], is introduced. Since the sub-block de-interleaver shall support P samples per clock cycles (w.r.t. QPP interleaver [START_REF] Wong | Reconfigurable Turbo Decoder With Parallel Architecture for 3GPP LTE System[END_REF]), data should be provided respecting a given order described in Figure 5 where each column represents a timing step. To support this scenario in which four data are accessed in parallel, each row of the QPP matrix must be mapped in a dedicated memory bank. However the inverse RM module outputs the data in a different and incompatible order (see Figure 6): four data are still provided in parallel and so each row of the RM matrix must be mapped in a dedicated memory bank. Unfortunately, the two sequences (and their associated memory mapping) do not fit, resulting in memory conflict accesses. For example, data <2, 24 and 68> are stored in the same memory: "bank 3"; which is not compatible with QPP interleaver input constraint since data <2, 24, 46 and 68> are supposed to be accessed in parallel at time t2 (Figure 5).

DEEPER ANALYSIS OF MEMORY CONFLICTS

Simple memory mapping approach

In order to analyze the memory mapping problem previously introduced, we explored all the bit sequences that could be provided by the IR matching to the QPP interleaver (see Figure t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 1), as described in the LTE-4G standard. For each, we computed the number of memory access conflicts generated with a simple memory mapping approach. Figure 7 shows the number of conflicts generated by the RM algorithm in the receiver for a parallelism of 8, with the simple and natural memory mapping approach mentioned in the previous section. It can be observed that if the number of conflicts grows with the number of data, even for the smallest block size (i.e. 40) the number of conflicts to be handled is important (12 in this case). Traditional solution to solve such conflicts consists in adding FIFOs before the memory banks, to temporary store all the conflicting data. However, this widely impacts area, power consumption and timing performances of the final architecture.

Smarter mapping approaches

A careful analysis of Figure 7 highlights a regularity in the number of memory conflicts depending on the block sizes. The same kind of observations have been made for parallelism 2, 4, 16, 32, 64 and 128. Obviously, these observations confirm that the different block sizes of the standard have been defined with a very smart mathematical approach (see [9][18]). As a consequence, a smart systematic sub-block deinterleaving (Figure 4) approach might be proposed in order to avoid any memory conflicts. Different memory mapping algorithms have been used ( [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] to [START_REF] Giulietti | Parallel turbo coding interleavers: avoiding collisions in accesses to storage elements[END_REF]). In most of the cases, the solutions were not able to achieve no conflicts for all the block sizes and all the considered parallelism degree. This is the reason why we decided to address this problem from a different perspective i.e. reducing the constraint from QPP interleaver. Let's consider a LTE-4G decoder architecture with a parallelism Ps=2, a payload size K=64 and an encoding ratio r=½. Of course, this is a very simple and pedagogical example to illustrate our approach.

Thanks to the payload generation procedure described in the previous section, the output bit sequence illustrated in Figure 8 is generated. Once tail bits (i.e. bits 64 to 67) have been removed, the resulting de-interleaver bit sequence is: Since P=2 and K=64, each memory (bank 0 and bank 1) has to store K/P=32 data. Thus, applying a simple memory mapping approach generates the mapping presented in Figure 10.

Figure 10. Simple memory mapping results (K=64 and P=2)

In this pedagogical example, the QPP interleaver processes the data in the order defined in Figure 11. Once again, it can be observed that the proposed memory mapping (Figure 10) generates conflicts in the decoder: e.g., at time t2 data 1 and 33 have to be accessed at the same time (Figure 11), -i.e. they must be stored in different memory banksbut it is not possible since they are both stored in bank 1. A dedicated memory mapping approach is thus required.

PROPOSED MEMORY MAPPING APPROACH

We propose to replace the original QPP input order constraint by a custom "Temporary mapping constraint" TMap. The idea is to find a mapping constraint that is a simple permutation π of the original QPP data input order, but easier to solve. Hence, these data are read from memories and written to the QPP module, through a simple rerouting network π -1 . From the pedagogical example introduced in the previous section, a hypothesis is made: for a given set of K data, a parallelism P, and a set of B=P memory banks, (1) each memory banks stores K/P data;

(2) for a given memory address α, the difference between any 2 data in each memory bank at address α is lower than P, and they can be ordered incrementally.

In few words, this means that if in the QPP interleaver any two data are accessed at the same cycle, they cannot be stored in the same memory bank in the memory mapping generated with TMap constraint. t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 t26 t27 t28 t29 t30 t31 t32 The obtained intermediate TMap constraint supposes that the QPP interleaver is able to access data as shown in Figure 12.

Figure 13. Conflict free memory mapping approach with TMap constraint Then, a Constraint Graph CG taking into account all these constraints is defined and a constraint solver (from [START_REF] Ur Rehman | In-place memory mapping approach for optimized parallel hardware interleaver architectures[END_REF]) is applied (see Figure 13). If we apply this memory mapping approach the resulting memory mapping is:

-Bank 0 = {0, [START_REF] Reed | Polynomial Codes Over Certain Finite Fields[END_REF][START_REF]WIFI, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Enhancements for Higher Throughput[END_REF][START_REF] Berrou | Near Shannon limit error-correcting coding and decoding: turbo-codes[END_REF][START_REF] Hspa | Technical specification group radio access network;multiplexing and channel coding[END_REF][START_REF] Dvb-Sh | Framing structure, channel coding and modulation for satellite services to handheld devices (SH) below 3 GHz[END_REF][START_REF] Ur Rehman | In-place memory mapping approach for optimized parallel hardware interleaver architectures[END_REF][START_REF] Thul | Optimized concurrent interleaving architecture for highthroughput turbo-decoding[END_REF][START_REF] Karkooti | Configurable LDPC Decoder Architecture for Regular and Irregular Codes[END_REF][START_REF] Gpp | Evolved Universal Terrestrial Radio Access (E-UTRA): Multiplexing and channel coding[END_REF][START_REF] Frenger | Performance comparison of HARQ with Chase combining and incremental redundancy for HSDPA[END_REF][START_REF] Ur Rehman | In-place memory mapping approach for optimized parallel hardware interleaver architectures[END_REF]24,26,28,30,33,35,37,39,41,43,45,47,49,51,53,55,57,59, 61, 63} -Bank 1 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62} This approach is able to generate conflict free memory mapping with respect to the output bit sequence of the inverse RM module and the QPP interleaver input order (Figure 11). The resulting architecture does not need any additional memories (see Figure 1), since we are able to find no-conflict memory mapping in any case. Only few MUXs are added to route the data from a memory bank to the right decoder input.

Figure 15. Final architecture for our example (Figure 14)

EXPERIMENTS

In our experiments the proposed memory mapping approach has been applied for all combination of K data, r redundancy value and parallelism P (with all the K and r values extracted from [START_REF]LTE, Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access; Multiplexing and Channel Coding (Release 8)[END_REF], and P ϵ {2, 4, 8, 16, 32}). The solver runs on a laptop with an Intel core i7-6700HQ (2,6 GHz) and 16Go RAM. The area results are presented in NAND equivalent to be agnostic about the final target (FPGA, ASIC…).

Figure 16. Cost comparisons for P=8 (see figure 7)

Figure 16 shows a comparison between a handcrafted design (considered as the reference), a FIFO-based architecture obtained with a simple memory mapping approach and an architecture using the memory mapping approach we have presented in the previous section. Hence, contrary to the FIFO-based solution, our approach has no impact on the throughput since, thanks to the conflict-free memory mapping, no memory access is postponed. The area overhead is at worst comparable with the FIFO-based approach and at best 11 times smaller. This additional area is constant because a Benes network is used to support all the permutations while FIFO-based architectures uses dedicated set of MUXs to dispatch the data.

CONCLUSION

A major design issue of LTE-4G based systems resides in solving the memory access conflicts when connecting Rate-Matching (RM) and Error Correction Code (ECC) modules.

In this paper, we have described and analyzed the problem before proposing a dedicated memory mapping approach to remove all the memory access conflicts. This solution, based on temporary mapping constraints and a mapping solver, has been validated for any of the 188 block sizes defined in the standard and for parallelism from 2 to 32.

Figure 1 .

 1 Figure 1. Communication between emitter and receiver

Figure 2 .

 2 Figure 2. LTE-4G Rate Matching algorithm

Figure 3 .

 3 Figure 3. Output bit sequence with redundant bits from parity 1 and 2 (resp. dark and light grey)

Figure 4 .

 4 Figure 4. Functional coverage in LTE decoder chain

Figure 5 .

 5 Figure 5. Input order for QPP interleaver (P=4, 22 cycles)

Figure 6 .

 6 Figure 6. Input sequence order without tailing bits (Systematic)

Figure 7 .

 7 Figure 7. Number of memory conflicts for each block size with a parallelism P=8 (log. scale)

Figure 8 .

 8 Figure 8. Output bit sequence (K=64, r=1/2)

Figure 9 .

 9 Figure 9. De-interleaver input bit sequence

Figure 11 .

 11 Figure 11. QPP interleaver input order (K=64 and P=2)

Figure 12 .

 12 Figure 12. Intermediate TMap constraint (K=64 and P=2)

Figure 14 .

 14 Figure 14. Resulting memory mapping (Bank 0 in white, Bank 1 in grey)

  27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 t26 t27 t28 t29 t30 t31 t32 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 t26 t27 t28 t29 t30 t31 t32 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 t26 t27 t28 t29 t30 t31 t32 Min. conflicts Max. conflicts Min. conflicts Max. conflicts Number of

Acknowledgements

This research has been founded by the FEDER project FlexDEC-5G.

RELATED WORK