Search

Improving the performance of applications is a core target of computer systems research and has led to the creation of various techniques. Among them is function memoization, an intuitive technique that, unfortunately, failed to live up to its promised potential. Traditional function memoization falls short mainly because it is input-based, meaning the system needs to pattern-match the current invocations inputs with previously seen ones to decide which memoized output value to return. This is often computationally intensive and only suitable for a limited set of functions. However, function calls often exhibit temporal value locality on their output. We capitalize on this observation to create the first output-based function memoization technique. We demonstrate that compiler-directed output-based memoization reduces energy and runtime by 50 to 75 percent (2-4x speedup) at the cost of a relatively small degradation of the applications output quality. [ABSTRACT FROM AUTHOR]

In many applications, there is a need to identify to which of a group of sets an element $x$ belongs, if any. For example, in a router, this functionality can be used to determine the next hop of an incoming packet. This problem is generally known as set separation and has been widely studied. Most existing solutions make use of hash-based algorithms, particularly when a small percentage of false positives is allowed. A known approach is to use a collection of Bloom filters in parallel. Such schemes can require several memory accesses, a significant limitation for some implementations. We propose an approach using Block Bloom Filters, where each element is first hashed to a single memory block that stores a small Bloom filter that tracks the element and the set or sets the element belongs to. In a naïve solution, when an element $x$ in a set $S$ is stored, it necessarily increases the false positive probability for finding that $x$ is in another set $T$. In this paper, we introduce our One Memory Access Set Separation (OMASS) scheme to avoid this problem. OMASS is designed so that for a given element $x$, the corresponding Bloom filter bits for each set map to different positions in the memory word. This ensures that the false positive rates for the Bloom filters for element $x$ under other sets are not affected. In addition, OMASS requires fewer hash functions compared to the naïve solution. [ABSTRACT FROM PUBLISHER]

Software maintainers use the traces of field failures to understand and diagnose faulty functions that cause the system to fail. Despite their usefulness, traces from the field can be quite overwhelming, especially for software systems with a vast client base. In the execution of realistic applications, many of them being millions of lines of code, there are just too many traces that are generated. In addition, traces are known to be extraordinarily large, which further complicates matters. Fortunately, not all field failures are caused by new faults. In fact, previous studies showed that 50% to 90% of field failures are due to previously known faults. In this paper, we propose a machine learning approach that automatically detects recurring faulty functions in the traces of new field failures. We achieve our goal by training decision trees on earlier resolved traces of system failures from the current and prior releases of the system. When applied to a large industrial system with 20 million lines of code and 200,000 functions, our approach was able to detect recurring faulty functions in the traces of field failures with an accuracy of 90%, to even 97% in some cases. [ABSTRACT FROM PUBLISHER]

Although several distance or similarity functions for trees have been introduced, their performance is not always satisfactory in many applications, ranging from document clustering to natural language processing. This research proposes a new similarity function for trees, namely Extended Subtree (EST), where a new subtree mapping is proposed. EST generalizes the edit base distances by providing new rules for subtree mapping. Further, the new approach seeks to resolve the problems and limitations of previous approaches. Extensive evaluation frameworks are developed to evaluate the performance of the new approach against previous proposals. Clustering and classification case studies utilizing three real-world and one synthetic labeled data sets are performed to provide an unbiased evaluation where different distance functions are investigated. The experimental results demonstrate the superior performance of the proposed distance function. In addition, an empirical runtime analysis demonstrates that the new approach is one of the best tree distance functions in terms of runtime efficiency. [ABSTRACT FROM AUTHOR]

Many practical methods and different approaches have been proposed to assess Multi-State Systems (MSS) reliability measures. The universal generating function (UGF) method, introduced in 1986, is known to be a very efficient way of evaluating the availability of different types of MSSs. In this paper, we propose an extension of the UGF method considering epistemic uncertainties. This extended method allows one to model ill-known probabilities and transition rates, or to model both aleatory and epistemic uncertainty in a single model. It is based on the use of belief functions which are general models of uncertainty. We also compare this extension with UGF methods based on interval arithmetic operations performed on probabilistic bounds. [ABSTRACT FROM AUTHOR]

