Volume 25 (2015): Issue 4 (December 2015)
Special issue: Complex Problems in High-Performance Computing Systems, Editors: Mauro Iacono, Joanna Kołodziej

When there is a mismatch between the cardinality of a periodic task set and the priority levels supported by the underlying hardware systems, multiple tasks are grouped into one class so as to maintain a specific level of confidence in their accuracy. However, such a transformation is achieved at the expense of the loss of schedulability of the original task set. We further investigate the aforementioned problem and report the following contributions: (i) a novel technique for mapping unlimited priority tasks into a reduced number of classes that do not violate the schedulability of the original task set and (ii) an efficient feasibility test that eliminates insufficient points during the feasibility analysis. The theoretical correctness of both contributions is checked through formal verifications. Moreover, the experimental results reveal the superiority of our work over the existing feasibility tests by reducing the number of scheduling points that are needed otherwise.

Supercomputers are today made up of hundreds of thousands of nodes. The interconnection network is responsible for connecting all these nodes to each other. Different interconnection networks have been proposed; high performance topologies have been introduced as a replacement for the conventional topologies of recent decades. A high order, a low degree and a small diameter are the usual properties aimed for by such topologies. However, this is not sufficient to lead to actual hardware implementations. Network scalability and topology simplicity are two critical parameters, and they are two of the reasons why modern supercomputers are often based on torus interconnection networks (e.g., Fujitsu K, IBM Sequoia). In this paper we first describe a new topology, torus-connected cycles (TCCs), realizing a combination of a torus and a ring, thus retaining interesting properties of torus networks in addition to those of hierarchical interconnection networks (HINs). Then, we formally establish the diameter of a TCC, and deduce a point-to-point routing algorithm. Next, we propose routing algorithms solving the Hamiltonian cycle problem, and, in a two dimensional TCC, the Hamiltonian path one. Correctness and complexities are formally proved. The proposed algorithms are time-optimal.

We present in this paper a novel distributed solution to a security-aware job scheduling problem in cloud computing infrastructures. We assume that the assignment of the available resources is governed exclusively by the specialized brokers assigned to individual users submitting their jobs to the system. The goal of this scheme is allocating a limited quantity of resources to a specific number of jobs minimizing their execution failure probability and total completion time. Our approach is based on the Pareto dominance relationship and implemented at an individual user level. To select the best scheduling strategies from the resulting Pareto frontiers and construct a global scheduling solution, we developed a decision-making mechanism based on the game-theoretic model of Spatial Prisoner’s Dilemma, realized by selfish agents operating in the two-dimensional cellular automata space. Their behavior is conditioned by the objectives of the various entities involved in the scheduling process and driven towards a Nash equilibrium solution by the employed social welfare criteria. The performance of the scheduler applied is verified by a number of numerical experiments. The related results show the effectiveness and scalability of the scheme in the presence of a large number of jobs and resources involved in the scheduling process.

We analyse Give and Take, a multi-stage resource sharing game to be played between two players. The payoff is dependent on the possession of an indivisible and durable resource, and in each stage players may either do nothing or, depending on their roles, give the resource or take it. Despite these simple rules, we show that this game has interesting complex dynamics. Unique to Give and Take is the existence of multiple Pareto optimal profiles that can also be Nash equilibria, and a built-in punishment action. This game allows us to study cooperation in sharing an indivisible and durable resource. Since there are multiple strategies to cooperate, Give and Take provides a base to investigate coordination under implicit or explicit agreements. We discuss its position in face of other games and real world situations that are better modelled by it. The paper presents an in-depth analysis of the game for the range of admissible parameter values. We show that, when taking is costly for both players, cooperation emerges as players prefer to give the resource.

The Lanczos algorithm is among the most frequently used iterative techniques for computing a few dominant eigenvalues of a large sparse non-symmetric matrix. At the same time, it serves as a building block within biconjugate gradient (BiCG) and quasi-minimal residual (QMR) methods for solving large sparse non-symmetric systems of linear equations. It is well known that, when implemented on distributed-memory computers with a huge number of processes, the synchronization time spent on computing dot products increasingly limits the parallel scalability. Therefore, we propose synchronization-reducing variants of the Lanczos, as well as BiCG and QMR methods, in an attempt to mitigate these negative performance effects. These so-called s-step algorithms are based on grouping dot products for joint execution and replacing time-consuming matrix operations by efficient vector recurrences. The purpose of this paper is to provide a rigorous derivation of the recurrences for the s-step Lanczos algorithm, introduce s-step BiCG and QMR variants, and compare the parallel performance of these new s-step versions with previous algorithms.

