Wave envelope technique for multimode wave guide problems

In this paper we propose a fast method for solving wave guide problems. In particular, we consider the guide to be inhomogeneous, and allow propagation of waves of higher-order modes. Such techniques have been handled successfully for acoustic wave propagation problems with single mode and finite length. This paper extends this concept to electromagnetic wave guides with several modes and infinite in length. The method is shown and results of computations are presented.Research was supported by the National Aeronautics and Space Administration under NASA Contract No. NAS1-18107 while the first author was in residence at the ICASE, NASA Langley Research Center, Hampton, VA 23665-5225, and by NASA Grant No. NAG-1-624.     

Semi-automatic process partitioning for parallel computation

Automatic process partitioning is the operation of automatically rewriting an algorithm as a collection of tasks, each operating primarily on its own portion of the data, to carry out the computation in parallel. Hybrid shared memory systems provide a hierarchy of globally accessible memories. To achieve high performance on such machines one must carefully distribute the work and the data so as to keep the workload balanced while optimizing the access to nonlocal data. In this paper we consider a semi-automatic approach to process partitioning in which the compiler, guided by advice from the user, automatically transforms programs into such an interacting set of tasks. This approach is illustrated with a picture processing example written in BLAZE, which is transformed by the compiler into a task system maximizing locality of memory reference.Research supported by an IBM Graduate Fellowship.Research supported under NASA Contract No. 520-1398-0356.Research supported by NASA Contract No. NAS1-18107 while the last two authors were in residence at ICASE, NASA, Langley Research Center.     

Approximate algorithms for partitioning problems

We consider the problem of optimally assigning the modules of a parallel/pipelined program over the processors of a multiple processor system under certain restrictions on the interconnection structure of the program as well as the multiple computer system. We show that for a variety of such problems, it is possible to find if a partition of the modular program exists in which the load on any processor is whithin a certain bound. This method when combined with a binary search over a fixed range, provides an optimal solution to the partitioning problem.The specific problems we consider are partitioning of (1) a chain structured parallel program over a chain-like computer system, (2) multiple chain-like programs over a host-satellite system, and (3) a tree structured parallel program over a host-satellite system.For a problem withN modules andM processors, the complexity of our algorithm is no worse thanO(Mlog(N)log(W _T/)), whereW _T is the cost of assigning all modules to one processors, and the desired accuracy. This algorithm provides an improvement over the recently developed best known algorithm that runs inO(MNlog(N)) time.This Research was supported by a grant from the Division of Research Extension and Advisory Services, University of Engineering and Technology Lahore, Pakistan. Further support was provided by NASA Contracts NAS1-17070 and NAS1-18107 while the author was resident at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, Virginia, USA.     

Numerical experiments on the accuracy of ENO and modified ENO schemes

In this paper we make further numerical experiments assessing an accuracy degeneracy phenomena reported by A. Rogerson and E. Meiburg (this issue, 1990). We also propose a modified ENO scheme, which recovers the correct order of accuracy for all the test problems with smooth initial conditions and gives results comparable to the original ENO schemes for discontinuous problems.Research supported by NSF grant No. DMS88-10150, NASA Langley contract No. NAS1-18605, and AFOSR grant No. 90-0093. Computation supported by NAS.     

A trust-region framework for managing the use of approximation models in optimization

This paper presents an analytically robust, globally convergent approach to managing the use of approximation models of varying fidelity in optimization. By robust global behaviour we mean the mathematical assurance that the iterates produced by the optimization algorithm, started at an arbitrary initial iterate, will converge to a stationary point or local optimizer for the original problem. The approach presented is based on the trust region idea from nonlinear programming and is shown to be provably convergent to a solution of the original high-fidelity problem. The proposed method for managing approximations in engineering optimization suggests ways to decide when the fidelity, and thus the cost, of the approximations might be fruitfully increased or decreased in the course of the optimization iterations. The approach is quite general. We make no assumptions on the structure of the original problem, in particular, no assumptions of convexity and separability, and place only mild requirements on the approximations. The approximations used in the framework can be of any nature appropriate to an application; for instance, they can be represented by analyses, simulations, or simple algebraic models. This paper introduces the approach and outlines the convergence analysis.This research was supported by the Dept. of Energy grant DEFG03-95ER25257 and Air Force Office of Scientific Research grant F49620-95-1-0210This research was supported by the National Aeronautics and Space Administration under NASA Contract No. NAS1-19480 while the author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23681, USAThis research was supported by the Air Force Office of Scientific Research grant F49620-95-1-0210 and by the National Aeronautics and Space Administration under NASA Contract No. NAS1-19480 while the author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23681, USA     

