Physical Sciences and Mathematics Commons^™

Disk-Directed I/O For Mimd Multiprocessors, David Kotz

Dartmouth Scholarship

Many scientific applications that run on today's multiprocessors, such as weather forecasting and seismic analysis, are bottlenecked by their file-I/O needs. Even if the multiprocessor is configured with sufficient I/O hardware, the file-system software often fails to provide the available bandwidth to the application. Although libraries and enhanced file-system interfaces can make a significant improvement, we believe that fundamental changes are needed in the file-server software. We propose a new technique, disk-directed I/O, to allow the disk servers to determine the flow of data for maximum performance. Our simulations show that tremendous performance gains are possible both for simple reads …

Turing Universality Of Neural Nets (Revisited), J. Pedro Neto, Hava Siegelmann, J. Félix Costa, C. P. Suárez Araujo

Hava Siegelmann

We show how to use recursive function theory to prove Turing universality of finite analog recurrent neural nets, with a piecewise linear sigmoid function as activation function. We emphasize the modular construction of nets within nets, a relevant issue from the software engineering point of view.

Least Space-Time First Scheduling Algorithm : Scheduling Complex Tasks With Hard Deadline On Parallel Machines, Bo-Chao Cheng

Dissertations

Both time constraints and logical correctness are essential to real-time systems and failure to specify and observe a time constraint may result in disaster. Two orthogonal issues arise in the design and analysis of real-time systems: one is the specification of the system, and the semantic model describing the properties of real-time programs; the other is the scheduling and allocation of resources that may be shared by real-time program modules.

The problem of scheduling tasks with precedence and timing constraints onto a set of processors in a way that minimizes maximum tardiness is here considered. A new scheduling heuristic, Least …

Massively Parallel Reasoning In Transitive Relationship Hierarchies, Yugyung Lee

Dissertations

This research focuses on building a parallel knowledge representation and reasoning system for the purpose of making progress in realizing human-like intelligence. To achieve human-like intelligence, it is necessary to model human reasoning processes by programs. Knowledge in the real world is huge in size, complex in structure, and is also constantly changing even in limited domains. Unfortunately, reasoning algorithms are very often intractable, which means that they are too slow for any practical applications. One technique to deal with this problem is to design special-purpose reasoners. Many past Al systems have worked rather nicely for limited problem sizes, but …

Safe Code Transfromations For Speculative Execution In Real-Time Systems, Mohamed Mohamed Younis

Dissertations

Although compiler optimization techniques are standard and successful in non-real-time systems, if naively applied, they can destroy safety guarantees and deadlines in hard real-time systems. For this reason, real-time systems developers have tended to avoid automatic compiler optimization of their code. However, real-time applications in several areas have been growing substantially in size and complexity in recent years. This size and complexity makes it impossible for real-time programmers to write optimal code, and consequently indicates a need for compiler optimization. Recently researchers have developed or modified analyses and transformations to improve performance without degrading worst-case execution times. Moreover, these optimization …

Abstraction Of An Object-Oriented Vocabulary By Providing A Standardized Interface, Hemant Kothavade

Theses

Controlled vocabularies are ubiquitous in varied application fields. They are particularly helpful in the medical field since they can unify disparate terminologies and provide information in a compact, comprehensible manner. In this thesis, we present a mechanism to efficiently retrieve and update knowledge stored in a controlled vocabulary modeled as an Object-Oriented Database (OODB) system. We aim to provide a standardized interface to the vocabulary, such that the implementation details of the vocabulary are transparent to all users. The user of this standardized interface will typically be an application programmer who is trying to provide the vocabulary's knowledge-base to end …

Application Of Geometric Hashing Techniques To Retrieval Of High Dimensional Objects In Scientific Databases, Joyce Ye Lu

Theses

An approach to designing very fast algorithms for tackling the problem of approximate object matching in very large databases of high-dimensional objects is proposed. Given are a target object C and a database D containing information about a set of high-dimensional objects each of which is represented as a set of points. Our algorithms have an off-line object preprocessing (shape representation) phase and a recognition phase. The described algorithms determine those objects from D which are the closest to object C, according to delete or insert some points, move and rotation. All of these can be achieved very efficiently with …

