Invariant diagrams with data refinement

Invariant based programming is an approach where we start to construct a program by first identifying the basic situations (pre- and post-conditions as well as invariants) that could arise during the execution of the algorithm. These situations are identified before any code is written. After that, we identify the transitions between the situations, which will give us the flow of control in the program. Data refinement is a technique of building correct programs working on concrete data structures as refinements of more abstract programs working on abstract data types. We study in this paper data refinement for invariant based programs and we apply it to the construction of the classical Deutsch–Schorr–Waite graph marking algorithm. Our results are formalized and mechanically proved in the Isabelle/HOL theorem prover.     

基于文化算法的生产过程建模法

文化算法是一种模拟文化进化过程的优化算法,它由基于个体和群体特性的信念空间和基于个体行为的种群空间组成,为进化搜索机制和知识存储的结合提供一个构架。建立基于生产过程输入输出数据的统计模型时,参数估计是其中的关键,文化算法为此提供了有效途径。本文研究用文化算法实现多变量优化的具体步骤、算法和关键环节的实施。建立裂解炉裂解深度的神经网络模型,并用文化算法优化网络参数,实验表明,文化算法比标准遗传算法搜索性能更优,搜索时间更快,同时得到了满意的裂解深度模型。     

Hybridization of Chaos and Flower Pollination Algorithm over K-Means for data clustering

Classical clustering algorithms like K-means often converge to local optima and have slow convergence rates for larger datasets. To overcome such situations in clustering, swarm based algorithms have been proposed. Swarm based approaches attempt to achieve the optimal solution for such problems in reasonable time. Many swarm based algorithms such as Flower Pollination Algorithm (FPA), Cuckoo Search Algorithm (CSA), Black Hole Algorithm (BHA), Bat Algorithm (BA) Particle Swarm Optimization (PSO), Firefly Algorithm (FFA), Artificial Bee Colony (ABC) etc have been successfully applied to many non-linear optimization problems. In this paper, an algorithm is proposed which hybridizes Chaos Optimization and Flower Pollination over K-means to improve the efficiency of minimizing the cluster integrity. The proposed algorithm referred as Chaotic FPA (CFPA) is compared with FPA, CSA, BHA, BA, FFA, and PSO over K-Means for data clustering problem. Experiments are conducted on sixteen benchmark datasets. Algorithms are compared on four different performance parameters — cluster integrity, execution time, number of iterations to converge (NIC) and stability. Results obtained are analyzed statistically using Non-parametric Friedman test. If Friedman test rejects the Null hypothesis then pair wise comparison is done using Nemenyi test. Experimental Result demonstrates the following: (a) CFPA and BHA have better performance on the basis of cluster integrity as compared to other algorithms; (b) Prove the superiority of CFPA and CSA over others on the basis of execution time; (c) CFPA and FPA converges earlier than other algorithms to evaluate optimal cluster integrity; (d) CFPA and BHA produce more stable results than other algorithms.     

Designing irregular parallel algorithms with mutual exclusion and lock-free protocols

Irregular parallel algorithms pose a significant challenge for achieving high performance because of the difficulty predicting memory access patterns or execution paths. Within an irregular application, fine-grained synchronization is one technique for managing the coordination of work; but in practice the actual performance for irregular problems depends on the input, the access pattern to shared data structures, the relative speed of processors, and the hardware support of synchronization primitives. In this paper, we focus on lock-free and mutual exclusion protocols for handling fine-grained synchronization. Mutual exclusion and lock-free protocols have received a fair amount of attention in coordinating accesses to shared data structures from concurrent processes. Mutual exclusion offers a simple programming abstraction, while lock-free data structures provide better fault tolerance and eliminate problems associated with critical sections such as priority inversion and deadlock. These synchronization protocols, however, are seldom used in parallel algorithm designs, especially for algorithms under the SPMD paradigm, as their implementations are highly hardware dependent and their costs are hard to characterize. Using graph-theoretic algorithms for illustrative purposes, we show experimental results on two shared-memory multiprocessors, the IBM pSeries 570 and the Sun Enterprise 4500, that irregular parallel algorithms with efficient fine-grained synchronization may yield good performance.     

Classification and dimensional reduction using restricted radial basis function networks