Given a set of objects $(P)$ and a set of ranking functions $(F)$ over $(P)$, an interesting problem is to compute the top ranked objects for all functions. Evaluation of multiple top-$(k)$ queries finds application in systems, where there is a heavy workload of ranking queries (e.g., online search engines and product recommendation systems). The simple solution of evaluating the top-$(k)$ queries one-by-one does not scale well; instead, the system can make use of the fact that similar queries share common results to accelerate search. This paper is the first, to our knowledge, thorough study of this problem. We propose methods that compute all top-$(k)$ queries in batch. Our first solution applies the block indexed nested loops paradigm, while our second technique is a view-based algorithm. We propose appropriate optimization techniques for the two approaches and demonstrate experimentally that the second approach is consistently the best. Our approach facilitates evaluation of other complex queries that depend on the computation of multiple top-$(k)$ queries, such as reverse top-$(k)$ and top-$(m)$ influential queries. We show that our batch processing technique for these complex queries outperform the state-of-the-art by orders of magnitude. [ABSTRACT FROM AUTHOR]

Independent component analysis (ICA) problem is often posed as the maximization/minimization of an objective/cost function under a unitary constraint, which presumes the prewhitening of the observed mixtures. The parallel adaptive algorithms corresponding to this optimization setting, where all the separators are jointly trained, are typically implemented by a gradient-based update of the separation matrix followed by the so-called symmetrical orthogonalization procedure to impose the unitary constraint. This article addresses the convergence analysis of such algorithms, which has been considered as a difficult task due to the complication caused by the minimum-(Frobenius or induced 2-norm) distance mapping step. We first provide a general characterization of the stationary points corresponding to these algorithms. Furthermore, we show that fixed point algorithms employing symmetrical orthogonalization are monotonically convergent for convex objective functions. We later generalize this convergence result for nonconvex objective functions. At the last part of the article, we concentrate on the kurtosis objective function as a special case. We provide a new set of critical points based on Householder reflection and we also provide the analysis for the minima/maxima/saddle-point classification of these critical points. [ABSTRACT FROM AUTHOR]

Maximum-likelihood estimation subject to nonlinear measurement functions is generally performed through optimization algorithms when accuracy is required and enough processing time is available, or with recursive filters for real-time applications but at the expense of a loss of accuracy. In this paper, we propose a new estimator for parameter estimation based on a polynomial approximation of the measurement signal. The raw dataset is replaced by n + 1 independent polynomial samples (PS) for a smoothing polynomial of order n, resulting in a reduction of the computational burden. It is shown that the PSs must be sampled at some deterministic instants and an approximate formula for the variance of the PSs is also provided. Moreover, it is also proved and illustrated on three examples that the new estimator which processes the PSs is equivalent to the standard maximum-likelihood estimator based on the raw dataset, provided that the measurement function and its first derivatives can be approximated with a polynomial of order n. Since this algorithm proceeds from a compact representation of a measurement signal, it can find applications in real-time processing, power saving processing, or estimation based on compressed data, even if this latter field has not been investigated from a theoretical perspective. Its structure which is made up of several separate tasks is also adapted to distributed processing problems. Because the performance of the method is related to the polynomial approximation quality, the algorithm is well suited for smooth measurement functions like in trajectory estimation applications. [ABSTRACT FROM AUTHOR]

This paper addresses the schedulability problem of periodic and sporadic real-time task sets with constrained deadlines preemptively scheduled on a multiprocessor platform composed by identical processors. We assume that a global work-conserving scheduler is used and migration from one processor to another is allowed during a task lifetime. First, a general method to derive schedulability conditions for multiprocessor real-time systems will be presented. The analysis will be applied to two typical scheduling algorithms: Earliest Deadline First (EDF) and Fixed Priority (FP). Then, the derived schedulability conditions will be tightened, refining the analysis with a simple and effective technique that significantly improves the percentage of accepted task sets. The effectiveness of the proposed test is shown through an extensive set of synthetic experiments. [ABSTRACT FROM AUTHOR]

