MASE-BDI: agent-based simulator for environmental land change with efficient and parallel auto-tuning

This paper presents an agent-based simulator for environmental land change that includes efficient and parallel auto-tuning. This simulator extends the Multi-Agent System for Environmental simulation (MASE) by introducing rationality to agents using a mentalistic approach—the Belief-Desire-Intention (BDI) model—and is thus named MASE-BDI. Because the manual tuning of simulation parameters is an error-prone, labour and computing intensive task, an auto-tuning approach with efficient multi-objective optimization algorithms is also introduced. Further, parallelization techniques are employed to speed up the auto-tuning process by deploying it in parallel systems. The MASE-BDI is compared to the MASE using the Brazilian Cerrado biome case. The MASE-BDI reduces the simulation execution times by at least 82 × and slightly improves the simulation quality. The auto-tuning algorithms, by evaluating less than 0.00115 % of a search space with 6 million parameter combinations, are able to quickly tune the simulation model, regardless of the objective used. Moreover, the experimental results show that executing the tuning in parallel leads to speedups of approximately 11 × compared to sequential execution in a hardware setting with 16-CPU cores.     

Profiling techniques for communication in fine‐grained parallel languages

Fine tuning the performance of large parallel programs is a very difficult task. A profiling tool can provide detailed insight into the utilization and communication of the different processors, which helps identify performance bottlenecks. In this paper we present two profiling techniques for the fine‐grained parallel programming language Split‐C, which provides a simple global address space memory model. One profiler provides a detailed analysis of a program's execution. The other profiler collects cumulative information. As our experience shows, it is quite challenging to profile programs that make use of efficient, low‐overhead communication. We incorporated techniques which minimize profiling effects on the running program, and quantified the profiling overhead. We present several Split‐C applications showing that the profiler is useful in determining performance bottlenecks. Copyright © 1999 John Wiley & Sons, Ltd.     

监督学习模型指导的函数级编译优化参数选择方法研究

基于机器学习的迭代编译方法可以在对新程序进行迭代编译时,有效预测新程序的最佳优化参数组合。现有方法在模型训练过程中存在优化参数组合搜索效率较低、程序特征表示不恰当、预测精度不高的问题。因此,基于机器学习的迭代编译方法是当前迭代编译领域内的一个研究热点,其研究挑战在于学习算法选择、优化参数搜索以及程序特征表示等问题。基于监督学习技术,提出了一种程序优化参数预测方法。该方法首先通过约束多目标粒子群算法对优化参数空间进行搜索,找到样本函数的最佳优化参数;然后,通过动静结合的程序特征表示技术,对函数特征进行抽取;最后,通过由函数特征和优化参数形成的样本构建监督学习模型,对新程序的优化参数进行预测。分别采用k近邻法和softmax回归建立统计模型,实验结果表明,新方法在NPB测试集和大型科学计算程序上实现了较好的预测性能。     

Multi-Path Reasoning in a Database

Rules have been used in a database context for several purposes:deductive database queries, active database triggers, and productionsystem programs. Exploring the search space for non-deterministicrule programs, however, has generally been available only in largemonolithic systems intended for artificial intelligence applications.The goal of this research is to provide multi-path reasoning fornon-deterministic rule programs in a database environment. Themotivation for this work includes the increasing use ofdatabase-style triggers to assist data-intensive applications, e.g.,the human genome project and the Intelligent Integration ofInformation (I ³) Program.A non-deterministic rule program is one where there is more than oneterminal state. Such programs are generally not consideredappropriate for database queries where the focus is on rules programsor techniques that guarantee a unique fixed point. Butnon-deterministic programs are commonly used for various heuristicsearch problems such as the traveling salesperson problem. With anon-deterministic program, it is particularly important to beflexible about the order in which the search space is exploredbecause exhaustive search is generally not feasible. Thecontributions of this research are: the representation of themulti-path search tree within a database and the ability for theproblem solver to control the search process for a non-deterministicrule program.     

Uncertainty‐Aware Exploration of Continuous Parameter Spaces Using Multivariate Prediction

