Dynamic Many-Objective Optimization Problems (DMaOPs) represent a significant challenge due to their inherent dynamism and the presence of a large number of objectives. In addressing this complexity, this paper proposes a new prediction-based strategy tailored to managing detected changes in such problems, which is one of the first attempts to address the DMaOPs. Our proposed algorithm constructs a Vector Autoregressive (VAR) model within a dimensionality-reduced space. This model effectively captures the mutual relationships among decision variables and enables an accurate prediction of the initial positions for the evolving solutions in dynamic environments. To accelerate the convergence process, the algorithm demonstrates adaptability by responding multiple times to the same detected change. In our empirical study, the performance of the proposed algorithm is evaluated using four selected test problems from various benchmarks. Our proposed approach shows competitive results compared to the other algorithms in most test instances.

Real world problems in various domains demonstrate different characteristics of changes over time. This is why several researchers have been interested in dynamic optimisation for the last two decades. Since changes occur over time in a dynamic optimisation problem, the goal of a related algorithm becomes tracking the changing optima over time. Evolutionary algorithms and various swarm intelligence techniques have been adapted in the literature to solve dynamic optimisation problems. The Fireworks Algorithm (FWA) is a recently proposed swarm intelligence algorithm for global optimisation of complex static functions that simulates the explosion process of fireworks. Although a set of improvements over the conventional FWA are presented in the literature for the static optimisation problems, the most evident extension is the Enhanced Fireworks Algorithm (EFWA). In this paper, cost effective extensions of the EFWA are proposed for solving dynamic optimisation problems in continuous space. The performance evaluation of our EFWA-based algorithms is validated with the Moving Peaks Benchmark. Empirical studies on different benchmark instances clearly show the applicability of our extensions. Our EFWA-based extensions outperform the related work in terms of both quality of solution and computational cost for a large set of test instances of the benchmark.

Task scheduling on fog environments surges new challenges compared to scheduling on conventional cloud computing. Various levels of heterogeneity and dynamism cause task scheduling problem is more challenging for fog computing. In this study, we present a multiobjective task scheduling model with a total of five objectives and propose a multiobjective multirank (MOMRank) scheduling algorithm for fog computing. The performance of the proposed strategy is assessed with well-known multiobjective metaheuristics [the nondominated sorting genetic algorithm II (NSGA-II) and the Strength Pareto Evolutionary Algorithm 2 (SPEA2)] and a widely used algorithm from the literature, the multiobjective heterogeneous earliest finish time (MOHEFT) algorithm using three common multiobjective metrics. Additionally, we incorporate two task clustering mechanisms to the algorithms in order to improve data transmissions on interconnection networks. Results of empirical evaluations given in performance profiles over all problem instances validate significance of both our algorithm and the integrated extensions for diminishing data transfer costs.

In this paper, we propose an enhanced feature selection algorithm able to cope with feature drift problem that may occur in data streams, where the set of relevant features change over time. We utilize a dynamic multi-objective evolutionary algorithm to continuously search for the updated set of relevant features after the occurrence of every change in the environment. An artificial neural network is employed to classify the new instances based on the up-to-date obtained set of relevant features efficiently. Our algorithm exploits a detection mechanism for the severity of changes to estimate the severity level of occurred changes and adaptively replies to these changes by introducing diversity to algorithm solutions. Furthermore, a fixed-size memory is used to store the good solutions and reuse them after each change to accelerate the convergence and searching process of the algorithm. The experimental results using three datasets and different environmental parameters show that the combination of our improved feature selection algorithm with the artificial neural network outperforms related work.

Summary The system reliability becomes a critical concern in modern architectures with the scale down of circuits. To deal with soft errors, the replication of system resources has been used at both hardware and software levels. Since the redundancy causes performance degradation, it is required to explore partial redundancy techniques that replicate the most vulnerable parts of the code. The redundancy level of user applications depends on user preferences and may be different for the users with different requirements. In this work, we propose a user‐assisted reliability assessment tool based on critical thread analysis for redundancy in parallel architectures. Our analysis evaluates the application threads of a parallel program by considering their criticality in the execution and selects the most critical thread or threads to be replicated. Moreover, we extend our analysis by exploring critical regions of individual threads and execute redundantly only those regions to reduce redundancy overhead. Our experimental evaluation indicates that the replication of the most critical thread improves the system reliability more (up to 10% for blackscholes application) than the replication of any other thread. The partial thread replication based on critical region analysis also reduces the vulnerability of the system by considering a fine‐grained approach.

