Temperature management for heterogeneous multi-core FPGAs using adaptive evolutionary multi-objective approaches

Heterogeneous multi-core FPGAs contain different types of cores, which can improve efficiency when used with an effective online task scheduler. However, it is not easy to find the right cores for tasks when there are multiple objectives or dozens of cores. Inappropriate scheduling may cause hot spots which decrease the reliability of the chip. Given that, our research builds a simulating platform to evaluate all kinds of scheduling algorithms on a variety of architectures. On this platform, we provide an online scheduler which uses multi-objective evolutionary algorithm (EA). Comparing the EA and current algorithms such as Predictive Dynamic Thermal Management (PDTM) and Adaptive Temperature Threshold Dynamic Thermal Management (ATDTM), we find some drawbacks in previous work. First, current algorithms are overly dependent on manually set constant parameters. Second, those algorithms neglect optimization for heterogeneous architectures. Third, they use single-objective methods, or use linear weighting method to convert a multi-objective optimization into a single-objective optimization. Unlike other algorithms, the EA is adaptive and does not require resetting parameters when workloads switch from one to another. EAs also improve performance when used on heterogeneous architecture. A efficient Pareto front can be obtained with EAs for the purpose of multiple objectives.

An integrated scheduling problem of PCB components on sequential pick-and-place machines:mathematical models and heuristic solutions

This paper formulates several mathematical models for determining the optimal sequence of component placements and assignment of component types to feeders simultaneously or the integrated scheduling problem for a type of surface mount technology placement machines, called the sequential pick-andplace (PAP) machine. A PAP machine has multiple stationary feeders storing components, a stationary working table holding a printed circuit board (PCB), and a movable placement head to pick up components from feeders and place them to a board. The objective of integrated problem is to minimize the total distance traveled by the placement head. Two integer nonlinear programming models are formulated first. Then, each of them is equivalently converted into an integer linear type. The models for the integrated problem are verified by two commercial packages. In addition, a hybrid genetic algorithm previously developed by the authors is adopted to solve the models. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total traveling distance.

Integrated component scheduling models for chip shooter machines

This paper focuses on minimizing printed circuit board (PCB) assembly time for a chipshootermachine, which has a movable feeder carrier holding components, a movable X–Y table carrying a PCB, and a rotary turret with multiple assembly heads. The assembly time of the machine depends on two inter-related optimization problems: the component sequencing problem and the feeder arrangement problem. Nevertheless, they were often regarded as two individual problems and solved separately. This paper proposes two complete mathematical models for the integrated problem of the machine. The models are verified by two commercial packages. Finally, a hybrid genetic algorithm previously developed by the authors is presented to solve the model. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total assembly time.

Message-passing algorithms for optimal utilization of cognitive radio networks

Cognitive Radio has been proposed as a key technology to significantly improve spectrum usage in wireless networks by enabling unlicensed users to access unused resource. We present new algorithms that are needed for the implementation of opportunistic scheduling policies that maximize the throughput utilization of resources by secondary users, under maximum interference constraints imposed by existing primary users. Our approach is based on the Belief Propagation (BP) algorithm, which is advantageous due to its simplicity and potential for distributed implementation. We examine convergence properties and evaluate the performance of the proposed BP algorithms via simulations and demonstrate that the results compare favorably with a benchmark greedy strategy. © 2013 IEEE.

Improving scheduling techniques in heterogeneous systems with dynamic, on-line optimisations

Computational performance increasingly depends on parallelism, and many systems rely on heterogeneous resources such as GPUs and FPGAs to accelerate computationally intensive applications. However, implementations for such heterogeneous systems are often hand-crafted and optimised to one computation scenario, and it can be challenging to maintain high performance when application parameters change. In this paper, we demonstrate that machine learning can help to dynamically choose parameters for task scheduling and load-balancing based on changing characteristics of the incoming workload. We use a financial option pricing application as a case study. We propose a simulation of processing financial tasks on a heterogeneous system with GPUs and FPGAs, and show how dynamic, on-line optimisations could improve such a system. We compare on-line and batch processing algorithms, and we also consider cases with no dynamic optimisations.

Recent research trend of economic-lot scheduling problems

Purpose - This research note aims to present a summary of research concerning economic-lot scheduling problem (ELSP). Design/methodology/approach - The paper's approach is to review over 100 selected studies published in the last 15 years (1997-2012), which are then grouped under different research themes. Findings - Five research themes are identified and insights for future studies are reported at the end of this paper. Research limitations/implications - The motivation of preparing this research note is to summarize key research studies in this field since 1997, when the ELSP problems have been verified as NP-hard. Originality/value - ELSP is an important scheduling problem that has been studied since the 1950s. Because of its complexity in delivering a feasible analytical closed form solution, many studies in the last two decades employed heuristic algorithms in order to come up with good and acceptable solutions. As a consequence, the solution approaches are quite diversified. The major contribution of this paper is to provide researchers who are interested in this area with a quick reference guide on the reviewed studies. © Emerald Group Publishing Limited.

Matching theory based travel plan aware charging algorithms in V2G smart grid networks

The frequency, time and places of charging have large impact on the Quality of Experience (QoE) of EV drivers. It is critical to design effective EV charging scheduling system to improve the QoE of EV drivers. In order to improve EV charging QoE and utilization of CSs, we develop an innovative travel plan aware charging scheduling scheme for moving EVs to be charged at Charging Stations (CS). In the design of the proposed charging scheduling scheme for moving EVs, the travel routes of EVs and the utility of CSs are taken into consideration. The assignment of EVs to CSs is modeled as a two-sided many-to-one matching game with the objective of maximizing the system utility which reflects the satisfactory degrees of EVs and the profits of CSs. A Stable Matching Algorithm (SMA) is proposed to seek stable matching between charging EVs and CSs. Furthermore, an improved Learning based On-LiNe scheduling Algorithm (LONA) is proposed to be executed by each CS in a distributed manner. The performance gain of the average system utility by the SMA is up to 38.2% comparing to the Random Charging Scheduling (RCS) algorithm, and 4.67% comparing to Only utility of Electric Vehicle Concerned (OEVC) scheme. The effectiveness of the proposed SMA and LONA is also demonstrated by simulations in terms of the satisfactory ratio of charging EVs and the the convergence speed of iteration.