A note on the accuracy of spectral method applied to nonlinear conservation laws

Fourier spectral method can achieve exponential accuracy both on the approximation level and for solving partial differential equations if the solutions are analytic. For a linear PDE with discontinuous solutions, Fourier spectral method will produce poor point-wise accuracy without post-processing, but still maintains exponential accuracy for all moments against analytic functions. In this note we assess the accuracy of Fourier spectral method applied to nonlinear conservation laws through a numerical case study. We have found out that the moments against analytic functions are no longer very accurate. However the numerical solution does contain accurate information which can be extracted by a Gegenbauer polynomial based post-processing.Research supported by ARO Grant DAAL03-91-G-0123 and DAAH04-94-G-0205, NSF Grant DMS-9211820, NASA Grant NAG1-1145 and contract NAS1-19480 while the first author was in residence at ICASE, NASA Langley Research Center, Hampton, Virginia 23681-0001, and AFOSR Grant 93-0090.     

Implementation of a parallel unstructured Euler solver on shared- and distributed-memory architectures

An efficient three-dimensional unstructured Euler solver is parallelized on a CRAY Y-MP C90 shared-memory computer and on an Intel Touchstone Delta distributed-memory computer. This paper relates the experiences gained and describes the software tools and hardware used in this study. Performance comparisons between the two differing architectures are made.This work was sponsored in part by ARPA (NAG-1-1485) and by NASA Contract No. NAS1-19480 while authors Mavriplis, Saltz and Das were in residence at ICASE, NASA Langley Research Center, Hampton, Virginia. This research was performed in part using the Intel Touchstone Delta System operated by Caltech on behalf of the Concurrent Supercomputing Consortium. Access to this fecility was provided by NASA Langley Research Center and the Center for Research in Parallel Processing. The content of the information does not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred.     

Multitasking a Navier-Stokes algorithm on the CRAY-2

This paper presents the results of multitasking a Navier-Stokes algorithm on the CRAY-2. The algorithm is a compact difference scheme for the solution of the incompressible, two-dimensional, time-dependent Navier-Stokes equations. Two implementations of multitasking on the CRAY-2 are considered: macrotasking (parallelism at the subroutine level) and microtasking (parallelism at the do-loop level). These two techniques are briefly described. The implementation of the algorithm is discussed in relation to these techniques, and the results for three problem sizes are presented. The timing results for both techniques are, in general, comparable with differences ranging between 2% and 14%, depending on the problem size. The best achieved speedup in a dedicated environment is 3.62 for macrotasking and 3.32 for microtasking. The task granularity for both techniques is computed, and the synchronization costs are estimated. For macrotasks of granularity of up to 0.5 msec, microtasking outperformed macrotasking, while the latter outperformed the former for granularity of over one msec.This research was supported by NASA Contract No. NAS2-11555 while the author was an employee of Sterling Software under contract to the Numerical Aerodynamic Simulation Systems Divison at NASA Ames Research Center, Moffett Field, CA 94035.     

Predicting Price/Performance Trade-offs for Whitney: A Commodity Computing Cluster

We couple simple performance models with pricing to optimize the design of clusters built from commodity components for scientific computing. We apply this technique using the NAS Parallel Benchmarks as a representative workload. We develop models of the BT, LU, and SP benchmarks. The models consist of closed form expressions based on problem size, number of processors, and three measured quantities (single processor performance, network latency, and network bandwidth). These models predict benchmark performance to within 30%. This technique was used in the design of Whitney, a commodity computing cluster at NASA Ames Research Center. In particular, for systems costing less than $1,000,000, the performance characteristics of Intel Pentium processors are better matched to the slower (and less expensive) Fast Ethernet, than to the faster (and more expensive) Myricom Myrinet.     

An algorithm for optimal single linear feature extraction from several gaussian pattern classes

A computational algorithm is presented for the extraction of an optimal single linear feature from several Gaussian pattern classes. The algorithm minimizes the increase in the probability of misclassification in the transformed (feature) space. The general approach used in this procedure was developed in a recent paper by R. J. P. de Figueiredo.⁽¹⁾ Numerical results on the application of this procedure to the remotely sensed data from the Purdue C1 flight line as well asLandsat data are presented. It was found that classification using the optimal single linear feature yielded a value for the probability of misclassification on the order of 30% less than that obtained by using the best single untransformed feature. The optimal single linear feature gave performance results comparable to those obtained by using the two features which maximized the average divergence. Also discussed are improvements in classification results using this method when the size of the training set is small.This work was supported by the Air Force Office of Scientific Research under Grant 75-2777 and by the National Aeronautics and Space Administration under contract NAS 9-12776.     