Automated Parallelization Of Discrete State-Space Generation, David M. Nicol, Gianfranco Ciardo

Computer Science Technical Reports

We consider the problem of generating a large state-space in a distributed fashion. Unlike previously proposed solutions that partition the set of reachable states according to a hashing function provided by the user, we explore heuristic methods that completely automate the process. The first step is an initial random walk through the state space to initialize a search tree, duplicated in each processor. Then, the reachability graph is built in a distributed way, using the search tree to assign each newly found state to classes assigned to the available processors. Furthermore, we explore two remapping criteria that attempt to balance …

Structural Issues In Active Rule Systems, James Bailey, Guozhu Dong, Kotagiri Ramamohanarao

Kno.e.sis Publications

Active database systems enhance the functionality of traditional databases through the use of active rules or ‘triggers’. There is little consensus, though, on what components should be included in a rule system. In this paper, the expressive power of some simple active database rule systems is examined and the effect of choosing different features studied. Four important parameters of variation are presented, namely the rule language, the external query language, the meta rule language and the pending rule structure. We show that each of these is highly influential in determining the expressiveness of the rule system as a whole, and …

Agent-Based Expert Assistance For Visual Problem Solving, Erika Rogers, Robin R. Murphy, Barb Ericson

Computer Science and Software Engineering

This paper presents a domain-independent architecture for facilitating visual problem solving between robots or softbots and humans. The architecture defines virtual and human agents in terms of their inherent cognitive and perceptual abilities, and their weak and strong knowledge sources. It introduces a third agent, an expert assistant called teleVIA, to mediate the flow of information, facilitate cooperation, filter and cache data, and generate the appropriate visual displays. The agent architecture addresses the technical issues of using an expert assistant to coordinate perception, thought, and action, manage sensing and perception, facilitate diagnosis, and to support the collaboration between people and …

Operation And Control In A Competitive Market: Distributed Generation In A Restructured Industry, Judith Cardell, Richard Tabors

Engineering: Faculty Publications

The prospect of independent ownership for distributed technologies is being encouraged by the current deregulation of the industry, and it is possible that the new generators will be independently operated as well as independently owned. The siting of numerous small-scale generators in distribution feeders is likely to have an impact on the operations and control of the power system, a system designed to operate with large, central generating facilities. In response to the new and potentially conflicting economic and technical demands of a growing number of independent players, the power system may require new means for coordinating system operations. Price …

Using Atm Networks For Processing Global Earth Data, Barbara L. Kess, Phillip R. Romig Iii, Stephen E. Reichenbach, Ashok K. Samal

CSE Conference and Workshop Papers

amount of computational power to researchers at an affordable cost, making it feasible to use workstations rather than expensive supercomputers to perform scientific analysis of large data sets, such as the Global Land 1-Km AVHRR data. In addition to this, inexpensive high speed ATM networks have the potential to improve the overall computational efficiency of workstations by using several workstations in a distributed environment. This research studies the practicality of using distributed workstations interconnected with a 155 Mb ATM network for analysis and compression of the Global Land 1-Km AVHRR data versus sequential computing on one of the workstations. Performance …

Synthesis For Testability By Two-Clock Control, Shashank K. Mehta, Sharad C. Seth, Kent L. Einspahr

CSE Conference and Workshop Papers

In previous studies clock control has been inserted after design to improve the testability of a sequential circuit. In this paper we propose a two-clock control scheme that is included as a part of the logic synthesis of a finite state machine (fsm). The scheme has low area overhead and competes well with scan methods in its ability to initialize and observe circuit states. The states of the machine are assigned a pair of binary values using a novel split coding system. The purpose of the encoding is to ease navigation between any pair of states using a combination of …

Minimizing The Number Of Optical Amplifiers Needed To Support A Multi-Wavelength Optical Lan/Man, Byrav Ramamurthy, Jason Iness, Biswanath Mukherjee

CSE Conference and Workshop Papers

