Quadratic Assignment Problems are a class of NP-hard combinatorial optimization problems with a wide range of real-world applications such as Vehicle Routing and FPGA Block Placement. Despite technological advances, solvers that target Quadratic Assignment Problems still require significant computing resources and time, especially as problem sizes grow; with the end of Dennard Scaling leading to the increased development of domain-specific hardware for such tasks. This paper presents MAQO: a hardware architecture for a scalable many-core annealer for quadratic optimization, implemented on an Intel Stratix 10 FPGA. MAQO is comprised of 32 domain-specific processing cores, supporting Quadratic Assignment Problems with up to 200 integer variables, in combination with a Parallel Tempering controller, all operating at 220MHz with a maximum FPGA power draw of 40W. We benchmark MAQO's performance, via solving some of the most difficult known Quadratic Assignment Problem instances, and show that it is, on average, 2.5 times faster than the next best competing solver with 22 times better performance-per-watt.

Assignment Problems are a class of NP-hard combinatorial optimization problems with a wide range of real-world applications such as Vehicle Routing and FPGA Block Placement. Despite technological advances, solvers that target Assignment Problems still require significant computing resources and time, especially as problem sizes grow. This paper introduces novel cost function formulations to leverage vector processing elements in accelerating local search algorithms for solving Quadratic Assignment and Semi-Assignment problems. We incorporate these vectorization methods within a Parallel Tempering framework to solve some of the most difficult known Quadratic Assignment and Semi-Assignment Problems up to sizes of 729 integer variables and show that this solver system can perform upwards of 300 times faster than other state-of-the-art solvers. We then conduct experiments to quantify the performance and scaling of these vectorization methods and qualify their situational strengths and trade-offs for use in future algorithms and hardware systems.

Boltzmann Machines are recurrent neural networks that have been used extensively in combinatorial optimization due to their simplicity and ease of parallelization. This paper introduces the Permutational Boltzmann Machine, a neural network capable of solving permutation optimization problems. We implement this network in combination with a Parallel Tempering algorithm with varying degrees of parallelism ranging from a single-thread variant to a multi-threaded system using a 64-core CPU with SIMD instructions. We benchmark the performance of this new system on Quadratic Assignment Problems, using some of the most difficult known instances, and show that our parallel system performs in excess of 100 $$\times $$ faster than any known dedicated solver, including those implemented on CPU clusters, GPUs, and FPGAs.

A replica exchange Markov Chain Monte Carlo (MCMC) engine is developed with automatic temperature adjustment for solving combinatorial optimization problems by minimizing the energy of the Ising model. The automatic temperature adjustment scheme ensures that the MCMC process is optimized at every stage of the execution. This approach is performed by dynamically adjusting temperatures of all replicas, based on the properties of any given problem, in addition to the capability of automatically inserting new replicas or removing any existing replicas to achieve the best possible resource efficiency and execution time. The proposed algorithm is integrated with parallel evaluation of energy increment and update scheme. The engine is implemented on the FPGA platform with a capacity of running up to 42 replicas in pipeline, each running 1024 fully-connected Ising spins in parallel. The performance of the hardware is examined with three different classes of problems, Vertex Cover, Maximum-Cut, and Travelling Salesman using the engine in three modes, simulated annealing, with replica exchange while the adjustments are turned on or off. Up to 16x speedup is observed by turning on the replica exchange capability in addition to the advantage of eliminating the challenging process of finding an optimal annealing schedule for simulated annealing process.

Cyber attacks on the power systems can mislead the control center to produce incorrect state and topology estimate. State and topology attacks can have harmful impacts on the operation of a power system. The problem of placing secure phasor measurement units (PMUs) to detect these attacks has been studied in the literature. Specifically, it has been shown that placing secure PMUs to disable undetectable state and topology attacks can enhance the security of the system against cyber attacks. Placing secure PMUs is indeed the minimum vertex cover problem. Since the cost of deploying PMUs is high, it is important to place the secure PMUs efficiently in order to maximize the ability of detecting cyber attacks while reducing the costs. In this paper, we use Digital Annealer to solve the vertex cover problem. Digital Annealer is a hardware architecture for solving combinatorial optimization problems. We have performed numerous numerical experiments and noticed that our approach has an enhanced level of optimality compared to other well-known alternatives in the literature.