Detecting the points in time where a change occurs in the landscape can have an important role for a number of evolutionary dynamic optimization techniques presented in the literature. The two common ways for change detection are the population-based scheme and the sensor-based scheme. The former one requires statistical hypothesis testing, which periodically checks whether two consecutive populations are derived from different distributions or not. On the other hand, the latter one utilizes re-evaluation of a set of sensors, throughout the search process. The population-based change detectors may cause false positives and the sensor-based detectors may lack of distinction between changes and noise in fitness functions. In this paper, we propose a hybrid technique to overcome the limitations of the change detection schemes and validate it by using Moving Peaks Benchmark (MPB).

The small feature sizes in current Networks-on-chip (NoCs) have increased the importance of reliability. However, existing fault tolerance schemes incur costs in terms of performance and power consumption which can be over-burdening. In order to tackle the reliability problem in NoCs while minimizing the performance and energy costs, a compiler-enhanced reliability scheme is introduced in this paper which assigns extra protection only to data transmissions in NoC which are considered critical. The experimental study validates that our scheme yields almost equal level of fault tolerance for critical data transmissions with the scheme that protects all packet transmissions indiscriminately. Our scheme is also shown to have better performance by approximately 7% than the conservative scheme for the tested criticality annotation.

Dynamic optimization problems have been captivating the interest of the researchers, since most real world problems in different domains have various characteristics of dynamism. Different evolutionary and swarm intelligence techniques are proposed to solve dynamic optimization problems. Fireworks Algorithm (FWA) is a recently proposed swarm intelligence algorithm for global optimization of complex functions. This paper proposes two extensions on the FWA, called the EFWA_D1 and the EFWA_D2 algorithms, in order to adapt on dynamic optimization problems. We validate performance of the EFWA_D1 and the EFWA_D2 with the Moving Peaks Benchmark (MPB), a well-known synthetic dynamic optimization problem that generates and updates a multidimensional landscape consisting of several peaks. Experimental evaluation on various instances of MPB validates the applicability of our extensions on the FWA for a dynamic optimization problem.

Collision checking takes most of the time in sampling based path planning algorithms. When the scene gets crowded, more samples are needed and the probability decreases to find a collision free sample. Broad phase algorithms are designed to eliminate obviously collision free samples, so narrow phase algorithms can concentrate on fewer samples suspected to be in collision. In this study, we compare the performance of two broad phase algorithms implemented on both CPU and GPU. A novel technique is proposed to provide load balancing and efficient cache utilization on Bounding Sphere Collision Detection algorithm. Furthermore, Thrust library is extensively utilized on Sweep and Prune (SAP) algorithm. Our experimental results indicate speedups up to 103 times faster for GPU-based SAP algorithm and 134 times faster for GPU-based Bounding Sphere algorithm, compared to CPU implementations. This may allow using sampling based path planning algorithms for scenes with many robots.

With the scale down of transistor sizes and higher frequencies with low power modes in modern architectures, the chip components become more susceptible to transient errors. Concurrently, multicore machines are replacing traditional single-core machines in most application domains. Thread Vulnerability Factor (TVF) is a metric to evaluate relative soft error vulnerability of multithreaded applications running on multicore architectures. It makes possible vulnerability analysis of parallel programs by providing comparisons between them. In this work, we design a simulation-based fault-injection framework to evaluate soft error vulnerability of parallel applications and perform a validation study to evaluate parallel program vulnerability. The results of the simulation-based fault injection framework is compared with the results based on TVF analysis. Our results demonstrate that TVF provides an efficient vulnerability analysis by having the same ordering and similar vulnerability rates with fault-injection results for a set of multithreaded applications.