Constrained Ordinal Optimization—A Feasibility Model Based Approach

Ordinal Optimization (OO) is a useful simulation-based approach for stochastic optimization problems such as the problems in Discrete Event Dynamic Systems (DEDS). However, OO cannot be applied directly for the problem since many infeasible decisions cannot be excluded from ordinal comparison without extensive computation involving the expectation operation. In this paper, a new approach for solving constrained ordinal optimization (COO) problems is presented. The key idea of our method for constrained OO problems is to estimate the feasibility of decisions and to choose selected subset based on the estimated feasibility. Any crude method such as the one based on rough set theory developed in our previous work can be applied to determine the decision feasibility efficiently. The algorithm for subset selection and the procedure of Blind Picking with Feasibility Model (BPFM) for COO are derived in the paper. The infeasible decisions are excluded by an imperfect feasibility model in the procedure of subset selection. The performance of the new method is evaluated and compared with the regular OO method. Numerical testing with two examples including the planning problem of a practical remanufacturing system shows that to meet the same required alignment probability, BPFM is more efficient than pure Blind Picking in regular OO. The research presented in this paper is supported in part by the National Outstanding Young Investigator Grant (6970025), National Science Foundation (60243001, 60274011, 60574067) and 863 High Tech Development Plan (2001AA413910) of China. The research effort of Ho is supported in part by U.S. Army Research Office (contract DAAD19-01-1-0610), U.S. Air Force Office of Scientific Research (contract F49620-01-1-0288).     

A formalization of priority inversion

A priority inversion occurs when a low-priority task causes the execution of a higher-priority task to be delayed. The possibility of priority inversions complicates the analysis of systems that use priority-based schedulers because priority inversions invalidate the assumption that a task can be delayed by only higher-priority tasks. This paper formalizes priority inversion and gives sufficient conditions as well as some new protocols for preventing priority inversions.Supported by the Commission of the European Communities under the ESPRIT Programme Basic Research Action Number 3092 (Predictably Dependable Computing Systems) and the Italian Ministry of Research and University, and in part by the Defense Advanced Research Projects Agency (DoD) under NASA Ames grant number NAG-2-593.Supported in part by the Defense Advanced Research Projects Agency (DoD) under NASA Ames grant number NAG 2-593, and by grants from IBM T.J. Watson Research Laboratory, the IBM Endicott Programming Laboratory, Siemens RTL, and Xerox Webster Research Center.Supported in part by the Office of Naval Research under contract N00014-91-J-1219, the National Science Foundation under Grant No. CCR-8701103, DARPA/NSF Grant No. CCR-9014363, and by the IBM Endicott Programming Laboratory.     

Unifying stabilization and termination in message-passing systems

The paper dispels the myth that it is impossible for a message-passing program to be both terminating and stabilizing. We consider a rather general notion of termination: a terminating program eventually stops its execution after the environment ceases to provide input. We identify termination-symmetry to be a necessary condition for a problem to admit a solution with such properties. Our results do confirm that a number of well-known problems (e.g., consensus, leader election) do not allow a terminating and stabilizing solution. On the flip side, they show that other problems such as mutual exclusion and reliable-transmission allow such solutions. We present a message-passing solution to the mutual exclusion problem that is both stabilizing and terminating. We also describe an approach of adding termination to a stabilizing program. To illustrate this approach, we add termination to a stabilizing solution for the reliable transmission problem.Published online: 15 November 2004Anish Arora: Supported in part by DARPA contract OSU-RF #F33615-01-C-1901,NSF grant NSF-CCR-9972368, Ohio State University Fellowship,and 2002-2003,2003-2004 grants from Microsoft Research.Mikhail Nesterenko: Supported in part by DARPA contract OSU-RF #F33615-01-C-1901 and byNSF CAREER Award 0347485Some of the results in this paper were presented at the 21st International Conference on Distributed Computing Systems, Mesa, Arizona, April 2001, pp 99-106. Correspondence to: Mikhail Nesterenko     

Retiming synchronous circuitry

This paper describes a circuit transformation calledretiming in which registers are added at some points in a circuit and removed from others in such a way that the functional behavior of the circuit as a whole is preserved. We show that retiming can be used to transform a given synchronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph in which the vertex setV is a collection of combinational logic elements and the edge setE is the set of interconnections, each of which may pass through zero or more registers. We give anO(¦VE¦lg¦V¦) algorithm for determining an equivalent retimed circuit with the smallest possible clock period. We show that the problem of determining an equivalent retimed circuit with minimum state (total number of registers) is polynomial-time solvable. This result yields a polynomial-time optimal solution to the problem of pipelining combinational circuitry with minimum register cost. We also give a chacterization of optimal retiming based on an efficiently solvable mixed-integer linear-programming problem.This research was supported in part by the Defense Advanced Research Projects Agency under Contract N00014-80-C-0622 and by the Office of Naval Research under Contract N00014-76-C-0370. Charles Leiserson was supported in part by an NSF Presidential Young Investigator Award with matching funds provided by AT&T Corporation, IBM Corporation, and Xerox Corporation. Most of the results reported here were obtained while James Saxe was in the Computer Science Department at Carnegie-Mellon University. During part of that period, he was supported by an IBM graduate fellowship.     