In this work, we study the computational perspective of network coding, focusing on two issues. First, we address the computational complexity of finding a network code for acyclic multicast networks. Second, we address the issue of reducing the amount of computation performed by network nodes. In particular, we consider the problem of finding a network code with the minimum possible number of encoding nodes, i.e., nodes that generate new packets by performing algebraic operations on packets received over incoming links. We present a deterministic algorithm that finds a feasible network code for a multicast network over an underlying graph G(V, E) in time O(∣E∣kh + ∣V∣k²h² + h4k³(k + h)), where k is the number of destinations and h is the number of packets. Our algorithm improves the best known running time for network code construction. In addition, our algorithm guarantees that the number of encoding nodes in the obtained network code is upper-bounded by O(h³k²). Next, we address the problem of finding integral and fractional network codes with the minimum number of encoding nodes. We prove that in the majority of settings this problem is NP-hard. However, we show that if h, = O(1), k = O(1), and the underlying communication graph is acyclic, then there exists an algorithm that solves this problem in polynomial time. [ABSTRACT FROM AUTHOR]

Flash memory has been widely adopted in various consumer products for information storage, especially for embedded systems. With strong demands on product designs for overhead control and performance requirements, vendors must have an effective design for the mapping of logical block addresses (LBAs) and physical addresses of data over flash memory. This paper targets such an essential issue by proposing a configurable mapping method that could trade the main-memory overhead with the system performance under the best needs of vendors. A series of experiments is conducted to provide insights on different configurations and the proposed method, compared to existing implementations. [ABSTRACT FROM AUTHOR]

A high-performance architecture of elliptic curve scalar multiplication based on the Montgomery ladder method over finite field CF(2m) is proposed. A pseudopipelined word-serial finite field multiplier, with word size w, suitable for the scalar multiplication is also developed, Implemented in hardware, this system performs a scalar multiplication in approximately 6[m/w](m - 1) clock cycles, and the gate delay in the critical path is equal to TAND + log2(w/k)]TXOR, where TAND and TXOR are delays due to two-input AND and XOR gates, respectively, and 1 ≤ k ⪡ w is used to shorten the critical path. [ABSTRACT FROM AUTHOR]

The problem of computing functions of values at the nodes in a network in a fully distributed manner, where nodes do not have unique identities and make decisions based only on local information, has applications in sensor, peer-to-peer, and ad hoc networks. The task of computing separable functions, which can be written as linear combinations of functions of individual variables, is studied in this context. Known iterative algorithms for averaging can be used to compute the normalized values of such functions, but these algorithms do not extend, in general, to the computation of the actual values of separable functions. The main contribution of this paper is the design of a distributed randomized algorithm for computing separable functions. The running time of the algorithm is shown to depend on the running time of a minimum computation algorithm used as a subroutine. Using a randomized gossip mechanism for minimum computation as the sub-routine yields a complete fully distributed algorithm for computing separable functions. For a class of graphs with small spectral gap, such as grid graphs, the time used by the algorithm to compute averages is of a smaller order than the time required by a known iterative averaging scheme. [ABSTRACT FROM AUTHOR]

Most Web applications exchange data as XML, but they create and process this data with languages that don't have native support for XML. With appropriate middleware, XQuery can dramatically simplify this process, treating all data sources as though they were XML. This article shows how to use XQuery for native XML processing and data integration, briefly explores other technologies used in the same space, and discusses some XQuery extensions for scripting and updates that are under way. [ABSTRACT FROM AUTHOR]

The authors discuss Universal Multimedia Access (UMA), which promises to adaptively deliver multimedia content to users according to their needs. Central to UMA is the development of metadata standards for describing multimedia resources to allow their adaptation. The authors report on the development of the Bitstream Syntax Description Language (BSDL), which allows computers to perform operations on data without requiring specific software for every format they might encounter. The article describes applications for scalable content adaptation, format independent streaming, and delivery and configurable media coding.