Optical networks based on passive star couplers and employing wavelength-division multiplexing (WDhf) have been proposed for deployment in local and metropolitan areas. Amplifiers are required in such networks to compensate for the power losses due to splitting and attenuation. However, an optical amplifier has constraints on the maximum gain and the maximum output power it can supply; thus optical amplifier placement becomes a challenging problem. The general problem of minimizing the total amplifier count, subject to the device constraints, is a mixed-integer non-linear problem. Previous studies have attacked the amplifier placement problem by adding the “artificial” constraint that all wavelengths, …

Genetic Algorithms For The Extended Gcd Problem, Jonathan P. Sorenson

Scholarship and Professional Work - LAS

We present several genetic algorithms for solving the extended greatest common divisor problem. After defining the problem and discussing previous work, we will state our results.

An Error Handling Framework For The Orbwork Workflow Enactment Service Of Meteor, Davasish Worah, Amit P. Sheth, Krzysztof J. Kochut, John A. Miller

Kno.e.sis Publications

Workflow Management Systems (WFMSs) can be used to re-engineer, streamline, automate, and track organizational processes involving humans and automated information systems. However, the state-of-the-art in workflow technology suffers from a number of limitations that prevent it from being widely used in large-scale mission critical applications. Error handling is one such issue. What makes the task of error handling challenging is the need to deal with errors that appear in various components of a complex distributed application execution environment, including various WFMS components, workflow application tasks of different types, and the heterogeneous computing infrastructure.

In this paper, we discuss a top-down …

Simulation Of Living Processes Utilizing Concurrency And Object-Oriented Programming, Aaron Ziegler

Honors Theses, 1963-2015

What does it mean to be alive? Is it possible to create artificial life-forms that are truly alive? Can a computer program be alive? To answer these questions, I first explore the history of artificial life, beginning with John von Neumann, who designed algorithms possessing lifelike capabilities, and moving on to other famous attempts, such as Horton Conway's 'Game of Life', and Thomas Ray's remarkable 'Tierra' project.

Also included is a discussion on the merits of Object-Oriented programming for simulating, and ultimately synthesizing life on a computer. concurrency is defined, and its value for stimulating and synthesizing life is made …

A Look At Kabbalah, Scott M. Wellman

Honors Theses, 1963-2015

No abstract provided.

A Feedback Control Structure For On-Line Learning Tasks, Manfred Huber, Roderic Grupen

Roderic Grupen

This paper addresses adaptive control architectures for systems that respond autonomously to changing tasks. Such systems often have many sensory and motor alternatives and behavior drawn from these produces varying quality solutions. The objective is then to ground behavior in control laws which, combined with resources, enumerate closed-loop behavioral alternatives. Use of such controllers leads to analyzable and predictable composite system, permitting the construction of abstract behavioral models. Here, discrete event system and reinforcement learning techniques are employed to constrain the behavioral alternatives and to synthesize behavior on-line. To illustrate this, a quadruped

Learning To Coordinate Controllers -- Reinforcement Learning On A Control Basis, Manfred Huber, Roderic Grupen

Roderic Grupen

Autonomous robot systems operating in an uncertain environment have to be reactive and adaptive in order to cope with changing environment conditions and task requirements. To achieve this, the hybrid control architecture presented in this paper uses reinforcement learning on top of a Discrete Event Dynamic System (DEDS) framework to learn to supervise a set of basis controllers in order to achieve a given task. The use of an abstract system model in the automatically derived supervisor reduces the complexity of the learning problem. In addition, safety constraints may be imposed a priori, such that the system learns on-line in …

The Brain As A Symbol-Processing Machine., Armando F. Rocha

Armando F Rocha

The knowledge accumulated about the biochemistry of the synapsis in the last decades completely changes the notion of brain processing founded exclusively over an electrical mechanism, toward that supported by a complex chemical message exchange occurring both locally, at the synaptic site, as well as at other localities, depending on the solubility of the involved chemical substances in the extracellular compartment. These biochemical transactions support a rich symbolic processing of the information both encoded by the genes and provided by actual data collected from the surrounding environment, by means of either special molecular or cellular receptor systems. In this processing, …

Learning In A Fuzzy Logic Robot Controller, Doug Blank, J. O. Ross

Computer Science Faculty Research and Scholarship

No abstract provided.

Incorporating A Connectionist Vision Module Into A Fuzzy, Behavior-Based Robot Controller, Doug Blank, J. Oliver Ross