Service life of many real-life systems cannot be considered infinite, and thus the systems will be eventually stopped or will break down. Some of them may be re-launched after possible maintenance under likely new initial conditions. In such systems, which are often modelled by birth and death processes, the assumption of stationarity may be too strong and performance characteristics obtained under this assumption may not make much sense. In such circumstances, time-dependent analysis is more meaningful. In this paper, transient analysis of one class of Markov processes defined on non-negative integers, specifically, inhomogeneous birth and death processes allowing special transitions from and to the origin, is carried out. Whenever the process is at the origin, transition can occur to any state, not necessarily a neighbouring one. Being in any other state, besides ordinary transitions to neighbouring states, a transition to the origin can occur. All possible transition intensities are assumed to be non-random functions of time and may depend (except for transition to the origin) on the process state. To the best of our knowledge, first ergodicity and perturbation bounds for this class of processes are obtained. Extensive numerical results are also provided.

In this paper, an approach to analyze the observability and controllability of sandwich systems with backlash is proposed. In this method, a non-smooth state-space function is used to describe the sandwich systems with backlash which are also non-smooth non-linear systems. Then, a linearization method based on non-smooth optimization is proposed to derive a linearized state-space function to approximate the non-smooth sandwich systems within a bounded region around the equilibrium point that we are interested in. Afterwards, both observability and controllability matrices are constructed and the methods to analyze the observability as well as controllability of sandwich system with backlash are derived. Finally, numerical examples are presented to validate the proposed method.

This work introduces a novel approach to stability and stabilization of nonlinear systems with delayed multivariable inputs; it provides exponential estimates as well as a guaranteed cost of the system solutions. The result is based on an exact convex representation of the nonlinear system which allows a Lyapunov–Krasovskii functional to be applied in order to obtain sufficient conditions in the form of linear matrix inequalities. These are efficiently solved via convex optimization techniques. A real-time implementation of the developed approach on the twin rotor MIMO system is included.

The positivity and linearization of a class of nonlinear continuous-time system by nonlinear state feedbacks are addressed. Necessary and sufficient conditions for the positivity of the class of nonlinear systems are established. A method for linearization of nonlinear systems by nonlinear state feedbacks is presented. It is shown that by a suitable choice of the state feedback it is possible to obtain an asymptotically stable and controllable linear system, and if the closed-loop system is positive then it is unstable.

This paper describes computationally efficient model predictive control (MPC) algorithms for nonlinear dynamic systems represented by discrete-time state-space models. Two approaches are detailed: in the first one the model is successively linearised on-line and used for prediction, while in the second one a linear approximation of the future process trajectory is directly found on-line. In both the cases, as a result of linearisation, the future control policy is calculated by means of quadratic optimisation. For state estimation, the extended Kalman filter is used. The discussed MPC algorithms, although disturbance state observers are not used, are able to compensate for deterministic constant-type external and internal disturbances. In order to illustrate implementation steps and compare the efficiency of the algorithms, a polymerisation reactor benchmark system is considered. In particular, the described MPC algorithms with on-line linearisation are compared with a truly nonlinear MPC approach with nonlinear optimisation repeated at each sampling instant.

The paper deals with the modeling and fault-tolerant control of a real battery assembly system which is under implementation at the RAFI GmbH company (one of the leading electronic manufacturing service providers in Germany). To model and control the battery assembly system, a unified max-plus algebra and model predictive control framework is introduced. Subsequently, the control strategy is enhanced with fault-tolerance features that increase the overall performance of the production system being considered. In particular, it enables tolerating (up to some degree) mobile robot, processing and transportation faults. The paper discusses also robustness issues, which are inevitable in real production systems. As a result, a novel robust predictive fault-tolerant strategy is developed that is applied to the battery assembly system. The last part of the paper shows illustrative examples, which clearly exhibit the performance of the proposed approach.

This paper is devoted to the blind identification problem of a special class of nonlinear systems, namely, Volterra models, using a real-coded genetic algorithm (RCGA). The model input is assumed to be a stationary Gaussian sequence or an independent identically distributed (i.i.d.) process. The order of the Volterra series is assumed to be known. The fitness function is defined as the difference between the calculated cumulant values and analytical equations in which the kernels and the input variances are considered. Simulation results and a comparative study for the proposed method and some existing techniques are given. They clearly show that the RCGA identification method performs better in terms of precision, time of convergence and simplicity of programming.

