14594677
Techniques and tools for dynamic optimization
Traditional code optimizers have produced significant performance improvements over the past forty years. While promising avenues of research still exist, traditional static and profiling techniques have reached the point of diminishing returns. The main problem is that these approaches have only a limited view of the program and have difficulty taking advantage of the actual run-time behavior of a program. We are addressing this problem through the development of a dynamic optimization system suited for aggressive optimization - using the full power of the most beneficial optimizations. We have designed our optimizer to operate using a software dynamic translation (SDT) execution system. Difficult challenges in this research include reducing SDT overhead and determining what optimizations to apply and where in the code to apply them. Another challenge is having the necessary tools to ensure the reliability of software that is dynamically optimized. In this paper, we describe our efforts in reducing overhead in SDT and efficient techniques for instrumenting the application code. We also describe our approach to determine what and where an optimization should be applied. We discuss other fundamental issues in developing a dynamic optimizer and finally present a basic debugger for SDT systems
13254850
Profile guided management of code partitions for embedded systems
Researchers have proposed to divide embedded applications into code partitions and to download partitions on demand from a wireless code server to enable a diverse set of applications for very tightly constrained embedded systems. This paper describes a new approach for managing the request and storage of code partitions and we explore the benefits of our scheme.
815725
Virtual Execution Environments: Support and Tools
In today's dynamic computing environments, the available resources and even underlying computation engine can change during the execution of a program. Additionally, current trends in software development favor the flexibility and cost-effectiveness of dynamically loaded components and libraries. Because of these trends, there has been increased research interest in virtual execution environments (VEEs) for delivering adaptable software suitable for today's rapidly changing, heterogeneous computing environments. In this project, we have been investigating tools and techniques to support implementation of VEEs using software dynamic translation (SDT). This paper highlights some of our recent results. One significant result is that we have developed novel translation techniques that reduce the memory and runtime overhead of SDT to negligible levels. We have also developed innovative debugging and instrumentation tools for SDT-based software environments. Together, these results make SDT-based systems viable for solving a wide range of pressing problems. The paper concludes with a discussion of how SDT may offer a solution to one such problem-inherent process variation in emerging chip multiprocessors.
135505
Image based regression using boosting method
We present a general algorithm of image based regression that is applicable to many vision problems. The proposed regressor that targets a multiple-output setting is learned using boosting method. We formulate a multiple-output regression problem in such a way that overfitting is decreased and an analytic solution is admitted. Because we represent the image via a set of highly redundant Haar-like features that can be evaluated very quickly and select relevant features through boosting to absorb the knowledge of the training data, during testing we require no storage of the training data and evaluate the regression function almost in no time. We also propose an efficient training algorithm that breaks the computational bottleneck in the greedy feature selection process. We validate the efficiency of the proposed regressor using three challenging tasks of age estimation, tumor detection, and endocardial wall localization and achieve the best performance with a dramatic speed, e.g., more than 1000 times faster than conventional data-driven techniques such as support vector regressor in the experiment of endocardial wall localization.
12615212
Finite locally-quasiprimitive graphs
A finite graph is said to be locally-quasiprimitive relative to a subgroup G of automorphisms if, for all vertices α, the stabiliser in G of α is quasiprimitive on the set of vertices adjacent to α. (A permutation group is said to be quasiprimitive if all of its non-trivial normal subgroups are transitive.) The graph theoretic condition of local quasiprimitivity is strictly weaker than the conditions of local primitivity and 2-arc transitivity which have been studied previously. It is shown that the family of locally-quasiprimitive graphs is closed under the formation of a certain kind of quotient graph, called a normal quotient, induced by a normal subgroup. Moreover, a locally-quasiprimitive graph is proved to be a multicover of each of its normal quotients. Thus finite locally-quasiprimitive graphs which are minimal in the sense that they have no non-trivial proper normal quotients form an important sub-family, since each finite locally-quasiprimitive graph has at least one such graph as a normal quotient. These minimal graphs in the family are called "basic" locally-quasiprimitive graphs, and their structure is analysed. The process of constructing locally-quasiprimitive graphs with a given locally-quasiprimitive graph Σ as a normal quotient is then considered. It turns out that this can be viewed as a problem of constructing covering graphs of certain multigraphs associated with Σ. Further, it is shown that, under certain conditions, a locally-quasiprimitive graph can be reconstructed from knowledge of two of its normal quotients. Finally a series of open problems is presented.
5971410
Time-space consistency in large-scale distributed virtual environments
Maintaining a consistent view of the simulated world among different simulation nodes is a fundamental problem in large-scale distributed virtual environments (DVEs). In this paper, we characterize this problem by quantifying the time-space inconsistency in a DVE. To this end, a metric is defined to measure the time-space inconsistency in a DVE. One major advantage of the metric is that it may be estimated based on some characteristic parameters of a DVE, such as clock asynchrony, message transmission delay, the accuracy of the dead reckoning algorithm, the kinetics of the moving entity, and human factors. Thus the metric can be used to evaluate the time-space consistency property of a DVE without the actual execution of the DVE application, which is especially useful in the design stage of a DVE. Our work also clearly shows how the characteristic parameters of a DVE are interrelated in deciding the time-space inconsistency, so that we may fine-tune the DVE to make it as consistent as possible. To verify the effectiveness of the metric, a Ping-Pong game is developed. Experimental results show that the metric is effective in evaluating the time-space consistency property of the game.
6042519
Imprimitive symmetric graphs, 3-arc graphs and 1-designs
Let Γ be a G-symmetric graph admitting a nontrivial G-invariant partition B. For B ∈ B, let D(B)=(B,ΓB(B),I) be the 1-design in which αIC for α ∈ B and C ∈ ΓR(B) if and only if α is adjacent to at least one vertex of C, where ΓB(B) is the neighbourhood of B in the quotient graph ΓB of Γ relative to B. In a natural way the setwise stabilizer GB of B in G induces a group of automorphisms of D(B). In this paper, we study those graphs Γ such that the actions of GB on B and ΓB(B) are permutationally equivalent, that is, there exists a bijection ρ :B → ΓB(B) such that ρ(αx) = (ρ(α))x for α ∈ B and x ∈ GB. In this case the vertices of Γ can be labelled naturally by the arcs of B. By using this labelling technique we analyse ΓB, D(B) and the bipartite subgraph Γ[B, C] induced by adjacent blocks B, C of B, and study the influence of them on the structure of Γ. We prove that the class of such graphs Γ is precisely the class of those graphs obtained from G-symmetric graphs Σ and self-paired G-orbits on 3-arcs of Σ by a construction introduced in a recent paper of Li, Praeger and the author, and that Γ can be reconstructed from ΓB via this construction.
8520561
Bounding the bandwidths for graphs
Let G;H be nite graphs with jV(H)j>jV(G)j. The bandwidth of G with respect to H is dened to be BH(G) = minmaxuv2E(G)dH((u);(v)), with the minimum taken over all injections from V(G )t oV(H), where dH(x;y) is the distance in H between two vertices x;y 2 V(H). This number is involved with the VLSI design and optimization, especially when the \host" graph H is a path Pn or a cycle Cn of length n = jV(G)j. In these two cases, BH(G) is known to be the ordinary bandwidth B(G) and the cyclic bandwidth Bc(G), respectively, and the corresponding decision problem is NP-complete. So estimations of B(G), Bc(G) and in general BH(G) are needed, especially in determining the bandwidths of some specic graphs. In this paper, we rst propose a systematic method for obtaining lower bounds for the bandwidth BH(G). By using this method, we then get a number of lower bounds for B(G) and Bc(G )i n terms of some distance- and degree-related parameters. c 2000 Elsevier Science B.V. All rights reserved.