One of the most efficient means to understand complex data is by visualizing them in two- or three-dimensional space. As meaningful data are likely to be high dimensional, visualizing them requires dimensional reduction algorithms, which objective is to map high-dimensional data into low-dimensional space while preserving some of their underlying structures. For labeled data, their low-dimensional representations should embed their classifiability so that their class-structures become visible. It is also beneficial if an algorithm can classify labeled input while at the same time executes dimensional reduction to visually offer information regarding the data’s structure to give rational behind the classification. However, most of the currently available dimensional reduction methods are not usually equipped with classification features, while most classification algorithm lacks transparencies in rationalizing their decisions. In this paper, the restricted radial basis function networks (rRBF), a recently proposed supervised neural network with low-dimensional internal representation, is utilized for visualizing high-dimensional data while also performing classification. The primary focus of this paper is to empirically explain the classifiability and visual transparency of the rRBF.

     

Scenario-based and value-based specification mining: better together

Specification mining takes execution traces as input and extracts likely program invariants, which can be used for comprehension, verification, and evolution related tasks. In this work we integrate scenario-based specification mining, which uses a data-mining algorithm to suggest ordering constraints in the form of live sequence charts, an inter-object, visual, modal, scenario-based specification language, with mining of value-based invariants, which detects likely invariants holding at specific program points. The key to the integration is a technique we call scenario-based slicing, running on top of the mining algorithms to distinguish the scenario-specific invariants from the general ones. The resulting suggested specifications are rich, consisting of modal scenarios annotated with scenario-specific value-based invariants, referring to event parameters and participating object properties. We have implemented the mining algorithm and the visual presentation of the mined scenarios within a standard development environment. An evaluation of our work over a number of case studies shows promising results in extracting expressive specifications from real programs, which could not be extracted previously. The more expressive the mined specifications, the higher their potential to support program comprehension and testing.     

Application of if-conversion to verification and optimization of workflows

Based on the workflow analysis graphs proposed in [1] and the well-known if-conversion method [2], a new algorithm of workflow verification is developed. This algorithm is based on the Boolean algebra principles, which is reflected in its name—Boolean Verification Algorithm (BVA). The BVA operates with arbitrary overlapping structures of the graph and with cycles. In the case of dense graphs, the time complexity of the algorithm does not exceed that of most other algorithms of workflow verification [3–6]. In the course of verification, the BVA determines an execution condition for each node of the graph, which makes it possible to create an additional algorithm of workflow optimization. Unlike the well-known algorithms of structural workflow optimization based on pattern transformations [7, 8], the proposed optimization algorithm allows for maximum (within a cycle) parallelization of workflows containing arbitrary overlapping structures.     

Visualizing and animating the winged-edge data structure

The winged- and half-edge data structures are commonly used representations for polyhedron models. Due to the complexity, students in an introductory course to computer graphics usually have difficulty in handling these data structures and developing applications. This paper describes the authors’ effort in the development of a visualization and animation tool for teaching and learning these data structures. This tool also includes a simple pseudo-code-like language for algorithm design. Instructors may employ this tool for presentation and demonstration purposes. Students may use the simple language to develop and experiment with new algorithms before their actual implementation. The visualization and animation system may be used to explore and understand the relationship among mesh elements and algorithm execution.     

Trace-based derivation of a scalable lock-free stack algorithm

We show how a sophisticated, lock-free concurrent stack implementation can be derived from an abstract specification in a series of verifiable steps. The algorithm is based on the scalable stack algorithm of Hendler et al. (Proceedings of the sixteenth annual ACM symposium on parallel algorithms, 27–30 June 2004, Barcelona, Spain, pp 206–215), which allows push and pop operations to be paired off and eliminated without affecting the central stack, thus reducing contention on the stack, and allowing multiple pairs of push and pop operations to be performed in parallel. Our algorithm uses a simpler data structure than Hendler, Shavit and Yerushalmi’s, and avoids an ABA problem. We first derive a simple lock-free stack algorithm using a linked-list implementation, and discuss issues related to memory management and the ABA problem. We then add an abstract model of the elimination process, from which we derive our elimination algorithm. This allows the basic algorithmic ideas to be separated from implementation details, and provides a basis for explaining and comparing different variants of the algorithm. We show that the elimination stack algorithm is linearisable by showing that any execution of the implementation can be transformed into an equivalent execution of an abstract model of a linearisable stack. Each step in the derivation is either a data refinement which preserves the level of atomicity, an operational refinement which may alter the level of atomicity, or a refactoring step which alters the structure of the system resulting from the preceding derivation. We verify our refinements using an extension of Lipton’s reduction method, allowing concurrent and non-concurrent aspects to be considered separately.     

