This paper focuses on obtaining the optimal communication topology in the smart grid architecture, i.e., what is the optimal communication setup of smart meters in a smart building. The fact that smart meters also consume energy, more often than not, gets ignored by researchers and engineers. In this paper, we will show that smart meter networks can consume significantly less energy with optimal scheduling. Numerical results show that the overall energy consumption can be reduced by implementing the optimal communication architecture and transmission rate setup, rather than implementing a straightforward communication architecture with uniform channel bandwidth.

We propose three novel mathematical optimization formulations that solve the same two-type heterogeneous multiprocessor scheduling problem for a real-time taskset with hard constraints. Our formulations are based on a global scheduling scheme and a fluid model. The first formulation is a mixed-integer nonlinear program, since the scheduling problem is intuitively considered as an assignment problem. However, by changing the scheduling problem to first determine a task workload partition and then to find the execution order of all tasks, the computation time can be significantly reduced. Specifically, the workload partitioning problem can be formulated as a continuous nonlinear program for a system with continuous operating frequency, and as a continuous linear program for a practical system with a discrete speed level set. The latter problem can therefore be solved by an interior point method to any accuracy in polynomial time. The task ordering problem can be solved by an algorithm with a complexity that is linear in the total number of tasks. The work is evaluated against existing global energy/feasibility optimal workload allocation formulations. The results illustrate that our algorithms are both feasibility optimal and energy optimal for both implicit and constrained deadline tasksets. Specifically, our algorithm can achieve up to 40% energy saving for some simulated tasksets with constrained deadlines. The benefit of our formulation compared with existing work is that our algorithms can solve a more general class of scheduling problems due to incorporating a scheduling dynamic model in the formulations and allowing for a time-varying speed profile.

Many numerical optimisation problems rely on fast algorithms for solving sparse triangular systems of linear equations (STLs). To accelerate the solution of such equations, two types of approaches have been used: on GPUs, concurrency has been prioritised to the disadvantage of data locality, while on multi-core CPUs, data locality has been prioritised to the disadvantage of concurrency. In this paper, we discuss the interaction between data locality and concurrency in the solution of STLs on GPUs, and we present a new algorithm that balances both. We demonstrate empirically that, subject to there being enough concurrency available in the input matrix, our algorithm outperforms Nvidia's concurrency-prioritising CUSPARSE algorithm for GPUs. Experimental results show a maximum speedup of 5.8-fold. Our solution algorithm, which we have implemented in OpenCL, requires a pre-processing phase that partitions the graph associated with the input matrix into sub-graphs, whose data can be stored in low-latency local memories. This preliminary analysis phase is expensive, but because it depends only on the input matrix, its cost can be amortised when solving for many different right-hand sides.

We consider the problem of enabling fixed-point implementation of linear algebra kernels on low-cost embedded systems, as well as motivating more efficient computational architectures for scientific applications. Fixed-point arithmetic presents additional design challenges compared to floating-point arithmetic, such as having to bound peak values of variables and control their dynamic ranges. Algorithms for solving linear equations or finding eigenvalues are typically nonlinear and iterative, making solving these design challenges a nontrivial task. For these types of algorithms, the bounding problem cannot be automated by current tools. We focus on the Lanczos iteration, the heart of well-known methods such as conjugate gradient and minimum residual. We show how one can modify the algorithm with a low-complexity scaling procedure to allow us to apply standard linear algebra to derive tight analytical bounds on all variables of the process, regardless of the properties of the original matrix. It is shown that the numerical behavior of fixed-point implementations of the modified problem can be chosen to be at least as good as a floating-point implementation, if necessary. The approach is evaluated on field-programmable gate array (FPGA) platforms, highlighting orders of magnitude potential performance and efficiency improvements by moving form floating-point to fixed-point computation.

We consider the problem of enabling fixed-point implementations of linear algebra kernels to match the strengths of the field-programmable gate array (FPGA). Algorithms for solving linear equations, finding eigen values or finding singular values are typically nonlinear and recursive making the problem of establishing analytical bounds on variable dynamic range non-trivial. Current approaches fail to provide tight bounds for this type of algorithms. We use as a case study one of the most important kernels in scientific computing, the Lanczos iteration, which lies at the heart of well known methods such as conjugate gradient and minimum residual, and we show how we can modify the algorithm to allow us to apply standard linear algebra analysis to prove tight analytical bounds on all variables of the process, regardless of the properties of the original matrix. It is shown that the numerical behaviour of fixed-point implementations of the modified problem can be chosen to be at least as good as a double precision floating point implementation. Using this approach it is possible to get sustained FPGA performance very close to the peak general-purpose graphics processing unit (GPGPU) performance in FPGAs of comparable size when solving a single problem. If there are several independent problems to solve simultaneously it is possible to exceed the peak floating-point performance of a GPGPU, obtaining approximately 1, 2 or 4 TFLOPs for error tolerances of 10-7, 10-5and 10-3, respectively, in a large Virtex 7 FPGA.

