26340659
Combinatorial properties of mesh of trees
A mesh of trees, which has two favorable properties: small diameter and large bisection, is known as the fastest network when considered in terms of speed. We show that the wide diameter, fault diameter, and Rabin number, which are three generalizations of diameter, of a two dimensional 2/sup n//spl times/2/sup n/ mesh of trees are equal to 5n+1.
13201367
Generalized Diameters of the Mesh of Trees
Abstract
The mesh of trees, which owns two favorable properties, small diameter and large bisection,
is known as the fastest network when considered in terms of speed. In this paper we show that
the wide diameter, fault diameter and Rabin number, which are three generalizations of diameter,
of a two-dimensional 2n×2n mesh of trees are equal to 5n + 1.


14040084
Divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures
An elementary approach is given to studying the recurrence relations associated with generalized heaps (or d-heaps), cost of optimal merge, and generalized divide-and-conquer minimization problems. We derive exact formulae for the solutions of all such recurrences and give some applications. In particular, we present a precise probabilistic analysis of Floyd's algorithm for constructing d-heaps when the input is randomly given. A variant of d-heap having some interesting combinatorial properties is also introduced.
5887540
An Algorithm for Computing a New Normal Form for Dynamical Systems
We propose in this paper a new normal form for dynamical systems or vector fields which improves the classical normal forms in the sense that it is a further reduction of the classical normal forms. We give an algorithm for an effective computation of these normal forms. Our approach is rational in the sense that if the coefficients of the system are in a field K(which, in practice, is Q, R), so is the normal form and all computations are done inK . As a particular case, if the matrix of the linear part is a companion matrix then we reduce the dynamical system to a single differential equation. Our method is applicable for both the nilpotent and the non-nilpotent cases. We have implemented our algorithm in Maple V and obtained many examples of the further reduced normal forms up to some finite order.
2548796
Four types of lookback
We present a classification that groups lookback into four types: direct strong lookback, universal strong lookback, direct weak lookback, and universal weak lookback. They are defined in terms of absolute and dynamic impact times. We discuss relationships between lookback types by considering when rollbacks and/or antimessages are avoided. From different types of lookback, we also derive three optimization techniques for optimistic simulation and point out their advantages over lazy cancellation. Finally, we show that all four types of lookback exist in the PCS network simulation and can be exploited by either lookback-based or optimistic protocols.
30765152
On the Quickest Path Problem
Abstract Let N be an input network and σ be the amount of data to be transmitted. We present an O( mn 2 ) time algorithm that finds all-pairs quickest paths, for a given value of σ, and show that the quickest path between any two nodes for any value of σ can be found in O(log m ) time, provided O( mn 2 ) preprocessing time is spent.
17483991
Energy-aware computation duplication for improving reliability in embedded chip multiprocessors
Compilers designed for current embedded systems must be capable of addressing multiple constraints such as low power, high performance, small memory footprint and form factor, and high reliability at the same time. In particular, optimizing for one constraint should be performed carefully, considering its impact on other constraints. Recent trends indicate that transient errors are becoming increasingly important in embedded systems. Focusing on an embedded chip multiprocessor and array-intensive applications, this paper demonstrates how reliability against transient errors can be improved without impacting execution time by utilizing idle processors for duplicating some of the computations of the active processors. It also shows how a balance between power savings and reliability improvement can be struck using a metric called the energy-delay-fallibility product. Our experimental results indicate that the "percentage of duplicated computations" is a useful high-level metric for studying the tradeoffs among performance, power, and reliability
37185470
An ILP-Based Approach to Locality Optimization
One of the most important factors that determine performance of data-intensive applications is data locality. A program with high data locality makes better use of fast, on-chip memories and can avoid large main memory latencies. Although previous compiler research investigated numerous techniques for enhancing locality, we lack of formal techniques, against which the existing heuristics can be compared. Motivated by this observation, this paper presents a fresh look at locality optimization based on integer linear programming (ILP). We formulate the conditions for data locality, and present a system of constraints whose solution gives optimal computation re-ordering and data-to-memory assignment under our objective function and cost model. Our experimental results using three data-intensive applications clearly indicate that the ILP-based approach generates very good results and outperforms a previously proposed heuristic solution to locality.