Systems projecting a continuous n‐dimensional parameter space to a continuous m‐dimensional target space play an important role in science and engineering. If evaluating the system is expensive, however, an analysis is often limited to a small number of sample points. The main contribution of this paper is an interactive approach to enable a continuous analysis of a sampled parameter space with respect to multiple target values. We employ methods from statistical learning to predict results in real‐time at any user‐defined point and its neighborhood. In particular, we describe techniques to guide the user to potentially interesting parameter regions, and we visualize the inherent uncertainty of predictions in 2D scatterplots and parallel coordinates. An evaluation describes a real‐world scenario in the application context of car engine design and reports feedback of domain experts. The results indicate that our approach is suitable to accelerate a local sensitivity analysis of multiple target dimensions, and to determine a sufficient local sampling density for interesting parameter regions.     

A systematic review of search-based testing for non-functional system properties

Search-based software testing is the application of metaheuristic search techniques to generate software tests. The test adequacy criterion is transformed into a fitness function and a set of solutions in the search space are evaluated with respect to the fitness function using a metaheuristic search technique. The application of metaheuristic search techniques for testing is promising due to the fact that exhaustive testing is infeasible considering the size and complexity of software under test. Search-based software testing has been applied across the spectrum of test case design methods; this includes white-box (structural), black-box (functional) and grey-box (combination of structural and functional) testing. In addition, metaheuristic search techniques have also been applied to test non-functional properties. The overall objective of undertaking this systematic review is to examine existing work into non-functional search-based software testing (NFSBST). We are interested in types of non-functional testing targeted using metaheuristic search techniques, different fitness functions used in different types of search-based non-functional testing and challenges in the application of these techniques. The systematic review is based on a comprehensive set of 35 articles obtained after a multi-stage selection process and have been published in the time span 1996–2007. The results of the review show that metaheuristic search techniques have been applied for non-functional testing of execution time, quality of service, security, usability and safety. A variety of metaheuristic search techniques are found to be applicable for non-functional testing including simulated annealing, tabu search, genetic algorithms, ant colony methods, grammatical evolution, genetic programming (and its variants including linear genetic programming) and swarm intelligence methods. The review reports on different fitness functions used to guide the search for each of the categories of execution time, safety, usability, quality of service and security; along with a discussion of possible challenges in the application of metaheuristic search techniques.     

On the use of many quality attributes for software refactoring: a many-objective search-based software engineering approach

Search-based software engineering (SBSE) solutions are still not scalable enough to handle high-dimensional objectives space. The majority of existing work treats software engineering problems from a single or bi-objective point of view, where the main goal is to maximize or minimize one or two objectives. However, most software engineering problems are naturally complex in which many conflicting objectives need to be optimized. Software refactoring is one of these problems involving finding a compromise between several quality attributes to improve the quality of the system while preserving the behavior. To this end, we propose a novel representation of the refactoring problem as a many-objective one where every quality attribute to improve is considered as an independent objective to be optimized. In our approach based on the recent NSGA-III algorithm, the refactoring solutions are evaluated using a set of 8 distinct objectives. We evaluated this approach on one industrial project and seven open source systems. We compared our findings to: several other many-objective techniques (IBEA, MOEA/D, GrEA, and DBEA-Eps), an existing multi-objective approach a mono-objective technique and an existing refactoring technique not based on heuristic search. Statistical analysis of our experiments over 31 runs shows the efficiency of our approach.     

调试器对并行程序干扰特性的研究

机群系统中并行程序的执行具有不确定性，这种不确定性给并行程序的调试带来了困难，并行程序的不确定性是由运行环境中的各种干扰因素造成的，该文研究交互式调试行为对调试程序的干扰特性，文中给出了算法可以在调试的过程中实时地报告出本次交互式调试操作是否对调试的程序造成了干扰。     

Performance measurement,visualization and modeling of parallel and distributed programs using the AIMS toolkit

