Towards improved parallelism through order reduction of accessing data in nD matrices

This paper encompasses the presentation of an enhanced approach with the capacity to reduce the time complexity of accessing nodes in m-dimensional matrices from \(O(n^m)\) to \(O(n\log n)\) . The accomplishment of this process is attained by the serialization of nD (nD) matrices to single-dimensional arrays followed by the access of nodes accordingly. Linear representation of nD matrix data structure induces a superior parallelism of matrix calculations over dense, parallel core micro-architecture computers, including NVIDIA GPGPU Supercomputing and Intel Xeon Phi processing boards. This approach is feasibly implemented as the core of matrix data representation in Math software such as Matlab, Mathematica and Maple, in IDEs for more optimized code generation and in Parallel Computing Libraries such as CUBLAS and Magma.     

3DyRM: a dynamic roofline model including memory latency information

Modern systems present complex memory hierarchies and heterogeneity among cores and processors. As a consequence, efficient programming is challenging. An easy-to-understand performance model, offering guidelines and information about the behaviour of a code, may be useful to alleviate these issues. In this paper, we present two extensions of the well-known Berkeley Roofline Model. The first of these extensions, the Dynamic Roofline Model (DyRM), takes into consideration the complexities of multicore and heterogeneous systems, offering a more detailed view of the evolution of the execution of a code. The second, the 3DyRM, also adds information about the latency of memory accesses to better represent the behaviour on systems with complex memory hierarchies. A set of tools to obtain and represent the models has been implemented. These tools obtain the needed data from hardware counters, with low overhead. Different views are displayed by the tool that can be used to extract the main features of the code. Results of studying, with these tools, the NAS Parallel Benchmarks for OpenMP on two different systems are presented.     

Sparse representation of precision matrices used in GMMs

The paper presents a novel precision matrix modeling technique for Gaussian Mixture Models (GMMs), which is based on the concept of sparse representation. Representation coefficients of each precision matrix (inverse covariance), as well as an accompanying overcomplete matrix dictionary, are learned by minimizing an appropriate functional, the first component of which corresponds to the sum of Kullback-Leibler (KL) divergences between the initial and the target GMM, and the second represents the sparse regularizer of the coefficients. Compared to the existing, alternative approaches for approximate GMM modeling, like popular subspace-based representation methods, the proposed model results in notably better trade-off between the representation error and the computational (memory) complexity. This is achieved under assumption that the training data in the recognition system utilizing GMM have an inherent sparseness property, which enables application of the proposed model and approximate representation using only one dictionary and a significantly smaller number of coefficients. Proposed model is experimentally compared with the Subspace Precision and Mean (SPAM) model, a state of the art instance of subspace-based representation models, using both the data from a real Automatic Speech Recognition (ASR) system, and specially designed sets of artificially created/synthetic data.     

An architecture modeling framework for probabilistic prediction

In the design phase of business and IT system development, it is desirable to predict the properties of the system-to-be. A number of formalisms to assess qualities such as performance, reliability and security have therefore previously been proposed. However, existing prediction systems do not allow the modeler to express uncertainty with respect to the design of the considered system. Yet, in contemporary business, the high rate of change in the environment leads to uncertainties about present and future characteristics of the system, so significant that ignoring them becomes problematic. In this paper, we propose a formalism, the Predictive, Probabilistic Architecture Modeling Framework (P²AMF), capable of advanced and probabilistically sound reasoning about business and IT architecture models, given in the form of Unified Modeling Language class and object diagrams. The proposed formalism is based on the Object Constraint Language (OCL). To OCL, P²AMF adds a probabilistic inference mechanism. The paper introduces P²AMF, describes its use for system property prediction and assessment and proposes an algorithm for probabilistic inference.     

Towards Model-Driven V&V assessment of railway control systems

Verification and Validation (V&V) activities aiming at certifying railway controllers are among the most critical and time-consuming in system development life cycle. As such, they would greatly benefit from novel approaches enabling both automation and traceability for assessment purposes. While several formal and Model-Based approaches have been proposed in the scientific literature, some of which are successfully employed in industrial settings, we are still far from an integrated and unified methodology which allows guiding design choices, minimizing the chances of failures/non-compliances, and considerably reducing the overall assessment effort. To address these issues, this paper describes a Model-Driven Engineering approach which is very promising to tackle the aforementioned challenges. In fact, the usage of appropriate Unified Modeling Language profiles featuring system analysis and test case specification capabilities, together with tool chains for model transformations and analysis, seems a viable way to allow end-users to concentrate on high-level holistic models and specification of non-functional requirements (i.e., dependability) and support the automation of the V&V process. We show, through a case study belonging to the railway signalling domain, how the approach is effective in supporting activities like system testing and availability evaluation.     

A Middleware-Based Simulation and Control Framework for Mobile Service Robots

