Digital Commons Network^™

Partially Preemptible Hash Joins, Hwee Hwa Pang, Michael J. Carey, Miron Livny

Research Collection School Of Computing and Information Systems

With the advent of real-time and goal-oriented database systems, priority scheduling is likely to be an important feature in future database management systems. A consequence of priority scheduling is that a transaction may lose its buffers to higher-priority transactions, and may be given additional memory when transactions leave the system. Due to their heavy reliance on main memory, hash joins are especially vulnerable to fluctuations in memory availability. Previous studies have proposed modifications to the hash join algorithm to cope with these fluctuations, but the proposed algorithms have not been extensively evaluated or compared with each other. This paper contains …

The Third International Conference On Expert Systems For Numerical Computing, Elias N. Houstis, John R. Rice, Robert Vichnevetsky

Department of Computer Science Technical Reports

No abstract provided.

Broadcast Methods In The Multiswitch Point-To-Point Network, Douglas E. Comer, Victor Norman

Department of Computer Science Technical Reports

No abstract provided.

On The Multisearching Problem For Hypercubes, Mikhail J. Atallah, Andreas Fabri

Department of Computer Science Technical Reports

No abstract provided.

Some Experiments With A Basic Linear Algebra Routine On Distributed Memory Parallel Systems, H. Byun, Elias N. Houstis, E. A. Vavalis

Department of Computer Science Technical Reports

No abstract provided.

Accurate Verification Of Five-Axis Numerically Controlled Machining, Jerome L. Quinn

Dartmouth College Ph.D Dissertations

Current automated machining systems are composed of a number of components to aid in bringing a surface from design to physical completion. Numerically controlled (NC) milling machines are used to cut parts out of stock. Programming these machines to cut a desired surface is still largely a matter of experienced human participation. Therefore, the need exists to verify that tool programs produce the desired part.

We present recent developments in the verification of NC tool programs. Many of these methods rely on approximating the stock material as vectors whose lengths reflect the amount of uncut material at any point. This …

Disk Subsystem Performance And Reliability Enhancements Through The Use Of Carnival Mirrors, Darrell G. Suggs

All Dissertations

Performance and reliability modeling of computer systems continues to be an area of active research. Analytic and simulation modeling of computer systems and subsystems provides a cost effective means of system design, system expansion, and system tuning. Recent breakthroughs in computational power, coupled with the continuing development of the performance and reliability modeling field, now provide us with an opportunity to begin to answer design questions previously considered far out of reach.

Traditional computer systems contained only single-unit disk subsystems. Many current computer systems have multiple-unit disks that are treated as a single logical unit. These multiple disk systems provide …

The Investigation Of Object-Oriented Methodology As An Enabling Technique For End-User Application Development, Eng Chong Lim

Honors Theses

This research studies the value of object-oriented methods to design information systems that can then be developed and implemented by end-users.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 9, Number 4, April 1993, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

An eight page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Efficient Parallel Algorithms For Some Tree Layout Problems, J Diaz, A Gibbons, Grammati E. Pantziou, M Serna, Paul G. Spirakis, J Toran

Computer Science Technical Reports

The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job sequencing questions. Both problems are NP-complete for general graphs and in P for trees. We present here two algorithms in NC. The first solves the minimum length linear arrangement problem for unrooted trees in $O(\log^2 n)$ time and $O(n^2 3^{\log n})$ CREW PRAM processors. The second algorithm solves the minimum cut arrangement for unrooted trees of maximum degree $d$ in $O(d \log^2 n)$ time and $O(n^2 /\log n)$ CREW PRAM processors.

Federated Autonomous Databases: Project Overview, Satya Prabhakar, Jiandong Huang, James Richardson, Jaideep Srivastava, Ee Peng Lim, Sham Navathe, Ashok Savarase, Mark Foresti

Research Collection School Of Computing and Information Systems

The paper presents an overview of an ongoing research program, Federated Autonomous Databases, sponsored by Rome Laboratory (US Air Force) and conducted by Honeywell in collaboration with the University of Minnesota and Georgia Institute of Technology. This program is exploratory in nature and is aimed at understanding and solving, within the scope of the program definition, the problem of providing integrated access to distributed, heterogeneous and autonomous databases.