Creation of views for reuse of software with different datarepresentations

Software reuse is inhibited by the many different ways in which equivalent data can be represented. We describe methods by which views can be constructed semi-automatically to describe how application data types correspond to the abstract types that are used in numerical generic algorithms. Given such views, specialized versions of the generic algorithms that operate directly on the application data can be produced by compilation. This enables reuse of the generic algorithms for an application with minimal effort. Graphical user interfaces allow views to be specified easily and rapidly. Algorithms are presented for deriving, by symbolic algebra, equations that relate the variables used in the application data to the variables needed for the generic algorithms. Arbitrary application data structures are allowed. Units of measurement are converted as needed. These techniques allow reuse of a single version of a generic algorithm for a variety of possible data representations and programming languages. These techniques can also be applied in data conversion and in object-oriented, functional, and transformational programming     

A conditional functional tree-handling generalized Markov algorithm which interprets a nondeterministic abstract machine

This paper presents an algorithmic interpretation of a method for the formal definition of programming lauguages which holds for languages having an ALGOL-like or PL/1-like structure. This algorithm is a Generalized Markov Algorithm (GMA) and models the behaviour of the abstract machine defined by the IBM Vienna Laboratory group for the formal definition of PL/1. The paper provides two extensions of the GMA method: The GMA here defined is nondeterministic and handles tree structured objects. The paper provides a set of rules defining the algorithm along with a technique for generating linear representations of objects having tree structures. The subject of this paper was first developed in a master thesis in mathematics at the University of Pisa (october 1968).     

Probabilistic sequential independent components analysis

Under-complete models, which derive lower dimensional representations of input data, are valuable in domains in which the number of input dimensions is very large, such as data consisting of a temporal sequence of images. This paper presents the under-complete product of experts (UPoE), where each expert models a one-dimensional projection of the data. Maximum-likelihood learning rules for this model constitute a tractable and exact algorithm for learning under-complete independent components. The learning rules for this model coincide with approximate learning rules proposed earlier for under-complete independent component analysis (UICA) models. This paper also derives an efficient sequential learning algorithm from this model and discusses its relationship to sequential independent component analysis (ICA), projection pursuit density estimation, and feature induction algorithms for additive random field models. This paper demonstrates the efficacy of these novel algorithms on high-dimensional continuous datasets.     

Sparse regularization for semi-supervised classification

Manifold regularization (MR) is a promising regularization framework for semi-supervised learning, which introduces an additional penalty term to regularize the smoothness of functions on data manifolds and has been shown very effective in exploiting the underlying geometric structure of data for classification. It has been shown that the performance of the MR algorithms depends highly on the design of the additional penalty term on manifolds. In this paper, we propose a new approach to define the penalty term on manifolds by the sparse representations instead of the adjacency graphs of data. The process to build this novel penalty term has two steps. First, the best sparse linear reconstruction coefficients for each data point are computed by the l¹-norm minimization. Secondly, the learner is subject to a cost function which aims to preserve the sparse coefficients. The cost function is utilized as the new penalty term for regularization algorithms. Compared with previous semi-supervised learning algorithms, the new penalty term needs less input parameters and has strong discriminative power for classification. The least square classifier using our novel penalty term is proposed in this paper, which is called the Sparse Regularized Least Square Classification (S-RLSC) algorithm. Experiments on real-world data sets show that our algorithm is very effective.     

Minimal Decomposition of Model-Based Invariants

Model-based invariants are relations between model parameters and image measurements, which are independent of the imaging parameters. Such relations are true for all images of the model. Here we describe an algorithm which, given L independent model-based polynomial invariants describing some shape, will provide a linear re-parameterization of the invariants. This re-parameterization has the properties that: (i) it includes the minimal number of terms, and (ii) the shape terms are the same in all the model-based invariants. This final representation has 2 main applications: (1) it gives new representations of shape in terms of hyperplanes, which are convenient for object recognition; (2) it allows the design of new linear shape from motion algorithms. In addition, we use this representation to identify object classes that have universal invariants.     

On the emergence of rules in neural networks