Modern architectures become more susceptible to transient errors with the scale down of circuits. This makes reliability an increasingly critical concern in computer systems. In general, there is a tradeoff between system reliability and performance of multithreaded applications running on multicore architectures. In this paper, we conduct a performance-reliability analysis for different parallel versions of three data-intensive applications including FFT, Jacobi Kernel, and Water Simulation. We measure the performance of these programs by counting execution clock cycles, while the system reliability is measured by Thread Vulnerability Factor (TVF) which is a recently-proposed metric. TVF measures the vulnerability of a thread to hardware faults at a high level. We carry out experiments by executing parallel implementations on multicore architectures and collect data about the performance and vulnerability. Our experimental evaluation indicates that the choice is clear for FFT application and Jacobi Kernel. Transpose algorithm for FFT application results in less than 5% performance loss while the vulnerability increases by 20% compared to binary-exchange algorithm. Unrolled Jacobi code reduces execution time up to 50% with no significant change on vulnerability values. However, the tradeoff is more interesting for Water Simulation where nsquared version reduces the vulnerability values significantly by worsening the performance with similar rates compared to faster but more vulnerable spatial version.

Locality analysis of an application helps us extract data access patterns and predict runtime cache behavior. In this paper, we propose a locality-aware dynamic mapping algorithm for multithreaded applications, which assigns computations with similar data access patterns to same cores. We collect the amounts of shared and distinct data used by all computations, called chunks and calculate sharing among those chunks. Then, chunks with the similar data access patterns are grouped into bins, which are subsequently assigned to threads for improving cache reuse and program performance. Our algorithm is illustrated with sparse matrix-vector multiply (SpMV), which is one of the most widely used kernel in engineering and scientific computing and suffers from irregular and indirect memory access patterns. Five inputs with different shapes and characteristics are considered for testing the performance of our algorithm. Based on the results of experimental study, our algorithm outperforms Linux scheduler with an average of 12.5% performance improvement for various scenarios considered.

Continuously reducing transistor sizes and aggressive low power operating modes employed by modern architectures tend to increase transient error rates. Concurrently, multicore machines are dominating the architectural spectrum in various application domains. These two trends require a fresh look at resiliency of multithreaded applications against transient errors from a software perspective. In this paper, we propose and evaluate a new metric called the Thread Vulnerability Factor (TVF). A distinguishing characteristic of TVF is that its calculation for a given thread (which is typically one of the threads of a multithreaded application) does not depend on its code alone, but also on the codes of the threads that share data with that thread. As a result, we decompose TVF of a thread into two complementary parts: local and remote. While the former captures the TVF induced by the code of the target thread, the latter represents the vulnerability impact of the threads that interact with the target thread. We quantify the local and remote TVF values for three architectural components (register file, ALUs, and caches) using a set of four multithreaded applications. Our experimental evaluation shows that TVF values tend to increase as the number of cores increases which means the system becomes more vulnerable as the core count rises. We also discuss how TVF values and execution cycles together can be used to explore performance-reliability tradeoffs in multicores at a source code level.

Positioning multiple sensors for acquisition of a given environment is one of the fundamental research areas in various fields, such as military scouting, computer vision, and robotics. In this paper, we propose a new model for the problem of sensor deployment. Deploying and configuring a set of given sensors on a synthetically generated 3-D terrain have multiple objectives on conflicting attributes: maximizing the visibility of the given terrain, maximizing the stealth of the sensors, and minimizing the cost of the sensors used. Since they are utility-independent, these complementary and conflicting objectives are modeled by a multiplicative total utility function, based on multiattribute utility theory. The total utility function proposed in this paper can also be adapted for various military scouting missions with different characteristics.

In this paper, we explore using a hybrid evolutionary algorithm (HEA) for deploying and configuring a set of given sensors on a synthetically generated 3-D terrain. In our evolutionary-algorithm (EA) based solution, various methods are considered in order to incorporate specialized operators for hybridization, including problem-specific heuristics for initial population generation, intelligent variation operators (contribution-based-crossover operator and proximity-based-crossover operator), which comprise problem-specific knowledge, and a local-search phase. The experimental study validates finding the optimal balance among visibility-oriented, stealth-oriented, and cost-oriented objectives. The obtained results also indicate the effectiveness and robustness of our HEA-based solution for various practical scenarios with different objectives.