FPGAs are widely used in digital circuits implementation because of their lower non-recurring engineering cost and shorter time-to-market in comparison with ASICs. However, there are still area, performance, and energy efficiency gaps between FPGAs and ASICs. In this work, we propose a new FPGA architecture to narrow the energy efficiency gap. Since more than 62% of FPGA power is consumed in its interconnect, we target power consumption of the interconnect and try to reduce dynamic power consumption of this part using low-swing signaling technique. To implement low-swing signaling, high-to-low and low-to-high voltage level converters are added to the switch boxes and connection blocks of the basic architecture. Simulation results on 20 largest MCNC circuits and 19 computational benchmarks confirm that the proposed architecture achieves an average of 13.5% total power reduction with the cost of less than 1% area and delay overhead. To the authors? knowledge, the proposed architecture in this work is the first architecture that provides low-swing signaling for single driver unidirectional routing scheme. Moreover, the proposed architecture has the maximum CAD tool flexibility and no extra constraint is required for the placement and routing algorithms.

This paper proposes a new technique for face detection and lip feature extraction. A real-time field-programmable gate array (FPGA) implementation of the two proposed techniques is also presented. Face detection is based on a naive Bayes classifier that classifies an edge-extracted representation of an image. Using edge representation significantly reduces the model's size to only 5184 B, which is 2417 times smaller than a comparable statistical modeling technique, while achieving an 86.6% correct detection rate under various lighting conditions. Lip feature extraction uses the contrast around the lip contour to extract the height and width of the mouth, metrics that are useful for speech filtering. The proposed FPGA system occupies only 15050 logic cells, or about six times less than a current comparable FPGA face detection system.

Cryptography circuits for smart cards and portable electronic devices provide user authentication and secure data communication. These circuits should, in general, occupy small chip area, consume low power, handle several cryptography algorithms, and provide acceptable performance. This paper presents, for the first time, a hardware implementation of three standard cryptography algorithms on a universal architecture. The microcoded cryptography processor targets smart card applications and implements both private key and public key algorithms and meets the power and performance specifications and is as small as 2.25 mm/sup 2/ in 0.18-/spl mu/m 6LM CMOS. A new algorithm is implemented by changing the contents of the memory blocks that are implemented in ferroelectric RAM (FeRAM). Using FeRAM allows nonvolatile storage of the configuration bits, which are changed only when a new algorithm instantiation is required.

The paper discusses an implementation of a dual-microphone phase-based speech enhancement technique. By using the phases of the incoming sound signals, we mask frequencies with low signal-to-noise ratio (SNR) between the two microphones. Phase-based filtering can achieve high SNR gains with just two microphones, making it ideal for hand-held devices. However, these devices have a limited battery life and lack the processing power needed for a software based implementation. The paper presents a field programmable gate array (FPGA) implementation that was designed specifically for low-power operation. The FPGA based implementation is compared, with respect to processing capabilities and power utilization, with an off-the-shelf low-power digital signal processor (DSP) implementation.

This paper presents a single FPGA implementation of a real-time sound localization system using two microphones. The implementation, utilizing a cross-correlation technique based on a modified version of the phase transform, successfully localizes sound sources in noisy environments with as low an SNR as 10 dB. Using the same algorithm and similar hardware architecture, it is shown that up to 5 parallel systems (using 10 microphones), all real-time, can be implemented on a single FPGA while only utilizing an estimated 77mW-108mW per microphone.

This paper presents a single FPGA implementation of a real-time sound localization system using two microphones. The implementation, utilizing a cross-correlation technique based on a modified version of the phase transform, successfully localizes sound sources in noisy environments with as low an SNR as 10 dB. Using the same algorithm and similar hardware architecture, it is shown that up to 5 parallel systems (using 10 microphones), all real-time, can be implemented on a single FPGA while only utilizing an estimated 77 mW-108 mW per microphone.

This paper surveys circuit innovations in ferroelectric memories at three circuit levels: memory cell, sensing and architecture. A ferroelectric memory cell consists of at least one ferroelectric capacitor, where binary data are stored, and one or two transistors that either allow access to the capacitor or amplify its contents for a read operation. Once a cell is accessed for a read operation, its data are presented in the form of an analog signal to a sense amplifier, where it is compared against a reference voltage to determine its logic level. The circuit techniques used to generate the reference voltage must be robust to semiconductor processing variations across the chip and the device imperfections of ferroelectric capacitors. We review six methods of generating a reference voltage, two being presented for the first time in this paper. These methods are discussed and evaluated in terms of their accuracy, area overhead and sensing complexity. Ferroelectric memories share architectural features such as addressing schemes and input/output circuitry with other types of random-access memories such as dynamic random-access memories. However, they have distinct features with respect to accessing the stored data, sensing, and overall circuit topology. We review nine different architectures for ferroelectric memories and discuss them in terms of speed, density and power consumption.