The paper presents algorithms for parameter identification of linear vessel models being in force for the current operating point of a ship. Advantages and disadvantages of gradient and genetic algorithms in identifying the model parameters are discussed. The study is supported by presentation of identification results for a nonlinear model of a drilling vessel.

One of the problems in the analysis of the set of images of a moving object is to evaluate the degree of freedom of motion and the angle of rotation. Here the intrinsic dimensionality of multidimensional data, characterizing the set of images, can be used. Usually, the image may be represented by a high-dimensional point whose dimensionality depends on the number of pixels in the image. The knowledge of the intrinsic dimensionality of a data set is very useful information in exploratory data analysis, because it is possible to reduce the dimensionality of the data without losing much information. In this paper, the maximum likelihood estimator (MLE) of the intrinsic dimensionality is explored experimentally. In contrast to the previous works, the radius of a hypersphere, which covers neighbours of the analysed points, is fixed instead of the number of the nearest neighbours in the MLE. A way of choosing the radius in this method is proposed. We explore which metric—Euclidean or geodesic—must be evaluated in the MLE algorithm in order to get the true estimate of the intrinsic dimensionality. The MLE method is examined using a number of artificial and real (images) data sets.

The paper is focused on the problem of multi-class classification of composite (piecewise-regular) objects (e.g., speech signals, complex images, etc.). We propose a mathematical model of composite object representation as a sequence of independent segments. Each segment is represented as a random sample of independent identically distributed feature vectors. Based on this model and a statistical approach, we reduce the task to a problem of composite hypothesis testing of segment homogeneity. Several nearest-neighbor criteria are implemented, and for some of them the well-known special cases (e.g., the Kullback–Leibler minimum information discrimination principle, the probabilistic neural network) are highlighted. It is experimentally shown that the proposed approach improves the accuracy when compared with contemporary classifiers.

In the subject literature, wavelets such as the Mexican hat (the second derivative of a Gaussian) or the quadratic box spline are commonly used for the task of singularity detection. The disadvantage of the Mexican hat, however, is its unlimited support; the disadvantage of the quadratic box spline is a phase shift introduced by the wavelet, making it difficult to locate singular points. The paper deals with the construction and properties of wavelets in the form of cubic box splines which have compact and short support and which do not introduce a phase shift. The digital filters associated with cubic box wavelets that are applied in implementing the discrete dyadic wavelet transform are defined. The filters and the algorithme à trous of the discrete dyadic wavelet transform are used in detecting signal singularities and in calculating the measures of signal singularities in the form of a Lipschitz exponent. The article presents examples illustrating the use of cubic box spline wavelets in the analysis of signal singularities.

In this paper we emphasize a similarity between the logarithmic type image processing (LTIP) model and the Naka–Rushton model of the human visual system (HVS). LTIP is a derivation of logarithmic image processing (LIP), which further replaces the logarithmic function with a ratio of polynomial functions. Based on this similarity, we show that it is possible to present a unifying framework for the high dynamic range (HDR) imaging problem, namely, that performing exposure merging under the LTIP model is equivalent to standard irradiance map fusion. The resulting HDR algorithm is shown to provide high quality in both subjective and objective evaluations.

In this article a new neural network based method for automatic classification of ground penetrating radar (GPR) traces is proposed. The presented approach is based on a new representation of GPR signals by polynomials approximation. The coefficients of the polynomial (the feature vector) are neural network inputs for automatic classification of a special kind of geologic structure—a sinkhole. The analysis and results show that the classifier can effectively distinguish sinkholes from other geologic structures.

The main aim is to present recent developments in applications of symbolic computing in probabilistic and stochastic analysis, and this is done using the example of the well-known MAPLE system. The key theoretical methods discussed are (i) analytical derivations, (ii) the classical Monte-Carlo simulation approach, (iii) the stochastic perturbation technique, as well as (iv) some semi-analytical approaches. It is demonstrated in particular how to engage the basic symbolic tools implemented in any system to derive the basic equations for the stochastic perturbation technique and how to make an efficient implementation of the semi-analytical methods using an automatic differentiation and integration provided by the computer algebra program itself. The second important illustration is probabilistic extension of the finite element and finite difference methods coded in MAPLE, showing how to solve boundary value problems with random parameters in the environment of symbolic computing. The response function method belongs to the third group, where interference of classical deterministic software with the non-linear fitting numerical techniques available in various symbolic environments is displayed. We recover in this context the probabilistic structural response in engineering systems and show how to solve partial differential equations including Gaussian randomness in their coefficients.