Open Access. Powered by Scholars. Published by Universities.®

Digital Commons Network™

Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences

Institution
Keyword
Publication Year
Publication
Publication Type
File Type

Articles 19981 - 20010 of 20563

Full-Text Articles in Entire DC Network

Deterministic Approximations To Co-Production Problems With Service Constraints And Random Yields, Gabriel R. Bitran, Thin Yin Leong May 1992

Deterministic Approximations To Co-Production Problems With Service Constraints And Random Yields, Gabriel R. Bitran, Thin Yin Leong

Research Collection School Of Computing and Information Systems

Production planning problems where multiple item categories are produced simultaneously are examined. The items have random yields and are used to satisfy the demands of many products. These products have specification requirements that overlap. An item originally targeted to satisfy the demand of one product may be used to satisfy the demand of other products when it conforms to their specifications. Customers' demand must be satisfied from inventory. The problem is formulated with service constraints and a near-optimal solution is provided to the problem with a fixed planning horizon. Simple heuristics are proposed for the problem solved with a rolling …

Go to article

An Enhanced Reconfigurable Embedding Scheme For Rings In Hypercubes, Junlin Liu, Bruce M. Mcmillin Apr 1992

An Enhanced Reconfigurable Embedding Scheme For Rings In Hypercubes, Junlin Liu, Bruce M. Mcmillin

Computer Science Technical Reports

In this paper we present an enhanced version of a reported reconfigurable embedding scheme (i.e., DC scheme) that based on the idea of divide and conquer to efficiently embed even length rings in hypercubes. It was shown that the system with the DC scheme is 3-step recoverable and needs an average of 1.3 steps to recover one single fault. Here, we show that the system with the enhanced embedding scheme will be 2-step recoverable when the dimensions of hypercubes are ~ 5, and the system is able to recover any single fault in an average of 1.1 steps.

Go to article

Relaxing Synchronization In Distributed Simulated Annealing, Chul-Eui Hong, Bruce M. Mcmillin Apr 1992

Relaxing Synchronization In Distributed Simulated Annealing, Chul-Eui Hong, Bruce M. Mcmillin

Computer Science Technical Reports

Simulated annealing is an attractive, but expensive, heuristic for approximating the solution to combinatorial optimization problems. Attempts to parallelize simulated annealing, particularly on distributed memory multicomputers, are hampered by the algorithm's requirement of a globally consistent system state. In a multicomputer, maintaining the global state S Involves explicit message traffic and is a critical performance bottleneck. To mitigate this bottleneck, it becomes necessary to amortize the overhead of these state updates over as many parallel state changes as possible. By using this technique, errors in the actual cost C(S) of a particular state S will be introduced into the annealing …

Go to article

Embedding Data Mappers With Distributed Memory Machine Compilers, Ravi Ponnusamy, Joel Saltz, Raja Das, Charles Koelbel, Alok Choudhary Apr 1992

Embedding Data Mappers With Distributed Memory Machine Compilers, Ravi Ponnusamy, Joel Saltz, Raja Das, Charles Koelbel, Alok Choudhary

Electrical Engineering and Computer Science - Technical Reports

In scalable multiprocessor systems, high performance demands that computational load be balanced evenly among processors and that interprocessor communication be limited as much as possible. Compilation techniques for achieving these goals have been explored extensively in recent years [3, 9, 11, 13, 17, 18]. This research has produced a variety of useful techniques, but most of it has assumed that the programmer specifies the distribution of large data structures among processor memories. A few projects have attempted to automatically derive data distributions for regular problems [12, 10, 8, 1]. In this paper, we study the more challenging problem of automatically …

Go to article

A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang Apr 1992

A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang

Electrical Engineering and Computer Science - Technical Reports

This paper presents a simple load balancing algorithm and its probabilistic analysis. Unlike most of the previous load balancing algorithms, this algorithm maintains locality. We show that the cost of this load balancing algorithm is small for practical situations and discuss some interesting applications for data remapping.

Go to article

A Survey Of Computer Use In Occupational Therapy Fieldwork Sites, Martha E. Parks Apr 1992

A Survey Of Computer Use In Occupational Therapy Fieldwork Sites, Martha E. Parks

Masters Theses