This paper presents an efficient and accurate high-level software energy estimation methodology using the concept of characterization-based macromodeling. In characterization-based macromodeling, a function or subroutine is characterized using an accurate lower level energy model of the target processor to construct a macromodel that relates the energy consumed in the function under consideration to various parameters that can be easily observed or calculated from a high-level programming language description. The constructed macromodels eliminate the need for significantly slower instruction-level interpretation or hardware simulation that is required in conventional approaches to software energy estimation. The authors present two different approaches to macromodeling for embedded software that offer distinct efficiency-accuracy characteristics: 1) complexity-based macromodeling, where the variables that determine the algorithmic complexity of the function under consideration are used as macromodeling parameters and 2) profiling-based macromodeling, where internal profiling statistics for the functions are used as the parameters in the energy macromodels. The authors have experimentally validated their software energy macromodeling techniques on a wide range of embedded software routines and two different target processor architectures. The experiments demonstrate that high-level macromodels constructed using the proposed techniques are able to estimate the energy consumption to within 94% accuracy on the average, while commanding speedups of one to five orders-of-magnitude over current instruction-level and architectural energy estimation techniques. This paper presents an efficient and accurate high-level software energy estimation methodology using the concept of characterization-based macromodeling. In characterization-based macromodeling, a function or subroutine is characterized using an accurate lower level energy model of the target processor to... [ABSTRACT FROM AUTHOR]

Recommends an algorithm for the automatic transformation of sequential programs into parallel code. Pitfalls of transforming sequential programs manually into parallel code; Details on the process of parallelizing subroutines; Information the steps of the algorithm.

Discusses the application of Engineering Work Station(EWS) and the Personal Computer(PC) which comprises a license-royalty free and portable graphical utilities for various electromagnetic problems in the computational electromagnetism. Plotter subroutine program; Application of g12ps and xg12ps; Implementation of xngraph; Conclusions.

A significant barrier to the reuse of software is the rigid interface presented by a subroutine. For nontrivial data structures, it is unlikely that the existing form of the data of an application will match the requirements of a separately written subroutine. We describe two methods of interfacing existing data to a subroutine: generation of a program to convert the data to the form needed by the subroutine, and rewriting the subroutine, through compilation, to fit the existing data. Both methods can be invoked through easily used menu-based negotiation with the user. These methods have been implemented using the GLISP language and compiler. [ABSTRACT FROM AUTHOR]

Several inequalities are derived for use in certifying function subroutines by means of black box testing. It is assumed that a function is approximated by means of a polynomial of limited degree on a closed interval. These inequalities give upper bounds on the error of the approximation over the entire interval based on the error measured over a finite sample and known properties of the function. [ABSTRACT FROM AUTHOR]

In the presence of an internal state, often a sequence of function calls is required to test software. In fact, to cover a particular branch of the code, a sequence of previous function calls might be required to put the internal state in the appropriate configuration. Internal states are not only present in object-oriented software, but also in procedural software (e.g., static variables in C programs). In the literature, there are many techniques to test this type of software. However, to the best of our knowledge, the properties related to the choice of the length of these sequences have received only a little attention in the literature. In this paper, we analyze the role that the length plays in software testing, in particular branch coverage. We show that, on “difficult” software testing benchmarks, longer test sequences make their testing trivial. Hence, we argue that the choice of the length of the test sequences is very important in software testing. Theoretical analyses and empirical studies on widely used benchmarks and on an industrial software are carried out to support our claims. [ABSTRACT FROM PUBLISHER]

High confidence in floating-point programs requires proving numerical properties of final and intermediate values. One may need to guarantee that a value stays within some range, or that the error relative to some ideal value is well bounded. This certification may require a time-consuming proof for each line of code, and it is usually broken by the smallest change to the code, e.g., for maintenance or optimization purpose. Certifying floating-point programs by hand is, therefore, very tedious and error-prone. The Gappa proof assistant is designed to make this task both easier and more secure, due to the following novel features: It automates the evaluation and propagation of rounding errors using interval arithmetic. Its input format is very close to the actual code to validate. It can be used incrementally to prove complex mathematical properties pertaining to the code. It generates a formal proof of the results, which can be checked independently by a lower level proof assistant like Coq. Yet it does not require any specific knowledge about automatic theorem proving, and thus, is accessible to a wide community. This paper demonstrates the practical use of this tool for a widely used class of floating-point programs: implementations of elementary functions in a mathematical library. [ABSTRACT FROM AUTHOR]