Entity Identification In Database Integration, Ee Peng Lim, Jaideep Srivastava, Satya Prabhakar, James Richardson

Research Collection School Of Computing and Information Systems

The objective of entity identification is to determine the correspondence between object instances from more than one database. Entity identification at the instance level, assuming that schema level heterogeneity has been resolved a priori, is examined. Soundness and completeness are defined as the desired properties of any entity identification technique. To achieve soundness, a set of identity and distinctness rules are established for entities in the integrated world. The use of extended key, which is the union of keys, and possibly other attributes, from the relations to be matched, and its corresponding identify rule are proposed to determine the equivalence …

Topology Based Routing Algorithms For Multilayer Ic Layout Design, Moazzem Hossain

Masters Theses

In this thesis, we consider the multilayer topological routing problem and also the geometric routing problem based on topological routing solution. We show that the problem of multilayer topological planar routing for any arbitrary routing region can be modeled as a problem in a simple closed routing region. We also show that the solution to the multilayer planar routing leads to a better result of the topological via minimization problem. We present a provably-good approximation algorithm for the multilayer topological planar routing problem for different routing regions.

We also propose a graph theoretic algorithm to find 2-layer topological solutions that …

Middle Terminal Cell Models For Efficient Over-The-Cell Routing, Siddharth Bhingarde

Masters Theses

In this thesis, we introduce a new class of cell models called Middle Terminal Models (MTM) which combines the advantages of existing cell models: BTM and CTM. This class contains the models 2MTM, 3MTM-V, and 3MTM+V depending on the number of metal layers and the permissibility of vias in over-the-cell areas. In MTM, two rows of terminals are located in the middle of the cell. This partitions over-the-cell area into three regions and allows allocation of more nets to over-the-cell area in congested channels. We prove that when vias are allowed over-the-cell, in "almost all" cases the MTM based layouts …

Optimal Parallel Hypercube Algorithms For Polygon Problems, Mikhail J. Atallah, Danny Z. Chen

Department of Computer Science Technical Reports

No abstract provided.

On The Convergence Domains Of The P-Cyclic Sor, A. Hadjidimos, D. Noutsos, M. Tzoumas

Department of Computer Science Technical Reports

No abstract provided.

Parallel Electronic Prototyping Of Physical Objects, Poting Wu, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.

Comparison Of Imsl/Idl With The Imsl Math Library And Exponet Graphics, Xingkang Fu, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Building A Large Scale Distributed Object System For A Multilingual Programming Environment, Patrick A. Muckelbauer, Vincent F. Russo

Department of Computer Science Technical Reports

No abstract provided.

Collaborating Pde Solvers With Interface Relaxation, Mo Mu, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Recognition Of Quadric Surfaces From Range Data: An Analytical Approach, Ivan X. D. D'Cunha

Electrical & Computer Engineering Theses & Dissertations

In this dissertation, a new technique based on analytic geometry for the recognition and description of three-dimensional quadric surfaces from range images is presented. Beginning with the explicit representation of quadrics, a set of ten coefficients are determined for various three-dimensional surfaces. For each quadric surface, a unique set of two-dimensional curves which serve as a feature set is obtained from the various angles at which the object is intersected with a plane. Based on a discriminant method, each of the curves is classified as a parabola, circle, ellipse, hyperbola, or a line. Each quadric surface is shown to be …

Fast Fourier Transforms On Distributed Memory Parallel Machines, Anshu Dubey

Computer Science Theses & Dissertations

One issue which is central in developing a general purpose subroutine on a distributed memory parallel machine is the data distribution. It is possible that users would like to use the subroutine with different data distributions. Thus there is a need to design algorithms on distributed memory parallel machines which can support a variety of data distributions. In this dissertation we have addressed the problem of developing such algorithms to compute the Discrete Fourier Transform (DFT) of real and complex data. The implementations given in this dissertation work for a class of data distributions commonly encountered in scientific applications, known …

A Performance Prediction Model For A Fault-Tolerant Computer During Recovery And Restoration, Rodrigo A. Obando