Model predictive control (MPC) is an advanced industrial control technique that relies on the solution of a quadratic programming (QP) problem at every sampling instant to determine the input action required to control the current and future behaviour of a physical system. Its ability in handling large multiple input multiple output (MIMO) systems with physical constraints has led to very successful applications in slow processes, where there is sufficient time for solving the optimization problem between sampling instants. The application of MPC to faster systems, which adds the requirement of greater sampling frequencies, relies on new ways of finding faster solutions to QP problems. Field-programmable gate arrays (FPGAs) are specially well suited for this application due to the large amount of computation for a small amount of I/O. In addition, unlike a software implementation, an FPGA can provide the precise timing guarantees required for interfacing the controller to the physical system. We present a high-throughput floating-point FPGA implementation that exploits the parallelism inherent in interior-point optimization methods. It is shown that by considering that the QPs come from a control formulation, it is possible to make heavy use of the sparsity in the problem to save computations and reduce memory requirements by 75%. The implementation yields a 6.5x improvement in latency and a 51x improvement in throughput for large problems over a software implementation running on a general purpose microprocessor.

Automatic control, the process of measuring, computing, and applying an input to control the behaviour of a physical system, is ubiquitous in engineering and industry. Model predictive control (MPC) is an advanced control technology that has been very successful in the chemical process industries due to its ability to handle large multiple input multiple output (MIMO) systems with physical constraints. It has recently been proposed to be applied to higher bandwidth systems, which add the requirement of greater sampling frequencies. The main hurdle is the need to solve a computationally intensive quadratic programming (QP) problem in real-time. In this paper we address the need for acceleration by proposing a highly efficient floating-point field-programmable gate array (FPGA) implementation that exploits the parallelism opportunities offered by interior-point optimization methods. The approach yields a 5x improvement in latency and a 40x improvement in throughput for large problems over a software implementation. This work builds on a previous FPGA implementation of an iterative linear solver, an operation at the heart of the interior-point method.

In this paper we exploit FPGA flexibility in the context of accelerating the solution of many small systems of linear equations, a problem central to model predictive control (MPC). The main observation exploited by this work is the distinction between accuracy (meaning the degree of correctness of a final computational result) and precision (meaning the degree of correctness of each atomic computation). Using iterative methods for solving linear systems, one can obtain improved accuracy either by running more iterations or by using more precise internal computations, unlike direct methods, where accuracy is only a function of operation precision. Thus, in iterative methods, for a given accuracy requirement we may conduct fewer iterations in a higher precision, or more in a lower precision. We argue that this suits FPGA architectures ideally, as low precision operations result in greater parallelism for any fixed area constraint. We show that we may therefore optimize the performance by balancing iteration count and operation precision, resulting in a several-fold speed improvement over a double-precision implementation, but with the same final result accuracy. Exploring this trade-off it is possible to provide a speed-up of 26x on average, 14x in the worst case and 36x in the best, compared to a high-end CPU running at 3.0 GHz. This has the potential to allow modern high-performance control techniques to be used in novel settings such as aircraft and diesel engines. Is the distinction between accuracy (meaning the degree of correctness of a final computational result) and precision(meaning the degree of correctness of each atomic computation). Using iterative methods for solving linear systems,one can obtain improved accuracy either by running more iterations or by using more precise internal computations, unlike direct methods, where accuracy is only a function of operation precision. Thus, in iterative methods, for a given accuracy requirement we may conduct fewer iterations in a higher precision, or more in a lower precision. We argue that this suits FPGA architectures ideally, as low precision operations result in greater parallelism for any fixed area constraint. We show that we may therefore optimize the performance by balancing iteration count and operation precision,resulting in a several-fold speed improvement over a double-precision implementation, but with the same final result accuracy. Exploring this trade-off it is possible to provide a speed-up of 26× on average, 14× in the worst case and 36× in the best, compared to a high-end CPU running at 3.0 GHz. This has the potential to allow modern high-performance control techniques to be used in novel settings such as aircraft and diesel engines.

Field programmable gate arrays (FPGAs) have gradually been increasing their capacities and started to incorporate optimized coarse-grained modules such as BlockRAMs, multipliers, and even processors. These developments have extended their field of applications and one field that has been gaining significant interest is the acceleration of floating-point scientific computing. In this field, a recurring subtask is the solution of systems of linear equations. One well studied method that has proven to be very efficient in software and robust at finding such solutions is the conjugate gradient (CG) algorithm. In this paper we present a hardware CG method which takes advantage of the banded structure present in many common problems. With the flexibility provided by FPGAs, this implementation employs wide-parallelization to convert the per iteration computation time for an order n matrix with band width w from Theta(nw) clock cycles for a software implementation to Theta(n) in hardware. It also explores deep-pipelining so that solutions to P problems are produced every Theta(n) cycles opposed to every Theta(Pnw) cycles in software. Results demonstrate that performances up to 32 GFLOPs are achievable on a Virtex5-330T FPGA and a software comparison reports significant speed-ups in relation to high-end CPUs.