A simple associationist neural network learns to factor abstract rules (i.e., grammars) from sequences of arbitrary input symbols by inventing abstract representations that accommodate unseen symbol sets as well as unseen but similar grammars. The neural network is shown to have the ability to transfer grammatical knowledge to both new symbol vocabularies and new grammars. Analysis of the state-space shows that the network learns generalized abstract structures of the input and is not simply memorizing the input strings. These representations are context sensitive, hierarchical, and based on the state variable of the finite-state machines that the neural network has learned. Generalization to new symbol sets or grammars arises from the spatial nature of the internal representations used by the network, allowing new symbol sets to be encoded close to symbol sets that have already been learned in the hidden unit space of the network. The results are counter to the arguments that learning algorithms based on weight adaptation after each exemplar presentation (such as the long term potentiation found in the mammalian nervous system) cannot in principle extract symbolic knowledge from positive examples as prescribed by prevailing human linguistic theory and evolutionary psychology.     

Symbolic execution with abstraction

We address the problem of error detection for programs that take recursive data structures and arrays as input. Previously we proposed a combination of symbolic execution and model checking for the analysis of such programs: we put a bound on the size of the program inputs and/or the search depth of the model checker to limit the search state space. Here we look beyond bounded model checking and consider state matching techniques to limit the state space. We describe a method for examining whether a symbolic state that arises during symbolic execution is subsumed by another symbolic state. Since the number of symbolic states may be infinite, subsumption is not enough to ensure termination. Therefore, we also consider abstraction techniques for computing and storing abstract states during symbolic execution. Subsumption checking determines whether an abstract state is being revisited, in which case the model checker backtracks—this enables analysis of an under-approximation of the program behaviors. We illustrate the technique with abstractions for lists and arrays. We also discuss abstractions for more general data structures. The abstractions encode both the shape of the program heap and the constraints on numeric data. We have implemented the techniques in the Java PathFinder tool and we show their effectiveness on Java programs. This paper is an extended version of Anand et al. (Proceedings of SPIN, pp. 163–181, 2006).     

A parallel formulation of back-propagation learning on distributed memory multiprocessors

This paper presents a mapping scheme for parallel pipelined execution of the Back-propagation Learning Algorithm on distributed memory multiprocessors. The proposed implementation exhibits inter-layer or pipelined parallelism, unique to the multilayer neural networks. Simple algorithms have been presented, which allow the data transfer involved in both recall and learning phases of the back-propagation algorithm to be carried out with a small communication overhead. The effectiveness of the mapping scheme has been illustrated, by estimating the speedup of the proposed implementation on an array of T-805 transputers.     

Black-Box Correctness Tests for Basic Parallel Data Structures

Operations on basic data structures such as queues, priority queues, stacks, and counters can dominate the execution time of a parallel program due to both their frequency and their coordination and contention overheads. There are considerable performance payoffs in developing highly optimized, asynchronous, distributed, cache-conscious, parallel implementations of such data structures. Such implementations may employ a variety of tricks to reduce latencies and avoid serial bottlenecks, as long as the semantics of the data structure are preserved. The complexity of the implementation and the difficulty in reasoning about asynchronous systems increases concerns regarding possible bugs in the implementation. In this paper we consider postmortem, black-box procedures for testing whether a parallel data structure behaved correctly. We present the first systematic study of algorithms and hardness results for such testing procedures, focusing on queues, priority queues, stacks, and counters, under various important scenarios. Our results demonstrate the importance of selecting test data such that distinct values are inserted into the data structure (as appropriate). In such cases we present an O(n) time algorithm for testing linearizable queues, an O(n log n) time algorithm for testing linearizable priority queues, and an O( np ² ) time algorithm for testing sequentially consistent queues, where n is the number of data structure operations and p is the number of processors. In contrast, we show that testing such data structures for executions with arbitrary input values is NP-complete. Our results also help clarify the thresholds between scenarios that admit polynomial time solutions and those that are NP-complete. Our algorithms are the first nontrivial algorithms for these problems.     

树型网格计算环境下的自适应任务调度算法

提出一种基于树型计算网格的自适应调度算法,实现对小粒度独立任务和用户大作业的自适应最优调度。通过对网格环境的实时检测,给出了基于节点负载状况、节点任务执行时间、任务传输时间和任务特性的自适应调度算法,即基于最优任务分配方案的启发式任务调度算法。通过实验与其他调度算法的比较,证明了所提出的任务调度算法在负载平衡和最优跨度方面具有明显的优越性。