Thread vulnerability in parallel applications

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 today 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$TVF$). A distinguishing characteristic of TVF$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 resources and data with that thread. As a result, we decompose TVF$TVF$ of a thread into two complementary parts: local and remote. While the former captures the TVF$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$TVF$ values for three architectural components (register file, ALUs, and caches) using a set of ten multithreaded applications from the Parsec and Splash-2 benchmark suites. Our experimental evaluation shows that TVF$TVF$ values tend to increase as the number of cores increases, which means the system becomes more vulnerable as the core count rises. We further discuss how TVF$TVF$ metric can be employed to explore performance–reliability tradeoffs in multicores. Reliability-based analysis of compiler optimizations and redundancy-based fault tolerance are also mentioned as potential usages of our TVF$TVF$ metric.     

Stratification associated with local b-functions

The local b$b$-function _bf,p(s)$b_{f,p}\left(s\right)$ of an n$n$-variate polynomial f∈C[x]$f\in \mathbb{C}\left[x\right]$ (x=(_x1,…,_xn)$x=(x_1,\dots ,x_n)$) at a point p∈Cⁿ$p\in {\mathbb{C}}^n$ is constant on each stratum of a stratification of Cⁿ${\mathbb{C}}^n$. We propose a new method for computing such a stratification and _bf,p(s)$b_{f,p}\left(s\right)$ on each stratum. In the existing method proposed in Oaku (1997b), a primary ideal decomposition of an ideal in C[x,s]$\mathbb{C}[x,s]$ is needed and our experiment shows that the primary decomposition can be a bottleneck for computing the stratification. In our new method, the computation can be done by just computing ideal quotients and examining inclusions of algebraic sets. The precise form of a stratum can be obtained by computing the decomposition of the radicals of the ideals in C[x]$\mathbb{C}\left[x\right]$ defining the stratum. We also introduce various techniques for improving the practical efficiency of the implementation and we show results of computations for some examples.     

Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes

In this paper, we investigate the fault-tolerant capabilities of the k-ary n-cubes for even integer k with respect to the hamiltonian and hamiltonian-connected properties. The k-ary n-cube is a bipartite graph if and only if k is an even integer. Let F   be a faulty set with nodes and/or links, and let k?3$k?3$ be an odd integer. When |F|?2n-2$\left|F\right|?2n-2$, we show that there exists a hamiltonian cycle in a wounded k-ary n  -cube. In addition, when |F|?2n-3$\left|F\right|?2n-3$, we prove that, for two arbitrary nodes, there exists a hamiltonian path connecting these two nodes in a wounded k-ary n-cube. Since the k-ary n  -cube is regular of degree 2n$2n$, the degrees of fault-tolerance 2n-3$2n-3$ and 2n-2$2n-2$ respectively, are optimal in the worst case.     

An approximation algorithm to the k-Steiner Forest problem

Given a graph G$G$, an integer k$k$, and a demand set D={(_s1,_t1),…,(_sl,_tl)}$D=\{(s_1,t_1),\dots ,(s_l,t_l)\}$, the k$k$-Steiner Forest problem finds a forest in graph G$G$ to connect at least k$k$ demands in D$D$ such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n^2/3logl)$O(n^{2/3}logl)$. We give a simpler and faster approximation algorithm to this problem with performance ratio O(n^2/3logk)$O(n^{2/3}logk)$ via greedy approach, improving the previously best known ratio in the literature.     

Simplifying the weft hierarchy

We give simple, self-contained proofs of the basic hardness results for the classes W[t]$W[t]$ of the weft hierarchy. We extend these proofs to higher levels of the hierarchy and illuminate the distinctions among its classes. The anti-monotone collapse at W[1,s]$W[1,s]$ and the normalization of weft-t$t$ formulas arise as by-products of the proofs.     

Set-theoretic generators of rational space curves

We show how to calculate three low degree set-theoretic generators (i.e., algebraic surfaces) for all rational space curves of low degree (degree ≤6$\le 6$) as well as for all higher degree rational space curves where at least one element of their μ$\mu$-basis has degree 1 from a μ$\mu$-basis of the parametrization. In addition to having low degree, at least two of these surface generators are always ruled surfaces. Whenever possible we also show how to compute two set-theoretic complete intersection generators for these rational space curves from a μ$\mu$-basis of their parametrization.     

MinT—Architecture and applications of the (t, m, s)-net and OOA database

Many different constructions for (t,m,s)$(t\text{,}m\text{,}s)$-nets and (t,s)$(t\text{,}s)$-sequences are known today. Propagation rules as well as connections to other mathematical objects make it difficult to determine the best net available in a given setting.     

Are Buchberger’s criteria necessary for the chain condition?

Buchberger’s Gröbner basis theory plays a fundamental role in symbolic computation. The resulting algorithms essentially carry out several S$S$-polynomial reductions. In his Ph.D. thesis and later publication Buchberger showed that sometimes one can skip S$S$-polynomial reductions if the leading terms of polynomials satisfy certain criteria. A question naturally arises: Are Buchberger’s criteria also necessary   for skipping S$S$-polynomial reductions? In this paper, after making the question more precise (in terms of a chain condition), we show the answer to be “almost, but not quite”: necessary when there are four or more polynomials, but not necessary when there are exactly three polynomials. For that case, we found an extension to Buchberger’s criteria that is necessary as well as sufficient.     

