Computer Sciences Commons^™

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We give algorithms to minimize density for channels with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, previous results for running time and space are improved by a factor of L/lg n and L , respectively, where L is the channel length and n is the number of terminals.

Matching Points To Lines: Sonar-Based Localization For The Psubot, Kevin Blythe Stanton

Dissertations and Theses

The PSUBOT (pronounced pea-es-you-bought) is an autonomous wheelchair robot for persons with certain disabilities. Its use of voice recognition and autonomous navigation enable it to carry out high level commands with little or no user assistance. We first describe the goals, constraints, and capabilities of the overall system including path planning and obstacle avoidance. We then focus on localization-the ability of the robot to locate itself in space. Odometry, a compass, and an algorithm which matches points to lines are each employed to accomplish this task. The matching algorithm (which matches "points" to "lines") is the main contribution to this …

The Ksr1: Experimentation And Modeling Of Poststore, Amy Apon, E Rosti, E Smirni, T D. Wagner, M Madhukar, L W. Dowdy

Publications

Kendall Square Research introduced the KSRl system in 1991. The architecture is based on a ring of rings of 64bit microprocessors. It is a distributed, shared memory system and is scalable. The memory structure is unique and is the key to understanding the system. Different levels of caching eliminates physical memory addressing and leads to the ALLCACHE TM scheme. Since requested data may be found in any of several caches, the initial access time is variable. Once pulled into the local (sub)cache, subsequent access times are fixed and minimal. Thus, the KSRl is a Cache-Only Memory Architecture (COMA) system. This …

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

BITs and PCs Newsletter

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

A Generalization Of The Trie Data Structure, Richard H. Connelly, F. Lockwood Morris

Electrical Engineering and Computer Science - Technical Reports

Tries, a form of string-indexed look-up structure, are generalized to permit indexing by terms built according to an arbitrary signature. The construction is parametric with respect to the type of data to be stored as values; this is essential, because the recursion which defines tries appeals from one value type to others. "Trie" (for any fixed signature) is then a functor, and the corresponding look-up function is a natural isomorphism. The trie functor is in principle definable by the "initial fixed point" semantics of Smyth and Plotkin. We simplify the construction, however, by introducing the "category-cpo", a class of category …

Graphical Evolution Experiments In Artificial Life, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

Larry Yaeger's alife simulation running on a Silicon Graphics Iris Workstation is called Poly World. Our description of PolyWorld is based on notes taken during an oral presentation and video demonstration given in the Artificial Life Panel Session of SIGGRAPH '92: In PolyWorld the visual organisms roam on a bounded two dimensional grid. The organisms "brains" are small neural nets enabling the organisms to control their external visual appearance and to perceive the external world by processing pixmaps. The simulation controls for total energy while striving to explore competition and self-organization. Genes present are for size, strength, maximum speed, mutation …

Decentralized Global Transaction Management In Multidatabase Systems, Aidong Zhang, Jiansan Chen, Ahmed K. Elmagarmid, Omran Bukhres

Department of Computer Science Technical Reports

No abstract provided.

Symbolic Methods In Computer Graphics And Geometric Modeling (Ph.D. Thesis), Andrew Vasanth Royappa

Department of Computer Science Technical Reports

No abstract provided.

Rowdlas User's Guide, H. Byun, Elias N. Houstis, E. A. Vavalis

Department of Computer Science Technical Reports

No abstract provided.

An Interactive X-Window Based User Interface For The Xox Solid Modeling Library, Poting Wu, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.

New Algorithms For Minimizing The Longest Wire Length During Circuit Compaction, Susanne E. Hambrusch, Hung-Yi Tu

Department of Computer Science Technical Reports

No abstract provided.

A Sign-To-Speech Translation System, Koka Veera Raghava Rao

School of Computing: Dissertations, Theses, and Student Research

This thesis describes sign-to-speech translation using neural networks. Sign language translation is an interesting but difficult problem for which neural network techniques seem promising because of their ability to adjust to the user's hand movements, which is not possible to do by most other techniques. However, even using neural networks and artificial sign languages, the translation is hard, and the best-known system, that of Fels & Hinton (1993), is capable of translating only 66 root words and 203 words including their conjugations. This research improves their results to 790 root signs and 2718 words including their conjugations while preserving a …

A Petri Net Toolkit For Parallel Program Debugging, Potla Kishore Reddy

Theses