In this paper, a novel hybrid method for path planning problem of multiple mobile sensors on a 3-D terrain is proposed. Our method proceeds in two phases: the global path-planning phase, and the local path planning phase. The first phase constructs a connectivity graph generated by a probabilistic roadmap (PRM) method and selects the control points of sensors' paths from the set of nodes generated by the PRM method. In the local path-planning phase, a hybrid evolutionary algorithm is proposed to determine the intermediate points, which are between control points of sensors' paths in order to complete the paths. The local-path planner considers the accessibility of control points, smoothness of each path, visibility of terrain covered by mobile sensors and the total cost of all paths (i.e. the total length of all paths). The experimental study points out the effectiveness of our framework under various terrain and sensor characteristics.

The generalized assignment problem is a well-known NP-complete problem whose objective is to find a minimum cost assignment of a set of jobs to a set of agents by considering the resource constraints. Dynamic instances of the generalized assignment problem can be created by changing the resource consumptions, capacity constraints and costs of jobs. Memory-based approaches are among a set of evolutionary techniques that are proposed for dynamic optimization problems. On the other hand, a hyper-heuristic is a high-level method which decides an appropriate low-level heuristic to apply on a given problem without using problem-specific information. In this paper, we present the applicability of hyper-heuristic methods for the dynamic generalized assignment problem. Our technique extends a memory-based approach by integrating it with various hyper-heuristics for the search population. Experimental evaluation performed on various benchmark instances indicates that our hyper-heuristic based approaches outperform the memory-based technique with respect to quality of solutions.

In this paper, we propose a framework for deploying and configuring a set of given sensors in a synthetically generated 3-D terrain with multiple objectives on conflicting attributes: maximizing the visibility of the given terrain, maximizing the stealth of the sensors and minimizing the cost of the sensors used. Because of their utility-independent nature, these complementary and conflicting objectives are represented by a multiplicative total utility function model, based on multi-attribute utility theory. In addition to theoretic foundations, this paper also present a hybrid evolutionary algorithm based technique to solve the sensor placement problem. It includes specialized operators for hybridization, which are problem-specific heuristics for initial population generation, intelligent variation operators which comprise problem specific knowledge, and a local search phase. The experimental study validates finding the optimal balance among the visibility, the stealth and the cost related objectives.

Military missions are turning to more complicated and advanced automation technology for maximum endurance and efficiency as well as the minimum vital risks. The path planners which generate collision-free and optimized paths are needed to give autonomous operation capability to the Unmanned Aerial Vehicles (UAVs). This paper presents an off-line path planner for UAVs. The path planner is based on Evolutionary Algorithms (EA), in order to calculate a curved path line with desired attributes in a 3-D terrain. The flight path is represented by parameterized B-Spline curves by considering four objectives: the shortest path to the destination, the feasible path without terrain collision, the path with the desired minimum and maximum distance to the terrain, and the path which provides UAV to maneuver with an angle greater than the minimum radius of curvature. The generated path is represented with the coordinates of its control points being the genes of the chromosome of the EA. The proposed method was tested in several 3-D terrains, which are generated with various terrain generator methods that differ with respect to levels of smoothness of the terrain.

Embedded systems are unique in the challenges they present to application programmers, such as power and memory space constraints. These characteristics make it imperative to design customized compiler passes. One of the important factors that shape runtime performance of a given embedded code is the register allocation phase of compilation. It is crucial to provide aggressive and sophisticated register allocators for embedded devices, where the excessive compilation time can be tolerated due to high demand on code quality. Failing to do a good job on allocating variables to registers (i.e., determining the set of variables to be stored in the limited number of registers) can have serious power, performance, and code size consequences. This paper explores the possibility of employing a hybrid evolutionary algorithm for register allocation problem in embedded systems. The proposed solution combines genetic algorithms with a local search technique. The algorithm exploits a novel, highly specialized crossover operator that takes into account domain-specific information. The results from our implementation based on synthetic benchmarks and routines that are extracted from well-known benchmark suites clearly show that the proposed approach is very successful in allocating registers to variables. In addition, our experimental evaluation also indicates that it outperforms a state-of-the-art register allocation heuristic based on graph coloring for most of the cases experimented.

Genetic Algorithms have widely been used for solving optimization problems in stationary environments. In recent years, there has been a growing interest for investigating and improving the performance of these algorithms in dynamic environments where the fitness landscape changes. In this study, we present an extensive comparison of several algorithms with different characteristics on a common platform by using the moving peaks benchmark and by varying problem parameters.