Open bisimulation,revisited

In the context of the π$\pi$-calculus, open bisimulation is prominent and popular due to its congruence properties and its easy implementability. Motivated by the attempt to generalise it to the spi-calculus, we offer a new, more refined definition and show how far it coincides with the original one.     

Multicriteria 0-1 knapsack problems with k-min objectives

This paper deals with the multicriteria 0-1 knapsack problem (KP) with k$k$-min objectives (MkMIN-KP) in which the first objective is of classical sum type and the remaining objectives are k$k$-min objective functions. The k$k$-min objectives are ordinal objectives, aiming at the maximization of the k$k$ th smallest objective coefficient in any feasible knapsack solution with at least k$k$ items in the knapsack. We develop efficient algorithms for the determination of the complete nondominated set of MkMIN-KP.     

Separation of synchronous and asynchronous communication via testing

One of the early results concerning the asynchronous π$\pi$-calculus which significantly contributed to its popularity is the capability of encoding the output prefix of the (choiceless) π$\pi$-calculus in a natural and elegant way. Encodings of this kind were proposed by Honda and Tokoro, by Nestmann and (independently) by Boudol. We investigate whether the above encodings preserve De Nicola and Hennessy’s testing semantics. In this sense, it turns out that, under some general conditions, no encoding of the output prefix is able to preserve the must testing. This negative result is due to (a) the non-atomicity of the sequences of steps which are necessary in the asynchronous π$\pi$-calculus to mimic synchronous communication, and (b) testing semantics’ sensitivity to divergence.     

Approximation of matrix operators applied to multiple vectors

In this paper we propose a numerical method for approximating the product of a matrix function with multiple vectors by Krylov subspace methods combined with a QR$QR$ decomposition of these vectors. This problem arises in the implementation of exponential integrators for semilinear parabolic problems. We will derive reliable stopping criteria and we suggest variants using up- and downdating techniques. Moreover, we show how Ritz vectors can be included in order to speed up the computation even further. By a number of numerical examples, we will illustrate that the proposed method will reduce the total number of Krylov steps significantly compared to a standard implementation if the vectors correspond to the evaluation of a smooth function at certain quadrature points.     

Optimal coverage of an infrastructure network using sensors with distance-decaying sensing quality

Motivated by recent applications of wireless sensor networks in monitoring infrastructure networks, we address the problem of optimal coverage of infrastructure networks using sensors whose sensing performance decays with distance. We show that this problem can be formulated as a continuous p-median problem on networks. The literature has addressed the discrete p-median problem   on networks and in continuum domains, and the continuous p$p$-median problem in continuum domains extensively. However, in-depth analysis of the continuous p$p$-median problem on networks has been lacking. With the sensing performance model that decays with distance, each sensor covers a region equivalent to its Voronoi partition on the network in terms of the shortest path distance metric. Using Voronoi partitions, we define a directional partial derivative of the coverage metric with respect to a sensor’s location. We then propose a gradient descent algorithm to obtain a locally optimal solution with guaranteed convergence. The quality of an optimal solution depends on the choice of the initial configuration of sensors. We obtain an initial configuration using two approaches: by solving the discrete p$p$-median problem on a lumped   network and by random sampling. We consider two methods of random sampling: uniform sampling and D²$D^2$-sampling. The first approach with the initial solution of the discrete p$p$-median problem leads to the best coverage performance for large networks, but at the cost of high running time. We also observe that the gradient descent on the initial solution with the D²$D^2$-sampling method yields a solution that is within at most 7% of the previous solution and with much shorter running time.     

Exploiting Universum data in AdaBoost using gradient descent

Recently, Universum data that does not belong to any class of the training data, has been applied for training better classifiers. In this paper, we address a novel boosting algorithm called U$\mathfrak{U}$AdaBoost that can improve the classification performance of AdaBoost with Universum data. U$\mathfrak{U}$AdaBoost chooses a function by minimizing the loss for labeled data and Universum data. The cost function is minimized by a greedy, stagewise, functional gradient procedure. Each training stage of U$\mathfrak{U}$AdaBoost is fast and efficient. The standard AdaBoost weights labeled samples during training iterations while U$\mathfrak{U}$AdaBoost gives an explicit weighting scheme for Universum samples as well. In addition, this paper describes the practical conditions for the effectiveness of Universum learning. These conditions are based on the analysis of the distribution of ensemble predictions over training samples. Experiments on handwritten digits classification and gender classification problems are presented. As exhibited by our experimental results, the proposed method can obtain superior performances over the standard AdaBoost by selecting proper Universum data.     

Non-associative Gröbner bases,finitely-presented Lie rings and the Engel condition,II

We give an algorithm for constructing a basis and a multiplication table of a finite-dimensional finitely-presented Lie ring. Secondly, we give relations that are equivalent to the n$n$-Engel condition, and only have to be checked for the elements of a basis of a Lie ring. We apply this to construct the freest t$t$-generator Lie rings that satisfy the n$n$-Engel condition, for (t,n)=(2,3),(3,3),(4,3),(2,4)$(t,n)=(2,3),(3,3),(4,3),(2,4)$.