Writing large-scale parallel and distributed scientific applications that make optimum use of the multiprocessor is a challenging problem. Typically, computational resources are underused due to performance failures in the application being executed. Performance-tuning tools are essential for exposing these performance failures and for suggesting ways to improve program performance. In this paper, we first address fundamental issues in building useful performance-tuning tools and then describe our experience with the AIMS toolkit for tuning parallel and distributed programs on a variety of platforms. AIMS supports source-code instrumentation, run-time monitoring, graphical execution profiles, performance indices and automated modeling techniques as ways to expose performance problems of programs. Using several examples representing a broad range of scientific applications, we illustrate AIMS' effectiveness in exposing performance problems in parallel and distributed programs.     

结合模型和迭代编译优化矩阵相乘程序

高性能计算应用程序获得的持续性能与机器峰值性能的差距日益扩大,很大程度上制约着高性能计算的发展。程序变换通过对程序进行适应机器体系结构特征的优化变换,提高程序实际执行性能,是解决该问题的有效途径之一。很多高级程序变换均具有数值参数,为了获得最优性能,需要仔细选择参数的值。传统的编译器使用简单的模型选择这些参数,难以适应日趋复杂的硬件平台和应用程序。迭代编译通过生成不同的程序版本并在实际硬件评估上运行程序,来评估关键优化参数的值并决定能够产生最优性能的值,显著优于静态方法,但巨大的优化开销限制了其应用范围。本文针对矩阵相乘程序提出一种结合性能模型和迭代编译的优化方法,利用基于对机器体系结构和程序的经验知识构造性能模型约束优化空间,并使用遗传算法加速在优化空间中寻找优秀解的过程。实验结果表明,该方法可以较低的开销获得更优的性能优化效果。     

State of the art in parallel search techniques for discreteoptimization problems

Discrete optimization problems arise in a variety of domains, such as VLSI design, transportation, scheduling and management, and design optimization. Very often, these problems are solved using state space search techniques. Due to the high computational requirements and inherent parallel nature of search techniques, there has been a great deal of interest in the development of parallel search methods since the dawn of parallel computing. Significant advances have been made in the use of powerful heuristics and parallel processing to solve large-scale discrete optimization problems. Problem instances that were considered computationally intractable only a few years ago are routinely solved currently on server-class symmetric multiprocessors and small workstation clusters. Parallel game-playing programs are challenging the best human minds at games like chess. In this paper, we describe the state of the art in parallel algorithms used for solving discrete optimization problems. We address heuristic and nonheuristic techniques for searching graphs as well as trees, and speed-up anomalies in parallel search that are caused by the inherent speculative nature of search techniques     

Arranging statements and data of program instances for locality

In memory hierarchies, programs can be speeded up by increasing their degree of locality. One human approach to locality optimization considers several small program instances of a given program, optimizes the instances for locality, and generalizes the structure of the solutions to the program. The paper suggests a semi-automatic locality-optimization method based on this approach. The major contribution is a local search algorithm that automatically optimizes program instances via combined code and data transformations. The algorithm uses a novel objective function that quantifies the intuitive notion of locality. Experimental results indicate that our method compares well with current compiler optimizations.     

ProSy: API-Based Synthesis with Probabilistic Model

Program synthesis is an exciting topic that desires to generate programs satisfying user intent automatically. But in most cases, only small programs for simple or domain-specific tasks can be synthesized. The major obstacle of synthesis lies in the huge search space. A common practice in addressing this problem is using a domain-specific language, while many approaches still wish to synthesize programs in general programming languages. With the rapid growth of reusable libraries, component-based synthesis provides a promising way, such as synthesizing Java programs which are only composed of APIs (application programming interfaces). However, the efficiency of searching for proper solutions for complex tasks is still a challenge. Given an unfamiliar programming task, programmers would search for API usage knowledge from various coding resources to reduce the search space. Considering this, we propose a novel approach named ProSy to synthesize API-based programs in Java. The key novelty is to retrieve related knowledge from Javadoc and Stack Overflow and then construct a probabilistic reachability graph. It assigns higher probabilities to APIs that are more likely to be used in implementing the given task. In the synthesis process, the program sketch with a higher probability will be considered first; thus, the number of explored reachable paths would be decreased. Some extension and optimization strategies are further studied in the paper. We implement our approach and conduct several experiments on it. We compare ProSy with SyPet and other state-of-the-art API-based synthesis approaches. The experimental results show that ProSy reduces the synthesis time of SyPet by up to 80%.

     