An effective debugger must support the language and operating system resource abstractions that are available to the programmer. Earlier debuggers worked at the machine architecture level: they dealt with machine instructions and registers. Current debuggers, designed for single process debugging, permit access to program variables and breakpoints and single-stepping at the level of high-level language statements. Eventhough the current debuggers, are already implemented to be a powerful tool, they still cannot do a job of parallel debugger.

In this thesis, a computer simulation system has been established by Petri Nets execution providing a convenient and friendly interface as it allows …

A Comparison Of Integration Architectures, Amar Mahidadia

Theses

This paper presents GenSIF, a Generic Systems Integration Framework. GenSIF features a pre-planned development process on a domain-wide basis and facilitates system integration and project coordination for very large, complex and distributed systems. Domain analysis, integration architecture design and infrastructure design are identified as the three main components of GenSIF. In the next step we map Beilcore's OSCA interoperability architecture, ANSA, IBM's SAA and Bull's DCM into GenSIF. Using the GenSIF concepts we compare each of these architectures.

GenSIF serves as a general framework to evaluate and position specific architecture. The OSCA architecture is used to discuss the impact of …

Protocol Conformance Test Generation Using Circular Uio With Overlapping, Sesharao Patchipala

Theses

The purpose of the protocol conformance testing is to ensure that protocol implementations are consistent with their specifications. After the U-method was introduced, several test methods based on the Unique Input/Output (UI0) sequences which were the main concept in the U-method have been proposed, namely, the RCP-method, MUIO-method, MUIO with overlapping method, B-method, C-method. A good test sequence must be short and have wide fault coverage. By comparing the test sequences generated by the above test methods based on experimental results, reveals that the test sequences by the MUIO with overlapping method are the worst in quality but their lengths …

Computer Implementation Of Mason's Rule And Software Development Of Stochastic Petri Nets, Xiaoyong Zhao

Theses

A symbolic performance analysis approach for discrete event systems can be formulated based on the integration of Petri nets and Moment Generating Function concepts [1-3]. The key steps in the method include modeling a system with arbitrary stochastic Petri nets (ASPN), generation of state machine Petri nets with transfer functions, derivation of equivalent transfer functions, and symbolic derivation of transfer functions to obtain the performance measures. Since Mason's rule can be used to effectively derive the closed-form transfer function, its computer implementation plays a very important role in automating the above procedure. This thesis develops the computer implementation of Mason's …

An Enhancement And Improvement Of A Prototype Distributed System Based On Elements Of An Integration Architecture, Kunal R. Shah

Theses

The concepts and results presented in this thesis are related to Integrated System Development. It provides introduction to Generic System Integration Framework (GenSIF). And hence its three principal components, Domain Analysis, Integration Architectures and Enabling Technology. It addresses certain issues of distributed processing relating to systems integration.

The primary objective of this thesis is to develop/improve a prototype by applying concepts and ideas presented in GenSIF, with an example channel based building block integration architecture as an example. This prototype was developed with the objective of studying the effect of system intregration framework in mind while working on an application. …

Systems Integration In Pharmaceutical Industry Using Object-Oriented Expert System Technology, Korrapolu Reddy

Theses

SPHINX is an object-oriented expert system addressed to solve the burning problems of pharmaceutical industry. SPHINX stands for Systems integration in PHarmaceutical INdustry using object-oriented eXpert system technology.

Various problems that American pharmaceutical industries are facing have been explained. Using the revolutionary object-oriented concepts and the powerful expert systems technology, it has been shown how a prescription can be written to solve all the problems of pharmaceutical industries. A problem "Minimizing the wastage of Interferon" has been taken to demonstrate the power of Object-oriented Expert System technology.

Genetic Algorithms For Vertex Splitting In Dags, Matthias Mayer, Fikret ErçAl

Computer Science Technical Reports

Directed Acyclic Graphs are often used to model circuits and networks. The path length in such Directed Acyclic Graphs represents circuit or network delays. In the vertex splitting problem, the objective is to determine a minimum number of vertices from the graph to split such that the resulting graph has no path of length greater than a given δ. The problem has been proven to be NP-hard. A Genetic Algorithm is used to solve the DAG Vertex Splitting Problem. This approach uses a variable string length to represent the vertices that split the graph and a dynamic population size. The …

Intermediate Code Generation For Portable Scalable, Compilers. Architecture Independent Data Parallelism: The Preliminaries, Lenore Mullin, C. Chang, S. Huang, Matthias Mayer, N. Nemer, C. Ramakrishna

Computer Science Technical Reports