Positioning multiple sensors for acquisition of a a given environment is one of the fundamental research areas in various fields, such as military scouting, computer vision and robotics. In this paper, we propose a framework for locating an configuring a set of given sensors in a synthetically generated terrain with multiple objectives of maximization of visibility of the terrain, maximization of stealth of the sensors and minimization of cost of the sensors. Because of their utility-independent nature, these complementary and conflicting objectives are represented by a multiplicative global utility function based on multi-attribute utility theory. In addition to theoretic foundations, we also present how a Genetic Algorithms can be applied to maximize the global utility function for a given terrain.

Task scheduling for parallel and distributed systems is an NP-complete problem, which is well documented and studied in the literature. A large set of proposed heuristics for this problem mainly target to minimize the completion time or the schedule length of the output schedule for a given task graph. An additional objective, which is not much studied, is the minimization of number of processors allocated for the schedule. These two objectives are both conflicting and complementary, where the former is on the time domain targeting to improve task utilization and the latter is on the resource domain targeting to improve processor utilization. In this paper, we unify these two objectives with a weighting scheme that allows to personalize the importance of the objectives. In this paper, we present a new genetic search framework for task scheduling problem by considering the new objective. The performance of our genetic algorithm is compared with the scheduling algorithms in the literature that consider the heterogeneous processors. The results of the synthetic benchmarks and task graphs that are extracted from well-known applications clearly show that our genetic algorithm-based framework outperforms the related work with respect to normalized cost values, for various task graph characteristics.

Efficient application scheduling is critical for achieving high performance in heterogeneous computing environments. The application scheduling problem has been shown to be NP-complete in general cases as well as in several restricted cases. Because of its key importance, this problem has been extensively studied and various algorithms have been proposed in the literature which are mainly for systems with homogeneous processors. Although there are a few algorithms in the literature for heterogeneous processors, they usually require significantly high scheduling costs and they may not deliver good quality schedules with lower costs. In this paper, we present two novel scheduling algorithms for a bounded number of heterogeneous processors with an objective to simultaneously meet high performance and fast scheduling time, which are called the Heterogeneous Earliest-Finish-Time (HEFT) algorithm and the Critical-Path-on-a-Processor (CPOP) algorithm. The HEFT algorithm selects the task with the highest upward rank value at each step and assigns the selected task to the processor, which minimizes its earliest finish time with an insertion-based approach. On the other hand, the CPOP algorithm uses the summation of upward and downward rank values for prioritizing tasks. Another difference is in the processor selection phase, which schedules the critical tasks onto the processor that minimizes the total execution time of the critical tasks. In order to provide a robust and unbiased comparison with the related work, a parametric graph generator was designed to generate weighted directed acyclic graphs with various characteristics. The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithms significantly surpass previous approaches in terms of both quality and cost of schedules, which are mainly presented with schedule length ratio, speedup, frequency of best results, and average scheduling time metrics.

The requirements of grand challenge problems and the deployment of gigabit networks makes the network computing framework an attractive and cost effective computing environment with which to interconnect geographically distributed processing and storage resources. Our project, Virtual Distributed Computing Environment (VDCE), provides a problem-solving environment for high-performance distributed computing over wide area networks. VDCE delivers well-defined library functions that relieve end-users of tedious task implementations and also support reusability. In this paper we present the conceptual design of VDCE software architecture, which is defined in three modules: (a) the Application Editor, a user-friendly application development environment that generates the Application Flow Graph (AFG) of an application; (b) the Application Scheduler, which provides an efficient task-to-resource mapping of AFG; and (c) the VDCE Runtime System, which is responsible for running and managing application execution and monitoring the VDCE resources.

Current advances in high-speed networks and WWW technologies have made network computing a cost-effective, high-performance computing alternative. New software tools are being developed to utilize efficiently the network computing environment. Our project, called Virtual Distributed Computing Environment (VDCE), is a high-performance computing environment that allows users to write and evaluate networked applications for different hardware and software configurations using a web interface. In this paper we present the software architecture of VDCE by emphasizing application development and specification, scheduling, and execution/runtime aspects.