Optimization by record dynamics

Large dynamical changes in thermalizing glassy systems are triggered by trajectories crossing record sized barriers, a behavior revealing the presence of a hierarchical structure in configuration space. The observation is here turned into a novel local search optimization algorithm dubbed record dynamics optimization, or RDO. RDO uses the Metropolis rule to accept or reject candidate solutions depending on the value of a parameter akin to the temperature and minimizes the cost function of the problem at hand through cycles where its ‘temperature’ is raised and subsequently decreased in order to expediently generate record high (and low) values of the cost function. Below, RDO is introduced and then tested by searching for the ground state of the Edwards–Anderson spin-glass model, in two and three spatial dimensions. A popular and highly efficient optimization algorithm, parallel tempering (PT), is applied to the same problem as a benchmark. RDO and PT turn out to produce solutions of similar quality for similar numerical effort, but RDO is simpler to program and additionally yields geometrical information on the system’s configuration space which is of interest in many applications. In particular, the effectiveness of RDO strongly indicates the presence of the above mentioned hierarchically organized configuration space, with metastable regions indexed by the cost (or energy) of the transition states connecting them.     

Approximate Program Smoothing Using Mean‐Variance Statistics,with Application to Procedural Shader Bandlimiting

We introduce a general method to approximate the convolution of a program with a Gaussian kernel. This results in the program being smoothed. Our compiler framework models intermediate values in the program as random variables, by using mean and variance statistics. We decompose the input program into atomic parts and relate the statistics of the different parts of the smoothed program. We give several approximate smoothing rules that can be used for the parts of the program. These include an improved variant of Dorn et al. [ DBLW15 ], a novel adaptive Gaussian approximation, Monte Carlo sampling, and compactly supported kernels. Our adaptive Gaussian approximation handles multivariate Gaussian distributed inputs, gives exact results for a larger class of programs than previous work, and is accurate to the second order in the standard deviation of the kernel for programs with certain analytic properties. Because each expression in the program can have multiple approximation choices, we use a genetic search to automatically select the best approximations. We apply this framework to the problem of automatically bandlimiting procedural shader programs. We evaluate our method on a variety of geometries and complex shaders, including shaders with parallax mapping, animation, and spatially varying statistics. The resulting smoothed shader programs outperform previous approaches both numerically and aesthetically.     

A join algorithm for combining AND parallel solutions in AND/OR parallel systems

When two or more literals in the body of a Prolog clause are solved in (AND) parallel, their solutions need to bejoined to compute solutions for the clause. This is often a difficult problem in parallel Prolog systems that exploit OR and independent AND parallelism in Prolog programs. In several AND/OR parallel systems proposed recently, this problem is side-stepped at the cost of unexploited OR parallelism in the program, in part due to the complexity of the backtracking algorithm beneath AND parallel branches. In some cases, the data dependency graphs used by these systems cannot represent all the exploitable indenpendent AND parallelism known at compile time.In this paper, we describe the compile time analysis for an optimizedjoin algorithm for supporting independent AND parallelism in logic programs efficiently without leaving any OR parallelism unexploited. We then discuss how this analysis can be used to yield very efficient runtime behavior. We also discuss problems associated with a tree representation of the search space when arbitrarily complex data dependency graphs are permitted. We describe how these problems can be resolved by mapping the search space onto the data dependency graphs themselves. The algorithm has been implemented in a compiler for parallel Prolog based on the Reduce-OR process model. The algorithm is suitable for the implementation of AND/OR systems on both shared and nonshared memory machines. Performance on benchmark programs exhibiting AND and OR parallelism on one shared memory machine and one message passing machine is presented.This work was supported in part by NSF Grants CCR-87-00988 and CCR-89-02496.A shorter version of this paper appears in theProceedings of NACLP 1990.     

Compositional Analysis of C/C++ Programs with VeriSoft