Electrical & Computer Engineering Theses & Dissertations

The modeling and design of a fault-tolerant multiprocessor system is addressed in this dissertation. In particular, the behavior of the system during recovery and restoration after a fault has occurred is investigated. Given that a multicomputer system is designed using the Algorithm to Architecture To Mapping Model (ATAMM) model, and that a fault (death of a computing resource) occurs during its normal steady-state operation, a model is presented as a viable research tool for predicting the performance bounds of the system during its recovery and restoration phases. Furthermore, the bounds of the performance behavior of the system during this transient …

Time-Optimal Algorithms On Meshes With Multiple Broadcasting, Dharmavani Bhagavathi

Computer Science Theses & Dissertations

The mesh-connected computer architecture has emerged as a natural choice for solving a large number of computational tasks in image processing, computational geometry, and computer vision. However, due to its large communication diameter, the mesh tends to be slow when it comes to handling data transfer operations over long distances. In an attempt to overcome this problem, mesh-connected computers have recently been augmented by the addition of various types of bus systems. One such system known as the mesh with multiple broadcasting involves enhancing the mesh architecture by the addition of row and column buses. The mesh with multiple broadcasting …

Resource Utilization Model For The Algorithm To Architecture Mapping Model, Rakesh R. Patel

Electrical & Computer Engineering Theses & Dissertations

The analytical model for resource utilization, and the variable node time and conditional node model for the enhanced ATAMM model for a real-time data flow architecture, is presented in this research. The Algorithm To Architecture Mapping Model, ATAMM, is a Petri net based graph theoretic model developed at Old Dominion University, and is capable of modeling the execution of large-grained algorithms on a real-time data flow architecture. Using the resource utilization model, the resource envelope may be obtained directly from a given graph and, consequently, the maximum number of required resources may be evaluated. The node timing diagram for one …

Integrating Theory And Practice In Parallel File Systems, Thomas H. Cormen, David Kotz

Computer Science Technical Reports

Several algorithms for parallel disk systems have appeared in the literature recently, and they are asymptotically optimal in terms of the number of disk accesses. Scalable systems with parallel disks must be able to run these algorithms. We present a list of capabilities that must be provided by the system to support these optimal algorithms: control over declustering, querying about the configuration, independent I/O, turning off file caching and prefetching, and bypassing parity. We summarize recent theoretical and empirical work that justifies the need for these capabilities.

A Systolic Simulation And Transformation System, Ronald I. Greenberg, H.-C. Oh

Computer Science: Faculty Publications and Other Works

This paper presents a CAD tool, SystSim, to ease the design of systolic systems. Given a high-level, functional description of processors, and a high-level description of their interconnection, SystSim will perform simulations and provide graphical output. SystSim will also perform transformations such as retiming, which eases use of the methodology of Leiserson and Saxe of designing a system with broadcasting and then obtaining a systolic system through retiming.

Difficulties Experienced Procedural Programmers Encounter When Transferring To An Object-Oriented Programming Paradigm, Scott Andrew Machaffie

Dissertations and Theses

Experienced procedural programmers seem to have difficulty when transferring from a procedural language to an object-oriented language. The problem is how to assist the experienced procedural programmers to make this shift. The long term goal of this research is to identify areas where programmers have problems and to develop an automated system to help them overcome these difficulties.

This study examines the class designs produced by procedural programmers and the effect of specifications and domain knowledge on class designs. Two types of specifications were used: those written from a procedural point of view which emphasized the functions and those written …

Comprehension Of Literate Programs By Novice And Intermediate Programmers, Christopher Forrest Bertholf

Dissertations and Theses

The studies reported herein compare comprehension of Lit style literate programs to that of traditional modular programs documented by embedded comments. Novice and intermediate programmers participated in three experiments designed to determine the comprehensibility of literate programs written using a language-independent system for abstraction-oriented literate programming compared with programs written using traditional modular programming techniques (traditional modular programs). Programs were written in either the C or FORTRAN programming language. Half of the subjects in each group received a literate program, while the other half received a traditional modular program with embedded documentation. Subjects received a problem specification, input and output …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 9, Number 3, March 1993, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A twelve page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.