Rational trigonometric approximations using Fourier series partial sums

A class of approximations {S _N,M } to a periodic functionf which uses the ideas of Padé, or rational function, approximations based on the Fourier series representation off, rather than on the Taylor series representation off, is introduced and studied. Each approximationS _N,M is the quotient of a trigonometric polynomial of degreeN and a trigonometric polynomial of degreeM. The coefficients in these polynomials are determined by requiring that an appropriate number of the Fourier coefficients ofS _N,M agree with those off. Explicit expressions are derived for these coefficients in terms of the Fourier coefficients off. It is proven that these Fourier-Padé approximations converge point-wise to (f(x ⁺) +f(x ^–))/2 more rapidly (in some cases by a factor of 1/k ^2M ) than the Fourier series partial sums on which they are based. The approximations are illustrated by several examples and an application to the solution of an initial, boundary value problem for the simple heat equation is presented.This research was supported by NASA contract NAS1-19480 while the author was in residence at ICASE, NASA Langley Research Center, Hampton, Virginia 23665.     

On the recognition of parameterized 2D objects

Determining the identity and pose of oceluded objects from noisy data is a critical step in interacting intelligently with an unstructured environment. Previous work has shown that local measurements of position and surface orientation may be used in a constrained search process to solve this problem, for the case of rigid objects, either two-dimensional or three-dimensional. This paper considers the more general problem of recognizing and locating objects that can vary in parameterized ways. We consider two-dimensional objects with rotational, translational, or scaling degrees of freedom, and two-dimensional objects that undergo stretching transformations. We show that the constrained search method can be extended to handle the recognition and localization of such generalized classes of object families.This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory's artificial intelligence research is provided in part by an Office of Naval Research University Research Initiative grant under contract N00014-86-K-0180, in part by the Advanced Research Projects Agency of the Department of Defense under Army contract number DACA76-85-C-0010, and in part by DARPA under. Office of Naval Research contract N00014-85-K-0124. A preliminary version of this work appeared in the proceedings of the First International Conference on Computer Vision, London, England, 1987.     

Schema manipulation in self-describing and self-documenting data models

This paper integrates data, schema and meta-schema into a uniform model and provides one data language to manipulate and modify both data and schema. The modifications on the schema are then propagated to the schema's extension via propagation rules. The integration and the schema modification are all developed within the framework of self-describing and self-documenting models of data and they are fundamental in capturing the evolution of the database, which includes not only data changes, but schema changes as well.This work has been partially supported by NASA under contract NAS 5-26810.     

NAS存储系统性能测评方法研究

基于文件级共享存取的NAS存储系统已被广泛使用,但随着数据量的急剧增长,存储系统规模迅速扩大,其性能问题也因此日趋严重,对其评测也变得非常复杂,目前还未形成对NAS存储系统性能评测的有效标准方案.因此,用户在选购存储产品时没有参考标准和方法,极大地影响了用户的数据中心建设规划;同时,测评技术的落后也制约了存储技术的发展.为了解决这些问题,通过对NAS存储系统性能影响因素等的大量研究,制定了一套包括测评指标和测评方法等内容在内的性能测评方案,并通过测试实验展示了对NAS存储系统性能测评的方法和性能分析.本测评方案为用户提供了可行的技术参考方法,解决了目前存储测评技术发展的主要问题.     

Maximum Dispersion and Geometric Maximum Weight Cliques

We consider a facility location problem, where the objective is to “disperse” a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.     

Observability for two-dimensional systems

Sufficient conditions that a two-dimensional system with output is locally observable are presented. Known results depend on time derivatives of the output and the inverse function theorem. In some cases, no information is provided by these theories, and one must study observability by other methods. We dualize the observability problem to the controllability problem, and apply the deep results of Hermes on local controllability to prove a theorem concerning local observability.Research supported by NASA Ames Research Center under Grant NAG2-189 and the Joint Services Electronics Program under ONR Contract N0014-76-C1136.Research supported by NASA Ames Research Center under Grant NAG2-203 and the Joint Services Electronics Program under ONR Contract N0014-76-C1136.