This paper introduces the goals of the Portable, Scalable, Architecture Independent (PSI) Compiler Project for Data Parallel Languages at the University of Missouri-Rolla. A goal of this project is to produce a subcompiler for data parallel scientific programming languages such as HPF(High Performance Fortran) where the input grammar is translated to a three-address code intermediate language. Ultimately we plan to integrate our work into automated synthesis systems for scientific programming because we feel that it should not be necessary to learn complicated programming techniques to use multiprocessor computers or networks of computers effectively. This paper shows how to compile a …

Modeling Of Supersonic Combustor Flows Using Parallel Computing, Bruce M. Mcmillin, Eric Jui-Lin Lu, Larry Reeves

Computer Science Technical Reports

Computational Fluid Dynamics (CFD) has matured rapidly in the past 20 years and is now an important tool for analyzing and understanding complex fluid flows. Since 1985, CFD has played a vital role in the study of hypersonic flight. It has provided the capability for scientists and engineers to model both internal and external hypersonic flow-fields. Such flows are often impractical or impossible to analyze in laboratory conditions. In particular, the recent application of CFD to the modeling of internal reacting supersonic combustor flows has significantly advanced the understanding of such flows and has increased confidence in the predictive ability …

The Computation Of Supersonic Combustor Flows Using Multi-Computers, Bruce M. Mcmillin, Eric Jui-Lin Lu, Larry Reeves

Computer Science Technical Reports

An explicit computational fluid dynamics (CFD) computer code with parallel processing capability has been developed for the purpose of simulating internal high-speed reacting flows. The code solves the three-dimensional Navier-Stokes equations for compressible flows. The CFD code can be executed on either sequential (single processor) computers or multi-computers (multiple processor machines with distributed memory and message passing between processors). The parallel implementation involves homogeneous domain decomposition between processors with message passing needed only between neighbor processors. The code is validated for a compression ramp, an expansion ramp, a viscous flat plate, and a viscous flat plate with wall injection. These …

How To Program In Ccsp, Elizabeth Arrowsmith, Bruce M. Mcmillin

Computer Science Technical Reports

No abstract provided.

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

BITs and PCs Newsletter

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

Emergent Control And Planning In An Autonomous Vehicle, Lisa Meeden, Gary Mcgraw, Doug Blank

Computer Science Faculty Research and Scholarship

No abstract provided.

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

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

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.

Static And Runtime Scheduling Of Unstructured Communication, Sanjay Ranka, Jyu-Chun Wang

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. All-to-many communication is required for solving a large class of irregular and loosely synchronous problems on distributed memory MIMD machines. In this paper we present several algorithms for decomposing all-to-many personalized communication into a set of disjoint partial permutations. These partial permutations avoid node contention and/or link contention. We discuss several algorithms and study their effectiveness both from the view of static scheduling as …

Solving The Region Growing Problem On The Connection Machine, Nawal Copty, Sanjay Ranka, Geoffrey C. Fox, Ravi Shankar

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

This paper presents a parallel algorithm for solving the region growing problem based on the split and merge approach. The algorithm was implemented on the CM-2 and the CM-5 in the data parallel and message passing models. The performance of these implementations is examined and compared.

Architectural Support For High-Performance Distributed Computing, Jongbaek Park, Salim Hariri

Electrical Engineering and Computer Science - All Scholarship

The emergence of high speed networks and the proliferation of high performance workstations have attracted a lot of interest in workstation-based distributed computing. Current trend in local area networks is toward higher communication bandwidth as we progress from Ethernet networks that operate at 10 Mbit/sec to higher speed networks that can operate in Gbit/sec range. Also, current workstations are capable of delivering tens and hundreds of Megaflops of computing power. By using a cluster of such high-performance workstations and the high-speed networks, a high-performance distributed computing environment could be built in cost-effective manner as an alternative of supercomputing platform. However, …

Formal Method For Scheduling, Routing And Communication Protocol, Lenore Mullin, S. A. Thibault, D. R. Dooling, E. A. Sandberg

Computer Science Faculty Research & Creative Works

The PRAM model has been shown to be an optimal design for emulating both loose and tightly coupled multiprocessors for unit time operations. When virtual processors are required, multiplexing work to available processors is employed. This introduces a form of latency incurred by operating system overhead. Further complications arise when bandwidth creates bottlenecking of work units. G.E. Blelloch (1989) showed how to add parallel prefix operations (scans) to an extended PRAM model which uses unit step, not time operations. This paper shows how the psi) calculus can be used to group work units, i.e., pipelining the work units, so that …