A mobile service robot is a complex distributed system integrating various technologies and having large heterogeneity. In order to facilitate component development and system integration of the mobile service robots, a middleware-based simulation and control framework for system integration and application development, as well as the robotic functional component (RFC) framework with a simplified structure and an efficient transmission scheme, is proposed for mobile service robot systems. Designed to implement a distributed modular mechanism for a mobile service robot, the middleware-based framework for simulation and control is comprised of four layers: low-level abstraction layer, communication layer, high-level abstraction layer, and application layer. Common Object Request Broker Architecture (CORBA) and Robot Technology Middleware (RTM) are employed as middleware for the development of RFCs and for system integration. Communication between the components and the graphical programming tool is done by the communication layer (CORBA ORB). The conducted experiments validated the proposed framework in terms of ideal performance of reusability, interoperability, and extensibility, as well as indicated that the proposed RFC framework is simplified and easy enough to perform well in data transmission, which will reduce the costs and the threshold of robot development.     

The plane with parallel coordinates

By means ofParallel Coordinates planar “graphs” of multivariate relations are obtained. Certain properties of the relationship correspond tothe geometrical properties of its graph. On the plane a point ←→ line duality with several interesting properties is induced. A new duality betweenbounded and unbounded convex sets and hstars (a generalization of hyperbolas) and between Convex Unions and Intersections is found. This motivates some efficient Convexity algorithms and other results inComputational Geometry. There is also a suprising “cusp” ←→ “inflection point” duality. The narrative ends with a preview of the corresponding results inR ^N .     

Adaptive AMG with coarsening based on compatible weighted matching

We introduce a new composite adaptive Algebraic Multigrid (composite \(\alpha \) AMG) method to solve systems of linear equations without a-priori knowledge or assumption on characteristics of near-null components of the AMG preconditioned problem referred to as algebraic smoothness. Our version of \(\alpha \) AMG is a composite solver built through a bootstrap strategy aimed to obtain a desired convergence rate. The coarsening process employed to build each new solver component relies on a pairwise aggregation scheme based on weighted matching in a graph, successfully exploited for reordering algorithms in sparse direct methods to enhance diagonal dominance, and compatible relaxation. The proposed compatible matching process replaces the commonly used characterization of strength of connection in both the coarse space selection and in the interpolation scheme. The goal is to design a method leading to scalable AMG for a wide class of problems that go beyond the standard elliptic Partial Differential Equations (PDEs). In the present work, we introduce the method and demonstrate its potential when applied to symmetric positive definite linear systems arising from finite element discretization of highly anisotropic elliptic PDEs on structured and unstructured meshes. We also report on some preliminary tests for 2D and 3D elasticity problems as well as on problems from the University of Florida Sparse Matrix Collection.     

Data-flow based execution mechanisms of Parallel and Concurrent Prolog

Study attempts to show that our machine architecture based on the data flow model is suitable for two types of logic programming languages with different aims: one is Parallel Prolog and the other is Concurrent Prolog. The data flow model can naturally implement parallel computation, and it has close similarity to these languages. Unification and nondeterministic control, two basic functions of these languages, are represented by data flow graphs and interpreted by the machine. Several representations of variables, that facilitate the development of parallel unification and nondeterministic control mechanisms for these languages, the unification and control primitives needed to execute these languages on this architecture are presented.     

Hand posture and gesture recognition technology

Hand gestures that are performed by one or two hands can be categorized according to their applications into different categories including conversational, controlling, manipulative and communicative gestures. Generally, hand gesture recognition aims to identify specific human gestures and use them to convey information. The process of hand gesture recognition composes mainly of four stages: hand gesture images collection, gesture image preprocessing using some techniques including edge detection, filtering and normalization, capture the main characteristics of the gesture images and the evaluation (or classification) stage where the image is classified to its corresponding gesture class. There are many methods that have been used in the classification stage of hand gesture recognition such as Artificial Neural Networks, template matching, Hidden Markov Models and Dynamic Time Warping. This exploratory survey aims to provide a progress report on hand posture and gesture recognition technology.     

A compressed sensing approach for query by example video retrieval

Recently, compressed Sensing (CS) has theoretically been proposed for more efficient signal compression and recovery. In this paper, the CS based algorithms are investigated for Query by Example Video Retrieval (QEVR) and a novel similarity measure approach is proposed. Combining CS theory with the traditional discrete cosine transform (DCT), better compression efficiency for spatially sparse is achieved. The similarity measure from three levels (frame level, shot level and video level, respectively) is also discussed. For several different kinds of natural videos, the experimental results demonstrate the effectiveness of system by the proposed method.     

Mechanism and Convergence Analysis of a Multi-Robot Swarm Approach Based on Natural Selection