This paper describes how the state space exploration ool VeriSoft can be used to analyze parallel C/C++ programs compositionally. VeriSoft is employed for two analyses: transition traceanalysis and assume/guarantee reasoning. Both analyses are compositional in the sense that the behaviour of a parallel program is determined in terms of the behaviour of its constituent processes. While both analyses have traditionally been carried out with “pencil and paper”, the paper demonstrates how VeriSoft can be used to automate them. In the context of transition trace analysis, the question whether a given program can exhibit a given trace is addressed with VeriSoft. To implement assume/guarantee reasoning, VeriSoft is used to determine whether a given program satisfies a given assume/guarantee specification. Since VeriSoft’s state space exploration is bounded and thus not complete in general, our proposed analyses are only meant to complement standard reasoning about parallel programs using traces or assume/guarantee specifications. For instance, a successful analysis does not always imply the general correctness of an assume/guarantee specification. However, it increases the confidence in the verification effort. On the other hand, an unsuccessful analysis always produces a counterexample which can be used to correct the specification or the program. VeriSoft’s optimization and visualization techniques make the analyses relatively efficient and effective.     

Visual Parallel Programming and Determinancy: A Language Specification,an Analysis Technique,and a Programming Tool

Phred is a visual parallel programming language in which programs can be statically analyzed for deterministic behavior. This paper presents the Phred language, techniques for analyzing the language, and a programming environment which supports Phred programming. There are many methods for specifying synchronization and data sharing in parallel programs. The Phred programmer uses graph constructs for describing parallelism, synchronization, and data sharing. These graphs are formally described in this paper as a graph grammar. The use of graphs in Phred provides an intuitive and visual representation for parallel computations. The inadvertent specification of nondeterministic computations is a common error in parallel programming. Phred addresses the issue of determinacy by visually indicating regions of a program where nondeterminacy may exist. This analysis and its integration into a programming environment is presented here. The Phred programming environment supports the specification, analysis, and execution of Phred programs. The distribution of the programming environment itself over several workstations is also described.     

A Genetic Algorithm for Multiobjective Robust Design

The goal of robust design is to develop stable products that exhibit minimum sensitivity to uncontrollable variations. The main drawback of many quality engineering approaches, including Taguchi's ideology, is that they cannot efficiently handle presence of several often conflicting objectives and constraints that occur in various design environments.Classical vector optimization and multiobjective genetic algorithms offer numerous techniques for simultaneous optimization of multiple responses, but they have not addressed the central quality control activities of tolerance design and parameter optimization. Due to their ability to search populations of candidate designs in parallel without assumptions of continuity, unimodality or convexity of underlying objectives, genetic algorithms are an especially viable tool for off-line quality control.In this paper we introduce a new methodology which integrates key concepts from diverse fields of robust design, multiobjective optimization and genetic algorithms. The genetic algorithm developed in this work applies natural genetic operators of reproduction, crossover and mutation to evolve populations of hyper-rectangular design regions while simultaneously reducing the sensitivity of the generated designs to uncontrollable variations. The improvement in quality of successive generations of designs is achieved by conducting orthogonal array experiments as to increase the average signal-to-noise ratio of a pool of candidate designs from one generation to the next.     

Game model-based co-evolutionary algorithm with non-dominated memory and Euclidean distance selection mechanisms for multi-objective optimization

Many real-world problems involve simultaneous optimization of several incommensurable and often competing objectives. In the search for solutions to multi-objective optimization problems (MOPs), we find that there is no single optimum but rather a set of optimums known as the “Pareto optimal set”. Co-evolutionary algorithms are well suited to optimization problems which involve several often competing objectives. Co-evolutionary algorithms are aimed at evolving individuals through individuals competing in an objective space. In order to approximate the ideal Pareto optimal set, the search capability of diverse individuals in an objective space can be used to determine the performance of evolutionary algorithms. Non-dominated memory and Euclidean distance selection mechanisms for co-evolutionary algorithms have the goal of overcoming the limited search capability of diverse individuals in the population space. In this paper, we propose a method for maintaining population diversity in game model-based co-evolutionary algorithms, and we evaluate the effectiveness of our approach by comparing it with other methods through rigorous experiments on several MOPs.