Computer Science Faculty Research and Scholarship

This paper describes the initial steps required to incorporate an artificial neural network vision module into an established fuzzy logic, behavior-based mobile robot and controller. This efficient and robust method is demonstrated to show its effectiveness in simple real-world environments.

Random Walks On Wheels, Matthew Lee, Mark Stamp

Faculty Publications, Computer Science

Suppose two particles occupy distinct vertices of a wheel graph and at each step the two particles move independently to adjacent vertices. In this paper we find the expected number of moves until the particles land on the same vertex.

A One-Pass Algorithm For Accurately Estimating Quantiles For Disk-Resident Data, Khaled Alsabti, Sanjay Ranka, Vineet Singh

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

The '-quantile of an ordered sequence of data values is the element with rank ' \Theta n, where n is the total number of values. Accurate estimates of quantiles are required for the solution of many practical applications. In this paper, we present a new algorithm for estimating the quantile values for disk-resident data. Our algorithm has the following characteristics: (1) It requires only one pass over the data; (2) It is deterministic; (3) It produces good lower and upper bounds of the true values of the quantiles; (4) It requires no a priori knowledge of the distribution of the …

A Load Balancing Technique For Multiphase Computations, Jerrell Watts, Marc Rieffel, Stephen Taylor

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

Parallel computations comprised of multiple, tightly interwoven phases of computation may require a different approach to dynamic load balancing than single-phase computations. This paper presents a load sharing method based on the view of load as a vector, rather than as a scalar. This approach allows multiphase computations to achieve higher efficiency on large-scale multicomputers than possible with traditional techniques. Results are presented for two large-scale particle simulations running on 128 nodes of an Intel Paragon and on 256 processors of a Cray T3D, respectively.

Semantics Vs. Syntax Vs. Computations: Machine Models For Type-2 Polynomial-Time Bounded Functionals, James S. Royer

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

This paper investigates analogs of the Kreisel-Lacombe-Shoenfield Theorem in the context of the type-2 basic feasible functionals. We develop a direct, polynomial-time analog of effective operation in which the time bounding on computations is modeled after Kapron and Cook's scheme for their basic polynomial-time functionals. We show that if P = NP, these polynomial-time effective operations are strictly more powerful on R (the class of recursive functions) than the basic feasible functions. We also consider a weaker notion of polynomial-time effective operation where the machines computing these functionals have access to the computations of their procedural parameter, but not to …

Concurrent Simulation Of Plasma Reactors, Marc Rieffel, Stephen Taylor, Jerrell Watts, Sadasivan Shankar

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

This paper summarizes the computational techniques behind a novel concurrent simulation method used for studying the neutral flow inside plasma reactors. The technique is intended to cope with low pressure flow (less than 1.5 Torr) in realistic three-dimensional geometries. It is based on the Direct Simulation Monte Carlo method to accurately model rarefied gas flow. The concurrent formulation operates on a broad variety of shared-memory multiprocessors, multicomputers, and networked workstations.

Practical Algorithms For Selection On Coarse-Grained Parallel Computers, Ibraheem Al-Furaih, Srinivas Aluru, Sanjay Goil, Sanjay Ranka

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

In this paper, we consider the problem of selection on coarse-grained distributed memory parallel computers. We discuss several deterministic and randomized algorithms for parallel selection. We also consider several algorithms for load balancing needed to keep a balanced distribution of data across processors during the execution of the selection algorithms. We have carried out detailed implementations of all the algorithms discussed on the CM-5 and report on the experimental results. We demonstrate that the randomized algorithms are superior to their deterministic counterparts.

Integer Sorting Algorithms For Coarse-Grained Parallel Machines, Khaled Alsabti, Sanjay Ranka

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

Integer sorting is a subclass of the sorting problem where the elements have integer values and the largest element is polynomially bounded in the number of elements to be sorted. It is useful for applications in which the size of the maximum value of element to be sorted is bounded. In this paper, we present a new distributed radix-sort algorithm for integer sorting. The structure of our algorithm is similar to radix sort except that it typically requires less number of communication phases. We present experimental results for our algorithm on two distributed memory multiprocessors, the Intel Paragon and the …