The Darwinian Particle Swarm Optimization (DPSO) is an evolutionary algorithm that extends the Particle Swarm Optimization (PSO) using natural selection, or survival-of-the-fittest, to enhance the ability to escape from local optima. An extension of the DPSO to multi-robot applications has been recently proposed and denoted as Robotic Darwinian PSO (RDPSO), benefiting from the dynamical partitioning of the whole population of robots. Therefore, the RDPSO decreases the amount of required information exchange among robots, and is scalable to large populations of robots. This paper presents a stability analysis of the RDPSO to better understand the relationship between the algorithm parameters and the robot’s convergence. Moreover, the analysis of the RDPSO is further extended for real robot constraints (e.g., robot dynamics, obstacles and communication constraints) and experimental assessment with physical robots. The optimal parameters are evaluated in groups of physical robots and a larger population of simulated mobile robots for different target distributions within larger scenarios. Experimental results show that robots are able to converge regardless of the RDPSO parameters within the defined attraction domain. However, a more conservative parametrization presents a significant influence on the convergence time. To further evaluate the herein proposed approach, the RDPSO is further compared with four state-of-the-art swarm robotic alternatives under simulation. It is observed that the RDPSO algorithm provably converges to the optimal solution faster and more accurately than the other approaches.     

Improving Skills and Perception in Robot Navigation by an Augmented Virtuality Assistance System

Successful navigation in a teleoperation scenario requires a good level of situational or environmental awareness. This paper presents the main features and capabilities of a new augmented virtuality-based system aimed at providing users with improved perception of the robot’s remote environment. With this purpose, a mixed-perspective exocentric display (ME3D), and a video centric display (VC2D) are compared. Both interfaces were implemented on a mobile robot and experiments were performed in a real working scenario. To assess this contribution, this works analyzes the teleoperation capability, performance, and human workload of users by means of NASA-TLX (Task Load Index). The results show that participants experienced a reduction in the driving workload and showed high degrees of acceptance for the proposed ME3D interface.     

NPB CG在分布式环境下的并行实现

ＣＧＢｅｎｃｈｍａｒｋ是ＮＡＳＰａｒａｌｅｌＢｅｎｃｈｍａｒｋｓ（ＮＰＢ）中的一个核心程序，它用共轭梯度法求大型稀疏对称正定矩阵的最小特征值，本文介绍其主要算法，并给出在分布式环境下的高效并行算法，最后给出了在ＳＧＩＣｈａｌｅｎｇｅＰＶＭ平台上的测试结果     

On parallel unification for Prolog

Parallel unification algorithms are not nearly so numerous or well-developed as sequential ones. In order to estimate the improvement in efficiency which may be expected, we define and discuss an objective measure of the effect of parallelism on a sequential algorithm. This measure, known as thepotential parallel factor (PPF), is applied to parallel versions of the unification algorithms of Yasuura and Jaffar. The PPFs for these algorithms are measured on a variety of running Prolog programs to estimate what increase in speed may be expected in a Prolog environment from the use of parallelism. Other potential uses of parallelism may be evaluated by different applications of our general methods and techniques.     

E-D2HCP: enhanced distributed dynamic host configuration protocol

Mobile Ad Hoc Networks (MANETs) consist of mobile nodes equipped with wireless devices. They do not need any kind of pre-existent infrastructure and are about self-managed networks. MANETs enable communication between mobile nodes without direct links and across multihop paths. To ensure correct operation of the routing protocols, MANETs, have to assign unique IP addresses to the MANET devices. Furthermore, the address assignment is an important issue when dealing with MANET networks because the traditional approaches are not applicable without some changes, having to provide new protocols for the address auto-configuration. These schemes must take into account the properties of MANETs such as dynamic topology, limited resources or lack of infrastructure. In this paper, we propose a stateful scheme for dynamic allocation of IP addresses in MANETs entitled Extended Distributed Dynamic Host Configuration Protocol because it is based on a previous piece of work (D2CHP). This extension includes the network merging not covered by its predecessor. Simulation results show that the new protocol also improves D2HCP functionality in areas such as fault tolerance, concurrency and latency.     

Architecture of a Reduction-Based Parallel Inference Machine: PIM-R

This paper presents a highly parallel machine architecture for logic programs. We propose a Reduction-Based Parallel Inference Machine: PIM-R and describe the parallel execution mechanisms for PIM-R to run Prolog and Concurrent Prolog programs and sofware simulation results. PIM-R uses the structure-copy method. It also uses the only reducible goal copy method, a unique process-structuring method, and the reverse compaction method to decrease the amount, of copying and various copyingrelated operations and the number of packets passing through the network. PIM-R architecture features include the distributed shared memory for Concurrent Prolog, network nodes for efficient packet distribution, and the structure memory to store a part of structured data for reducing the copying overhead.     

Inductive logic programming

A new research area, Inductive Logic Programming, is presently emerging. While inheriting various positive characteristics of the parent subjects of Logic Programming and Machine Learning, it is hoped that the new area will overcome many of the limitations of its forebears. The background to present developments within this area is discussed and various goals and aspirations for the increasing body of researchers are identified. Inductive Logic Programming needs to be based on sound principles from both Logic and Statistics. On the side of statistical justification of hypotheses we discuss the possible relationship between Algorithmic Complexity theory and Probably-Approximately-Correct (PAC) Learning. In terms of logic we provide a unifying framework for Muggleton and Buntine’s Inverse Resolution (IR) and Plotkin’s Relative Least General Generalisation (RLGG) by rederiving RLGG in terms of IR. This leads to a discussion of the feasibility of extending the RLGG framework to allow for the invention of new predicates, previously discussed only within the context of IR.