Eighty-three Western Michigan University occupational therapy fieldwork sites were surveyed to determine: (a) extent of computer use, (b) diagnostic categories with which computers are used, (c) extent of computer knowledge of registered occupational therapists (OTRs), and (d) adequacy of computer knowledge of fieldwork students. Forty-seven (56.6%) of the 83 surveys were returned. OTRs at 36 (76.6%) of the 47 sites currently use computers. Word processing is the most common way in which these OTRs use computers. The most common clinical use of computers is perceptual/motor assessment and treatment, while the most common research use of computers is for report writing. …

Go to article

Formant Estimation From Dctc's Using A Feedforward Neural Network, Shubhangi U. Kelkar Apr 1992

Formant Estimation From Dctc's Using A Feedforward Neural Network, Shubhangi U. Kelkar

Electrical & Computer Engineering Theses & Dissertations

Formants are the natural frequencies of the human vocal tract. Existing methods for estimating formants from speech signals are computationally complex and subject to errors for certain type of speech sounds. This thesis describes a method for estimating vowel formant frequencies from Discrete Cosine Transform Coefficients (DCTC's), a form of cepstral coefficients, using a feedforward neural network with back-propagation training. Experimental results are based on a large multispeaker data base. The results are obtained for both a linear transformation and a feedforward neural network with a nonlinear hidden layer. In general, the neural network transformation is superior to the linear …

Go to article

An Algorithm For Generating Executable Assertions For Fault Tolerance, Martina Schollmeyer, Hanan Lutfiyya, Bruce M. Mcmillin Mar 1992

An Algorithm For Generating Executable Assertions For Fault Tolerance, Martina Schollmeyer, Hanan Lutfiyya, Bruce M. Mcmillin

Computer Science Technical Reports

This paper presents an algorithm for deriving executable assertions that can be evaluated in a faulty distributed environment. A transformation from the global auxiliary variable approach into a new proof system based on the history of the auxiliary variables is introduced. This transformation, which matches the operational distributed environment more closely than the global auxiliary variable system, is then shown to retain the properties of this system such as noninterference, satisfaction, soundness, and completeness. An example is presented in which a model problem is transformed from one system into the other.

Go to article

Fault-Tolerant Distributed Database Lock Managers Formally Derived From Program Verification, Hanan Lutfiyya, Martina Schollmeyer, Bruce M. Mcmillin Mar 1992

Fault-Tolerant Distributed Database Lock Managers Formally Derived From Program Verification, Hanan Lutfiyya, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

This paper presents a system for formally deriving executable assertions that can be evaluated in the faulty distributed computing environment. Since executable assertions for fault tolerance need to show that a program meets its specification and, since program verification is the process of formally showing that a program satisfies some particular properties with respect to its specification, we use program verification as a basis for derivation. It is well known that in the sequential computing environment the assertions from a program verification proof outline may be translated directly into executable assertions. However, due to the lack of global state information …

Go to article

A Non-Deterministric Parallel Sorting Algorithm, Xue Shirley Li, F. Lockwood Morris Mar 1992

A Non-Deterministric Parallel Sorting Algorithm, Xue Shirley Li, F. Lockwood Morris

Electrical Engineering and Computer Science - Technical Reports

A miniswap Si,1 ≤ i < n, compares two adjacent keys Пi, Пi+1 in the sequence (П1, ... , Пn), and transposes them if they are out of order. A full sweep is any composition of all n - 1 possible miniswaps. We prove that the composition of any n- 1 full sweeps is a sorting function.

Go to article

Development Of A Flight Information System Using The Structured Method, Yeong-Lae Kwak Mar 1992

Development Of A Flight Information System Using The Structured Method, Yeong-Lae Kwak

Theses and Dissertations

This thesis documents the development of a database system for the Flight Information System (FIS) of the Korean Air Force. The scope of the FIS is too large to be covered by this thesis. Thus, this thesis covers only the core part of the FIS due to the limitation of time and man-power. This thesis uses the structured method. Structured analysis and structured design techniques are mainly used two techniques. This thesis focused not only the development of the FIS but also the application of the software development method, the structured method, and its tools such as DFD, DD, ERD, …

Go to article

A Declarative Foundation Of Λprolog With Equality, Mino Bai Feb 1992

A Declarative Foundation Of Λprolog With Equality, Mino Bai

Electrical Engineering and Computer Science - Technical Reports

We build general model-theoretic semantics for higher-order logic programming languages. Usual semantics for first-order logic is two-level: i.e., at a lower level we define a domain of individuals, and then, we define satisfaction of formulas with respect to this domain. In a higher-order logic which includes the propositional type in its primitive set of types, the definition of satisfaction of formulas is mutually recursive with the process of evaluation of terms. As result of this in higher-order logic it is extremely difficult to define an effective semantics. For example to define T p operator for logic program P, we need …

Go to article

Conceptual Background For Symbolic Computation, Klaus Berkling Feb 1992

Conceptual Background For Symbolic Computation, Klaus Berkling

Electrical Engineering and Computer Science - Technical Reports

This paper is a tutorial which examines the three major models of computation--the Turing Machine, Combinators, and Lambda Calculus--with respect to their usefulness to practical engineering of computing machines. While the classical von Neumann architecture can be deduced from the Turing Machine model, and Combinator machines have been built on an experimental basis, no serious attempts have been made to construct a Lambda Calculus machine. This paper gives a basic outline of how to incorporate a Lambda Calculus capability into a von Neumann type architecture, maintaining full backward compatibility and at the same time making optimal use of its advantages …

Go to article

Fault-Detection In Networks, H. F. Mattson Jr Feb 1992

Fault-Detection In Networks, H. F. Mattson Jr

Electrical Engineering and Computer Science - Technical Reports

To find broken links in networks we use the cut-set space. Information on which nodes can talk, or not, to which other nodes allows reduction of the problem to that of decoding the cut-set code of a graph. Special classes of such codes are known to have polynomial-time decoding algorithms. We present a simple algorithm to achieve the reduction and apply it in two examples.

Go to article

Fault-Tolerant Concurrent Branch And Bound Algorithm Derived From Program Verification, Hanan Lutfiyya, Aggie Sun, Bruce M. Mcmillin Jan 1992

Fault-Tolerant Concurrent Branch And Bound Algorithm Derived From Program Verification, Hanan Lutfiyya, Aggie Sun, Bruce M. Mcmillin

Computer Science Technical Reports

The process of showing that a program satisfies some particular properties with respect to its specification is called program verification. Axiomatic semantics is a verification method that makes assertions describing properties about the states of the program. There exists a transformation from the assertions of the verification proof of a program to executable assertions. These executable assertions may be embedded in the program to create a fault-tolerant program. While this approach has been applied to the sequential programming environment, the distributed programming environment presents special challenges. This paper focuses on applying concurrent programming axiomatic proof systems to generate executable assertions …

Go to article

A Divide And Conquer Ring Embedding Scheme On Hypercubes With Efficient Recovery Ability, Junlin Liu, Bruce M. Mcmillin Jan 1992

A Divide And Conquer Ring Embedding Scheme On Hypercubes With Efficient Recovery Ability, Junlin Liu, Bruce M. Mcmillin

Computer Science Technical Reports

The hypercube architecture has been considered a useful host to simulate many networks. However, when processors on hypercubes become faulty, the simulated topologies may no longer be valid and, thus, the system needs to invoke some reconfiguration algorithm to recover the topology. The efficiency of this reconfiguration depends heavily on the initial embedding method. This paper proposes a general scheme based on the idea of divide and conquer that efficiently embeds even length rings on hypercubes with small expansion and recovery cost. It is shown that the average expansion for the proposed scheme is 1.58, and the average number of …

Go to article

Exploring The Symbolic/Subsymbolic Continuum: A Case Study Of Raam, Doug Blank, Lisa Meeden, James Marshall Jan 1992

Exploring The Symbolic/Subsymbolic Continuum: A Case Study Of Raam, Doug Blank, Lisa Meeden, James Marshall

Computer Science Faculty Research and Scholarship

No abstract provided.

Go to article

The Expressiveness Of Locally Stratified Programs, Howard A. Blair, Wiktor Marek, John S. Schlipf Jan 1992

The Expressiveness Of Locally Stratified Programs, Howard A. Blair, Wiktor Marek, John S. Schlipf

Electrical Engineering and Computer Science - Technical Reports

This paper completes an investigation of the logical expressibility of finite, locally stratified, general logic programs. We show that every hyperarithmetic set can be computed by a suitably chosen locally stratified logic program (as a set of values of a predicate over its perfect model). This is an optimal result, since the perfect model of a locally stratified program is itself an implicitly definable hyperarithmetic set (under a recursive coding of the Herbrand base); hence to obtain all hyperarithmetic sets requires something new, in this case selecting one predicate from the model. We find that the expressive power of programs …

Go to article

A Large Scale Comparison Of Option Pricing Models With Historical Market Data, Kim Mills, Michael Vinson, Gang Cheng Jan 1992

A Large Scale Comparison Of Option Pricing Models With Historical Market Data, Kim Mills, Michael Vinson, Gang Cheng

Northeast Parallel Architecture Center

A set of stock option pricing models are implemented on the Connection Machine-2 and the DECmpp-12000 to compare model prices and historical market data. Improved models, which incorporate stochastic volatility with American call generally have smaller pricing errors than simpler models which are based on constant volatility and European call. In a refinement of the comparison between model and market prices, a figure of merit based on the bid/ask spread in the market, and the use of optimization techniques for model parameter estimation, are evaluated. Optimization appears to hold great promise for improving the accuracy of existing pricing models, especially …

Go to article

Software Issues And Performance Of A Parallel Model For Stock Option Pricing, Kim Mills, Gang Cheng, Michael Vinson, Sanjay Ranka Jan 1992

Software Issues And Performance Of A Parallel Model For Stock Option Pricing, Kim Mills, Gang Cheng, Michael Vinson, Sanjay Ranka

Northeast Parallel Architecture Center

The finance industry is beginning to adopt parallel computing for numerical computation, and will soon be in a position to use parallel supercomputers. This paper examines software issues and performance of a stock option pricing model running on the Connection Machine-2 and DECmpp-12000. Pricing models incorporating stochastic volatility with American call (early exercise) are computationally intensive and require substantial communication. Three parallel versions of a stock option pricing model were developed which varied in data distribution, load balancing, and communication. The performance of this set of increasingly refined models ranged over no improvement, 10 times, and 100 times faster than …

Go to article

Parti Primitives For Unstructured And Block Structured Problems, Alan Sussman, Joel Saltz, Raja Das, S. Gupta, Dimitri Mavriplis, Ravi Ponnusamy Jan 1992

Parti Primitives For Unstructured And Block Structured Problems, Alan Sussman, Joel Saltz, Raja Das, S. Gupta, Dimitri Mavriplis, Ravi Ponnusamy

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper describes a set of primitives (PARTI) developed to efficiently execute unstructured and block structured problems on distributed memory parallel machines. We present experimental data from a 3-D unstructured Euler solver run on the Intel Touchstone Delta to demonstrate the usefulness of our methods.

Go to article

Benchmarking The Cm-5 For Image Processing Applications, Ravi V. Shankar, Ravi Ponnusamy, Sanjay Ranka Jan 1992

Benchmarking The Cm-5 For Image Processing Applications, Ravi V. Shankar, Ravi Ponnusamy, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

This paper presents benchmarking results for image processing algorithms on the Connection Machine model CM-5 and compares them with the results from the CM-2 and the Sun-4. Image processing algorithms with varying communication and computational requirements were implemented, tested and timed. The performance and the scalabilty of the CM-5 were analyzed and compared with that of the CM-2.

Go to article

Software Support For Irregular And Loosely Synchronous Problems, Alok Choudhary, Geoffrey C. Fox, Sanjay Ranka, Seema Hiranandani Jan 1992

Software Support For Irregular And Loosely Synchronous Problems, Alok Choudhary, Geoffrey C. Fox, Sanjay Ranka, Seema Hiranandani

Electrical Engineering and Computer Science - All Scholarship

A large class of scientific and engineering applications may be classified as irregular and loosely synchronous from the perspective of parallel processing. We present a partial classification of such problems. This classification has motivated us to enhance Fortran D to provide language support for irregular, loosely synchronous problems. We present techniques for parallelization of such problems in the context of Fortran D.

Go to article

A Prototype Document Image Analysis System For Technical Journals, George Nagy, Sharad C. Seth, Mahesh Viswanathan Jan 1992

A Prototype Document Image Analysis System For Technical Journals, George Nagy, Sharad C. Seth, Mahesh Viswanathan

School of Computing: Faculty Publications

Intelligent document segmentation can bring electronic browsing within the reach of most users. The authors show how this is achieved through document processing, analysis, and parsing the graphic sentence.

Go to article

Lessons From Massively Parallel Applications On Message Passing Computers, Geoffrey C. Fox Jan 1992

Lessons From Massively Parallel Applications On Message Passing Computers, Geoffrey C. Fox

Northeast Parallel Architecture Center

We review a decade's work on message passing MIMD parallel computers in the areas of hardware, software and applications. We conclude that distributed memory parallel computing works, and describe the implications of this for future portable software systems.

Go to article

Static And Runtime Algorithms For All-To-Many Personalized Communication On Permutation Networks, Sanjay Ranka, Jhy-Chun Wang, Geoffrey C. Fox Jan 1992

Static And Runtime Algorithms For All-To-Many Personalized Communication On Permutation Networks, Sanjay Ranka, Jhy-Chun Wang, Geoffrey C. Fox

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

With the advent of new routing methods, the distance to which a message is sent is becoming relatively less and less important. Thus, assuming no link contention, permutation seems to be an efficient collective communication primitive. In this paper we present several algorithms for decomposing all-to-many personalized communication into a set of disjoint partial permutations. We discuss several algorithms and study their effectiveness from the view of static scheduling as well as runtime scheduling. An approximate analysis shows that with n processors and assuming that every processor sends and receives d messages to random destinations, our algorithm can perform the …

Go to article

Flattening C++ Classes, Umesh Bellur, Al Villarica, Kevin Shank, Imram Bashir, Doug Lea Jan 1992

Flattening C++ Classes, Umesh Bellur, Al Villarica, Kevin Shank, Imram Bashir, Doug Lea

Center for Advanced Systems and Engineering

Inheritance with derived classes and virtual functions are key design concepts in C++. Despite this, their use can result in significant degradation of run time performance. We present a class flattening tool, which we believe will help eliminate the overhead associated with virtual functions in C++ programs. A flattener may also prove useful in the reuse, debugging, and understanding of C++ components. This report deals with the issues associated with flattening, and then presents a detailed design of such a tool.

Go to article

Software Support For Irregular And Loosely Synchronous Problems, Alok Choudhary, Geoffrey C. Fox, Sanja Ranka, Seema Hiranandani Jan 1992

Software Support For Irregular And Loosely Synchronous Problems, Alok Choudhary, Geoffrey C. Fox, Sanja Ranka, Seema Hiranandani

Northeast Parallel Architecture Center

A large class of scientific and engineering applications may be classified as irregular and loosely synchronous from the perspective of parallel processing. We present a partial classification of such problems. This classification has motivated us to enhance Fortran D to provide language support for irregular, loosely synchronous problems. We present techniques for parallelization of such problems in the context of Fortran D.

Go to article

Scheduling Regular And Irregular Communication Patterns On The Cm-5, Ravi Ponnusamy, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox Jan 1992

Scheduling Regular And Irregular Communication Patterns On The Cm-5, Ravi Ponnusamy, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox

Northeast Parallel Architecture Center

In this paper, we study the communication characteristics of the CM-5 and the performance effects of scheduling regular and irregular communication patterns on the CM-5. We consider the scheduling of regular communication patterns such as complete exchange and broadcast. We have implemented four algorithms for complete exchange and studied their performances on a 2D FFT algorithm. We have also implemented four algorithms for scheduling irregular communication patterns and studied their performance on the communication patterns of several synthetic as well as real problems such as the conjugate gradient solver and the Euler solver.

Go to article

Which Applications Can Use High Performance Fortran And Fortran-D: Industry Standard Data Parallel Languages?, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt, S. Ranka Jan 1992

Which Applications Can Use High Performance Fortran And Fortran-D: Industry Standard Data Parallel Languages?, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt, S. Ranka

Northeast Parallel Architecture Center

In this paper, we present the first, preliminary results of HPF/Fortran-D language analysis based on compiling and running benchmark applications using a prototype implementation of HPF/Fortran-D compiler. The analysis indicate that the HPF is a very convenient tool for programming many applications on massively parallel and/or distributed systems. In addition, we cumulate experience on how to parallelize irregular problems to extend the scope of Fortran-D beyond HPF and suggest future extensions to the Fortran standard.

Go to article

First Prev Next Last